|
==Finding an augmenting path==
The search for an augmenting path uses an auxiliary data structure consisting of a [[forest (graph theory)|forest]] ''{{mvar|F''}} whose individual trees correspond to specific portions of the graph ''{{mvar|G''}}. In fact, the forest ''{{mvar|F''}} is the same that would be used to find maximum matchings in [[bipartite graph]]s (without need for shrinking blossoms).
In each iteration the algorithm either (1) finds an augmenting path, (2) finds a blossom and recurses onto the corresponding contracted graph, or (3) concludes there are no augmenting paths. The auxiliary structure is built by an incremental procedure discussed next.<ref name = "tarjan notes"/>
The construction procedure considers vertices ''{{mvar|v''}} and edges ''{{mvar|e''}} in ''{{mvar|G''}} and incrementally updates ''{{mvar|F''}} as appropriate. If ''{{mvar|v''}} is in a tree ''{{mvar|T''}} of the forest, we let ''{{code|root(v)}}'' denote the root of ''{{mvar|T''}}. If both ''{{mvar|u''}} and ''{{mvar|v''}} are in the same tree ''{{mvar|T''}} in ''{{mvar|F''}}, we let ''{{code|distance(u,v)}}'' denote the length of the unique path from ''{{mvar|u''}} to ''{{mvar|v''}} in ''{{mvar|T''}}.
INPUT: Graph ''G'', matching ''M'' on ''G''
[[File:blossom contraction.png|400px|alt=Blossom contraction on line B21]]
Finally, it locates an augmenting path {{mvar|P′}} in the contracted graph (line B22) and lifts it to the original graph (line B23). Note that the ability of the algorithm to contract blossoms is crucial here; the algorithm cannot find ''{{mvar|P''}} in the original graph directly because only out-of-forest edges between vertices at even distances from the roots are considered on line B17 of the algorithm.
[[File:path detection.png|400px|alt=Detection of augmenting path {{mvar|P′}} in {{mvar|G′}} on line B17]]
[[File:path lifting.png|400px|alt=Lifting of {{mvar|P′}} to corresponding augmenting path in {{mvar|G}} on line B25]]
===Analysis===
The forest ''{{mvar|F''}} constructed by the ''{{code|find_augmenting_path()''}} function is an alternating forest.<ref name = "kenyon report">{{citation
| author1 = Kenyon, Claire
| author2 = Lovász, László
| title = Technical Report CS-TR-251-90, Department of Computer Science, Princeton University
}}</ref>
* a tree ''{{mvar|T''}} in ''{{mvar|G''}} is an '''alternating tree''' with respect to ''{{mvar|M''}}, if
** ''{{mvar|T''}} contains exactly one exposed vertex ''{{mvar|r''}} called the tree root
** every vertex at an odd distance from the root has exactly two incident edges in ''{{mvar|T''}}, and
** all paths from ''{{mvar|r''}} to leaves in ''{{mvar|T''}} have even lengths, their odd edges are not in ''{{mvar|M''}} and their even edges are in ''{{mvar|M''}}.
* a forest ''{{mvar|F''}} in ''{{mvar|G''}} is an '''alternating forest''' with respect to ''{{mvar|M''}}, if
** its connected components are alternating trees, and
** every exposed vertex in ''{{mvar|G''}} is a root of an alternating tree in ''{{mvar|F''}}.
Each iteration of the loop starting at line B09 either adds to a tree ''{{mvar|T''}} in ''{{mvar|F''}} (line B10) or finds an augmenting path (line B17) or finds a blossom (line B20). It is easy to see that the running time is <math>O( |E||V|^2)</math>.
===Bipartite matching===
When ''{{mvar|G''}} is [[bipartite graph|bipartite]], there are no odd cycles in ''{{mvar|G''}}. In that case, blossoms will never be found and one can simply remove lines B20 – B24 of the algorithm. The algorithm thus reduces to the standard algorithm to construct maximum cardinality matchings in bipartite graphs<ref name = "karp notes"/> where we repeatedly search for an augmenting path by a simple graph traversal: this is for instance the case of the [[Ford–Fulkerson algorithm]].
===Weighted matching===
The matching problem can be generalized by assigning weights to edges in ''{{mvar|G''}} and asking for a set ''{{mvar|M''}} that produces a matching of maximum (minimum) total weight: this is the [[maximum weight matching]] problem. This problem can be solved by a combinatorial algorithm that uses the unweighted Edmonds's algorithm as a subroutine.<ref name = "matching book"/> Kolmogorov provides an efficient C++ implementation of this.<ref name = blossom5>{{citation
| author = Kolmogorov, Vladimir
| title = Blossom V: A new implementation of a minimum cost perfect matching algorithm
| 