Recursive CTE Example: Path Enumeration in a Graph

Path enumeration in a graph can be accomplished using recursive Common Table Expressions (CTEs) in SQL. Path enumeration involves finding all possible paths between nodes in a graph. Here’s how you can do it with SQL:

Table Structure

Assume you have a table edges representing the edges of the graph:

sql
CREATE TABLE edges (
    start_node INT,
    end_node INT
);

Sample Data

Here’s some sample data for the edges table:

sql
INSERT INTO edges (start_node, end_node) VALUES
(1, 2),
(1, 3),
(2, 4),
(3, 4),
(4, 5),
(2, 5),
(3, 5);

SQL Query to Enumerate All Paths

To enumerate all paths between nodes using a recursive CTE, you can use the following SQL query. This query will find all possible paths starting from a given node, say 1.

sql
WITH RECURSIVE PathCTE AS (
    -- Anchor member: start with the initial node
    SELECT 
        start_node AS path_start,
        end_node AS path_end,
        CAST(start_node AS VARCHAR(100)) || '->' || CAST(end_node AS VARCHAR(100)) AS path,
        1 AS depth
    FROM 
        edges
    WHERE 
        start_node = 1

    UNION ALL

    -- Recursive member: find the next nodes in the path
    SELECT 
        p.path_start,
        e.end_node AS path_end,
        p.path || '->' || CAST(e.end_node AS VARCHAR(100)) AS path,
        p.depth + 1
    FROM 
        PathCTE p
    INNER JOIN 
        edges e ON p.path_end = e.start_node
)
SELECT 
    path,
    depth
FROM 
    PathCTE
ORDER BY 
    depth, path;

Explanation

1. Anchor Member:

   sql
   SELECT 
       start_node AS path_start,
       end_node AS path_end,
       CAST(start_node AS VARCHAR(100)) || '->' || CAST(end_node AS VARCHAR(100)) AS path,
       1 AS depth
   FROM 
       edges
   WHERE 
       start_node = 1

   This initializes the CTE with paths starting from the initial node (in this case, node 1). The CAST functions are used to concatenate the nodes into a path string.

2. Recursive Member:

   sql
   SELECT 
       p.path_start,
       e.end_node AS path_end,
       p.path || '->' || CAST(e.end_node AS VARCHAR(100)) AS path,
       p.depth + 1
   FROM 
       PathCTE p
   INNER JOIN 
       edges e ON p.path_end = e.start_node

   This part of the CTE extends the paths by joining the current path’s end node with the start node of the next edge. It concatenates the next node to the path string and increments the depth.

3. Final Select:

   sql
   SELECT 
       path,
       depth
   FROM 
       PathCTE
   ORDER BY 
       depth, path;

   This selects and orders the paths by depth and then by the path string.

Result

The result will be a table listing all possible paths starting from node 1, along with their respective depths:

 path             | depth
------------------|-------
 1->2             |     1
 1->3             |     1
 1->2->4          |     2
 1->2->5          |     2
 1->3->4          |     2
 1->3->5          |     2
 1->2->4->5       |     3
 1->3->4->5       |     3