| <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 |
| refering 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="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> |