COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#264 closed defect (fixed)

Improvements and fixes for some algorithms

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.1 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description


Attachments (5)

impr-ec88ea358b76-477748655ff2-d5355a5e7b6a.bundle (9.9 KB) - added by Peter Kovacs 10 years ago.
impr1-293551ad254f.patch (25.8 KB) - added by Peter Kovacs 10 years ago.
impr2-493533ead9df-2ebfdb89ec66.bundle (3.6 KB) - added by Peter Kovacs 10 years ago.
impr3-b61354458b59.patch (37.9 KB) - added by Peter Kovacs 10 years ago.
2ca0cdb5f366.patch (3.5 KB) - added by Balazs Dezso 10 years ago.
Bug fix in HaoOrlin?

Download all attachments as: .zip

Change History (19)

Changed 10 years ago by Peter Kovacs

comment:1 Changed 10 years ago by Peter Kovacs

Status: newassigned

The attached bundle file contains three changesets: [ec88ea358b76], [477748655ff2], [d5355a5e7b6a], all of which significantly improve the documentation and the test files of some algorithms or tools.

comment:2 Changed 10 years ago by Peter Kovacs

These changes revealed another problem/bug. In [477748655ff2] I extended the test file for HaoOrlin, since it was only tested for an undirected graph although it is designed for directed graphs. It gives zero as the minimum cut value for all the three digraph instances I've added to the test file, although as far as I understand the definition of the problem, all instances should have positive solution. See the hao_orlin_test.cc file for more details.

Could someone check the test digraph instances and verify or contradict the bug notes I put in the test file?

comment:3 in reply to:  2 ; Changed 10 years ago by Peter Kovacs

Replying to kpeter:

Could someone check the test digraph instances and verify or contradict the bug notes I put in the test file?

I made a mistake in this test file, [293551ad254f] contains a fixed version for this problematic changeset. It still gives faulty results, as far as I see. Could someone check it, please?

Changed 10 years ago by Peter Kovacs

Attachment: impr1-293551ad254f.patch added

Changed 10 years ago by Peter Kovacs

comment:4 Changed 10 years ago by Peter Kovacs

The attached bundle file contains two changesets: [493533ead9df], [2ebfdb89ec66]. The first one is bug fix for Euler iterators, the second one contains a lot of doc + test improvements for the Euler tools. (It is an extended version of the previous changeset [ec88ea358b76]).

Changed 10 years ago by Peter Kovacs

Attachment: impr3-b61354458b59.patch added

comment:5 Changed 10 years ago by Peter Kovacs

And finally [b61354458b59] is the same as [d5355a5e7b6a], but it is rebased on the top the current main repository.

comment:6 Changed 10 years ago by Alpar Juttner

I got lost. Could you explain which changesets are still relevant?

comment:7 in reply to:  6 ; Changed 10 years ago by Peter Kovacs

Replying to alpar:

I got lost. Could you explain which changesets are still relevant?

All changesets except for the ones in the first bundle file.

  • [293551ad254f] for the min. cut algorithms (HaoOrlin and GomoryHu). HaoOrlin still seems to give false results. make check passes for this changeset, but it shouldn't (and there are additional checks which are in comments now, but they should also work) as far as I understand.
  • [493533ead9df] and [2ebfdb89ec66] for the Euler tools (bug fix + improvements).
  • [d5355a5e7b6a] for the matching algorithms.

All of them are rebased on [630c4898c548].

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

Replying to kpeter:

Replying to alpar:

I got lost. Could you explain which changesets are still relevant?

And what about [b61354458b59]? Is it relevant too?

comment:9 in reply to:  3 ; Changed 10 years ago by Alpar Juttner

Replying to kpeter:

I made a mistake in this test file, [293551ad254f] contains a fixed version for this problematic changeset. It still gives faulty results, as far as I see. Could someone check it, please?

Have this issue been resolved somewhere?

comment:10 in reply to:  8 Changed 10 years ago by Peter Kovacs

Replying to alpar:

Replying to kpeter:

Replying to alpar:

I got lost. Could you explain which changesets are still relevant?

And what about [b61354458b59]? Is it relevant too?

I made a mistake, I wrote [d5355a5e7b6a], but I wanted to write [b61354458b59]. They are indeed the same, but the later one is rebased on the top of the main repository.

So consider:

comment:11 in reply to:  9 ; Changed 10 years ago by Peter Kovacs

Replying to alpar:

Replying to kpeter:

I made a mistake in this test file, [293551ad254f] contains a fixed version for this problematic changeset. It still gives faulty results, as far as I see. Could someone check it, please?

Have this issue been resolved somewhere?

No. make check passes in [293551ad254f], but I think it shouldn't.

The other three changesets that were mentioned in my previous comment could be pushed into the main branch.

comment:12 in reply to:  11 Changed 10 years ago by Alpar Juttner

Replying to kpeter:

Have this issue been resolved somewhere?

No. make check passes in [293551ad254f], but I think it shouldn't.

Do something with it, please.

The other three changesets that were mentioned in my previous comment could be pushed into the main branch.

Done.

Changed 10 years ago by Balazs Dezso

Attachment: 2ca0cdb5f366.patch added

Bug fix in HaoOrlin?

comment:13 in reply to:  2 Changed 10 years ago by Balazs Dezso

Replying to kpeter:

These changes revealed another problem/bug. In [477748655ff2] I extended the test file for HaoOrlin, since it was only tested for an undirected graph although it is designed for directed graphs. It gives zero as the minimum cut value for all the three digraph instances I've added to the test file, although as far as I understand the definition of the problem, all instances should have positive solution. See the hao_orlin_test.cc file for more details.

Could someone check the test digraph instances and verify or contradict the bug notes I put in the test file?

I checked the new tests, and the results were really wrong. The problem came from the missing reinitialization of _source_set. The [2ca0cdb5f366] contains the patch.

comment:14 Changed 10 years ago by Alpar Juttner

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