1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2004 The Trustees of Indiana University
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 #ifndef BOOST_GRAPH_SEQUENTIAL_VERTEX_COLORING_HPP
11 #define BOOST_GRAPH_SEQUENTIAL_VERTEX_COLORING_HPP
14 #include <boost/graph/graph_traits.hpp>
15 #include <boost/tuple/tuple.hpp>
16 #include <boost/property_map/property_map.hpp>
17 #include <boost/limits.hpp>
19 #ifdef BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS
23 /* This algorithm is to find coloring of a graph
26 Let G = (V,E) be a graph with vertices (somehow) ordered v_1, v_2, ...,
27 v_n. For k = 1, 2, ..., n the sequential algorithm assigns v_k to the
28 smallest possible color.
32 Thomas F. Coleman and Jorge J. More, Estimation of sparse Jacobian
33 matrices and graph coloring problems. J. Numer. Anal. V20, P187-209, 1983
35 v_k is stored as o[k] here.
37 The color of the vertex v will be stored in color[v].
38 i.e., vertex v belongs to coloring color[v] */
41 template <class VertexListGraph
, class OrderPA
, class ColorMap
>
42 typename property_traits
<ColorMap
>::value_type
43 sequential_vertex_coloring(const VertexListGraph
& G
, OrderPA order
,
46 typedef graph_traits
<VertexListGraph
> GraphTraits
;
47 typedef typename
GraphTraits::vertex_descriptor Vertex
;
48 typedef typename property_traits
<ColorMap
>::value_type size_type
;
50 size_type max_color
= 0;
51 const size_type V
= num_vertices(G
);
53 // We need to keep track of which colors are used by
54 // adjacent vertices. We do this by marking the colors
55 // that are used. The mark array contains the mark
56 // for each color. The length of mark is the
57 // number of vertices since the maximum possible number of colors
58 // is the number of vertices.
59 std::vector
<size_type
> mark(V
,
60 std::numeric_limits
<size_type
>::max
BOOST_PREVENT_MACRO_SUBSTITUTION());
63 typename
GraphTraits::vertex_iterator v
, vend
;
64 for (tie(v
, vend
) = vertices(G
); v
!= vend
; ++v
)
67 //Determine the color for every vertex one by one
68 for ( size_type i
= 0; i
< V
; i
++) {
69 Vertex current
= get(order
,i
);
70 typename
GraphTraits::adjacency_iterator v
, vend
;
72 //Mark the colors of vertices adjacent to current.
73 //i can be the value for marking since i increases successively
74 for (tie(v
,vend
) = adjacent_vertices(current
, G
); v
!= vend
; ++v
)
75 mark
[get(color
,*v
)] = i
;
77 //Next step is to assign the smallest un-marked color
78 //to the current vertex.
81 //Scan through all useable colors, find the smallest possible
82 //color that is not used by neighbors. Note that if mark[j]
83 //is equal to i, color j is used by one of the current vertex's
85 while ( j
< max_color
&& mark
[j
] == i
)
88 if ( j
== max_color
) //All colors are used up. Add one more color
91 //At this point, j is the smallest possible color
92 put(color
, current
, j
); //Save the color of vertex current
98 template<class VertexListGraph
, class ColorMap
>
99 typename property_traits
<ColorMap
>::value_type
100 sequential_vertex_coloring(const VertexListGraph
& G
, ColorMap color
)
102 typedef typename graph_traits
<VertexListGraph
>::vertex_descriptor
104 typedef typename graph_traits
<VertexListGraph
>::vertex_iterator
107 std::pair
<vertex_iterator
, vertex_iterator
> v
= vertices(G
);
108 #ifndef BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS
109 std::vector
<vertex_descriptor
> order(v
.first
, v
.second
);
111 std::vector
<vertex_descriptor
> order
;
112 order
.reserve(std::distance(v
.first
, v
.second
));
113 while (v
.first
!= v
.second
) order
.push_back(*v
.first
++);
115 return sequential_vertex_coloring
117 make_iterator_property_map
118 (order
.begin(), identity_property_map(),
119 graph_traits
<VertexListGraph
>::null_vertex()),