COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#356 closed defect (fixed)

MaxWeightedPerfectMatching re-run crash

Reported by: Ben Strasser Owned by: Balazs Dezso
Priority: critical Milestone: LEMON 1.2 release
Component: core Version: release branch 1.1
Keywords: MaxWeightedPerfectMatching run Cc:
Revision id:

Description (last modified by Alpar Juttner)

Hello,

when calling run a second time after changing the referenced graph and weights the matching function may crash.

Graph g;
Graph::EdgeMap<int>w(g);
// fill g and w
MaxWeightedPerfectMatching<Graph> mm(g, w);
mm.run();
// modify g and w
mm.run();
for(EdgeIt i(g);i!=INVALID; ++i)
  mm.matching(i); // This can crash here

Version is the 1.1.2 Download from the main site.

Attachments (2)

4ac8f688b6fc.patch (6.6 KB) - added by Balazs Dezso 10 years ago.
Fix multiple execution
dd9ba625e801.patch (3.0 KB) - added by Balazs Dezso 10 years ago.
Fractional matching and jumpstart

Download all attachments as: .zip

Change History (11)

comment:1 Changed 10 years ago by Alpar Juttner

Description: modified (diff)
Milestone: LEMON 1.2 release
Owner: changed from Alpar Juttner to Balazs Dezso
Priority: minorcritical

comment:2 Changed 10 years ago by Alpar Juttner

Thanks for reporting this problem. In your orig e-mail you were talking about changing w only. Can you confirm that the problem can also appear when you don't touch the graph but only the weights?

comment:3 Changed 10 years ago by Balazs Dezso

Status: newassigned

Changed 10 years ago by Balazs Dezso

Attachment: 4ac8f688b6fc.patch added

Fix multiple execution

comment:4 Changed 10 years ago by Balazs Dezso

Some of the data structures were not cleared between executions. It is fixed already in [4ac8f688b6fc].

comment:5 Changed 10 years ago by Ben Strasser

Can you confirm that the problem can also appear when you don't touch the graph but only the weights?

No

comment:6 in reply to:  4 Changed 10 years ago by Alpar Juttner

Replying to deba:

Some of the data structures were not cleared between executions. It is fixed already in [4ac8f688b6fc].

Thanks. The bugfix was rebased as [5b926cc36a4b], then it has been merged to both 1.1 and the default branches. So, it will be included in the soon-to-be-come 1.2 release and in release 1.1.3 (which will be released a bit later, probably along with the first bugfix release of 1.2).

The jumpstart matching initialization (see #314) has also been merged into the main branch. Could you check if it also works correctly in case of the multiple execution?

Some specific test cases for the multiple execution could also be nice.

Changed 10 years ago by Balazs Dezso

Attachment: dd9ba625e801.patch added

Fractional matching and jumpstart

comment:7 Changed 10 years ago by Balazs Dezso

The patch [dd9ba625e801] solves the same problem in fractional matching algorithms and in jumpstart initialization.

comment:8 in reply to:  7 Changed 10 years ago by Alpar Juttner

Replying to deba:

The patch [dd9ba625e801] solves the same problem in fractional matching algorithms and in jumpstart initialization.

It went to the main branch with changes log msg, see [7f6e2bd76654]

comment:9 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.