Opened 4 years ago
Last modified 4 years 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 years ago by
Changed 4 years ago by
| Attachment: | failing_graph_1.lgf added |
|---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 years ago by
| Attachment: | failing_graph_2.lgf added |
|---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 years ago by
| Attachment: | failing_graph_3.lgf added |
|---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 years ago by
| Attachment: | failing_graph_4.lgf added |
|---|
A graph for which MaxWeightedPerfectMatching? fails (in LEMON graph format)
Changed 4 years ago by
| Attachment: | working_graph.lgf added |
|---|
A graph for which MaxWeightedPerfectMatching? succeeds (in LEMON graph format)
comment:1 Changed 4 years 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?