Indentation in lines 72,73 is off, leading to an endless loop about edmonds-blossom HOT 4 CLOSED

Hi, could you please provide a sample? Thanks!

from edmonds-blossom.

Sure, though I do not have a (very) small sample at hand. Consider

edges =[(3, 0), (0, 3), (3, 1), (1, 3), (3, 2), (2, 3), (4, 3), (3, 4), (5, 0), (0, 5), (5, 1), (1, 5), (5, 2), (2, 5), (5, 3), (3, 5), (5, 4), (4, 5), (6, 0), (0, 6), (6, 1), (1, 6), (6, 2), (2, 6), (6, 3), (3, 6), (6, 4), (4, 6), (6, 5), (5, 6), (7, 0), (0, 7), (7, 1), (1, 7), (7, 2), (2, 7), (7, 3), (3, 7), (7, 4), (4, 7), (7, 5), (5, 7), (7, 6), (6, 7), (8, 0), (0, 8), (8, 1), (1, 8), (8, 2), (2, 8), (8, 3), (3, 8), (8, 4), (4, 8), (8, 5), (5, 8), (8, 6), (6, 8), (8, 7), (7, 8), (9, 0), (0, 9), (9, 1), (1, 9), (9, 2), (2, 9), (9, 3), (3, 9), (9, 4), (4, 9), (9, 5), (5, 9), (9, 6), (6, 9), (9, 7), (7, 9), (9, 8), (8, 9)]

being the set of edges (listed both ways, i.e. (i,j) and (j,i) as you did in test.py) of a graph on 10 nodes, which is almost fully-connected. This is the smallest example I could produce. When I run

match = Match.from_edges(num_nodes,edges)
match.unmatched_nodes()

the program consistently gets stuck in Path's replace method. I have not had it get stuck after increasing indentation by one of
else:
raise Exception("replace error.")
in the while loop in Path's replace method.

I am running Python 2.7.13 in an Anaconda environment on Windows.

from edmonds-blossom.

Hi Azii, the bug is fixed. Thanks for your detailed comment.

The reason is not as you guess, but when a blossom is found, we need to continue searching from the contracted blossom, because some nodes in the search queue may have nodes in the blossom being their ancestors within the search tree.

from edmonds-blossom.

That is interesting, I seem not to have understood the code correctly. Though I have not dealt with the algorithm myself anyway. I'd never encountered a for/else construct before and took that as being the bug. Thanks again for providing the implementation! I'm doing the foobar challenge for fun and needed a maximum matching :) Your new code worked like a charm!

from edmonds-blossom.