boost_1_45_0/libs/graph/doc/stanford_graph.html - nest-learning-thermostat/5.0/boost - Git at Google

 <HTML>
 <!--
   Copyright (C) 2001, Andreas Scherer, Jeremy Siek, Lie-Quan Lee,
   and Andrew Lumsdaine

      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: Stanford Graph Interface</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>
 Using SGB Graphs in BGL
 </H1>

 The Boost Graph Library (BGL) header, <a
 href="../../../boost/graph/stanford_graph.hpp"
 ><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>, adapts a
 Stanford GraphBase (SGB) <tt>Graph</tt> pointer into a BGL-compatible
 <a href="./VertexListGraph.html">VertexListGraph</a>.&nbsp; Note that
 a graph adaptor <b>class</b> is <i>not</i> used; SGB's <tt>Graph*</tt>
 itself becomes a model of VertexListGraph.&nbsp; The VertexListGraph
 concept is fulfilled by defining the appropriate non-member functions
 for <tt>Graph*</tt>.

 <H2><a name="sec:SGB"></a>
 The Stanford GraphBase
 </H2>

 <P>
 "The <a href="http://www-cs-staff.stanford.edu/~knuth/sgb.html">Stanford
 GraphBase</a> (SGB) is a collection of datasets and computer programs that
 generate and examine a wide variety of graphs and networks."&nbsp; The SGB was
 developed and published by
 <a href="http://www-cs-staff.stanford.edu/~knuth">Donald E. Knuth</a>
 in 1993.&nbsp; The fully documented source code is available for anonymous ftp
 from <a href="ftp://labrea.stanford.edu/pub/sgb/sgb.tar.gz">Stanford
 University</a> and in the book "The Stanford GraphBase, A Platform for
 Combinatorial Computing," published jointly by ACM Press and Addison-Wesley
 Publishing Company in 1993.&nbsp; (This book contains several chapters with
 additional information not available in the electronic distribution.)

 <H3><a name="sec:CWEB"></a>
 Prerequisites
 </H3>

 The source code of SGB is written in accordance with the rules of the
 <a href="http://www-cs-staff.stanford.edu/~knuth/lp.html">Literate
 Programming</a> paradigm, so you need to make sure that your computer supports
 the <a href="http://www-cs-staff.stanford.edu/~knuth/cweb.html">CWEB</a>
 system.&nbsp; The CWEB sources are available for anonymous ftp from
 <a href="ftp://labrea.stanford.edu/pub/cweb/cweb.tar.gz">Stanford
 University</a>.&nbsp; Bootstrapping CWEB on Unix systems is elementary and
 documented in the CWEB distribution; pre-compiled binary executables of the
 CWEB tools for Win32 systems are available from
 <a href="http://www.literateprogramming.com">www.literateprogramming.com</a>.

 <H3><a name="sec:SGB:Installation"></a>
 Installing the SGB
 </H3>

 After you have acquired the <a href="#sec:SGB">SGB sources</a> and have
 installed a working <a href="#sec:CWEB">CWEB system</a> (at least the
 "ctangle" processor is required), you're almost set for compiling the SGB
 sources.&nbsp; SGB is written in "old-style C," but the Boost Graph Library
 expects to handle "modern C" and C++.&nbsp; Fortunately, the SGB distribution
 comes with an appropriate set of patches that convert all the sources from
 "KR-C" to "ANSI-C," thus allowing for smooth integration of the Stanford
 GraphBase in the Boost Graph Library.

 <ul>
 <li>
 <b>Unix</b>: After extracting the SGB archive, but prior to invoking
 "<tt>make tests</tt>" and "<tt>make install</tt>," you should say
 "<tt>ln -s PROTOTYPES/*.ch .</tt>" in the root directory where you extracted
 the SGB files (or you can simply copy the change files next to the proper
 source files).&nbsp; The Unix <tt>Makefile</tt> coming with SGB conveniently
 looks for "change files" matching the SGB source files and automatically
 applies them with the "ctangle" processor.&nbsp; The resulting C files will
 smoothly run through the compiler.
 </li>
 <li>
 <b>Win32</b>: The "MSVC" subdirectory of the SGB distribution contains a
 complete set of "Developer Studio Projects" (and a single "Workspace"),
 applicable with Microsoft Developer Studio 6.&nbsp; The installation process
 is documented in the accompanying file <tt>README.MSVC</tt>.&nbsp; The "MSVC"
 contribution has been updated to make use of the "PROTOTYPES" as well, so you
 don't need to worry about that.
 </li>
 </ul>

 <H3><a name="sec:UsingSGB"></a>
 Using the SGB
 </H3>

 After you have run <a href="#sec:SGB:Installation">the installation
 process</a> of the SGB, you can use the BGL graph interface with the
 SGB <tt>Graph*</tt>, <a href="../../../boost/graph/stanford_graph.hpp"
 ><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>, which will be
 described <a href="#sec:BGL:Interface">next</a>.&nbsp; All you have to
 do is tell the C++ compiler where to look for the SGB headerfiles (by
 default, <tt>/usr/local/sgb/include</tt> on Unix and the "MSVC"
 subdirectory of the SGB installation on Win32) and the linker where to
 find the SGB static library file (<tt>libgb.a</tt> on Unix and
 <tt>libgb.lib</tt> on Win32); consult the documentation of your
 particular compiler about how to do that.

 <H3><a name="sec:SGB:Problems"></a>
 Technicalities
 </H3>

 <ul>
 <li>
 <b>Headerfile selection</b>: The two SGB modules <tt>gb_graph</tt> and
 <tt>gb_io</tt> use the preprocessor switch <tt>SYSV</tt> to select either the
 headerfile <tt>&lt;string.h&gt;</tt> (if <tt>SYSV</tt> is <tt>#define</tt>d)
 or the headerfile <tt>&lt;strings.h&gt;</tt> (if <tt>SYSV</tt> is <i>not</i>
 <tt>#define</tt>d).&nbsp; Some compilers, like <tt>gcc</tt>/<tt>g++</tt>,
 don't care much (<tt>gcc</tt> "knows" about the "string" functions without
 refering to <tt>&lt;string.h&gt;</tt>), but others, like MSVC on Win32, do (so
 all "Developer Studio Projects" in the "MSVC" subdirectory of the
 <a href="#sec:SGB">SGB distribution</a> appropriately define <tt>SYSV</tt>).
 You should be careful to set (or not) <tt>SYSV</tt> according to the needs of
 your compiler.
 </li>
 <li>
 <b>Missing include guards</b>: None of the SGB headerfiles uses "internal
 include guards" to protect itself from multiple inclusion.&nbsp; To avoid
 trouble, you must <i>not</i> <tt>#include</tt> any of the SGB headerfiles
 before or after <a href="#sec:Wrapper">the BGL wrapper</a> in a compilation
 unit; it will fully suffice to use the BGL interface.
 </li>
 <li>
 <b>Preprocessor macros</b>: The SGB headerfiles make liberal use of the
 preprocessor <i>without</i> sticking to a particular convention (like
 all-uppercase names or a particular prefix).&nbsp; At the time of writing,
 already three of these preprocessor macros collide with the conventions of
 either C++, g++, or BGL, and are fixed in <a href="#sec:Wrapper">the BGL
 wrapper</a>.&nbsp; We can not guarantee that no other preprocessor-induced
 problems may arise (but we are willing to learn about any such collisions).
 </li>
 </ul>

 <H2><a name="sec:BGL:Interface"></a>
 The BGL Interface for the SGB
 </H2>

 <H3><a name="sec:Wrapper"></a>
 Where Defined
 </H3>

 <a href="../../../boost/graph/stanford_graph.hpp"
 ><tt>&lt;boost/graph/stanford_graph.hpp&gt;</tt></a>

 <p> The main purpose of this Boost Graph Library (BGL) headerfile is to
 <tt>#include</tt> all global definitions for the general stuff of the
 <a href="#sec:SGB">Stanford GraphBase</a> (SGB) and its various graph generator
 functions by reading all <a href="#sec:SGB:Problems">SGB headerfiles</a> as in
 section 2 of the "<tt>test_sample</tt>" program.

 <p> On top of the SGB stuff, the BGL <tt>stanford_graph.hpp</tt>
 header adds and defines appropriate types and functions for using the
 SGB graphs in the BGL framework.&nbsp; Apart from the improved
 interface, the <a href="#sec:UsingSGB">SGB (static) library</a> is
 used "as is" in the context of BGL.

 <H3>
 Model Of
 </H3>

 <a href="./VertexListGraph.html">Vertex List Graph</a> and <a
 href="./PropertyGraph.html">Property Graph</a>.  The set of property
 tags that can be used with the SGB graph is described in the <a
 href="#properties">Vertex and Edge Properties</a> section below.


 <H3><a name="sec:Example"></a>
 Example
 </H3>

 The example program <a href="../example/miles_span.cpp">
 <tt>&lt;example/miles_span.cpp&gt;</tt></a> represents the first
 application of the generic framework of BGL to an SGB graph.&nbsp; It
 uses Prim's algorithm to solve the "minimum spanning tree"
 problem.&nbsp; In addition, the programs <a
 href="../../../libs/graph/example/girth.cpp">
 <tt>&lt;example/girth.cpp&gt;</tt></a> and <a
 href="../example/roget_components.cpp">
 <tt>&lt;example/roget_components.cpp&gt;</tt></a> have been ported
 from the SGB.&nbsp; We intend to implement more algorithms from SGB in
 a generic fashion and to provide the remaining example programs of SGB
 for the BGL framework.&nbsp; If you would like to help, feel free to
 submit your contributions!

 <H3>
 Associated Types
 </H3>

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::vertex_descriptor</tt><br><br>
 The type for the vertex descriptors associated with the <tt>Graph*</tt>.
 We use the type <tt>Vertex*</tt> as the vertex descriptor.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::edge_descriptor</tt><br><br> The type
 for the edge descriptors associated with the <tt>Graph*</tt>.  This is
 the type <tt>boost::sgb_edge</tt>. In addition to supporting all the
 required operations of a BGL edge descriptor, the
 <tt>boost::sgb_edge</tt> class has the following constructor.
 <pre>
    sgb_edge::sgb_edge(Arc* arc, Vertex* source)
 </pre>

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::vertex_iterator</tt><br><br>
 The type for the iterators returned by <tt>vertices()</tt>.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::out_edge_iterator</tt><br><br>
 The type for the iterators returned by <tt>out_edges()</tt>.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::adjacency_iterator</tt><br><br>
 The type for the iterators returned by <tt>adjacent_vertices()</tt>.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::vertices_size_type</tt><br><br>
 The type used for dealing with the number of vertices in the graph.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::edge_size_type</tt><br><br>
 The type used for dealing with the number of edges in the graph.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::degree_size_type</tt><br><br>
 The type used for dealing with the number of edges incident to a vertex
 in the graph.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::directed_category</tt><br><br>
 Provides information about whether the graph is directed or
 undirected. An SGB <tt>Graph*</tt> is directed so this type is
 <tt>directed_tag</tt>.

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::traversal_category</tt><br><br>
 An SGB <tt>Graph*</tt> provides traversal of the vertex set,
 out edges, and adjacent vertices. Therefore the traversal category
 tag is defined as follows:
 <pre>
 struct sgb_traversal_tag :
   public virtual vertex_list_graph_tag,
   public virtual incidence_graph_tag,
   public virtual adjacency_graph_tag { };
 </pre>

 <hr>

 <tt>graph_traits&lt;Graph*&gt;::edge_parallel_category</tt><br><br>
 This describes whether the graph class allows the insertion of parallel edges
 (edges with the same source and target).&nbsp; The SGB <tt>Graph*</tt>
 does not prevent addition of parallel edges, so this type
 is <tt>allow_parallel_edge_tag</tt>.

 <hr>

 <H3>
 Non-Member Functions
 </H3>

 <hr>

 <pre>
 std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
 vertices(Graph*&nbsp;g)
 </pre>
 Returns an iterator-range providing access to the vertex set of graph
 <tt>g</tt>.

 <hr>

 <pre>
 std::pair&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
 out_edges(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
 </pre>
 Returns an iterator-range providing access to the out-edges of vertex
 <tt>v</tt> in graph <tt>g</tt>.<br>
 There is no corresponding <tt>in_edges</tt> function.

 <hr>

 <pre>
 std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;
 adjacent_vertices(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
 </pre>
 Returns an iterator-range providing access to the adjacent vertices of vertex
 <tt>v</tt> in graph <tt>g</tt>.

 <hr>

 <pre>
 vertex_descriptor
 source(edge_descriptor&nbsp;e, Graph*&nbsp;g)
 </pre>
 Returns the source vertex of edge <tt>e</tt>.

 <hr>

 <pre>
 vertex_descriptor
 target(edge_descriptor&nbsp;e, Graph*&nbsp;g)
 </pre>
 Returns the target vertex of edge <tt>e</tt>.

 <hr>

 <pre>
 degree_size_type
 out_degree(vertex_descriptor&nbsp;v, Graph*&nbsp;g)
 </pre>
 Returns the number of edges leaving vertex <tt>v</tt>.<br>
 There is no corresponding <tt>in_degree</tt> function.

 <hr>

 <pre>
 vertices_size_type
 num_vertices(Graph*&nbsp;g)
 </pre>
 Returns the number of vertices in the graph <tt>g</tt>.

 <hr>

 <pre>
 edge_size_type
 num_edges(Graph*&nbsp;g)
 </pre>
 Returns the number of edges in the graph <tt>g</tt>.

 <hr>

 <pre>
 vertex_descriptor
 vertex(vertices_size_type&nbsp;n, Graph*&nbsp;g)
 </pre>
 Returns the (0-based) nth vertex in the graph's vertex list.

 <hr>

 <pre>
 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 property_map&lt;Graph*, PropertyTag&gt;::type
 get(PropertyTag, Graph*&amp; g)

 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 property_map&lt;Graph*, Tag&gt;::const_type
 get(PropertyTag, const Graph*&amp; g)
 </pre>
 Returns the property map object for the vertex property specified by
 <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must be one of
 the described below.

 <hr>

 <h3><a name="properties">Vertex and Edge Properties</a></h3>

 The SGB <tt>Vertex</tt> and <tt>Arc</tt> structures provide
 &quot;utility&quot; fields for storing extra information.  We provide
 BGL wrappers that provide access to these fields through <a
 href="../../property_map/doc/property_map.html">property maps</a>.  In
 addition, vertex index and edge length maps are provided. A property
 map object can be obtained from a SGB <tt>Graph*</tt> using the
 <tt>get()</tt> function described in the <a
 href="./PropertyGraph.html">Property Graph</a> concept.

 <p>
 The following list of property tags can be used to specify which
 utility field you would like a property map for.
 </p>

 <pre>
 <i>// vertex properties</i>
 template &lt;class T&gt; u_property;
 template &lt;class T&gt; v_property;
 template &lt;class T&gt; w_property;
 template &lt;class T&gt; x_property;
 template &lt;class T&gt; y_property;
 template &lt;class T&gt; z_property;

 <i>// edge properties</i>
 template &lt;class T&gt; a_property;
 template &lt;class T&gt; b_property;
 </pre>

 <p>
 The template parameter <tt>T</tt> for these tags is limited to the
 types in the <tt>util</tt> union declared in the SGB header
 <tt>gb_graph.h</tt>, which are <tt>Vertex*</tt>, <tt>Arc*</tt>,
 <tt>Graph*</tt>, <tt>char*</tt>, and <tt>long</tt>. The property maps
 for the utility fields are models of <a
 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 Map</a>.
 </p>

 <p>
 The property map for vertex indices can be obtained using the
 <tt>vertex_index_t</tt> tag, and this property map is a <a
 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 Map</a>. A property map for edge length's can be obtained using the
 <tt>edge_length_t</tt> tag, and this property map is a <a
 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 Map</a> whose value type is <tt>long</tt>.
 </p>

 <p>
 Property map objects can be obtained via the <tt>get()</tt> function
 of the Property Graph concept. The type of the property map is given
 by the <a href="./property_map.html"><tt>property_map</tt></a> traits
 class.</p>


 <HR>
 <TABLE>
 <TR valign=top>
 <TD nowrap>Copyright &copy; 2001</TD><TD>
 <A HREF="http://people.freenet.de/andreas.scherer">Andreas Scherer</A>,
 Aachen (<A
 HREF="mailto:andreas_freenet@freenet.de">andreas_freenet@freenet.de</A>)<br>
 <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>
	<HTML>
	<!--
	Copyright (C) 2001, Andreas Scherer, Jeremy Siek, Lie-Quan Lee,
	and Andrew Lumsdaine

	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: Stanford Graph Interface</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>
	Using SGB Graphs in BGL
	</H1>

	The Boost Graph Library (BGL) header, <a
	href="../../../boost/graph/stanford_graph.hpp"
	><tt><boost/graph/stanford_graph.hpp></tt></a>, adapts a
	Stanford GraphBase (SGB) <tt>Graph</tt> pointer into a BGL-compatible
	<a href="./VertexListGraph.html">VertexListGraph</a>.  Note that
	a graph adaptor <b>class</b> is <i>not</i> used; SGB's <tt>Graph*</tt>
	itself becomes a model of VertexListGraph.  The VertexListGraph
	concept is fulfilled by defining the appropriate non-member functions
	for <tt>Graph*</tt>.

	<H2><a name="sec:SGB"></a>
	The Stanford GraphBase
	</H2>

	<P>
	"The <a href="http://www-cs-staff.stanford.edu/~knuth/sgb.html">Stanford
	GraphBase</a> (SGB) is a collection of datasets and computer programs that
	generate and examine a wide variety of graphs and networks."  The SGB was
	developed and published by
	<a href="http://www-cs-staff.stanford.edu/~knuth">Donald E. Knuth</a>
	in 1993.  The fully documented source code is available for anonymous ftp
	from <a href="ftp://labrea.stanford.edu/pub/sgb/sgb.tar.gz">Stanford
	University</a> and in the book "The Stanford GraphBase, A Platform for
	Combinatorial Computing," published jointly by ACM Press and Addison-Wesley
	Publishing Company in 1993.  (This book contains several chapters with
	additional information not available in the electronic distribution.)

	<H3><a name="sec:CWEB"></a>
	Prerequisites
	</H3>

	The source code of SGB is written in accordance with the rules of the
	<a href="http://www-cs-staff.stanford.edu/~knuth/lp.html">Literate
	Programming</a> paradigm, so you need to make sure that your computer supports
	the <a href="http://www-cs-staff.stanford.edu/~knuth/cweb.html">CWEB</a>
	system.  The CWEB sources are available for anonymous ftp from
	<a href="ftp://labrea.stanford.edu/pub/cweb/cweb.tar.gz">Stanford
	University</a>.  Bootstrapping CWEB on Unix systems is elementary and
	documented in the CWEB distribution; pre-compiled binary executables of the
	CWEB tools for Win32 systems are available from
	<a href="http://www.literateprogramming.com">www.literateprogramming.com</a>.

	<H3><a name="sec:SGB:Installation"></a>
	Installing the SGB
	</H3>

	After you have acquired the <a href="#sec:SGB">SGB sources</a> and have
	installed a working <a href="#sec:CWEB">CWEB system</a> (at least the
	"ctangle" processor is required), you're almost set for compiling the SGB
	sources.  SGB is written in "old-style C," but the Boost Graph Library
	expects to handle "modern C" and C++.  Fortunately, the SGB distribution
	comes with an appropriate set of patches that convert all the sources from
	"KR-C" to "ANSI-C," thus allowing for smooth integration of the Stanford
	GraphBase in the Boost Graph Library.

	<ul>
	<li>
	<b>Unix</b>: After extracting the SGB archive, but prior to invoking
	"<tt>make tests</tt>" and "<tt>make install</tt>," you should say
	"<tt>ln -s PROTOTYPES/*.ch .</tt>" in the root directory where you extracted
	the SGB files (or you can simply copy the change files next to the proper
	source files).  The Unix <tt>Makefile</tt> coming with SGB conveniently
	looks for "change files" matching the SGB source files and automatically
	applies them with the "ctangle" processor.  The resulting C files will
	smoothly run through the compiler.
	</li>
	<li>
	<b>Win32</b>: The "MSVC" subdirectory of the SGB distribution contains a
	complete set of "Developer Studio Projects" (and a single "Workspace"),
	applicable with Microsoft Developer Studio 6.  The installation process
	is documented in the accompanying file <tt>README.MSVC</tt>.  The "MSVC"
	contribution has been updated to make use of the "PROTOTYPES" as well, so you
	don't need to worry about that.
	</li>
	</ul>

	<H3><a name="sec:UsingSGB"></a>
	Using the SGB
	</H3>

	After you have run <a href="#sec:SGB:Installation">the installation
	process</a> of the SGB, you can use the BGL graph interface with the
	SGB <tt>Graph*</tt>, <a href="../../../boost/graph/stanford_graph.hpp"
	><tt><boost/graph/stanford_graph.hpp></tt></a>, which will be
	described <a href="#sec:BGL:Interface">next</a>.  All you have to
	do is tell the C++ compiler where to look for the SGB headerfiles (by
	default, <tt>/usr/local/sgb/include</tt> on Unix and the "MSVC"
	subdirectory of the SGB installation on Win32) and the linker where to
	find the SGB static library file (<tt>libgb.a</tt> on Unix and
	<tt>libgb.lib</tt> on Win32); consult the documentation of your
	particular compiler about how to do that.

	<H3><a name="sec:SGB:Problems"></a>
	Technicalities
	</H3>

	<ul>
	<li>
	<b>Headerfile selection</b>: The two SGB modules <tt>gb_graph</tt> and
	<tt>gb_io</tt> use the preprocessor switch <tt>SYSV</tt> to select either the
	headerfile <tt><string.h></tt> (if <tt>SYSV</tt> is <tt>#define</tt>d)
	or the headerfile <tt><strings.h></tt> (if <tt>SYSV</tt> is <i>not</i>
	<tt>#define</tt>d).  Some compilers, like <tt>gcc</tt>/<tt>g++</tt>,
	don't care much (<tt>gcc</tt> "knows" about the "string" functions without
	refering to <tt><string.h></tt>), but others, like MSVC on Win32, do (so
	all "Developer Studio Projects" in the "MSVC" subdirectory of the
	<a href="#sec:SGB">SGB distribution</a> appropriately define <tt>SYSV</tt>).
	You should be careful to set (or not) <tt>SYSV</tt> according to the needs of
	your compiler.
	</li>
	<li>
	<b>Missing include guards</b>: None of the SGB headerfiles uses "internal
	include guards" to protect itself from multiple inclusion.  To avoid
	trouble, you must <i>not</i> <tt>#include</tt> any of the SGB headerfiles
	before or after <a href="#sec:Wrapper">the BGL wrapper</a> in a compilation
	unit; it will fully suffice to use the BGL interface.
	</li>
	<li>
	<b>Preprocessor macros</b>: The SGB headerfiles make liberal use of the
	preprocessor <i>without</i> sticking to a particular convention (like
	all-uppercase names or a particular prefix).  At the time of writing,
	already three of these preprocessor macros collide with the conventions of
	either C++, g++, or BGL, and are fixed in <a href="#sec:Wrapper">the BGL
	wrapper</a>.  We can not guarantee that no other preprocessor-induced
	problems may arise (but we are willing to learn about any such collisions).
	</li>
	</ul>

	<H2><a name="sec:BGL:Interface"></a>
	The BGL Interface for the SGB
	</H2>

	<H3><a name="sec:Wrapper"></a>
	Where Defined
	</H3>

	<a href="../../../boost/graph/stanford_graph.hpp"
	><tt><boost/graph/stanford_graph.hpp></tt></a>

	<p> The main purpose of this Boost Graph Library (BGL) headerfile is to
	<tt>#include</tt> all global definitions for the general stuff of the
	<a href="#sec:SGB">Stanford GraphBase</a> (SGB) and its various graph generator
	functions by reading all <a href="#sec:SGB:Problems">SGB headerfiles</a> as in
	section 2 of the "<tt>test_sample</tt>" program.

	<p> On top of the SGB stuff, the BGL <tt>stanford_graph.hpp</tt>
	header adds and defines appropriate types and functions for using the
	SGB graphs in the BGL framework.  Apart from the improved
	interface, the <a href="#sec:UsingSGB">SGB (static) library</a> is
	used "as is" in the context of BGL.

	<H3>
	Model Of
	</H3>

	<a href="./VertexListGraph.html">Vertex List Graph</a> and <a
	href="./PropertyGraph.html">Property Graph</a>. The set of property
	tags that can be used with the SGB graph is described in the <a
	href="#properties">Vertex and Edge Properties</a> section below.


	<H3><a name="sec:Example"></a>
	Example
	</H3>

	The example program <a href="../example/miles_span.cpp">
	<tt><example/miles_span.cpp></tt></a> represents the first
	application of the generic framework of BGL to an SGB graph.  It
	uses Prim's algorithm to solve the "minimum spanning tree"
	problem.  In addition, the programs <a
	href="../../../libs/graph/example/girth.cpp">
	<tt><example/girth.cpp></tt></a> and <a
	href="../example/roget_components.cpp">
	<tt><example/roget_components.cpp></tt></a> have been ported
	from the SGB.  We intend to implement more algorithms from SGB in
	a generic fashion and to provide the remaining example programs of SGB
	for the BGL framework.  If you would like to help, feel free to
	submit your contributions!

	<H3>
	Associated Types
	</H3>

	<hr>

	<tt>graph_traits<Graph*>::vertex_descriptor</tt><br><br>
	The type for the vertex descriptors associated with the <tt>Graph*</tt>.
	We use the type <tt>Vertex*</tt> as the vertex descriptor.

	<hr>

	<tt>graph_traits<Graph*>::edge_descriptor</tt><br><br> The type
	for the edge descriptors associated with the <tt>Graph*</tt>. This is
	the type <tt>boost::sgb_edge</tt>. In addition to supporting all the
	required operations of a BGL edge descriptor, the
	<tt>boost::sgb_edge</tt> class has the following constructor.
	<pre>
	sgb_edge::sgb_edge(Arc* arc, Vertex* source)
	</pre>

	<hr>

	<tt>graph_traits<Graph*>::vertex_iterator</tt><br><br>
	The type for the iterators returned by <tt>vertices()</tt>.

	<hr>

	<tt>graph_traits<Graph*>::out_edge_iterator</tt><br><br>
	The type for the iterators returned by <tt>out_edges()</tt>.

	<hr>

	<tt>graph_traits<Graph*>::adjacency_iterator</tt><br><br>
	The type for the iterators returned by <tt>adjacent_vertices()</tt>.

	<hr>

	<tt>graph_traits<Graph*>::vertices_size_type</tt><br><br>
	The type used for dealing with the number of vertices in the graph.

	<hr>

	<tt>graph_traits<Graph*>::edge_size_type</tt><br><br>
	The type used for dealing with the number of edges in the graph.

	<hr>

	<tt>graph_traits<Graph*>::degree_size_type</tt><br><br>
	The type used for dealing with the number of edges incident to a vertex
	in the graph.

	<hr>

	<tt>graph_traits<Graph*>::directed_category</tt><br><br>
	Provides information about whether the graph is directed or
	undirected. An SGB <tt>Graph*</tt> is directed so this type is
	<tt>directed_tag</tt>.

	<hr>

	<tt>graph_traits<Graph*>::traversal_category</tt><br><br>
	An SGB <tt>Graph*</tt> provides traversal of the vertex set,
	out edges, and adjacent vertices. Therefore the traversal category
	tag is defined as follows:
	<pre>
	struct sgb_traversal_tag :
	public virtual vertex_list_graph_tag,
	public virtual incidence_graph_tag,
	public virtual adjacency_graph_tag { };
	</pre>

	<hr>

	<tt>graph_traits<Graph*>::edge_parallel_category</tt><br><br>
	This describes whether the graph class allows the insertion of parallel edges
	(edges with the same source and target).  The SGB <tt>Graph*</tt>
	does not prevent addition of parallel edges, so this type
	is <tt>allow_parallel_edge_tag</tt>.

	<hr>

	<H3>
	Non-Member Functions
	</H3>

	<hr>

	<pre>
	std::pair<vertex_iterator, vertex_iterator>
	vertices(Graph* g)
	</pre>
	Returns an iterator-range providing access to the vertex set of graph
	<tt>g</tt>.

	<hr>

	<pre>
	std::pair<out_edge_iterator, out_edge_iterator>
	out_edges(vertex_descriptor v, Graph* g)
	</pre>
	Returns an iterator-range providing access to the out-edges of vertex
	<tt>v</tt> in graph <tt>g</tt>.<br>
	There is no corresponding <tt>in_edges</tt> function.

	<hr>

	<pre>
	std::pair<adjacency_iterator, adjacency_iterator>
	adjacent_vertices(vertex_descriptor v, Graph* g)
	</pre>
	Returns an iterator-range providing access to the adjacent vertices of vertex
	<tt>v</tt> in graph <tt>g</tt>.

	<hr>

	<pre>
	vertex_descriptor
	source(edge_descriptor e, Graph* g)
	</pre>
	Returns the source vertex of edge <tt>e</tt>.

	<hr>

	<pre>
	vertex_descriptor
	target(edge_descriptor e, Graph* g)
	</pre>
	Returns the target vertex of edge <tt>e</tt>.

	<hr>

	<pre>
	degree_size_type
	out_degree(vertex_descriptor v, Graph* g)
	</pre>
	Returns the number of edges leaving vertex <tt>v</tt>.<br>
	There is no corresponding <tt>in_degree</tt> function.

	<hr>

	<pre>
	vertices_size_type
	num_vertices(Graph* g)
	</pre>
	Returns the number of vertices in the graph <tt>g</tt>.

	<hr>

	<pre>
	edge_size_type
	num_edges(Graph* g)
	</pre>
	Returns the number of edges in the graph <tt>g</tt>.

	<hr>

	<pre>
	vertex_descriptor
	vertex(vertices_size_type n, Graph* g)
	</pre>
	Returns the (0-based) nth vertex in the graph's vertex list.

	<hr>

	<pre>
	template <class <a href="./PropertyTag.html">PropertyTag</a>>
	property_map<Graph*, PropertyTag>::type
	get(PropertyTag, Graph*& g)

	template <class <a href="./PropertyTag.html">PropertyTag</a>>
	property_map<Graph*, Tag>::const_type
	get(PropertyTag, const Graph*& g)
	</pre>
	Returns the property map object for the vertex property specified by
	<TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must be one of
	the described below.

	<hr>

	<h3><a name="properties">Vertex and Edge Properties</a></h3>

	The SGB <tt>Vertex</tt> and <tt>Arc</tt> structures provide
	"utility" fields for storing extra information. We provide
	BGL wrappers that provide access to these fields through <a
	href="../../property_map/doc/property_map.html">property maps</a>. In
	addition, vertex index and edge length maps are provided. A property
	map object can be obtained from a SGB <tt>Graph*</tt> using the
	<tt>get()</tt> function described in the <a
	href="./PropertyGraph.html">Property Graph</a> concept.

	<p>
	The following list of property tags can be used to specify which
	utility field you would like a property map for.
	</p>

	<pre>
	<i>// vertex properties</i>
	template <class T> u_property;
	template <class T> v_property;
	template <class T> w_property;
	template <class T> x_property;
	template <class T> y_property;
	template <class T> z_property;

	<i>// edge properties</i>
	template <class T> a_property;
	template <class T> b_property;
	</pre>

	<p>
	The template parameter <tt>T</tt> for these tags is limited to the
	types in the <tt>util</tt> union declared in the SGB header
	<tt>gb_graph.h</tt>, which are <tt>Vertex</tt>, <tt>Arc</tt>,
	<tt>Graph</tt>, <tt>char</tt>, and <tt>long</tt>. The property maps
	for the utility fields are models of <a
	href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
	Map</a>.
	</p>

	<p>
	The property map for vertex indices can be obtained using the
	<tt>vertex_index_t</tt> tag, and this property map is a <a
	href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
	Map</a>. A property map for edge length's can be obtained using the
	<tt>edge_length_t</tt> tag, and this property map is a <a
	href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
	Map</a> whose value type is <tt>long</tt>.
	</p>

	<p>
	Property map objects can be obtained via the <tt>get()</tt> function
	of the Property Graph concept. The type of the property map is given
	by the <a href="./property_map.html"><tt>property_map</tt></a> traits
	class.</p>


	<HR>
	<TABLE>
	<TR valign=top>
	<TD nowrap>Copyright © 2001</TD><TD>
	<A HREF="http://people.freenet.de/andreas.scherer">Andreas Scherer</A>,
	Aachen (<A
	HREF="mailto:andreas_freenet@freenet.de">andreas_freenet@freenet.de</A>)<br>
	<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>