Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/stanford_graph.html @ 45

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

updated boost from 1_33_1 to 1_34_1
File size: 15.6 KB
Line 
1<HTML>
2<!--
3  Copyright (C) 2001, Andreas Scherer, Jeremy Siek, Lie-Quan Lee,
4  and Andrew Lumsdaine
5
6  -- Distributed under the Boost Software License, Version 1.0.
7  -- (See accompanying file LICENSE_1_0.txt or copy at
8  -- http://www.boost.org/LICENSE_1_0.txt)
9  -->
10<Head>
11<Title>Boost Graph Library: Stanford Graph Interface</Title>
12<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
13        ALINK="#ff0000"> 
14<IMG SRC="../../../boost.png" 
15     ALT="C++ Boost" width="277" height="86"> 
16
17<BR Clear>
18
19<H1>
20Using SGB Graphs in BGL
21</H1>
22
23The Boost Graph Library (BGL) header, <a
24href="../../../boost/graph/stanford_graph.hpp"
25><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>, adapts a
26Stanford GraphBase (SGB) <tt>Graph</tt> pointer into a BGL-compatible
27<a href="./VertexListGraph.html">VertexListGraph</a>.&nbsp; Note that
28a graph adaptor <b>class</b> is <i>not</i> used; SGB's <tt>Graph*</tt>
29itself becomes a model of VertexListGraph.&nbsp; The VertexListGraph
30concept is fulfilled by defining the appropriate non-member functions
31for <tt>Graph*</tt>.
32
33<H2><a name="sec:SGB"></a>
34The Stanford GraphBase
35</H2>
36
37<P>
38"The <a href="http://www-cs-staff.stanford.edu/~knuth/sgb.html">Stanford
39GraphBase</a> (SGB) is a collection of datasets and computer programs that
40generate and examine a wide variety of graphs and networks."&nbsp; The SGB was
41developed and published by
42<a href="http://www-cs-staff.stanford.edu/~knuth">Donald E. Knuth</a>
43in 1993.&nbsp; The fully documented source code is available for anonymous ftp
44from <a href="ftp://labrea.stanford.edu/pub/sgb/sgb.tar.gz">Stanford
45University</a> and in the book "The Stanford GraphBase, A Platform for
46Combinatorial Computing," published jointly by ACM Press and Addison-Wesley
47Publishing Company in 1993.&nbsp; (This book contains several chapters with
48additional information not available in the electronic distribution.)
49
50<H3><a name="sec:CWEB"></a>
51Prerequisites
52</H3>
53
54The source code of SGB is written in accordance with the rules of the
55<a href="http://www-cs-staff.stanford.edu/~knuth/lp.html">Literate
56Programming</a> paradigm, so you need to make sure that your computer supports
57the <a href="http://www-cs-staff.stanford.edu/~knuth/cweb.html">CWEB</a>
58system.&nbsp; The CWEB sources are available for anonymous ftp from
59<a href="ftp://labrea.stanford.edu/pub/cweb/cweb.tar.gz">Stanford
60University</a>.&nbsp; Bootstrapping CWEB on Unix systems is elementary and
61documented in the CWEB distribution; pre-compiled binary executables of the
62CWEB tools for Win32 systems are available from
63<a href="http://www.literateprogramming.com">www.literateprogramming.com</a>.
64
65<H3><a name="sec:SGB:Installation"></a>
66Installing the SGB
67</H3>
68
69After you have acquired the <a href="#sec:SGB">SGB sources</a> and have
70installed a working <a href="#sec:CWEB">CWEB system</a> (at least the
71"ctangle" processor is required), you're almost set for compiling the SGB
72sources.&nbsp; SGB is written in "old-style C," but the Boost Graph Library
73expects to handle "modern C" and C++.&nbsp; Fortunately, the SGB distribution
74comes with an appropriate set of patches that convert all the sources from
75"KR-C" to "ANSI-C," thus allowing for smooth integration of the Stanford
76GraphBase in the Boost Graph Library.
77
78<ul>
79<li>
80<b>Unix</b>: After extracting the SGB archive, but prior to invoking
81"<tt>make tests</tt>" and "<tt>make install</tt>," you should say
82"<tt>ln -s PROTOTYPES/*.ch .</tt>" in the root directory where you extracted
83the SGB files (or you can simply copy the change files next to the proper
84source files).&nbsp; The Unix <tt>Makefile</tt> coming with SGB conveniently
85looks for "change files" matching the SGB source files and automatically
86applies them with the "ctangle" processor.&nbsp; The resulting C files will
87smoothly run through the compiler.
88</li>
89<li>
90<b>Win32</b>: The "MSVC" subdirectory of the SGB distribution contains a
91complete set of "Developer Studio Projects" (and a single "Workspace"),
92applicable with Microsoft Developer Studio 6.&nbsp; The installation process
93is documented in the accompanying file <tt>README.MSVC</tt>.&nbsp; The "MSVC"
94contribution has been updated to make use of the "PROTOTYPES" as well, so you
95don't need to worry about that.
96</li>
97</ul>
98
99<H3><a name="sec:UsingSGB"></a>
100Using the SGB
101</H3>
102
103After you have run <a href="#sec:SGB:Installation">the installation
104process</a> of the SGB, you can use the BGL graph interface with the
105SGB <tt>Graph*</tt>, <a href="../../../boost/graph/stanford_graph.hpp"
106><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>, which will be
107described <a href="#sec:BGL:Interface">next</a>.&nbsp; All you have to
108do is tell the C++ compiler where to look for the SGB headerfiles (by
109default, <tt>/usr/local/sgb/include</tt> on Unix and the "MSVC"
110subdirectory of the SGB installation on Win32) and the linker where to
111find the SGB static library file (<tt>libgb.a</tt> on Unix and
112<tt>libgb.lib</tt> on Win32); consult the documentation of your
113particular compiler about how to do that.
114
115<H3><a name="sec:SGB:Problems"></a>
116Technicalities
117</H3>
118
119<ul>
120<li>
121<b>Headerfile selection</b>: The two SGB modules <tt>gb_graph</tt> and
122<tt>gb_io</tt> use the preprocessor switch <tt>SYSV</tt> to select either the
123headerfile <tt>&lt;string.h&gt;</tt> (if <tt>SYSV</tt> is <tt>#define</tt>d)
124or the headerfile <tt>&lt;strings.h&gt;</tt> (if <tt>SYSV</tt> is <i>not</i>
125<tt>#define</tt>d).&nbsp; Some compilers, like <tt>gcc</tt>/<tt>g++</tt>,
126don't care much (<tt>gcc</tt> "knows" about the "string" functions without
127refering to <tt>&lt;string.h&gt;</tt>), but others, like MSVC on Win32, do (so
128all "Developer Studio Projects" in the "MSVC" subdirectory of the
129<a href="#sec:SGB">SGB distribution</a> appropriately define <tt>SYSV</tt>).
130You should be careful to set (or not) <tt>SYSV</tt> according to the needs of
131your compiler.
132</li>
133<li>
134<b>Missing include guards</b>: None of the SGB headerfiles uses "internal
135include guards" to protect itself from multiple inclusion.&nbsp; To avoid
136trouble, you must <i>not</i> <tt>#include</tt> any of the SGB headerfiles
137before or after <a href="#sec:Wrapper">the BGL wrapper</a> in a compilation
138unit; it will fully suffice to use the BGL interface.
139</li>
140<li>
141<b>Preprocessor macros</b>: The SGB headerfiles make liberal use of the
142preprocessor <i>without</i> sticking to a particular convention (like
143all-uppercase names or a particular prefix).&nbsp; At the time of writing,
144already three of these preprocessor macros collide with the conventions of
145either C++, g++, or BGL, and are fixed in <a href="#sec:Wrapper">the BGL
146wrapper</a>.&nbsp; We can not guarantee that no other preprocessor-induced
147problems may arise (but we are willing to learn about any such collisions).
148</li>
149</ul>
150
151<H2><a name="sec:BGL:Interface"></a>
152The BGL Interface for the SGB
153</H2>
154
155<H3><a name="sec:Wrapper"></a>
156Where Defined
157</H3>
158
159<a href="../../../boost/graph/stanford_graph.hpp"
160><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>
161
162<p> The main purpose of this Boost Graph Library (BGL) headerfile is to
163<tt>#include</tt> all global definitions for the general stuff of the
164<a href="#sec:SGB">Stanford GraphBase</a> (SGB) and its various graph generator
165functions by reading all <a href="#sec:SGB:Problems">SGB headerfiles</a> as in
166section 2 of the "<tt>test_sample</tt>" program.
167
168<p> On top of the SGB stuff, the BGL <tt>stanford_graph.hpp</tt>
169header adds and defines appropriate types and functions for using the
170SGB graphs in the BGL framework.&nbsp; Apart from the improved
171interface, the <a href="#sec:UsingSGB">SGB (static) library</a> is
172used "as is" in the context of BGL.
173
174<H3>
175Model Of
176</H3>
177
178<a href="./VertexListGraph.html">Vertex List Graph</a> and <a
179href="./PropertyGraph.html">Property Graph</a>.  The set of property
180tags that can be used with the SGB graph is described in the <a
181href="#properties">Vertex and Edge Properties</a> section below.
182
183
184<H3><a name="sec:Example"></a>
185Example
186</H3>
187
188The example program <a href="../example/miles_span.cpp">
189<tt>&lt;example/miles_span.cpp&gt;</tt></a> represents the first
190application of the generic framework of BGL to an SGB graph.&nbsp; It
191uses Prim's algorithm to solve the "minimum spanning tree"
192problem.&nbsp; In addition, the programs <a
193href="../../../libs/graph/example/girth.cpp">
194<tt>&lt;example/girth.cpp&gt;</tt></a> and <a
195href="../example/roget_components.cpp">
196<tt>&lt;example/roget_components.cpp&gt;</tt></a> have been ported
197from the SGB.&nbsp; We intend to implement more algorithms from SGB in
198a generic fashion and to provide the remaining example programs of SGB
199for the BGL framework.&nbsp; If you would like to help, feel free to
200submit your contributions!
201
202<H3>
203Associated Types
204</H3>
205
206<hr>
207
208<tt>graph_traits&lt;Graph*&gt;::vertex_descriptor</tt><br><br>
209The type for the vertex descriptors associated with the <tt>Graph*</tt>.
210We use the type <tt>Vertex*</tt> as the vertex descriptor.
211
212<hr>
213
214<tt>graph_traits&lt;Graph*&gt;::edge_descriptor</tt><br><br> The type
215for the edge descriptors associated with the <tt>Graph*</tt>.  This is
216the type <tt>boost::sgb_edge</tt>. In addition to supporting all the
217required operations of a BGL edge descriptor, the
218<tt>boost::sgb_edge</tt> class has the following constructor.
219<pre>
220   sgb_edge::sgb_edge(Arc* arc, Vertex* source)
221</pre>
222
223<hr>
224
225<tt>graph_traits&lt;Graph*&gt;::vertex_iterator</tt><br><br>
226The type for the iterators returned by <tt>vertices()</tt>.
227
228<hr>
229
230<tt>graph_traits&lt;Graph*&gt;::out_edge_iterator</tt><br><br>
231The type for the iterators returned by <tt>out_edges()</tt>.
232
233<hr>
234
235<tt>graph_traits&lt;Graph*&gt;::adjacency_iterator</tt><br><br>
236The type for the iterators returned by <tt>adjacent_vertices()</tt>.
237
238<hr>
239
240<tt>graph_traits&lt;Graph*&gt;::vertices_size_type</tt><br><br>
241The type used for dealing with the number of vertices in the graph.
242
243<hr>
244
245<tt>graph_traits&lt;Graph*&gt;::edge_size_type</tt><br><br>
246The type used for dealing with the number of edges in the graph.
247
248<hr>
249
250<tt>graph_traits&lt;Graph*&gt;::degree_size_type</tt><br><br>
251The type used for dealing with the number of edges incident to a vertex
252in the graph.
253
254<hr>
255
256<tt>graph_traits&lt;Graph*&gt;::directed_category</tt><br><br>
257Provides information about whether the graph is directed or
258undirected. An SGB <tt>Graph*</tt> is directed so this type is
259<tt>directed_tag</tt>.
260
261<hr>
262
263<tt>graph_traits&lt;Graph*&gt;::traversal_category</tt><br><br>
264An SGB <tt>Graph*</tt> provides traversal of the vertex set,
265out edges, and adjacent vertices. Therefore the traversal category
266tag is defined as follows:
267<pre>
268struct sgb_traversal_tag :
269  public virtual vertex_list_graph_tag,
270  public virtual incidence_graph_tag,
271  public virtual adjacency_graph_tag { };
272</pre>
273
274<hr>
275
276<tt>graph_traits&lt;Graph*&gt;::edge_parallel_category</tt><br><br>
277This describes whether the graph class allows the insertion of parallel edges
278(edges with the same source and target).&nbsp; The SGB <tt>Graph*</tt>
279does not prevent addition of parallel edges, so this type
280is <tt>allow_parallel_edge_tag</tt>.
281
282<hr>
283
284<H3>
285Non-Member Functions
286</H3>
287
288<hr>
289
290<pre>
291std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
292vertices(Graph*&nbsp;g)
293</pre>
294Returns an iterator-range providing access to the vertex set of graph
295<tt>g</tt>.
296
297<hr>
298
299<pre>
300std::pair&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
301out_edges(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
302</pre>
303Returns an iterator-range providing access to the out-edges of vertex
304<tt>v</tt> in graph <tt>g</tt>.<br>
305There is no corresponding <tt>in_edges</tt> function.
306
307<hr>
308
309<pre>
310std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;
311adjacent_vertices(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
312</pre>
313Returns an iterator-range providing access to the adjacent vertices of vertex
314<tt>v</tt> in graph <tt>g</tt>.
315
316<hr>
317
318<pre>
319vertex_descriptor
320source(edge_descriptor&nbsp;e, Graph*&nbsp;g)
321</pre>
322Returns the source vertex of edge <tt>e</tt>.
323
324<hr>
325
326<pre>
327vertex_descriptor
328target(edge_descriptor&nbsp;e, Graph*&nbsp;g)
329</pre>
330Returns the target vertex of edge <tt>e</tt>.
331
332<hr>
333
334<pre>
335degree_size_type
336out_degree(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
337</pre>
338Returns the number of edges leaving vertex <tt>v</tt>.<br>
339There is no corresponding <tt>in_degree</tt> function.
340
341<hr>
342
343<pre>
344vertices_size_type
345num_vertices(Graph*&nbsp;g)
346</pre>
347Returns the number of vertices in the graph <tt>g</tt>.
348
349<hr>
350
351<pre>
352edge_size_type
353num_edges(Graph*&nbsp;g)
354</pre>
355Returns the number of edges in the graph <tt>g</tt>.
356
357<hr>
358
359<pre>
360vertex_descriptor
361vertex(vertices_size_type&nbsp;n, Graph*&nbsp;g)
362</pre>
363Returns the (0-based) nth vertex in the graph's vertex list.
364
365<hr>
366
367<pre>
368template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
369property_map&lt;Graph*, PropertyTag&gt;::type
370get(PropertyTag, Graph*&amp; g)
371
372template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
373property_map&lt;Graph*, Tag&gt;::const_type
374get(PropertyTag, const Graph*&amp; g)
375</pre>
376Returns the property map object for the vertex property specified by
377<TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must be one of
378the described below.
379
380<hr>
381
382<h3><a name="properties">Vertex and Edge Properties</a></h3>
383
384The SGB <tt>Vertex</tt> and <tt>Arc</tt> structures provide
385&quot;utility&quot; fields for storing extra information.  We provide
386BGL wrappers that provide access to these fields through <a
387href="../../property_map/property_map.html">property maps</a>.  In
388addition, vertex index and edge length maps are provided. A property
389map object can be obtained from a SGB <tt>Graph*</tt> using the
390<tt>get()</tt> function described in the <a
391href="./PropertyGraph.html">Property Graph</a> concept.
392
393<p>
394The following list of property tags can be used to specify which
395utility field you would like a property map for.
396</p>
397
398<pre>
399<i>// vertex properties</i>
400template &lt;class T&gt; u_property;
401template &lt;class T&gt; v_property;
402template &lt;class T&gt; w_property;
403template &lt;class T&gt; x_property;
404template &lt;class T&gt; y_property;
405template &lt;class T&gt; z_property;
406
407<i>// edge properties</i>
408template &lt;class T&gt; a_property;
409template &lt;class T&gt; b_property;
410</pre>
411
412<p>
413The template parameter <tt>T</tt> for these tags is limited to the
414types in the <tt>util</tt> union declared in the SGB header
415<tt>gb_graph.h</tt>, which are <tt>Vertex*</tt>, <tt>Arc*</tt>,
416<tt>Graph*</tt>, <tt>char*</tt>, and <tt>long</tt>. The property maps
417for the utility fields are models of <a
418href="../../property_map/LvaluePropertyMap.html">Lvalue Property
419Map</a>.
420</p>
421
422<p>
423The property map for vertex indices can be obtained using the
424<tt>vertex_index_t</tt> tag, and this property map is a <a
425href="../../property_map/ReadablePropertyMap.html">Readable Property
426Map</a>. A property map for edge length's can be obtained using the
427<tt>edge_length_t</tt> tag, and this property map is a <a
428href="../../property_map/LvaluePropertyMap.html">Lvalue Property
429Map</a> whose value type is <tt>long</tt>.
430</p>
431
432<p>
433Property map objects can be obtained via the <tt>get()</tt> function
434of the Property Graph concept. The type of the property map is given
435by the <a href="./property_map.html"><tt>property_map</tt></a> traits
436class.</p>
437
438
439<HR>
440<TABLE>
441<TR valign=top>
442<TD nowrap>Copyright &copy 2001</TD><TD>
443<A HREF="http://people.freenet.de/andreas.scherer">Andreas Scherer</A>,
444Aachen (<A
445HREF="mailto:andreas_freenet@freenet.de">andreas_freenet@freenet.de</A>)<br>
446<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
447Indiana University (<A
448HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
449<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>,
450Indiana University (<A
451HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
452<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
453Indiana University (<A
454HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
455</TD></TR></TABLE>
456
457</BODY>
458</HTML> 
Note: See TracBrowser for help on using the repository browser.