A short intro to the BS-DFS algorithm from our preprint:

Frank Bauernöppel, Jörg-Rüdiger Sack; “Enumerating Length-Bounded Simple Paths and Cycles in Directed Graphs with O(k(n+m)) Delay Using Edge-Consistent Node Barriers”

submitted to The Journal of Graph Algorithms and Applications (JGAA).

Basics

A call bsdfs(G, s, t, k) enumerates all simple paths in graph G starting at node s and terminating at node t having at most k edges. For the special case s==t, simple cycles through node s are enumerated, including cycles of length 2, which are excluded in some literature.

For graph terminology, we follow the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. For coding, we use Python and the NetworkX graph library. For simplicity, we consider directed simple graphs (no self-loops, no parallel edges) here, but the algorithm can be adapted to multigraphs and undirected graphs.

Example

With the BS-DFS implementation, the code

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(0,1), (0,2), (1, 2), (2,3), (2,4), (3, 4)])
s = 0
t = 4
k = 3
for path in bsdfs(G, s, t, k):
    print(path)

prints 3 paths:

[0, 1, 2, 4]
[0, 2, 3, 4]
[0, 2, 4]

Path [0, 1, 2, 3, 4] is too long to be reported for k = 3. If we set k = 4, it will be reported as well. The output order depends on the adjacency-list order of the internal graph representation.

Efficiency - The Delay Bounds

The number of length-bounded paths or cycles can grow exponentially in the graph size, even for fixed k. Luckily, bsdfs is implemented as a generator function and can be stopped whenever “enough” paths have been generated. But: how long do we have to wait for the next output or termination?

Let’s call the start, each path generation (output), and the termination the events of a call bsdfs(G, s, t, k). Then, the delay (waiting time between two consecutive events) is bounded by O(k(n+m)). Here, n=|V| is the number of vertices and m=|E| is the number of edges in G. So, for any fixed k, the delay is linear in the graph size.

With a suitable definition of elementary steps (node visit or output, edge scan), the following is proven in our paper:

In benchmark tests, the observed delays were typically well below these theoretical upper bounds.

Motivation

A depth-first search will eventually enumerate all s-t paths or s-cycles. If the search depth is limited to k (see dldfs), length-bounded s-t paths or s-cycles will be enumerated. The problem is that this kind of search recurses over and over again when a node is revisited. For example, let s lie in a large clique from which t is reachable via a single edge (s, t) which comes last in the adjacency list of s. Then all search paths of length ≤ k inside the clique are fruitlessly explored before edge (s, t) is scanned and the path (s, t) is reported. The number of such search paths, and hence the delay until the first output, can be exponential in the clique size.

To avoid repeated fruitless searches, each node x gets a barrier b[x], initially 0, see bbdfs. Let h denote the length of the current search path from s to x. If search(x) finds no path to t, the barrier is raised to b[x] = k - h + 1. When some later search(y) with search path length h' scans the same node x in its successor loop, the entry condition if b[x] + h' < k ensures that search(x) is called only if the new search path length h' + 1 (including x) is smaller than the old length h; i.e. if that later search arrives at x with more budget left to reach t. In this phase barriers only increase. Each node is entered at most k+1 times, so the total work for finding a first path/cycle is bounded by (k+1)(n+m).

The above method works if only the first s-t path P0 of length ≤ k is wanted (or only its existence). Barriers were raised with respect to the then-current search path. When the search backtracks, popped vertices are no longer blocked for a re-visit and a formerly fruitless search may become a fruitful one.

How does bsdfs repair barriers for re-use when more paths than P0 are requested? Resetting all barriers to 0 when a node v is popped keeps the algorithm correct but throws away the work already spent, and the delay bounds no longer hold. Instead, b[v] is set to sd, the length of the shortest path to t found from v with respect to the now-current search path. The barriers of its direct and indirect predecessors are then decreased by walking backwards over in-edges in the fruitful procedure. But only as far as needed to restore edge-consistency, a property defined and discussed in the paper.

BS-DFS in Action

The video shows execution of the following code:

  import networkx as nx
  Z = nx.parse_adjlist(['s a d', 'a c t', 'b a', 'c b z', 'd t z', 'z b c'], create_using=nx.DiGraph)
  list(bsdfs(Z, "s", "t", 5))

BS-DFS in Competition

All three algorithms run on the same input, a small synthetic street graph. All edges are processed in the same adjacency-list order.

dldfs performs depth-first search limited to the depth k. Both bsdfs and bbdfs use barriers for pruning. Therefore, every step executed by either algorithm is also executed by dldfs. When pruning occurs, the algorithm pauses and remains idle until dldfs reaches the corresponding search state. The diagram compares the number of search calls made so far.

Verdict