Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/constructing_algorithms.html @ 14

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

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