Finding the paths in a rooted tree

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.

Notice that, because a rooted tree is such a drastically restricted specialization of the general graph, it allows a simpler representation where only the nodes are explicitly represented and where the edges are inferred. This is explained in the section Using a recursive CTE to traverse an employee hierarchy. It's unlikely, therefore, that you'd represent a rooted tree in the way for which the code presented in this section is written. It is, however, important to show that the general approach for graph traversal does indeed handle all the restricted 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 Rooted tree 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
  ('n01', 'n02'),
  ('n01', 'n03'),
  ('n01', 'n04'),
  ('n02', 'n05'),
  ('n02', 'n06'),
  ('n05', 'n11'),
  ('n05', 'n12'),
  ('n03', 'n07'),
  ('n03', 'n08'),
  ('n04', 'n09'),
  ('n04', 'n10'),
  ('n10', 'n13'),
  ('n10', 'n14');

Now re-create the simpler implementation of "find_paths()", shown at cr-find-paths-no-nocycle-check.sql, that omits the cycle prevention code.

Because the root is uniquely defined, it can be determined mechanically. Do this:

do $body$
declare
  root constant text not null := (
    select distinct node_1 from edges
    where node_1 not in (
      select node_2 from edges)
  );
begin
  call find_paths(start_node => root);
end;
$body$;

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

This is the result:

 path #   cardinality   path
 ------   -----------   ----
      1             2   n01 > n02
      2             2   n01 > n03
      3             2   n01 > n04
      4             3   n01 > n02 > n05
      5             3   n01 > n02 > n06
      6             3   n01 > n03 > n07
      7             3   n01 > n03 > n08
      8             3   n01 > n04 > n09
      9             3   n01 > n04 > n10
     10             4   n01 > n02 > n05 > n11
     11             4   n01 > n02 > n05 > n12
     12             4   n01 > n04 > n10 > n13
     13             4   n01 > n04 > n10 > n14

A rooted tree has only one path to any node, so calling the procedure "restrict_to_shortest_paths()" will not remove any paths. Confirm this using the same procedure "assert_shortest_paths_same_as_raw_paths()" that was used in the section How to implement early path pruning to show that the version of "find_paths()" that implements early pruning produces the same set of paths as does the implementation that uses the recursive CTE ordinarily followed by a call to "restrict_to_shortest_paths()":

call restrict_to_shortest_paths('raw_paths', 'shortest_paths');
call assert_shortest_paths_same_as_raw_paths();

The assertion holds.