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: is_bipartite</title> 12</head> 13<body> 14 15<IMG SRC="../../../boost.png" 16ALT="C++ Boost" width="277" height="86"> 17<h1> 18<tt>is_bipartite</tt> 19</h1> 20 21<pre> 22<i>// Version with a colormap to retrieve the bipartition</i> 23template <typename Graph, typename IndexMap, typename PartitionMap> 24bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map) 25 26template <typename Graph, typename IndexMap> 27bool is_bipartite (const Graph& graph, const IndexMap index_map) 28 29<i>// Version which uses the internal index map</i> 30template <typename Graph> 31bool is_bipartite (const Graph& graph); 32</pre> 33 34<p> 35The <tt>is_bipartite()</tt> functions tests a given graph for 36bipartiteness using 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> 48The bipartition is recorded in the color map <tt>partition_map</tt>, 49which will contain a two-coloring of the graph, i.e. an assignment of 50<i>black</i> and <i>white</i> to the vertices such that no edge is monochromatic. 51The predicate whether the graph is bipartite is the return value of the function. 52</p> 53 54<h3>Where Defined</h3> 55 56<p> 57<a href="../../../boost/graph/bipartite.hpp"><tt>boost/graph/bipartite.hpp</tt></a> 58</p> 59 60<h3>Parameters</h3> 61 62<p> 63IN: <tt>const Graph& graph</tt> 64</p> 65<blockquote><p> 66An undirected graph. The graph type must be a model of <a 67href="VertexListGraph.html">Vertex List Graph</a> and <a 68href="IncidenceGraph.html">Incidence Graph</a>.<br/> 69</p></blockquote> 70 71<p> 72IN: <tt>const IndexMap index_map</tt> 73</p> 74<blockquote><p> 75This maps each vertex to an integer in the range <tt>[0, 76num_vertices(graph))</tt>. The type <tt>VertexIndexMap</tt> 77must be a model of <a 78href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 79Map</a>. The value type of the map must be an integer type. The 80vertex descriptor type of the graph needs to be usable as the key 81type of the map.<br/> 82</p></blockquote> 83 84 85<p> 86OUT: <tt>PartitionMap partition_map</tt> 87</p> 88<blockquote><p> 89The algorithm tests whether the graph is bipartite and assigns each 90vertex either a white or a black color, according to the partition. 91The <tt>PartitionMap</tt> type must be a model of 92<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 93Map</a> and 94<a href="../../property_map/doc/WritablePropertyMap.html">Writable Property 95Map</a> The value type must model <a href="./ColorValue.html">ColorValue</a>. 96</p></blockquote> 97 98 99<h3>Complexity</h3> 100 101<p> 102The time complexity for the algorithm is <i>O(V + E)</i>. 103</p> 104 105<h3>See Also</h3> 106 107<p> 108<a href="./find_odd_cycle.html"><tt>find_odd_cycle()</tt></a> 109</p> 110 111<h3>Example</h3> 112 113<p> 114The file <a href="../example/bipartite_example.cpp"><tt>examples/bipartite.cpp</tt></a> 115contains an example of testing an undirected graph for bipartiteness. 116<br/> 117</p> 118 119<hr/> 120 121<p> 122Copyright © 2010 Matthias Walter 123(<a class="external" href="mailto:xammy@xammy.homelinux.net">xammy@xammy.homelinux.net</a>) 124</p> 125 126</body> 127</html> 128
