File size: 4,027 Bytes
f911107 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
"""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
|