Linear Time Bridge Detection

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