[Lemon-devel] Performance bug in MaxMatching

[Balazs Dezso]

Dear Developers,

I have found a performance bug in the MaxMatching implementation. The 
UnionFindEnum class was used to store the alternating tree blossoms. This 
class provides just really slow erasing operation, which running time is 
proportional to the number of the items in the component. I have solved the 
problem introducing a simpler class (ExtendFind), which is not able to merge 
two components, but it can erase an item in constant time.

Time measurement on random graph with n=10^5 nodes and m=1.5 * 10^5 edges:
Lemon current buggy implementation:
u: 47.99s, s: 0.09s, cu: 0s, cs: 0s, real: 49.1548s

Old UFE based: (with std::lists) (before svn 2929)
u: 62.93s, s: 0.15s, cu: 0s, cs: 0s, real: 64.5056s

My new version:
u: 0.74s, s: 0s, cu: 0s, cs: 0s, real: 0.752375s

I also made some tests, I used the nauty program to test the MaxMatching 
algorithm on all graphs with less than 11 nodes. At last, I redesigned the 
interface of the class.

Best, Balazs