Bug: KolmogorovWeightedPerfectMatching.getMatching runs indefinitely

[luraith]

 * JGraphT version: 1.5.2
 * Java version (java -version)/platform:  18.0.2

Issue
For some graphs KolmogorovWeightedPerfectMatching.getMatching takes either very long to return a result or runs indefinetly (it seems to me that the latter is the case, but of couse I can't exclude that possibility that it would everually return something)

Steps to reproduce (small coding example)
Download example_graph.txt and run

SimpleWeightedGraph<Integer, DefaultWeightedEdge> graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

KolmogorovWeightedPerfectMatching<Integer, DefaultWeightedEdge> matcher = new KolmogorovWeightedPerfectMatching<>(graph, ObjectiveSense.MAXIMIZE);


Integer[] v = new Integer[32];

for(int i = 0; i < 32; i++) {
	v[i] = Integer.valueOf(i);
	graph.addVertex(v[i]);
}

BufferedReader bf = new BufferedReader(new FileReader("example_graph.txt"));

for(int i = 0; i < 32; i++)
	for(int k = i+1; k < 32; k++) {
		
		String s = bf.readLine();
		String weight = s.split(" ")[1];
		
		DefaultWeightedEdge e = graph.addEdge(v[i], v[k]);
		graph.setEdgeWeight(e, Double.parseDouble(weight));
		
	}

System.out.println("before matching " + System.currentTimeMillis());
Matching<Integer, DefaultWeightedEdge> matching = matcher.getMatching();
System.out.println("after matching " + System.currentTimeMillis());

Expected behaviour
The last line of code will never gets executed because the getMatching Method of KolmogorovWeightedPerfectMatching never returns

[jsichi]

@Toptachamann could you take a look?

[luraith]

I noticed the license sales page for the original implementation of Blossom V states "By default, the code uses weights of type “int”. While it is possible to change it to “double”, it is not recommended: rounding errors may then lead to unexpected behaviour, such as non-termination. Internally, small numbers are represented as differences of big numbers, so with a floating point precision the code becomes unstable." Perhaps a same or similiar problem is the source of non-termination here?