[Boost-bugs] [Boost C++ Libraries] #8433: Algorithm for finding all the elementary circuits in a directed (multi)graph

Subject: [Boost-bugs] [Boost C++ Libraries] #8433: Algorithm for finding all the elementary circuits in a directed (multi)graph
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-04-12 14:03:17

#8433: Algorithm for finding all the elementary circuits in a directed
(multi)graph
---------------------------------------------------+------------------------
 Reporter:  Louis Dionne                           |       Owner:  jewillco      
     Type:  Feature Requests                       |      Status:  new           
Milestone:  To Be Determined                       |   Component:  graph         
  Version:  Boost 1.54.0                           |    Severity:  Not Applicable
 Keywords:  graph multigraph circuit cycle hawick  |  
---------------------------------------------------+------------------------
 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/

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/8433>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.