Obtain the subset of a directed graph reaching a given node with SQL

Question

I have a directed graph in a Postgres database defined with these relations:

CREATE TABLE node (
    id int4 NOT NULL,
    "name" varchar NULL,
    CONSTRAINT pk_node PRIMARY KEY (id),
    CONSTRAINT unq_node_name UNIQUE ("name"),
);

CREATE TABLE link (
    id int4 NOT NULL,
    "name" varchar NULL,
    id_node_from int4 NULL,
    id_node_to int4 NULL,
    CONSTRAINT pk_link PRIMARY KEY (id),
    CONSTRAINT unq_link_name UNIQUE ("name"),
    CONSTRAINT fk_link_node_from FOREIGN KEY (id_node_from) REFERENCES node(id),
    CONSTRAINT fk_link_node_to FOREIGN KEY (id_node_to) REFERENCES node(id)
);

Given a node n, I would like to obtain the set of nodes from which it is possible to reach n traversing the directed graph.

How can it be made with a single SQL query?

I think you're after a recursive cte. Example: http://stackoverflow.com/questions/25754366/recursive-query-challenge-simple-parent-child-example or http://stackoverflow.com/questions/53108/is-it-possible-to-make-a-recursive-sql-query (note the highest upvoted answer) or even http://stackoverflow.com/questions/30336265/postgresql-recursive-cte-results-ordering — xQbert, Aug 16 '16 at 12:52
xQbert: I know how to achieve this with a function (stored procedure). I am wondering if it can be made with a recursive SQL query - they are not too hard with trees, but so far I failed to do it with a directed graph. — Luís de Sousa, Aug 16 '16 at 13:13

score 1 · Accepted Answer · answered Aug 16 '16 at 20:44

Here you have query which lists all noncyclic graph paths:

with recursive path(id_from, id_to, path, cycle) as (
    select 
      l.id_node_from, l.id_node_to, array[l.id_node_from, l.id_node_to], false 
    from link l
  union all
    select
      p.id_from, l.id_node_to, p.path || l.id_node_to, l.id_node_to = any(p.path)
    from link l
    join path p on l.id_node_from = p.id_to and not cycle
)
select * from path;

Apply some additional condition to the final select * from path, join node and

Given a node n, I would like to obtain the set of nodes from which it is possible to reach n traversing the directed graph.

voila!

Side note: it is taken (and slightly adjusted) from https://www.postgresql.org/docs/current/static/queries-with.html . Have you tried looking there first ;) ?

`and not cycle` - that is the bit I was missing. – Luís de Sousa Aug 17 '16 at 08:23 — Luís de Sousa, Aug 17 '16 at 08:23

Obtain the subset of a directed graph reaching a given node with SQL

1 Answers1