Hawick Circuits

Enumerates all elementary circuits in a directed multigraph, including self-loops and circuits caused by parallel edges.

Complexity: Exponential in the worst case; use max_length to limit search depth
Defined in: <boost/graph/hawick_circuits.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/hawick_circuits.hpp>
#include <iostream>
#include <vector>

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS>;
using Vertex = graph_traits<Graph>::vertex_descriptor;

struct circuit_printer {
    template <typename Vertices, typename G>
    void cycle(const Vertices& circuit, const G&) {
        for (auto v : circuit) { std::cout << v << " "; }
        std::cout << "\n";
    }
};

int main() {
    Graph g(4);
    add_edge(0, 1, g); add_edge(1, 2, g);
    add_edge(2, 0, g); add_edge(2, 3, g); add_edge(3, 0, g);

    std::cout << "Circuits:\n";
    circuit_printer visitor;
    hawick_circuits(g, visitor);
}
Circuits:
0 1 2
0 1 2 3

(1) hawick_circuits

template <typename Graph, typename Visitor,
          typename VertexIndexMap>
void hawick_circuits(
    Graph const& graph,
    Visitor visitor,
    VertexIndexMap const& vim = get(vertex_index, graph),
    unsigned int max_length = 0);
Direction Parameter Description

IN

Graph const& graph

The graph on which the algorithm is to be performed. It must be a model of the VertexListGraph and AdjacencyGraph 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, with circuit being a const-reference to a random access sequence of vertex_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

A model of the ReadablePropertyMap concept mapping each vertex_descriptor to an integer in the range [0, num_vertices(graph)).
Default: get(vertex_index, graph)

IN

unsigned int max_length

The maximum circuit length to consider. Beyond this it truncates the depth-first search, reducing the computation time by ignoring longer circuits.
Default: 0 (no maximum)

(2) hawick_unique_circuits

template <typename Graph, typename Visitor,
          typename VertexIndexMap>
void hawick_unique_circuits(
    Graph const& graph,
    Visitor visitor,
    VertexIndexMap const& vim = get(vertex_index, graph),
    unsigned int max_length = 0);
Direction Parameter Description

IN

Graph const& graph

The graph on which the algorithm is to be performed. It must be a model of the VertexListGraph and AdjacencyGraph 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, with circuit being a const-reference to a random access sequence of vertex_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

A model of the ReadablePropertyMap concept mapping each vertex_descriptor to an integer in the range [0, num_vertices(graph)).
Default: get(vertex_index, graph)

IN

unsigned int max_length

The maximum circuit length to consider. Beyond this it truncates the depth-first search, reducing the computation time by ignoring longer circuits.
Default: 0 (no maximum)

Description

Enumerate all the elementary circuits (of length ≤ max_length, if nonzero) 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 Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.

Notes

  • hawick_circuits enumerates all elementary circuits including redundant ones caused by parallel edges. Use hawick_unique_circuits to suppress those duplicates.

  • The visitor is passed by value. If your visitor contains state, consider holding it by pointer or reference so that changes made during the algorithm are visible to the caller. If visitor is a std::reference_wrapper, it will be unwrapped before the .cycle method is called on it, which allows passing a visitor that shouldn’t be copied.