[ceph.git] / ceph / src / boost / libs / graph / doc / stanford_graph.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>&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>
Commit	Line	Data
7c673cae FG	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><boost/graph/stanford_graph.hpp></tt></a>, adapts a
	26	Stanford GraphBase (SGB) <tt>Graph</tt> pointer into a BGL-compatible
	27	<a href="./VertexListGraph.html">VertexListGraph</a>.  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.  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."  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.  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.  (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.  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>.  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.  SGB is written in "old-style C," but the Boost Graph Library
73	expects to handle "modern C" and C++.  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).  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.  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.  The installation process
93	is documented in the accompanying file <tt>README.MSVC</tt>.  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><boost/graph/stanford_graph.hpp></tt></a>, which will be
107	described <a href="#sec:BGL:Interface">next</a>.  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><string.h></tt> (if <tt>SYSV</tt> is <tt>#define</tt>d)
124	or the headerfile <tt><strings.h></tt> (if <tt>SYSV</tt> is <i>not</i>
125	<tt>#define</tt>d).  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><string.h></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.  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).  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>.  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><boost/graph/stanford_graph.hpp></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.  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><example/miles_span.cpp></tt></a> represents the first
190	application of the generic framework of BGL to an SGB graph.  It
191	uses Prim's algorithm to solve the "minimum spanning tree"
192	problem.  In addition, the programs <a
193	href="../../../libs/graph/example/girth.cpp">
194	<tt><example/girth.cpp></tt></a> and <a
195	href="../example/roget_components.cpp">
196	<tt><example/roget_components.cpp></tt></a> have been ported
197	from the SGB.  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.  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<Graph*>::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<Graph*>::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<Graph*>::vertex_iterator</tt><br><br>
226	The type for the iterators returned by <tt>vertices()</tt>.
227
228	<hr>
229
230	<tt>graph_traits<Graph*>::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<Graph*>::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<Graph*>::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<Graph*>::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<Graph*>::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<Graph*>::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<Graph*>::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<Graph*>::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).  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<vertex_iterator, vertex_iterator>
292	vertices(Graph* 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<out_edge_iterator, out_edge_iterator>
301	out_edges(vertex_descriptor v, Graph* 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<adjacency_iterator, adjacency_iterator>
311	adjacent_vertices(vertex_descriptor v, Graph* 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 e, Graph* 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 e, Graph* 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 v, Graph* 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* 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* 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 n, Graph* g)
362	</pre>
363	Returns the (0-based) nth vertex in the graph's vertex list.
364
365	<hr>
366
367	<pre>
368	template <class <a href="./PropertyTag.html">PropertyTag</a>>
369	property_map<Graph*, PropertyTag>::type
370	get(PropertyTag, Graph*& g)
371
372	template <class <a href="./PropertyTag.html">PropertyTag</a>>
373	property_map<Graph*, Tag>::const_type
374	get(PropertyTag, const Graph*& 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	"utility" 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 <class T> u_property;
401	template <class T> v_property;
402	template <class T> w_property;
403	template <class T> x_property;
404	template <class T> y_property;
405	template <class T> z_property;
406
407	<i>// edge properties</i>
408	template <class T> a_property;
409	template <class T> 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 © 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>