1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 2<html> 3<!-- 4 Authors: Matthias Walter 5 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE_1_0.txt or copy at 8 http://www.boost.org/LICENSE_1_0.txt) 9 --> 10<head> 11<title>Boost Graph Library: find_odd_cycle</title> 12</head> 13<body> 14 15<IMG SRC="../../../boost.png" 16ALT="C++ Boost" width="277" height="86"> 17<h1> 18<tt>find_odd_cycle</tt> 19</h1> 20 21<pre> 22<i>// Version with a colormap to retrieve the bipartition</i> 23template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator> 24OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map, OutputIterator result) 25 26template <typename Graph, typename IndexMap, typename OutputIterator> 27OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result) 28 29<i>// Version which uses the internal index map</i> 30template <typename Graph, typename OutputIterator> 31OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result) 32</pre> 33 34<p> 35The <tt>find_odd_cycle</tt> function tests a given graph for bipartiteness 36using a DFS-based coloring approach. 37</p> 38 39<p> 40An undirected graph is bipartite if one can partition its set of vertices 41into two sets "left" and "right", such that each edge goes from either side 42to the other. Obviously, a two-coloring of the graph is exactly the same as 43a two-partition. <tt>is_bipartite()</tt> tests whether such a two-coloring 44is possible and can return it in a given property map. 45</p> 46 47<p> 48Another equivalent characterization is the non-existance of odd-length cycles, 49meaning that a graph is bipartite if and only if it does not contain a 50cycle with an odd number of vertices as a subgraph. 51<tt>find_odd_cycle()</tt> does nearly the same as 52<a href="./is_bipartite.html"><tt>is_bipartite()</tt></a>, 53but additionally constructs an odd-length cycle if the graph is found to be 54not bipartite. 55</p> 56 57<p> 58The bipartition is recorded in the color map <tt>partition_map</tt>, 59which will contain a two-coloring of the graph, i.e. an assignment of 60<i>black</i> and <i>white</i> to the vertices such that no edge is monochromatic. 61The odd-length cycle is written into the Output Iterator <tt>result</tt> if 62one exists. The final final iterator is returned by the function. 63</p> 64 65<h3>Where Defined</h3> 66 67<p> 68<a href="../../../boost/graph/bipartite.hpp"><tt>boost/graph/bipartite.hpp</tt></a> 69</p> 70 71<h3>Parameters</h3> 72 73<p> 74IN: <tt>const Graph& graph</tt> 75</p> 76<blockquote><p> 77An undirected graph. The graph type must be a model of <a 78href="VertexListGraph.html">Vertex List Graph</a> and <a 79href="IncidenceGraph.html">Incidence Graph</a>.<br/> 80</p></blockquote> 81 82<p> 83IN: <tt>const IndexMap index_map</tt> 84</p> 85<blockquote><p> 86This maps each vertex to an integer in the range <tt>[0, 87num_vertices(graph))</tt>. The type <tt>VertexIndexMap</tt> 88must be a model of <a 89href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 90Map</a>. The value type of the map must be an integer type. The 91vertex descriptor type of the graph needs to be usable as the key 92type of the map.<br/> 93</p></blockquote> 94 95 96<p> 97OUT: <tt>PartitionMap partition_map</tt> 98</p> 99<blockquote><p> 100The algorithm tests whether the graph is bipartite and assigns each 101vertex either a white or a black color, according to the partition. 102The <tt>PartitionMap</tt> type must be a model of 103<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 104Map</a> and 105<a href="../../property_map/doc/WritablePropertyMap.html">Writable Property 106Map</a>. The value type must model <a href="./ColorValue.html">ColorValue</a>. 107</p></blockquote> 108 109<p> 110OUT: <tt>OutputIterator result</tt> 111</p> 112<blockquote><p> 113The <tt>find_odd_cycle</tt> function finds an odd-length cycle if the graph is 114not bipartite. The sequence of vertices producing such a cycle is written 115into this iterator. The <tt>OutputIterator</tt> type must be a model of 116<a class="external" href="http://www.boost.org/sgi/stl/OutputIterator.html"> 117OutputIterator</a>. The graph's vertex descriptor type must be in the set 118of value types of the iterator. The final value is returned by the 119function. If the graph is bipartite (i.e. no odd-length cycle exists), nothing 120is written, thus the given iterator matches the return value. 121</p></blockquote> 122 123 124<h3>Complexity</h3> 125 126<p> 127The time complexity for the algorithm is <i>O(V + E)</i>. 128</p> 129 130<h3>See Also</h3> 131 132<p> 133<a href="./is_bipartite.html"><tt>is_bipartite()</tt></a> 134</p> 135 136<h3>Example</h3> 137 138<p> 139The file <a href="../example/bipartite_example.cpp"><tt>example/bipartite_example.cpp</tt></a> 140contains an example of testing an undirected graph for bipartiteness. 141<br/> 142</p> 143 144<hr/> 145 146<p> 147Copyright © 2010 Matthias Walter 148(<a class="external" href="mailto:xammy@xammy.homelinux.net">xammy@xammy.homelinux.net</a>) 149</p> 150 151</body> 152</html> 153
