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

[Louis Dionne]

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/

[Jeremiah Willcock]

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.

[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.

[Jeremiah Willcock]

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.

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

3. That's fine; I see that ClosedMatrix isn't part of a public interface so it can be whatever you want.

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

5. 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?

[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.

2. 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.

4. 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.

5. 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.

[Jeremiah Willcock]

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?

[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.

[Jeremiah Willcock]

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

[Jeremiah Willcock]

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.

[Smithe854]

I'm truly enjoying the design and layout of your blog. It's a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a developer to create your theme? Outstanding work! effckkaddggaecee

[ldionne.2@…]

Damn bot. We should be good to close this once ​https://github.com/boostorg/graph/pull/50 is merged.