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.
graph_avg_path_length( apsp_table, output_table )
Arguments
TEXT. Name of the output table generated by a prior run of all pairs shortest path (APSP).
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);
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
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;
avg_path_length ------------------ 2.973684210526316 (1 row)
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);
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 );
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;
grp | avg_path_length ----—+-------------------— 0 | 2.973684210526316 1 | 0.56 (2 rows)