Ticket #8433 (closed Feature Requests: fixed)
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:|
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.
- Status changed from new to closed
- Resolution set to fixed