Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/constructing_algorithms.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 8.1 KB
Line 
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&nbsp;[<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>&nbsp;[<A HREF="bibliography.html#welsch67">31</A>],
58<I>smallest-last</I>&nbsp;[<a
59href="bibliography.html#matula72:_graph_theory_computing">29</a>], and
60<I>incidence degree</I>&nbsp;[<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>function_requires()</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/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/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 &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    function_requires&lt; VertexListGraphConcept&lt;VertexListGraph&gt; &gt;();
126    function_requires&lt; ReadWritePropertyMapConcept&lt;Color, vertex_descriptor&gt; &gt;();
127    function_requires&lt; IntegerConcept&lt;ColorType&gt; &gt;();
128    function_requires&lt; size_type, ReadablePropertyMapConcept&lt;Order&gt; &gt;();
129    typedef typename same_type&lt;OrderType, vertex_descriptor&gt;::type req_same;
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 (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 (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="../../../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="../../../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>,
178Indiana University (<A
179HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
180</TD></TR></TABLE>
181
182</BODY>
183</HTML> 
Note: See TracBrowser for help on using the repository browser.