Boost Graph Library: Stanford Graph Interface

# 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 `#define`d) or the headerfile `<strings.h>` (if `SYSV` is not `#define`d). 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 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.

Copyright © 2001 | Andreas Scherer, Aachen (andreas_freenet@freenet.de) Jeremy Siek, Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)