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
print_bipartite(const Graph & g)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
main(int argc,char ** argv)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 }
126