153 lines
4.9 KiB
HTML
153 lines
4.9 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
|
<html>
|
|
<!--
|
|
Authors: Matthias Walter
|
|
|
|
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)
|
|
-->
|
|
<head>
|
|
<title>Boost Graph Library: find_odd_cycle</title>
|
|
</head>
|
|
<body>
|
|
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
<h1>
|
|
<tt>find_odd_cycle</tt>
|
|
</h1>
|
|
|
|
<pre>
|
|
<i>// Version with a colormap to retrieve the bipartition</i>
|
|
template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator>
|
|
OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map, OutputIterator result)
|
|
|
|
template <typename Graph, typename IndexMap, typename OutputIterator>
|
|
OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result)
|
|
|
|
<i>// Version which uses the internal index map</i>
|
|
template <typename Graph, typename OutputIterator>
|
|
OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result)
|
|
</pre>
|
|
|
|
<p>
|
|
The <tt>find_odd_cycle</tt> function tests a given graph for bipartiteness
|
|
using a DFS-based coloring approach.
|
|
</p>
|
|
|
|
<p>
|
|
An undirected graph is bipartite if one can partition its set of vertices
|
|
into two sets "left" and "right", such that each edge goes from either side
|
|
to the other. Obviously, a two-coloring of the graph is exactly the same as
|
|
a two-partition. <tt>is_bipartite()</tt> tests whether such a two-coloring
|
|
is possible and can return it in a given property map.
|
|
</p>
|
|
|
|
<p>
|
|
Another equivalent characterization is the non-existance of odd-length cycles,
|
|
meaning that a graph is bipartite if and only if it does not contain a
|
|
cycle with an odd number of vertices as a subgraph.
|
|
<tt>find_odd_cycle()</tt> does nearly the same as
|
|
<a href="./is_bipartite.html"><tt>is_bipartite()</tt></a>,
|
|
but additionally constructs an odd-length cycle if the graph is found to be
|
|
not bipartite.
|
|
</p>
|
|
|
|
<p>
|
|
The bipartition is recorded in the color map <tt>partition_map</tt>,
|
|
which will contain a two-coloring of the graph, i.e. an assignment of
|
|
<i>black</i> and <i>white</i> to the vertices such that no edge is monochromatic.
|
|
The odd-length cycle is written into the Output Iterator <tt>result</tt> if
|
|
one exists. The final final iterator is returned by the function.
|
|
</p>
|
|
|
|
<h3>Where Defined</h3>
|
|
|
|
<p>
|
|
<a href="../../../boost/graph/bipartite.hpp"><tt>boost/graph/bipartite.hpp</tt></a>
|
|
</p>
|
|
|
|
<h3>Parameters</h3>
|
|
|
|
<p>
|
|
IN: <tt>const Graph& graph</tt>
|
|
</p>
|
|
<blockquote><p>
|
|
An undirected graph. The graph type must be a model of <a
|
|
href="VertexListGraph.html">Vertex List Graph</a> and <a
|
|
href="IncidenceGraph.html">Incidence Graph</a>.<br/>
|
|
</p></blockquote>
|
|
|
|
<p>
|
|
IN: <tt>const IndexMap index_map</tt>
|
|
</p>
|
|
<blockquote><p>
|
|
This maps each vertex to an integer in the range <tt>[0,
|
|
num_vertices(graph))</tt>. The type <tt>VertexIndexMap</tt>
|
|
must be a model of <a
|
|
href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
|
|
Map</a>. The value type of the map must be an integer type. The
|
|
vertex descriptor type of the graph needs to be usable as the key
|
|
type of the map.<br/>
|
|
</p></blockquote>
|
|
|
|
|
|
<p>
|
|
OUT: <tt>PartitionMap partition_map</tt>
|
|
</p>
|
|
<blockquote><p>
|
|
The algorithm tests whether the graph is bipartite and assigns each
|
|
vertex either a white or a black color, according to the partition.
|
|
The <tt>PartitionMap</tt> type must be a model of
|
|
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
|
|
Map</a> and
|
|
<a href="../../property_map/doc/WritablePropertyMap.html">Writable Property
|
|
Map</a>. The value type must model <a href="./ColorValue.html">ColorValue</a>.
|
|
</p></blockquote>
|
|
|
|
<p>
|
|
OUT: <tt>OutputIterator result</tt>
|
|
</p>
|
|
<blockquote><p>
|
|
The <tt>find_odd_cycle</tt> function finds an odd-length cycle if the graph is
|
|
not bipartite. The sequence of vertices producing such a cycle is written
|
|
into this iterator. The <tt>OutputIterator</tt> type must be a model of
|
|
<a class="external" href="http://www.boost.org/sgi/stl/OutputIterator.html">
|
|
OutputIterator</a>. The graph's vertex descriptor type must be in the set
|
|
of value types of the iterator. The final value is returned by the
|
|
function. If the graph is bipartite (i.e. no odd-length cycle exists), nothing
|
|
is written, thus the given iterator matches the return value.
|
|
</p></blockquote>
|
|
|
|
|
|
<h3>Complexity</h3>
|
|
|
|
<p>
|
|
The time complexity for the algorithm is <i>O(V + E)</i>.
|
|
</p>
|
|
|
|
<h3>See Also</h3>
|
|
|
|
<p>
|
|
<a href="./is_bipartite.html"><tt>is_bipartite()</tt></a>
|
|
</p>
|
|
|
|
<h3>Example</h3>
|
|
|
|
<p>
|
|
The file <a href="../example/bipartite_example.cpp"><tt>example/bipartite_example.cpp</tt></a>
|
|
contains an example of testing an undirected graph for bipartiteness.
|
|
<br/>
|
|
</p>
|
|
|
|
<hr/>
|
|
|
|
<p>
|
|
Copyright © 2010 Matthias Walter
|
|
(<a class="external" href="mailto:xammy@xammy.homelinux.net">xammy@xammy.homelinux.net</a>)
|
|
</p>
|
|
|
|
</body>
|
|
</html>
|