Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/tests/test_matching.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Unit tests for the :mod:`networkx.algorithms.bipartite.matching` module.""" | |
2 import itertools | |
3 | |
4 import networkx as nx | |
5 | |
6 import pytest | |
7 | |
8 from networkx.algorithms.bipartite.matching import eppstein_matching | |
9 from networkx.algorithms.bipartite.matching import hopcroft_karp_matching | |
10 from networkx.algorithms.bipartite.matching import maximum_matching | |
11 from networkx.algorithms.bipartite.matching import minimum_weight_full_matching | |
12 from networkx.algorithms.bipartite.matching import to_vertex_cover | |
13 | |
14 | |
15 class TestMatching: | |
16 """Tests for bipartite matching algorithms.""" | |
17 | |
18 def setup(self): | |
19 """Creates a bipartite graph for use in testing matching algorithms. | |
20 | |
21 The bipartite graph has a maximum cardinality matching that leaves | |
22 vertex 1 and vertex 10 unmatched. The first six numbers are the left | |
23 vertices and the next six numbers are the right vertices. | |
24 | |
25 """ | |
26 self.simple_graph = nx.complete_bipartite_graph(2, 3) | |
27 self.simple_solution = {0: 2, 1: 3, 2: 0, 3: 1} | |
28 | |
29 edges = [(0, 7), (0, 8), (2, 6), (2, 9), (3, 8), (4, 8), (4, 9), (5, 11)] | |
30 self.top_nodes = set(range(6)) | |
31 self.graph = nx.Graph() | |
32 self.graph.add_nodes_from(range(12)) | |
33 self.graph.add_edges_from(edges) | |
34 | |
35 # Example bipartite graph from issue 2127 | |
36 G = nx.Graph() | |
37 G.add_nodes_from( | |
38 [ | |
39 (1, "C"), | |
40 (1, "B"), | |
41 (0, "G"), | |
42 (1, "F"), | |
43 (1, "E"), | |
44 (0, "C"), | |
45 (1, "D"), | |
46 (1, "I"), | |
47 (0, "A"), | |
48 (0, "D"), | |
49 (0, "F"), | |
50 (0, "E"), | |
51 (0, "H"), | |
52 (1, "G"), | |
53 (1, "A"), | |
54 (0, "I"), | |
55 (0, "B"), | |
56 (1, "H"), | |
57 ] | |
58 ) | |
59 G.add_edge((1, "C"), (0, "A")) | |
60 G.add_edge((1, "B"), (0, "A")) | |
61 G.add_edge((0, "G"), (1, "I")) | |
62 G.add_edge((0, "G"), (1, "H")) | |
63 G.add_edge((1, "F"), (0, "A")) | |
64 G.add_edge((1, "F"), (0, "C")) | |
65 G.add_edge((1, "F"), (0, "E")) | |
66 G.add_edge((1, "E"), (0, "A")) | |
67 G.add_edge((1, "E"), (0, "C")) | |
68 G.add_edge((0, "C"), (1, "D")) | |
69 G.add_edge((0, "C"), (1, "I")) | |
70 G.add_edge((0, "C"), (1, "G")) | |
71 G.add_edge((0, "C"), (1, "H")) | |
72 G.add_edge((1, "D"), (0, "A")) | |
73 G.add_edge((1, "I"), (0, "A")) | |
74 G.add_edge((1, "I"), (0, "E")) | |
75 G.add_edge((0, "A"), (1, "G")) | |
76 G.add_edge((0, "A"), (1, "H")) | |
77 G.add_edge((0, "E"), (1, "G")) | |
78 G.add_edge((0, "E"), (1, "H")) | |
79 self.disconnected_graph = G | |
80 | |
81 def check_match(self, matching): | |
82 """Asserts that the matching is what we expect from the bipartite graph | |
83 constructed in the :meth:`setup` fixture. | |
84 | |
85 """ | |
86 # For the sake of brevity, rename `matching` to `M`. | |
87 M = matching | |
88 matched_vertices = frozenset(itertools.chain(*M.items())) | |
89 # Assert that the maximum number of vertices (10) is matched. | |
90 assert matched_vertices == frozenset(range(12)) - {1, 10} | |
91 # Assert that no vertex appears in two edges, or in other words, that | |
92 # the matching (u, v) and (v, u) both appear in the matching | |
93 # dictionary. | |
94 assert all(u == M[M[u]] for u in range(12) if u in M) | |
95 | |
96 def check_vertex_cover(self, vertices): | |
97 """Asserts that the given set of vertices is the vertex cover we | |
98 expected from the bipartite graph constructed in the :meth:`setup` | |
99 fixture. | |
100 | |
101 """ | |
102 # By Konig's theorem, the number of edges in a maximum matching equals | |
103 # the number of vertices in a minimum vertex cover. | |
104 assert len(vertices) == 5 | |
105 # Assert that the set is truly a vertex cover. | |
106 for (u, v) in self.graph.edges(): | |
107 assert u in vertices or v in vertices | |
108 # TODO Assert that the vertices are the correct ones. | |
109 | |
110 def test_eppstein_matching(self): | |
111 """Tests that David Eppstein's implementation of the Hopcroft--Karp | |
112 algorithm produces a maximum cardinality matching. | |
113 | |
114 """ | |
115 self.check_match(eppstein_matching(self.graph, self.top_nodes)) | |
116 | |
117 def test_hopcroft_karp_matching(self): | |
118 """Tests that the Hopcroft--Karp algorithm produces a maximum | |
119 cardinality matching in a bipartite graph. | |
120 | |
121 """ | |
122 self.check_match(hopcroft_karp_matching(self.graph, self.top_nodes)) | |
123 | |
124 def test_to_vertex_cover(self): | |
125 """Test for converting a maximum matching to a minimum vertex cover.""" | |
126 matching = maximum_matching(self.graph, self.top_nodes) | |
127 vertex_cover = to_vertex_cover(self.graph, matching, self.top_nodes) | |
128 self.check_vertex_cover(vertex_cover) | |
129 | |
130 def test_eppstein_matching_simple(self): | |
131 match = eppstein_matching(self.simple_graph) | |
132 assert match == self.simple_solution | |
133 | |
134 def test_hopcroft_karp_matching_simple(self): | |
135 match = hopcroft_karp_matching(self.simple_graph) | |
136 assert match == self.simple_solution | |
137 | |
138 def test_eppstein_matching_disconnected(self): | |
139 with pytest.raises(nx.AmbiguousSolution): | |
140 match = eppstein_matching(self.disconnected_graph) | |
141 | |
142 def test_hopcroft_karp_matching_disconnected(self): | |
143 with pytest.raises(nx.AmbiguousSolution): | |
144 match = hopcroft_karp_matching(self.disconnected_graph) | |
145 | |
146 def test_issue_2127(self): | |
147 """Test from issue 2127""" | |
148 # Build the example DAG | |
149 G = nx.DiGraph() | |
150 G.add_edge("A", "C") | |
151 G.add_edge("A", "B") | |
152 G.add_edge("C", "E") | |
153 G.add_edge("C", "D") | |
154 G.add_edge("E", "G") | |
155 G.add_edge("E", "F") | |
156 G.add_edge("G", "I") | |
157 G.add_edge("G", "H") | |
158 | |
159 tc = nx.transitive_closure(G) | |
160 btc = nx.Graph() | |
161 | |
162 # Create a bipartite graph based on the transitive closure of G | |
163 for v in tc.nodes(): | |
164 btc.add_node((0, v)) | |
165 btc.add_node((1, v)) | |
166 | |
167 for u, v in tc.edges(): | |
168 btc.add_edge((0, u), (1, v)) | |
169 | |
170 top_nodes = {n for n in btc if n[0] == 0} | |
171 matching = hopcroft_karp_matching(btc, top_nodes) | |
172 vertex_cover = to_vertex_cover(btc, matching, top_nodes) | |
173 independent_set = set(G) - {v for _, v in vertex_cover} | |
174 assert {"B", "D", "F", "I", "H"} == independent_set | |
175 | |
176 def test_vertex_cover_issue_2384(self): | |
177 G = nx.Graph([(0, 3), (1, 3), (1, 4), (2, 3)]) | |
178 matching = maximum_matching(G) | |
179 vertex_cover = to_vertex_cover(G, matching) | |
180 for u, v in G.edges(): | |
181 assert u in vertex_cover or v in vertex_cover | |
182 | |
183 def test_unorderable_nodes(self): | |
184 a = object() | |
185 b = object() | |
186 c = object() | |
187 d = object() | |
188 e = object() | |
189 G = nx.Graph([(a, d), (b, d), (b, e), (c, d)]) | |
190 matching = maximum_matching(G) | |
191 vertex_cover = to_vertex_cover(G, matching) | |
192 for u, v in G.edges(): | |
193 assert u in vertex_cover or v in vertex_cover | |
194 | |
195 | |
196 def test_eppstein_matching(): | |
197 """Test in accordance to issue #1927""" | |
198 G = nx.Graph() | |
199 G.add_nodes_from(["a", 2, 3, 4], bipartite=0) | |
200 G.add_nodes_from([1, "b", "c"], bipartite=1) | |
201 G.add_edges_from([("a", 1), ("a", "b"), (2, "b"), (2, "c"), (3, "c"), (4, 1)]) | |
202 matching = eppstein_matching(G) | |
203 assert len(matching) == len(maximum_matching(G)) | |
204 assert all(x in set(matching.keys()) for x in set(matching.values())) | |
205 | |
206 | |
207 class TestMinimumWeightFullMatching: | |
208 @classmethod | |
209 def setup_class(cls): | |
210 global scipy | |
211 scipy = pytest.importorskip("scipy") | |
212 | |
213 def test_minimum_weight_full_matching_incomplete_graph(self): | |
214 B = nx.Graph() | |
215 B.add_nodes_from([1, 2], bipartite=0) | |
216 B.add_nodes_from([3, 4], bipartite=1) | |
217 B.add_edge(1, 4, weight=100) | |
218 B.add_edge(2, 3, weight=100) | |
219 B.add_edge(2, 4, weight=50) | |
220 matching = minimum_weight_full_matching(B) | |
221 assert matching == {1: 4, 2: 3, 4: 1, 3: 2} | |
222 | |
223 def test_minimum_weight_full_matching_with_no_full_matching(self): | |
224 B = nx.Graph() | |
225 B.add_nodes_from([1, 2, 3], bipartite=0) | |
226 B.add_nodes_from([4, 5, 6], bipartite=1) | |
227 B.add_edge(1, 4, weight=100) | |
228 B.add_edge(2, 4, weight=100) | |
229 B.add_edge(3, 4, weight=50) | |
230 B.add_edge(3, 5, weight=50) | |
231 B.add_edge(3, 6, weight=50) | |
232 with pytest.raises(ValueError): | |
233 minimum_weight_full_matching(B) | |
234 | |
235 def test_minimum_weight_full_matching_square(self): | |
236 G = nx.complete_bipartite_graph(3, 3) | |
237 G.add_edge(0, 3, weight=400) | |
238 G.add_edge(0, 4, weight=150) | |
239 G.add_edge(0, 5, weight=400) | |
240 G.add_edge(1, 3, weight=400) | |
241 G.add_edge(1, 4, weight=450) | |
242 G.add_edge(1, 5, weight=600) | |
243 G.add_edge(2, 3, weight=300) | |
244 G.add_edge(2, 4, weight=225) | |
245 G.add_edge(2, 5, weight=300) | |
246 matching = minimum_weight_full_matching(G) | |
247 assert matching == {0: 4, 1: 3, 2: 5, 4: 0, 3: 1, 5: 2} | |
248 | |
249 def test_minimum_weight_full_matching_smaller_left(self): | |
250 G = nx.complete_bipartite_graph(3, 4) | |
251 G.add_edge(0, 3, weight=400) | |
252 G.add_edge(0, 4, weight=150) | |
253 G.add_edge(0, 5, weight=400) | |
254 G.add_edge(0, 6, weight=1) | |
255 G.add_edge(1, 3, weight=400) | |
256 G.add_edge(1, 4, weight=450) | |
257 G.add_edge(1, 5, weight=600) | |
258 G.add_edge(1, 6, weight=2) | |
259 G.add_edge(2, 3, weight=300) | |
260 G.add_edge(2, 4, weight=225) | |
261 G.add_edge(2, 5, weight=290) | |
262 G.add_edge(2, 6, weight=3) | |
263 matching = minimum_weight_full_matching(G) | |
264 assert matching == {0: 4, 1: 6, 2: 5, 4: 0, 5: 2, 6: 1} | |
265 | |
266 def test_minimum_weight_full_matching_smaller_top_nodes_right(self): | |
267 G = nx.complete_bipartite_graph(3, 4) | |
268 G.add_edge(0, 3, weight=400) | |
269 G.add_edge(0, 4, weight=150) | |
270 G.add_edge(0, 5, weight=400) | |
271 G.add_edge(0, 6, weight=1) | |
272 G.add_edge(1, 3, weight=400) | |
273 G.add_edge(1, 4, weight=450) | |
274 G.add_edge(1, 5, weight=600) | |
275 G.add_edge(1, 6, weight=2) | |
276 G.add_edge(2, 3, weight=300) | |
277 G.add_edge(2, 4, weight=225) | |
278 G.add_edge(2, 5, weight=290) | |
279 G.add_edge(2, 6, weight=3) | |
280 matching = minimum_weight_full_matching(G, top_nodes=[3, 4, 5, 6]) | |
281 assert matching == {0: 4, 1: 6, 2: 5, 4: 0, 5: 2, 6: 1} | |
282 | |
283 def test_minimum_weight_full_matching_smaller_right(self): | |
284 G = nx.complete_bipartite_graph(4, 3) | |
285 G.add_edge(0, 4, weight=400) | |
286 G.add_edge(0, 5, weight=400) | |
287 G.add_edge(0, 6, weight=300) | |
288 G.add_edge(1, 4, weight=150) | |
289 G.add_edge(1, 5, weight=450) | |
290 G.add_edge(1, 6, weight=225) | |
291 G.add_edge(2, 4, weight=400) | |
292 G.add_edge(2, 5, weight=600) | |
293 G.add_edge(2, 6, weight=290) | |
294 G.add_edge(3, 4, weight=1) | |
295 G.add_edge(3, 5, weight=2) | |
296 G.add_edge(3, 6, weight=3) | |
297 matching = minimum_weight_full_matching(G) | |
298 assert matching == {1: 4, 2: 6, 3: 5, 4: 1, 5: 3, 6: 2} | |
299 | |
300 def test_minimum_weight_full_matching_negative_weights(self): | |
301 G = nx.complete_bipartite_graph(2, 2) | |
302 G.add_edge(0, 2, weight=-2) | |
303 G.add_edge(0, 3, weight=0.2) | |
304 G.add_edge(1, 2, weight=-2) | |
305 G.add_edge(1, 3, weight=0.3) | |
306 matching = minimum_weight_full_matching(G) | |
307 assert matching == {0: 3, 1: 2, 2: 1, 3: 0} | |
308 | |
309 def test_minimum_weight_full_matching_different_weight_key(self): | |
310 G = nx.complete_bipartite_graph(2, 2) | |
311 G.add_edge(0, 2, mass=2) | |
312 G.add_edge(0, 3, mass=0.2) | |
313 G.add_edge(1, 2, mass=1) | |
314 G.add_edge(1, 3, mass=2) | |
315 matching = minimum_weight_full_matching(G, weight="mass") | |
316 assert matching == {0: 3, 1: 2, 2: 1, 3: 0} |