ceph/src/boost/libs/graph/doc/graph_coloring.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine  2000
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Graph Coloring Example</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18 <H1>Graph Coloring</H1>
  19
  20 The graph (or vertex) coloring problem, which involves assigning
  21 colors to vertices in a graph such that adjacenct vertices have
  22 distinct colors, arises in a number of scientific and engineering
  23 applications such as scheduling&nbsp;, register allocation&nbsp;,
  24 optimization&nbsp; and parallel numerical computation.
  25
  26 <P>
  27 Mathmatically, a proper vertex coloring of an undirected graph
  28 <i>G=(V,E)</i> is a map <i>c: V -> S</i> such that <i>c(u) != c(v)</i>
  29 whenever there exists an edge <i>(u,v)</i> in <i>G</i>. The elements
  30 of set <i>S</i> are called the available colors. The problem is often
  31 to determine the minimum cardinality (the number of colors) of
  32 <i>S</i> for a given graph <i>G</i> or to ask whether it is able to
  33 color graph <i>G</i> with a certain number of colors. For example, how
  34 many color do we need to color the United States on a map in such a
  35 way that adjacent states have different color? A compiler needs to
  36 decide whether variables and temporaries could be allocated in fixed
  37 number of registers at some point.  If a target machine has <i>K</i>
  38 registers, can a particular interference graph be colored with
  39 <i>K</i> colors? (Each vertex in the interference graph represents a
  40 temporary value; each edge indicates a pair of temporaries that cannot
  41 be assigned to the same register.)
  42
  43 <P>
  44 Another example is in the estimation of sparse Jacobian matrix by
  45 differences in large scale nonlinear problems in optimization and
  46 differential equations. Given a nonlinear function <i>F</i>, the
  47 estimation of Jacobian matrix <i>J</i> can be obtained by estimating
  48 <i>Jd</i> for suitable choices of vector <i>d</i>. Curtis, Powell and
  49 Reid&nbsp;[<a href="bibliography.html#curtis74:_jacob">9</a>] observed that a group of columns of <i>J</i> can be
  50 determined by one evaluation of <i>Jd</i> if no two columns in this
  51 group have a nonzero in the same row position.  Therefore, a question
  52 is emerged: what is the number of function evaluations need to compute
  53 approximate Jacobian matrix?  As a matter of fact this question is the
  54 same as to compute the minimum numbers of colors for coloring a graph
  55 if we construct the graph in the following matter: A vertex represents
  56 a column of <i>J</i> and there is an edge if and only if the two
  57 column have a nonzero in the same row position.
  58
  59 <P>
  60 However, coloring a general graph with the minimum number of colors
  61 (the cardinality of set <i>S</i>) is known to be an NP-complete
  62 problem&nbsp;[<a
  63 href="bibliography.html#garey79:computers-and-intractability">30</a>].
  64 One often relies on heuristics to find a solution. A widely-used
  65 general greedy based approach is starting from an ordered vertex
  66 enumeration <i>v<sub>1</sub>, ..., v<sub>n</sub></i> of <i>G</i>, to
  67 assign <i>v<sub>i</sub></i> to the smallest possible color for
  68 <i>i</i> from <i>1</i> to <i>n</i>.  In section <a
  69 href="constructing_algorithms.html">Constructing graph
  70 algorithms with BGL</a> we have shown how to write this algorithm in
  71 the generic programming paradigm. However, the ordering of the
  72 vertices dramatically affects the coloring.  The arbitrary order may
  73 perform very poorly while another ordering may produces an optimal
  74 coloring.  Several ordering algorithms have been studied to help the
  75 greedy coloring heuristics including largest-first ordering,
  76 smallest-last ordering and incidence degree ordering.
  77
  78 <P>
  79 In the BGL framework,  the process of constructing/prototyping such a
  80 ordering is fairly easy because  writing such a ordering  follows the
  81 algorithm  description   closely.  As  an  example,   we  present  the
  82 smallest-last ordering algorithm.
  83
  84 <P>
  85 The basic idea of the smallest-last ordering&nbsp;[<a
  86 href="bibliography.html#matula72:_graph_theory_computing">29</a>] is
  87 as follows: Assuming that the vertices <i>v<sub>k+1</sub>, ...,
  88 v<sub>n</sub></i> have been selected, choose <i>v<sub>k</sub></i> so
  89 that the degree of <i>v<sub>k</sub></i> in the subgraph induced by
  90 <i>V - {v<sub>k+1</sub>, ..., v<sub>n</sub>}</i> is minimal.
  91
  92 <P>
  93 The algorithm uses a bucket sorter for the vertices in the graph where
  94 bucket is the degree. Two vertex property maps, <TT>degree</TT> and
  95 <TT>marker</TT>,  are used  in the  algorithm.  The former  is to  store
  96 degree of  every vertex while the  latter is to mark  whether a vertex
  97 has been ordered or processed during traversing adjacent vertices. The
  98 ordering is stored in the <TT>order</TT>. The algorithm is as follows:
  99
 100 <UL>
 101 <LI>put all vertices in the bucket sorter
 102 </LI>
 103 <LI>find the vertex <tt>node</tt> with smallest degree in the bucket sorter
 104 </LI>
 105 <LI>number <tt>node</tt> and traverse through its adjacent vertices to
 106  update its degree and the position in the bucket sorter.
 107 </LI>
 108 <LI>go to the step 2 until all vertices are numbered.
 109 </LI>
 110 </UL>
 111
 112 <P>
 113 <PRE>
 114 namespace boost {
 115   template &lt;class VertexListGraph, class Order, class Degree,
 116             class Marker, class BucketSorter&gt;
 117   void
 118   smallest_last_ordering(const VertexListGraph&amp; G, Order order,
 119                          Degree degree, Marker marker,
 120                          BucketSorter&amp; degree_buckets) {
 121     typedef typename graph_traits&lt;VertexListGraph&gt; GraphTraits;
 122
 123     typedef typename GraphTraits::vertex_descriptor Vertex;
 124     //typedef typename GraphTraits::size_type size_type;
 125     typedef size_t size_type;
 126
 127     const size_type num = num_vertices(G);
 128
 129     typename GraphTraits::vertex_iterator v, vend;
 130     for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
 131       put(marker, *v, num);
 132       put(degree, *v, out_degree(*v, G));
 133       degree_buckets.push(*v);
 134     }
 135
 136     size_type minimum_degree = 1;
 137     size_type current_order = num - 1;
 138
 139     while ( 1 ) {
 140       typedef typename BucketSorter::stack MDStack;
 141       MDStack minimum_degree_stack = degree_buckets[minimum_degree];
 142       while (minimum_degree_stack.empty())
 143         minimum_degree_stack = degree_buckets[++minimum_degree];
 144
 145       Vertex node = minimum_degree_stack.top();
 146       put(order, current_order, node);
 147
 148       if ( current_order == 0 ) //find all vertices
 149         break;
 150
 151       minimum_degree_stack.pop();
 152       put(marker, node, 0); //node has been ordered.
 153
 154       typename GraphTraits::adjacency_iterator v, vend;
 155       for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
 156
 157         if ( get(marker, *v) &gt; current_order ) { //*v is unordered vertex
 158           put(marker, *v, current_order);   //mark the columns adjacent to node
 159
 160           //It is possible minimum degree goes down
 161           //Here we keep tracking it.
 162           put(degree, *v, get(degree, *v) - 1);
 163           minimum_degree = std::min(minimum_degree, get(degree, *v));
 164
 165           //update the position of *v in the bucket sorter
 166           degree_buckets.update(*v);
 167         }
 168
 169       current_order--;
 170     }
 171     //at this point, get(order, i) == vertex(i, g);
 172   }
 173 } // namespace boost
 174 </PRE>
 175
 176 <br>
 177 <HR>
 178 <TABLE>
 179 <TR valign=top>
 180 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 181 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 182 Indiana University (<A
 183 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 184 <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
 185 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 186 Indiana University (<A
 187 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 188 </TD></TR></TABLE>
 189
 190 </BODY>
 191 </HTML>