COIN-OR::LEMON - Graph Library

Opened 8 years ago

Closed 7 years ago

#397 closed enhancement (done)

Port maximum cardinality search algorithm

Reported by: thoneyvazul Owned by: alpar
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 8 years ago.
70bee017b584.patch (32.2 KB) - added by thoneyvazul 8 years ago.

Download all attachments as: .zip

Change History (14)

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

comment:2 in reply to: ↑ 1 ; follow-ups: Changed 8 years ago by kpeter

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

Replying to kpeter:

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

I agree.

comment:4 follow-ups: Changed 8 years ago by 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"
  • 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 8 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 8 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 ; follow-up: Changed 8 years ago by kpeter

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

comment:8 Changed 8 years ago by thoneyvazul

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

comment:9 in reply to: ↑ 7 Changed 8 years ago by alpar

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

[70bee017b584] has gone to the main branch.

comment:11 in reply to: ↑ 10 Changed 7 years ago by kpeter

Replying to alpar:

[70bee017b584] has gone to the main branch.

May we close this ticket?

comment:12 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.