Finding the paths in a directed cyclic graph
Before trying the code in this section, make sure that you have created the "edges" table (see cr-edges.sql) and installed all the code shown in the section Common code for traversing all kinds of graph.
First, define a suitable constraint on the "edges" table for representing a directed cyclic graph and populate the table with the data that represents the graph shown in the Directed cyclic graph section.
delete from edges;
alter table edges drop constraint if exists edges_chk cascade;
alter table edges add constraint edges_chk check(node_1 <> node_2);
insert into edges(node_1, node_2) values
('n2', 'n1'),
('n2', 'n4'),
('n4', 'n5'),
('n4', 'n6'),
('n6', 'n4'),
('n5', 'n6'),
('n5', 'n3'),
('n3', 'n2');
Now reinstate the implementation of "find_paths()" shown at cr-find-paths-with-nocycle-check.sql.
Find all the paths from "n2" and create the filtered subset of shortest paths to the distinct terminal nodes:
call find_paths(start_node => 'n2');
call restrict_to_shortest_paths('raw_paths', 'shortest_paths');
Look at the "raw_paths":
\t on
select t from list_paths('raw_paths');
\t off
This is the result:
path # cardinality path
------ ----------- ----
1 2 n2 > n1
2 2 n2 > n4
3 3 n2 > n4 > n5
4 3 n2 > n4 > n6
5 4 n2 > n4 > n5 > n3
6 4 n2 > n4 > n5 > n6
Look at the "filtered_paths":
\t on
select t from list_paths('shortest_paths');
\t off
This is the result:
path # cardinality path
------ ----------- ----
1 2 n2 > n1
2 2 n2 > n4
3 3 n2 > n4 > n5
4 3 n2 > n4 > n6
5 4 n2 > n4 > n5 > n3