Re: [Boost-bugs] [Boost C++ Libraries] #8433: Algorithm for finding all the elementary circuits in a directed (multi)graph

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #8433: Algorithm for finding all the elementary circuits in a directed (multi)graph
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-08-16 02:30:54

#8433: Algorithm for finding all the elementary circuits in a directed
(multi)graph
-------------------------+-------------------------------------------------
  Reporter:  Louis       |      Owner:  jewillco
  Dionne                 |     Status:  new
      Type:  Feature     |  Component:  graph
  Requests               |   Severity:  Not Applicable
 Milestone:  To Be       |   Keywords:  graph multigraph circuit cycle
  Determined             |  hawick
   Version:  Boost       |
  1.54.0                 |
Resolution:              |
-------------------------+-------------------------------------------------

Comment (by Louis Dionne):

 Replying to [comment:1 jewillco]:

 Sorry, I did not notice your reply and now quite a bit of time has passed.
 Anyway, the algorithm is still a very relevant addition to Boost.Graph.


 > Here are a few comments on the code:
 >
 > * It looks good and is almost ready to put in.
 > * There is no documentation file that I can see.

 The documentation that I should write is almost the same as that of
 `tiernan_all_cycles`. Is there a way to say "the behavior for
 `hawick_circuits` is the same as `tiernan_all_cycles`, except it detects
 self-loops and loops involving parallel edges in multigraphs"?

 Also, what would be the preferred way of providing documentation? I am not
 familiar with QuickBook; if it's possible to stick with something else
 then I'd be happy.


 > * Please use `boost::graph_detail::find` from
 `<boost/pending/container_traits.hpp>` instead of `std::find`; that code
 will automatically use a member find to get better performance on types
 such as `set` and `unordered_set`.  If you know that you are searching a
 non-associative container, you can also use `boost::container_contains`
 from `<boost/detail/algorithm.hpp>`.

 I'm now using `boost::container_contains`. I do find it awful that
 `<boost/detail/algorithm.hpp>` includes so many unneeded headers, though.


 > * What concept is `ClosedMatrix` expected to model?

 IIRC, `ClosedMatrix` is just a two dimensional array of vertices. It is an
 implementation detail and it is not expected to model any specific
 concept.


 > * There is no need to use perfect forwarding on the graph type; passing
 `const` references is fine.  You can also assume vertex descriptors and
 property maps are inexpensive to copy, but forwarding those is acceptable
 if you want to do it.

 I like to use perfect forwarding whenever it makes sense to do it, i.e.
 whenever I don't use an argument but I only forward it to another
 function. While it may be useless in some cases, it is never harmful and I
 feel it captures my intent better.


 > * You refer to citation `[1]` in the code, but do not provide the full
 information about the source there.

 Thanks, fixed.


 > * Boost.Graph has a Dot parser (and output routines) if you want to use
 them in your test harness.

 Thanks, but the test harness is made to work with the test suite at
 [https://github.com/josch/cycle_test]. The input format is not exactly
 Dot.


 I updated the repository at [https://github.com/ldionne/hawick_circuits].
 I guess we have to settle on the documentation and then we'll be good to
 go.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/8433#comment:2>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.