Tiernan All Cycles

Enumerates all elementary cycles in a directed graph. An elementary cycle visits each vertex at most once.

Complexity: exponential in the number of cycles
Defined in: <boost/graph/tiernan_all_cycles.hpp>

Example

// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// Example: Finding all elementary cycles with Tiernan's algorithm

#include <boost/graph/directed_graph.hpp>
#include <boost/graph/tiernan_all_cycles.hpp>
#include <iostream>
#include <vector>

// Directed graph with no bundled properties
using Graph = boost::directed_graph<>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

// Custom visitor that prints each cycle found.
// The cycle is passed as a const vector of vertex descriptors.
struct PrintCyclesVisitor
{
    template <typename Path, typename G>
    void cycle(const Path& p, const G& g)
    {
        std::cout << "Cycle: ";
        for (std::size_t i = 0; i < p.size(); ++i)
        {
            if (i > 0)
            {
                std::cout << " -> ";
            }
            std::cout << boost::get(boost::vertex_index, g, p[i]);
        }
        std::cout << " -> " << boost::get(boost::vertex_index, g, p.front())
                  << std::endl;
    }
};

int main()
{
    // Build a directed graph with 4 vertices and two cycles:
    //
    //   0 --> 1 --> 2
    //   ^     ^     |
    //   |     |     |
    //   +-----+-----+
    //         |
    //         3
    //
    // Edges: 0->1, 1->2, 2->0, 1->3, 3->1
    // Cycle 1: 0 -> 1 -> 2 -> 0
    // Cycle 2: 1 -> 3 -> 1

    Graph g;

    Vertex v0 = g.add_vertex();
    Vertex v1 = g.add_vertex();
    Vertex v2 = g.add_vertex();
    Vertex v3 = g.add_vertex();

    g.add_edge(v0, v1);
    g.add_edge(v1, v2);
    g.add_edge(v2, v0);
    g.add_edge(v1, v3);
    g.add_edge(v3, v1);

    std::cout << "Finding all elementary cycles:" << std::endl;
    boost::tiernan_all_cycles(g, PrintCyclesVisitor{});

    return 0;
}

Finding all elementary cycles:
Cycle: 0 -> 1 -> 2 -> 0
Cycle: 1 -> 3 -> 1

(1) tiernan_all_cycles (explicit min and max)

template <typename Graph, typename Visitor>
void tiernan_all_cycles(const Graph& g, Visitor vis,
                        std::size_t minlen,
                        std::size_t maxlen);

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	Must model Vertex List Graph with a `vertex_index` property.
IN	`Visitor vis`	Called with `vis.cycle(path, g)` for each cycle found. `path` is a `const std::vector<vertex_descriptor>&`.
IN	`std::size_t minlen`	Minimum cycle length (inclusive). Cycles shorter than this are skipped.
IN	`std::size_t maxlen`	Maximum cycle length (inclusive).

const Graph& g

Must model Vertex List Graph with a vertex_index property.

Visitor vis

Called with vis.cycle(path, g) for each cycle found. path is a const std::vector<vertex_descriptor>&.

std::size_t minlen

Minimum cycle length (inclusive). Cycles shorter than this are skipped.

std::size_t maxlen

Maximum cycle length (inclusive).

(2) tiernan_all_cycles (explicit max, default min)

template <typename Graph, typename Visitor>
void tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen);

Same as overload (1) with minlen defaulted to the smallest cycle length admissible for the graph’s directed category (loops and length-1 cycles excluded as appropriate).

(3) tiernan_all_cycles (default min and max)

template <typename Graph, typename Visitor>
void tiernan_all_cycles(const Graph& g, Visitor vis);

Equivalent to overload (2) with maxlen set to std::numeric_limits<std::size_t>::max() (no upper bound).

(4) tiernan_girth_and_circumference

template <typename Graph>
std::pair<std::size_t, std::size_t>
tiernan_girth_and_circumference(const Graph& g);

Returns (girth, circumference) — the smallest and largest cycle lengths in the graph. If the graph is acyclic, both values equal std::numeric_limits<std::size_t>::max().

(5) tiernan_girth

template <typename Graph>
std::size_t tiernan_girth(const Graph& g);

Returns the girth (shortest cycle length). Thin wrapper over tiernan_girth_and_circumference.

(6) tiernan_circumference

template <typename Graph>
std::size_t tiernan_circumference(const Graph& g);

Returns the circumference (longest cycle length). Thin wrapper over tiernan_girth_and_circumference.

For simply detecting whether a cycle exists (without enumerating), use DFS with a back-edge visitor. That is O(V + E) instead of exponential.

Edit this Page