docs/v1.20.0/group__grp__graph__avg__path__length.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: Average Path Length</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>
 <script type="text/x-mathjax-config">
   MathJax.Hub.Config({
     extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
     jax: ["input/TeX","output/HTML-CSS"],
 });
 </script><script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js"></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.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.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.20.0</span>
    </div>
    <div id="projectbrief">User Documentation for Apache 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__graph__avg__path__length.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">Average Path Length<div class="ingroups"><a class="el" href="group__grp__graph.html">Graph</a> &raquo; <a class="el" href="group__grp__graph__measures.html">Measures</a></div></div>  </div>
 </div><!--header-->
 <div class="contents">
 <div class="toc"><b>Contents</b> <ul>
 <li>
 <a href="#avg_path_length">Average Path Length</a> </li>
 <li>
 <a href="#examples">Examples</a> </li>
 </ul>
 </div><p>This function computes the average of the shortest paths between each pair of vertices. Average path length is based on "reachable target vertices", so it ignores infinite-length paths between vertices that are not connected. This means the function will average the path lengths in each connected component. If the user requires the average path length of a particular component, the weakly_connected_components function may be used to isolate the relevant vertices.</p>
 <dl class="section note"><dt>Note</dt><dd>This function assumes a valid output from a prior APSP run - both the APSP table and the associated output summary table. APSP is a computationally expensive algorithm because it finds the shortest path between all nodes in the graph. The worst case run-time for this implementation is O(V^2 * E) where V is the number of vertices and E is the number of edges. In practice, run-time will be generally be much less than this, depending on the graph.</dd></dl>
 <p><a class="anchor" id="avg_path_length"></a></p><dl class="section user"><dt>Average Path Length</dt><dd><pre class="syntax">
 graph_avg_path_length( apsp_table,
                        output_table
                      )
 </pre></dd></dl>
 <p><b>Arguments</b> </p><dl class="arglist">
 <dt>apsp_table </dt>
 <dd><p class="startdd">TEXT. Name of the output table generated by a prior run of all pairs shortest path (APSP). </p>
 <p class="enddd"></p>
 </dd>
 <dt>out_table </dt>
 <dd>TEXT. Name of the table to store the average path length. It contains a row for every group, and the average path value.  </dd>
 </dl>
 <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,
         name TEXT
         );
 CREATE TABLE edge(
         src_id INTEGER,
         dest_id INTEGER,
         edge_weight FLOAT8
         );
 INSERT INTO vertex VALUES
 (0, 'A'),
 (1, 'B'),
 (2, 'C'),
 (3, 'D'),
 (4, 'E'),
 (5, 'F'),
 (6, 'G'),
 (7, 'H');
 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 all-pair shortest paths: <pre class="syntax">
 DROP TABLE IF EXISTS out_apsp, out_apsp_summary;
 SELECT madlib.graph_apsp('vertex',      -- Vertex table
                          'id',          -- Vertix id column (NULL means use default naming)
                          'edge',        -- Edge table
                          'src=src_id, dest=dest_id, weight=edge_weight',
                                         -- Edge arguments (NULL means use default naming)
                          'out_apsp');        -- Output table of shortest paths
 </pre></li>
 <li>Compute the average path length measure: <pre class="syntax">
 DROP TABLE IF EXISTS out_avg_path_length;
 SELECT madlib.graph_avg_path_length('out_apsp', 'out_avg_path_length');
 SELECT * FROM out_avg_path_length;
 </pre> <pre class="result">
  avg_path_length
 ------------------
  2.973684210526316
 (1 row)
 </pre></li>
 <li>Create a graph with 2 groups and find APSP for each group: <pre class="syntax">
 DROP TABLE IF EXISTS edge_gr;
 CREATE TABLE edge_gr AS
 (
   SELECT *, 0 AS grp FROM edge
   UNION
   SELECT *, 1 AS grp FROM edge WHERE src_id &lt; 6 AND dest_id &lt; 6
 );
 INSERT INTO edge_gr VALUES
 (4,5,-20,1);
 </pre></li>
 <li>Find APSP for all groups: <pre class="syntax">
 DROP TABLE IF EXISTS out_gr, out_gr_summary;
 SELECT madlib.graph_apsp(
                          'vertex',      -- Vertex table
                          NULL,          -- Vertex id column (NULL means use default naming)
                          'edge_gr',     -- Edge table
                          'src=src_id, dest=dest_id, weight=edge_weight',
                          'out_gr',      -- Output table of shortest paths
                          'grp'          -- Grouping columns
 );
 </pre></li>
 <li>Find the average path length in every group <pre class="syntax">
 DROP TABLE IF EXISTS out_gr_path;
 SELECT madlib.graph_avg_path_length('out_gr', 'out_gr_path');
 SELECT * FROM out_gr_path ORDER BY grp;
 </pre> <pre class="result">
  grp |  avg_path_length
 ----&mdash;+-------------------&mdash;
    0 |  2.973684210526316
    1 |               0.56
 (2 rows)
 </pre> </li>
 </ol>
 </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 Tue Jul 19 2022 12:19:26 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: Average Path Length</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>
	<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
	extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
	jax: ["input/TeX","output/HTML-CSS"],
	});
	</script><script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js"></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.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.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.20.0</span>
	</div>
	<div id="projectbrief">User Documentation for Apache 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__graph__avg__path__length.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">Average Path Length<div class="ingroups"><a class="el" href="group__grp__graph.html">Graph</a> » <a class="el" href="group__grp__graph__measures.html">Measures</a></div></div> </div>
	</div><!--header-->
	<div class="contents">
	<div class="toc"><b>Contents</b> <ul>
	<li>
	<a href="#avg_path_length">Average Path Length</a> </li>
	<li>
	<a href="#examples">Examples</a> </li>
	</ul>
	</div><p>This function computes the average of the shortest paths between each pair of vertices. Average path length is based on "reachable target vertices", so it ignores infinite-length paths between vertices that are not connected. This means the function will average the path lengths in each connected component. If the user requires the average path length of a particular component, the weakly_connected_components function may be used to isolate the relevant vertices.</p>
	<dl class="section note"><dt>Note</dt><dd>This function assumes a valid output from a prior APSP run - both the APSP table and the associated output summary table. APSP is a computationally expensive algorithm because it finds the shortest path between all nodes in the graph. The worst case run-time for this implementation is O(V^2 * E) where V is the number of vertices and E is the number of edges. In practice, run-time will be generally be much less than this, depending on the graph.</dd></dl>
	<p><a class="anchor" id="avg_path_length"></a></p><dl class="section user"><dt>Average Path Length</dt><dd><pre class="syntax">
	graph_avg_path_length( apsp_table,
	output_table
	)
	</pre></dd></dl>
	<p><b>Arguments</b> </p><dl class="arglist">
	<dt>apsp_table </dt>
	<dd><p class="startdd">TEXT. Name of the output table generated by a prior run of all pairs shortest path (APSP). </p>
	<p class="enddd"></p>
	</dd>
	<dt>out_table </dt>
	<dd>TEXT. Name of the table to store the average path length. It contains a row for every group, and the average path value. </dd>
	</dl>
	<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,
	name TEXT
	);
	CREATE TABLE edge(
	src_id INTEGER,
	dest_id INTEGER,
	edge_weight FLOAT8
	);
	INSERT INTO vertex VALUES
	(0, 'A'),
	(1, 'B'),
	(2, 'C'),
	(3, 'D'),
	(4, 'E'),
	(5, 'F'),
	(6, 'G'),
	(7, 'H');
	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 all-pair shortest paths: <pre class="syntax">
	DROP TABLE IF EXISTS out_apsp, out_apsp_summary;
	SELECT madlib.graph_apsp('vertex', -- Vertex table
	'id', -- Vertix id column (NULL means use default naming)
	'edge', -- Edge table
	'src=src_id, dest=dest_id, weight=edge_weight',
	-- Edge arguments (NULL means use default naming)
	'out_apsp'); -- Output table of shortest paths
	</pre></li>
	<li>Compute the average path length measure: <pre class="syntax">
	DROP TABLE IF EXISTS out_avg_path_length;
	SELECT madlib.graph_avg_path_length('out_apsp', 'out_avg_path_length');
	SELECT * FROM out_avg_path_length;
	</pre> <pre class="result">
	avg_path_length
	------------------
	2.973684210526316
	(1 row)
	</pre></li>
	<li>Create a graph with 2 groups and find APSP for each group: <pre class="syntax">
	DROP TABLE IF EXISTS edge_gr;
	CREATE TABLE edge_gr AS
	(
	SELECT *, 0 AS grp FROM edge
	UNION
	SELECT *, 1 AS grp FROM edge WHERE src_id < 6 AND dest_id < 6
	);
	INSERT INTO edge_gr VALUES
	(4,5,-20,1);
	</pre></li>
	<li>Find APSP for all groups: <pre class="syntax">
	DROP TABLE IF EXISTS out_gr, out_gr_summary;
	SELECT madlib.graph_apsp(
	'vertex', -- Vertex table
	NULL, -- Vertex id column (NULL means use default naming)
	'edge_gr', -- Edge table
	'src=src_id, dest=dest_id, weight=edge_weight',
	'out_gr', -- Output table of shortest paths
	'grp' -- Grouping columns
	);
	</pre></li>
	<li>Find the average path length in every group <pre class="syntax">
	DROP TABLE IF EXISTS out_gr_path;
	SELECT madlib.graph_avg_path_length('out_gr', 'out_gr_path');
	SELECT * FROM out_gr_path ORDER BY grp;
	</pre> <pre class="result">
	grp \| avg_path_length
	----—+-------------------—
	0 \| 2.973684210526316
	1 \| 0.56
	(2 rows)
	</pre> </li>
	</ol>
	</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 Tue Jul 19 2022 12:19:26 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>