1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>Boost Graph Library: Sequential Vertex Coloring</title>
</head>
<body>
<IMG SRC="../../../boost.png"
ALT="C++ Boost" width="277" height="86">
<h1><img src="figs/python.gif" alt="(Python)"/><tt>sequential_vertex_coloring</tt></h1>
<p>
<pre>
template<class VertexListGraph, class OrderPA, class ColorMap>
typename property_traits<ColorMap>::value_type
sequential_vertex_coloring(const VertexListGraph& g, OrderPA order,
ColorMap color);
template<class VertexListGraph, class ColorMap>
typename property_traits<ColorMap>::value_type
sequential_vertex_coloring(const VertexListGraph& g, ColorMap color);
</pre>
<p>Computes a <a href="graph_coloring.html">vertex coloring</a> for
the vertices in the graph, using a simple algorithm [<a
href="bibliography.html#coleman83">59</a>]. Given vertices
ordered v<sub>1</sub>, v<sub>2</sub>, ... , v<sub>n</sub>, for k = 1,
2, ..., n the algorithm assigns v<sub>k</sub> to the smallest possible
color. The algorithm does not guarantee an optimum coloring.
<p>Here is the coloring that would be produced on a graph given the
vertex ordering A, B, C, D, E.
<p><img src="figs/sequential_vertex_coloring.png">,
<h3>Where Defined</h3>
<a href="../../../boost/graph/sequential_vertex_coloring.hpp"><tt>boost/graph/sequential_vertex_coloring.hpp</tt></a>
<h3>Parameters</h3>
IN: <tt>const Graph& g</tt>
<blockquote>
The graph object on which the algorithm will be applied. The type
<tt>Graph</tt> must be a model of <a
href="VertexListGraph.html">Vertex List Graph</a> and <a
href="AdjacencyGraph.html">Adjacency Graph</a>.<br>
<b>Python</b>: The parameter is named <tt>graph</tt>.
</blockquote>
OUT: <tt>ColorMap color</tt>
<blockquote>
This property map records the colors of each vertex. It must be a
model of
<a href="../../property_map/WritablePropertyMap.html">Writeable
Property Map</a> whose key type is the same as the vertex descriptor
type of the graph and whose value type is an integral type that can
store all values of the graph's <tt>vertices_size_type</tt>.<br>
<b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.
</blockquote>
IN: <tt>OrderPA order</tt>
<blockquote>
A mapping from integers in the range <em>[0, num_vertices(g))</em>
to the vertices of the graph.<br>
<b>Default:</b> A property map ordering the vertices in the same way
they are ordered by <tt>vertices(g)</tt>.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
<h3>Complexity</h3>
The time complexity is <em>O(V(d+k))</em>, where <em>V</em> is the
number of vertices, <em>d</em> is the maximum degree of the vertices
in the graph, and <em>k</em> is the number of colors used.
<h3>Example</h3>
<pre>
typedef adjacency_list<listS, vecS, undirectedS> Graph;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef property_map<Graph, vertex_index_t>::const_type vertex_index_map;
typedef std::pair<int, int> Edge;
enum nodes {A, B, C, D, E, n};
Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A),
Edge(E, B) };
int m = sizeof(edge_array) / sizeof(Edge);
Graph g(edge_array, edge_array + m, n);
<em>// Test with the normal order</em>
std::vector<vertices_size_type> color_vec(num_vertices(g));
iterator_property_map<vertices_size_type*, vertex_index_map>
color(&color_vec.front(), get(vertex_index, g));
<b>vertices_size_type num_colors = sequential_vertex_coloring(g, color);</b>
</pre>
<hr>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 1997-2004</TD><TD>
<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)<br>
<A HREF="../../../people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor -at- cs.indiana.edu)</A>)
</TD></TR></TABLE>
</body>
</html>
|
