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 > |
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 > |
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 > |
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 | |
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(t0&: vertex_iter, t1&: vertex_end) |
178 | = boost::vertices(g_: 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(t0&: vertex_iter, t1&: vertex_end) |
188 | = boost::vertices(g_: 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(g: bipartite_vector_graph, |
199 | index_map: boost::get(p: boost::vertex_index, g&: bipartite_vector_graph), is_bipartite: true); |
200 | check_bipartite(g: bipartite_list_graph, index_map: bipartite_index_property_map, is_bipartite: true); |
201 | |
202 | check_bipartite(g: non_bipartite_vector_graph, |
203 | index_map: boost::get(p: boost::vertex_index, g&: non_bipartite_vector_graph), is_bipartite: false); |
204 | check_bipartite( |
205 | g: non_bipartite_list_graph, index_map: non_bipartite_index_property_map, is_bipartite: 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 | |