mirror of
https://github.com/boostorg/graph.git
synced 2025-05-09 23:14:00 +00:00
73 lines
3.3 KiB
HTML
73 lines
3.3 KiB
HTML
<!--
|
|
Copyright (c) 2013-2015 Louis Dionne
|
|
|
|
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)
|
|
-->
|
|
|
|
<p><body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000"></p>
|
|
|
|
<p><img src="../../../boost.png" alt="C++ Boost" /></p>
|
|
|
|
<h1 id="hawick_circuits"><code>hawick_circuits</code></h1>
|
|
|
|
<pre><code>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);
|
|
|
|
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);
|
|
</code></pre>
|
|
|
|
<p>Enumerate all the elementary circuits (of length ≤ <code>max_length</code>, if nonzero) in a directed multigraph. Specifically,
|
|
self-loops and redundant circuits caused by parallel edges are enumerated too.
|
|
<code>hawick_unique_circuits</code> may be used if redundant circuits caused by parallel
|
|
edges are not desired.</p>
|
|
|
|
<p>The algorithm is described in detail in
|
|
<a href="https://www.researchgate.net/publication/221440635_Enumerating_Circuits_and_Loops_in_Graphs_with_Self-Arcs_and_Multiple-Arcs">https://www.researchgate.net/publication/221440635_Enumerating_Circuits_and_Loops_in_Graphs_with_Self-Arcs_and_Multiple-Arcs</a>.</p>
|
|
|
|
<h3 id="where-defined">Where defined</h3>
|
|
|
|
<p><a href="../../../boost/graph/hawick_circuits.hpp"><code>#include <boost/graph/hawick_circuits.hpp></code></a></p>
|
|
|
|
<h3 id="parameters">Parameters</h3>
|
|
|
|
<p><strong>IN:</strong> <code>Graph const& graph</code></p>
|
|
|
|
<blockquote>
|
|
<p>The graph on which the algorithm is to be performed. It must be a model of
|
|
the <code>VertexListGraph</code> and <code>AdjacencyGraph</code> concepts.</p>
|
|
</blockquote>
|
|
|
|
<p><strong>IN:</strong> <code>Visitor visitor</code></p>
|
|
|
|
<blockquote>
|
|
<p>The visitor that will be notified on each circuit found by the algorithm.
|
|
The <code>visitor.cycle(circuit, graph)</code> expression must be valid, with <code>circuit</code>
|
|
being a <code>const</code>-reference to a random access sequence of <code>vertex_descriptor</code>s.</p>
|
|
|
|
<p>For example, if a circuit <code>u -> v -> w -> u</code> exists in the graph, the
|
|
visitor will be called with a sequence consisting of <code>(u, v, w)</code>.</p>
|
|
</blockquote>
|
|
|
|
<p><strong>IN:</strong> <code>VertexIndexMap const& vim = get(vertex_index, graph)</code></p>
|
|
|
|
<blockquote>
|
|
<p>A model of the <code>ReadablePropertyMap</code> concept mapping each <code>vertex_descriptor</code>
|
|
to an integer in the range <code>[0, num_vertices(graph))</code>. It defaults to using
|
|
the vertex index map provided by the <code>graph</code>.</p>
|
|
</blockquote>
|
|
|
|
<p><strong>IN:</strong> <code>unsigned int max_length = 0</code></p>
|
|
|
|
<blockquote>
|
|
<p>The maximum circuit length to consider. Beyond this it truncates the depth-first search, reducing the computation time by ignoring longer circuits. The default value of <code>max_length = 0</code> implies no maximum.</p>
|
|
</blockquote>
|
|
|
|
<hr />
|
|
|
|
<div class="footer">
|
|
© 2013-2015 Louis Dionne
|
|
</div>
|