ceph/src/boost/libs/graph_parallel/doc/boman_et_al_graph_coloring.rst

   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]