PostgreSQL requête SQL pour parcourir tout un graphe non orienté et retourner tous les bords trouvé

Question

Je dispose d'un bords table de ma base de données PostgreSQL qui représente les arêtes d'un graphe dirigé, avec deux colonnes: node_from et node_to (la valeur est l'identifiant d'un noeud).

un seul noeud Étant donné (initial_node) Je voudrais pouvoir traverser le graphe entier, mais d'une manière undirected.

Ce que je veux dire est, par exemple pour le graphique suivant:

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

Si initial_node est un dans tous les cas, b, c ou d, je obtiendrait [un, b, c, d].

J'ai utilisé la requête SQL suivante (basée sur 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 

Il a bien fonctionné ... Jusqu'à ce que j'ai eu un cas avec 12 noeuds qui sont tous reliés entre eux, dans toutes les directions (pour chaque paire J'ai les deux (a-> b) et (b-> a)), ce qui rend les boucles de requête indéfiniment. (La modification de UNION ALL en UNION n'élimine pas la boucle.)

Quelqu'un a-t-il des conseils pour résoudre ce problème?

Cheers,

Antoine.

Answer 1

je suis arrivé à cela, il ne faut pas entrer dans des boucles infinies avec tout type de données:

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

Les requêtes récursives sont très limitatives en termes de ce qui peut être sélectionné, et qu'ils ne permettent pas l'utilisation les résultats récursifs à l'intérieur d'une sous-sélection, on ne peut pas utiliser NOT IN (sélectionner * dans récursif où ...). Stocker les résultats dans un tableau, en utilisant LEFT JOIN LATERAL et en utilisant = ANY() et <> ALL() a résolu cette énigme.