Finding the paths in a directed acyclic 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 acyclic 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
  ('n1', 'n2'),
  ('n1', 'n3'),
  ('n2', 'n5'),
  ('n2', 'n6'),
  ('n3', 'n6'),
  ('n4', 'n3'),
  ('n4', 'n7'),
  ('n3', 'n7');

Now create a simpler implementation of "find_paths()" that omits the cycle prevention code. (It's derived trivially from the code shown at cr-find-paths-no-nocycle-check.sql.)

cr-find-paths-no-nocycle-check.sql

drop procedure if exists find_paths(text) cascade;

create procedure find_paths(start_node in text)
  language plpgsql
as $body$
begin
  -- See "cr-find-paths-with-pruning.sql". This index demonstrates that
  -- no more than one path has been found to any particular terminal node.
  drop index if exists raw_paths_terminal_unq cascade;
  commit;
  delete from raw_paths;

  with
    recursive paths(path) as (
      select array[start_node, node_2]
      from edges
      where node_1 = start_node

      union all

      select p.path||e.node_2
      from edges e
      inner join paths p on e.node_1 = terminal(p.path)
      )
  insert into raw_paths(path)
  select path
  from paths;
end;
$body$;

Find all the paths from "n1" and create the filtered subset of shortest paths to the distinct terminal nodes:

call find_paths(start_node => 'n1');
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   n1 > n2
      2             2   n1 > n3
      3             3   n1 > n2 > n5
      4             3   n1 > n2 > n6
      5             3   n1 > n3 > n6
      6             3   n1 > n3 > n7

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   n1 > n2
      2             2   n1 > n3
      3             3   n1 > n2 > n5
      4             3   n1 > n2 > n6
      5             3   n1 > n3 > n7

Notice that only the first (in sorting order) of the two paths to the same node, "n1 > n2 > n6" and "n1 > n3 > n6", has been retained.

Finally, add the shortest paths starting at each of the remaining nodes into the "shortest_paths" table and list the final result.

do $body$
declare
  node text not null := '';
begin
  for node in (
    select distinct node_1 from edges
    where node_1 <> 'n1')
  loop
    call find_paths(start_node => node);
    call restrict_to_shortest_paths('raw_paths', 'shortest_paths', append=>true);
  end loop;
end;
$body$;

\t on
select t from list_paths('shortest_paths');
\t off

This is the result:

 path #   cardinality   path
 ------   -----------   ----
      1             2   n1 > n2
      2             2   n1 > n3
      3             3   n1 > n2 > n5
      4             3   n1 > n2 > n6
      5             3   n1 > n3 > n7
      6             2   n2 > n5
      7             2   n2 > n6
      8             2   n3 > n6
      9             2   n3 > n7
     10             2   n4 > n3
     11             2   n4 > n7
     12             3   n4 > n3 > n6