COIN-OR::LEMON - Graph Library

Opened 16 years ago

Closed 12 years ago

#56 closed enhancement (done)

Port Nagamochi-Ibaraki algorithm

Reported by: Alpar Juttner Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.3 release
Component: core Version:
Keywords: Cc:
Revision id:

Description

The following files are affected

  • lemon/nagamochi_ibaraki.h

Attachments (1)

5087694945e4.patch (27.8 KB) - added by Balazs Dezso 13 years ago.
Port of Nagamochi-Ibaraki

Download all attachments as: .zip

Change History (16)

comment:1 Changed 16 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:2 Changed 15 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

comment:3 Changed 13 years ago by thoneyvazul

nagamochi_ibaraki.h also contains a nice implementation of the maximum cardinality search algorithm, which might be applied for solving different problems besides the min cut problem. So it might be a good idea separating it from the NI alg and porting it in a different header file say maximum_cardinality_search.h. What do you think?

comment:4 Changed 13 years ago by thoneyvazul

I opened a new ticket for the question (#397)

comment:5 in reply to:  3 Changed 13 years ago by Balazs Dezso

Replying to thoneyvazul:

nagamochi_ibaraki.h also contains a nice implementation of the maximum cardinality search algorithm, which might be applied for solving different problems besides the min cut problem. So it might be a good idea separating it from the NI alg and porting it in a different header file say maximum_cardinality_search.h. What do you think?

It's a good idea, because in the latest NI version the MaxCardinalitySearch? class was not used (the algorithm was reimplemented in the NI class, because of efficiency reasons). I was already working on the port of NI (or rather on a new implementation, becuase I wanted to modify the main data structures and the contraction method), and my new implementation doesn't either use the the MaxCardinalitySearch? class, so it is better to move this algorithm to separate file.

Changed 13 years ago by Balazs Dezso

Attachment: 5087694945e4.patch added

Port of Nagamochi-Ibaraki

comment:6 Changed 13 years ago by Balazs Dezso

I have uploaded the patch [5087694945e4], which contains a new implementation of the Nagamochi-Ibaraki algorithm. It is faster than the old SVN implementation, and I also made some experiments with other implementations (union-find and std::map based implementations).

comment:7 Changed 13 years ago by Alpar Juttner

Could you also adjust the CMAKE config?

Note that we are about to make the CMAKE build environment the default one.

comment:8 in reply to:  7 ; Changed 13 years ago by Balazs Dezso

Replying to alpar:

Could you also adjust the CMAKE config?

Note that we are about to make the CMAKE build environment the default one.

Which CMake config file has to be modified? I modified the config in the test directory, but as I know, I don't have to modify other config files, because the header file is automatically included into the lib.

comment:9 in reply to:  8 Changed 13 years ago by Alpar Juttner

Replying to deba:

Which CMake config file has to be modified? I modified the config in the test directory,

I was wrong, you indeed modified the CMAKE config correctly. Sorry for that.

comment:10 Changed 13 years ago by Alpar Juttner

Milestone: LEMON 1.3 release
Type: taskenhancement

[5087694945e4] has been merged to the main branch.

A general question - wouldn't it be nice to have some more advanced query functionality? E.g.

  • query whether a single node/edge is in the cut
  • list the nodes/edges in a cut.

This applies to HaoOrlin, too.

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

Replying to alpar:

A general question - wouldn't it be nice to have some more advanced query functionality? E.g.

  • query whether a single node/edge is in the cut
  • list the nodes/edges in a cut.

This applies to HaoOrlin, too.

Yes, it would be nice. See #238 for a similar task and see my comment there. Maybe, the name of this ticket should be generalized to cover all max. flow and min. cut algorithms.

comment:12 in reply to:  11 Changed 13 years ago by Peter Kovacs

Replying to kpeter:

... the name of this ticket

I mean the name of 'that' ticket (#238) could be changed to a more general one.

comment:13 Changed 12 years ago by Peter Kovacs

May we close this ticket?

comment:14 Changed 12 years ago by Peter Kovacs

Type: enhancementtask

comment:15 Changed 12 years ago by Alpar Juttner

Resolution: done
Status: newclosed
Type: taskenhancement
Note: See TracTickets for help on using tickets.