123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Boost Graph Library: Constructing Graph Algorithms</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1>Constructing graph algorithms with BGL</H1>
- <P>
- The <I>main</I> goal of BGL is not to provide a nice graph class, or
- to provide a comprehensive set of reusable graph algorithms (though
- these are goals). The main goal of BGL is to encourage others to
- write reusable graph algorithms. By reusable we mean maximally
- reusable. Generic programming is a methodology for making algorithms
- maximally reusable, and in this section we will discuss how to apply
- generic programming to constructing graph algorithms.
- <P>
- To illustrate the generic programming process we will step though the
- construction of a graph coloring algorithm. The graph coloring problem
- (or more specifically, the vertex coloring problem) is to label each
- vertex in a graph <i>G</i> with a color such that no two adjacent
- vertices are labeled with the same color and such that the minimum
- number of colors are used. In general, the graph coloring problem is
- NP-complete, and therefore it is impossible to find an optimal
- solution in a reasonable amount of time. However, there are many
- algorithms that use heuristics to find colorings that are close to the
- minimum.
- <P>
- The particular algorithm we present here is based on the linear time
- <TT>SEQ</TT> subroutine that is used in the estimation of sparse
- Jacobian and Hessian matrices [<A
- HREF="bibliography.html#curtis74:_jacob">9</A>,<A
- HREF="bibliography.html#coleman84:_estim_jacob">7</A>,<A
- HREF="bibliography.html#coleman85:_algor">6</A>]. This algorithm
- visits all of the vertices in the graph according to the order defined
- by the input order. At each vertex the algorithm marks the colors of
- the adjacent vertices, and then chooses the smallest unmarked color
- for the color of the current vertex. If all of the colors are already
- marked, a new color is created. A color is considered marked if its
- mark number is equal to the current vertex number. This saves the
- trouble of having to reset the marks for each vertex. The
- effectiveness of this algorithm is highly dependent on the input
- vertex order. There are several ordering algorithms, including the
- <I>largest-first</I> [<A HREF="bibliography.html#welsch67">31</A>],
- <I>smallest-last</I> [<a
- href="bibliography.html#matula72:_graph_theory_computing">29</a>], and
- <I>incidence degree</I> [<a
- href="bibliography.html#brelaz79:_new">32</a>] algorithms, which
- improve the effectiveness of this coloring algorithm.
- <P>
- The first decision to make when constructing a generic graph algorithm
- is to decide what graph operations are necessary for implementing the
- algorithm, and which graph concepts the operations map to. In this
- algorithm we will need to traverse through all of the vertices to
- intialize the vertex colors. We also need to access the adjacent
- vertices. Therefore, we will choose the <a
- href="./VertexListGraph.html">VertexListGraph</a> concept because it
- is the minimum concept that includes these operations. The graph type
- will be parameterized in the template function for this algorithm. We
- do not restrict the graph type to a particular graph class, such as
- the BGL <a href="./adjacency_list.html"><TT>adjacency_list</TT></a>,
- for this would drastically limit the reusability of the algorithm (as
- most algorithms written to date are). We do restrict the graph type to
- those types that model <a
- href="./VertexListGraph.html">VertexListGraph</a>. This is enforced by
- the use of those graph operations in the algorithm, and furthermore by
- our explicit requirement added as a concept check with
- <TT>BOOST_CONCEPT_ASSERT()</TT> (see Section <A
- HREF="../../concept_check/concept_check.htm">Concept
- Checking</A> for more details about concept checking).
- <P>
- Next we need to think about what vertex or edge properties will be
- used in the algorithm. In this case, the only property is vertex
- color. The most flexible way to specify access to vertex color is to
- use the propery map interface. This gives the user of the
- algorithm the ability to decide how they want to store the properties.
- Since we will need to both read and write the colors we specify the
- requirements as <a
- href="../../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a>. The
- <TT>key_type</TT> of the color map must be the
- <TT>vertex_descriptor</TT> from the graph, and the <TT>value_type</TT>
- must be some kind of integer. We also specify the interface for the
- <TT>order</TT> parameter as a property map, in this case a <a
- href="../../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a>. For
- order, the <TT>key_type</TT> is an integer offset and the
- <TT>value_type</TT> is a <TT>vertex_descriptor</TT>. Again we enforce
- these requirements with concept checks. The return value of this
- algorithm is the number of colors that were needed to color the graph,
- hence the return type of the function is the graph's
- <TT>vertices_size_type</TT>. The following code shows the interface for our
- graph algorithm as a template function, the concept checks, and some
- typedefs. The implementation is straightforward, the only step not
- discussed above is the color initialization step, where we set the
- color of all the vertices to "uncolored."
- <P>
- <PRE>
- namespace boost {
- template <class VertexListGraph, class Order, class Color>
- typename graph_traits<VertexListGraph>::vertices_size_type
- sequential_vertex_color_ting(const VertexListGraph& G,
- Order order, Color color)
- {
- typedef graph_traits<VertexListGraph> GraphTraits;
- typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
- typedef typename GraphTraits::vertices_size_type size_type;
- typedef typename property_traits<Color>::value_type ColorType;
- typedef typename property_traits<Order>::value_type OrderType;
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<VertexListGraph> ));
- BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Color, vertex_descriptor> ));
- BOOST_CONCEPT_ASSERT(( IntegerConcept<ColorType> ));
- BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<Order, size_type> ));
- BOOST_STATIC_ASSERT((is_same<OrderType, vertex_descriptor>::value));
-
- size_type max_color = 0;
- const size_type V = num_vertices(G);
- std::vector<size_type>
- mark(V, numeric_limits_max(max_color));
-
- typename GraphTraits::vertex_iterator v, vend;
- for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
- color[*v] = V - 1; // which means "not colored"
-
- for (size_type i = 0; i < V; i++) {
- vertex_descriptor current = order[i];
- // mark all the colors of the adjacent vertices
- typename GraphTraits::adjacency_iterator ai, aend;
- for (boost::tie(ai, aend) = adjacent_vertices(current, G); ai != aend; ++ai)
- mark[color[*ai]] = i;
- // find the smallest color unused by the adjacent vertices
- size_type smallest_color = 0;
- while (smallest_color < max_color && mark[smallest_color] == i)
- ++smallest_color;
- // if all the colors are used up, increase the number of colors
- if (smallest_color == max_color)
- ++max_color;
- color[current] = smallest_color;
- }
- return max_color;
- }
- } // namespace boost
- </PRE>
- <P>
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
- Indiana University (<A
- HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
- <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>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|