You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@madlib.apache.org by GitBox <gi...@apache.org> on 2020/03/07 01:19:03 UTC
[GitHub] [madlib] fmcquillan99 commented on issue #486: Graph: Filter out
infinite paths
fmcquillan99 commented 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 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:
users@infra.apache.org
With regards,
Apache Git Services