yorkyer / edmonds-blossom Goto Github PK

The program will be stuck in an endless loop in this case:

edges = [(1, 3), (1, 7), (1, 4), (7, 8), (7, 1), (7, 2), (7, 9), (5, 2), (8, 3), (8, 7), (8, 4), (8, 6), (4, 1), (4, 2), (4, 8), (4, 9), (3, 8), (3, 2), (3, 9), (3, 1), (3, 6), (2, 7), (2, 3), (2, 0), (2, 4), (2, 5), (0, 2), (6, 8), (6, 3), (9, 3), (9, 4), (9, 7)]
match = Match.from_edges(10, edges)

Hello yorkyer,
first off all, thank you for providing this implementation of the blossom algorithm! I had an issue with it: In many cases it did not terminate. After tracing where it got stuck, I think I found the error: In lines 72,73 the indentation seems to be off, leading to no exception being raised.
Best, Azad

from max_matching import Match
unique_edges = [(0, 1), (0, 14), (1, 2), (2, 15), (2, 3), (3, 4), (4, 27), (5, 6), (5, 26), (6, 7), (7, 25), (7, 8), (8, 9), (9, 24), (9, 10), (10, 11), (12, 13), (12, 16), (13, 14), (14, 15), (16, 17), (18, 19), (18, 21), (19, 20), (21, 22), (22, 23), (24, 25), (26, 27)]
edges = unique_edges + [(j,i) for i,j in unique_edges]
match = Match.from_edges(28, edges)
match.maximum_matching()
for n in match.nodes:
if n.mate is not None:
i = n.index
j = n.mate.index
if i < j:
print(i,j)

9 is duplicated

#0 14
#2 3
#4 27
#5 26
#6 7
#8 9
#9 24
#10 11
#12 13
#16 17
#18 21
#19 20
#22 23

https://github.com/yorkyer/edmonds-blossom/blob/b4b2335b4ff42fc9fd06f1dfb01bbce4fc4326da/test.py#L1