Using SGB Graphs in BGL
The Boost Graph Library (BGL) header, <boost/graph/stanford_graph.hpp>, adapts a
Stanford GraphBase (SGB) Graph pointer into a BGLcompatible
VertexListGraph. Note that
a graph adaptor class is not used; SGB's Graph*
itself becomes a model of VertexListGraph. The VertexListGraph
concept is fulfilled by defining the appropriate nonmember functions
for Graph*.
The Stanford GraphBase
"The Stanford
GraphBase (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
Donald E. Knuth
in 1993. The fully documented source code is available for anonymous ftp
from Stanford
University and in the book "The Stanford GraphBase, A Platform for
Combinatorial Computing," published jointly by ACM Press and AddisonWesley
Publishing Company in 1993. (This book contains several chapters with
additional information not available in the electronic distribution.)
Prerequisites
The source code of SGB is written in accordance with the rules of the
Literate
Programming paradigm, so you need to make sure that your computer supports
the CWEB
system. The CWEB sources are available for anonymous ftp from
Stanford
University. Bootstrapping CWEB on Unix systems is elementary and
documented in the CWEB distribution; precompiled binary executables of the
CWEB tools for Win32 systems are available from
www.literateprogramming.com.
Installing the SGB
After you have acquired the SGB sources and have
installed a working CWEB system (at least the
"ctangle" processor is required), you're almost set for compiling the SGB
sources. SGB is written in "oldstyle 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
"KRC" to "ANSIC," thus allowing for smooth integration of the Stanford
GraphBase in the Boost Graph Library.

Unix: After extracting the SGB archive, but prior to invoking
"make tests" and "make install," you should say
"ln s PROTOTYPES/*.ch ." 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 Makefile 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.

Win32: 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 README.MSVC. The "MSVC"
contribution has been updated to make use of the "PROTOTYPES" as well, so you
don't need to worry about that.
Using the SGB
After you have run the installation
process of the SGB, you can use the BGL graph interface with the
SGB Graph*, <boost/graph/stanford_graph.hpp>, which will be
described next. All you have to
do is tell the C++ compiler where to look for the SGB headerfiles (by
default, /usr/local/sgb/include on Unix and the "MSVC"
subdirectory of the SGB installation on Win32) and the linker where to
find the SGB static library file (libgb.a on Unix and
libgb.lib on Win32); consult the documentation of your
particular compiler about how to do that.
Technicalities

Headerfile selection: The two SGB modules gb_graph and
gb_io use the preprocessor switch SYSV to select either the
headerfile <string.h> (if SYSV is #defined)
or the headerfile <strings.h> (if SYSV is not
#defined). Some compilers, like gcc/g++,
don't care much (gcc "knows" about the "string" functions without
referring to <string.h>), but others, like MSVC on Win32, do (so
all "Developer Studio Projects" in the "MSVC" subdirectory of the
SGB distribution appropriately define SYSV).
You should be careful to set (or not) SYSV according to the needs of
your compiler.

Missing include guards: None of the SGB headerfiles uses "internal
include guards" to protect itself from multiple inclusion. To avoid
trouble, you must not #include any of the SGB headerfiles
before or after the BGL wrapper in a compilation
unit; it will fully suffice to use the BGL interface.

Preprocessor macros: The SGB headerfiles make liberal use of the
preprocessor without sticking to a particular convention (like
alluppercase 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 the BGL
wrapper. We can not guarantee that no other preprocessorinduced
problems may arise (but we are willing to learn about any such collisions).
The BGL Interface for the SGB
Where Defined
<boost/graph/stanford_graph.hpp>
The main purpose of this Boost Graph Library (BGL) headerfile is to
#include all global definitions for the general stuff of the
Stanford GraphBase (SGB) and its various graph generator
functions by reading all SGB headerfiles as in
section 2 of the "test_sample" program.
On top of the SGB stuff, the BGL stanford_graph.hpp
header adds and defines appropriate types and functions for using the
SGB graphs in the BGL framework. Apart from the improved
interface, the SGB (static) library is
used "as is" in the context of BGL.
Model Of
Vertex List Graph and Property Graph. The set of property
tags that can be used with the SGB graph is described in the Vertex and Edge Properties section below.
Example
The example program
<example/miles_span.cpp> 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
<example/girth.cpp> and
<example/roget_components.cpp> 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!
Associated Types
graph_traits<Graph*>::vertex_descriptor
The type for the vertex descriptors associated with the Graph*.
We use the type Vertex* as the vertex descriptor.
graph_traits<Graph*>::edge_descriptor
The type
for the edge descriptors associated with the Graph*. This is
the type boost::sgb_edge. In addition to supporting all the
required operations of a BGL edge descriptor, the
boost::sgb_edge class has the following constructor.
sgb_edge::sgb_edge(Arc* arc, Vertex* source)
graph_traits<Graph*>::vertex_iterator
The type for the iterators returned by vertices().
graph_traits<Graph*>::out_edge_iterator
The type for the iterators returned by out_edges().
graph_traits<Graph*>::adjacency_iterator
The type for the iterators returned by adjacent_vertices().
graph_traits<Graph*>::vertices_size_type
The type used for dealing with the number of vertices in the graph.
graph_traits<Graph*>::edge_size_type
The type used for dealing with the number of edges in the graph.
graph_traits<Graph*>::degree_size_type
The type used for dealing with the number of edges incident to a vertex
in the graph.
graph_traits<Graph*>::directed_category
Provides information about whether the graph is directed or
undirected. An SGB Graph* is directed so this type is
directed_tag.
graph_traits<Graph*>::traversal_category
An SGB Graph* provides traversal of the vertex set,
out edges, and adjacent vertices. Therefore the traversal category
tag is defined as follows:
struct sgb_traversal_tag :
public virtual vertex_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag { };
graph_traits<Graph*>::edge_parallel_category
This describes whether the graph class allows the insertion of parallel edges
(edges with the same source and target). The SGB Graph*
does not prevent addition of parallel edges, so this type
is allow_parallel_edge_tag.
NonMember Functions
std::pair<vertex_iterator, vertex_iterator>
vertices(Graph* g)
Returns an iteratorrange providing access to the vertex set of graph
g.
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor v, Graph* g)
Returns an iteratorrange providing access to the outedges of vertex
v in graph g.
There is no corresponding in_edges function.
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor v, Graph* g)
Returns an iteratorrange providing access to the adjacent vertices of vertex
v in graph g.
vertex_descriptor
source(edge_descriptor e, Graph* g)
Returns the source vertex of edge e.
vertex_descriptor
target(edge_descriptor e, Graph* g)
Returns the target vertex of edge e.
degree_size_type
out_degree(vertex_descriptor v, Graph* g)
Returns the number of edges leaving vertex v.
There is no corresponding in_degree function.
vertices_size_type
num_vertices(Graph* g)
Returns the number of vertices in the graph g.
edge_size_type
num_edges(Graph* g)
Returns the number of edges in the graph g.
vertex_descriptor
vertex(vertices_size_type n, Graph* g)
Returns the (0based) nth vertex in the graph's vertex list.
template <class PropertyTag>
property_map<Graph*, PropertyTag>::type
get(PropertyTag, Graph*& g)
template <class PropertyTag>
property_map<Graph*, Tag>::const_type
get(PropertyTag, const Graph*& g)
Returns the property map object for the vertex property specified by
PropertyTag. The PropertyTag must be one of
the described below.
The SGB Vertex and Arc structures provide
"utility" fields for storing extra information. We provide
BGL wrappers that provide access to these fields through property maps. In
addition, vertex index and edge length maps are provided. A property
map object can be obtained from a SGB Graph* using the
get() function described in the Property Graph concept.
The following list of property tags can be used to specify which
utility field you would like a property map for.
// vertex properties
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;
// edge properties
template <class T> a_property;
template <class T> b_property;
The template parameter T for these tags is limited to the
types in the util union declared in the SGB header
gb_graph.h, which are Vertex*, Arc*,
Graph*, char*, and long. The property maps
for the utility fields are models of Lvalue Property
Map.
The property map for vertex indices can be obtained using the
vertex_index_t tag, and this property map is a Readable Property
Map. A property map for edge length's can be obtained using the
edge_length_t tag, and this property map is a Lvalue Property
Map whose value type is long.
Property map objects can be obtained via the get() function
of the Property Graph concept. The type of the property map is given
by the property_map traits
class.