128 lines
3.6 KiB
HTML
128 lines
3.6 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: 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>
|