COIN-OR::LEMON - Graph Library

Opened 13 years ago

Closed 12 years ago

#397 closed enhancement (done)

Port maximum cardinality search algorithm

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

Description

The affected files in

-lemon/nagamochi_ibaraki.h

Attachments (2)

42a752f840ef.patch (32.2 KB) - added by thoneyvazul 13 years ago.
70bee017b584.patch (32.2 KB) - added by thoneyvazul 13 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 13 years ago by 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.

Changed 13 years ago by thoneyvazul

Attachment: 42a752f840ef.patch added

comment:2 in reply to:  1 ; Changed 13 years ago by 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.

comment:3 in reply to:  2 Changed 13 years ago by Alpar Juttner

Replying to kpeter:

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

I agree.

comment:4 Changed 13 years ago by 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.

comment:5 in reply to:  2 Changed 13 years ago by thoneyvazul

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

comment:6 in reply to:  4 Changed 13 years ago by 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.

comment:7 in reply to:  4 ; Changed 13 years ago by 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.

Changed 13 years ago by thoneyvazul

Attachment: 70bee017b584.patch added

comment:8 Changed 13 years ago by thoneyvazul

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

comment:9 in reply to:  7 Changed 13 years ago by 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.

comment:10 Changed 13 years ago by Alpar Juttner

[70bee017b584] has gone to the main branch.

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

Replying to alpar:

[70bee017b584] has gone to the main branch.

May we close this ticket?

comment:12 Changed 12 years ago by Alpar Juttner

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