| <HTML> |
| <!-- |
| Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| --> |
| <Head> |
| <Title>Graph Coloring Example</Title> |
| <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
| ALINK="#ff0000"> |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| |
| <BR Clear> |
| |
| <H1>Graph Coloring</H1> |
| |
| The graph (or vertex) coloring problem, which involves assigning |
| colors to vertices in a graph such that adjacenct vertices have |
| distinct colors, arises in a number of scientific and engineering |
| applications such as scheduling , register allocation , |
| optimization and parallel numerical computation. |
| |
| <P> |
| Mathmatically, a proper vertex coloring of an undirected graph |
| <i>G=(V,E)</i> is a map <i>c: V -> S</i> such that <i>c(u) != c(v)</i> |
| whenever there exists an edge <i>(u,v)</i> in <i>G</i>. The elements |
| of set <i>S</i> are called the available colors. The problem is often |
| to determine the minimum cardinality (the number of colors) of |
| <i>S</i> for a given graph <i>G</i> or to ask whether it is able to |
| color graph <i>G</i> with a certain number of colors. For example, how |
| many color do we need to color the United States on a map in such a |
| way that adjacent states have different color? A compiler needs to |
| decide whether variables and temporaries could be allocated in fixed |
| number of registers at some point. If a target machine has <i>K</i> |
| registers, can a particular interference graph be colored with |
| <i>K</i> colors? (Each vertex in the interference graph represents a |
| temporary value; each edge indicates a pair of temporaries that cannot |
| be assigned to the same register.) |
| |
| <P> |
| Another example is in the estimation of sparse Jacobian matrix by |
| differences in large scale nonlinear problems in optimization and |
| differential equations. Given a nonlinear function <i>F</i>, the |
| estimation of Jacobian matrix <i>J</i> can be obtained by estimating |
| <i>Jd</i> for suitable choices of vector <i>d</i>. Curtis, Powell and |
| Reid [<a href="bibliography.html#curtis74:_jacob">9</a>] observed that a group of columns of <i>J</i> can be |
| determined by one evaluation of <i>Jd</i> if no two columns in this |
| group have a nonzero in the same row position. Therefore, a question |
| is emerged: what is the number of function evaluations need to compute |
| approximate Jacobian matrix? As a matter of fact this question is the |
| same as to compute the minimum numbers of colors for coloring a graph |
| if we construct the graph in the following matter: A vertex represents |
| a column of <i>J</i> and there is an edge if and only if the two |
| column have a nonzero in the same row position. |
| |
| <P> |
| However, coloring a general graph with the minimum number of colors |
| (the cardinality of set <i>S</i>) is known to be an NP-complete |
| problem [<a |
| href="bibliography.html#garey79:computers-and-intractability">30</a>]. |
| One often relies on heuristics to find a solution. A widely-used |
| general greedy based approach is starting from an ordered vertex |
| enumeration <i>v<sub>1</sub>, ..., v<sub>n</sub></i> of <i>G</i>, to |
| assign <i>v<sub>i</sub></i> to the smallest possible color for |
| <i>i</i> from <i>1</i> to <i>n</i>. In section <a |
| href="constructing_algorithms.html">Constructing graph |
| algorithms with BGL</a> we have shown how to write this algorithm in |
| the generic programming paradigm. However, the ordering of the |
| vertices dramatically affects the coloring. The arbitrary order may |
| perform very poorly while another ordering may produces an optimal |
| coloring. Several ordering algorithms have been studied to help the |
| greedy coloring heuristics including largest-first ordering, |
| smallest-last ordering and incidence degree ordering. |
| |
| <P> |
| In the BGL framework, the process of constructing/prototyping such a |
| ordering is fairly easy because writing such a ordering follows the |
| algorithm description closely. As an example, we present the |
| smallest-last ordering algorithm. |
| |
| <P> |
| The basic idea of the smallest-last ordering [<a |
| href="bibliography.html#matula72:_graph_theory_computing">29</a>] is |
| as follows: Assuming that the vertices <i>v<sub>k+1</sub>, ..., |
| v<sub>n</sub></i> have been selected, choose <i>v<sub>k</sub></i> so |
| that the degree of <i>v<sub>k</sub></i> in the subgraph induced by |
| <i>V - {v<sub>k+1</sub>, ..., v<sub>n</sub>}</i> is minimal. |
| |
| <P> |
| The algorithm uses a bucket sorter for the vertices in the graph where |
| bucket is the degree. Two vertex property maps, <TT>degree</TT> and |
| <TT>marker</TT>, are used in the algorithm. The former is to store |
| degree of every vertex while the latter is to mark whether a vertex |
| has been ordered or processed during traversing adjacent vertices. The |
| ordering is stored in the <TT>order</TT>. The algorithm is as follows: |
| |
| <UL> |
| <LI>put all vertices in the bucket sorter |
| </LI> |
| <LI>find the vertex <tt>node</tt> with smallest degree in the bucket sorter |
| </LI> |
| <LI>number <tt>node</tt> and traverse through its adjacent vertices to |
| update its degree and the position in the bucket sorter. |
| </LI> |
| <LI>go to the step 2 until all vertices are numbered. |
| </LI> |
| </UL> |
| |
| <P> |
| <PRE> |
| namespace boost { |
| template <class VertexListGraph, class Order, class Degree, |
| class Marker, class BucketSorter> |
| void |
| smallest_last_ordering(const VertexListGraph& G, Order order, |
| Degree degree, Marker marker, |
| BucketSorter& degree_buckets) { |
| typedef typename graph_traits<VertexListGraph> GraphTraits; |
| |
| typedef typename GraphTraits::vertex_descriptor Vertex; |
| //typedef typename GraphTraits::size_type size_type; |
| typedef size_t size_type; |
| |
| const size_type num = num_vertices(G); |
| |
| typename GraphTraits::vertex_iterator v, vend; |
| for (tie(v, vend) = vertices(G); v != vend; ++v) { |
| put(marker, *v, num); |
| put(degree, *v, out_degree(*v, G)); |
| degree_buckets.push(*v); |
| } |
| |
| size_type minimum_degree = 1; |
| size_type current_order = num - 1; |
| |
| while ( 1 ) { |
| typedef typename BucketSorter::stack MDStack; |
| MDStack minimum_degree_stack = degree_buckets[minimum_degree]; |
| while (minimum_degree_stack.empty()) |
| minimum_degree_stack = degree_buckets[++minimum_degree]; |
| |
| Vertex node = minimum_degree_stack.top(); |
| put(order, current_order, node); |
| |
| if ( current_order == 0 ) //find all vertices |
| break; |
| |
| minimum_degree_stack.pop(); |
| put(marker, node, 0); //node has been ordered. |
| |
| typename GraphTraits::adjacency_iterator v, vend; |
| for (tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v) |
| |
| if ( get(marker, *v) > current_order ) { //*v is unordered vertex |
| put(marker, *v, current_order); //mark the columns adjacent to node |
| |
| //It is possible minimum degree goes down |
| //Here we keep tracking it. |
| put(degree, *v, get(degree, *v) - 1); |
| minimum_degree = std::min(minimum_degree, get(degree, *v)); |
| |
| //update the position of *v in the bucket sorter |
| degree_buckets.update(*v); |
| } |
| |
| current_order--; |
| } |
| //at this point, get(order, i) == vertex(i, g); |
| } |
| } // namespace boost |
| </PRE> |
| |
| <br> |
| <HR> |
| <TABLE> |
| <TR valign=top> |
| <TD nowrap>Copyright © 2000-2001</TD><TD> |
| <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, |
| Indiana University (<A |
| HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> |
| <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> |
| <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>) |
| </TD></TR></TABLE> |
| |
| </BODY> |
| </HTML> |