COIN-OR::LEMON - Graph Library

Opened 3 years ago

Closed 3 years ago

#638 closed defect (fixed)

Segmentation fault on matching for SimpleGraph

Reported by: Fabio Durastante Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: release branch 1.3
Keywords: stack overflow, matching Cc:
Revision id:

Description

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.

Attachments (3)

weightmatrix_256005x256005.tar.xz (11.3 MB) - added by Fabio Durastante 3 years ago.
Weighted adjacency matrix of the graph in matrix market format
51691ae2d947.patch (7.8 KB) - added by Balazs Dezso 3 years ago.
008bc4c6ed4a.patch (8.2 KB) - added by Balazs Dezso 3 years ago.

Change History (8)

Changed 3 years ago by Fabio Durastante

Weighted adjacency matrix of the graph in matrix market format

comment:1 Changed 3 years ago by 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.

Changed 3 years ago by Balazs Dezso

Attachment: 51691ae2d947.patch added

comment:2 Changed 3 years ago by Alpar Juttner

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

comment:3 Changed 3 years ago by 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!

Changed 3 years ago by Balazs Dezso

Attachment: 008bc4c6ed4a.patch added

comment:4 Changed 3 years ago by 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.

comment:5 Changed 3 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

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

Note: See TracTickets for help on using tickets.