Port maximum cardinality search algorithm

[thoneyvazul]

The affected files in

-lemon/nagamochi_ibaraki.h

[thoneyvazul]

The 42a752f840ef.patch contains a port for the maximum cardinality search algorithm. Differences to the svn version: The algorithm implementation is separated in max_cardinality_search.h Changed the default capacitymap template parameter from arcMap to ConstMap? because that's when the used heap is specialized from binheap to bucketheap. When the default capmap type is used, user doesn't have to create the constmap manually and pass to the constructor, the algorithm allocates one automatically. Added some query functions to the used maps. I did a little renaming from queueSize() and emptyQueue to heapSize() and emptyHeap() Made a test for the algorithm.

[Peter Kovacs]

Replying to thoneyvazul:

I did a little renaming from queueSize() and emptyQueue to heapSize() and emptyHeap()

I'm not sure whether it's a good idea. In Bfs, Dfs, and Dijkstra, we use 'queue'. In Bfs, it is actually a queue, in Dijkstra, it is a priority queue (heap), but in Dfs, it is a stack. However, we call it a 'queue', to define (almost) the same interface for these classes. I think this word is used in an abstract meaning here, not restricted to the standard queue data structure.

Therefore, I suggest to keep the original names in this class.

[Alpar Juttner]

Replying to kpeter:

Replying to thoneyvazul: Therefore, I suggest to keep the original names in this class.

I agree.

[Alpar Juttner]

Some comments on the doc.

• The MaxCardinalitySearch class is under the "Graph Search" module (that's right), but the header file "max_cardinality_search.h" appears under "Auxiliary Algorithms"
• The private members should not appear in the reference guide. It is good to have them documented, but use '' instead of '/'. (An alternative would be to use the \internal feature of Doxygen, but last time I tried it (years ago) it didn't work as I expected.)
• The brief doc of the Set* classes are missing from the Doxygen output, with the exception of SetStandardHeap. I can't understand why.

[thoneyvazul]

Replying to kpeter: Thanks for the explanation. I'm convinced now and will change it back.

[thoneyvazul]

Replying to alpar:

Some comments on the doc.

• The MaxCardinalitySearch class is under the "Graph Search" module (that's right), but the header file "max_cardinality_search.h" appears under "Auxiliary Algorithms"

I wanted to change the module, because I wasn't sure it is a search algorithm. Other algorithms use it for searching for things like order of nodes, mincut or special triangles, but itself only calculates weights. That's why a chose the aux algorithms, but I also feel that it is not the best place for it. It is also reasonable leave it among the search algorithms.

• The private members should not appear in the reference guide.
• The brief doc of the Set* classes are missing from the Doxygen output.

I see. I'll check them.

[Peter Kovacs]

Replying to alpar:

• The brief doc of the Set* classes are missing from the Doxygen output, with the exception of SetStandardHeap. I can't understand why.

I think it is an annoying bug in Doxygen. I noticed several times before that if the brief and the full doc are exactly the same, then the brief doc won't be shown. I don't know why, but it seems to be a consistent behavior. There are many such examples in the current code base, see e.g. the init() functions of Bfs, Dfs, Dijkstra or the Set* classes of Suurballe.

I don't know what to do with this problem. Should we write a bug report for Doxygen developers and wait for a fix? Or should we use the 'repeat brief doc' mode of Doxygen (it is the default)? I think it would solve the problem, but it would require a lot of work to rewrite the existing doc according to this option.

[thoneyvazul]

I uploaded a new patch with the changes mentioned above. 70bee017b584.patch

[Alpar Juttner]

Replying to kpeter:

I think it is an annoying bug in Doxygen. I noticed several times before that if the brief and the full doc are exactly the same, then the brief doc won't be shown. I don't know why, but it seems to be a consistent behavior. There are many such examples in the current code base, see e.g. the init() functions of Bfs, Dfs, Dijkstra or the Set* classes of Suurballe.

It was certainly not the case in the "good old time", when we started using Doxygen.

I don't know what to do with this problem.

I think using not exactly the same brief and long description is a satisfactory workaround. We can always change a word.

Should we write a bug report for Doxygen developers and wait for a fix?

Yes we should. Why not?

Or should we use the 'repeat brief doc' mode of Doxygen (it is the default)?

I played with that option years ago, but somehow didn't like the result.

[Alpar Juttner]

[70bee017b584] has gone to the main branch.

[Peter Kovacs]

Replying to alpar:

[70bee017b584] has gone to the main branch.

May we close this ticket?