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 <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/lookup_edge.hpp>
15 #include <boost/core/lightweight_test.hpp>
16 #include <boost/graph/bipartite.hpp>
17
18 /// Verifies a 2-coloring
19
20 template < typename Graph, typename ColorMap >
check_two_coloring(const Graph & g,const ColorMap color_map)21 void check_two_coloring(const Graph& g, const ColorMap color_map)
22 {
23 typedef boost::graph_traits< Graph > traits;
24 typename traits::edge_iterator edge_iter, edge_end;
25
26 for (boost::tie(edge_iter, edge_end) = boost::edges(g);
27 edge_iter != edge_end; ++edge_iter)
28 {
29 typename traits::vertex_descriptor source, target;
30 source = boost::source(*edge_iter, g);
31 target = boost::target(*edge_iter, g);
32 BOOST_TEST(
33 boost::get(color_map, source) != boost::get(color_map, target));
34 }
35 }
36
37 /// Tests for a vertex sequence to define an odd cycle
38
39 template < typename Graph, typename RandomAccessIterator >
check_odd_cycle(const Graph & g,RandomAccessIterator first,RandomAccessIterator beyond)40 void check_odd_cycle(
41 const Graph& g, RandomAccessIterator first, RandomAccessIterator beyond)
42 {
43 typedef boost::graph_traits< Graph > traits;
44
45 typename traits::vertex_descriptor first_vertex, current_vertex,
46 last_vertex;
47
48 BOOST_TEST((beyond - first) % 2 == 1);
49
50 // std::cout << "odd_cycle: " << int(*first) << std::endl;
51
52 for (first_vertex = current_vertex = *first++; first != beyond; ++first)
53 {
54 // std::cout << "odd_cycle: " << int(*first) << std::endl;
55
56 last_vertex = current_vertex;
57 current_vertex = *first;
58
59 BOOST_TEST(
60 boost::lookup_edge(current_vertex, last_vertex, g).second);
61 }
62
63 BOOST_TEST(boost::lookup_edge(first_vertex, current_vertex, g).second);
64 }
65
66 /// Call the is_bipartite and find_odd_cycle functions and verify their results.
67
68 template < typename Graph, typename IndexMap >
check_bipartite(const Graph & g,IndexMap index_map,bool is_bipartite)69 void check_bipartite(const Graph& g, IndexMap index_map, bool is_bipartite)
70 {
71 typedef boost::graph_traits< Graph > traits;
72 typedef std::vector< boost::default_color_type > partition_t;
73 typedef std::vector< typename traits::vertex_descriptor > vertex_vector_t;
74 typedef boost::iterator_property_map< partition_t::iterator, IndexMap >
75 partition_map_t;
76
77 partition_t partition(boost::num_vertices(g));
78 partition_map_t partition_map(partition.begin(), index_map);
79
80 vertex_vector_t odd_cycle(boost::num_vertices(g));
81
82 bool first_result = boost::is_bipartite(g, index_map, partition_map);
83
84 BOOST_TEST(first_result == boost::is_bipartite(g, index_map));
85
86 if (first_result)
87 check_two_coloring(g, partition_map);
88
89 BOOST_TEST(first_result == is_bipartite);
90
91 typename vertex_vector_t::iterator second_first = odd_cycle.begin();
92 typename vertex_vector_t::iterator second_beyond
93 = boost::find_odd_cycle(g, index_map, partition_map, second_first);
94
95 if (is_bipartite)
96 {
97 BOOST_TEST(second_beyond == second_first);
98 check_two_coloring(g, partition_map);
99 }
100 else
101 {
102 check_odd_cycle(g, second_first, second_beyond);
103 }
104
105 second_beyond = boost::find_odd_cycle(g, index_map, second_first);
106 if (is_bipartite)
107 {
108 BOOST_TEST(second_beyond == second_first);
109 }
110 else
111 {
112 check_odd_cycle(g, second_first, second_beyond);
113 }
114 }
115
main(int argc,char ** argv)116 int main(int argc, char** argv)
117 {
118 typedef boost::adjacency_list< boost::vecS, boost::vecS,
119 boost::undirectedS >
120 vector_graph_t;
121 typedef boost::adjacency_list< boost::listS, boost::listS,
122 boost::undirectedS >
123 list_graph_t;
124 typedef std::pair< int, int > E;
125
126 typedef std::map< boost::graph_traits< list_graph_t >::vertex_descriptor,
127 size_t >
128 index_map_t;
129 typedef boost::associative_property_map< index_map_t > index_property_map_t;
130
131 /**
132 * Create the graph drawn below.
133 *
134 * 0 - 1 - 2
135 * | |
136 * 3 - 4 - 5 - 6
137 * / \ /
138 * | 7
139 * | |
140 * 8 - 9 - 10
141 **/
142
143 E bipartite_edges[]
144 = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 4), E(3, 8), E(4, 5),
145 E(4, 7), E(5, 6), E(6, 7), E(7, 10), E(8, 9), E(9, 10) };
146 vector_graph_t bipartite_vector_graph(&bipartite_edges[0],
147 &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
148 list_graph_t bipartite_list_graph(&bipartite_edges[0],
149 &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
150
151 /**
152 * Create the graph drawn below.
153 *
154 * 2 - 1 - 0
155 * | |
156 * 3 - 6 - 5 - 4
157 * / \ /
158 * | 7
159 * | /
160 * 8 ---- 9
161 *
162 **/
163
164 E non_bipartite_edges[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 4),
165 E(3, 8), E(4, 5), E(4, 7), E(5, 6), E(6, 7), E(7, 9), E(8, 9) };
166 vector_graph_t non_bipartite_vector_graph(&non_bipartite_edges[0],
167 &non_bipartite_edges[0] + sizeof(non_bipartite_edges) / sizeof(E), 10);
168 list_graph_t non_bipartite_list_graph(&non_bipartite_edges[0],
169 &non_bipartite_edges[0] + sizeof(non_bipartite_edges) / sizeof(E), 10);
170
171 /// Create index maps
172
173 index_map_t bipartite_index_map, non_bipartite_index_map;
174 boost::graph_traits< list_graph_t >::vertex_iterator vertex_iter,
175 vertex_end;
176 size_t i = 0;
177 for (boost::tie(vertex_iter, vertex_end)
178 = boost::vertices(bipartite_list_graph);
179 vertex_iter != vertex_end; ++vertex_iter)
180 {
181 bipartite_index_map[*vertex_iter] = i++;
182 }
183 index_property_map_t bipartite_index_property_map
184 = index_property_map_t(bipartite_index_map);
185
186 i = 0;
187 for (boost::tie(vertex_iter, vertex_end)
188 = boost::vertices(non_bipartite_list_graph);
189 vertex_iter != vertex_end; ++vertex_iter)
190 {
191 non_bipartite_index_map[*vertex_iter] = i++;
192 }
193 index_property_map_t non_bipartite_index_property_map
194 = index_property_map_t(non_bipartite_index_map);
195
196 /// Call real checks
197
198 check_bipartite(bipartite_vector_graph,
199 boost::get(boost::vertex_index, bipartite_vector_graph), true);
200 check_bipartite(bipartite_list_graph, bipartite_index_property_map, true);
201
202 check_bipartite(non_bipartite_vector_graph,
203 boost::get(boost::vertex_index, non_bipartite_vector_graph), false);
204 check_bipartite(
205 non_bipartite_list_graph, non_bipartite_index_property_map, false);
206
207 /// Test some more interfaces
208
209 BOOST_TEST(is_bipartite(bipartite_vector_graph));
210 BOOST_TEST(!is_bipartite(non_bipartite_vector_graph));
211
212 return boost::report_errors();
213 }
214