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

**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.**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.

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