Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/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 """Functions for computing and verifying matchings in a graph.""" | |
2 from collections import Counter | |
3 from itertools import combinations | |
4 from itertools import repeat | |
5 | |
6 __all__ = [ | |
7 "is_matching", | |
8 "is_maximal_matching", | |
9 "is_perfect_matching", | |
10 "max_weight_matching", | |
11 "maximal_matching", | |
12 ] | |
13 | |
14 | |
15 def maximal_matching(G): | |
16 r"""Find a maximal matching in the graph. | |
17 | |
18 A matching is a subset of edges in which no node occurs more than once. | |
19 A maximal matching cannot add more edges and still be a matching. | |
20 | |
21 Parameters | |
22 ---------- | |
23 G : NetworkX graph | |
24 Undirected graph | |
25 | |
26 Returns | |
27 ------- | |
28 matching : set | |
29 A maximal matching of the graph. | |
30 | |
31 Notes | |
32 ----- | |
33 The algorithm greedily selects a maximal matching M of the graph G | |
34 (i.e. no superset of M exists). It runs in $O(|E|)$ time. | |
35 """ | |
36 matching = set() | |
37 nodes = set() | |
38 for u, v in G.edges(): | |
39 # If the edge isn't covered, add it to the matching | |
40 # then remove neighborhood of u and v from consideration. | |
41 if u not in nodes and v not in nodes and u != v: | |
42 matching.add((u, v)) | |
43 nodes.add(u) | |
44 nodes.add(v) | |
45 return matching | |
46 | |
47 | |
48 def matching_dict_to_set(matching): | |
49 """Converts a dictionary representing a matching (as returned by | |
50 :func:`max_weight_matching`) to a set representing a matching (as | |
51 returned by :func:`maximal_matching`). | |
52 | |
53 In the definition of maximal matching adopted by NetworkX, | |
54 self-loops are not allowed, so the provided dictionary is expected | |
55 to never have any mapping from a key to itself. However, the | |
56 dictionary is expected to have mirrored key/value pairs, for | |
57 example, key ``u`` with value ``v`` and key ``v`` with value ``u``. | |
58 | |
59 """ | |
60 # Need to compensate for the fact that both pairs (u, v) and (v, u) | |
61 # appear in `matching.items()`, so we use a set of sets. This way, | |
62 # only the (frozen)set `{u, v}` appears as an element in the | |
63 # returned set. | |
64 | |
65 return {(u, v) for (u, v) in set(map(frozenset, matching.items()))} | |
66 | |
67 | |
68 def is_matching(G, matching): | |
69 """Decides whether the given set or dictionary represents a valid | |
70 matching in ``G``. | |
71 | |
72 A *matching* in a graph is a set of edges in which no two distinct | |
73 edges share a common endpoint. | |
74 | |
75 Parameters | |
76 ---------- | |
77 G : NetworkX graph | |
78 | |
79 matching : dict or set | |
80 A dictionary or set representing a matching. If a dictionary, it | |
81 must have ``matching[u] == v`` and ``matching[v] == u`` for each | |
82 edge ``(u, v)`` in the matching. If a set, it must have elements | |
83 of the form ``(u, v)``, where ``(u, v)`` is an edge in the | |
84 matching. | |
85 | |
86 Returns | |
87 ------- | |
88 bool | |
89 Whether the given set or dictionary represents a valid matching | |
90 in the graph. | |
91 | |
92 """ | |
93 if isinstance(matching, dict): | |
94 matching = matching_dict_to_set(matching) | |
95 # TODO This is parallelizable. | |
96 return all(len(set(e1) & set(e2)) == 0 for e1, e2 in combinations(matching, 2)) | |
97 | |
98 | |
99 def is_maximal_matching(G, matching): | |
100 """Decides whether the given set or dictionary represents a valid | |
101 maximal matching in ``G``. | |
102 | |
103 A *maximal matching* in a graph is a matching in which adding any | |
104 edge would cause the set to no longer be a valid matching. | |
105 | |
106 Parameters | |
107 ---------- | |
108 G : NetworkX graph | |
109 | |
110 matching : dict or set | |
111 A dictionary or set representing a matching. If a dictionary, it | |
112 must have ``matching[u] == v`` and ``matching[v] == u`` for each | |
113 edge ``(u, v)`` in the matching. If a set, it must have elements | |
114 of the form ``(u, v)``, where ``(u, v)`` is an edge in the | |
115 matching. | |
116 | |
117 Returns | |
118 ------- | |
119 bool | |
120 Whether the given set or dictionary represents a valid maximal | |
121 matching in the graph. | |
122 | |
123 """ | |
124 if isinstance(matching, dict): | |
125 matching = matching_dict_to_set(matching) | |
126 # If the given set is not a matching, then it is not a maximal matching. | |
127 if not is_matching(G, matching): | |
128 return False | |
129 # A matching is maximal if adding any unmatched edge to it causes | |
130 # the resulting set to *not* be a valid matching. | |
131 # | |
132 # HACK Since the `matching_dict_to_set` function returns a set of | |
133 # sets, we need to convert the list of edges to a set of sets in | |
134 # order for the set difference function to work. Ideally, we would | |
135 # just be able to do `set(G.edges()) - matching`. | |
136 all_edges = set(map(frozenset, G.edges())) | |
137 matched_edges = set(map(frozenset, matching)) | |
138 unmatched_edges = all_edges - matched_edges | |
139 # TODO This is parallelizable. | |
140 return all(not is_matching(G, matching | {e}) for e in unmatched_edges) | |
141 | |
142 | |
143 def is_perfect_matching(G, matching): | |
144 """Decides whether the given set represents a valid perfect matching in | |
145 ``G``. | |
146 | |
147 A *perfect matching* in a graph is a matching in which exactly one edge | |
148 is incident upon each vertex. | |
149 | |
150 Parameters | |
151 ---------- | |
152 G : NetworkX graph | |
153 | |
154 matching : dict or set | |
155 A dictionary or set representing a matching. If a dictionary, it | |
156 must have ``matching[u] == v`` and ``matching[v] == u`` for each | |
157 edge ``(u, v)`` in the matching. If a set, it must have elements | |
158 of the form ``(u, v)``, where ``(u, v)`` is an edge in the | |
159 matching. | |
160 | |
161 Returns | |
162 ------- | |
163 bool | |
164 Whether the given set or dictionary represents a valid perfect | |
165 matching in the graph. | |
166 | |
167 """ | |
168 if isinstance(matching, dict): | |
169 matching = matching_dict_to_set(matching) | |
170 | |
171 if not is_matching(G, matching): | |
172 return False | |
173 | |
174 counts = Counter(sum(matching, ())) | |
175 | |
176 return all(counts[v] == 1 for v in G) | |
177 | |
178 | |
179 def max_weight_matching(G, maxcardinality=False, weight="weight"): | |
180 """Compute a maximum-weighted matching of G. | |
181 | |
182 A matching is a subset of edges in which no node occurs more than once. | |
183 The weight of a matching is the sum of the weights of its edges. | |
184 A maximal matching cannot add more edges and still be a matching. | |
185 The cardinality of a matching is the number of matched edges. | |
186 | |
187 Parameters | |
188 ---------- | |
189 G : NetworkX graph | |
190 Undirected graph | |
191 | |
192 maxcardinality: bool, optional (default=False) | |
193 If maxcardinality is True, compute the maximum-cardinality matching | |
194 with maximum weight among all maximum-cardinality matchings. | |
195 | |
196 weight: string, optional (default='weight') | |
197 Edge data key corresponding to the edge weight. | |
198 If key not found, uses 1 as weight. | |
199 | |
200 | |
201 Returns | |
202 ------- | |
203 matching : set | |
204 A maximal matching of the graph. | |
205 | |
206 Notes | |
207 ----- | |
208 If G has edges with weight attributes the edge data are used as | |
209 weight values else the weights are assumed to be 1. | |
210 | |
211 This function takes time O(number_of_nodes ** 3). | |
212 | |
213 If all edge weights are integers, the algorithm uses only integer | |
214 computations. If floating point weights are used, the algorithm | |
215 could return a slightly suboptimal matching due to numeric | |
216 precision errors. | |
217 | |
218 This method is based on the "blossom" method for finding augmenting | |
219 paths and the "primal-dual" method for finding a matching of maximum | |
220 weight, both methods invented by Jack Edmonds [1]_. | |
221 | |
222 Bipartite graphs can also be matched using the functions present in | |
223 :mod:`networkx.algorithms.bipartite.matching`. | |
224 | |
225 References | |
226 ---------- | |
227 .. [1] "Efficient Algorithms for Finding Maximum Matching in Graphs", | |
228 Zvi Galil, ACM Computing Surveys, 1986. | |
229 """ | |
230 # | |
231 # The algorithm is taken from "Efficient Algorithms for Finding Maximum | |
232 # Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986. | |
233 # It is based on the "blossom" method for finding augmenting paths and | |
234 # the "primal-dual" method for finding a matching of maximum weight, both | |
235 # methods invented by Jack Edmonds. | |
236 # | |
237 # A C program for maximum weight matching by Ed Rothberg was used | |
238 # extensively to validate this new code. | |
239 # | |
240 # Many terms used in the code comments are explained in the paper | |
241 # by Galil. You will probably need the paper to make sense of this code. | |
242 # | |
243 | |
244 class NoNode: | |
245 """Dummy value which is different from any node.""" | |
246 | |
247 pass | |
248 | |
249 class Blossom: | |
250 """Representation of a non-trivial blossom or sub-blossom.""" | |
251 | |
252 __slots__ = ["childs", "edges", "mybestedges"] | |
253 | |
254 # b.childs is an ordered list of b's sub-blossoms, starting with | |
255 # the base and going round the blossom. | |
256 | |
257 # b.edges is the list of b's connecting edges, such that | |
258 # b.edges[i] = (v, w) where v is a vertex in b.childs[i] | |
259 # and w is a vertex in b.childs[wrap(i+1)]. | |
260 | |
261 # If b is a top-level S-blossom, | |
262 # b.mybestedges is a list of least-slack edges to neighbouring | |
263 # S-blossoms, or None if no such list has been computed yet. | |
264 # This is used for efficient computation of delta3. | |
265 | |
266 # Generate the blossom's leaf vertices. | |
267 def leaves(self): | |
268 for t in self.childs: | |
269 if isinstance(t, Blossom): | |
270 yield from t.leaves() | |
271 else: | |
272 yield t | |
273 | |
274 # Get a list of vertices. | |
275 gnodes = list(G) | |
276 if not gnodes: | |
277 return set() # don't bother with empty graphs | |
278 | |
279 # Find the maximum edge weight. | |
280 maxweight = 0 | |
281 allinteger = True | |
282 for i, j, d in G.edges(data=True): | |
283 wt = d.get(weight, 1) | |
284 if i != j and wt > maxweight: | |
285 maxweight = wt | |
286 allinteger = allinteger and (str(type(wt)).split("'")[1] in ("int", "long")) | |
287 | |
288 # If v is a matched vertex, mate[v] is its partner vertex. | |
289 # If v is a single vertex, v does not occur as a key in mate. | |
290 # Initially all vertices are single; updated during augmentation. | |
291 mate = {} | |
292 | |
293 # If b is a top-level blossom, | |
294 # label.get(b) is None if b is unlabeled (free), | |
295 # 1 if b is an S-blossom, | |
296 # 2 if b is a T-blossom. | |
297 # The label of a vertex is found by looking at the label of its top-level | |
298 # containing blossom. | |
299 # If v is a vertex inside a T-blossom, label[v] is 2 iff v is reachable | |
300 # from an S-vertex outside the blossom. | |
301 # Labels are assigned during a stage and reset after each augmentation. | |
302 label = {} | |
303 | |
304 # If b is a labeled top-level blossom, | |
305 # labeledge[b] = (v, w) is the edge through which b obtained its label | |
306 # such that w is a vertex in b, or None if b's base vertex is single. | |
307 # If w is a vertex inside a T-blossom and label[w] == 2, | |
308 # labeledge[w] = (v, w) is an edge through which w is reachable from | |
309 # outside the blossom. | |
310 labeledge = {} | |
311 | |
312 # If v is a vertex, inblossom[v] is the top-level blossom to which v | |
313 # belongs. | |
314 # If v is a top-level vertex, inblossom[v] == v since v is itself | |
315 # a (trivial) top-level blossom. | |
316 # Initially all vertices are top-level trivial blossoms. | |
317 inblossom = dict(zip(gnodes, gnodes)) | |
318 | |
319 # If b is a sub-blossom, | |
320 # blossomparent[b] is its immediate parent (sub-)blossom. | |
321 # If b is a top-level blossom, blossomparent[b] is None. | |
322 blossomparent = dict(zip(gnodes, repeat(None))) | |
323 | |
324 # If b is a (sub-)blossom, | |
325 # blossombase[b] is its base VERTEX (i.e. recursive sub-blossom). | |
326 blossombase = dict(zip(gnodes, gnodes)) | |
327 | |
328 # If w is a free vertex (or an unreached vertex inside a T-blossom), | |
329 # bestedge[w] = (v, w) is the least-slack edge from an S-vertex, | |
330 # or None if there is no such edge. | |
331 # If b is a (possibly trivial) top-level S-blossom, | |
332 # bestedge[b] = (v, w) is the least-slack edge to a different S-blossom | |
333 # (v inside b), or None if there is no such edge. | |
334 # This is used for efficient computation of delta2 and delta3. | |
335 bestedge = {} | |
336 | |
337 # If v is a vertex, | |
338 # dualvar[v] = 2 * u(v) where u(v) is the v's variable in the dual | |
339 # optimization problem (if all edge weights are integers, multiplication | |
340 # by two ensures that all values remain integers throughout the algorithm). | |
341 # Initially, u(v) = maxweight / 2. | |
342 dualvar = dict(zip(gnodes, repeat(maxweight))) | |
343 | |
344 # If b is a non-trivial blossom, | |
345 # blossomdual[b] = z(b) where z(b) is b's variable in the dual | |
346 # optimization problem. | |
347 blossomdual = {} | |
348 | |
349 # If (v, w) in allowedge or (w, v) in allowedg, then the edge | |
350 # (v, w) is known to have zero slack in the optimization problem; | |
351 # otherwise the edge may or may not have zero slack. | |
352 allowedge = {} | |
353 | |
354 # Queue of newly discovered S-vertices. | |
355 queue = [] | |
356 | |
357 # Return 2 * slack of edge (v, w) (does not work inside blossoms). | |
358 def slack(v, w): | |
359 return dualvar[v] + dualvar[w] - 2 * G[v][w].get(weight, 1) | |
360 | |
361 # Assign label t to the top-level blossom containing vertex w, | |
362 # coming through an edge from vertex v. | |
363 def assignLabel(w, t, v): | |
364 b = inblossom[w] | |
365 assert label.get(w) is None and label.get(b) is None | |
366 label[w] = label[b] = t | |
367 if v is not None: | |
368 labeledge[w] = labeledge[b] = (v, w) | |
369 else: | |
370 labeledge[w] = labeledge[b] = None | |
371 bestedge[w] = bestedge[b] = None | |
372 if t == 1: | |
373 # b became an S-vertex/blossom; add it(s vertices) to the queue. | |
374 if isinstance(b, Blossom): | |
375 queue.extend(b.leaves()) | |
376 else: | |
377 queue.append(b) | |
378 elif t == 2: | |
379 # b became a T-vertex/blossom; assign label S to its mate. | |
380 # (If b is a non-trivial blossom, its base is the only vertex | |
381 # with an external mate.) | |
382 base = blossombase[b] | |
383 assignLabel(mate[base], 1, base) | |
384 | |
385 # Trace back from vertices v and w to discover either a new blossom | |
386 # or an augmenting path. Return the base vertex of the new blossom, | |
387 # or NoNode if an augmenting path was found. | |
388 def scanBlossom(v, w): | |
389 # Trace back from v and w, placing breadcrumbs as we go. | |
390 path = [] | |
391 base = NoNode | |
392 while v is not NoNode: | |
393 # Look for a breadcrumb in v's blossom or put a new breadcrumb. | |
394 b = inblossom[v] | |
395 if label[b] & 4: | |
396 base = blossombase[b] | |
397 break | |
398 assert label[b] == 1 | |
399 path.append(b) | |
400 label[b] = 5 | |
401 # Trace one step back. | |
402 if labeledge[b] is None: | |
403 # The base of blossom b is single; stop tracing this path. | |
404 assert blossombase[b] not in mate | |
405 v = NoNode | |
406 else: | |
407 assert labeledge[b][0] == mate[blossombase[b]] | |
408 v = labeledge[b][0] | |
409 b = inblossom[v] | |
410 assert label[b] == 2 | |
411 # b is a T-blossom; trace one more step back. | |
412 v = labeledge[b][0] | |
413 # Swap v and w so that we alternate between both paths. | |
414 if w is not NoNode: | |
415 v, w = w, v | |
416 # Remove breadcrumbs. | |
417 for b in path: | |
418 label[b] = 1 | |
419 # Return base vertex, if we found one. | |
420 return base | |
421 | |
422 # Construct a new blossom with given base, through S-vertices v and w. | |
423 # Label the new blossom as S; set its dual variable to zero; | |
424 # relabel its T-vertices to S and add them to the queue. | |
425 def addBlossom(base, v, w): | |
426 bb = inblossom[base] | |
427 bv = inblossom[v] | |
428 bw = inblossom[w] | |
429 # Create blossom. | |
430 b = Blossom() | |
431 blossombase[b] = base | |
432 blossomparent[b] = None | |
433 blossomparent[bb] = b | |
434 # Make list of sub-blossoms and their interconnecting edge endpoints. | |
435 b.childs = path = [] | |
436 b.edges = edgs = [(v, w)] | |
437 # Trace back from v to base. | |
438 while bv != bb: | |
439 # Add bv to the new blossom. | |
440 blossomparent[bv] = b | |
441 path.append(bv) | |
442 edgs.append(labeledge[bv]) | |
443 assert label[bv] == 2 or ( | |
444 label[bv] == 1 and labeledge[bv][0] == mate[blossombase[bv]] | |
445 ) | |
446 # Trace one step back. | |
447 v = labeledge[bv][0] | |
448 bv = inblossom[v] | |
449 # Add base sub-blossom; reverse lists. | |
450 path.append(bb) | |
451 path.reverse() | |
452 edgs.reverse() | |
453 # Trace back from w to base. | |
454 while bw != bb: | |
455 # Add bw to the new blossom. | |
456 blossomparent[bw] = b | |
457 path.append(bw) | |
458 edgs.append((labeledge[bw][1], labeledge[bw][0])) | |
459 assert label[bw] == 2 or ( | |
460 label[bw] == 1 and labeledge[bw][0] == mate[blossombase[bw]] | |
461 ) | |
462 # Trace one step back. | |
463 w = labeledge[bw][0] | |
464 bw = inblossom[w] | |
465 # Set label to S. | |
466 assert label[bb] == 1 | |
467 label[b] = 1 | |
468 labeledge[b] = labeledge[bb] | |
469 # Set dual variable to zero. | |
470 blossomdual[b] = 0 | |
471 # Relabel vertices. | |
472 for v in b.leaves(): | |
473 if label[inblossom[v]] == 2: | |
474 # This T-vertex now turns into an S-vertex because it becomes | |
475 # part of an S-blossom; add it to the queue. | |
476 queue.append(v) | |
477 inblossom[v] = b | |
478 # Compute b.mybestedges. | |
479 bestedgeto = {} | |
480 for bv in path: | |
481 if isinstance(bv, Blossom): | |
482 if bv.mybestedges is not None: | |
483 # Walk this subblossom's least-slack edges. | |
484 nblist = bv.mybestedges | |
485 # The sub-blossom won't need this data again. | |
486 bv.mybestedges = None | |
487 else: | |
488 # This subblossom does not have a list of least-slack | |
489 # edges; get the information from the vertices. | |
490 nblist = [ | |
491 (v, w) for v in bv.leaves() for w in G.neighbors(v) if v != w | |
492 ] | |
493 else: | |
494 nblist = [(bv, w) for w in G.neighbors(bv) if bv != w] | |
495 for k in nblist: | |
496 (i, j) = k | |
497 if inblossom[j] == b: | |
498 i, j = j, i | |
499 bj = inblossom[j] | |
500 if ( | |
501 bj != b | |
502 and label.get(bj) == 1 | |
503 and ((bj not in bestedgeto) or slack(i, j) < slack(*bestedgeto[bj])) | |
504 ): | |
505 bestedgeto[bj] = k | |
506 # Forget about least-slack edge of the subblossom. | |
507 bestedge[bv] = None | |
508 b.mybestedges = list(bestedgeto.values()) | |
509 # Select bestedge[b]. | |
510 mybestedge = None | |
511 bestedge[b] = None | |
512 for k in b.mybestedges: | |
513 kslack = slack(*k) | |
514 if mybestedge is None or kslack < mybestslack: | |
515 mybestedge = k | |
516 mybestslack = kslack | |
517 bestedge[b] = mybestedge | |
518 | |
519 # Expand the given top-level blossom. | |
520 def expandBlossom(b, endstage): | |
521 # Convert sub-blossoms into top-level blossoms. | |
522 for s in b.childs: | |
523 blossomparent[s] = None | |
524 if isinstance(s, Blossom): | |
525 if endstage and blossomdual[s] == 0: | |
526 # Recursively expand this sub-blossom. | |
527 expandBlossom(s, endstage) | |
528 else: | |
529 for v in s.leaves(): | |
530 inblossom[v] = s | |
531 else: | |
532 inblossom[s] = s | |
533 # If we expand a T-blossom during a stage, its sub-blossoms must be | |
534 # relabeled. | |
535 if (not endstage) and label.get(b) == 2: | |
536 # Start at the sub-blossom through which the expanding | |
537 # blossom obtained its label, and relabel sub-blossoms untili | |
538 # we reach the base. | |
539 # Figure out through which sub-blossom the expanding blossom | |
540 # obtained its label initially. | |
541 entrychild = inblossom[labeledge[b][1]] | |
542 # Decide in which direction we will go round the blossom. | |
543 j = b.childs.index(entrychild) | |
544 if j & 1: | |
545 # Start index is odd; go forward and wrap. | |
546 j -= len(b.childs) | |
547 jstep = 1 | |
548 else: | |
549 # Start index is even; go backward. | |
550 jstep = -1 | |
551 # Move along the blossom until we get to the base. | |
552 v, w = labeledge[b] | |
553 while j != 0: | |
554 # Relabel the T-sub-blossom. | |
555 if jstep == 1: | |
556 p, q = b.edges[j] | |
557 else: | |
558 q, p = b.edges[j - 1] | |
559 label[w] = None | |
560 label[q] = None | |
561 assignLabel(w, 2, v) | |
562 # Step to the next S-sub-blossom and note its forward edge. | |
563 allowedge[(p, q)] = allowedge[(q, p)] = True | |
564 j += jstep | |
565 if jstep == 1: | |
566 v, w = b.edges[j] | |
567 else: | |
568 w, v = b.edges[j - 1] | |
569 # Step to the next T-sub-blossom. | |
570 allowedge[(v, w)] = allowedge[(w, v)] = True | |
571 j += jstep | |
572 # Relabel the base T-sub-blossom WITHOUT stepping through to | |
573 # its mate (so don't call assignLabel). | |
574 bw = b.childs[j] | |
575 label[w] = label[bw] = 2 | |
576 labeledge[w] = labeledge[bw] = (v, w) | |
577 bestedge[bw] = None | |
578 # Continue along the blossom until we get back to entrychild. | |
579 j += jstep | |
580 while b.childs[j] != entrychild: | |
581 # Examine the vertices of the sub-blossom to see whether | |
582 # it is reachable from a neighbouring S-vertex outside the | |
583 # expanding blossom. | |
584 bv = b.childs[j] | |
585 if label.get(bv) == 1: | |
586 # This sub-blossom just got label S through one of its | |
587 # neighbours; leave it be. | |
588 j += jstep | |
589 continue | |
590 if isinstance(bv, Blossom): | |
591 for v in bv.leaves(): | |
592 if label.get(v): | |
593 break | |
594 else: | |
595 v = bv | |
596 # If the sub-blossom contains a reachable vertex, assign | |
597 # label T to the sub-blossom. | |
598 if label.get(v): | |
599 assert label[v] == 2 | |
600 assert inblossom[v] == bv | |
601 label[v] = None | |
602 label[mate[blossombase[bv]]] = None | |
603 assignLabel(v, 2, labeledge[v][0]) | |
604 j += jstep | |
605 # Remove the expanded blossom entirely. | |
606 label.pop(b, None) | |
607 labeledge.pop(b, None) | |
608 bestedge.pop(b, None) | |
609 del blossomparent[b] | |
610 del blossombase[b] | |
611 del blossomdual[b] | |
612 | |
613 # Swap matched/unmatched edges over an alternating path through blossom b | |
614 # between vertex v and the base vertex. Keep blossom bookkeeping | |
615 # consistent. | |
616 def augmentBlossom(b, v): | |
617 # Bubble up through the blossom tree from vertex v to an immediate | |
618 # sub-blossom of b. | |
619 t = v | |
620 while blossomparent[t] != b: | |
621 t = blossomparent[t] | |
622 # Recursively deal with the first sub-blossom. | |
623 if isinstance(t, Blossom): | |
624 augmentBlossom(t, v) | |
625 # Decide in which direction we will go round the blossom. | |
626 i = j = b.childs.index(t) | |
627 if i & 1: | |
628 # Start index is odd; go forward and wrap. | |
629 j -= len(b.childs) | |
630 jstep = 1 | |
631 else: | |
632 # Start index is even; go backward. | |
633 jstep = -1 | |
634 # Move along the blossom until we get to the base. | |
635 while j != 0: | |
636 # Step to the next sub-blossom and augment it recursively. | |
637 j += jstep | |
638 t = b.childs[j] | |
639 if jstep == 1: | |
640 w, x = b.edges[j] | |
641 else: | |
642 x, w = b.edges[j - 1] | |
643 if isinstance(t, Blossom): | |
644 augmentBlossom(t, w) | |
645 # Step to the next sub-blossom and augment it recursively. | |
646 j += jstep | |
647 t = b.childs[j] | |
648 if isinstance(t, Blossom): | |
649 augmentBlossom(t, x) | |
650 # Match the edge connecting those sub-blossoms. | |
651 mate[w] = x | |
652 mate[x] = w | |
653 # Rotate the list of sub-blossoms to put the new base at the front. | |
654 b.childs = b.childs[i:] + b.childs[:i] | |
655 b.edges = b.edges[i:] + b.edges[:i] | |
656 blossombase[b] = blossombase[b.childs[0]] | |
657 assert blossombase[b] == v | |
658 | |
659 # Swap matched/unmatched edges over an alternating path between two | |
660 # single vertices. The augmenting path runs through S-vertices v and w. | |
661 def augmentMatching(v, w): | |
662 for (s, j) in ((v, w), (w, v)): | |
663 # Match vertex s to vertex j. Then trace back from s | |
664 # until we find a single vertex, swapping matched and unmatched | |
665 # edges as we go. | |
666 while 1: | |
667 bs = inblossom[s] | |
668 assert label[bs] == 1 | |
669 assert (labeledge[bs] is None and blossombase[bs] not in mate) or ( | |
670 labeledge[bs][0] == mate[blossombase[bs]] | |
671 ) | |
672 # Augment through the S-blossom from s to base. | |
673 if isinstance(bs, Blossom): | |
674 augmentBlossom(bs, s) | |
675 # Update mate[s] | |
676 mate[s] = j | |
677 # Trace one step back. | |
678 if labeledge[bs] is None: | |
679 # Reached single vertex; stop. | |
680 break | |
681 t = labeledge[bs][0] | |
682 bt = inblossom[t] | |
683 assert label[bt] == 2 | |
684 # Trace one more step back. | |
685 s, j = labeledge[bt] | |
686 # Augment through the T-blossom from j to base. | |
687 assert blossombase[bt] == t | |
688 if isinstance(bt, Blossom): | |
689 augmentBlossom(bt, j) | |
690 # Update mate[j] | |
691 mate[j] = s | |
692 | |
693 # Verify that the optimum solution has been reached. | |
694 def verifyOptimum(): | |
695 if maxcardinality: | |
696 # Vertices may have negative dual; | |
697 # find a constant non-negative number to add to all vertex duals. | |
698 vdualoffset = max(0, -min(dualvar.values())) | |
699 else: | |
700 vdualoffset = 0 | |
701 # 0. all dual variables are non-negative | |
702 assert min(dualvar.values()) + vdualoffset >= 0 | |
703 assert len(blossomdual) == 0 or min(blossomdual.values()) >= 0 | |
704 # 0. all edges have non-negative slack and | |
705 # 1. all matched edges have zero slack; | |
706 for i, j, d in G.edges(data=True): | |
707 wt = d.get(weight, 1) | |
708 if i == j: | |
709 continue # ignore self-loops | |
710 s = dualvar[i] + dualvar[j] - 2 * wt | |
711 iblossoms = [i] | |
712 jblossoms = [j] | |
713 while blossomparent[iblossoms[-1]] is not None: | |
714 iblossoms.append(blossomparent[iblossoms[-1]]) | |
715 while blossomparent[jblossoms[-1]] is not None: | |
716 jblossoms.append(blossomparent[jblossoms[-1]]) | |
717 iblossoms.reverse() | |
718 jblossoms.reverse() | |
719 for (bi, bj) in zip(iblossoms, jblossoms): | |
720 if bi != bj: | |
721 break | |
722 s += 2 * blossomdual[bi] | |
723 assert s >= 0 | |
724 if mate.get(i) == j or mate.get(j) == i: | |
725 assert mate[i] == j and mate[j] == i | |
726 assert s == 0 | |
727 # 2. all single vertices have zero dual value; | |
728 for v in gnodes: | |
729 assert (v in mate) or dualvar[v] + vdualoffset == 0 | |
730 # 3. all blossoms with positive dual value are full. | |
731 for b in blossomdual: | |
732 if blossomdual[b] > 0: | |
733 assert len(b.edges) % 2 == 1 | |
734 for (i, j) in b.edges[1::2]: | |
735 assert mate[i] == j and mate[j] == i | |
736 # Ok. | |
737 | |
738 # Main loop: continue until no further improvement is possible. | |
739 while 1: | |
740 | |
741 # Each iteration of this loop is a "stage". | |
742 # A stage finds an augmenting path and uses that to improve | |
743 # the matching. | |
744 | |
745 # Remove labels from top-level blossoms/vertices. | |
746 label.clear() | |
747 labeledge.clear() | |
748 | |
749 # Forget all about least-slack edges. | |
750 bestedge.clear() | |
751 for b in blossomdual: | |
752 b.mybestedges = None | |
753 | |
754 # Loss of labeling means that we can not be sure that currently | |
755 # allowable edges remain allowable throughout this stage. | |
756 allowedge.clear() | |
757 | |
758 # Make queue empty. | |
759 queue[:] = [] | |
760 | |
761 # Label single blossoms/vertices with S and put them in the queue. | |
762 for v in gnodes: | |
763 if (v not in mate) and label.get(inblossom[v]) is None: | |
764 assignLabel(v, 1, None) | |
765 | |
766 # Loop until we succeed in augmenting the matching. | |
767 augmented = 0 | |
768 while 1: | |
769 | |
770 # Each iteration of this loop is a "substage". | |
771 # A substage tries to find an augmenting path; | |
772 # if found, the path is used to improve the matching and | |
773 # the stage ends. If there is no augmenting path, the | |
774 # primal-dual method is used to pump some slack out of | |
775 # the dual variables. | |
776 | |
777 # Continue labeling until all vertices which are reachable | |
778 # through an alternating path have got a label. | |
779 while queue and not augmented: | |
780 | |
781 # Take an S vertex from the queue. | |
782 v = queue.pop() | |
783 assert label[inblossom[v]] == 1 | |
784 | |
785 # Scan its neighbours: | |
786 for w in G.neighbors(v): | |
787 if w == v: | |
788 continue # ignore self-loops | |
789 # w is a neighbour to v | |
790 bv = inblossom[v] | |
791 bw = inblossom[w] | |
792 if bv == bw: | |
793 # this edge is internal to a blossom; ignore it | |
794 continue | |
795 if (v, w) not in allowedge: | |
796 kslack = slack(v, w) | |
797 if kslack <= 0: | |
798 # edge k has zero slack => it is allowable | |
799 allowedge[(v, w)] = allowedge[(w, v)] = True | |
800 if (v, w) in allowedge: | |
801 if label.get(bw) is None: | |
802 # (C1) w is a free vertex; | |
803 # label w with T and label its mate with S (R12). | |
804 assignLabel(w, 2, v) | |
805 elif label.get(bw) == 1: | |
806 # (C2) w is an S-vertex (not in the same blossom); | |
807 # follow back-links to discover either an | |
808 # augmenting path or a new blossom. | |
809 base = scanBlossom(v, w) | |
810 if base is not NoNode: | |
811 # Found a new blossom; add it to the blossom | |
812 # bookkeeping and turn it into an S-blossom. | |
813 addBlossom(base, v, w) | |
814 else: | |
815 # Found an augmenting path; augment the | |
816 # matching and end this stage. | |
817 augmentMatching(v, w) | |
818 augmented = 1 | |
819 break | |
820 elif label.get(w) is None: | |
821 # w is inside a T-blossom, but w itself has not | |
822 # yet been reached from outside the blossom; | |
823 # mark it as reached (we need this to relabel | |
824 # during T-blossom expansion). | |
825 assert label[bw] == 2 | |
826 label[w] = 2 | |
827 labeledge[w] = (v, w) | |
828 elif label.get(bw) == 1: | |
829 # keep track of the least-slack non-allowable edge to | |
830 # a different S-blossom. | |
831 if bestedge.get(bv) is None or kslack < slack(*bestedge[bv]): | |
832 bestedge[bv] = (v, w) | |
833 elif label.get(w) is None: | |
834 # w is a free vertex (or an unreached vertex inside | |
835 # a T-blossom) but we can not reach it yet; | |
836 # keep track of the least-slack edge that reaches w. | |
837 if bestedge.get(w) is None or kslack < slack(*bestedge[w]): | |
838 bestedge[w] = (v, w) | |
839 | |
840 if augmented: | |
841 break | |
842 | |
843 # There is no augmenting path under these constraints; | |
844 # compute delta and reduce slack in the optimization problem. | |
845 # (Note that our vertex dual variables, edge slacks and delta's | |
846 # are pre-multiplied by two.) | |
847 deltatype = -1 | |
848 delta = deltaedge = deltablossom = None | |
849 | |
850 # Compute delta1: the minimum value of any vertex dual. | |
851 if not maxcardinality: | |
852 deltatype = 1 | |
853 delta = min(dualvar.values()) | |
854 | |
855 # Compute delta2: the minimum slack on any edge between | |
856 # an S-vertex and a free vertex. | |
857 for v in G.nodes(): | |
858 if label.get(inblossom[v]) is None and bestedge.get(v) is not None: | |
859 d = slack(*bestedge[v]) | |
860 if deltatype == -1 or d < delta: | |
861 delta = d | |
862 deltatype = 2 | |
863 deltaedge = bestedge[v] | |
864 | |
865 # Compute delta3: half the minimum slack on any edge between | |
866 # a pair of S-blossoms. | |
867 for b in blossomparent: | |
868 if ( | |
869 blossomparent[b] is None | |
870 and label.get(b) == 1 | |
871 and bestedge.get(b) is not None | |
872 ): | |
873 kslack = slack(*bestedge[b]) | |
874 if allinteger: | |
875 assert (kslack % 2) == 0 | |
876 d = kslack // 2 | |
877 else: | |
878 d = kslack / 2.0 | |
879 if deltatype == -1 or d < delta: | |
880 delta = d | |
881 deltatype = 3 | |
882 deltaedge = bestedge[b] | |
883 | |
884 # Compute delta4: minimum z variable of any T-blossom. | |
885 for b in blossomdual: | |
886 if ( | |
887 blossomparent[b] is None | |
888 and label.get(b) == 2 | |
889 and (deltatype == -1 or blossomdual[b] < delta) | |
890 ): | |
891 delta = blossomdual[b] | |
892 deltatype = 4 | |
893 deltablossom = b | |
894 | |
895 if deltatype == -1: | |
896 # No further improvement possible; max-cardinality optimum | |
897 # reached. Do a final delta update to make the optimum | |
898 # verifyable. | |
899 assert maxcardinality | |
900 deltatype = 1 | |
901 delta = max(0, min(dualvar.values())) | |
902 | |
903 # Update dual variables according to delta. | |
904 for v in gnodes: | |
905 if label.get(inblossom[v]) == 1: | |
906 # S-vertex: 2*u = 2*u - 2*delta | |
907 dualvar[v] -= delta | |
908 elif label.get(inblossom[v]) == 2: | |
909 # T-vertex: 2*u = 2*u + 2*delta | |
910 dualvar[v] += delta | |
911 for b in blossomdual: | |
912 if blossomparent[b] is None: | |
913 if label.get(b) == 1: | |
914 # top-level S-blossom: z = z + 2*delta | |
915 blossomdual[b] += delta | |
916 elif label.get(b) == 2: | |
917 # top-level T-blossom: z = z - 2*delta | |
918 blossomdual[b] -= delta | |
919 | |
920 # Take action at the point where minimum delta occurred. | |
921 if deltatype == 1: | |
922 # No further improvement possible; optimum reached. | |
923 break | |
924 elif deltatype == 2: | |
925 # Use the least-slack edge to continue the search. | |
926 (v, w) = deltaedge | |
927 assert label[inblossom[v]] == 1 | |
928 allowedge[(v, w)] = allowedge[(w, v)] = True | |
929 queue.append(v) | |
930 elif deltatype == 3: | |
931 # Use the least-slack edge to continue the search. | |
932 (v, w) = deltaedge | |
933 allowedge[(v, w)] = allowedge[(w, v)] = True | |
934 assert label[inblossom[v]] == 1 | |
935 queue.append(v) | |
936 elif deltatype == 4: | |
937 # Expand the least-z blossom. | |
938 expandBlossom(deltablossom, False) | |
939 | |
940 # End of a this substage. | |
941 | |
942 # Paranoia check that the matching is symmetric. | |
943 for v in mate: | |
944 assert mate[mate[v]] == v | |
945 | |
946 # Stop when no more augmenting path can be found. | |
947 if not augmented: | |
948 break | |
949 | |
950 # End of a stage; expand all S-blossoms which have zero dual. | |
951 for b in list(blossomdual.keys()): | |
952 if b not in blossomdual: | |
953 continue # already expanded | |
954 if blossomparent[b] is None and label.get(b) == 1 and blossomdual[b] == 0: | |
955 expandBlossom(b, True) | |
956 | |
957 # Verify that we reached the optimum solution (only for integer weights). | |
958 if allinteger: | |
959 verifyOptimum() | |
960 | |
961 return matching_dict_to_set(mate) |