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)
Change History (7)
Changed 4 weeks ago by
Changed 4 weeks ago by
Attachment: | failing_graph_1.lgf added |
---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 weeks ago by
Attachment: | failing_graph_2.lgf added |
---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 weeks ago by
Attachment: | failing_graph_3.lgf added |
---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 weeks ago by
Attachment: | failing_graph_4.lgf added |
---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 weeks ago by
Attachment: | working_graph.lgf added |
---|
A graph for which MaxWeightedPerfectMatching? succeeds (in LEMON graph format)
comment:1 Changed 4 weeks ago by
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.
Loads the lgf graphs and outputs success/failure of MaxWeightedPerfectMatching?