ceph/src/boost/libs/graph/example/bipartite_example.cpp

   1 /**
   2  *
   3  * Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net)
   4  *
   5  * Authors: Matthias Walter
   6  *
   7  * Distributed under the Boost Software License, Version 1.0. (See
   8  * accompanying file LICENSE_1_0.txt or copy at
   9  * http://www.boost.org/LICENSE_1_0.txt)
  10  *
  11  */
  12
  13 #include <iostream>
  14 #include <boost/graph/adjacency_list.hpp>
  15 #include <boost/graph/bipartite.hpp>
  16
  17 using namespace boost;
  18
  19 /// Example to test for bipartiteness and print the certificates.
  20
  21 template <typename Graph>
  22 void print_bipartite (const Graph& g)
  23 {
  24   typedef graph_traits <Graph> traits;
  25   typename traits::vertex_iterator vertex_iter, vertex_end;
  26
  27   /// Most simple interface just tests for bipartiteness.
  28
  29   bool bipartite = is_bipartite (g);
  30
  31   if (bipartite)
  32   {
  33     typedef std::vector <default_color_type> partition_t;
  34     typedef typename property_map <Graph, vertex_index_t>::type index_map_t;
  35     typedef iterator_property_map <partition_t::iterator, index_map_t> partition_map_t;
  36
  37     partition_t partition (num_vertices (g));
  38     partition_map_t partition_map (partition.begin (), get (vertex_index, g));
  39
  40     /// A second interface yields a bipartition in a color map, if the graph is bipartite.
  41
  42     is_bipartite (g, get (vertex_index, g), partition_map);
  43
  44     for (boost::tie (vertex_iter, vertex_end) = vertices (g); vertex_iter != vertex_end; ++vertex_iter)
  45     {
  46       std::cout << "Vertex " << *vertex_iter << " has color " << (get (partition_map, *vertex_iter) == color_traits <
  47           default_color_type>::white () ? "white" : "black") << std::endl;
  48     }
  49   }
  50   else
  51   {
  52     typedef std::vector <typename traits::vertex_descriptor> vertex_vector_t;
  53     vertex_vector_t odd_cycle;
  54
  55     /// A third interface yields an odd-cycle if the graph is not bipartite.
  56
  57     find_odd_cycle (g, get (vertex_index, g), std::back_inserter (odd_cycle));
  58
  59     std::cout << "Odd cycle consists of the vertices:";
  60     for (size_t i = 0; i < odd_cycle.size (); ++i)
  61     {
  62       std::cout << " " << odd_cycle[i];
  63     }
  64     std::cout << std::endl;
  65   }
  66 }
  67
  68 int main (int argc, char **argv)
  69 {
  70   typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;
  71   typedef std::pair <int, int> E;
  72
  73   /**
  74    * Create the graph drawn below.
  75    *
  76    *       0 - 1 - 2
  77    *       |       |
  78    *   3 - 4 - 5 - 6
  79    *  /      \   /
  80    *  |        7
  81    *  |        |
  82    *  8 - 9 - 10
  83    **/
  84
  85   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 (
  86       6, 7), E (7, 10), E (8, 9), E (9, 10) };
  87   vector_graph_t bipartite_vector_graph (&bipartite_edges[0],
  88       &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
  89
  90   /**
  91    * Create the graph drawn below.
  92    *
  93    *       2 - 1 - 0
  94    *       |       |
  95    *   3 - 6 - 5 - 4
  96    *  /      \   /
  97    *  |        7
  98    *  |       /
  99    *  8 ---- 9
 100    *
 101    **/
 102
 103   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),
 104       E (6, 7), E (7, 9), E (8, 9) };
 105   vector_graph_t non_bipartite_vector_graph (&non_bipartite_edges[0], &non_bipartite_edges[0]
 106       + sizeof(non_bipartite_edges) / sizeof(E), 10);
 107
 108   /// Call test routine for a bipartite and a non-bipartite graph.
 109
 110   print_bipartite (bipartite_vector_graph);
 111
 112   print_bipartite (non_bipartite_vector_graph);
 113
 114   return 0;
 115 }