Add support for multigraphs to nx.bridges. (#5397)

Adds support for multigraphs to the nx.bridges function.

Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

2 files changed, 26 insertions, 6 deletions

diff --git a/networkx/algorithms/bridges.py b/networkx/algorithms/bridges.py
index 5788e8fe..959a67fe 100644
--- a/networkx/algorithms/bridges.py
+++ b/networkx/algorithms/bridges.py
@@ -7,14 +7,14 @@ from networkx.utils import not_implemented_for
 __all__ = ["bridges", "has_bridges", "local_bridges"]
 
 
-@not_implemented_for("multigraph")
 @not_implemented_for("directed")
 def bridges(G, root=None):
     """Generate all bridges in a graph.
 
     A *bridge* in a graph is an edge whose removal causes the number of
     connected components of the graph to increase.  Equivalently, a bridge is an
-    edge that does not belong to any cycle.
+    edge that does not belong to any cycle. Bridges are also known as cut-edges,
+    isthmuses, or cut arcs.
 
     Parameters
     ----------
@@ -45,10 +45,14 @@ def bridges(G, root=None):
 
     Notes
     -----
-    This is an implementation of the algorithm described in _[1].  An edge is a
+    This is an implementation of the algorithm described in [1]_.  An edge is a
     bridge if and only if it is not contained in any chain. Chains are found
     using the :func:`networkx.chain_decomposition` function.
 
+    The algorithm described in [1]_ requires a simple graph. If the provided
+    graph is a multigraph, we convert it to a simple graph and verify that any
+    bridges discovered by the chain decomposition algorithm are not multi-edges.
+
     Ignoring polylogarithmic factors, the worst-case time complexity is the
     same as the :func:`networkx.chain_decomposition` function,
     $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is
@@ -58,14 +62,17 @@ def bridges(G, root=None):
     ----------
     .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions
     """
-    chains = nx.chain_decomposition(G, root=root)
+    multigraph = G.is_multigraph()
+    H = nx.Graph(G) if multigraph else G
+    chains = nx.chain_decomposition(H, root=root)
     chain_edges = set(chain.from_iterable(chains))
-    for u, v in G.edges():
+    for u, v in H.edges():
         if (u, v) not in chain_edges and (v, u) not in chain_edges:
+            if multigraph and len(G[u][v]) > 1:
+                continue
             yield u, v
 
 
-@not_implemented_for("multigraph")
 @not_implemented_for("directed")
 def has_bridges(G, root=None):
     """Decide whether a graph has any bridges.
diff --git a/networkx/algorithms/tests/test_bridges.py b/networkx/algorithms/tests/test_bridges.py
index 8f6b0a87..059cf3da 100644
--- a/networkx/algorithms/tests/test_bridges.py
+++ b/networkx/algorithms/tests/test_bridges.py
@@ -37,6 +37,19 @@ class TestBridges:
         bridges = list(nx.bridges(G, source))
         assert bridges == [(2, 3)]
 
+    def test_multiedge_bridge(self):
+        edges = [
+            (0, 1),
+            (0, 2),
+            (1, 2),
+            (1, 2),
+            (2, 3),
+            (3, 4),
+            (3, 4),
+        ]
+        G = nx.MultiGraph(edges)
+        assert list(nx.bridges(G)) == [(2, 3)]
+
 
 class TestLocalBridges:
     """Unit tests for the local_bridge function."""