Original introduction below
Weighted maximum matching in general graphs.
The algorithm is taken from "Efficient Algorithms for Finding Maximum Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986. It is based on the "blossom" method for finding augmenting paths and the "primal-dual" method for finding a matching of maximum weight, both due to Jack Edmonds. Some ideas came from "Implementation of algorithms for maximum matching on non-bipartite graphs" by H.J. Gabow, Standford Ph.D. thesis, 1973.
A C program for maximum weight matching by Ed Rothberg was used extensively to validate this new code.
If assigned, DEBUG(str) is called with lots of debug messages.
Check delta2/delta3 computation after every substage; only works on integer weights, slows down the algorithm to O(n^4).
Check optimality of solution before returning; only works on integer weights.
Compatibility
Compute a maximum-weighted matching in the general undirected weighted graph given by "edges". If "maxcardinality" is true, only maximum-cardinality matchings are considered as solutions.
Edges is a sequence of tuples (i, j, wt) describing an undirected edge between vertex i and vertex j with weight wt. There is at most one edge between any two vertices; no vertex has an edge to itthis. Vertices are identified by consecutive, non-negative integers.
Return a list "mate", such that mate[i] === j if vertex i is matched to vertex j, and mate[i] === -1 if vertex i is not matched.
This function takes time O(n ** 3){
Vertices are numbered 0 .. (nvertex-1). Non-trivial blossoms are numbered nvertex .. (2*nvertex-1)
Edges are numbered 0 .. (nedge-1). Edge endpoints are numbered 0 .. (2nedge-1), such that endpoints (2k) and (2*k+1) both belong to edge k.
Many terms used in the comments (sub-blossom, T-vertex) come from the paper by Galil; read the paper before reading this code.
Deal swiftly with empty graphs.
Count vertices + find the maximum edge weight.
If p is an edge endpoint, endpoint[p] is the vertex to which endpoint p is attached. Not modified by the algorithm.
If v is a vertex, neighbend[v] is the list of remote endpoints of the edges attached to v. Not modified by the algorithm.
If v is a vertex, mate[v] is the remote endpoint of its matched edge, or -1 if it is single (i.e. endpoint[mate[v]] is v's partner vertex). Initially all vertices are single; updated during augmentation.
If b is a top-level blossom, label[b] is 0 if b is unlabeled (free); 1 if b is an S-vertex/blossom; 2 if b is a T-vertex/blossom. The label of a vertex is found by looking at the label of its top-level containing blossom. If v is a vertex inside a T-blossom, label[v] is 2 iff v is reachable from an S-vertex outside the blossom. Labels are assigned during a stage and reset after each augmentation.
If b is a labeled top-level blossom, labelend[b] is the remote endpoint of the edge through which b obtained its label, or -1 if b's base vertex is single. If v is a vertex inside a T-blossom and label[v] === 2, labelend[v] is the remote endpoint of the edge through which v is reachable from outside the blossom.
If v is a vertex, inblossom[v] is the top-level blossom to which v belongs. If v is a top-level vertex, v is itthis a blossom (a trivial blossom) and inblossom[v] === v. Initially all vertices are top-level trivial blossoms.
If b is a sub-blossom, blossomparent[b] is its immediate parent (sub-)blossom. If b is a top-level blossom, blossomparent[b] is -1.
If b is a non-trivial (sub-)blossom, blossomchilds[b] is an ordered list of its sub-blossoms, starting with the base and going round the blossom.
If b is a (sub-)blossom, blossombase[b] is its base VERTEX (i.e. recursive sub-blossom).
If b is a non-trivial (sub-)blossom, blossomendps[b] is a list of endpoints on its connecting edges, such that blossomendps[b][i] is the local endpoint of blossomchilds[b][i] on the edge that connects it to blossomchilds[b][wrap(i+1)].
If v is a free vertex (or an unreached vertex inside a T-blossom), bestedge[v] is the edge to an S-vertex with least slack, or -1 if there is no such edge. If b is a (possibly trivial) top-level S-blossom, bestedge[b] is the least-slack edge to a different S-blossom, or -1 if there is no such edge. This is used for efficient computation of delta2 and delta3.
If b is a non-trivial top-level S-blossom, blossombestedges[b] is a list of least-slack edges to neighbouring S-blossoms, or null if no such list has been computed yet. This is used for efficient computation of delta3.
List of currently unused blossom numbers.
If v is a vertex, dualvar[v] = 2 * u(v) where u(v) is the v's variable in the dual optimization problem (multiplication by two ensures integer values throughout the algorithm if all edge weights are integers). If b is a non-trivial blossom, dualvar[b] = z(b) where z(b) is b's variable in the dual optimization problem.
If allowedge[k] is true, edge k has zero slack in the optimization problem; if allowedge[k] is false, the edge's slack may or may not be zero.
Queue of newly discovered S-vertices.
Return 2 * slack of edge k (does not work inside blossoms).
Generate the leaf vertices of a blossom.
Assign label t to the top-level blossom containing vertex w and record the fact that w was reached through the edge with remote endpoint p.
b became an S-vertex/blossom; add it(s vertices) to the queue.
b became a T-vertex/blossom; assign label S to its mate. (If b is a non-trivial blossom, its base is the only vertex with an external mate.)
Trace back from vertices v and w to discover either a new blossom or an augmenting path. Return the base vertex of the new blossom or -1.
Trace back from v and w, placing breadcrumbs as we go.
Look for a breadcrumb in v's blossom or put a new breadcrumb.
Trace one step back.
The base of blossom b is single; stop tracing this path.
b is a T-blossom; trace one more step back.
Swap v and w so that we alternate between both paths.
Remove breadcrumbs.
Return base vertex, if we found one.
Construct a new blossom with given base, containing edge k which connects a pair of S vertices. Label the new blossom as S; set its dual variable to zero; relabel its T-vertices to S and add them to the queue.
Create blossom.
Make list of sub-blossoms and their interconnecting edge endpoints.
Trace back from v to base.
Add bv to the new blossom.
Trace one step back.
Reverse lists, add endpoint that connects the pair of S vertices.
Trace back from w to base.
Add bw to the new blossom.
Trace one step back.
Set label to S.
Set dual variable to zero.
Relabel vertices.
This T-vertex now turns into an S-vertex because it becomes part of an S-blossom; add it to the queue.
Compute blossombestedges[b].
This subblossom does not have a list of least-slack edges; get the information from the vertices.
Walk this subblossom's least-slack edges.
Forget about least-slack edges of the subblossom.
Select bestedge[b].
Expand the given top-level blossom.
Convert sub-blossoms into top-level blossoms.
Recursively expand this sub-blossom.
If we expand a T-blossom during a stage, its sub-blossoms must be relabeled.
Start at the sub-blossom through which the expanding blossom obtained its label, and relabel sub-blossoms untili we reach the base. Figure out through which sub-blossom the expanding blossom obtained its label initially.
Decide in which direction we will go round the blossom.
Start index is odd; go forward.
Start index is even; go backward.
Move along the blossom until we get to the base.
Relabel the T-sub-blossom.
Step to the next S-sub-blossom and note its forward endpoint.
Step to the next T-sub-blossom.
Relabel the base T-sub-blossom WITHOUT stepping through to its mate (so don't call assignLabel).
Continue along the blossom until we get back to entrychild.
Examine the vertices of the sub-blossom to see whether it is reachable from a neighbouring S-vertex outside the expanding blossom.
This sub-blossom just got label S through one of its neighbours; leave it.
If the sub-blossom contains a reachable vertex, assign label T to the sub-blossom.
Recycle the blossom number.
Swap matched/unmatched edges over an alternating path through blossom b between vertex v and the base vertex. Keep blossom bookkeeping consistent.
Bubble up through the blossom tree from vertex v to an immediate sub-blossom of b.
Recursively deal with the first sub-blossom.
Decide in which direction we will go round the blossom.
Start index is odd; go forward.
Start index is even; go backward.
Move along the blossom until we get to the base.
Step to the next sub-blossom and augment it recursively.
Step to the next sub-blossom and augment it recursively.
Match the edge connecting those sub-blossoms.
Rotate the list of sub-blossoms to put the new base at the front.
Swap matched/unmatched edges over an alternating path between two single vertices. The augmenting path runs through edge k, which connects a pair of S vertices.
Match vertex s to remote endpoint p. Then trace back from s until we find a single vertex, swapping matched and unmatched edges as we go.
Augment through the S-blossom from s to base.
Update mate[s]
Trace one step back.
Reached single vertex; stop.
Trace one step back.
Augment through the T-blossom from j to base.
Update mate[j]
Keep the opposite endpoint; it will be assigned to mate[s] in the next step.
Verify that the optimum solution has been reached.
Vertices may have negative dual; find a constant non-negative number to add to all vertex duals.
Ok.
Check optimized delta2 against a trivial computation.
Check optimized delta3 against a trivial computation.
Main loop: continue until no further improvement is possible.
Each iteration of this loop is a "stage". A stage finds an augmenting path and uses that to improve the matching.
Remove labels from top-level blossoms/vertices.
Forget all about least-slack edges.
Loss of labeling means that we can not be sure that currently allowable edges remain allowable througout this stage.
Make queue empty.
Label single blossoms/vertices with S and put them in the queue.
Loop until we succeed in augmenting the matching.
Each iteration of this loop is a "substage". A substage tries to find an augmenting path; if found, the path is used to improve the matching and the stage ends. If there is no augmenting path, the primal-dual method is used to pump some slack out of the dual variables.
Continue labeling until all vertices which are reachable through an alternating path have got a label.
Take an S vertex from the queue.
Scan its neighbours:
w is a neighbour to v
this edge is internal to a blossom; ignore it
edge k has zero slack => it is allowable
(C1) w is a free vertex; label w with T and label its mate with S (R12).
(C2) w is an S-vertex (not in the same blossom); follow back-links to discover either an augmenting path or a new blossom.
Found a new blossom; add it to the blossom bookkeeping and turn it into an S-blossom.
Found an augmenting path; augment the matching and end this stage.
w is inside a T-blossom, but w itthis has not yet been reached from outside the blossom; mark it as reached (we need this to relabel during T-blossom expansion).
keep track of the least-slack non-allowable edge to a different S-blossom.
w is a free vertex (or an unreached vertex inside a T-blossom) but we can not reach it yet; keep track of the least-slack edge that reaches w.
There is no augmenting path under these constraints; compute delta and reduce slack in the optimization problem. (Note that our vertex dual variables, edge slacks and delta's are pre-multiplied by two.)
Verify data structures for delta2/delta3 computation.
Compute delta1: the minumum value of any vertex dual.
Compute delta2: the minimum slack on any edge between an S-vertex and a free vertex.
Compute delta3: half the minimum slack on any edge between a pair of S-blossoms.
Compute delta4: minimum z variable of any T-blossom.
No further improvement possible; max-cardinality optimum reached. Do a final delta update to make the optimum verifyable.
Update dual variables according to delta.
S-vertex: 2u = 2u - 2*delta
T-vertex: 2u = 2u + 2*delta
top-level S-blossom: z = z + 2*delta
top-level T-blossom: z = z - 2*delta
Take action at the point where minimum delta occurred.
No further improvement possible; optimum reached.
Use the least-slack edge to continue the search.
Use the least-slack edge to continue the search.
Expand the least-z blossom.
End of a this substage.
Stop when no more augmenting path can be found.
End of a stage; expand all S-blossoms which have dualvar = 0.
Verify that we reached the optimum solution.
Transform mate[] such that mate[v] is the vertex to which v is paired.
Adapted from http://jorisvr.nl/maximummatching.html All credit for the implementation goes to Joris van Rantwijk [http://jorisvr.nl].