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

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<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>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" >
<Title>The Boost Graph Library</Title>
<BODY bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" 
        alink="#ff0000"> 
<IMG src="../../../boost.png" 
     alt="C++ Boost" width="277" height="86"> 

<h1>The Boost Graph Library (BGL)
<a href="http://www.awprofessional.com/title/0201729148">
<img src="bgl-cover.jpg" alt="BGL Book" align="RIGHT"></a>
</h1>

<P>
Graphs are mathematical abstractions that are useful for solving many
types of problems in computer science. Consequently, these
abstractions must also be represented in computer programs.  A
standardized generic interface for traversing graphs is of utmost
importance to encourage reuse of graph algorithms and data structures.
Part of the Boost Graph Library is a generic interface that allows
access to a graph's structure, but hides the details of the
implementation.  This is an &ldquo;open&rdquo; interface in the sense that any
graph library that implements this interface will be interoperable
with the BGL generic algorithms and with other algorithms that also
use this interface. The BGL provides some general purpose graph classes
that conform to this interface, but they are not meant to be the
&ldquo;only&rdquo; graph classes; there certainly will be other graph classes
that are better for certain situations.  We believe that the main
contribution of the The BGL is the formulation of this interface.

<P>
The BGL graph interface and graph components are <I>generic</I>, in the
same sense as the Standard Template Library (STL)&nbsp;[<A
HREF="bibliography.html#austern99:_gener_progr_stl">2</A>].

In the following sections, we review the role that generic programming
plays in the STL and compare that to how we applied generic
programming in the context of graphs.

<P>
Of course, if you are already familiar with generic programming,
please dive right in! Here's the <a
href="./table_of_contents.html">Table of Contents</a>.  For distributed-memory
parallelism, you can also look at the <a
href="../../graph_parallel/doc/html/index.html">Parallel BGL</a>.

<P>
The source for the BGL is available as part of the Boost distribution,
which you can <a href="http://sourceforge.net/project/showfiles.php?group_id=7586">
download from here</a>.

<H2>How to Build the BGL</H2>
<p><b>DON'T!</b> The Boost Graph Library is a header-only library and
does not need to be built to be used. The only exceptions are the <a
href="read_graphviz.html">GraphViz input parser</a> and the <a
href="read_graphml.html">GraphML parser</a>.</p>

<p>When compiling programs that use the BGL, <b>be sure to compile
with optimization</b>. For instance, select &ldquo;Release&rdquo; mode with
Microsoft Visual C++ or supply the flag <tt>-O2</tt> or <tt>-O3</tt>
to GCC. </p>

<H2>Genericity in STL</H2>

<P>
There are three ways in which the STL is generic.  

<P>

<H3>Algorithm/Data-Structure Interoperability</H3>

<P>
First, each algorithm is written in a data-structure neutral way,
allowing a single template function to operate on many different
classes of containers. The concept of an iterator is the key
ingredient in this decoupling of algorithms and data-structures.  The
impact of this technique is a reduction in the STL's code size from
<i>O(M*N)</i> to <i>O(M+N)</i>, where <i>M</i> is the number of
algorithms and <i>N</i> is the number of containers. Considering a
situation of 20 algorithms and 5 data-structures, this would be the
difference between writing 100 functions versus only 25 functions! And
the differences continues to grow faster and faster as the number of
algorithms and data-structures increase.

<P>

<H3>Extension through Function Objects</H3>

<P>
The second way that STL is generic is that its algorithms and containers
are extensible. The user can adapt and customize the STL through the
use of function objects. This flexibility is what makes STL such a
great tool for solving real-world problems. Each programming problem
brings its own set of entities and interactions that must be
modeled. Function objects provide a mechanism for extending the STL to
handle the specifics of each problem domain.

<P>

<H3>Element Type Parameterization</H3>

<P>
The third way that STL is generic is that its containers are
parameterized on the element type. Though hugely important, this is
perhaps the least &ldquo;interesting&rdquo; way in which STL is generic.
Generic programming is often summarized by a brief description of
parameterized lists such as <TT>std::list&lt;T&gt;</TT>. This hardly scratches
the surface!

<P>

<H2>Genericity in the Boost Graph Library
</H2>

<P>
Like the STL, there are three ways in which the BGL is generic.

<P>

<H3>Algorithm/Data-Structure Interoperability</H3>

<P>
First, the graph algorithms of the BGL are written to an interface that
abstracts away the details of the particular graph data-structure.
Like the STL, the BGL uses iterators to define the interface for
data-structure traversal. There are three distinct graph traversal
patterns: traversal of all vertices in the graph, through all of the
edges, and along the adjacency structure of the graph (from a vertex
to each of its neighbors). There are separate iterators for each
pattern of traversal.

<P>
This generic interface allows template functions such as <a
href="./breadth_first_search.html"><TT>breadth_first_search()</TT></a>
to work on a large variety of graph data-structures, from graphs
implemented with pointer-linked nodes to graphs encoded in
arrays. This flexibility is especially important in the domain of
graphs. Graph data-structures are often custom-made for a particular
application. Traditionally, if programmers want to reuse an
algorithm implementation they must convert/copy their graph data into
the graph library's prescribed graph structure.  This is the case with
libraries such as LEDA, GTL, Stanford GraphBase; it is especially true
of graph algorithms written in Fortran. This severely limits the reuse
of their graph algorithms.

<P>
In contrast, custom-made (or even legacy) graph structures can be used
as-is with the generic graph algorithms of the BGL, using <I>external
adaptation</I> (see Section <A HREF="./leda_conversion.html">How to
Convert Existing Graphs to the BGL</A>).  External adaptation wraps a new
interface around a data-structure without copying and without placing
the data inside adaptor objects.  The BGL interface was carefully
designed to make this adaptation easy. To demonstrate this, we have
built interfacing code for using a variety of graph dstructures (LEDA
graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in
BGL graph algorithms.

<P>

<H3>Extension through Visitors</H3>

<P>
Second, the graph algorithms of the BGL are extensible. The BGL introduces the
notion of a <I>visitor</I>, which is just a function object with
multiple methods.  In graph algorithms, there are often several key
&ldquo;event points&rdquo; at which it is useful to insert user-defined
operations. The visitor object has a different method that is invoked
at each event point. The particular event points and corresponding
visitor methods depend on the particular algorithm.  They often
include methods like <TT>start_vertex()</TT>,
<TT>discover_vertex()</TT>, <TT>examine_edge()</TT>,
<tt>tree_edge()</tt>, and <TT>finish_vertex()</TT>.

<P>

<H3>Vertex and Edge Property Multi-Parameterization</H3>

<P>
The third way that the BGL is generic is analogous to the parameterization
of the element-type in STL containers, though again the story is a bit
more complicated for graphs. We need to associate values (called
&ldquo;properties&rdquo;) with both the vertices and the edges of the graph. 
In addition, it will often be necessary to associate
multiple properties with each vertex and edge; this is what we mean
by multi-parameterization. 
The STL <tt>std::list&lt;T&gt;</tt> class has a parameter <tt>T</tt>
for its element type. Similarly, BGL graph classes have template
parameters for vertex and edge &ldquo;properties&rdquo;. A
property specifies the parameterized type of the property and also assigns
an identifying tag to the property. This tag is used to distinguish
between the multiple properties which an edge or vertex may have. A
property value that is attached to a 
particular vertex or edge can be obtained via a <I>property
map</I>. There is a separate property map for each property.

<P>
Traditional graph libraries and graph structures fall down when it
comes to the parameterization of graph properties. This is one of the
primary reasons that graph data-structures must be custom-built for
applications. The parameterization of properties in the  BGL graph
classes makes them well suited for re-use.

<p>

<H2>Algorithms</H2>

<P>
The BGL algorithms consist of a core set of algorithm <I>patterns</I>
(implemented as generic algorithms) and a larger set of graph
algorithms. The core algorithm patterns are

<P>

<UL>
<LI>Breadth First Search
</LI>
<LI>Depth First Search
</LI>
<LI>Uniform Cost Search
</LI>
</UL>

<P>
By themselves, the algorithm patterns do not compute any meaningful
quantities over graphs; they are merely building blocks for
constructing graph algorithms. The graph algorithms in the BGL currently
include

<P>

<UL>
<LI>Dijkstra's Shortest Paths</LI>
<LI>Bellman-Ford Shortest Paths</LI>
<LI>Johnson's All-Pairs Shortest Paths</LI>
<LI>Kruskal's Minimum Spanning Tree</LI>
<LI>Prim's Minimum Spanning Tree</LI>
<LI>Connected Components</LI>
<LI>Strongly Connected Components</LI>
<LI>Dynamic Connected Components (using Disjoint Sets)</LI>
<LI>Topological Sort</LI>
<LI>Transpose</LI>
<LI>Reverse Cuthill Mckee Ordering</LI>
<LI>Smallest Last Vertex Ordering</LI>
<LI>Sequential Vertex Coloring</LI>
</UL>

<P>

<H2>Data Structures</H2>

<P>
The BGL currently provides two graph classes and an edge list adaptor:
<P>

<UL>
<LI><a href="adjacency_list.html"><TT>adjacency_list</TT></a></LI>
<LI><a href="adjacency_matrix.html"><TT>adjacency_matrix</TT></a></LI>
<LI><a href="edge_list.html"><TT>edge_list</TT></a></LI>
</UL>

<P>
The <TT>adjacency_list</TT> class is the general purpose &ldquo;swiss army
knife&rdquo; of graph classes. It is highly parameterized so that it can be
optimized for different situations: the graph is directed or
undirected, allow or disallow parallel edges, efficient access to just
the out-edges or also to the in-edges, fast vertex insertion and
removal at the cost of extra space overhead, etc.

<P>
The <tt>adjacency_matrix</tt> class stores edges in a <i>|V| x |V|</i>
matrix (where <i>|V|</i> is the number of vertices). The elements of
this matrix represent edges in the graph. Adjacency matrix
representations are especially suitable for very dense graphs, i.e.,
those where the number of edges approaches <i>|V|<sup>2</sup></i>.

<P>
The <TT>edge_list</TT> class is an adaptor that takes any kind of edge
iterator and implements an <a href="./EdgeListGraph.html">Edge List Graph</a>.


<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	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
	2	"http://www.w3.org/TR/html4/loose.dtd">
	3	<HTML>
	4	<!--
	5	Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
	6
	7	Distributed under the Boost Software License, Version 1.0.
	8	(See accompanying file LICENSE_1_0.txt or copy at
	9	http://www.boost.org/LICENSE_1_0.txt)
	10	-->
	11	<Head>
	12	<meta http-equiv="Content-Type" content="text/html;charset=utf-8" >
	13	<Title>The Boost Graph Library</Title>
	14	<BODY bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"
	15	alink="#ff0000">
	16	<IMG src="../../../boost.png"
	17	alt="C++ Boost" width="277" height="86">
	18
	19	<h1>The Boost Graph Library (BGL)
	20	<a href="http://www.awprofessional.com/title/0201729148">
	21	<img src="bgl-cover.jpg" alt="BGL Book" align="RIGHT"></a>
	22	</h1>
	23
	24	<P>
	25	Graphs are mathematical abstractions that are useful for solving many
	26	types of problems in computer science. Consequently, these
	27	abstractions must also be represented in computer programs. A
	28	standardized generic interface for traversing graphs is of utmost
	29	importance to encourage reuse of graph algorithms and data structures.
	30	Part of the Boost Graph Library is a generic interface that allows
	31	access to a graph's structure, but hides the details of the
	32	implementation. This is an “open” interface in the sense that any
	33	graph library that implements this interface will be interoperable
	34	with the BGL generic algorithms and with other algorithms that also
	35	use this interface. The BGL provides some general purpose graph classes
	36	that conform to this interface, but they are not meant to be the
	37	“only” graph classes; there certainly will be other graph classes
	38	that are better for certain situations. We believe that the main
	39	contribution of the The BGL is the formulation of this interface.
	40
	41	<P>
	42	The BGL graph interface and graph components are <I>generic</I>, in the
	43	same sense as the Standard Template Library (STL) [<A
	44	HREF="bibliography.html#austern99:_gener_progr_stl">2</A>].
	45
	46	In the following sections, we review the role that generic programming
	47	plays in the STL and compare that to how we applied generic
	48	programming in the context of graphs.
	49
	50	<P>
	51	Of course, if you are already familiar with generic programming,
	52	please dive right in! Here's the <a
	53	href="./table_of_contents.html">Table of Contents</a>. For distributed-memory
	54	parallelism, you can also look at the <a
	55	href="../../graph_parallel/doc/html/index.html">Parallel BGL</a>.
	56
	57	<P>
	58	The source for the BGL is available as part of the Boost distribution,
	59	which you can <a href="http://sourceforge.net/project/showfiles.php?group_id=7586">
	60	download from here</a>.
	61
	62	<H2>How to Build the BGL</H2>
	63	<p><b>DON'T!</b> The Boost Graph Library is a header-only library and
	64	does not need to be built to be used. The only exceptions are the <a
65	href="read_graphviz.html">GraphViz input parser</a> and the <a
66	href="read_graphml.html">GraphML parser</a>.</p>
67
68	<p>When compiling programs that use the BGL, <b>be sure to compile
69	with optimization</b>. For instance, select “Release” mode with
70	Microsoft Visual C++ or supply the flag <tt>-O2</tt> or <tt>-O3</tt>
71	to GCC. </p>
72
73	<H2>Genericity in STL</H2>
74
75	<P>
76	There are three ways in which the STL is generic.
77
78	<P>
79
80	<H3>Algorithm/Data-Structure Interoperability</H3>
81
82	<P>
83	First, each algorithm is written in a data-structure neutral way,
84	allowing a single template function to operate on many different
85	classes of containers. The concept of an iterator is the key
86	ingredient in this decoupling of algorithms and data-structures. The
87	impact of this technique is a reduction in the STL's code size from
88	<i>O(M*N)</i> to <i>O(M+N)</i>, where <i>M</i> is the number of
89	algorithms and <i>N</i> is the number of containers. Considering a
90	situation of 20 algorithms and 5 data-structures, this would be the
91	difference between writing 100 functions versus only 25 functions! And
92	the differences continues to grow faster and faster as the number of
93	algorithms and data-structures increase.
94
95	<P>
96
97	<H3>Extension through Function Objects</H3>
98
99	<P>
100	The second way that STL is generic is that its algorithms and containers
101	are extensible. The user can adapt and customize the STL through the
102	use of function objects. This flexibility is what makes STL such a
103	great tool for solving real-world problems. Each programming problem
104	brings its own set of entities and interactions that must be
105	modeled. Function objects provide a mechanism for extending the STL to
106	handle the specifics of each problem domain.
107
108	<P>
109
110	<H3>Element Type Parameterization</H3>
111
112	<P>
113	The third way that STL is generic is that its containers are
114	parameterized on the element type. Though hugely important, this is
115	perhaps the least “interesting” way in which STL is generic.
116	Generic programming is often summarized by a brief description of
117	parameterized lists such as <TT>std::list<T></TT>. This hardly scratches
118	the surface!
119
120	<P>
121
122	<H2>Genericity in the Boost Graph Library
123	</H2>
124
125	<P>
126	Like the STL, there are three ways in which the BGL is generic.
127
128	<P>
129
130	<H3>Algorithm/Data-Structure Interoperability</H3>
131
132	<P>
133	First, the graph algorithms of the BGL are written to an interface that
134	abstracts away the details of the particular graph data-structure.
135	Like the STL, the BGL uses iterators to define the interface for
136	data-structure traversal. There are three distinct graph traversal
137	patterns: traversal of all vertices in the graph, through all of the
138	edges, and along the adjacency structure of the graph (from a vertex
139	to each of its neighbors). There are separate iterators for each
140	pattern of traversal.
141
142	<P>
143	This generic interface allows template functions such as <a
144	href="./breadth_first_search.html"><TT>breadth_first_search()</TT></a>
145	to work on a large variety of graph data-structures, from graphs
146	implemented with pointer-linked nodes to graphs encoded in
147	arrays. This flexibility is especially important in the domain of
148	graphs. Graph data-structures are often custom-made for a particular
149	application. Traditionally, if programmers want to reuse an
150	algorithm implementation they must convert/copy their graph data into
151	the graph library's prescribed graph structure. This is the case with
152	libraries such as LEDA, GTL, Stanford GraphBase; it is especially true
153	of graph algorithms written in Fortran. This severely limits the reuse
154	of their graph algorithms.
155
156	<P>
157	In contrast, custom-made (or even legacy) graph structures can be used
158	as-is with the generic graph algorithms of the BGL, using <I>external
159	adaptation</I> (see Section <A HREF="./leda_conversion.html">How to
160	Convert Existing Graphs to the BGL</A>). External adaptation wraps a new
161	interface around a data-structure without copying and without placing
162	the data inside adaptor objects. The BGL interface was carefully
163	designed to make this adaptation easy. To demonstrate this, we have
164	built interfacing code for using a variety of graph dstructures (LEDA
165	graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in
166	BGL graph algorithms.
167
168	<P>
169
170	<H3>Extension through Visitors</H3>
171
172	<P>
173	Second, the graph algorithms of the BGL are extensible. The BGL introduces the
174	notion of a <I>visitor</I>, which is just a function object with
175	multiple methods. In graph algorithms, there are often several key
176	“event points” at which it is useful to insert user-defined
177	operations. The visitor object has a different method that is invoked
178	at each event point. The particular event points and corresponding
179	visitor methods depend on the particular algorithm. They often
180	include methods like <TT>start_vertex()</TT>,
181	<TT>discover_vertex()</TT>, <TT>examine_edge()</TT>,
182	<tt>tree_edge()</tt>, and <TT>finish_vertex()</TT>.
183
184	<P>
185
186	<H3>Vertex and Edge Property Multi-Parameterization</H3>
187
188	<P>
189	The third way that the BGL is generic is analogous to the parameterization
190	of the element-type in STL containers, though again the story is a bit
191	more complicated for graphs. We need to associate values (called
192	“properties”) with both the vertices and the edges of the graph.
193	In addition, it will often be necessary to associate
194	multiple properties with each vertex and edge; this is what we mean
195	by multi-parameterization.
196	The STL <tt>std::list<T></tt> class has a parameter <tt>T</tt>
197	for its element type. Similarly, BGL graph classes have template
198	parameters for vertex and edge “properties”. A
199	property specifies the parameterized type of the property and also assigns
200	an identifying tag to the property. This tag is used to distinguish
201	between the multiple properties which an edge or vertex may have. A
202	property value that is attached to a
203	particular vertex or edge can be obtained via a <I>property
204	map</I>. There is a separate property map for each property.
205
206	<P>
207	Traditional graph libraries and graph structures fall down when it
208	comes to the parameterization of graph properties. This is one of the
209	primary reasons that graph data-structures must be custom-built for
210	applications. The parameterization of properties in the BGL graph
211	classes makes them well suited for re-use.
212
213	<p>
214
215	<H2>Algorithms</H2>
216
217	<P>
218	The BGL algorithms consist of a core set of algorithm <I>patterns</I>
219	(implemented as generic algorithms) and a larger set of graph
220	algorithms. The core algorithm patterns are
221
222	<P>
223
224	<UL>
225	<LI>Breadth First Search
226	</LI>
227	<LI>Depth First Search
228	</LI>
229	<LI>Uniform Cost Search
230	</LI>
231	</UL>
232
233	<P>
234	By themselves, the algorithm patterns do not compute any meaningful
235	quantities over graphs; they are merely building blocks for
236	constructing graph algorithms. The graph algorithms in the BGL currently
237	include
238
239	<P>
240
241	<UL>
242	<LI>Dijkstra's Shortest Paths</LI>
243	<LI>Bellman-Ford Shortest Paths</LI>
244	<LI>Johnson's All-Pairs Shortest Paths</LI>
245	<LI>Kruskal's Minimum Spanning Tree</LI>
246	<LI>Prim's Minimum Spanning Tree</LI>
247	<LI>Connected Components</LI>
248	<LI>Strongly Connected Components</LI>
249	<LI>Dynamic Connected Components (using Disjoint Sets)</LI>
250	<LI>Topological Sort</LI>
251	<LI>Transpose</LI>
252	<LI>Reverse Cuthill Mckee Ordering</LI>
253	<LI>Smallest Last Vertex Ordering</LI>
254	<LI>Sequential Vertex Coloring</LI>
255	</UL>
256
257	<P>
258
259	<H2>Data Structures</H2>
260
261	<P>
262	The BGL currently provides two graph classes and an edge list adaptor:
263	<P>
264
265	<UL>
266	<LI><a href="adjacency_list.html"><TT>adjacency_list</TT></a></LI>
267	<LI><a href="adjacency_matrix.html"><TT>adjacency_matrix</TT></a></LI>
268	<LI><a href="edge_list.html"><TT>edge_list</TT></a></LI>
269	</UL>
270
271	<P>
272	The <TT>adjacency_list</TT> class is the general purpose “swiss army
273	knife” of graph classes. It is highly parameterized so that it can be
274	optimized for different situations: the graph is directed or
275	undirected, allow or disallow parallel edges, efficient access to just
276	the out-edges or also to the in-edges, fast vertex insertion and
277	removal at the cost of extra space overhead, etc.
278
279	<P>
280	The <tt>adjacency_matrix</tt> class stores edges in a <i>\|V\| x \|V\|</i>
281	matrix (where <i>\|V\|</i> is the number of vertices). The elements of
282	this matrix represent edges in the graph. Adjacency matrix
283	representations are especially suitable for very dense graphs, i.e.,
284	those where the number of edges approaches <i>\|V\|<sup>2</sup></i>.
285
286	<P>
287	The <TT>edge_list</TT> class is an adaptor that takes any kind of edge
288	iterator and implements an <a href="./EdgeListGraph.html">Edge List Graph</a>.
289
290
291	<br>
292	<HR>
293	<TABLE>
294	<TR valign=top>
295	<TD nowrap>Copyright © 2000-2001</TD><TD>
296	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
297	Indiana University (<A
298	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
299	<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>
300	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
301	Indiana University (<A
302	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
303	</TD></TR></TABLE>
304
305	</BODY>
306	</HTML>