projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <!-- |
| 2 | Copyright (c) 2013-2015 Louis Dionne | |
| 3 | ||
| 4 | Distributed under the Boost Software License, Version 1.0. | |
| 5 | (See accompanying file LICENSE_1_0.txt or copy at | |
| 6 | http://www.boost.org/LICENSE_1_0.txt) | |
| 7 | --> | |
| 8 | ||
| 9 | <p><body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000"></p> | |
| 10 | ||
| 11 | <p><img src="../../../boost.png" alt="C++ Boost" /></p> | |
| 12 | ||
| 13 | <h1 id="hawick_circuits"><code>hawick_circuits</code></h1> | |
| 14 | ||
| 15 | <pre><code>template <typename Graph, typename Visitor, typename VertexIndexMap> | |
| 16 | void hawick_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph)); | |
| 17 | ||
| 18 | template <typename Graph, typename Visitor, typename VertexIndexMap> | |
| 19 | void hawick_unique_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph)); | |
| 20 | </code></pre> | |
| 21 | ||
| 22 | <p>Enumerate all the elementary circuits in a directed multigraph. Specifically, | |
| 23 | self-loops and redundant circuits caused by parallel edges are enumerated too. | |
| 24 | <code>hawick_unique_circuits</code> may be used if redundant circuits caused by parallel | |
| 25 | edges are not desired.</p> | |
| 26 | ||
| 27 | <p>The algorithm is described in detail in | |
| 28 | <a href="http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf">http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf</a>.</p> | |
| 29 | ||
| 30 | <h3 id="where-defined">Where defined</h3> | |
| 31 | ||
| 32 | <p><a href="../../../boost/graph/hawick_circuits.hpp"><code>#include <boost/graph/hawick_circuits.hpp></code></a></p> | |
| 33 | ||
| 34 | <h3 id="parameters">Parameters</h3> | |
| 35 | ||
| 36 | <p><strong>IN:</strong> <code>Graph const& graph</code></p> | |
| 37 | ||
| 38 | <blockquote> | |
| 39 | <p>The graph on which the algorithm is to be performed. It must be a model of | |
| 40 | the <code>VertexListGraph</code> and <code>AdjacencyGraph</code> concepts.</p> | |
| 41 | </blockquote> | |
| 42 | ||
| 43 | <p><strong>IN:</strong> <code>Visitor visitor</code></p> | |
| 44 | ||
| 45 | <blockquote> | |
| 46 | <p>The visitor that will be notified on each circuit found by the algorithm. | |
| 47 | The <code>visitor.cycle(circuit, graph)</code> expression must be valid, with <code>circuit</code> | |
| 48 | being a <code>const</code>-reference to a random access sequence of <code>vertex_descriptor</code>s.</p> | |
| 49 | ||
| 50 | <p>For example, if a circuit <code>u -> v -> w -> u</code> exists in the graph, the | |
| 51 | visitor will be called with a sequence consisting of <code>(u, v, w)</code>.</p> | |
| 52 | </blockquote> | |
| 53 | ||
| 54 | <p><strong>IN:</strong> <code>VertexIndexMap const& vim = get(vertex_index, graph)</code></p> | |
| 55 | ||
| 56 | <blockquote> | |
| 57 | <p>A model of the <code>ReadablePropertyMap</code> concept mapping each <code>vertex_descriptor</code> | |
| 58 | to an integer in the range <code>[0, num_vertices(graph))</code>. It defaults to using | |
| 59 | the vertex index map provided by the <code>graph</code>.</p> | |
| 60 | </blockquote> | |
| 61 | ||
| 62 | <hr /> | |
| 63 | ||
| 64 | <div class="footer"> | |
| 65 | © 2013-2015 Louis Dionne | |
| 66 | </div> |