Segmentation fault on matching for SimpleGraph

[Fabio Durastante]

Hi,

I encounter a Segmentation fault when running the MaxWeightedMatching? algorithm for a SmartGraph? object. Valgrind tells me that there is a stack-overflow. Compiling with GCC version 7.5.0 and -fsanitize=address I get pointed to an error in

    #7 0x55d64a51fea8 in void lemon::HeapUnionFind<double, lemon::GraphExtender<lemon::SmartGraphBase>::NodeMap<int>, std::less<double> >::split<std::back_insert_iterator<std::vector<int, std::allocator<int> > > >(int, std::back_insert_iterator<std::vector<int, std::allocator<int> > >) /auxlibs/include/lemon/unionfind.h:1563
    #8 0x55d64a542d2e in lemon::MaxWeightedMatching<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double> >::extractBlossom(int, lemon::SmartGraphBase::Node const&, lemon::SmartGraphBase::Arc const&) /auxlibs/include/lemon/matching.h:1518

I am attaching a matrix market file with the weighted adjacency graph of the matrix causing the error.

Thank you very much.

[Fabio Durastante]

Weighted adjacency matrix of the graph in matrix market format

[Balazs Dezso]

This SEGFAULT is caused by the recursive implementation of the extractBlossom() function. I could reproduce the problem and setting ulimit -s 65536 is a proper workaround.

However, the right solution is to refactor the code to a non-recursive version.

[Alpar Juttner]

A like this patch. Can I just merge into the main branch? Is there any remaining issue with it?

[Fabio Durastante]

Hi! Sorry for the delay in the answer. I have tried the patch on several test cases that were giving me the same issue, and it seems to be resolved. Thank you very much for the effort!

[Balazs Dezso]

I have just created an almost identical patch [008bc4c6ed4a], but I think the new patch is slightly more efficient (However, the blossom extraction is not the most critical part of this algorithm).

Otherwise, it looks to be OK to merge the patch to the main branch.

[Alpar Juttner]

The second version​ of the patch is in the main branch as [c6aa2cc1af04]. Thanks.