...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

Mathmatically, a proper vertex coloring of an undirected graph
*G=(V,E)* is a map *c: V -> S* such that *c(u) != c(v)*
whenever there exists an edge *(u,v)* in *G*. The elements
of set *S* are called the available colors. The problem is often
to determine the minimum cardinality (the number of colors) of
*S* for a given graph *G* or to ask whether it is able to
color graph *G* 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 *K*
registers, can a particular interference graph be colored with
*K* 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.)

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 *F*, the
estimation of Jacobian matrix *J* can be obtained by estimating
*Jd* for suitable choices of vector *d*. Curtis, Powell and
Reid [9] observed that a group of columns of *J* can be
determined by one evaluation of *Jd* 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 *J* and there is an edge if and only if the two
column have a nonzero in the same row position.

However, coloring a general graph with the minimum number of colors
(the cardinality of set *S*) is known to be an NP-complete
problem [30].
One often relies on heuristics to find a solution. A widely-used
general greedy based approach is starting from an ordered vertex
enumeration *v _{1}, ..., v_{n}* of

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.

The basic idea of the smallest-last ordering [29] is
as follows: Assuming that the vertices *v _{k+1}, ...,
v_{n}* have been selected, choose

The algorithm uses a bucket sorter for the vertices in the graph where
bucket is the degree. Two vertex property maps, `degree` and
`marker`, 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 `order`. The algorithm is as follows:

- put all vertices in the bucket sorter
- find the vertex
`node`with smallest degree in the bucket sorter - number
`node`and traverse through its adjacent vertices to update its degree and the position in the bucket sorter. - go to the step 2 until all vertices are numbered.

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

Copyright © 2000-2001 |
Jeremy Siek,
Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |