Enumerating all paths in a directed acyclic graph

Enumerating All Paths in a Directed Acyclic Graph (DAG)

Learn how to systematically find and list every possible path from a source node to a destination node in a Directed Acyclic Graph (DAG) using depth-first search (DFS).

Directed Acyclic Graphs (DAGs) are fundamental data structures used in various fields, from task scheduling and dependency management to data processing pipelines. A common problem when working with DAGs is enumerating all possible paths between two given nodes. This article will guide you through the process of finding every unique path from a specified source node to a target node within a DAG, primarily using a Depth-First Search (DFS) approach.

Understanding Directed Acyclic Graphs (DAGs)

A Directed Acyclic Graph is a graph where all edges point in one direction (directed) and contain no cycles (acyclic). The 'acyclic' property is crucial because it guarantees that a path will never revisit a node, simplifying path enumeration as we don't need to worry about infinite loops. Each edge (u, v) indicates that there is a direct connection from node u to node v.

graph TD
    A[Start] --> B(Task 1)
    A --> C(Task 2)
    B --> D(Task 3)
    C --> D
    D --> E[End]
    C --> F(Task 4)
    F --> E

Example of a Directed Acyclic Graph (DAG)

The Depth-First Search (DFS) Approach

Depth-First Search is a natural fit for path enumeration. It explores as far as possible along each branch before backtracking. When applied to finding all paths, DFS systematically traverses the graph, keeping track of the current path. When the destination node is reached, the current path is recorded. If a dead end is encountered or the destination is not reachable from the current node, the algorithm backtracks to explore other branches.

Algorithm Steps for Path Enumeration

The core idea is to use a recursive DFS function. This function will take the current node, the destination node, the graph representation (adjacency list), and the current path being built as arguments. When the current node matches the destination, the path is complete and added to a list of all found paths.

1. Initialize Data Structures

Create an adjacency list to represent the graph. Initialize an empty list to store all found paths and an empty list to store the current path during traversal.

2. Define DFS Function

Implement a recursive dfs(currentNode, destinationNode, graph, currentPath, allPaths) function. This function will append currentNode to currentPath.

3. Base Case: Destination Reached

If currentNode is equal to destinationNode, a complete path has been found. Add a copy of currentPath to allPaths.

4. Recursive Step: Explore Neighbors

For each neighbor of currentNode in the graph's adjacency list, recursively call dfs(neighbor, destinationNode, graph, currentPath, allPaths).

5. Backtrack

After exploring all neighbors of currentNode (and their subsequent paths), remove currentNode from currentPath to backtrack and allow exploration of other branches.

6. Initiate Search

Call the dfs function with the sourceNode, destinationNode, graph, and initial empty path lists.

Python

def find_all_paths_dfs(graph, start, end): all_paths = [] current_path = []

def dfs(node):
    current_path.append(node)
    if node == end:
        all_paths.append(list(current_path)) # Add a copy of the current path
    else:
        for neighbor in graph.get(node, []):
            dfs(neighbor)
    current_path.pop() # Backtrack

dfs(start)
return all_paths

Example Usage:

graph = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'F'], 'D': ['E'], 'F': ['E'] }

start_node = 'A' end_node = 'E' paths = find_all_paths_dfs(graph, start_node, end_node) print(f"All paths from {start_node} to {end_node}: {paths}")

Expected output: [['A', 'B', 'D', 'E'], ['A', 'C', 'D', 'E'], ['A', 'C', 'F', 'E']]

JavaScript

function findAllPathsDFS(graph, start, end) { const allPaths = []; const currentPath = [];

function dfs(node) {
    currentPath.push(node);
    if (node === end) {
        allPaths.push([...currentPath]); // Add a copy of the current path
    } else {
        const neighbors = graph[node] || [];
        for (const neighbor of neighbors) {
            dfs(neighbor);
        }
    }
    currentPath.pop(); // Backtrack
}

dfs(start);
return allPaths;

}

// Example Usage: const graph = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'F'], 'D': ['E'], 'F': ['E'] };

const startNode = 'A'; const endNode = 'E'; const paths = findAllPathsDFS(graph, startNode, endNode); console.log(All paths from ${startNode} to ${endNode}:, paths); // Expected output: [ [ 'A', 'B', 'D', 'E' ], [ 'A', 'C', 'D', 'E' ], [ 'A', 'C', 'F', 'E' ] ]