Faster MaxMatching implementation

[Alpar Juttner]

From Joran van Apeldoorn:

On odd graphs it does not notice when a perfect matching (as in (n-1)/2 matched edges) is found and continues to do a BFS from the one unmatched vertex, off course without result. This makes the running time for slightly dense graphs a lot longer on odd graphs then on even graphs, to the extend that it can take easely a 100 times longer on odd graphs.

[Alpar Juttner]

The attached changeset [da78005589e9] is a straightforward implementation of this idea. Could someone review it?

Right now only MaxMatching is modified. Shouldn't we do the same in MaxWeightedMatching, too?

[Balazs Dezso]

If we stop the algorithm early, then we don't find a Gallai-Edmonds decomposition.

Otherwise, I think it's better to maintain the number of nodes in UNMATCHED status. If that goes below 2, then we can stop. It's slightly more efficient than your solution, because the number of UNMATCHED nodes decreased even if we fail to find a larger matching in a process step.

I think the same idea doesn't work for weighted matchings, because it's not guaranteed that the solution is optimal when only one node is not covered in the matching.

[Balazs Dezso]

I have created a new patch [3d9bcf07f7e5].

It keeps track of the number of unmatched nodes and stops if there is only one.

[Peter Kovacs]

I think it would be better to add a sentence to the doc that using decomposition = false can make the algorithm significantly faster for graphs with odd number of nodes. (Provided that I understand correctly.)

[Balazs Dezso]

New patch with the recommended comment is available.

[Alpar Juttner]

It went to the main branch as [8c567e298d7f].