Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

Subject: [Boost-commit] svn:boost r60485 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2010-03-11 11:56:03

Author: jewillco
Date: 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
New Revision: 60485
URL: http://svn.boost.org/trac/boost/changeset/60485

Log:
Added bipartite graph algorithms from Matthias Walter
Added:
   trunk/boost/graph/bipartite.hpp (contents, props changed)
   trunk/libs/graph/doc/find_odd_cycle.html (contents, props changed)
   trunk/libs/graph/doc/is_bipartite.html (contents, props changed)
   trunk/libs/graph/example/bipartite_example.cpp (contents, props changed)
   trunk/libs/graph/test/bipartite_test.cpp (contents, props changed)
Text files modified:
   trunk/libs/graph/doc/table_of_contents.html | 2 ++
   trunk/libs/graph/example/Jamfile.v2 | 1 +
   trunk/libs/graph/test/Jamfile.v2 | 1 +
   3 files changed, 4 insertions(+), 0 deletions(-)

Added: trunk/boost/graph/bipartite.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/bipartite.hpp 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -0,0 +1,386 @@
+/**
+ *
+ * Copyright (c) 2010 Matthias Walter (xammy_at_[hidden])
+ *
+ * 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)
+ *
+ */
+
+#ifndef BOOST_GRAPH_BIPARTITE_HPP
+#define BOOST_GRAPH_BIPARTITE_HPP
+
+#include <utility>
+#include <vector>
+#include <exception>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/depth_first_search.hpp>
+#include <boost/graph/one_bit_color_map.hpp>
+#include <boost/bind.hpp>
+
+namespace boost {
+
+ namespace detail {
+
+ /**
+ * The bipartite_visitor_error is thrown if an edge cannot be colored.
+ * The witnesses are the edges incident vertices.
+ */
+
+ template <typename Vertex>
+ struct bipartite_visitor_error: std::exception
+ {
+ std::pair <Vertex, Vertex> witnesses;
+
+ bipartite_visitor_error (Vertex a, Vertex b) :
+ witnesses (a, b)
+ {
+
+ }
+
+ const char* what () const throw ()
+ {
+ return "Graph is not bipartite.";
+ }
+ };
+
+ /**
+ * Functor which colors edges to be non-monochromatic.
+ */
+
+ template <typename PartitionMap>
+ struct bipartition_colorize
+ {
+ typedef on_tree_edge event_filter;
+
+ bipartition_colorize (PartitionMap partition_map) :
+ partition_map_ (partition_map)
+ {
+
+ }
+
+ template <typename Edge, typename Graph>
+ void operator() (Edge e, const Graph& g)
+ {
+ typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
+ typedef color_traits <typename property_traits <PartitionMap>::value_type> color_traits;
+
+ vertex_descriptor_t source_vertex = source (e, g);
+ vertex_descriptor_t target_vertex = target (e, g);
+ if (get (partition_map_, source_vertex) == color_traits::white ())
+ put (partition_map_, target_vertex, color_traits::black ());
+ else
+ put (partition_map_, target_vertex, color_traits::white ());
+ }
+
+ private:
+ PartitionMap partition_map_;
+ };
+
+ /**
+ * Creates a bipartition_colorize functor which colors edges
+ * to be non-monochromatic.
+ *
+ * @param partition_map Color map for the bipartition
+ * @return The functor.
+ */
+
+ template <typename PartitionMap>
+ inline bipartition_colorize <PartitionMap> colorize_bipartition (PartitionMap partition_map)
+ {
+ return bipartition_colorize <PartitionMap> (partition_map);
+ }
+
+ /**
+ * Functor which tests an edge to be monochromatic.
+ */
+
+ template <typename PartitionMap>
+ struct bipartition_check
+ {
+ typedef on_back_edge event_filter;
+
+ bipartition_check (PartitionMap partition_map) :
+ partition_map_ (partition_map)
+ {
+
+ }
+
+ template <typename Edge, typename Graph>
+ void operator() (Edge e, const Graph& g)
+ {
+ typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
+
+ vertex_descriptor_t source_vertex = source (e, g);
+ vertex_descriptor_t target_vertex = target (e, g);
+ if (get (partition_map_, source_vertex) == get (partition_map_, target_vertex))
+ throw bipartite_visitor_error <vertex_descriptor_t> (source_vertex, target_vertex);
+ }
+
+ private:
+ PartitionMap partition_map_;
+ };
+
+ /**
+ * Creates a bipartition_check functor which raises an error if a
+ * monochromatic edge is found.
+ *
+ * @param partition_map The map for a bipartition.
+ * @return The functor.
+ */
+
+ template <typename PartitionMap>
+ inline bipartition_check <PartitionMap> check_bipartition (PartitionMap partition_map)
+ {
+ return bipartition_check <PartitionMap> (partition_map);
+ }
+
+ /**
+ * Find the beginning of a common suffix of two sequences
+ *
+ * @param sequence1 Pair of bidirectional iterators defining the first sequence.
+ * @param sequence2 Pair of bidirectional iterators defining the second sequence.
+ * @return Pair of iterators pointing to the beginning of the common suffix.
+ */
+
+ template <typename BiDirectionalIterator1, typename BiDirectionalIterator2>
+ inline std::pair <BiDirectionalIterator1, BiDirectionalIterator2> reverse_mismatch (std::pair <
+ BiDirectionalIterator1, BiDirectionalIterator1> sequence1, std::pair <BiDirectionalIterator2,
+ BiDirectionalIterator2> sequence2)
+ {
+ if (sequence1.first == sequence1.second || sequence2.first == sequence2.second)
+ return std::make_pair (sequence1.first, sequence2.first);
+
+ BiDirectionalIterator1 iter1 = sequence1.second;
+ BiDirectionalIterator2 iter2 = sequence2.second;
+
+ while (true)
+ {
+ --iter1;
+ --iter2;
+ if (*iter1 != *iter2)
+ {
+ ++iter1;
+ ++iter2;
+ break;
+ }
+ if (iter1 == sequence1.first)
+ break;
+ if (iter2 == sequence2.first)
+ break;
+ }
+
+ return std::make_pair (iter1, iter2);
+ }
+
+ }
+
+ /**
+ * Checks a given graph for bipartiteness and fills the given color map with
+ * white and black according to the bipartition. If the graph is not
+ * bipartite, the contents of the color map are undefined. Runs in linear
+ * time in the size of the graph, if access to the property maps is in
+ * constant time.
+ *
+ * @param graph The given graph.
+ * @param index_map An index map associating vertices with an index.
+ * @param partition_map A color map to fill with the bipartition.
+ * @return true if and only if the given graph is bipartite.
+ */
+
+ template <typename Graph, typename IndexMap, typename PartitionMap>
+ bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map)
+ {
+ /// General types and variables
+ typedef typename property_traits <PartitionMap>::value_type partition_color_t;
+ typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
+ typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t;
+
+ /// Declare dfs visitor
+ // detail::empty_recorder recorder;
+ // typedef detail::bipartite_visitor <PartitionMap, detail::empty_recorder> dfs_visitor_t;
+ // dfs_visitor_t dfs_visitor (partition_map, recorder);
+
+
+ /// Call dfs
+ try
+ {
+ depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair (
+ detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map),
+ put_property (partition_map, color_traits <partition_color_t>::white (), on_start_vertex ()))))));
+
+ // depth_first_search (graph, vertex_index_map (index_map).visitor (dfs_visitor));
+ }
+ catch (detail::bipartite_visitor_error <vertex_descriptor_t> error)
+ {
+ return false;
+ }
+
+ return true;
+ }
+
+ /**
+ * Checks a given graph for bipartiteness.
+ *
+ * @param graph The given graph.
+ * @param index_map An index map associating vertices with an index.
+ * @return true if and only if the given graph is bipartite.
+ */
+
+ template <typename Graph, typename IndexMap>
+ bool is_bipartite (const Graph& graph, const IndexMap index_map)
+ {
+ typedef one_bit_color_map <IndexMap> partition_map_t;
+ partition_map_t partition_map (num_vertices (graph), index_map);
+
+ return is_bipartite (graph, index_map, partition_map);
+ }
+
+ /**
+ * Checks a given graph for bipartiteness. The graph must
+ * have an internal vertex_index property. Runs in linear time in the
+ * size of the graph, if access to the property maps is in constant time.
+ *
+ * @param graph The given graph.
+ * @return true if and only if the given graph is bipartite.
+ */
+
+ template <typename Graph>
+ bool is_bipartite (const Graph& graph)
+ {
+ return is_bipartite (graph, get (vertex_index, graph));
+ }
+
+ /**
+ * Checks a given graph for bipartiteness and fills a given color map with
+ * white and black according to the bipartition. If the graph is not
+ * bipartite, a sequence of vertices, producing an odd-cycle, is written to
+ * the output iterator. The final iterator value is returned. Runs in linear
+ * time in the size of the graph, if access to the property maps is in
+ * constant time.
+ *
+ * @param graph The given graph.
+ * @param index_map An index map associating vertices with an index.
+ * @param partition_map A color map to fill with the bipartition.
+ * @param result An iterator to write the odd-cycle vertices to.
+ * @return The final iterator value after writing.
+ */
+
+ 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)
+ {
+ /// General types and variables
+ typedef typename property_traits <PartitionMap>::value_type partition_color_t;
+ typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
+ typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t;
+ vertex_iterator_t vertex_iter, vertex_end;
+
+ /// Declare predecessor map
+ typedef std::vector <vertex_descriptor_t> predecessors_t;
+ typedef iterator_property_map <typename predecessors_t::iterator, IndexMap, vertex_descriptor_t,
+ vertex_descriptor_t&> predecessor_map_t;
+ typedef predecessor_recorder <predecessor_map_t, IndexMap> predecessor_recorder_t;
+
+ predecessors_t predecessors (num_vertices (graph), graph_traits <Graph>::null_vertex ());
+ predecessor_map_t predecessor_map (predecessors.begin (), index_map);
+ predecessor_recorder_t predecessor_recorder (predecessor_map);
+
+ /// Initialize predecessor map
+ for (tie (vertex_iter, vertex_end) = vertices (graph); vertex_iter != vertex_end; ++vertex_iter)
+ {
+ put (predecessor_map, *vertex_iter, *vertex_iter);
+ }
+
+ /// Call dfs
+ try
+ {
+ depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair (
+ detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map),
+ std::make_pair (put_property (partition_map, color_traits <partition_color_t>::white (),
+ on_start_vertex ()), record_predecessors (predecessor_map, on_tree_edge ())))))));
+ }
+ catch (detail::bipartite_visitor_error <vertex_descriptor_t> error)
+ {
+ typedef std::vector <vertex_descriptor_t> path_t;
+
+ path_t path1, path2;
+ vertex_descriptor_t next, current;
+
+ /// First path
+ next = error.witnesses.first;
+ do
+ {
+ current = next;
+ path1.push_back (current);
+ next = predecessor_map[current];
+ }
+ while (current != next);
+
+ /// Second path
+ next = error.witnesses.second;
+ do
+ {
+ current = next;
+ path2.push_back (current);
+ next = predecessor_map[current];
+ }
+ while (current != next);
+
+ /// Find beginning of common suffix
+ std::pair <typename path_t::iterator, typename path_t::iterator> mismatch = detail::reverse_mismatch (
+ std::make_pair (path1.begin (), path1.end ()), std::make_pair (path2.begin (), path2.end ()));
+
+ /// Copy the odd-length cycle
+ result = std::copy (path1.begin (), mismatch.first + 1, result);
+ return std::reverse_copy (path2.begin (), mismatch.second, result);
+ }
+
+ return result;
+ }
+
+ /**
+ * Checks a given graph for bipartiteness. If the graph is not bipartite, a
+ * sequence of vertices, producing an odd-cycle, is written to the output
+ * iterator. The final iterator value is returned. Runs in linear time in the
+ * size of the graph, if access to the property maps is in constant time.
+ *
+ * @param graph The given graph.
+ * @param index_map An index map associating vertices with an index.
+ * @param result An iterator to write the odd-cycle vertices to.
+ * @return The final iterator value after writing.
+ */
+
+ template <typename Graph, typename IndexMap, typename OutputIterator>
+ OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result)
+ {
+ typedef one_bit_color_map <IndexMap> partition_map_t;
+ partition_map_t partition_map (num_vertices (graph), index_map);
+
+ return find_odd_cycle (graph, index_map, partition_map, result);
+ }
+
+ /**
+ * Checks a given graph for bipartiteness. If the graph is not bipartite, a
+ * sequence of vertices, producing an odd-cycle, is written to the output
+ * iterator. The final iterator value is returned. The graph must have an
+ * internal vertex_index property. Runs in linear time in the size of the
+ * graph, if access to the property maps is in constant time.
+ *
+ * @param graph The given graph.
+ * @param result An iterator to write the odd-cycle vertices to.
+ * @return The final iterator value after writing.
+ */
+
+ template <typename Graph, typename OutputIterator>
+ OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result)
+ {
+ return find_odd_cycle (graph, get (vertex_index, graph), result);
+ }
+}
+
+#endif /// BOOST_GRAPH_BIPARTITE_HPP

Added: trunk/libs/graph/doc/find_odd_cycle.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/find_odd_cycle.html 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -0,0 +1,152 @@
+<!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 &lt;typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator&gt;
+OutputIterator find_odd_cycle (const Graph&amp; graph, const IndexMap index_map, PartitionMap partition_map, OutputIterator result)
+
+template &lt;typename Graph, typename IndexMap, typename OutputIterator&gt;
+OutputIterator find_odd_cycle (const Graph&amp; graph, const IndexMap index_map, OutputIterator result)
+
+<i>// Version which uses the internal index map</i>
+template &lt;typename Graph, typename OutputIterator&gt;
+OutputIterator find_odd_cycle (const Graph&amp; 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
+is_bipartite(),
+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>
+boost/graph/bipartite.hpp
+</p>
+
+<h3>Parameters</h3>
+
+<p>
+IN: <tt>const Graph&amp; 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 ColorValue.
+</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.sgi.com/tech/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>
+is_bipartite()
+</p>
+
+<h3>Example</h3>
+
+<p>
+The file example/bipartite_example.cpp
+contains an example of testing an undirected graph for bipartiteness.
+<br/>
+</p>
+
+<hr/>
+
+<p>
+Copyright &copy; 2010 Matthias Walter
+(<a class="external" href="mailto:xammy_at_[hidden]">xammy_at_[hidden]</a>)
+</p>
+
+</body>
+</html>

Added: trunk/libs/graph/doc/is_bipartite.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/is_bipartite.html 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -0,0 +1,127 @@
+<!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 &lt;typename Graph, typename IndexMap, typename PartitionMap&gt;
+bool is_bipartite (const Graph&amp; graph, const IndexMap index_map, PartitionMap partition_map)
+
+template &lt;typename Graph, typename IndexMap&gt;
+bool is_bipartite (const Graph&amp; graph, const IndexMap index_map)
+
+<i>// Version which uses the internal index map</i>
+template &lt;typename Graph&gt;
+bool is_bipartite (const Graph&amp; 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>
+boost/graph/bipartite.hpp
+</p>
+
+<h3>Parameters</h3>
+
+<p>
+IN: <tt>const Graph&amp; 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 ColorValue.
+</p></blockquote>
+
+
+<h3>Complexity</h3>
+
+<p>
+The time complexity for the algorithm is <i>O(V + E)</i>.
+</p>
+
+<h3>See Also</h3>
+
+<p>
+find_odd_cycle()
+</p>
+
+<h3>Example</h3>
+
+<p>
+The file examples/bipartite.cpp
+contains an example of testing an undirected graph for bipartiteness.
+<br/>
+</p>
+
+<hr/>
+
+<p>
+Copyright &copy; 2010 Matthias Walter
+(<a class="external" href="mailto:xammy_at_[hidden]">xammy_at_[hidden]</a>)
+</p>
+
+</body>
+</html>

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -265,6 +265,8 @@
                   <ol>
                       <li>metric_tsp_approx</li>
                       <LI>sequential_vertex_coloring
+ <LI>is_bipartite (including two-coloring of bipartite graphs)
+ <LI>find_odd_cycle
                   </ol>
               </li>
 

Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 (original)
+++ trunk/libs/graph/example/Jamfile.v2 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -20,3 +20,4 @@
 exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;
 exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;
 exe grid_graph_example : grid_graph_example.cpp ;
+exe bipartite_example : bipartite_example.cpp ;

Added: trunk/libs/graph/example/bipartite_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/bipartite_example.cpp 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -0,0 +1,115 @@
+/**
+ *
+ * Copyright (c) 2010 Matthias Walter (xammy_at_[hidden])
+ *
+ * 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)
+ *
+ */
+
+#include <iostream>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/bipartite.hpp>
+
+using namespace boost;
+
+/// Example to test for bipartiteness and print the certificates.
+
+template <typename Graph>
+void print_bipartite (const Graph& g)
+{
+ typedef graph_traits <Graph> traits;
+ typename traits::vertex_iterator vertex_iter, vertex_end;
+
+ /// Most simple interface just tests for bipartiteness.
+
+ bool bipartite = is_bipartite (g);
+
+ if (bipartite)
+ {
+ typedef std::vector <default_color_type> partition_t;
+ typedef vec_adj_list_vertex_id_map <no_property, unsigned int> index_map_t;
+ typedef iterator_property_map <partition_t::iterator, index_map_t> partition_map_t;
+
+ partition_t partition (num_vertices (g));
+ partition_map_t partition_map (partition.begin (), get (vertex_index, g));
+
+ /// A second interface yields a bipartition in a color map, if the graph is bipartite.
+
+ is_bipartite (g, get (vertex_index, g), partition_map);
+
+ for (tie (vertex_iter, vertex_end) = vertices (g); vertex_iter != vertex_end; ++vertex_iter)
+ {
+ std::cout << "Vertex " << *vertex_iter << " has color " << (get (partition_map, *vertex_iter) == color_traits <
+ default_color_type>::white () ? "white" : "black") << std::endl;
+ }
+ }
+ else
+ {
+ typedef std::vector <typename traits::vertex_descriptor> vertex_vector_t;
+ vertex_vector_t odd_cycle;
+
+ /// A third interface yields an odd-cycle if the graph is not bipartite.
+
+ find_odd_cycle (g, get (vertex_index, g), std::back_inserter (odd_cycle));
+
+ std::cout << "Odd cycle consists of the vertices:";
+ for (size_t i = 0; i < odd_cycle.size (); ++i)
+ {
+ std::cout << " " << odd_cycle[i];
+ }
+ std::cout << std::endl;
+ }
+}
+
+int main (int argc, char **argv)
+{
+ typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;
+ typedef std::pair <int, int> E;
+
+ /**
+ * Create the graph drawn below.
+ *
+ * 0 - 1 - 2
+ * | |
+ * 3 - 4 - 5 - 6
+ * / \ /
+ * | 7
+ * | |
+ * 8 - 9 - 10
+ **/
+
+ E bipartite_edges[] = { E (0, 1), E (0, 4), E (1, 2), E (2, 6), E (3, 4), E (3, 8), E (4, 5), E (4, 7), E (5, 6), E (
+ 6, 7), E (7, 10), E (8, 9), E (9, 10) };
+ vector_graph_t bipartite_vector_graph (&bipartite_edges[0],
+ &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
+
+ /**
+ * Create the graph drawn below.
+ *
+ * 2 - 1 - 0
+ * | |
+ * 3 - 6 - 5 - 4
+ * / \ /
+ * | 7
+ * | /
+ * 8 ---- 9
+ *
+ **/
+
+ E non_bipartite_edges[] = { E (0, 1), E (0, 4), E (1, 2), E (2, 6), E (3, 6), E (3, 8), E (4, 5), E (4, 7), E (5, 6),
+ E (6, 7), E (7, 9), E (8, 9) };
+ vector_graph_t non_bipartite_vector_graph (&non_bipartite_edges[0], &non_bipartite_edges[0]
+ + sizeof(non_bipartite_edges) / sizeof(E), 10);
+
+ /// Call test routine for a bipartite and a non-bipartite graph.
+
+ print_bipartite (bipartite_vector_graph);
+
+ print_bipartite (non_bipartite_vector_graph);
+
+ return 0;
+}

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -36,6 +36,7 @@
     [ run bellman-test.cpp ]
     [ run betweenness_centrality_test.cpp : 100 ]
     [ run bidir_remove_edge.cpp ]
+ [ run bipartite_test.cpp ]
     [ run csr_graph_test.cpp : : : : : <variant>release ]
     [ run dag_longest_paths.cpp ]
     [ run dfs.cpp ../../test/build//boost_test_exec_monitor ]

Added: trunk/libs/graph/test/bipartite_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/bipartite_test.cpp 2010-03-11 11:56:01 EST (Thu, 11 Mar 2010)
@@ -0,0 +1,189 @@
+/**
+ *
+ * Copyright (c) 2010 Matthias Walter (xammy_at_[hidden])
+ *
+ * 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)
+ *
+ */
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/lookup_edge.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/bipartite.hpp>
+
+/// Verifies a 2-coloring
+
+template <typename Graph, typename ColorMap>
+void check_two_coloring (const Graph& g, const ColorMap color_map)
+{
+ typedef boost::graph_traits <Graph> traits;
+ typename traits::edge_iterator edge_iter, edge_end;
+
+ for (boost::tie (edge_iter, edge_end) = boost::edges (g); edge_iter != edge_end; ++edge_iter)
+ {
+ typename traits::vertex_descriptor source, target;
+ source = boost::source (*edge_iter, g);
+ target = boost::target (*edge_iter, g);
+ BOOST_REQUIRE (boost::get(color_map, source) != boost::get(color_map, target));
+ }
+}
+
+/// Tests for a vertex sequence to define an odd cycle
+
+template <typename Graph, typename RandomAccessIterator>
+void check_odd_cycle (const Graph& g, RandomAccessIterator first, RandomAccessIterator beyond)
+{
+ typedef boost::graph_traits <Graph> traits;
+
+ typename traits::vertex_descriptor first_vertex, current_vertex, last_vertex;
+
+ BOOST_CHECK ((beyond - first) % 2 == 1);
+
+ // std::cout << "odd_cycle: " << int(*first) << std::endl;
+
+ for (first_vertex = current_vertex = *first++; first != beyond; ++first)
+ {
+ // std::cout << "odd_cycle: " << int(*first) << std::endl;
+
+ last_vertex = current_vertex;
+ current_vertex = *first;
+
+ BOOST_REQUIRE (boost::lookup_edge (current_vertex, last_vertex, g).second);
+ }
+
+ BOOST_REQUIRE (boost::lookup_edge (first_vertex, current_vertex, g).second);
+}
+
+/// Call the is_bipartite and find_odd_cycle functions and verify their results.
+
+template <typename Graph, typename IndexMap>
+void check_bipartite (const Graph& g, IndexMap index_map, bool is_bipartite)
+{
+ typedef boost::graph_traits <Graph> traits;
+ typedef std::vector <boost::default_color_type> partition_t;
+ typedef std::vector <typename traits::vertex_descriptor> vertex_vector_t;
+ typedef boost::iterator_property_map <partition_t::iterator, IndexMap> partition_map_t;
+
+ partition_t partition (boost::num_vertices (g));
+ partition_map_t partition_map (partition.begin (), index_map);
+
+ vertex_vector_t odd_cycle (boost::num_vertices (g));
+
+ bool first_result = boost::is_bipartite (g, index_map, partition_map);
+
+ BOOST_REQUIRE (first_result == boost::is_bipartite(g, index_map));
+
+ if (first_result)
+ check_two_coloring (g, partition_map);
+
+ BOOST_CHECK (first_result == is_bipartite);
+
+ typename vertex_vector_t::iterator second_first = odd_cycle.begin ();
+ typename vertex_vector_t::iterator second_beyond = boost::find_odd_cycle (g, index_map, partition_map, second_first);
+
+ if (is_bipartite)
+ {
+ BOOST_CHECK (second_beyond == second_first);
+ check_two_coloring (g, partition_map);
+ }
+ else
+ {
+ check_odd_cycle (g, second_first, second_beyond);
+ }
+
+ second_beyond = boost::find_odd_cycle (g, index_map, second_first);
+ if (is_bipartite)
+ {
+ BOOST_CHECK (second_beyond == second_first);
+ }
+ else
+ {
+ check_odd_cycle (g, second_first, second_beyond);
+ }
+}
+
+int test_main (int argc, char **argv)
+{
+ typedef boost::adjacency_list <boost::vecS, boost::vecS, boost::undirectedS> vector_graph_t;
+ typedef boost::adjacency_list <boost::listS, boost::listS, boost::undirectedS> list_graph_t;
+ typedef std::pair <int, int> E;
+
+ typedef std::map <boost::graph_traits <list_graph_t>::vertex_descriptor, size_t> index_map_t;
+ typedef boost::associative_property_map <index_map_t> index_property_map_t;
+
+ /**
+ * Create the graph drawn below.
+ *
+ * 0 - 1 - 2
+ * | |
+ * 3 - 4 - 5 - 6
+ * / \ /
+ * | 7
+ * | |
+ * 8 - 9 - 10
+ **/
+
+ E bipartite_edges[] = { E (0, 1), E (0, 4), E (1, 2), E (2, 6), E (3, 4), E (3, 8), E (4, 5), E (4, 7), E (5, 6), E (
+ 6, 7), E (7, 10), E (8, 9), E (9, 10) };
+ vector_graph_t bipartite_vector_graph (&bipartite_edges[0],
+ &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
+ list_graph_t
+ bipartite_list_graph (&bipartite_edges[0], &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
+
+ /**
+ * Create the graph drawn below.
+ *
+ * 2 - 1 - 0
+ * | |
+ * 3 - 6 - 5 - 4
+ * / \ /
+ * | 7
+ * | /
+ * 8 ---- 9
+ *
+ **/
+
+ E non_bipartite_edges[] = { E (0, 1), E (0, 4), E (1, 2), E (2, 6), E (3, 4), E (3, 8), E (4, 5), E (4, 7), E (5, 6),
+ E (6, 7), E (7, 9), E (8, 9) };
+ vector_graph_t non_bipartite_vector_graph (&non_bipartite_edges[0], &non_bipartite_edges[0]
+ + sizeof(non_bipartite_edges) / sizeof(E), 10);
+ list_graph_t non_bipartite_list_graph (&non_bipartite_edges[0], &non_bipartite_edges[0] + sizeof(non_bipartite_edges)
+ / sizeof(E), 10);
+
+ /// Create index maps
+
+ index_map_t bipartite_index_map, non_bipartite_index_map;
+ boost::graph_traits <list_graph_t>::vertex_iterator vertex_iter, vertex_end;
+ size_t i = 0;
+ for (boost::tie (vertex_iter, vertex_end) = boost::vertices (bipartite_list_graph); vertex_iter != vertex_end; ++vertex_iter)
+ {
+ bipartite_index_map[*vertex_iter] = i++;
+ }
+ index_property_map_t bipartite_index_property_map = index_property_map_t (bipartite_index_map);
+
+ i = 0;
+ for (boost::tie (vertex_iter, vertex_end) = boost::vertices (non_bipartite_list_graph); vertex_iter != vertex_end; ++vertex_iter)
+ {
+ non_bipartite_index_map[*vertex_iter] = i++;
+ }
+ index_property_map_t non_bipartite_index_property_map = index_property_map_t (non_bipartite_index_map);
+
+ /// Call real checks
+
+ check_bipartite (bipartite_vector_graph, boost::get (boost::vertex_index, bipartite_vector_graph), true);
+ check_bipartite (bipartite_list_graph, bipartite_index_property_map, true);
+
+ check_bipartite (non_bipartite_vector_graph, boost::get (boost::vertex_index, non_bipartite_vector_graph), false);
+ check_bipartite (non_bipartite_list_graph, non_bipartite_index_property_map, false);
+
+ /// Test some more interfaces
+
+ BOOST_REQUIRE (is_bipartite (bipartite_vector_graph));
+ BOOST_REQUIRE (!is_bipartite (non_bipartite_vector_graph));
+
+ return 0;
+}

Date view Thread view Subject view Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk