COIN-OR::LEMON - Graph Library

Opened 2 years ago

Closed 6 weeks 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)

da78005589e9.patch (2.9 KB) - added by Alpar Juttner 2 years ago.
3d9bcf07f7e5.patch (7.6 KB) - added by Balazs Dezso 7 weeks ago.
6e5eaf83872f.patch (7.8 KB) - added by Balazs Dezso 6 weeks ago.

Download all attachments as: .zip

Change History (10)

Changed 2 years ago by Alpar Juttner

Attachment: da78005589e9.patch added

comment:1 Changed 2 years ago by 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?

comment:2 Changed 2 years ago by 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.

Changed 7 weeks ago by Balazs Dezso

Attachment: 3d9bcf07f7e5.patch added

comment:3 Changed 7 weeks ago by 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.

comment:4 Changed 6 weeks ago by 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.)

Changed 6 weeks ago by Balazs Dezso

Attachment: 6e5eaf83872f.patch added

comment:5 Changed 6 weeks ago by Balazs Dezso

New patch with the recommended comment is available.

comment:6 Changed 6 weeks ago by Alpar Juttner

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

comment:7 Changed 6 weeks ago by Alpar Juttner

Resolution: done
Status: newclosed
Note: See TracTickets for help on using tickets.