| <!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: is_bipartite</title> |
| </head> |
| <body> |
| |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| <h1> |
| <tt>is_bipartite</tt> |
| </h1> |
| |
| <pre> |
| <i>// Version with a colormap to retrieve the bipartition</i> |
| template <typename Graph, typename IndexMap, typename PartitionMap> |
| bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map) |
| |
| template <typename Graph, typename IndexMap> |
| bool is_bipartite (const Graph& graph, const IndexMap index_map) |
| |
| <i>// Version which uses the internal index map</i> |
| template <typename Graph> |
| bool is_bipartite (const Graph& graph); |
| </pre> |
| |
| <p> |
| The <tt>is_bipartite()</tt> functions 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> |
| 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 predicate whether the graph is bipartite is the return value of 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> |
| |
| |
| <h3>Complexity</h3> |
| |
| <p> |
| The time complexity for the algorithm is <i>O(V + E)</i>. |
| </p> |
| |
| <h3>See Also</h3> |
| |
| <p> |
| <a href="./find_odd_cycle.html"><tt>find_odd_cycle()</tt></a> |
| </p> |
| |
| <h3>Example</h3> |
| |
| <p> |
| The file <a href="../example/bipartite_example.cpp"><tt>examples/bipartite.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> |
