ceph/src/boost/libs/graph/doc/constructing_algorithms.html

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