Linear Time Bridge Detection

January 26, 2020

Fleury’s algorithm is an algorithm for finding an Eulerian path/cycle in an undirected graph. It relies on being able to detect bridges in such a graph. A bridge is an edge, which when deleted, increases the number of connected components. Note that this is distinct from the concept of strongly-connected components, which is relevant only for directed graphs. There is also an algorithm for detecting strong bridges, the removal of which increases the number of strongly-connected components.

This is an implementation of such a bridge-detection algorithm, which uses a single pass of DFS and runs in linear time with respect to the number of edges. I am not sure if it’s similar to Tarjan’s algorithm, since I couldn’t fully understand the description of the algorithm as given on Wikipedia, but the core idea is probably similar.

Imaging doing a pre-order traversal of a given graph, and numbering off each node when you visit it for the first time. pre is a dictionary which stores that numbering. In this context, let’s say a node A is considered earlier than another node B if A’s number is smaller than B’s number.

low, on the other hand, is a dictionary which stores the earliest node that is reachable from a given node, including itself. Note that when considering this, we must be careful to ignore “back” edges. “Back” in this sense of the word refers to a direction that is opposite of the pre-order traversal.

The idea then, of using pre and low, is this:

From a given, earlier, node A, looking at some adjacent, later, neighbour B, if low[B] is equal to pre[B], then the edge A-B is a bridge.

The reason for this is because a bridge is any edge that is not part of a cycle. If, from B, we can reach an earlier node than A, then it means the edge A-B is part of a larger cycle, and therefore not a bridge.

There are only 2 situations we have to consider when looking at the possible values of pre[B]:

  1. It is equal to low[B]. This means that B is either a terminal node, or there exists some cycle that B is a part of, but A is not.
  2. It is lower than low[B]. This means that, aside from actually going backwards through A, its pre-order predecessor, there exists some cycle that connects B eventually back to A. Therefore, the edge A-B is not a cycle.

Let’s take an undirected graph like this for example:

          E
          |
A -- B -- C --- D
     |          |
     ------------

Then pre will be:

pre = {
    'A': 0,
    'B': 1,
    'C': 2,
    'D': 3,
    'E': 4,
}

and low will be:

low = {
    'A': 0,
    'B': 1,
    'C': 1,
    'D': 1,
    'E': 4,
}

Note that low[B] is 1, not 0, even though the graph is supposedly undirected, since B -> A runs opposite to the pre-order traversal.

Here is a complete implementation in Python:

class Graph:
    def __init__(self, connections: List[Tuple[str, str, int]], directed: bool = False):
        self._graph: DefaultDict[str, Dict[str, int]] = defaultdict(lambda: defaultdict(int))
        self._directed = directed
        for c1, c2, weight in connections:
            self.add_edge(c1, c2, weight)
            
    def add_edge(self, start: str, end: str, weight: int):
        self._graph[start][end] = weight
        if not self._directed:
            self._graph[end][start] = weight
        
    def bridge_detection(self) -> List[Tuple[str, str]]:
        bridges = []
        pre: Dict[str, int] = {}
        low: Dict[str, int] = {}
        count = [0] # mimic a mutable integer
        for node in self._graph.keys():
            if node not in pre:
                self.bridge_dfs(bridges, low, pre, count, node, node)
        return bridges

    def bridge_dfs(self, bridges, low, pre, count, u, v):
        # assign a pre-order numbering to this node
        pre[v] = count[0]
        count[0] += 1
        # tentatively assign low[v] to pre[v]
        low[v] = pre[v]
        for neighbour in self._graph[v]:
            # for each neighbour, if they haven't been visited yet
            # visit them
            if neighbour not in pre:
                self.bridge_dfs(bridges, low, pre, count, v, neighbour)
                # if any neighbour has an earlier reachable node, we need to
                # update the parent's one as well
                low[v] = min(low[v], low[neighbour])
                # for any neighbour, if its earliest reachable node is itself
                # then there is no other way to reach the neighbour except from v
                # therefore, the edge from v to this neighbour is a bridge
                if low[neighbour] == pre[neighbour]:
                    bridges.append((v, neighbour))
            # we must ignore "back" edges while iterating over the neighbours
            elif neighbour != u:
                low[v] = min(low[v], low[neighbour])
graph = Graph([
    ('A', 'B', 1),
    ('B', 'C', 1),
    ('C', 'E', 1),
    ('C', 'D', 1),
    ('D', 'B', 1),
])

print(graph.bridge_detection()) # [('A', 'B'), ('C', 'E')]

Using this, the overall running time of Fleury’s algorithm is O(E^2), since every time we traverse and remove the just-traversed edge, we must re-run the bridge detection algorithm. There are faster ways to find Eulerian paths/cycles (see Hierholzer’s algorithm, which runs in overall linear time by exhaustively drawing disjunct cycles).