[boost] [Graph] Efficiently finding cycles in a (multi)graph

Subject: [boost] [Graph] Efficiently finding cycles in a (multi)graph
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2013-04-10 20:11:50

Dear Boost,

I have implemented the `hawick_circuits` 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].

I am posting this message for two reasons:
    1. To know whether there is interest for such an algorithm in Boost.Graph.

    2. To spread the word that this implementation exists for C++, to save
       people the hassle of reinventing the wheel before Boost.Graph
       officially provides it.

I will create a Trac ticket if there is interest, but note that I won't submit
a patch immediately because I am in deep juice with school right now.

Regards,

Louis Dionne

P.S.: More information on the test suite can be found at [4].

[1] http://bit.ly/12LMwIr
[2] http://bit.ly/10MSAhW
[3] http://bit.ly/YdLHVn
[4] http://bit.ly/16SvlW6