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