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>Boost Graph Library: Constructing Graph Algorithms</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>Constructing graph algorithms with BGL</H1> 19 20<P> 21The <I>main</I> goal of BGL is not to provide a nice graph class, or 22to provide a comprehensive set of reusable graph algorithms (though 23these are goals). The main goal of BGL is to encourage others to 24write reusable graph algorithms. By reusable we mean maximally 25reusable. Generic programming is a methodology for making algorithms 26maximally reusable, and in this section we will discuss how to apply 27generic programming to constructing graph algorithms. 28 29<P> 30To illustrate the generic programming process we will step though the 31construction of a graph coloring algorithm. The graph coloring problem 32(or more specifically, the vertex coloring problem) is to label each 33vertex in a graph <i>G</i> with a color such that no two adjacent 34vertices are labeled with the same color and such that the minimum 35number of colors are used. In general, the graph coloring problem is 36NP-complete, and therefore it is impossible to find an optimal 37solution in a reasonable amount of time. However, there are many 38algorithms that use heuristics to find colorings that are close to the 39minimum. 40 41<P> 42The particular algorithm we present here is based on the linear time 43<TT>SEQ</TT> subroutine that is used in the estimation of sparse 44Jacobian and Hessian matrices [<A 45HREF="bibliography.html#curtis74:_jacob">9</A>,<A 46HREF="bibliography.html#coleman84:_estim_jacob">7</A>,<A 47HREF="bibliography.html#coleman85:_algor">6</A>]. This algorithm 48visits all of the vertices in the graph according to the order defined 49by the input order. At each vertex the algorithm marks the colors of 50the adjacent vertices, and then chooses the smallest unmarked color 51for the color of the current vertex. If all of the colors are already 52marked, a new color is created. A color is considered marked if its 53mark number is equal to the current vertex number. This saves the 54trouble of having to reset the marks for each vertex. The 55effectiveness of this algorithm is highly dependent on the input 56vertex order. There are several ordering algorithms, including the 57<I>largest-first</I> [<A HREF="bibliography.html#welsch67">31</A>], 58<I>smallest-last</I> [<a 59href="bibliography.html#matula72:_graph_theory_computing">29</a>], and 60<I>incidence degree</I> [<a 61href="bibliography.html#brelaz79:_new">32</a>] algorithms, which 62improve the effectiveness of this coloring algorithm. 63 64<P> 65The first decision to make when constructing a generic graph algorithm 66is to decide what graph operations are necessary for implementing the 67algorithm, and which graph concepts the operations map to. In this 68algorithm we will need to traverse through all of the vertices to 69intialize the vertex colors. We also need to access the adjacent 70vertices. Therefore, we will choose the <a 71href="./VertexListGraph.html">VertexListGraph</a> concept because it 72is the minimum concept that includes these operations. The graph type 73will be parameterized in the template function for this algorithm. We 74do not restrict the graph type to a particular graph class, such as 75the BGL <a href="./adjacency_list.html"><TT>adjacency_list</TT></a>, 76for this would drastically limit the reusability of the algorithm (as 77most algorithms written to date are). We do restrict the graph type to 78those types that model <a 79href="./VertexListGraph.html">VertexListGraph</a>. This is enforced by 80the use of those graph operations in the algorithm, and furthermore by 81our explicit requirement added as a concept check with 82<TT>BOOST_CONCEPT_ASSERT()</TT> (see Section <A 83HREF="../../concept_check/concept_check.htm">Concept 84Checking</A> for more details about concept checking). 85 86<P> 87Next we need to think about what vertex or edge properties will be 88used in the algorithm. In this case, the only property is vertex 89color. The most flexible way to specify access to vertex color is to 90use the propery map interface. This gives the user of the 91algorithm the ability to decide how they want to store the properties. 92Since we will need to both read and write the colors we specify the 93requirements as <a 94href="../../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a>. The 95<TT>key_type</TT> of the color map must be the 96<TT>vertex_descriptor</TT> from the graph, and the <TT>value_type</TT> 97must be some kind of integer. We also specify the interface for the 98<TT>order</TT> parameter as a property map, in this case a <a 99href="../../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a>. For 100order, the <TT>key_type</TT> is an integer offset and the 101<TT>value_type</TT> is a <TT>vertex_descriptor</TT>. Again we enforce 102these requirements with concept checks. The return value of this 103algorithm is the number of colors that were needed to color the graph, 104hence the return type of the function is the graph's 105<TT>vertices_size_type</TT>. The following code shows the interface for our 106graph algorithm as a template function, the concept checks, and some 107typedefs. The implementation is straightforward, the only step not 108discussed above is the color initialization step, where we set the 109color of all the vertices to "uncolored." 110 111<P> 112<PRE> 113namespace boost { 114 template <class VertexListGraph, class Order, class Color> 115 typename graph_traits<VertexListGraph>::vertices_size_type 116 sequential_vertex_color_ting(const VertexListGraph& G, 117 Order order, Color color) 118 { 119 typedef graph_traits<VertexListGraph> GraphTraits; 120 typedef typename GraphTraits::vertex_descriptor vertex_descriptor; 121 typedef typename GraphTraits::vertices_size_type size_type; 122 typedef typename property_traits<Color>::value_type ColorType; 123 typedef typename property_traits<Order>::value_type OrderType; 124 125 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<VertexListGraph> )); 126 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Color, vertex_descriptor> )); 127 BOOST_CONCEPT_ASSERT(( IntegerConcept<ColorType> )); 128 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<Order, size_type> )); 129 BOOST_STATIC_ASSERT((is_same<OrderType, vertex_descriptor>::value)); 130 131 size_type max_color = 0; 132 const size_type V = num_vertices(G); 133 std::vector<size_type> 134 mark(V, numeric_limits_max(max_color)); 135 136 typename GraphTraits::vertex_iterator v, vend; 137 for (boost::tie(v, vend) = vertices(G); v != vend; ++v) 138 color[*v] = V - 1; // which means "not colored" 139 140 for (size_type i = 0; i < V; i++) { 141 vertex_descriptor current = order[i]; 142 143 // mark all the colors of the adjacent vertices 144 typename GraphTraits::adjacency_iterator ai, aend; 145 for (boost::tie(ai, aend) = adjacent_vertices(current, G); ai != aend; ++ai) 146 mark[color[*ai]] = i; 147 148 // find the smallest color unused by the adjacent vertices 149 size_type smallest_color = 0; 150 while (smallest_color < max_color && mark[smallest_color] == i) 151 ++smallest_color; 152 153 // if all the colors are used up, increase the number of colors 154 if (smallest_color == max_color) 155 ++max_color; 156 157 color[current] = smallest_color; 158 } 159 return max_color; 160 } 161} // namespace boost 162</PRE> 163 164<P> 165 166 167 168<br> 169<HR> 170<TABLE> 171<TR valign=top> 172<TD nowrap>Copyright © 2000-2001</TD><TD> 173<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 174Indiana University (<A 175HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 176<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> 177<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 178Indiana University (<A 179HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 180</TD></TR></TABLE> 181 182</BODY> 183</HTML> 184
