123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152 |
- <!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: find_odd_cycle</title>
- </head>
- <body>
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <h1>
- <tt>find_odd_cycle</tt>
- </h1>
- <pre>
- <i>// Version with a colormap to retrieve the bipartition</i>
- template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator>
- OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map, OutputIterator result)
- template <typename Graph, typename IndexMap, typename OutputIterator>
- OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result)
- <i>// Version which uses the internal index map</i>
- template <typename Graph, typename OutputIterator>
- OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result)
- </pre>
- <p>
- The <tt>find_odd_cycle</tt> function 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>
- Another equivalent characterization is the non-existance of odd-length cycles,
- meaning that a graph is bipartite if and only if it does not contain a
- cycle with an odd number of vertices as a subgraph.
- <tt>find_odd_cycle()</tt> does nearly the same as
- <a href="./is_bipartite.html"><tt>is_bipartite()</tt></a>,
- but additionally constructs an odd-length cycle if the graph is found to be
- not bipartite.
- </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 odd-length cycle is written into the Output Iterator <tt>result</tt> if
- one exists. The final final iterator is returned by 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>
- <p>
- OUT: <tt>OutputIterator result</tt>
- </p>
- <blockquote><p>
- The <tt>find_odd_cycle</tt> function finds an odd-length cycle if the graph is
- not bipartite. The sequence of vertices producing such a cycle is written
- into this iterator. The <tt>OutputIterator</tt> type must be a model of
- <a class="external" href="http://www.boost.org/sgi/stl/OutputIterator.html">
- OutputIterator</a>. The graph's vertex descriptor type must be in the set
- of value types of the iterator. The final value is returned by the
- function. If the graph is bipartite (i.e. no odd-length cycle exists), nothing
- is written, thus the given iterator matches the return value.
- </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="./is_bipartite.html"><tt>is_bipartite()</tt></a>
- </p>
- <h3>Example</h3>
- <p>
- The file <a href="../example/bipartite_example.cpp"><tt>example/bipartite_example.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>
|