Repository: incubator-madlib Updated Branches: refs/heads/master 08ed92661 -> 9e632f1aa
Graph: Minor documentation fixes Project: http://git-wip-us.apache.org/repos/asf/incubator-madlib/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-madlib/commit/9e632f1a Tree: http://git-wip-us.apache.org/repos/asf/incubator-madlib/tree/9e632f1a Diff: http://git-wip-us.apache.org/repos/asf/incubator-madlib/diff/9e632f1a Branch: refs/heads/master Commit: 9e632f1aaa73efcce8475a162ea1d56d81ff2605 Parents: 08ed926 Author: Orhan Kislal <okis...@pivotal.io> Authored: Thu Jun 15 14:22:50 2017 -0700 Committer: Orhan Kislal <okis...@pivotal.io> Committed: Thu Jun 15 14:22:50 2017 -0700 ---------------------------------------------------------------------- src/ports/postgres/modules/graph/apsp.sql_in | 61 ++++++++++++----------- src/ports/postgres/modules/graph/sssp.py_in | 2 +- 2 files changed, 34 insertions(+), 29 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/9e632f1a/src/ports/postgres/modules/graph/apsp.sql_in ---------------------------------------------------------------------- diff --git a/src/ports/postgres/modules/graph/apsp.sql_in b/src/ports/postgres/modules/graph/apsp.sql_in index 41fe3b6..c8df70a 100644 --- a/src/ports/postgres/modules/graph/apsp.sql_in +++ b/src/ports/postgres/modules/graph/apsp.sql_in @@ -42,7 +42,16 @@ m4_include(`SQLCommon.m4') @brief Finds the shortest paths between every vertex pair in a given graph. -The all pairs shortest paths (APSP) algorithm finds the lengths (summed weights) of the shortest paths between all pairs of vertices such that the sum of the weights of the path edges is minimized. +The all pairs shortest paths (APSP) algorithm finds the length (summed weights) +of the shortest paths between all pairs of vertices, such that the sum of the +weights of the path edges is minimized. + +@note APSP is an expensive algorithm for run-time +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. @anchor apsp @par APSP @@ -87,20 +96,20 @@ this string argument: <dd>TEXT. Name of the table to store the result of APSP. It contains a row for every vertex of every group and have the following columns (in addition to the grouping columns): - - source_vertex : The id for the source vertex. Will use the input edge + - source_vertex: The id for the source vertex. Will use the input edge column 'src' for column naming. - - dest_vertex : The id for the destination vertex. Will use the input + - dest_vertex: The id for the destination vertex. Will use the input edge column 'dest' for column naming. - - weight : The total weight of the shortest path from the source vertex to - this particular vertex. Will use the input parameter 'weight' for column + - weight: The total weight of the shortest path from the source vertex to + the destination vertex. Will use the input parameter 'weight' for column naming. - - parent : The parent of the destination vertex in the shortest path from - source. praent will be equal to dest_vertex is there are no more - intermediary vertices. Will use 'parent' for column naming. + - parent: The parent of the destination vertex in the shortest path from + source. Parent will equal dest_vertex if there are no + intermediate vertices. Will use 'parent' for column naming. A summary table named <out_table>_summary is also created. This is an internal table that keeps a record of the input parameters and is used by the path -function described below. +retrieval function described below. </dd> <dt>grouping_cols</dt> @@ -136,10 +145,10 @@ graph_apsp_get_path( apsp_table, <dt>path_table</dt> <dd>TEXT. Name of the output table that contains the path. It contains a row for every group and has the following columns: - - grouping_cols : The grouping columns given in the creation of the APSP + - grouping_cols: The grouping columns given in the creation of the APSP table. If there are no grouping columns, these columns will not exist and the table will have a single row. - - path (ARRAY) : The shortest path from the source vertex to the destination + - path (ARRAY): The shortest path from the source vertex to the destination vertex. </dd> @@ -150,8 +159,9 @@ It contains a row for every group and has the following columns: Graphs with negative edges are supported but graphs with negative cycles are not. -The implementation is analogous to a the matrix multiplication procedure. -Please refer to the design documents, [1] and [2] for more details. +The implementation is analogous to a matrix multiplication procedure. +Please refer to the MADlib design document and references [1] and [2] +for more details. Also see the Grail project [3] for more background on graph analytics processing in relational databases. @@ -224,10 +234,7 @@ SELECT * FROM out ORDER BY src,dest; 1 | 5 | 3 | 2 1 | 6 | 4 | 5 1 | 7 | 5 | 6 - . - . - . -(8 rows) +(showing only 16 of 64 rows) </pre> -# Get the shortest path from vertex 0 to vertex 5: @@ -251,14 +258,14 @@ 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> --# Get the shortest path from vertex 1: +-# Calculate the shortest paths: <pre class="syntax"> DROP TABLE IF EXISTS out_alt, out_alt_summary; SELECT madlib.graph_apsp( 'vertex_alt', -- Vertex table - 'v_id', -- Vertex id column (NULL means use default naming) + 'v_id', -- Vertex id column 'edge_alt', -- Edge table - 'src=e_src, weight=e_weight', -- Edge arguments (NULL means use default naming) + 'src=e_src, weight=e_weight', -- Edge arguments 'out_alt'); -- Output table of shortest paths SELECT * FROM out_alt ORDER BY e_src, dest; </pre> @@ -281,13 +288,10 @@ SELECT * FROM out_alt ORDER BY e_src, dest; 1 | 5 | 3 | 2 1 | 6 | 4 | 5 1 | 7 | 5 | 6 - . - . - . -(8 rows) +(showing only 16 of 64 rows) </pre> --# Create a graph with 2 groups: +-# 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 @@ -300,7 +304,7 @@ INSERT INTO edge_gr VALUES (4,5,-20,1); </pre> --# Find APSP for all groups +-# Find APSP for all groups: <pre class="syntax"> DROP TABLE IF EXISTS out_gr, out_gr_summary; SELECT madlib.graph_apsp( @@ -344,6 +348,7 @@ SELECT * FROM out_gr WHERE src < 2 ORDER BY grp,src,dest; 1 | 1 | 3 | 3 | 2 1 | 1 | 4 | 14 | 0 1 | 1 | 5 | -6 | 4 +(28 rows) </pre> -# Find the path from vertex 0 to vertex 5 in every group @@ -403,8 +408,8 @@ m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_apsp_get_path( apsp_table TEXT, source_vertex INT, - dest_vertex INT, - path_table TEXT + dest_vertex INT, + path_table TEXT ) RETURNS VOID AS $$ PythonFunction(graph, apsp, graph_apsp_get_path) http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/9e632f1a/src/ports/postgres/modules/graph/sssp.py_in ---------------------------------------------------------------------- diff --git a/src/ports/postgres/modules/graph/sssp.py_in b/src/ports/postgres/modules/graph/sssp.py_in index 933623e..4839d2d 100644 --- a/src/ports/postgres/modules/graph/sssp.py_in +++ b/src/ports/postgres/modules/graph/sssp.py_in @@ -721,7 +721,7 @@ INSERT INTO edge VALUES ; -- Compute the SSSP: -DROP TABLE IF EXISTS pagerank_out; +DROP TABLE IF EXISTS out; SELECT madlib.graph_sssp( 'vertex', -- Vertex table 'id', -- Vertix id column
