author | hgs |
Thu, 14 Oct 2010 14:15:50 +0530 | |
changeset 72 | 403e7f6ed6c5 |
parent 0 | e4d67989cc36 |
permissions | -rw-r--r-- |
0
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
1 |
//======================================================================= |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
2 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
3 |
// Copyright 2004 The Trustees of Indiana University |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
4 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
5 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
7 |
// accompanying file LICENSE_1_0.txt or copy at |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
8 |
// http://www.boost.org/LICENSE_1_0.txt) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
9 |
//======================================================================= |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
10 |
#ifndef BOOST_GRAPH_SEQUENTIAL_VERTEX_COLORING_HPP |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
11 |
#define BOOST_GRAPH_SEQUENTIAL_VERTEX_COLORING_HPP |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
12 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
13 |
#include <vector> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
14 |
#include <boost/graph/graph_traits.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
15 |
#include <boost/tuple/tuple.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
16 |
#include <boost/property_map.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
17 |
#include <boost/limits.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
18 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
19 |
#ifdef BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
20 |
# include <iterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
21 |
#endif |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
22 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
23 |
/* This algorithm is to find coloring of a graph |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
24 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
25 |
Algorithm: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
26 |
Let G = (V,E) be a graph with vertices (somehow) ordered v_1, v_2, ..., |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
27 |
v_n. For k = 1, 2, ..., n the sequential algorithm assigns v_k to the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
28 |
smallest possible color. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
29 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
30 |
Reference: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
31 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
32 |
Thomas F. Coleman and Jorge J. More, Estimation of sparse Jacobian |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
33 |
matrices and graph coloring problems. J. Numer. Anal. V20, P187-209, 1983 |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
34 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
35 |
v_k is stored as o[k] here. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
36 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
37 |
The color of the vertex v will be stored in color[v]. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
38 |
i.e., vertex v belongs to coloring color[v] */ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
39 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
40 |
namespace boost { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
41 |
template <class VertexListGraph, class OrderPA, class ColorMap> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
42 |
typename property_traits<ColorMap>::value_type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
43 |
sequential_vertex_coloring(const VertexListGraph& G, OrderPA order, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
44 |
ColorMap color) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
45 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
46 |
typedef graph_traits<VertexListGraph> GraphTraits; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
47 |
typedef typename GraphTraits::vertex_descriptor Vertex; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
48 |
typedef typename property_traits<ColorMap>::value_type size_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
49 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
50 |
size_type max_color = 0; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
51 |
const size_type V = num_vertices(G); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
52 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
53 |
// We need to keep track of which colors are used by |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
54 |
// adjacent vertices. We do this by marking the colors |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
55 |
// that are used. The mark array contains the mark |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
56 |
// for each color. The length of mark is the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
57 |
// number of vertices since the maximum possible number of colors |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
58 |
// is the number of vertices. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
59 |
std::vector<size_type> mark(V, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
60 |
std::numeric_limits<size_type>::max BOOST_PREVENT_MACRO_SUBSTITUTION()); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
61 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
62 |
//Initialize colors |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
63 |
typename GraphTraits::vertex_iterator v, vend; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
64 |
for (tie(v, vend) = vertices(G); v != vend; ++v) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
65 |
put(color, *v, V-1); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
66 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
67 |
//Determine the color for every vertex one by one |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
68 |
for ( size_type i = 0; i < V; i++) { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
69 |
Vertex current = get(order,i); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
70 |
typename GraphTraits::adjacency_iterator v, vend; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
71 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
72 |
//Mark the colors of vertices adjacent to current. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
73 |
//i can be the value for marking since i increases successively |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
74 |
for (tie(v,vend) = adjacent_vertices(current, G); v != vend; ++v) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
75 |
mark[get(color,*v)] = i; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
76 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
77 |
//Next step is to assign the smallest un-marked color |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
78 |
//to the current vertex. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
79 |
size_type j = 0; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
80 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
81 |
//Scan through all useable colors, find the smallest possible |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
82 |
//color that is not used by neighbors. Note that if mark[j] |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
83 |
//is equal to i, color j is used by one of the current vertex's |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
84 |
//neighbors. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
85 |
while ( j < max_color && mark[j] == i ) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
86 |
++j; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
87 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
88 |
if ( j == max_color ) //All colors are used up. Add one more color |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
89 |
++max_color; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
90 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
91 |
//At this point, j is the smallest possible color |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
92 |
put(color, current, j); //Save the color of vertex current |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
93 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
94 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
95 |
return max_color; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
96 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
97 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
98 |
template<class VertexListGraph, class ColorMap> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
99 |
typename property_traits<ColorMap>::value_type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
100 |
sequential_vertex_coloring(const VertexListGraph& G, ColorMap color) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
101 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
102 |
typedef typename graph_traits<VertexListGraph>::vertex_descriptor |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
103 |
vertex_descriptor; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
104 |
typedef typename graph_traits<VertexListGraph>::vertex_iterator |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
105 |
vertex_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
106 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
107 |
std::pair<vertex_iterator, vertex_iterator> v = vertices(G); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
108 |
#ifndef BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
109 |
std::vector<vertex_descriptor> order(v.first, v.second); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
110 |
#else |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
111 |
std::vector<vertex_descriptor> order; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
112 |
order.reserve(std::distance(v.first, v.second)); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
113 |
while (v.first != v.second) order.push_back(*v.first++); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
114 |
#endif |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
115 |
return sequential_vertex_coloring |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
116 |
(G, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
117 |
make_iterator_property_map |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
118 |
(order.begin(), identity_property_map(), |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
119 |
graph_traits<VertexListGraph>::null_vertex()), |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
120 |
color); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
121 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
122 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
123 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
124 |
#endif |