ceph/src/boost/libs/graph/doc/is_bipartite.html

   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"
  16 ALT="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>
  23 template &lt;typename Graph, typename IndexMap, typename PartitionMap&gt;
  24 bool is_bipartite (const Graph&amp; graph, const IndexMap index_map, PartitionMap partition_map)
  25
  26 template &lt;typename Graph, typename IndexMap&gt;
  27 bool is_bipartite (const Graph&amp; graph, const IndexMap index_map)
  28
  29 <i>// Version which uses the internal index map</i>
  30 template &lt;typename Graph&gt;
  31 bool is_bipartite (const Graph&amp; graph);
  32 </pre>
  33
  34 <p>
  35 The <tt>is_bipartite()</tt> functions tests a given graph for
  36 bipartiteness using a DFS-based coloring approach.
  37 </p>
  38
  39 <p>
  40 An undirected graph is bipartite if one can partition its set of vertices
  41 into two sets "left" and "right", such that each edge goes from either side
  42 to the other. Obviously, a two-coloring of the graph is exactly the same as
  43 a two-partition. <tt>is_bipartite()</tt> tests whether such a two-coloring
  44 is possible and can return it in a given property map.
  45 </p>
  46
  47 <p>
  48 The bipartition is recorded in the color map <tt>partition_map</tt>,
  49 which 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.
  51 The 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>
  63 IN: <tt>const Graph&amp; graph</tt>
  64 </p>
  65 <blockquote><p>
  66 An undirected graph. The graph type must be a model of <a
  67 href="VertexListGraph.html">Vertex List Graph</a> and <a
  68 href="IncidenceGraph.html">Incidence Graph</a>.<br/>
  69 </p></blockquote>
  70
  71 <p>
  72 IN: <tt>const IndexMap index_map</tt>
  73 </p>
  74 <blockquote><p>
  75 This maps each vertex to an integer in the range <tt>[0,
  76 num_vertices(graph))</tt>. The type <tt>VertexIndexMap</tt>
  77 must be a model of <a
  78 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
  79 Map</a>. The value type of the map must be an integer type. The
  80 vertex descriptor type of the graph needs to be usable as the key
  81 type of the map.<br/>
  82 </p></blockquote>
  83
  84
  85 <p>
  86 OUT: <tt>PartitionMap partition_map</tt>
  87 </p>
  88 <blockquote><p>
  89 The algorithm tests whether the graph is bipartite and assigns each
  90 vertex either a white or a black color, according to the partition.
  91 The <tt>PartitionMap</tt> type must be a model of
  92 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
  93 Map</a> and
  94 <a href="../../property_map/doc/WritablePropertyMap.html">Writable Property
  95 Map</a> The value type must model <a href="./ColorValue.html">ColorValue</a>.
  96 </p></blockquote>
  97
  98
  99 <h3>Complexity</h3>
 100
 101 <p>
 102 The 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>
 114 The file <a href="../example/bipartite_example.cpp"><tt>examples/bipartite.cpp</tt></a>
 115 contains an example of testing an undirected graph for bipartiteness.
 116 <br/>
 117 </p>
 118
 119 <hr/>
 120
 121 <p>
 122 Copyright &copy; 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>