I need your help about the visit of a directed graph stored in a database.
Consider the following directed graph
1->2
2->1,3
3->1
A table stores those relations:
create database test;
\c test;
create table ownership (
parent bigint,
child bigint,
primary key (parent, child)
);
insert into ownership (parent, child) values (1, 2);
insert into ownership (parent, child) values (2, 1);
insert into ownership (parent, child) values (2, 3);
insert into ownership (parent, child) values (3, 1);
I'd like to extract all the semi-connected edges (i.e. the connected edges ignoring the direction) of the graph reachable from a node. I.e., if I start from parent=1, I'd like to have the following output
1,2
2,1
2,3
3,1
I'm using postgresql.
I've modified the example on Postgres' manual which explains recursive queries, and I've adapted the join condition to go "up" and "down" (doing so I ignore the directions). My query is the following one:
\c test
WITH RECURSIVE graph(parent, child, path, depth, cycle) AS (
SELECT o.parent, o.child, ARRAY[ROW(o.parent, o.child)], 0, false
from ownership o
where o.parent = 1
UNION ALL
SELECT
o.parent, o.child,
path||ROW(o.parent, o.child),
depth+1,
ROW(o.parent, o.child) = ANY(path)
from
ownership o, graph g
where
(g.parent = o.child or g.child = o.parent)
and not cycle
)
select g.parent, g.child, g.path, g.cycle
from
graph g
its output follows:
parent | child | path | cycle
--------+-------+-----------------------------------+-------
1 | 2 | {"(1,2)"} | f
2 | 1 | {"(1,2)","(2,1)"} | f
2 | 3 | {"(1,2)","(2,3)"} | f
3 | 1 | {"(1,2)","(3,1)"} | f
1 | 2 | {"(1,2)","(2,1)","(1,2)"} | t
1 | 2 | {"(1,2)","(2,3)","(1,2)"} | t
3 | 1 | {"(1,2)","(2,3)","(3,1)"} | f
1 | 2 | {"(1,2)","(3,1)","(1,2)"} | t
2 | 3 | {"(1,2)","(3,1)","(2,3)"} | f
1 | 2 | {"(1,2)","(2,3)","(3,1)","(1,2)"} | t
2 | 3 | {"(1,2)","(2,3)","(3,1)","(2,3)"} | t
1 | 2 | {"(1,2)","(3,1)","(2,3)","(1,2)"} | t
3 | 1 | {"(1,2)","(3,1)","(2,3)","(3,1)"} | t
(13 rows)
I have a problem: the query extracts the same edges many times, as they are reached through different paths, and I'd like to avoid this. If I modify the outer query into
select distinct g.parent, g.child from graph
I have the desired result, but inefficiencies remain in the WITH query, as unneeded joins are done. So, is there a solution to extract the reachable edges of a graph in a db, starting from a given one, without using distinct?
I also have another problem (this one is solved, look at the bottom): as you can see from the output, cycles stop only when a node is reached for the second time. I.e. I have (1,2) (2,3) (1,2).
I'd like to stop the cycle before cycling over that last node again, i.e. having (1,2) (2,3).
I've tried to modify the where condition as follows
where
(g.parent = o.child or g.child = o.parent)
and (ROW(o.parent, o.child) <> any(path))
and not cycle
to avoid visiting already visited edges, but it doesn't work and I cannot understand why ((ROW(o.parent, o.child) <> any(path)) should avoid cycling before going on the cycled edge again but doesn't work). How can I do to stop cycles one step before the node that closes the cycle?
Edit: as danihp suggested, to solve the second problem I used
where
(g.parent = o.child or g.child = o.parent)
and not (ROW(o.parent, o.child) = any(path))
and not cycle
and now the output contains no cycles. Rows went from 13 to 6, but I still have duplicates, so the main (the first) problem of extracting all the edges without duplicates and without distinct is still alive. Current output with and not ROW
parent | child | path | cycle
--------+-------+---------------------------+-------
1 | 2 | {"(1,2)"} | f
2 | 1 | {"(1,2)","(2,1)"} | f
2 | 3 | {"(1,2)","(2,3)"} | f
3 | 1 | {"(1,2)","(3,1)"} | f
3 | 1 | {"(1,2)","(2,3)","(3,1)"} | f
2 | 3 | {"(1,2)","(3,1)","(2,3)"} | f
(6 rows)
Edit #2:: following what Erwin Brandstetter suggested, I modified my query, but if I'm not wrong, the proposed query gives MORE rows than mine (ROW comparison is still there as it seems more clear to me, even I understood that string comparison will be more efficient). Using the new query, I obtain 20 rows, while mine gives 6 rows
WITH RECURSIVE graph(parent, child, path, depth) AS (
SELECT o.parent, o.child, ARRAY[ROW(o.parent, o.child)], 0
from ownership o
where 1 in (o.child, o.parent)
UNION ALL
SELECT
o.parent, o.child,
path||ROW(o.parent, o.child),
depth+1
from
ownership o, graph g
where
g.child in (o.parent, o.child)
and ROW(o.parent, o.child) <> ALL(path)
)
select g.parent, g.child from graph g
Edit 3: so, as Erwin Brandstetter pointed out, the last query was still wrong, while the right one can be found in his answer.
When I posted my first query, I hadn't understood that I was missing some joins, as it happens in the following case: if I start with the node 3, the db selects the rows (2,3) and (3,1). Then, the first inductive step of the query would select, joining from these rows, the rows (1,2), (2,3) and (3,1), missing the row (2,1) that should be included in the result as conceptually the algorithm would imply ( (2,1) is "near" (3,1) )
When I tried to adapt the example in Postgresql manual, I was right trying to join ownership's parent and child, but I was wrong not saving the value of graph that had to be joined in each step.
These type of queries seem to generate a different set of rows depending on the starting node (i.e. depending on the set of rows selected in the base step). So, I think it could be useful to select just one row containing the starting node in the base step, as you'll get any other "adjacent" node anyway.
and NOT (ROW(o.parent, o.child) = any(path))? Is not enought with:select distinct g.parent, g.child from graph g where cycle = f? – Willful(ROW(o.parent, o.child) <> ALL(path))instead ofNOT (ROW(o.parent, o.child) = ANY(path)). – Falster