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 > void print_bipartite(const Graph& g)
  22 {
  23     typedef graph_traits< Graph > traits;
  24     typename traits::vertex_iterator vertex_iter, vertex_end;
  25
  26     /// Most simple interface just tests for bipartiteness.
  27
  28     bool bipartite = is_bipartite(g);
  29
  30     if (bipartite)
  31     {
  32         typedef std::vector< default_color_type > partition_t;
  33         typedef
  34             typename property_map< Graph, vertex_index_t >::type index_map_t;
  35         typedef iterator_property_map< partition_t::iterator, index_map_t >
  36             partition_map_t;
  37
  38         partition_t partition(num_vertices(g));
  39         partition_map_t partition_map(partition.begin(), get(vertex_index, g));
  40
  41         /// A second interface yields a bipartition in a color map, if the graph
  42         /// is bipartite.
  43
  44         is_bipartite(g, get(vertex_index, g), partition_map);
  45
  46         for (boost::tie(vertex_iter, vertex_end) = vertices(g);
  47              vertex_iter != vertex_end; ++vertex_iter)
  48         {
  49             std::cout
  50                 << "Vertex " << *vertex_iter << " has color "
  51                 << (get(partition_map, *vertex_iter)
  52                                == color_traits< default_color_type >::white()
  53                            ? "white"
  54                            : "black")
  55                 << std::endl;
  56         }
  57     }
  58     else
  59     {
  60         typedef std::vector< typename traits::vertex_descriptor >
  61             vertex_vector_t;
  62         vertex_vector_t odd_cycle;
  63
  64         /// A third interface yields an odd-cycle if the graph is not bipartite.
  65
  66         find_odd_cycle(g, get(vertex_index, g), std::back_inserter(odd_cycle));
  67
  68         std::cout << "Odd cycle consists of the vertices:";
  69         for (size_t i = 0; i < odd_cycle.size(); ++i)
  70         {
  71             std::cout << " " << odd_cycle[i];
  72         }
  73         std::cout << std::endl;
  74     }
  75 }
  76
  77 int main(int argc, char** argv)
  78 {
  79     typedef adjacency_list< vecS, vecS, undirectedS > vector_graph_t;
  80     typedef std::pair< int, int > E;
  81
  82     /**
  83      * Create the graph drawn below.
  84      *
  85      *       0 - 1 - 2
  86      *       |       |
  87      *   3 - 4 - 5 - 6
  88      *  /      \   /
  89      *  |        7
  90      *  |        |
  91      *  8 - 9 - 10
  92      **/
  93
  94     E bipartite_edges[]
  95         = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 4), E(3, 8), E(4, 5),
  96               E(4, 7), E(5, 6), E(6, 7), E(7, 10), E(8, 9), E(9, 10) };
  97     vector_graph_t bipartite_vector_graph(&bipartite_edges[0],
  98         &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
  99
 100     /**
 101      * Create the graph drawn below.
 102      *
 103      *       2 - 1 - 0
 104      *       |       |
 105      *   3 - 6 - 5 - 4
 106      *  /      \   /
 107      *  |        7
 108      *  |       /
 109      *  8 ---- 9
 110      *
 111      **/
 112
 113     E non_bipartite_edges[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 6),
 114         E(3, 8), E(4, 5), E(4, 7), E(5, 6), E(6, 7), E(7, 9), E(8, 9) };
 115     vector_graph_t non_bipartite_vector_graph(&non_bipartite_edges[0],
 116         &non_bipartite_edges[0] + sizeof(non_bipartite_edges) / sizeof(E), 10);
 117
 118     /// Call test routine for a bipartite and a non-bipartite graph.
 119
 120     print_bipartite(bipartite_vector_graph);
 121
 122     print_bipartite(non_bipartite_vector_graph);
 123
 124     return 0;
 125 }