suvajit790 / edmonds-blossom

Edmonds' blossom shrinking algorithm for finding best matching in general graphs

Edmonds' blossom shrinking algorithm

• Insert the graph in adjacency matrix formats in a text file
• Pass the text file through command line argument like

./a.out graph.txt

• The maximum matching array will be shown as output where if vertex a is matched with vertex b then it will be shown as a[b] b[a] if a vetex v is not matched with any other vertex then v[-1] will be shown.

edmonds-blossom's Issues

How should we interpret the output result?

For your first graph (in graph.txt), we get this

1 1 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 
0 1 1 1 0 0 0 0 0 0 0 
0 0 1 1 1 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 1 0 0 
0 0 0 0 1 1 1 0 0 0 0 
0 0 0 0 0 1 1 1 0 1 0 
0 0 0 0 0 0 1 1 1 0 0 
0 0 0 0 1 0 0 1 1 0 0 
0 0 0 0 0 0 1 0 0 1 1 
0 0 0 0 0 0 0 0 0 1 1 
0 -> 1
Augmenting Path (0-1)
2 -> 1
2 -> 3
Augmenting Path (2-3)
4 -> 3
4 -> 5
Augmenting Path (4-5)
6 -> 5
6 -> 7
Augmenting Path (6-7)
8 -> 4
8 -> 7
9 -> 6
Augmenting Path (9-6-7-8)
10 -> 9
6 -> 5
6 -> 7
4 -> 3
4 -> 8
Blossom (4,5,6,7,8)
5 -> 4
6 -> 3
2 -> 1
Maximum Matching = 0[1] 1[0] 2[3] 3[2] 4[5] 5[4] 6[9] 7[8] 8[7] 9[6] 10[-1] 

How should we interpret this result, especially the maximum matching? 0[1] and 1[0] is not same? Why does an edge appears two times, and why does 10[-1] appear? What does -1 mean?