COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 7 years ago

#56 closed enhancement (done)

Port Nagamochi-Ibaraki algorithm

Reported by: alpar Owned by: alpar
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 deba 8 years ago.
Port of Nagamochi-Ibaraki

Download all attachments as: .zip

Change History (16)

comment:1 Changed 10 years ago by alpar

  • Milestone changed from LEMON 1.0 release to Post 1.0

comment:2 Changed 10 years ago by alpar

  • Milestone LEMON 1.1 release deleted

comment:3 follow-up: Changed 8 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 8 years ago by thoneyvazul

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

comment:5 in reply to: ↑ 3 Changed 8 years ago by deba

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 8 years ago by deba

Port of Nagamochi-Ibaraki

comment:6 Changed 8 years ago by deba

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 follow-up: Changed 8 years ago by alpar

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 ; follow-up: Changed 8 years ago by deba

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 8 years ago by alpar

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 follow-up: Changed 8 years ago by alpar

  • Milestone set to LEMON 1.3 release
  • Type changed from task to enhancement

[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 ; follow-up: Changed 8 years ago by kpeter

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 8 years ago by kpeter

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 7 years ago by kpeter

May we close this ticket?

comment:14 Changed 7 years ago by kpeter

  • Type changed from enhancement to task

comment:15 Changed 7 years ago by alpar

  • Resolution set to done
  • Status changed from new to closed
  • Type changed from task to enhancement
Note: See TracTickets for help on using tickets.