1 // Copyright 2004 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #include <boost/graph/sequential_vertex_coloring.hpp>
10 #include <boost/test/minimal.hpp>
11 #include <boost/graph/adjacency_list.hpp>
14 using namespace boost
;
16 int test_main(int, char*[])
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
;
22 typedef std::pair
<int, int> Edge
;
23 enum nodes
{A
, B
, C
, D
, E
, n
};
24 Edge edge_array
[] = { Edge(A
, C
), Edge(B
, B
), Edge(B
, D
), Edge(B
, E
),
25 Edge(C
, B
), Edge(C
, D
), Edge(D
, E
), Edge(E
, A
),
27 int m
= sizeof(edge_array
) / sizeof(Edge
);
28 Graph
g(edge_array
, edge_array
+ m
, n
);
30 // Test with the normal order
31 std::vector
<vertices_size_type
> color_vec(num_vertices(g
));
32 iterator_property_map
<vertices_size_type
*, vertex_index_map
,
33 vertices_size_type
, vertices_size_type
&>
34 color(&color_vec
.front(), get(vertex_index
, g
));
35 vertices_size_type num_colors
= sequential_vertex_coloring(g
, color
);
36 BOOST_CHECK(num_colors
== 3);
37 BOOST_CHECK(get(color
, (vertices_size_type
)A
) == 0);
38 BOOST_CHECK(get(color
, (vertices_size_type
)B
) == 0);
39 BOOST_CHECK(get(color
, (vertices_size_type
)C
) == 1);
40 BOOST_CHECK(get(color
, (vertices_size_type
)D
) == 2);
41 BOOST_CHECK(get(color
, (vertices_size_type
)E
) == 1);