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.
graph_sssp( vertex_table, vertex_id, edge_table, edge_args, source_vertex, out_table, grouping_cols )
Arguments
TEXT. Name of the table containing the vertex data for the graph. Must contain the column specified in the 'vertex_id' parameter below.
TEXT, default = 'id'. Name of the column in 'vertex_table' containing vertex ids. The vertex ids can be of type INTEGER or BIGINT with no duplicates. They do not need to be contiguous.
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.
TEXT. A comma-delimited string containing multiple named arguments of the form "name=value". The following parameters are supported for this string argument:
INTEGER or BIGINT. The source vertex id for the algorithm to start. This vertex id must exist in the 'vertex_id' column of 'vertex_table'.
TEXT. Name of the table to store the result of SSSP. It contains a row for every vertex of every group and have the following columns (in addition to the grouping columns):
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.
The path retrieval function returns the shortest path from the source vertex to a specified desination vertex.
graph_sssp_get_path( sssp_table, dest_vertex, path_table )
Arguments
TEXT. Name of the table that contains the SSSP output.
INTEGER or BIGINT. The vertex that will be the destination of the desired path.
TEXT. Name of the output table that contains the path. It contains a row for every group and has the following columns:
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);
DROP TABLE IF EXISTS out, out_summary; 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;
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)
DROP TABLE IF EXISTS out_path; SELECT madlib.graph_sssp_get_path('out',5,'out_path'); SELECT * FROM out_path;
path --------- {0,2,5}
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;
DROP TABLE IF EXISTS out_alt, out_alt_summary; SELECT madlib.graph_sssp( 'vertex_alt', -- Vertex table 'v_id', -- Vertex 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;
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)
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 < 6 AND dest < 6 ); INSERT INTO edge_gr VALUES (4,5,-20,1);
DROP TABLE IF EXISTS out_gr, out_gr_summary; SELECT madlib.graph_sssp( 'vertex', -- Vertex table NULL, -- Vertex id column (NULL means use default naming) 'edge_gr', -- Edge table NULL, -- Edge arguments (NULL means use default naming) 0, -- Source vertex for path calculation 'out_gr', -- Output table of shortest paths 'grp' -- Grouping columns ); SELECT * FROM out_gr ORDER BY grp,id;
grp | id | weight | parent -----+----+--------+-------- 0 | 0 | 0 | 0 0 | 1 | 1 | 0 0 | 2 | 1 | 0 0 | 3 | 2 | 2 0 | 4 | 10 | 0 0 | 5 | 2 | 2 0 | 6 | 3 | 5 0 | 7 | 4 | 6 1 | 0 | 0 | 0 1 | 1 | 1 | 0 1 | 2 | 1 | 0 1 | 3 | 2 | 2 1 | 4 | 10 | 0 1 | 5 | -10 | 4
DROP TABLE IF EXISTS out_gr_path; SELECT madlib.graph_sssp_get_path('out_gr',5,'out_gr_path'); SELECT * FROM out_gr_path ORDER BY grp;
grp | path -----+--------- 0 | {0,2,5} 1 | {0,4,5}
[1] Bellman–Ford algorithm. https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
[2] The case against specialized graph analytics engines, J. Fan, G. Soosai Raj, and J. M. Patel. CIDR 2015. http://cidrdb.org/cidr2015/Papers/CIDR15_Paper20.pdf