Fixed unused root argument in has_bridges (#5846)

* Fixed unused root argument in has_bridges

* Verify if root is in graph in chain_decomposition function

* Fix bridges function returning only bridges in connected component of root

* Apply suggestions from code review

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

* Apply suggestions from code review

Co-authored-by: Dan Schult <dschult@colgate.edu>

* Fix bridge test when root is not in G

* Rewrite code to make it more readable

* Add missing tests for chain decomposition and bridges

* Apply suggestions from code review

Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

* Apply suggestions from code review

Co-authored-by: Dan Schult <dschult@colgate.edu>

Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
Co-authored-by: Dan Schult <dschult@colgate.edu>

4 files changed, 74 insertions, 1 deletions

diff --git a/networkx/algorithms/bridges.py b/networkx/algorithms/bridges.py
index eda4a4f6..42e6a8e7 100644
--- a/networkx/algorithms/bridges.py
+++ b/networkx/algorithms/bridges.py
@@ -69,6 +69,9 @@ def bridges(G, root=None):
     H = nx.Graph(G) if multigraph else G
     chains = nx.chain_decomposition(H, root=root)
     chain_edges = set(chain.from_iterable(chains))
+    H_copy = H.copy()
+    if root is not None:
+        H = H.subgraph(nx.node_connected_component(H, root)).copy()
     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:
@@ -128,7 +131,7 @@ def has_bridges(G, root=None):
 
     """
     try:
-        next(bridges(G))
+        next(bridges(G, root=root))
     except StopIteration:
         return False
     else:
diff --git a/networkx/algorithms/chains.py b/networkx/algorithms/chains.py
index 2018c885..53ec84c7 100644
--- a/networkx/algorithms/chains.py
+++ b/networkx/algorithms/chains.py
@@ -141,6 +141,10 @@ def chain_decomposition(G, root=None):
             u, v = v, G.nodes[v]["parent"]
         yield u, v
 
+    # Check if the root is in the graph G. If not, raise NodeNotFound
+    if root is not None and root not in G:
+        raise nx.NodeNotFound(f"Root node {root} is not in graph")
+
     # Create a directed version of H that has the DFS edges directed
     # toward the root and the nontree edges directed away from the root
     # (in each connected component).
diff --git a/networkx/algorithms/tests/test_bridges.py b/networkx/algorithms/tests/test_bridges.py
index 059cf3da..9c3ceba6 100644
--- a/networkx/algorithms/tests/test_bridges.py
+++ b/networkx/algorithms/tests/test_bridges.py
@@ -1,5 +1,7 @@
 """Unit tests for bridge-finding algorithms."""
 
+import pytest
+
 import networkx as nx
 
 
@@ -51,6 +53,61 @@ class TestBridges:
         assert list(nx.bridges(G)) == [(2, 3)]
 
 
+class TestHasBridges:
+    """Unit tests for the has bridges function."""
+
+    def test_single_bridge(self):
+        edges = [
+            # DFS tree edges.
+            (1, 2),
+            (2, 3),
+            (3, 4),
+            (3, 5),
+            (5, 6),  # The only bridge edge
+            (6, 7),
+            (7, 8),
+            (5, 9),
+            (9, 10),
+            # Nontree edges.
+            (1, 3),
+            (1, 4),
+            (2, 5),
+            (5, 10),
+            (6, 8),
+        ]
+        G = nx.Graph(edges)
+        assert nx.has_bridges(G)  # Default root
+        assert nx.has_bridges(G, root=1)  # arbitrary root in G
+
+    def test_has_bridges_raises_root_not_in_G(self):
+        G = nx.Graph()
+        G.add_nodes_from([1, 2, 3])
+        with pytest.raises(nx.NodeNotFound):
+            nx.has_bridges(G, root=6)
+
+    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 nx.has_bridges(G)
+        # Make every edge a multiedge
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        assert not nx.has_bridges(G)
+
+    def test_bridges_multiple_components(self):
+        G = nx.Graph()
+        nx.add_path(G, [0, 1, 2])  # One connected component
+        nx.add_path(G, [4, 5, 6])  # Another connected component
+        assert list(nx.bridges(G, root=4)) == [(4, 5), (5, 6)]
+
+
 class TestLocalBridges:
     """Unit tests for the local_bridge function."""
 
diff --git a/networkx/algorithms/tests/test_chains.py b/networkx/algorithms/tests/test_chains.py
index f8886c97..6a1b1142 100644
--- a/networkx/algorithms/tests/test_chains.py
+++ b/networkx/algorithms/tests/test_chains.py
@@ -1,6 +1,8 @@
 """Unit tests for the chain decomposition functions."""
 from itertools import cycle, islice
 
+import pytest
+
 import networkx as nx
 
 
@@ -129,3 +131,10 @@ class TestChainDecomposition:
         assert len(chains) == len(expected)
         for chain in chains:
             self.assertContainsChain(chain, expected)
+
+    def test_chain_decomposition_root_not_in_G(self):
+        """Test chain decomposition when root is not in graph"""
+        G = nx.Graph()
+        G.add_nodes_from([1, 2, 3])
+        with pytest.raises(nx.NodeNotFound):
+            nx.has_bridges(G, root=6)