459 lines
16 KiB
HTML
459 lines
16 KiB
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
|
|
referring 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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|