ceph/src/boost/libs/graph/doc/stanford_graph.html

   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>
  20 Using SGB Graphs in BGL
  21 </H1>
  22
  23 The Boost Graph Library (BGL) header, <a
  24 href="../../../boost/graph/stanford_graph.hpp"
  25 ><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>, adapts a
  26 Stanford GraphBase (SGB) <tt>Graph</tt> pointer into a BGL-compatible
  27 <a href="./VertexListGraph.html">VertexListGraph</a>.&nbsp; Note that
  28 a graph adaptor <b>class</b> is <i>not</i> used; SGB's <tt>Graph*</tt>
  29 itself becomes a model of VertexListGraph.&nbsp; The VertexListGraph
  30 concept is fulfilled by defining the appropriate non-member functions
  31 for <tt>Graph*</tt>.
  32
  33 <H2><a name="sec:SGB"></a>
  34 The Stanford GraphBase
  35 </H2>
  36
  37 <P>
  38 "The <a href="http://www-cs-staff.stanford.edu/~knuth/sgb.html">Stanford
  39 GraphBase</a> (SGB) is a collection of datasets and computer programs that
  40 generate and examine a wide variety of graphs and networks."&nbsp; The SGB was
  41 developed and published by
  42 <a href="http://www-cs-staff.stanford.edu/~knuth">Donald E. Knuth</a>
  43 in 1993.&nbsp; The fully documented source code is available for anonymous ftp
  44 from <a href="ftp://labrea.stanford.edu/pub/sgb/sgb.tar.gz">Stanford
  45 University</a> and in the book "The Stanford GraphBase, A Platform for
  46 Combinatorial Computing," published jointly by ACM Press and Addison-Wesley
  47 Publishing Company in 1993.&nbsp; (This book contains several chapters with
  48 additional information not available in the electronic distribution.)
  49
  50 <H3><a name="sec:CWEB"></a>
  51 Prerequisites
  52 </H3>
  53
  54 The 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
  56 Programming</a> paradigm, so you need to make sure that your computer supports
  57 the <a href="http://www-cs-staff.stanford.edu/~knuth/cweb.html">CWEB</a>
  58 system.&nbsp; The CWEB sources are available for anonymous ftp from
  59 <a href="ftp://labrea.stanford.edu/pub/cweb/cweb.tar.gz">Stanford
  60 University</a>.&nbsp; Bootstrapping CWEB on Unix systems is elementary and
  61 documented in the CWEB distribution; pre-compiled binary executables of the
  62 CWEB 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>
  66 Installing the SGB
  67 </H3>
  68
  69 After you have acquired the <a href="#sec:SGB">SGB sources</a> and have
  70 installed 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
  72 sources.&nbsp; SGB is written in "old-style C," but the Boost Graph Library
  73 expects to handle "modern C" and C++.&nbsp; Fortunately, the SGB distribution
  74 comes 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
  76 GraphBase 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
  83 the SGB files (or you can simply copy the change files next to the proper
  84 source files).&nbsp; The Unix <tt>Makefile</tt> coming with SGB conveniently
  85 looks for "change files" matching the SGB source files and automatically
  86 applies them with the "ctangle" processor.&nbsp; The resulting C files will
  87 smoothly run through the compiler.
  88 </li>
  89 <li>
  90 <b>Win32</b>: The "MSVC" subdirectory of the SGB distribution contains a
  91 complete set of "Developer Studio Projects" (and a single "Workspace"),
  92 applicable with Microsoft Developer Studio 6.&nbsp; The installation process
  93 is documented in the accompanying file <tt>README.MSVC</tt>.&nbsp; The "MSVC"
  94 contribution has been updated to make use of the "PROTOTYPES" as well, so you
  95 don't need to worry about that.
  96 </li>
  97 </ul>
  98
  99 <H3><a name="sec:UsingSGB"></a>
 100 Using the SGB
 101 </H3>
 102
 103 After you have run <a href="#sec:SGB:Installation">the installation
 104 process</a> of the SGB, you can use the BGL graph interface with the
 105 SGB <tt>Graph*</tt>, <a href="../../../boost/graph/stanford_graph.hpp"
 106 ><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>, which will be
 107 described <a href="#sec:BGL:Interface">next</a>.&nbsp; All you have to
 108 do is tell the C++ compiler where to look for the SGB headerfiles (by
 109 default, <tt>/usr/local/sgb/include</tt> on Unix and the "MSVC"
 110 subdirectory of the SGB installation on Win32) and the linker where to
 111 find the SGB static library file (<tt>libgb.a</tt> on Unix and
 112 <tt>libgb.lib</tt> on Win32); consult the documentation of your
 113 particular compiler about how to do that.
 114
 115 <H3><a name="sec:SGB:Problems"></a>
 116 Technicalities
 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
 123 headerfile <tt>&lt;string.h&gt;</tt> (if <tt>SYSV</tt> is <tt>#define</tt>d)
 124 or 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>,
 126 don't care much (<tt>gcc</tt> "knows" about the "string" functions without
 127 refering to <tt>&lt;string.h&gt;</tt>), but others, like MSVC on Win32, do (so
 128 all "Developer Studio Projects" in the "MSVC" subdirectory of the
 129 <a href="#sec:SGB">SGB distribution</a> appropriately define <tt>SYSV</tt>).
 130 You should be careful to set (or not) <tt>SYSV</tt> according to the needs of
 131 your compiler.
 132 </li>
 133 <li>
 134 <b>Missing include guards</b>: None of the SGB headerfiles uses "internal
 135 include guards" to protect itself from multiple inclusion.&nbsp; To avoid
 136 trouble, you must <i>not</i> <tt>#include</tt> any of the SGB headerfiles
 137 before or after <a href="#sec:Wrapper">the BGL wrapper</a> in a compilation
 138 unit; 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
 142 preprocessor <i>without</i> sticking to a particular convention (like
 143 all-uppercase names or a particular prefix).&nbsp; At the time of writing,
 144 already three of these preprocessor macros collide with the conventions of
 145 either C++, g++, or BGL, and are fixed in <a href="#sec:Wrapper">the BGL
 146 wrapper</a>.&nbsp; We can not guarantee that no other preprocessor-induced
 147 problems 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>
 152 The BGL Interface for the SGB
 153 </H2>
 154
 155 <H3><a name="sec:Wrapper"></a>
 156 Where 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
 165 functions by reading all <a href="#sec:SGB:Problems">SGB headerfiles</a> as in
 166 section 2 of the "<tt>test_sample</tt>" program.
 167
 168 <p> On top of the SGB stuff, the BGL <tt>stanford_graph.hpp</tt>
 169 header adds and defines appropriate types and functions for using the
 170 SGB graphs in the BGL framework.&nbsp; Apart from the improved
 171 interface, the <a href="#sec:UsingSGB">SGB (static) library</a> is
 172 used "as is" in the context of BGL.
 173
 174 <H3>
 175 Model Of
 176 </H3>
 177
 178 <a href="./VertexListGraph.html">Vertex List Graph</a> and <a
 179 href="./PropertyGraph.html">Property Graph</a>.  The set of property
 180 tags that can be used with the SGB graph is described in the <a
 181 href="#properties">Vertex and Edge Properties</a> section below.
 182
 183
 184 <H3><a name="sec:Example"></a>
 185 Example
 186 </H3>
 187
 188 The example program <a href="../example/miles_span.cpp">
 189 <tt>&lt;example/miles_span.cpp&gt;</tt></a> represents the first
 190 application of the generic framework of BGL to an SGB graph.&nbsp; It
 191 uses Prim's algorithm to solve the "minimum spanning tree"
 192 problem.&nbsp; In addition, the programs <a
 193 href="../../../libs/graph/example/girth.cpp">
 194 <tt>&lt;example/girth.cpp&gt;</tt></a> and <a
 195 href="../example/roget_components.cpp">
 196 <tt>&lt;example/roget_components.cpp&gt;</tt></a> have been ported
 197 from the SGB.&nbsp; We intend to implement more algorithms from SGB in
 198 a generic fashion and to provide the remaining example programs of SGB
 199 for the BGL framework.&nbsp; If you would like to help, feel free to
 200 submit your contributions!
 201
 202 <H3>
 203 Associated Types
 204 </H3>
 205
 206 <hr>
 207
 208 <tt>graph_traits&lt;Graph*&gt;::vertex_descriptor</tt><br><br>
 209 The type for the vertex descriptors associated with the <tt>Graph*</tt>.
 210 We 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
 215 for the edge descriptors associated with the <tt>Graph*</tt>.  This is
 216 the type <tt>boost::sgb_edge</tt>. In addition to supporting all the
 217 required 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>
 226 The 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>
 231 The 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>
 236 The 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>
 241 The 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>
 246 The 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>
 251 The type used for dealing with the number of edges incident to a vertex
 252 in the graph.
 253
 254 <hr>
 255
 256 <tt>graph_traits&lt;Graph*&gt;::directed_category</tt><br><br>
 257 Provides information about whether the graph is directed or
 258 undirected. 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>
 264 An SGB <tt>Graph*</tt> provides traversal of the vertex set,
 265 out edges, and adjacent vertices. Therefore the traversal category
 266 tag is defined as follows:
 267 <pre>
 268 struct 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>
 277 This 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>
 279 does not prevent addition of parallel edges, so this type
 280 is <tt>allow_parallel_edge_tag</tt>.
 281
 282 <hr>
 283
 284 <H3>
 285 Non-Member Functions
 286 </H3>
 287
 288 <hr>
 289
 290 <pre>
 291 std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
 292 vertices(Graph*&nbsp;g)
 293 </pre>
 294 Returns an iterator-range providing access to the vertex set of graph
 295 <tt>g</tt>.
 296
 297 <hr>
 298
 299 <pre>
 300 std::pair&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
 301 out_edges(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
 302 </pre>
 303 Returns an iterator-range providing access to the out-edges of vertex
 304 <tt>v</tt> in graph <tt>g</tt>.<br>
 305 There is no corresponding <tt>in_edges</tt> function.
 306
 307 <hr>
 308
 309 <pre>
 310 std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;
 311 adjacent_vertices(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
 312 </pre>
 313 Returns 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>
 319 vertex_descriptor
 320 source(edge_descriptor&nbsp;e, Graph*&nbsp;g)
 321 </pre>
 322 Returns the source vertex of edge <tt>e</tt>.
 323
 324 <hr>
 325
 326 <pre>
 327 vertex_descriptor
 328 target(edge_descriptor&nbsp;e, Graph*&nbsp;g)
 329 </pre>
 330 Returns the target vertex of edge <tt>e</tt>.
 331
 332 <hr>
 333
 334 <pre>
 335 degree_size_type
 336 out_degree(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
 337 </pre>
 338 Returns the number of edges leaving vertex <tt>v</tt>.<br>
 339 There is no corresponding <tt>in_degree</tt> function.
 340
 341 <hr>
 342
 343 <pre>
 344 vertices_size_type
 345 num_vertices(Graph*&nbsp;g)
 346 </pre>
 347 Returns the number of vertices in the graph <tt>g</tt>.
 348
 349 <hr>
 350
 351 <pre>
 352 edge_size_type
 353 num_edges(Graph*&nbsp;g)
 354 </pre>
 355 Returns the number of edges in the graph <tt>g</tt>.
 356
 357 <hr>
 358
 359 <pre>
 360 vertex_descriptor
 361 vertex(vertices_size_type&nbsp;n, Graph*&nbsp;g)
 362 </pre>
 363 Returns the (0-based) nth vertex in the graph's vertex list.
 364
 365 <hr>
 366
 367 <pre>
 368 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 369 property_map&lt;Graph*, PropertyTag&gt;::type
 370 get(PropertyTag, Graph*&amp; g)
 371
 372 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 373 property_map&lt;Graph*, Tag&gt;::const_type
 374 get(PropertyTag, const Graph*&amp; g)
 375 </pre>
 376 Returns the property map object for the vertex property specified by
 377 <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must be one of
 378 the described below.
 379
 380 <hr>
 381
 382 <h3><a name="properties">Vertex and Edge Properties</a></h3>
 383
 384 The SGB <tt>Vertex</tt> and <tt>Arc</tt> structures provide
 385 &quot;utility&quot; fields for storing extra information.  We provide
 386 BGL wrappers that provide access to these fields through <a
 387 href="../../property_map/doc/property_map.html">property maps</a>.  In
 388 addition, vertex index and edge length maps are provided. A property
 389 map object can be obtained from a SGB <tt>Graph*</tt> using the
 390 <tt>get()</tt> function described in the <a
 391 href="./PropertyGraph.html">Property Graph</a> concept.
 392
 393 <p>
 394 The following list of property tags can be used to specify which
 395 utility field you would like a property map for.
 396 </p>
 397
 398 <pre>
 399 <i>// vertex properties</i>
 400 template &lt;class T&gt; u_property;
 401 template &lt;class T&gt; v_property;
 402 template &lt;class T&gt; w_property;
 403 template &lt;class T&gt; x_property;
 404 template &lt;class T&gt; y_property;
 405 template &lt;class T&gt; z_property;
 406
 407 <i>// edge properties</i>
 408 template &lt;class T&gt; a_property;
 409 template &lt;class T&gt; b_property;
 410 </pre>
 411
 412 <p>
 413 The template parameter <tt>T</tt> for these tags is limited to the
 414 types 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
 417 for the utility fields are models of <a
 418 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 419 Map</a>.
 420 </p>
 421
 422 <p>
 423 The property map for vertex indices can be obtained using the
 424 <tt>vertex_index_t</tt> tag, and this property map is a <a
 425 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 426 Map</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
 428 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 429 Map</a> whose value type is <tt>long</tt>.
 430 </p>
 431
 432 <p>
 433 Property map objects can be obtained via the <tt>get()</tt> function
 434 of the Property Graph concept. The type of the property map is given
 435 by the <a href="./property_map.html"><tt>property_map</tt></a> traits
 436 class.</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>,
 444 Aachen (<A
 445 HREF="mailto:andreas_freenet@freenet.de">andreas_freenet@freenet.de</A>)<br>
 446 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 447 Indiana University (<A
 448 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 449 <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>,
 450 Indiana University (<A
 451 HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
 452 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 453 Indiana University (<A
 454 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 455 </TD></TR></TABLE>
 456
 457 </BODY>
 458 </HTML>