diff options
author | S. Solomon Darnell | 2025-03-28 21:52:21 -0500 |
---|---|---|
committer | S. Solomon Darnell | 2025-03-28 21:52:21 -0500 |
commit | 4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch) | |
tree | ee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_bridges.py | |
parent | cc961e04ba734dd72309fb548a2f97d67d578813 (diff) | |
download | gn-ai-master.tar.gz |
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_bridges.py')
-rw-r--r-- | .venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_bridges.py | 144 |
1 files changed, 144 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_bridges.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_bridges.py new file mode 100644 index 00000000..b47f5860 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_bridges.py @@ -0,0 +1,144 @@ +"""Unit tests for bridge-finding algorithms.""" + +import pytest + +import networkx as nx + + +class TestBridges: + """Unit tests for the bridge-finding function.""" + + def test_single_bridge(self): + edges = [ + # DFS tree edges. + (1, 2), + (2, 3), + (3, 4), + (3, 5), + (5, 6), + (6, 7), + (7, 8), + (5, 9), + (9, 10), + # Nontree edges. + (1, 3), + (1, 4), + (2, 5), + (5, 10), + (6, 8), + ] + G = nx.Graph(edges) + source = 1 + bridges = list(nx.bridges(G, source)) + assert bridges == [(5, 6)] + + def test_barbell_graph(self): + # The (3, 0) barbell graph has two triangles joined by a single edge. + G = nx.barbell_graph(3, 0) + source = 0 + 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 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.""" + + @classmethod + def setup_class(cls): + cls.BB = nx.barbell_graph(4, 0) + cls.square = nx.cycle_graph(4) + cls.tri = nx.cycle_graph(3) + + def test_nospan(self): + expected = {(3, 4), (4, 3)} + assert next(nx.local_bridges(self.BB, with_span=False)) in expected + assert set(nx.local_bridges(self.square, with_span=False)) == self.square.edges + assert list(nx.local_bridges(self.tri, with_span=False)) == [] + + def test_no_weight(self): + inf = float("inf") + expected = {(3, 4, inf), (4, 3, inf)} + assert next(nx.local_bridges(self.BB)) in expected + expected = {(u, v, 3) for u, v in self.square.edges} + assert set(nx.local_bridges(self.square)) == expected + assert list(nx.local_bridges(self.tri)) == [] + + def test_weight(self): + inf = float("inf") + G = self.square.copy() + + G.edges[1, 2]["weight"] = 2 + expected = {(u, v, 5 - wt) for u, v, wt in G.edges(data="weight", default=1)} + assert set(nx.local_bridges(G, weight="weight")) == expected + + expected = {(u, v, 6) for u, v in G.edges} + lb = nx.local_bridges(G, weight=lambda u, v, d: 2) + assert set(lb) == expected |