[Graph] Efficiently finding cycles in a (multi)graph
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
Louis Dionne
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.
[...] A Boost-ready implementation can be found here: https://github.com/ldionne/hawick_circuits Looking for comments/improvements/etc.. Louis Dionne
participants (1)
-
Louis Dionne