Port Nagamochi-Ibaraki algorithm

[Alpar Juttner]

The following files are affected

• lemon/nagamochi_ibaraki.h

[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?

[thoneyvazul]

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

[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.

[Balazs Dezso]

Port of Nagamochi-Ibaraki

[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).

[Alpar Juttner]

Could you also adjust the CMAKE config?

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

[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.

[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.

[Alpar Juttner]

[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.

[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.

[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.

[Peter Kovacs]

May we close this ticket?