docs/v1.10/group__grp__sssp.html - madlib-site - Git at Google

 <!-- HTML header for doxygen 1.8.4-->
 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
 <html xmlns="http://www.w3.org/1999/xhtml">
 <head>
 <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
 <meta http-equiv="X-UA-Compatible" content="IE=9"/>
 <meta name="generator" content="Doxygen 1.8.13"/>
 <meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/>
 <title>MADlib: Single Source Shortest Path</title>
 <link href="tabs.css" rel="stylesheet" type="text/css"/>
 <script type="text/javascript" src="jquery.js"></script>
 <script type="text/javascript" src="dynsections.js"></script>
 <link href="navtree.css" rel="stylesheet" type="text/css"/>
 <script type="text/javascript" src="resize.js"></script>
 <script type="text/javascript" src="navtreedata.js"></script>
 <script type="text/javascript" src="navtree.js"></script>
 <script type="text/javascript">
   $(document).ready(initResizable);
 </script>
 <link href="search/search.css" rel="stylesheet" type="text/css"/>
 <script type="text/javascript" src="search/searchdata.js"></script>
 <script type="text/javascript" src="search/search.js"></script>
 <script type="text/javascript">
   $(document).ready(function() { init_search(); });
 </script>
 <!-- hack in the navigation tree -->
 <script type="text/javascript" src="eigen_navtree_hacks.js"></script>
 <link href="doxygen.css" rel="stylesheet" type="text/css" />
 <link href="madlib_extra.css" rel="stylesheet" type="text/css"/>
 <!-- google analytics -->
 <script>
   (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
   (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
   m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
   })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
   ga('create', 'UA-45382226-1', 'madlib.incubator.apache.org');
   ga('send', 'pageview');
 </script>
 </head>
 <body>
 <div id="top"><!-- do not remove this div, it is closed by doxygen! -->
 <div id="titlearea">
 <table cellspacing="0" cellpadding="0">
  <tbody>
  <tr style="height: 56px;">
   <td id="projectlogo"><a href="http://madlib.incubator.apache.org"><img alt="Logo" src="madlib.png" height="50" style="padding-left:0.5em;" border="0"/ ></a></td>
   <td style="padding-left: 0.5em;">
    <div id="projectname">
    <span id="projectnumber">1.10.0</span>
    </div>
    <div id="projectbrief">User Documentation for MADlib</div>
   </td>
    <td>        <div id="MSearchBox" class="MSearchBoxInactive">
         <span class="left">
           <img id="MSearchSelect" src="search/mag_sel.png"
                onmouseover="return searchBox.OnSearchSelectShow()"
                onmouseout="return searchBox.OnSearchSelectHide()"
                alt=""/>
           <input type="text" id="MSearchField" value="Search" accesskey="S"
                onfocus="searchBox.OnSearchFieldFocus(true)"
                onblur="searchBox.OnSearchFieldFocus(false)"
                onkeyup="searchBox.OnSearchFieldChange(event)"/>
           </span><span class="right">
             <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
           </span>
         </div>
 </td>
  </tr>
  </tbody>
 </table>
 </div>
 <!-- end header part -->
 <!-- Generated by Doxygen 1.8.13 -->
 <script type="text/javascript">
 var searchBox = new SearchBox("searchBox", "search",false,'Search');
 </script>
 </div><!-- top -->
 <div id="side-nav" class="ui-resizable side-nav-resizable">
   <div id="nav-tree">
     <div id="nav-tree-contents">
       <div id="nav-sync" class="sync"></div>
     </div>
   </div>
   <div id="splitbar" style="-moz-user-select:none;"
        class="ui-resizable-handle">
   </div>
 </div>
 <script type="text/javascript">
 $(document).ready(function(){initNavTree('group__grp__sssp.html','');});
 </script>
 <div id="doc-content">
 <!-- window showing the filter options -->
 <div id="MSearchSelectWindow"
      onmouseover="return searchBox.OnSearchSelectShow()"
      onmouseout="return searchBox.OnSearchSelectHide()"
      onkeydown="return searchBox.OnSearchSelectKey(event)">
 </div>

 <!-- iframe showing the search results (closed by default) -->
 <div id="MSearchResultsWindow">
 <iframe src="javascript:void(0)" frameborder="0"
         name="MSearchResults" id="MSearchResults">
 </iframe>
 </div>

 <div class="header">
   <div class="headertitle">
 <div class="title">Single Source Shortest Path<div class="ingroups"><a class="el" href="group__grp__graph.html">Graph</a></div></div>  </div>
 </div><!--header-->
 <div class="contents">
 <div class="toc"><b>Contents</b> <ul>
 <li>
 <a href="#sssp">SSSP</a> </li>
 <li>
 <a href="#notes">Notes</a> </li>
 <li>
 <a href="#examples">Examples</a> </li>
 <li>
 <a href="#literature">Literature</a> </li>
 </ul>
 </div><p>Given a graph and a source vertex, the single source shortest path (SSSP) algorithm finds a path from the source vertex to every other vertex in the graph, such that the sum of the weights of the path edges is minimized.</p>
 <p><a class="anchor" id="sssp"></a></p><dl class="section user"><dt>SSSP</dt><dd><pre class="syntax">
 graph_sssp( vertex_table,
             vertex_id,
             edge_table,
             edge_args,
             source_vertex,
             out_table
           )
 </pre></dd></dl>
 <p><b>Arguments</b> </p><dl class="arglist">
 <dt>vertex_table </dt>
 <dd><p class="startdd">TEXT. Name of the table containing the vertex data for the graph. Must contain the column specified in the 'vertex_id' parameter below.</p>
 <p class="enddd"></p>
 </dd>
 <dt>vertex_id </dt>
 <dd><p class="startdd">TEXT, default = 'id'. Name of the column in 'vertex_table' containing vertex ids. The vertex ids are of type INTEGER with no duplicates. They do not need to be contiguous.</p>
 <p class="enddd"></p>
 </dd>
 <dt>edge_table </dt>
 <dd><p class="startdd">TEXT. Name of the table containing the edge data. The edge table must contain columns for source vertex, destination vertex and edge weight. Column naming convention is described below in the 'edge_args' parameter.</p>
 <p class="enddd"></p>
 </dd>
 <dt>edge_args </dt>
 <dd><p class="startdd">TEXT. A comma-delimited string containing multiple named arguments of the form "name=value". The following parameters are supported for this string argument:</p><ul>
 <li>src (INTEGER): Name of the column containing the source vertex ids in the edge table. Default column name is 'src'.</li>
 <li>dest (INTEGER): Name of the column containing the destination vertex ids in the edge table. Default column name is 'dest'.</li>
 <li>weight (FLOAT8): Name of the column containing the edge weights in the edge table. Default column name is 'weight'.</li>
 </ul>
 <p class="enddd"></p>
 </dd>
 <dt>source_vertex </dt>
 <dd><p class="startdd">INTEGER. The source vertex id for the algorithm to start. This vertex id must exist in the 'vertex_id' column of 'vertex_table'.</p>
 <p class="enddd"></p>
 </dd>
 <dt>out_table </dt>
 <dd>TEXT. Name of the table to store the result of SSSP. It will contain a row for every vertex from 'vertex_table' and have the following columns:<ul>
 <li>vertex_id : The id for the destination. Will use the input parameter 'vertex_id' for column naming.</li>
 <li>weight : The total weight of the shortest path from the source vertex to this particular vertex. Will use the input parameter (weight) for column naming.</li>
 <li>parent : The parent of this vertex in the shortest path from source. Will use 'parent' for column naming. </li>
 </ul>
 </dd>
 </dl>
 <dl class="section user"><dt>Path Retrieval</dt><dd></dd></dl>
 <p>The path retrieval function returns the shortest path from the source vertex to a specified desination vertex.</p>
 <pre class="syntax">
 graph_sssp( sssp_table,
             dest_vertex
           )
 </pre><p><b>Arguments</b> </p><dl class="arglist">
 <dt>sssp_table </dt>
 <dd><p class="startdd">TEXT. Name of the table that contains the SSSP output.</p>
 <p class="enddd"></p>
 </dd>
 <dt>dest_vertex </dt>
 <dd>INTEGER. The vertex that will be the destination of the desired path. </dd>
 </dl>
 <p><a class="anchor" id="notes"></a></p><dl class="section user"><dt>Notes</dt><dd></dd></dl>
 <p>The Bellman-Ford algorithm [1] is used to implement SSSP. This algorithm allows negative edges but not negative cycles. In the case of graphs with negative cycles, an error will be given and no output table will be generated.</p>
 <p>Also see the Grail project [2] for more background on graph analytics processing in relational databases.</p>
 <p><a class="anchor" id="examples"></a></p><dl class="section user"><dt>Examples</dt><dd></dd></dl>
 <ol type="1">
 <li>Create vertex and edge tables to represent the graph: <pre class="syntax">
 DROP TABLE IF EXISTS vertex, edge;
 CREATE TABLE vertex(
         id INTEGER
         );
 CREATE TABLE edge(
         src INTEGER,
         dest INTEGER,
         weight FLOAT8
         );
 INSERT INTO vertex VALUES
 (0),
 (1),
 (2),
 (3),
 (4),
 (5),
 (6),
 (7);
 INSERT INTO edge VALUES
 (0, 1, 1.0),
 (0, 2, 1.0),
 (0, 4, 10.0),
 (1, 2, 2.0),
 (1, 3, 10.0),
 (2, 3, 1.0),
 (2, 5, 1.0),
 (2, 6, 3.0),
 (3, 0, 1.0),
 (4, 0, -2.0),
 (5, 6, 1.0),
 (6, 7, 1.0);
 </pre></li>
 <li>Calculate the shortest paths from vertex 0: <pre class="syntax">
 DROP TABLE IF EXISTS out;
 SELECT madlib.graph_sssp(
                          'vertex',      -- Vertex table
                          NULL,          -- Vertix id column (NULL means use default naming)
                          'edge',        -- Edge table
                          NULL,          -- Edge arguments (NULL means use default naming)
                          0,             -- Source vertex for path calculation
                          'out');        -- Output table of shortest paths
 SELECT * FROM out ORDER BY id;
 </pre> <pre class="result">
  id | weight | parent
 ----+--------+--------
   0 |      0 |      0
   1 |      1 |      0
   2 |      1 |      0
   3 |      2 |      2
   4 |     10 |      0
   5 |      2 |      2
   6 |      3 |      5
   7 |      4 |      6
 (8 rows)
 </pre></li>
 <li>Get the shortest path to vertex 6: <pre class="syntax">
 SELECT madlib.graph_sssp_get_path('out',6) AS spath;
 </pre> <pre class="result">
    spath
 -----------
  {0,2,5,6}
 </pre></li>
 <li>Now let's do a similar example except using different column names in the tables (i.e., not the defaults). Create the vertex and edge tables: <pre class="syntax">
 DROP TABLE IF EXISTS vertex_alt, edge_alt;
 CREATE TABLE vertex_alt AS SELECT id AS v_id FROM vertex;
 CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight FROM edge;
 </pre></li>
 <li>Get the shortest path from vertex 1: <pre class="syntax">
 DROP TABLE IF EXISTS out_alt;
 SELECT madlib.graph_sssp(
                          'vertex_alt',                  -- Vertex table
                          'v_id',                        -- Vertix id column (NULL means use default naming)
                          'edge_alt',                    -- Edge table
                          'src=e_src, weight=e_weight',  -- Edge arguments (NULL means use default naming)
                          1,                             -- Source vertex for path calculation
                          'out_alt');                    -- Output table of shortest paths
 SELECT * FROM out_alt ORDER BY v_id;
 </pre> <pre class="result">
  v_id | e_weight | parent
 ------+----------+--------
     0 |        4 |      3
     1 |        0 |      1
     2 |        2 |      1
     3 |        3 |      2
     4 |       14 |      0
     5 |        3 |      2
     6 |        4 |      5
     7 |        5 |      6
 (8 rows)
 </pre></li>
 </ol>
 <p><a class="anchor" id="literature"></a></p><dl class="section user"><dt>Literature</dt><dd></dd></dl>
 <p>[1] Bellman–Ford algorithm. <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm">https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm</a></p>
 <p>[2] The case against specialized graph analytics engines, J. Fan, G. Soosai Raj, and J. M. Patel. CIDR 2015. <a href="http://cidrdb.org/cidr2015/Papers/CIDR15_Paper20.pdf">http://cidrdb.org/cidr2015/Papers/CIDR15_Paper20.pdf</a> </p>
 </div><!-- contents -->
 </div><!-- doc-content -->
 <!-- start footer part -->
 <div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
   <ul>
     <li class="footer">Generated on Fri Mar 10 2017 16:46:57 for MADlib by
     <a href="http://www.doxygen.org/index.html">
     <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.13 </li>
   </ul>
 </div>
 </body>
 </html>
	<!-- HTML header for doxygen 1.8.4-->
	<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
	<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
	<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
	<meta http-equiv="X-UA-Compatible" content="IE=9"/>
	<meta name="generator" content="Doxygen 1.8.13"/>
	<meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/>
	<title>MADlib: Single Source Shortest Path</title>
	<link href="tabs.css" rel="stylesheet" type="text/css"/>
	<script type="text/javascript" src="jquery.js"></script>
	<script type="text/javascript" src="dynsections.js"></script>
	<link href="navtree.css" rel="stylesheet" type="text/css"/>
	<script type="text/javascript" src="resize.js"></script>
	<script type="text/javascript" src="navtreedata.js"></script>
	<script type="text/javascript" src="navtree.js"></script>
	<script type="text/javascript">
	$(document).ready(initResizable);
	</script>
	<link href="search/search.css" rel="stylesheet" type="text/css"/>
	<script type="text/javascript" src="search/searchdata.js"></script>
	<script type="text/javascript" src="search/search.js"></script>
	<script type="text/javascript">
	$(document).ready(function() { init_search(); });
	</script>
	<!-- hack in the navigation tree -->
	<script type="text/javascript" src="eigen_navtree_hacks.js"></script>
	<link href="doxygen.css" rel="stylesheet" type="text/css" />
	<link href="madlib_extra.css" rel="stylesheet" type="text/css"/>
	<!-- google analytics -->
	<script>
	(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]\|\|function(){
	(i[r].q=i[r].q\|\|[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
	m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
	})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
	ga('create', 'UA-45382226-1', 'madlib.incubator.apache.org');
	ga('send', 'pageview');
	</script>
	</head>
	<body>
	<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
	<div id="titlearea">
	<table cellspacing="0" cellpadding="0">
	<tbody>
	<tr style="height: 56px;">
	<td id="projectlogo"><a href="http://madlib.incubator.apache.org"><img alt="Logo" src="madlib.png" height="50" style="padding-left:0.5em;" border="0"/ ></a></td>
	<td style="padding-left: 0.5em;">
	<div id="projectname">
	<span id="projectnumber">1.10.0</span>
	</div>
	<div id="projectbrief">User Documentation for MADlib</div>
	</td>
	<td> <div id="MSearchBox" class="MSearchBoxInactive">
	<span class="left">
	<img id="MSearchSelect" src="search/mag_sel.png"
	onmouseover="return searchBox.OnSearchSelectShow()"
	onmouseout="return searchBox.OnSearchSelectHide()"
	alt=""/>
	<input type="text" id="MSearchField" value="Search" accesskey="S"
	onfocus="searchBox.OnSearchFieldFocus(true)"
	onblur="searchBox.OnSearchFieldFocus(false)"
	onkeyup="searchBox.OnSearchFieldChange(event)"/>
	</span><span class="right">
	<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
	</span>
	</div>
	</td>
	</tr>
	</tbody>
	</table>
	</div>
	<!-- end header part -->
	<!-- Generated by Doxygen 1.8.13 -->
	<script type="text/javascript">
	var searchBox = new SearchBox("searchBox", "search",false,'Search');
	</script>
	</div><!-- top -->
	<div id="side-nav" class="ui-resizable side-nav-resizable">
	<div id="nav-tree">
	<div id="nav-tree-contents">
	<div id="nav-sync" class="sync"></div>
	</div>
	</div>
	<div id="splitbar" style="-moz-user-select:none;"
	class="ui-resizable-handle">
	</div>
	</div>
	<script type="text/javascript">
	$(document).ready(function(){initNavTree('group__grp__sssp.html','');});
	</script>
	<div id="doc-content">
	<!-- window showing the filter options -->
	<div id="MSearchSelectWindow"
	onmouseover="return searchBox.OnSearchSelectShow()"
	onmouseout="return searchBox.OnSearchSelectHide()"
	onkeydown="return searchBox.OnSearchSelectKey(event)">
	</div>

	<!-- iframe showing the search results (closed by default) -->
	<div id="MSearchResultsWindow">
	<iframe src="javascript:void(0)" frameborder="0"
	name="MSearchResults" id="MSearchResults">
	</iframe>
	</div>

	<div class="header">
	<div class="headertitle">
	<div class="title">Single Source Shortest Path<div class="ingroups"><a class="el" href="group__grp__graph.html">Graph</a></div></div> </div>
	</div><!--header-->
	<div class="contents">
	<div class="toc"><b>Contents</b> <ul>
	<li>
	<a href="#sssp">SSSP</a> </li>
	<li>
	<a href="#notes">Notes</a> </li>
	<li>
	<a href="#examples">Examples</a> </li>
	<li>
	<a href="#literature">Literature</a> </li>
	</ul>
	</div><p>Given a graph and a source vertex, the single source shortest path (SSSP) algorithm finds a path from the source vertex to every other vertex in the graph, such that the sum of the weights of the path edges is minimized.</p>
	<p><a class="anchor" id="sssp"></a></p><dl class="section user"><dt>SSSP</dt><dd><pre class="syntax">
	graph_sssp( vertex_table,
	vertex_id,
	edge_table,
	edge_args,
	source_vertex,
	out_table
	)
	</pre></dd></dl>
	<p><b>Arguments</b> </p><dl class="arglist">
	<dt>vertex_table </dt>
	<dd><p class="startdd">TEXT. Name of the table containing the vertex data for the graph. Must contain the column specified in the 'vertex_id' parameter below.</p>
	<p class="enddd"></p>
	</dd>
	<dt>vertex_id </dt>
	<dd><p class="startdd">TEXT, default = 'id'. Name of the column in 'vertex_table' containing vertex ids. The vertex ids are of type INTEGER with no duplicates. They do not need to be contiguous.</p>
	<p class="enddd"></p>
	</dd>
	<dt>edge_table </dt>
	<dd><p class="startdd">TEXT. Name of the table containing the edge data. The edge table must contain columns for source vertex, destination vertex and edge weight. Column naming convention is described below in the 'edge_args' parameter.</p>
	<p class="enddd"></p>
	</dd>
	<dt>edge_args </dt>
	<dd><p class="startdd">TEXT. A comma-delimited string containing multiple named arguments of the form "name=value". The following parameters are supported for this string argument:</p><ul>
	<li>src (INTEGER): Name of the column containing the source vertex ids in the edge table. Default column name is 'src'.</li>
	<li>dest (INTEGER): Name of the column containing the destination vertex ids in the edge table. Default column name is 'dest'.</li>
	<li>weight (FLOAT8): Name of the column containing the edge weights in the edge table. Default column name is 'weight'.</li>
	</ul>
	<p class="enddd"></p>
	</dd>
	<dt>source_vertex </dt>
	<dd><p class="startdd">INTEGER. The source vertex id for the algorithm to start. This vertex id must exist in the 'vertex_id' column of 'vertex_table'.</p>
	<p class="enddd"></p>
	</dd>
	<dt>out_table </dt>
	<dd>TEXT. Name of the table to store the result of SSSP. It will contain a row for every vertex from 'vertex_table' and have the following columns:<ul>
	<li>vertex_id : The id for the destination. Will use the input parameter 'vertex_id' for column naming.</li>
	<li>weight : The total weight of the shortest path from the source vertex to this particular vertex. Will use the input parameter (weight) for column naming.</li>
	<li>parent : The parent of this vertex in the shortest path from source. Will use 'parent' for column naming. </li>
	</ul>
	</dd>
	</dl>
	<dl class="section user"><dt>Path Retrieval</dt><dd></dd></dl>
	<p>The path retrieval function returns the shortest path from the source vertex to a specified desination vertex.</p>
	<pre class="syntax">
	graph_sssp( sssp_table,
	dest_vertex
	)
	</pre><p><b>Arguments</b> </p><dl class="arglist">
	<dt>sssp_table </dt>
	<dd><p class="startdd">TEXT. Name of the table that contains the SSSP output.</p>
	<p class="enddd"></p>
	</dd>
	<dt>dest_vertex </dt>
	<dd>INTEGER. The vertex that will be the destination of the desired path. </dd>
	</dl>
	<p><a class="anchor" id="notes"></a></p><dl class="section user"><dt>Notes</dt><dd></dd></dl>
	<p>The Bellman-Ford algorithm [1] is used to implement SSSP. This algorithm allows negative edges but not negative cycles. In the case of graphs with negative cycles, an error will be given and no output table will be generated.</p>
	<p>Also see the Grail project [2] for more background on graph analytics processing in relational databases.</p>
	<p><a class="anchor" id="examples"></a></p><dl class="section user"><dt>Examples</dt><dd></dd></dl>
	<ol type="1">
	<li>Create vertex and edge tables to represent the graph: <pre class="syntax">
	DROP TABLE IF EXISTS vertex, edge;
	CREATE TABLE vertex(
	id INTEGER
	);
	CREATE TABLE edge(
	src INTEGER,
	dest INTEGER,
	weight FLOAT8
	);
	INSERT INTO vertex VALUES
	(0),
	(1),
	(2),
	(3),
	(4),
	(5),
	(6),
	(7);
	INSERT INTO edge VALUES
	(0, 1, 1.0),
	(0, 2, 1.0),
	(0, 4, 10.0),
	(1, 2, 2.0),
	(1, 3, 10.0),
	(2, 3, 1.0),
	(2, 5, 1.0),
	(2, 6, 3.0),
	(3, 0, 1.0),
	(4, 0, -2.0),
	(5, 6, 1.0),
	(6, 7, 1.0);
	</pre></li>
	<li>Calculate the shortest paths from vertex 0: <pre class="syntax">
	DROP TABLE IF EXISTS out;
	SELECT madlib.graph_sssp(
	'vertex', -- Vertex table
	NULL, -- Vertix id column (NULL means use default naming)
	'edge', -- Edge table
	NULL, -- Edge arguments (NULL means use default naming)
	0, -- Source vertex for path calculation
	'out'); -- Output table of shortest paths
	SELECT * FROM out ORDER BY id;
	</pre> <pre class="result">
	id \| weight \| parent
	----+--------+--------
	0 \| 0 \| 0
	1 \| 1 \| 0
	2 \| 1 \| 0
	3 \| 2 \| 2
	4 \| 10 \| 0
	5 \| 2 \| 2
	6 \| 3 \| 5
	7 \| 4 \| 6
	(8 rows)
	</pre></li>
	<li>Get the shortest path to vertex 6: <pre class="syntax">
	SELECT madlib.graph_sssp_get_path('out',6) AS spath;
	</pre> <pre class="result">
	spath
	-----------
	{0,2,5,6}
	</pre></li>
	<li>Now let's do a similar example except using different column names in the tables (i.e., not the defaults). Create the vertex and edge tables: <pre class="syntax">
	DROP TABLE IF EXISTS vertex_alt, edge_alt;
	CREATE TABLE vertex_alt AS SELECT id AS v_id FROM vertex;
	CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight FROM edge;
	</pre></li>
	<li>Get the shortest path from vertex 1: <pre class="syntax">
	DROP TABLE IF EXISTS out_alt;
	SELECT madlib.graph_sssp(
	'vertex_alt', -- Vertex table
	'v_id', -- Vertix id column (NULL means use default naming)
	'edge_alt', -- Edge table
	'src=e_src, weight=e_weight', -- Edge arguments (NULL means use default naming)
	1, -- Source vertex for path calculation
	'out_alt'); -- Output table of shortest paths
	SELECT * FROM out_alt ORDER BY v_id;
	</pre> <pre class="result">
	v_id \| e_weight \| parent
	------+----------+--------
	0 \| 4 \| 3
	1 \| 0 \| 1
	2 \| 2 \| 1
	3 \| 3 \| 2
	4 \| 14 \| 0
	5 \| 3 \| 2
	6 \| 4 \| 5
	7 \| 5 \| 6
	(8 rows)
	</pre></li>
	</ol>
	<p><a class="anchor" id="literature"></a></p><dl class="section user"><dt>Literature</dt><dd></dd></dl>
	<p>[1] Bellman–Ford algorithm. <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm">https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm</a></p>
	<p>[2] The case against specialized graph analytics engines, J. Fan, G. Soosai Raj, and J. M. Patel. CIDR 2015. <a href="http://cidrdb.org/cidr2015/Papers/CIDR15_Paper20.pdf">http://cidrdb.org/cidr2015/Papers/CIDR15_Paper20.pdf</a> </p>
	</div><!-- contents -->
	</div><!-- doc-content -->
	<!-- start footer part -->
	<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
	<ul>
	<li class="footer">Generated on Fri Mar 10 2017 16:46:57 for MADlib by
	<a href="http://www.doxygen.org/index.html">
	<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.13 </li>
	</ul>
	</div>
	</body>
	</html>