projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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 <typename Graph, typename IndexMap, typename PartitionMap> | |
| 24 | bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map) | |
| 25 | ||
| 26 | template <typename Graph, typename IndexMap> | |
| 27 | bool is_bipartite (const Graph& graph, const IndexMap index_map) | |
| 28 | ||
| 29 | <i>// Version which uses the internal index map</i> | |
| 30 | template <typename Graph> | |
| 31 | bool is_bipartite (const Graph& 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& 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 © 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> |