30.2. Paths in a Graph

Finding a path in a graph is the most important commercial application of graphs. Graphs model transportation networks, electrical and cable systems, process control flow and thousands of other things.

A path, P, of length L from a node n0 to a node nk in the graph is defined as a traversal of (L + 1) contiguous nodes along a sequence of edges, where the first node is node number 0 and the last is node number k.

CREATE VIEW Paths (begin_node_id, end_node_id, this_node_id, seq_nbr, begin_lft, begin_rgt, end_lft, end_rgt, this_lft, this_rgt) AS SELECT PE.begin_node_id, PE.end_node_id, G1.node_id, (SELECT COUNT(*) FROM NestedSetsGraph AS G2 WHERE G2.lft > PE.begin_lft AND G2.lft <= G1.lft AND G2.rgt >= G1.rgt), PE.begin_lft, ...

Get Joe Celko's SQL for Smarties, 3rd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.