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