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 |
5 | // |
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 |
12 | |
13 | #include <vector> |
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> |
18 | |
19 | #ifdef BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS |
20 | # include <iterator> |
21 | #endif |
22 | |
23 | /* This algorithm is to find coloring of a graph |
24 | |
25 | Algorithm: |
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. |
29 | |
30 | Reference: |
31 | |
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 |
34 | |
35 | v_k is stored as o[k] here. |
36 | |
37 | The color of the vertex v will be stored in color[v]. |
38 | i.e., vertex v belongs to coloring color[v] */ |
39 | |
40 | namespace boost { |
41 | template <class VertexListGraph, class OrderPA, class ColorMap> |
42 | typename property_traits<ColorMap>::value_type |
43 | sequential_vertex_coloring(const VertexListGraph& G, OrderPA order, |
44 | ColorMap color) |
45 | { |
46 | typedef graph_traits<VertexListGraph> GraphTraits; |
47 | typedef typename GraphTraits::vertex_descriptor Vertex; |
48 | typedef typename property_traits<ColorMap>::value_type size_type; |
49 | |
50 | size_type max_color = 0; |
51 | const size_type V = num_vertices(G); |
52 | |
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()); |
61 | |
62 | //Initialize colors |
63 | typename GraphTraits::vertex_iterator v, vend; |
64 | for (boost::tie(v, vend) = vertices(G); v != vend; ++v) |
65 | put(color, *v, V-1); |
66 | |
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; |
71 | |
72 | //Mark the colors of vertices adjacent to current. |
73 | //i can be the value for marking since i increases successively |
74 | for (boost::tie(v,vend) = adjacent_vertices(current, G); v != vend; ++v) |
75 | mark[get(color,*v)] = i; |
76 | |
77 | //Next step is to assign the smallest un-marked color |
78 | //to the current vertex. |
79 | size_type j = 0; |
80 | |
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 |
84 | //neighbors. |
85 | while ( j < max_color && mark[j] == i ) |
86 | ++j; |
87 | |
88 | if ( j == max_color ) //All colors are used up. Add one more color |
89 | ++max_color; |
90 | |
91 | //At this point, j is the smallest possible color |
92 | put(color, current, j); //Save the color of vertex current |
93 | } |
94 | |
95 | return max_color; |
96 | } |
97 | |
98 | template<class VertexListGraph, class ColorMap> |
99 | typename property_traits<ColorMap>::value_type |
100 | sequential_vertex_coloring(const VertexListGraph& G, ColorMap color) |
101 | { |
102 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor |
103 | vertex_descriptor; |
104 | typedef typename graph_traits<VertexListGraph>::vertex_iterator |
105 | vertex_iterator; |
106 | |
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); |
110 | #else |
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++); |
114 | #endif |
115 | return sequential_vertex_coloring |
116 | (G, |
117 | make_iterator_property_map |
118 | (order.begin(), identity_property_map(), |
119 | graph_traits<VertexListGraph>::null_vertex()), |
120 | color); |
121 | } |
122 | } |
123 | |
124 | #endif |
125 | |