aJFUUG9r

1/*
2We consider an oriented graph, with nodes ("+" : numbers) and arcs ( "-" : letters). Each arc is oriented from lowest node id to highest node id.
3We want to follow the graph from node 1 to node 10, propagating through all arcs, and keeping all arcs just once in our results.
4We want to keep the paths which we followed to each new visited arc.
5
6The graph : 
7
8       +1
9       |
10       |A
11   B   |
123+-----+2
13 |     |
14 |     |
15C|     |E
16 |     |
174+-----+5
18   D   |
19       |F
20       |
21   G   |
22 7+----+6
23  |    |I
24  |H   |
25  \----+8
26       |
27       | J
28       |
29       +9
30       |
31       |K
32       |
33       +10
34
35Expected result : 
36A
37A-B
38A-E
39A-B-C
40A-E-F
41A-B-C-D
42A-E-F-G
43A-E-F-I
44A-E-F-G-H
45A-E-F-I-J
46A-E-F-I-J-K
47( 11 rows )
48*/ 
49
50/* create our graph table */
51
52drop table if exists graph;
53create table graph (
54id serial
55, node_start int
56, node_end int
57, nam varchar
58);
59
60/* insert the data corresponding to the graph above */
61insert into graph (node_start, node_end, nam)
62values ( 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');
63
64/* check data */
65select * from graph;
66
67-- Follow the graph from 1 to 10 ( arc A to K )
68-- We only keep node identifiers and use union to deduplicate
69
70with recursive search_graph (id, node_end, nam) as (
71select g.id, g.node_end, g.nam from graph as g where nam = 'A'
72union 
73select g.id, g.node_end, g.nam from search_graph as sg join graph as g on sg.node_end = g.node_start
74) 
75select * from search_graph limit 100;
76-- 11 rows with visited nodes
77
78-- We now want to keep the paths to visited nodes
79with recursive search_graph (id, node_end, nam, path, depth) as (
80-- start data set : arc A
81select g.id, g.node_end, g.nam, ARRAY[g.nam] as path, 1 as depth from graph as g where nam = 'A'
82-- Recursive part
83-- Since the path is distinct for every new line, union does not deduplicate any longer
84-- we have to filter further on each recursion/iteration to deduplicate
85union 
86select 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
87) 
88select * from search_graph limit 100;
89
90-- This is the query we would expect to work
91with recursive search_graph (id, node_end, nam, path, depth) as (
92-- same data set as start : arc A
93select g.id, g.node_end, g.nam, ARRAY[g.nam] as path, 1 as depth from graph as g where nam = 'A'
94-- union does not deduplicate since we have the path
95union 
96-- in the following line, PostgreSQL raises an error :
97-- ERROR:  recursive reference to query "search_graph" must not appear within a subquery
98-- we could also use a "left join is null" structure, but PostgreSQL prevents the recursive CTE to be used in an outer join
99select 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)
100) 
101select * from search_graph limit 100;