PostgreSQL SQL-Abfrage für eine ganze ungerichteten Graphen durchlaufen und alle Kanten Rückkehr gefunden

Question

Ich habe eine Kanten Tabelle in meiner PostgreSQL-Datenbank, die die Kanten eines gerichtet Graph, mit zwei Säulen steht: node_from und node_to (Wert ist die ID eines Knotens).

einen einzelnen Knoten (initial_node) Da ich die gesamte Grafik zu durchqueren können, möchte aber in eine ungerichtete Weise.

Was ich meine ist, zum Beispiel für die folgende Grafik:

(a->b) 
(c->b) 
(c->d) 

Wenn initial_node ist ein, b, c oder d, auf jeden Fall, ich [a, b, c, d].

ich verwendet, um die folgende SQL-Abfrage (basierend auf http://www.postgresql.org/docs/8.4/static/queries-with.html):

WITH RECURSIVE search_graph(uniq, depth, path, cycle) AS (
     SELECT 
      CASE WHEN g.node_from = 'initial_node' THEN g.node_to ELSE g.node_from END, 
      1, 
      CASE WHEN g.node_from = 'initial_node' THEN ARRAY[g.node_from] ELSE ARRAY[g.node_to] END, 
      false 
     FROM edges g 
     WHERE 'initial_node' in (node_from, node_to) 
     UNION ALL 
     SELECT 
      CASE WHEN g.node_from = sg.uniq THEN g.node_to ELSE g.node_from END, 
      sg.depth + 1, 
      CASE WHEN g.node_from = sg.uniq THEN path || g.node_from ELSE path || g.node_to END, 
      g.node_to = ANY(path) OR g.node_from = ANY(path) 
     FROM edges g, search_graph sg 
     WHERE sg.uniq IN (g.node_from, g.node_to) AND NOT cycle 
) 
SELECT * FROM search_graph 

Es funktionierte gut ... Bis ich einen Fall mit 12 Knoten hatte, die alle zusammen in alle Richtungen verbunden sind (für jedes Paar Ich habe beide (a-> b) und (b-> a)), was die Abfrage unendlich lange macht. (Wenn UNION ALL in UNION geändert wird, wird die Schleife nicht gelöscht.)

Hat jemand einen Ratschlag, um dieses Problem zu lösen?

Prost,

Antoine.

Answer 1

ich dazu kam, soll es nicht mit jeder Art von Daten in Endlosschleifen erhalten:

--create temp table edges ("from" text, "to" text); 
--insert into edges values ('initial_node', 'a'), ('a', 'b'), ('a', 'c'), ('c', 'd'); 

with recursive graph(points) as (
    select array(select distinct "to" from edges where "from" = 'initial_node') 
    union all 
    select g.points || e1.p || e2.p 
    from graph g 
    left join lateral (
    select array(
     select distinct "to" 
     from edges 
     where "from" =any(g.points) and "to" <>all(g.points) and "to" <> 'initial_node') AS p) e1 on (true) 
    left join lateral (
    select array(
     select distinct "from" 
     from edges 
     where "to" =any(g.points) and "from" <>all(g.points) and "from" <> 'initial_node') AS p) e2 on (true) 
    where e1.p <> '{}' OR e2.p <> '{}' 
) 
select distinct unnest(points) 
from graph 
order by 1 

rekursive Anfragen in Bezug auf die sehr einschränkend sind, was kann ausgewählt werden, und da sie nicht erlauben, mit die rekursiven Ergebnisse innerhalb eines Subselect, kann man nicht NOT IN (wählen Sie * aus rekursive where ...). Das Speichern von Ergebnissen in einem Array mit LINKER JOIN LATERAL und der Verwendung von = ANY() und <> ALL() löste dieses Rätsel.