123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458 |
- <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>
|