# 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
``````