]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Copyright (C) 2004-2008 The Trustees of Indiana University. |
2 | Use, modification and distribution is subject to the Boost Software | |
3 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
4 | http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | ================================= | |
7 | |Logo| Boman et al graph coloring | |
8 | ================================= | |
9 | ||
10 | :: | |
11 | ||
12 | namespace graph { | |
13 | template<typename DistributedGraph, typename ColorMap> | |
14 | typename property_traits<ColorMap>::value_type | |
15 | boman_et_al_graph_coloring | |
16 | (const DistributedGraph& g, | |
17 | ColorMap color, | |
18 | typename graph_traits<DistributedGraph>::vertices_size_type s = 100); | |
19 | ||
20 | template<typename DistributedGraph, typename ColorMap, typename ChooseColor> | |
21 | typename property_traits<ColorMap>::value_type | |
22 | boman_et_al_graph_coloring | |
23 | (const DistributedGraph& g, | |
24 | ColorMap color, | |
25 | typename graph_traits<DistributedGraph>::vertices_size_type s, | |
26 | ChooseColor choose_color); | |
27 | ||
28 | template<typename DistributedGraph, typename ColorMap, typename ChooseColor, | |
29 | typename VertexOrdering> | |
30 | typename property_traits<ColorMap>::value_type | |
31 | boman_et_al_graph_coloring | |
32 | (const DistributedGraph& g, ColorMap color, | |
33 | typename graph_traits<DistributedGraph>::vertices_size_type s, | |
34 | ChooseColor choose_color, VertexOrdering ordering); | |
35 | ||
36 | template<typename DistributedGraph, typename ColorMap, typename ChooseColor, | |
37 | typename VertexOrdering, typename VertexIndexMap> | |
38 | typename property_traits<ColorMap>::value_type | |
39 | boman_et_al_graph_coloring | |
40 | (const DistributedGraph& g, | |
41 | ColorMap color, | |
42 | typename graph_traits<DistributedGraph>::vertices_size_type s, | |
43 | ChooseColor choose_color, | |
44 | VertexOrdering ordering, VertexIndexMap vertex_index); | |
45 | } | |
46 | ||
47 | The ``boman_et_al_graph_coloring`` function colors the vertices of an | |
48 | undirected, distributed graph such that no two adjacent vertices have | |
49 | the same color. All of the vertices of a given color form an | |
50 | independent set in the graph. Graph coloring has been used to solve | |
51 | various problems, including register allocation in compilers, | |
52 | optimization problems, and scheduling problems. | |
53 | ||
54 | .. image:: ../vertex_coloring.png | |
55 | :width: 462 | |
56 | :height: 269 | |
57 | :alt: Vertex coloring example | |
58 | :align: right | |
59 | ||
60 | The problem of coloring a graph with the fewest possible number of | |
61 | colors is NP-complete, so many algorithms (including the one | |
62 | implemented here) are heuristic algorithms that try to minimize the | |
63 | number of colors but are not guaranteed to provide an optimal | |
64 | solution. This algorithm [BBC05]_ is similar to the | |
65 | ``sequential_vertex_coloring`` algorithm, that iterates through the | |
66 | vertices once and selects the lowest-numbered color that the current | |
67 | vertex can have. The coloring and the number of colors is therefore | |
68 | related to the ordering of the vertices in the sequential case. | |
69 | ||
70 | The distributed ``boman_et_al_graph_coloring`` algorithm will produce | |
71 | different colorings depending on the ordering and distribution of the | |
72 | vertices and the number of parallel processes cooperating to perform | |
73 | the coloring. | |
74 | ||
75 | The algorithm returns the number of colors ``num_colors`` used to | |
76 | color the graph. | |
77 | ||
78 | .. contents:: | |
79 | ||
80 | Where Defined | |
81 | ~~~~~~~~~~~~~ | |
82 | <``boost/graph/distributed/boman_et_al_graph_coloring.hpp``> | |
83 | ||
84 | Parameters | |
85 | ~~~~~~~~~~ | |
86 | ||
87 | IN: ``Graph& g`` | |
88 | The graph type must be a model of `Distributed Vertex List Graph`_ and | |
89 | `Distributed Edge List Graph`_. | |
90 | ||
91 | ||
92 | ||
93 | UTIL/OUT: ``ColorMap color`` | |
94 | Stores the color of each vertex, which will be a value in the range | |
95 | [0, ``num_colors``). The type ``ColorMap`` must model the | |
96 | `Read/Write Property Map`_ concept and must be a `distributed | |
97 | property map`_. | |
98 | ||
99 | ||
100 | ||
101 | IN: ``vertices_size_type s`` | |
102 | The number of vertices to color within each superstep. After | |
103 | ``s`` vertices have been colored, the colors of boundary vertices | |
104 | will be sent to their out-of-process neighbors. Smaller values | |
105 | communicate more often but may reduce the risk of conflicts, | |
106 | whereas larger values do more work in between communication steps | |
107 | but may create many conflicts. | |
108 | ||
109 | **Default**: 100 | |
110 | ||
111 | IN: ``ChooseColor choose_color`` | |
112 | A function object that chooses the color for a vertex given the | |
113 | colors of its neighbors. The function object will be passed a vector | |
114 | of values (``marked``) and a ``marked_true`` value, and should | |
115 | return a ``color`` value such that ``color >= marked.size()`` or | |
116 | ``marked[color] != marked_true``. | |
117 | ||
118 | **Default**: | |
119 | ``boost::graph::distributed::first_fit_color<color_type>()``, where | |
120 | ``color_type`` is the value type of the ``ColorMap`` property map. | |
121 | ||
122 | IN: ``VertexOrdering ordering`` | |
123 | A binary predicate function object that provides total ordering on | |
124 | the vertices in the graph. Whenever a conflict arises, only one of | |
125 | the processes involved will recolor the vertex in the next round, | |
126 | and this ordering determines which vertex should be considered | |
127 | conflicting (its owning process will then handle the | |
128 | conflict). Ideally, this predicate should order vertices so that | |
129 | conflicting vertices will be spread uniformly across | |
130 | processes. However, this predicate *must* resolve the same way on | |
131 | both processors. | |
132 | ||
133 | **Default**: *unspecified* | |
134 | ||
135 | IN: ``VertexIndexMap index`` | |
136 | A mapping from vertex descriptors to indices in the range *[0, | |
137 | num_vertices(g))*. This must be a `Readable Property Map`_ whose | |
138 | key type is a vertex descriptor and whose value type is an integral | |
139 | type, typically the ``vertices_size_type`` of the graph. | |
140 | ||
141 | **Default:** ``get(vertex_index, g)`` | |
142 | ||
143 | Complexity | |
144 | ~~~~~~~~~~ | |
145 | The complexity of this algorithm is hard to characterize, | |
146 | because it depends greatly on the number of *conflicts* that occur | |
147 | during the algorithm. A conflict occurs when a *boundary vertex* | |
148 | (i.e., a vertex that is adjacent to a vertex stored on a different | |
149 | processor) is given the same color is a boundary vertex adjacency to | |
150 | it (but on another processor). Conflicting vertices must be assigned | |
151 | new colors, requiring additional work and communication. The work | |
152 | involved in reassigning a color for a conflicting vertex is *O(d)*, | |
153 | where *d* is the degree of the vertex and *O(1)* messages of *O(1)* | |
154 | size are needed to resolve the conflict. Note that the number of | |
155 | conflicts grows with (1) the number of processes and (2) the number | |
156 | of inter-process edges. | |
157 | ||
158 | Performance | |
159 | ~~~~~~~~~~~ | |
160 | ||
161 | The performance of this implementation of Bomen et al's graph coloring | |
162 | algorithm is illustrated by the following charts. Scaling and | |
163 | performance is reasonable for all of the graphs we have tried. | |
164 | ||
165 | .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&cluster=Odin&columns=11 | |
166 | :align: left | |
167 | .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&cluster=Odin&columns=11&speedup=1 | |
168 | ||
169 | .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&cluster=Odin&columns=11 | |
170 | :align: left | |
171 | .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&cluster=Odin&columns=11&speedup=1 | |
172 | ||
173 | ----------------------------------------------------------------------------- | |
174 | ||
175 | Copyright (C) 2005 The Trustees of Indiana University. | |
176 | ||
177 | Authors: Douglas Gregor and Andrew Lumsdaine | |
178 | ||
179 | .. |Logo| image:: pbgl-logo.png | |
180 | :align: middle | |
181 | :alt: Parallel BGL | |
182 | :target: http://www.osl.iu.edu/research/pbgl | |
183 | ||
184 | .. _Distributed Vertex List Graph: DistributedVertexListGraph.html | |
185 | .. _Distributed Edge List Graph: DistributedEdgeListGraph.html | |
186 | .. _Distributed property map: distributed_property_map.html | |
187 | .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html | |
188 | .. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html | |
189 | .. [BBC05] Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw | |
190 | H. Gebremedhin, and Fredrik Manne. A Scalable Parallel Graph Coloring | |
191 | Algorithm for Distributed Memory Computers. [preprint] |