Incorrect Bridge Computation

[ImmanuelHaffner]

I believe that the computation of bridges (for undirected graphs) is incorrect. I have the following example, where easygraph fails to correctly compute the bridges:

Consider as undirected graph G a clique of size 4, i.e. with 4 nodes [0, 1, 2, 3] and edges [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)].
Then, we remove edges [(0, 1), (0, 2)] by repeatedly calling G.remove_edge(...).
After removing these edges, node 0 will have a single edge (0, 3) connecting it to the remainder of the graph. Hence, edge (0, 3) must be a bridge.
However, computing the bridges with easygraph.bridges(G) returns an emtpy set. This is an error.

Here is a minimal test case:

import easygraph as eg
G = eg.Graph()
G.add_edges([ (0, 3), (1, 2), (1, 3), (2, 3), ])
bridges = eg.bridges(G)
assert (0, 3) in bridges

[ImmanuelHaffner]

FWIW, I implemented bridge computation in Python like this:

def compute_bridges(G :eg.Graph) -> set:
    visited = set()
    bridges = set((e[0], e[1]) for e in G.edges)
    assert eg.is_connected(G), 'graph must be connected'

    def dfs(n :int, path=list()):
        visited.add(n)
        neighbors = set(G.neighbors(n))

        #===== Neighbors in the path (excluding the parent) form back edges and back edges form cycles. =====
        assert neighbors.intersection(visited).issubset(path), 'there can only be back edges to nodes in the path'
        back_edges = neighbors.intersection(path)
        if path:
            back_edges.remove(path[-1]) # exclude parent from back edges

        #===== The back edge to the smallest vertex (w.r.t. DFS numbering) on the path is the largest cycle. =====
        if back_edges:
            idx = next(idx for idx, v in enumerate(path) if v in back_edges) # first vertex in path that is reached by a back edge
            cycle = path[idx:]
            cycle.append(n)
            for i in range(0, len(cycle) - 1):
                bridges.discard((cycle[i], cycle[i+1]))
            bridges.discard((cycle[-1], cycle[0]))

        #===== Recurse =====
        path.append(n)
        for s in neighbors:
            if s not in visited:
                dfs(s, path)
        path.pop()

    dfs(0)
    return bridges

EDIT: Simplified the algorithm.

[yizhihenpidehou]

I believe that the computation of bridges (for undirected graphs) is incorrect. I have the following example, where easygraph fails to correctly compute the bridges:

Consider as undirected graph G a clique of size 4, i.e. with 4 nodes [0, 1, 2, 3] and edges [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]. Then, we remove edges [(0, 1), (0, 2)] by repeatedly calling G.remove_edge(...). After removing these edges, node 0 will have a single edge (0, 3) connecting it to the remainder of the graph. Hence, edge (0, 3) must be a bridge. However, computing the bridges with easygraph.bridges(G) returns an emtpy set. This is an error.

Here is a minimal test case:

import easygraph as eg
G = eg.Graph()
G.add_edges([ (0, 3), (1, 2), (1, 3), (2, 3), ])
bridges = eg.bridges(G)
assert (0, 3) in bridges

Thank you for the test that let us find this problem!!! We have fixed this problem lately😃😃😃

[ImmanuelHaffner]

Thanks for reacting so quickly!
AFAICS, 01831d1 adresses this issue and has already been merged. I guess we can close the issue then.