dtEzFHiz

1/*
2       +1
3       |
4       |A
5   B   |
63+-----+2
7 |     |
8 |     |
9C|     |E
10 |     |
114+-----+5
12   D   |
13       |F
14       |
15   G   |
16 7+----+6
17  |    |I
18  |H   |
19  \----+8
20       |
21       | J
22       |
23       +9
24       |
25       |K
26       |
27       +10
28
29*/ 
30
31
32drop table if exists graph;
33create table graph (
34id serial
35, node_start int
36, node_end int
37, nam varchar
38);
39
40insert into graph (node_start, node_end, nam)
41values ( 1, 2, 'A'), (2, 3, 'B'), (3, 4, 'C'), (4, 5, 'D'), (2, 5, 'E'), (5, 6, 'F'), (6, 7, 'G'), (7, 8, 'H'), (6, 8, 'I'), (8, 9, 'J'), (9, 10, 'K');
42
43select * from graph;
44
45-- parcours du graphe de A a K
46-- on ne garde que les identifiants et on a seulement un union pour dédoublonner
47with recursive search_graph (id, node_end, nam) as (
48
49select g.id, g.node_end, g.nam from graph as g where nam = 'A'
50union 
51select g.id, g.node_end, g.nam from search_graph as sg join graph as g on sg.node_end = g.node_start
52) 
53select * from search_graph limit 100;
54-- ok on a bien nos 11 lignes
55
56-- on cherche maintenant a garder le path parcouru
57with recursive search_graph (id, node_end, nam, path, depth) as (
58
59select g.id, g.node_end, g.nam, ARRAY[g.nam] as path, 1 as depth from graph as g where nam = 'A'
60-- le union je joue plus son role car on a le path qui est distinct
61-- on pourrait garder union all ( meme effet), mais pour avoir les memes resultats il faut dedoublonner
62union 
63select g.id, g.node_end, g.nam, sg.path || g.nam as path, depth + 1 as depth from search_graph as sg join graph as g on sg.node_end = g.node_start
64) 
65select * from search_graph limit 100;
66
67-- la methode qu'on s'ettendrait a voir fonctionner
68with recursive search_graph (id, node_end, nam, path, depth) as (
69
70select g.id, g.node_end, g.nam, ARRAY[g.nam] as path, 1 as depth from graph as g where nam = 'A'
71-- le union je joue plus son role car on a le path qui est distinct
72union 
73-- dans la ligne suivante : ERROR:  recursive reference to query "search_graph" must not appear within a subquery
74-- on a une erreur aussi si utiliser une structure "left join is null" car la CTE recursive ne peut pas etre utilisee dans une jointure externe
75select g.id, g.node_end, g.nam, sg.path || g.nam as path, depth + 1 as depth from search_graph as sg join graph as g on sg.node_end = g.node_start and g.id not in (select id from search_graph)
76) 
77select * from search_graph limit 100;