search

dkondor / maxmatch_MV

Micali Vazirani Maximum Cardinality Matching Algorithm for symmetric (undirected) graphs
7 stars 2 forks source link

Wrong matching sizes #1

Closed ripaul closed 5 years ago

ripaul commented 5 years ago

Hi there,

I'm currently working on approximate maximum cardinality matching algorithms and stumbled upon your implementation, when searching for a fast implementation of the Micali-Vazirani algorithm in order to benchmark my own results.

Although your implementation is quite fast, there seems to be a bug in your code: When run several times using the same input, the result differs between two values. Apparently sometimes your program does not search for the augmenting paths after passing the greedy initialization phase. I counter-checked the results of your program using the boost implementation of Edmond's blossom algorithm (https://github.com/ripaul/edmonds_blossom). There is also a test input for which you should be able to observe the bug. I tested your program on two machines using the test, on one the strange behavior only appears, when compiling without the -O3 flag. Also, when compiling with -Wall flag, a lot of warnings show up.

My results for the provided test input are size 4653 (which is wrong) and 6654 (which seems to be right, when counter-checking with the boost implementation and this one)

A fast and reliable MCM-algorithm would be quite helpful for my work, so I'd appreciate any help regarding this issue. Thanks in advance!

Best, Richi

dkondor commented 5 years ago

Hi, thanks for reporting this, I'll look into it. I can't find the test input you mention, could you check if you updated it in the repo? (or post a direct link to it in case I just can't find it)

Thanks, Daniel

dkondor commented 5 years ago

Also, in the meantime, I recommend LEMON (https://lemon.cs.elte.hu/trac/lemon); it is a fairly comprehensive graph library that can compute various maximum matchings. For me, the main limitation is that it only supports graphs with < 2^31 edges (edge IDs are stored as ints).

ripaul commented 5 years ago

Hi,

thanks for the reply. Indeed forgot to push the test file. Here it is: https://github.com/ripaul/edmonds_blossom/blob/master/enwiki.edgelist

Thanks for the LEMON advice, I'll have a look at it. But it seems they only have implemented Edmond's blossoms algorithm, not the Micali-Vazirani algorithm, which you implemented. I'd just like to test, if our algorithms can compete against the (as far as I am aware) fastest exact algorithm.

Thanks for having a look at it! Richi

dkondor commented 5 years ago

Hi,

it seems that the problem was caused by the matchnum variable being uninitialized in the MVGraph class. At least adding a debug printout before calling greedy_init() showed that it is a bogus value when the bug is present and always 0 when it is behaving correctly (for me, the bug is not deterministic, it triggers only sometime with your example file). So I think it is pretty easily fixed; let me know if it works for you now.

I also cleaned up the warnings (I was hoping to find something valuable there), mainly by changing the node level variables from int -> unsigned int as I realized these should never be negative; I hope this does not introduce any problems later.

Best, Daniel

ripaul commented 5 years ago

Hi Daniel,

the fix seems to have eliminated the bug, I receive the same matching size for several runs and same result as when I use the boost implementation.

But apparently I found a second bug. For this input, the program segfaults. I compiled using g++ -o mmmv *.cpp -march=native -std=gnu++14 -Wall -g, ran the program through valgrind and got the following output:

$ valgrind ./mmmv -i ../edmonds_blossom/bel.edgelist > /dev/null
==4353== Memcheck, a memory error detector
==4353== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4353== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==4353== Command: ./mmmv -i ../edmonds_blossom/bel.edgelist
==4353== 
==4353== Invalid read of size 4
==4353==    at 0x115201: MVGraph::MAX(unsigned int) (MV.cpp:91)
==4353==    by 0x114F58: MVGraph::max_match_phase() (MV.cpp:31)
==4353==    by 0x114EB8: MVGraph::max_match() (MV.cpp:17)
==4353==    by 0x121A3B: main (main.cpp:58)
==4353==  Address 0x19b52f90 is 1,600 bytes inside a block of size 16,384 free'd
==4353==    at 0x4C3123B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4353==    by 0x10D043: __gnu_cxx::new_allocator<std::pair<unsigned int, unsigned int> >::deallocate(std::pair<unsigned int, unsigned int>*, unsigned long) (new_allocator.h:125)
==4353==    by 0x10CC9A: std::allocator_traits<std::allocator<std::pair<unsigned int, unsigned int> > >::deallocate(std::allocator<std::pair<unsigned int, unsigned int> >&, std::pair<unsigned int, unsigned int>*, unsigned long) (alloc_traits.h:462)
==4353==    by 0x10C705: std::_Vector_base<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_deallocate(std::pair<unsigned int, unsigned int>*, unsigned long) (stl_vector.h:180)
==4353==    by 0x10C906: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_realloc_insert<std::pair<unsigned int, unsigned int> >(__gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, std::pair<unsigned int, unsigned int>&&) (vector.tcc:448)
==4353==    by 0x10C2C3: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::emplace_back<std::pair<unsigned int, unsigned int> >(std::pair<unsigned int, unsigned int>&&) (vector.tcc:105)
==4353==    by 0x10BF71: std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::push_back(std::pair<unsigned int, unsigned int>&&) (stl_vector.h:954)
==4353==    by 0x10EDF3: MVGraph::add_to_bridges(unsigned int, unsigned int, unsigned int) (Graph.cpp:43)
==4353==    by 0x115599: MVGraph::MAX(unsigned int) (MV.cpp:121)
==4353==    by 0x114F58: MVGraph::max_match_phase() (MV.cpp:31)
==4353==    by 0x114EB8: MVGraph::max_match() (MV.cpp:17)
==4353==    by 0x121A3B: main (main.cpp:58)
==4353==  Block was alloc'd at
==4353==    at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4353==    by 0x10D22B: __gnu_cxx::new_allocator<std::pair<unsigned int, unsigned int> >::allocate(unsigned long, void const*) (new_allocator.h:111)
==4353==    by 0x10D091: std::allocator_traits<std::allocator<std::pair<unsigned int, unsigned int> > >::allocate(std::allocator<std::pair<unsigned int, unsigned int> >&, unsigned long) (alloc_traits.h:436)
==4353==    by 0x10CE97: std::_Vector_base<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_allocate(unsigned long) (stl_vector.h:172)
==4353==    by 0x10C7E3: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_realloc_insert<std::pair<unsigned int, unsigned int> >(__gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, std::pair<unsigned int, unsigned int>&&) (vector.tcc:406)
==4353==    by 0x10C2C3: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::emplace_back<std::pair<unsigned int, unsigned int> >(std::pair<unsigned int, unsigned int>&&) (vector.tcc:105)
==4353==    by 0x10BF71: std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::push_back(std::pair<unsigned int, unsigned int>&&) (stl_vector.h:954)
==4353==    by 0x10EDF3: MVGraph::add_to_bridges(unsigned int, unsigned int, unsigned int) (Graph.cpp:43)
==4353==    by 0x1159D5: MVGraph::step_to(unsigned int, unsigned int, unsigned int) (MV.cpp:58)
==4353==    by 0x1150B6: MVGraph::MIN(unsigned int) (MV.cpp:74)
==4353==    by 0x114F47: MVGraph::max_match_phase() (MV.cpp:30)
==4353==    by 0x114EB8: MVGraph::max_match() (MV.cpp:17)
==4353== 
==4353== Invalid read of size 4
==4353==    at 0x11520D: MVGraph::MAX(unsigned int) (MV.cpp:92)
==4353==    by 0x114F58: MVGraph::max_match_phase() (MV.cpp:31)
==4353==    by 0x114EB8: MVGraph::max_match() (MV.cpp:17)
==4353==    by 0x121A3B: main (main.cpp:58)
==4353==  Address 0x19b52f94 is 1,604 bytes inside a block of size 16,384 free'd
==4353==    at 0x4C3123B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4353==    by 0x10D043: __gnu_cxx::new_allocator<std::pair<unsigned int, unsigned int> >::deallocate(std::pair<unsigned int, unsigned int>*, unsigned long) (new_allocator.h:125)
==4353==    by 0x10CC9A: std::allocator_traits<std::allocator<std::pair<unsigned int, unsigned int> > >::deallocate(std::allocator<std::pair<unsigned int, unsigned int> >&, std::pair<unsigned int, unsigned int>*, unsigned long) (alloc_traits.h:462)
==4353==    by 0x10C705: std::_Vector_base<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_deallocate(std::pair<unsigned int, unsigned int>*, unsigned long) (stl_vector.h:180)
==4353==    by 0x10C906: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_realloc_insert<std::pair<unsigned int, unsigned int> >(__gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, std::pair<unsigned int, unsigned int>&&) (vector.tcc:448)
==4353==    by 0x10C2C3: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::emplace_back<std::pair<unsigned int, unsigned int> >(std::pair<unsigned int, unsigned int>&&) (vector.tcc:105)
==4353==    by 0x10BF71: std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::push_back(std::pair<unsigned int, unsigned int>&&) (stl_vector.h:954)
==4353==    by 0x10EDF3: MVGraph::add_to_bridges(unsigned int, unsigned int, unsigned int) (Graph.cpp:43)
==4353==    by 0x115599: MVGraph::MAX(unsigned int) (MV.cpp:121)
==4353==    by 0x114F58: MVGraph::max_match_phase() (MV.cpp:31)
==4353==    by 0x114EB8: MVGraph::max_match() (MV.cpp:17)
==4353==    by 0x121A3B: main (main.cpp:58)
==4353==  Block was alloc'd at
==4353==    at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4353==    by 0x10D22B: __gnu_cxx::new_allocator<std::pair<unsigned int, unsigned int> >::allocate(unsigned long, void const*) (new_allocator.h:111)
==4353==    by 0x10D091: std::allocator_traits<std::allocator<std::pair<unsigned int, unsigned int> > >::allocate(std::allocator<std::pair<unsigned int, unsigned int> >&, unsigned long) (alloc_traits.h:436)
==4353==    by 0x10CE97: std::_Vector_base<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_allocate(unsigned long) (stl_vector.h:172)
==4353==    by 0x10C7E3: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::_M_realloc_insert<std::pair<unsigned int, unsigned int> >(__gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, std::pair<unsigned int, unsigned int>&&) (vector.tcc:406)
==4353==    by 0x10C2C3: void std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::emplace_back<std::pair<unsigned int, unsigned int> >(std::pair<unsigned int, unsigned int>&&) (vector.tcc:105)
==4353==    by 0x10BF71: std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >::push_back(std::pair<unsigned int, unsigned int>&&) (stl_vector.h:954)
==4353==    by 0x10EDF3: MVGraph::add_to_bridges(unsigned int, unsigned int, unsigned int) (Graph.cpp:43)
==4353==    by 0x1159D5: MVGraph::step_to(unsigned int, unsigned int, unsigned int) (MV.cpp:58)
==4353==    by 0x1150B6: MVGraph::MIN(unsigned int) (MV.cpp:74)
==4353==    by 0x114F47: MVGraph::max_match_phase() (MV.cpp:30)
==4353==    by 0x114EB8: MVGraph::max_match() (MV.cpp:17)
==4353== 
548.744079
221871
==4353== Conditional jump or move depends on uninitialised value(s)
==4353==    at 0x12216B: MVGraph::~MVGraph() (Graph.h:52)
==4353==    by 0x121B4F: main (main.cpp:51)
==4353== 
==4353== 
==4353== HEAP SUMMARY:
==4353==     in use at exit: 134,218,280 bytes in 2 blocks
==4353==   total heap usage: 1,557,139 allocs, 1,557,137 frees, 408,780,512 bytes allocated
==4353== 
==4353== LEAK SUMMARY:
==4353==    definitely lost: 0 bytes in 0 blocks
==4353==    indirectly lost: 0 bytes in 0 blocks
==4353==      possibly lost: 134,217,728 bytes in 1 blocks
==4353==    still reachable: 552 bytes in 1 blocks
==4353==         suppressed: 0 bytes in 0 blocks
==4353== Rerun with --leak-check=full to see details of leaked memory
==4353== 
==4353== For counts of detected and suppressed errors, rerun with: -v
==4353== Use --track-origins=yes to see where uninitialised values come from
==4353== ERROR SUMMARY: 23809 errors from 3 contexts (suppressed: 0 from 0)

The computed matching size (221871) however seems to be correct, I get the same result when using the boost implementation.

You mind having a look at this too? I really appreciate your help! Best, Richi

dkondor commented 5 years ago

Hi,

thanks for reporting this. One issue I found is vectors modified while looping over them in a C++11 style foreach loop -- this results in UB if the vector grows. I think this is the issue reported by valgrind in MVGraph::MAX -- for me, the crash appeared in the DDFS function called from MAX. For me, it is fixed now.

Also, there was a further problem (the uninitialized variable reported by valgrind) which I fixed. Let me know if it works now.

Best,

Daniel

ripaul commented 5 years ago

Hi,

thanks for the fixes! It seems to work very stably now, at least for all my small test inputs. Thank you very much for your support.

Best, Richi