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 BGL-compatible 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 non-member 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 Addison-Wesley 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; pre-compiled 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 "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.

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 refering 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 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 the BGL wrapper. We can not guarantee that no other preprocessor-induced 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.

Non-Member Functions

std::pair<vertex_iterator, vertex_iterator>
vertices(Graph* g)

Returns an iterator-range 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 iterator-range providing access to the out-edges 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 iterator-range 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 (0-based) 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.

Vertex and Edge Properties

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.

Andreas Scherer, Aachen ([email protected])
Jeremy Siek, Indiana University ([email protected])
Lie-Quan Lee, Indiana University ([email protected])
Andrew Lumsdaine, Indiana University ([email protected])