id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	revision
650	MaxWeightedPerfectMatching fails for some graphs	Oscar Higgott	Alpar Juttner	"`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)."	defect	new	major	LEMON 1.4 release	core	hg main		MaxWeightedPerfectMatching