123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191 |
- <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 (boost::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 (boost::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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|