Opened 8 years ago
Closed 5 years ago
#604 closed enhancement (done)
Faster MaxMatching implementation
Reported by: | Alpar Juttner | Owned by: | Balazs Dezso |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.4 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | joran.van.apeldoorn@… | |
Revision id: |
Description
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.
Attachments (3)
Change History (10)
Changed 8 years ago by
Attachment: | da78005589e9.patch added |
---|
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
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.
Changed 5 years ago by
Attachment: | 3d9bcf07f7e5.patch added |
---|
comment:3 Changed 5 years ago by
I have created a new patch [3d9bcf07f7e5].
It keeps track of the number of unmatched nodes and stops if there is only one.
comment:4 Changed 5 years ago by
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.)
Changed 5 years ago by
Attachment: | 6e5eaf83872f.patch added |
---|
comment:7 Changed 5 years ago by
Resolution: | → done |
---|---|
Status: | new → closed |
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 inMaxWeightedMatching
, too?