...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
hawick_circuits
template <typename Graph, typename Visitor, typename VertexIndexMap>
void hawick_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph));
template <typename Graph, typename Visitor, typename VertexIndexMap>
void hawick_unique_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph));
Enumerate all the elementary circuits in a directed multigraph. Specifically,
self-loops and redundant circuits caused by parallel edges are enumerated too.
hawick_unique_circuits
may be used if redundant circuits caused by parallel
edges are not desired.
The algorithm is described in detail in https://www.researchgate.net/publication/221440635_Enumerating_Circuits_and_Loops_in_Graphs_with_Self-Arcs_and_Multiple-Arcs.
#include <boost/graph/hawick_circuits.hpp>
IN: Graph const& graph
The graph on which the algorithm is to be performed. It must be a model of the
VertexListGraph
andAdjacencyGraph
concepts.
IN: Visitor visitor
The visitor that will be notified on each circuit found by the algorithm. The
visitor.cycle(circuit, graph)
expression must be valid, withcircuit
being aconst
-reference to a random access sequence ofvertex_descriptor
s.For example, if a circuit
u -> v -> w -> u
exists in the graph, the visitor will be called with a sequence consisting of(u, v, w)
.
IN: VertexIndexMap const& vim = get(vertex_index, graph)
A model of the
ReadablePropertyMap
concept mapping eachvertex_descriptor
to an integer in the range[0, num_vertices(graph))
. It defaults to using the vertex index map provided by thegraph
.