COIN-OR::LEMON - Graph Library

Opened 4 weeks ago

Last modified 4 weeks ago

#650 new defect

MaxWeightedPerfectMatching fails for some graphs

Reported by: Oscar Higgott Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: MaxWeightedPerfectMatching Cc:
Revision id:

Description

MaxWeightedPerfectMatching fails to find a solution for some graphs (i.e. MaxWeightedPerfectMatching.run() returns false).

I attach 4 graphs which fail (failing_graph_i.lgf for i=1,2,3,4), as well as one which succeeds (working_graph.lgf), drawn from the same distribution, for comparison.

The attached file main.cpp attempts to solve the MWPM problem using lemon::MaxWeightedPerfectMatching for these graphs and output success/failure.

All five graphs are drawn from the same distribution (from which >1% of graphs fail), however for failing_graph_1.lgf and failing_graph_2.lgf I changed all the edge weights to 1, and the MWPM problem still fails (i.e. the problem seems to be independent of the choice of edge weights).

I have tested this using versions lemon-main-a278d16bd2d0 and lemon-1-3-e5af35e6c93f (both fail).

Attachments (6)

main.cpp (994 bytes) - added by Oscar Higgott 4 weeks ago.
Loads the lgf graphs and outputs success/failure of MaxWeightedPerfectMatching?
failing_graph_1.lgf (4.8 KB) - added by Oscar Higgott 4 weeks ago.
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
failing_graph_2.lgf (4.5 KB) - added by Oscar Higgott 4 weeks ago.
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
failing_graph_3.lgf (30.5 KB) - added by Oscar Higgott 4 weeks ago.
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
failing_graph_4.lgf (33.6 KB) - added by Oscar Higgott 4 weeks ago.
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
working_graph.lgf (30.9 KB) - added by Oscar Higgott 4 weeks ago.
A graph for which MaxWeightedPerfectMatching? succeeds (in LEMON graph format)

Download all attachments as: .zip

Change History (7)

Changed 4 weeks ago by Oscar Higgott

Attachment: main.cpp added

Loads the lgf graphs and outputs success/failure of MaxWeightedPerfectMatching?

Changed 4 weeks ago by Oscar Higgott

Attachment: failing_graph_1.lgf added

A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)

Changed 4 weeks ago by Oscar Higgott

Attachment: failing_graph_2.lgf added

A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)

Changed 4 weeks ago by Oscar Higgott

Attachment: failing_graph_3.lgf added

A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)

Changed 4 weeks ago by Oscar Higgott

Attachment: failing_graph_4.lgf added

A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)

Changed 4 weeks ago by Oscar Higgott

Attachment: working_graph.lgf added

A graph for which MaxWeightedPerfectMatching? succeeds (in LEMON graph format)

comment:1 Changed 4 weeks ago by Oscar Higgott

Having looked again at the graphs I see that the ones that "failed" in fact don't have a perfect matching, so it's a problem with the graphs not LEMON, apologies. I wasn't sure of the definition of the bool returned by MaxWeightedPerfectMatching.run(), but I now assume it only returns false if the graph doesn't have a perfect matching. It might be worth clarifying this in the docs, but otherwise feel free to close this ticket.

Note: See TracTickets for help on using tickets.