1 | // Copyright 2004 The Trustees of Indiana University. |
2 | |
3 | // Use, modification and distribution is subject to the Boost Software |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | // Authors: Douglas Gregor |
8 | // Andrew Lumsdaine |
9 | #include <boost/graph/sequential_vertex_coloring.hpp> |
10 | #include <boost/core/lightweight_test.hpp> |
11 | #include <boost/graph/adjacency_list.hpp> |
12 | #include <utility> |
13 | |
14 | using namespace boost; |
15 | |
16 | int main(int, char*[]) |
17 | { |
18 | typedef adjacency_list< listS, vecS, undirectedS > Graph; |
19 | typedef graph_traits< Graph >::vertices_size_type vertices_size_type; |
20 | typedef property_map< Graph, vertex_index_t >::const_type vertex_index_map; |
21 | |
22 | typedef std::pair< int, int > Edge; |
23 | enum nodes |
24 | { |
25 | A, |
26 | B, |
27 | C, |
28 | D, |
29 | E, |
30 | n |
31 | }; |
32 | Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), |
33 | Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) }; |
34 | int m = sizeof(edge_array) / sizeof(Edge); |
35 | Graph g(edge_array, edge_array + m, n); |
36 | |
37 | // Test with the normal order |
38 | std::vector< vertices_size_type > color_vec(num_vertices(g_: g)); |
39 | iterator_property_map< vertices_size_type*, vertex_index_map, |
40 | vertices_size_type, vertices_size_type& > |
41 | color(&color_vec.front(), get(p: vertex_index, g)); |
42 | vertices_size_type num_colors = sequential_vertex_coloring(G: g, color); |
43 | BOOST_TEST(num_colors == 3); |
44 | BOOST_TEST(get(color, (vertices_size_type)A) == 0); |
45 | BOOST_TEST(get(color, (vertices_size_type)B) == 0); |
46 | BOOST_TEST(get(color, (vertices_size_type)C) == 1); |
47 | BOOST_TEST(get(color, (vertices_size_type)D) == 2); |
48 | BOOST_TEST(get(color, (vertices_size_type)E) == 1); |
49 | return boost::report_errors(); |
50 | } |
51 | |