[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section Tiernan All Cycles]
[template ex_tiernan_printing_cycles[] [link
    boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.examples.printing_cycles
    Printing Cycles Example]]
[template ex_tiernan_girth_circumference[] [link
    boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.examples.girth_and_circumference
    Girth and Circumference Example]]

[heading Overview]
This function uses the Tiernan algorithm to find all /cycles/ within a given graph,
invoking a visitor when each cycle is found. A cycle is a path (a sequence of
connected vertices) within a graph, and whose tail (the last vertex in the path)
is connected to its head (the first vertex in the path).

Consider the directed graph in Figure 1.

[figure
    images/reference/prism_3_2.png
    *Figure 1.* A directed graph.
]

This graph has 11 distinct cycles. Some of the more obvious are:

* 0, 1, 2
* 3, 4, 5
* 0, 3
* 1, 4
* 2, 5

For more details see the [ex_tiernan_printing_cycles].

The order in which cycles are visited is determined by the algorithm. It iterates
over each vertex in the order of its vertex indices. The algorithm identifies cycles
by first finding long paths and determining if they form cycles. Once the paths
have been examined, the algorithm backtracks along the path searching for alternate
cycles. The result (as shown in the output of the [ex_tiernan_printing_cycles]) is a
listing that visits longer cycles first in the lexicographical order of vertex
indices. Note that the order of visitation does /not/ imply anything about the
relative importance of the cycle within the graph.

The Tiernan algorithm is designed to work on directed graphs, but works for undirected
graphs as well. When running on undirected graphs, however, the algorithm treats each
edge connecting two vertices /(u,v)/ as if it were two distinct edges /(u,v)/ and
/(v,u)/. As result the algorithm will report cycles in both directions. Consider the
following undirected graph in Figure 2.

[figure
    images/reference/triangle.png
    *Figure 2.* An undirected triangle.
]

If the Tiernan algorithm is run on this graph, it will visit the paths 0, 1, 2 and
0, 2, 1.

There are two properties of a graph that are derived from knowing a graphs cycles:
/girth/ and /circumference/. The girth of a graph is defined as the minimum-length
cycle in the graph, and the circumference is defined as the largest-length cycle.
This module provides functions for computing these values using Tiernan's algorithm.
See the [ex_tiernan_girth_circumference] for details.

[section [^tiernan_all_cycles()]]
    #include <boost/graph/tiernan_all_cycles.hpp>

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

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

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

The `tiernan_all_cycles()` function visits all cycles in a graph. There are three
variants of this algorithm. The first will simply find and visit all cycles in the
target graph. The second variant allows the caller to specify an upper bound to the
length of cycles visited, and the third variant allows the user to specify both
upper and lower bounds on the lengths of paths being visited. The minimum cycle
length must be at least two.

Note that the default minimum cycle length differs between directed and undirected
graphs. For directed graphs, the algorithm allows the discovery and visitation
of length-two cycles. For undirected graphs, the default minimum cycle length is
three. This prevents the algorithm from visiting every pair of connected vertices
in an undirected graph as a cycle.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which cliques are being visited.

            *Requirements:* The `Graph` type must be a model of the
            [IncidenceGraph] and [VertexIndexGraph] concepts.
        ]
    ]
    [
        [required, in] [`Visitor vis`]
        [
            The visitor object to the algorithm.

            *Requirements:* This `Visitor` class must model the
            [CliqueVisitor] class.
        ]
    ]
    [
        [optional, in] [`std::size_t max`]
        [
            The maximum-length path that will be visited by the algorithm.

            *Default:* `std::numeric_limits<std::size_t>::max()`.
        ]
    ]
    [
        [optional, in] [`std::size_t min`]
        [
            The minimum-length path that will be visited by the algorithm. The
            default minimum length path is determined by the type of graph.

            *Precondition:* `min >= 2`

            *Default:* If `Graph` is directed, this value defaults to 2. Otherwise
            the default value is 3.
        ]
    ]
]

[heading Complexity]
This function has a (loose) upper bound of ['O(2[sup n])] where /n/ is the
number of vertices a graph. This bound is derived from the powerset of vertices
in /g/ and does not account for the vertex of origin or directionality of edges
connecting vertices in a path. If one considers the paths in a triangle {1, 2, 3}
and {3, 2, 1} to be distinct cycles within a graph, then this bound can potentially
be much greater. From a practical standpoint, it is unlikely that real graphs will
ever approach a number of paths remotely close to this number.

This function requires ['O(n[sup 2])] space where /n/ is the number of vertices
in a graph.
[endsect]

[section [^tiernan_girth()]]
    #include <boost/graph/tiernan_all_cycles.hpp>

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

Comptutes the girth (the minimum length cycle) of the graph `g` by visiting all
cycles using Tiernan's algorithm. If the graph is acyclic, it has no cycles and
an infinite girth. If computing both girth and circumference, use the
[tiernan_girth_and_circumference] function since this computation can be fairly
time consuming.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the girth is computed.

            *Requirements:* The `Graph` type must be a model of the
            [IncidenceGraph] and [VertexIndexGraph] concepts.
        ]
    ]
]

[heading Return]
The `tiernan_girth()` function returns the girth of the given graph.

[heading Complexity]
The `tiernan_girth()` function has the same time complexity as the [tiernan_all_cycles]
function.
[endsect]

[section [^tiernan_circumference()]]
    #include <boost/graph/tiernan_all_cycles.hpp>

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

Comptutes the circumference (the maximum length cycle) of the graph `g` by visiting all
cycles using Tiernan's algorithm. If the graph is acyclic, it has no cycles and an
infinite circumference. If computing both girth and circumference, use the
[tiernan_girth_and_circumference] function since this computation can be fairly
time consuming.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the circumference is being computed.

            *Requirements:* The `Graph` type must be a model of the
            [IncidenceGraph] and [VertexIndexGraph] concepts.
        ]
    ]
]

[heading Return]
The `tiernan_circumference()` function returns the girth of the given graph.

[heading Complexity]
The `tiernan_circumference()` function has the same time complexity as the
[tiernan_all_cycles] function.
[endsect]

[section [^tiernan_girth_and_circumference()]]
    #include <boost/graph/tiernan_all_cycles.hpp>

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

Comptutes the both the girth (minimum length cycle) and circumference (maximum length
cycle) of the graph `g` by visiting all cycles using Tiernan's algorithm. If the
graph is acyclic, it has no cycles and both girth and cicumference are infinite.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the girth and circumference are being computed.

            *Preconditions:* The indices of vertices in the graph must be
            in the range...

            *Requirements:* The `Graph` type must be a model of the
            [IncidenceGraph] and [VertexIndexGraph] concepts.
        ]
    ]
]

[heading Return]
The `tiernan_girth_and_circumference()` function returns the girth of the given graph.

[heading Complexity]
The `tiernan_girth_and_circumference()` function has the same time complexity as the
[tiernan_all_cycles] function.
[endsect]

[section Examples]
[heading Printing Cycles]
This example demonstrates the construction of a cycle visitor and its use with
the `tiernan_all_cycles()` function. This file includes the following files:

* [^examples/tiernan_print_cycles.cpp]
* [^examples/helper.hpp]

[tiernan_print_cycles]

If this program is given the `prism_3_2.graph` file as input, it will print all
the cycles in the graph shown in Figure 1.

[pre
0 1 2 5 3
0 1 2
0 1 4 5 3
0 1 4 5 2
0 3 4 5 2
0 3 4 1 2
0 3
1 2 5 3 4
1 4
2 5
3 4 5
]

[heading Girth and Circumference]
This example demonstrates the use of Tiernan's algorithm to compute the girth
and circumference of a directed graph. This example includes the following files:

* [^examples/tiernan_girth_circumference.cpp]
* [^examples/helper.hpp]

[tiernan_girth_circumference]

If this program is given the `prism_3_2.graph` file as input, it will print the
following output:

[pre
girth: 2
circumference: 5
]

[endsect]

[endsect]