C++ Boost

Graph Coloring

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.

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 v1, ..., vn of G, to assign vi to the smallest possible color for i from 1 to n. In section Constructing graph algorithms with BGL 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.

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 vk+1, ..., vn have been selected, choose vk so that the degree of vk in the subgraph induced by V - {vk+1, ..., vn} is minimal.

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:

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& bucket_sorter) {
    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 ([email protected])
Lie-Quan Lee, Indiana University ([email protected])
Andrew Lumsdaine, Indiana University ([email protected])