[ceph.git] / ceph / src / boost / libs / graph / doc / constructing_algorithms.html

<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&nbsp;[<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>&nbsp;[<A HREF="bibliography.html#welsch67">31</A>],
<I>smallest-last</I>&nbsp;[<a
href="bibliography.html#matula72:_graph_theory_computing">29</a>], and
<I>incidence degree</I>&nbsp;[<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 &lt;class VertexListGraph, class Order, class Color&gt;
  typename graph_traits&lt;VertexListGraph&gt;::vertices_size_type
  sequential_vertex_color_ting(const VertexListGraph&amp; G, 
    Order order, Color color)
  {
    typedef graph_traits&lt;VertexListGraph&gt; GraphTraits;
    typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
    typedef typename GraphTraits::vertices_size_type size_type;
    typedef typename property_traits&lt;Color&gt;::value_type ColorType;
    typedef typename property_traits&lt;Order&gt;::value_type OrderType;

    BOOST_CONCEPT_ASSERT(( VertexListGraphConcept&lt;VertexListGraph&gt; ));
    BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept&lt;Color, vertex_descriptor&gt; ));
    BOOST_CONCEPT_ASSERT(( IntegerConcept&lt;ColorType&gt; ));
    BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept&lt;Order, size_type&gt; ));
    BOOST_STATIC_ASSERT((is_same&lt;OrderType, vertex_descriptor&gt;::value));
    
    size_type max_color = 0;
    const size_type V = num_vertices(G);
    std::vector&lt;size_type&gt; 
      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 &lt; 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 &lt; max_color &amp;&amp; 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 &copy; 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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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 [<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> [<A HREF="bibliography.html#welsch67">31</A>],
	58	<I>smallest-last</I> [<a
	59	href="bibliography.html#matula72:_graph_theory_computing">29</a>], and
	60	<I>incidence degree</I> [<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 <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>,
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>