Subject: [boost] [Graph] Efficiently finding cycles in a (multi)graph
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2013-04-10 20:11:50
I have implemented the `hawick_circuits` algorithm described in  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 . It is licensed under the Boost license
and was tested using the test suite at .
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.
P.S.: More information on the test suite can be found at .
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk