fmcquillan99 edited a comment on issue #486: Graph: Filter out infinite paths URL: https://github.com/apache/madlib/pull/486#issuecomment-596027308 (1) SSSP - filter out infinite paths ``` 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); ``` Note that vertex 7 is disconnect from the rest of the graph ^^^ ``` DROP TABLE IF EXISTS out, out_summary; SELECT madlib.graph_sssp( 'vertex', -- Vertex table NULL, -- Vertex 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 rows) ``` Note that `id=7` has no row ^^^ OK Now check path to 7: ``` DROP TABLE IF EXISTS out_path; SELECT madlib.graph_sssp_get_path('out',7, 'out_path'); ERROR: plpy.Error: Graph SSSP: Vertex 7 is not present in the SSSP table out (plpython.c:5038) CONTEXT: Traceback (most recent call last): PL/Python function "graph_sssp_get_path", line 21, in <module> return sssp.graph_sssp_get_path(**globals()) PL/Python function "graph_sssp_get_path", line 507, in graph_sssp_get_path PL/Python function "graph_sssp_get_path" ``` OK (2) APSP - filter out infinite paths ``` DROP TABLE IF EXISTS out, out_summary; SELECT madlib.graph_apsp( 'vertex', -- Vertex table NULL, -- Vertix id column (NULL means use default naming) 'edge', -- Edge table NULL, -- Edge arguments (NULL means use default naming) 'out'); -- Output table of shortest paths select * from out order by src, dest; src | dest | weight | parent -----+------+--------+-------- 0 | 0 | 0 | 0 0 | 1 | 1 | 1 0 | 2 | 1 | 2 0 | 3 | 2 | 2 0 | 4 | 10 | 4 0 | 5 | 2 | 2 0 | 6 | 3 | 5 1 | 0 | 4 | 3 1 | 1 | 0 | 1 1 | 2 | 2 | 2 1 | 3 | 3 | 2 1 | 4 | 14 | 0 1 | 5 | 3 | 2 1 | 6 | 4 | 5 2 | 0 | 2 | 3 2 | 1 | 3 | 0 2 | 2 | 0 | 2 2 | 3 | 1 | 3 2 | 4 | 12 | 0 2 | 5 | 1 | 5 2 | 6 | 2 | 5 3 | 0 | 1 | 0 3 | 1 | 2 | 0 3 | 2 | 2 | 0 3 | 3 | 0 | 3 3 | 4 | 11 | 0 3 | 5 | 3 | 2 3 | 6 | 4 | 5 4 | 0 | -2 | 0 4 | 1 | -1 | 0 4 | 2 | -1 | 0 4 | 3 | 0 | 2 4 | 4 | 0 | 4 4 | 5 | 0 | 2 4 | 6 | 1 | 5 5 | 5 | 0 | 5 5 | 6 | 1 | 6 6 | 6 | 0 | 6 (38 rows) ``` Note that `id=7` has no row ^^^ OK Now try to get path to 7: ``` DROP TABLE IF EXISTS out_path; SELECT madlib.graph_apsp_get_path('out',0,7,'out_path'); ERROR: plpy.Error: Graph APSP: Vertex 0 and/or 7 is not present in the APSP table 7 (plpython.c:5038) CONTEXT: Traceback (most recent call last): PL/Python function "graph_apsp_get_path", line 21, in <module> return apsp.graph_apsp_get_path(**globals()) PL/Python function "graph_apsp_get_path", line 533, in graph_apsp_get_path PL/Python function "graph_apsp_get_path" ``` OK (3) Make BFS output match SSSP and APSP ``` DROP TABLE IF EXISTS vertex, edge; CREATE TABLE vertex( id INTEGER ); CREATE TABLE edge( src INTEGER, dest INTEGER ); INSERT INTO vertex VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11); INSERT INTO edge VALUES (0, 5), (1, 0), (1, 3), (2, 6), (3, 4), (3, 5), (4, 2), (8, 9), (9, 10), (9, 11), (10, 8); DROP TABLE IF EXISTS out, out_summary; SELECT madlib.graph_bfs( 'vertex', -- Vertex table NULL, -- Vertix id column (NULL means use default naming) 'edge', -- Edge table NULL, -- Edge arguments (NULL means use default naming) 3, -- Source vertex for BFS 'out'); -- Output table of nodes reachable from source_vertex -- Default values used for the other arguments SELECT * FROM out ORDER BY dist,id; id | dist | parent ----+------+-------- 3 | 0 | 3 1 | 1 | 3 4 | 1 | 3 5 | 1 | 3 0 | 2 | 1 2 | 2 | 4 6 | 3 | 2 (7 rows) ``` Note BFS now has output similar to SSSP & APSP with the "self" row included with `dist=0` ^^^ OK This PR LGTM
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services
