Besorgen Sie sich die Teilmenge eines gerichteten Graphen einen bestimmten Knoten mit SQL

Question

Erreichen

Ich habe ein gerichteter Graph in einer Postgres-Datenbank mit diesen Beziehungen definiert:

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) 
); 

einen Knoten Gegeben n, würde Ich mag das erhalten Satz von Knoten, von denen es möglich ist, n zu erreichen, der den gerichteten Graph durchquert.

Wie kann es mit einer einzigen SQL-Abfrage gemacht werden?

Answer 1

Hier können Sie Abfrage, die alle nicht-zyklische Graph Pfade auflistet:

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; 

Tragen Sie etwas zusätzliche Bedingung der endgültigen select * from path, verbinden node und

einen Knoten n gegeben, würde Ich mag erhalten die Gruppe von Knoten, von der aus es möglich ist, n zu erreichen, die den gerichteten Graphen durchlaufen.

voila!

Seitliche Anmerkung: es ist genommen (und leicht angepasst) von https://www.postgresql.org/docs/current/static/queries-with.html. Hast du schon mal versucht, dort nachzuschauen;)?