Modify

Ticket #8433 (closed Feature Requests: fixed)

Opened 12 months ago

Last modified 8 months ago

Algorithm for finding all the elementary circuits in a directed (multi)graph

Reported by: Louis Dionne Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.54.0 Severity: Not Applicable
Keywords: graph multigraph circuit cycle hawick Cc:

Description

I have implemented the algorithm described in (1) for finding all the elementary circuits of a directed (multi)graph. I implemented it in a generic fashion, planning to propose it for inclusion in Boost.

Boost.Graph currently contains the tiernan_all_cycles algorithm for finding all the cycles in a graph. However, it is undocumented and it has a time bound (for which no precise analysis is provided) that makes it unsuitable even for moderately sized graphs. In fact, I implemented hawick_circuits because tiernan_all_cycles did not cut it for my application.

My implementation is available at (2). It is licensed under the Boost license and was tested using the test suite at (3). More information on the test suite can be found at (4).

Comments on improvements would be appreciated.

(1)  http://www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf

(2)  https://github.com/ldionne/hawick_circuits

(3)  https://github.com/josch/cycle_test

(4)  http://blog.mister-muffin.de/2012/07/04/enumerating-elementary-circuits-of-a-directed_graph/

Attachments

Change History

comment:1 follow-up: ↓ 2 Changed 12 months ago by jewillco

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.
  • 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>.
  • What concept is ClosedMatrix expected to model?
  • 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.
  • You refer to citation [1] in the code, but do not provide the full information about the source there.
  • Boost.Graph has a Dot parser (and output routines) if you want to use them in your test harness.

comment:2 in reply to: ↑ 1 Changed 8 months ago by Louis Dionne

Replying to 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.

comment:3 follow-up: ↓ 4 Changed 8 months ago by jewillco

Here are responses to your questions:

  1. Yes, you can have the documentation refer to another algorithm's documentation, but your page should at least have the function signatures and any differences. Most BGL documentation is in fairly straightforward, hand-written HTML; just copy one of the existing pages and modify it for your algorithm.
  1. It looks like container_contains does not do any optimizations, so you should probably use boost::graph_detail::find anyway.
  1. That's fine; I see that ClosedMatrix isn't part of a public interface so it can be whatever you want.
  1. OK, perfect forwarding is fine as long as your code works in C++03.
  1. I'm not seeing exactly where the test graphs (or generators for them) are in the repository you give. How different are they from Graphviz format?

comment:4 in reply to: ↑ 3 Changed 8 months ago by Louis Dionne <ldionne.2@…>

Replying to jewillco:

Here are responses to your questions:

  1. Yes, you can have the documentation refer to another algorithm's documentation, but your page should at least have the function signatures and any differences. Most BGL documentation is in fairly straightforward, hand-written HTML; just copy one of the existing pages and modify it for your algorithm.

I wrote documentation in Markdown and generated HTML from it. It looks exactly as the rest of the documentation.

  1. It looks like container_contains does not do any optimizations, so you should probably use boost::graph_detail::find anyway.

Since I'm only searching in a vector, there won't be any optimization. I'll stick with container_contains, since that expresses my intent better.

  1. OK, perfect forwarding is fine as long as your code works in C++03.

The code works in C++03 and C++11. It was compiled with Clang 3.3 and G++ 4.9.

  1. I'm not seeing exactly where the test graphs (or generators for them) are in the repository you give. How different are they from Graphviz format?

I'm not providing any tests with the algorithm, that's why. The algorithm is tested using an external test suite, and it would be fairly complicated to migrate those tests to Boost. Basically, you should ignore the hawick_circuits.cpp file at the root of the repository, which is only useful for the external test suite.

comment:5 follow-up: ↓ 6 Changed 8 months ago by jewillco

Instead of container_contains, it would probably be better to use std::find directly (which I believe you did before). Are you going to have any kind of testing in the Boost version? It would be nice to at least have testing with a small graph or two that makes sure that the code compiles and can run simple problems. Can you use random graphs like the tiernan_all_cycles.cpp test does?

comment:6 in reply to: ↑ 5 Changed 8 months ago by Louis Dionne <ldionne.2@…>

Replying to jewillco:

Instead of container_contains, it would probably be better to use std::find directly (which I believe you did before).

Fixed.

Are you going to have any kind of testing in the Boost version? It would be nice to at least have testing with a small graph or two that makes sure that the code compiles and can run simple problems. Can you use random graphs like the tiernan_all_cycles.cpp test does?

I adapted tiernan_all_cycles.cpp into a reusable header for cycle algorithms, and used it to generate a small unit test for hawick_circuits. It might also be interesting to use that header from tiernan_all_cycles.cpp to reduce code duplication.

comment:7 Changed 8 months ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

(In [85533]) Added Hawick circuits code from Louis Dionne; fixes #8433

comment:8 Changed 8 months ago by jewillco

I've added your code to the Boost trunk, but I still need a couple of changes (please attach patches to the bug report for those):

  • The documentation files do not include copyright or license information; could you please send a patch with that added?
  • Where should your algorithm be in the table of contents of the documentation? I put it in the "Miscellaneous Algorithms" part for now.

Also, here are some changes I made; please tell me if you disagree:

  • I put the hawick_circuits.cpp file from the root directory of your Github repository into libs/graph/example and added it as a file to build there.
  • I removed two lines (typedefs) from cycle_test.hpp to fix GCC warnings about unused typedefs.
View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.