[Boost-commit] svn:boost r7421

From: asutton_at_[hidden]
Date: 2007-07-13 12:35:57

Author: asutton
Date: 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
New Revision: 7421
URL: http://svn.boost.org/trac/boost/changeset/7421

Log:
Wrote some more documentation
Implemnented an algorithm for finding all cycles in a graph (more or less,
it has some problems, but I've documented them).

Added:
   sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
   sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp              |     6 +                                       
   sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp                   |    21 ++++++                                  
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk        |   122 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk |     5                                         
   sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2                          |    12 +++                                     
   sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp                        |     4                                         
   6 files changed, 161 insertions(+), 9 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -37,7 +37,8 @@
                     directed_tag)
 
         {
-            return (edge(u, v, g).second ? 1 : 0) + (edge(v, u, g).second ? 1 : 0);
+            return (edge(u, v, g).second ? 1 : 0) +
+                   (edge(v, u, g).second ? 1 : 0);
         }
 
         // This template matches undirectedS
@@ -67,6 +68,9 @@
         return ret;
     }
 
+    // This is seriously flawed for directed graphs...
+    // Adjacenct vertices correspond to out degrees.
+
     template <typename Graph>
     inline size_t
     num_centered_triangles(const Graph& g,

Added: sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/cycle.hpp	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -0,0 +1,295 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_CYCLE_HXX
+#define BOOST_GRAPH_CYCLE_HXX
+
+#include <vector>
+#include <limits>
+
+#include <boost/utility.hpp>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost
+{
+
+    // The implementation of this algorithm is a reproduction of the Teirnan
+    // approach for directed graphs: bibtex follows
+    //
+    //     @article{362819,
+    //         author = {James C. Tiernan},
+    //         title = {An efficient search algorithm to find the elementary circuits of a graph},
+    //         journal = {Commun. ACM},
+    //         volume = {13},
+    //         number = {12},
+    //         year = {1970},
+    //         issn = {0001-0782},
+    //         pages = {722--726},
+    //         doi = {http://doi.acm.org/10.1145/362814.362819},
+    //             publisher = {ACM Press},
+    //             address = {New York, NY, USA},
+    //         }
+    //
+    // It should be pointed out that the author does not provide a complete analysis for
+    // either time or space. This is in part, due to the fact that it's a fairly input
+    // sensitive problem related to the density and construction of the graph, not just
+    // its size.
+    //
+    // I've also taken some liberties with the interpretation of the algorithm - I've
+    // basically modernized it to use real data structures (no more arrays and matrices).
+    // Oh... and there's explicit control structures - not just gotos.
+    //
+    // The problem is definitely NP-complete, an an unbounded implementation of this
+    // will probably run for quite a while (i.e.) on a large graph. The conclusions
+    // of this paper alkso reference a Paton algorithm for undirected graphs as being
+    // much more efficient (apparently based on spanning trees). Although not implemented,
+    // it can be found here:
+    //
+    //     @article{363232,
+    //         author = {Keith Paton},
+    //         title = {An algorithm for finding a fundamental set of cycles of a graph},
+    //         journal = {Commun. ACM},
+    //         volume = {12},
+    //         number = {9},
+    //         year = {1969},
+    //         issn = {0001-0782},
+    //         pages = {514--518},
+    //         doi = {http://doi.acm.org/10.1145/363219.363232},
+    //             publisher = {ACM Press},
+    //             address = {New York, NY, USA},
+    //         }
+
+    // TODO: The algorithm, as presented, suffers from a number of disappoinments (not
+    // just being slow. It only really works on the most simple directed and undirected
+    // graphs. Because of the requirement on increasingly large vertex indices, the
+    // algorithm will never follow bidirected or reflexive edges. This failure causes
+    // the algorithm to miss a number cycles that end up bridging those reflexive
+    // humps.
+    //
+    // An interesting tradeoff would be to remove the test for increasing indices
+    // in detail::ignore_vertex(), causing the algorithm to visit every permutation
+    // of each cycle - that actually hits them all. Some extra work could be done
+    // mapping permuations into combinations - if you really want to.
+    //
+    // However, I should point out that this never miscomputes triangles - which
+    // is what I'd intended it for.
+
+    struct cycle_visitor
+    {
+        template <class Vertex, class Graph>
+        inline void start_vertex(Vertex v, Graph& g)
+        { }
+
+        template <class Vertex, class Graph>
+        inline void finish_vertex(Vertex v, Graph& g)
+        { }
+
+        template <class Path, class Graph>
+        inline void cycle(const Path& p, Graph& g)
+        { }
+    };
+
+    struct cycle_counter
+        : public cycle_visitor
+    {
+        cycle_counter(std::size_t& num)
+            : m_num(num)
+        { }
+
+        template <class Path, class Graph>
+        inline void cycle(const Path& p, Graph& g)
+        { ++m_num; }
+
+        size_t& m_num;
+    };
+
+    namespace detail
+    {
+        template <typename Graph, typename Path>
+        inline bool
+        is_in_path(const Graph&,
+                   typename graph_traits<Graph>::vertex_descriptor v,
+                   const Path& p)
+        {
+            return (std::find(p.begin(), p.end(), v) != p.end());
+        }
+
+        template <typename Graph, typename ClosedMatrix>
+        inline bool
+        is_path_closed(const Graph& g,
+                       typename graph_traits<Graph>::vertex_descriptor u,
+                       typename graph_traits<Graph>::vertex_descriptor v,
+                       const ClosedMatrix& closed)
+        {
+            // the path from u to v is closed if v can be found in the list
+            // of closed vertices associated with u.
+            typedef typename ClosedMatrix::const_reference Row;
+            Row r = closed[get(vertex_index, g, u)];
+            if(find(r.begin(), r.end(), v) != r.end()) {
+                return true;
+            }
+            return false;
+        }
+
+        template <typename Graph, typename Path, typename ClosedMatrix>
+        inline bool
+        ignore_vertex(const Graph& g,
+                      typename graph_traits<Graph>::vertex_descriptor u,
+                      typename graph_traits<Graph>::vertex_descriptor v,
+                      const Path& p,
+                      const ClosedMatrix& m)
+        {
+            // for undirected graphs, we're actually going to follow the
+            // original algorithm and disallow back-tracking over the
+            // undirected edge.
+            return get(vertex_index, g, v) < get(vertex_index, g, u) ||
+                   is_in_path(g, v, p) ||
+                   is_path_closed(g, u, v, m);
+        }
+
+        template <typename Graph, typename Path, typename ClosedMatrix>
+        inline typename graph_traits<Graph>::vertex_descriptor
+        extend_path(const Graph& g, Path& p, ClosedMatrix& closed)
+        {
+            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+            typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
+
+            // basically, p is a sequence of vertex descriptors.
+            // we want to find an adjacent vertex that the path
+            // can extend over.
+
+            // get the current vertex
+            Vertex u = p.back();
+            Vertex ret = graph_traits<Graph>::null_vertex();
+
+            AdjacencyIterator i, end;
+            for(tie(i, end) = adjacent_vertices(u, g); i != end; ++i) {
+                Vertex v = *i;
+                if(ignore_vertex(g, u, v, p, closed)) {
+                    continue;
+                }
+
+                // if we get here, we've actually satisfied the loop
+                // so we can just break and return
+                p.push_back(v);
+                ret = v;
+                break;
+            }
+            return ret;
+        }
+
+        template <typename Graph, typename Path, typename ClosedMatrix>
+        inline bool
+        exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
+        {
+            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+            // if there's more than one vertex in the path, this closes
+            // of some possible routes and returns true. otherwise, if there's
+            // only one vertex left, the vertex has been used up
+            if(p.size() > 1) {
+                // get the last and second to last vertices, popping the last
+                // vertex off the path
+                Vertex last, prev;
+                last = p.back();
+                p.pop_back();
+                prev = p.back();
+
+                // reset the closure for the last vertex of the path and
+                // indicate that the last vertex in p is now closed to
+                // the next-to-last vertex in p
+                closed[get(vertex_index, g, last)].clear();
+                closed[get(vertex_index, g, prev)].push_back(last);
+                return true;
+            }
+            else {
+                return false;
+            }
+        }
+    }
+
+    // TODO: I may need to templatize the path type - it would add a little extra
+    // flexibility, but I'm not certain its a great idea.
+
+    template <typename Graph, typename Visitor>
+    inline void
+    visit_cycles(const Graph& g,
+                 Visitor vis,
+                 std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
+                 std::size_t minlen = 3)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        typedef std::vector<Vertex> Path;
+        typedef std::vector<Vertex> VertexList;
+        typedef std::vector<VertexList> ClosedMatrix;
+
+        // closed contains the list of vertices that are "closed" to a vertex. this
+        // is a kind of strange half-mapped matrix. rows are indexed by vertex, but
+        // the columns are not - they simply store the list of vertices that are
+        // closed to the vertex represented by the row.
+
+        const Vertex null = graph_traits<Graph>::null_vertex();
+
+        VertexIterator i, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            Path p;
+            ClosedMatrix closed(num_vertices(g), VertexList());
+            p.push_back(*i);
+
+            vis.start_vertex(*i, g);
+
+            while(1) {
+                // extend the path until we've reached the end or the maximum
+                // sized cycle
+                Vertex j = null;
+                while(((j = detail::extend_path(g, p, closed)) != null)
+                       && (p.size() < maxlen))
+                    ; // empty loop
+
+                // at this point, we need to see if there's a cycle
+                if(edge(p.back(), p.front(), g).second) {
+                    if(p.size() >= minlen) {
+                        vis.cycle(p, g);
+                    }
+                }
+
+                if(!detail::exhaust_paths(g, p, closed)) {
+                    break;
+                }
+            }
+
+            vis.finish_vertex(*i, g);
+        }
+    }
+
+    template <typename Graph>
+    inline size_t
+    count_cycles(const Graph& g,
+                 std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
+                 std::size_t minlen = 3)
+    {
+        size_t ret = 0;
+        visit_triangles(g, cycle_counter(ret), maxlen, minlen);
+        return ret;
+    }
+
+    template <typename Graph, typename Visitor>
+    inline void
+    visit_triangles(const Graph& g, Visitor vis)
+    { visit_cycles(g, vis, 3, 3); }
+
+    template <typename Graph>
+    inline size_t
+    count_triangles(const Graph& g)
+    {
+        size_t ret = 0;
+        visit_triangles(g, cycle_counter(ret));
+        return ret;
+    }
+}
+
+#endif

Modified: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -25,8 +25,9 @@
         // property vectors. Otherwise, the descriptor is generally a void-cast
         // pointer to the stored element.
 
-        // Edge descriptors are a little different. They may be required to
-        // be in associative maps.
+        // TODO: Edge descriptors are a little different. They may be required to
+        // be in associative maps regardless of actual type (maybe). There's not
+        // a single example of using exterior edge properties in Boost.Graph.
 
         template <typename Vertex, typename Value>
         struct choose_ext_vprop_container
@@ -66,6 +67,22 @@
             detail::choose_ext_vprop_map<Graph, container_type>::type
             map_type;
     };
+
+    // These functions are needed to abstract the initialization sequence.
+    // If you know the actual container type of your exerior property, then
+    // you skip these functions. If you don't and you're declaring these
+    // generically, then you _must_ use these to ensure correct initialiation
+    // of the property map.
+
+    template <typename Key, typename Value>
+    static inline std::tr1::unordered_map<Key, Value>&
+    make_property_map(std::tr1::unordered_map<Key, Value>& c)
+    { return c; }
+
+    template <typename Value>
+    static inline typename std::vector<Value>::iterator
+    make_property_map(std::vector<Value>& c)
+    { return c.begin(); }
 }
 
 #endif

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -105,14 +105,130 @@
 [include property_graph.qbk]
 [include mutable_property_graph.qbk]
 
+[h3 Pseudo-Concepts]
+The concepts above describe the type and functional requirements of graphs. However,
+these do not directly common concepts such as "directed graph" or "multigraph". As
+such, there are a number of pseudo-concepts with which we can also describe graph objects.
+
+[h4 Directed and Undirected Graphs]
+The interface that Boost.Graph provides for accessing and manipulating an undirected
+graph is the same as the interface for directed graphs described in the following
+sections, however there are some differences in the behaviour and semantics. For example,
+in a directed graph we can talk about out-edges and in-edges of a vertex. In an
+undirected graph there is no "in" and "out", there are just edges incident to a vertex.
+Nevertheless, in Boost.Graph we still use the `out_edges()` function (or `in_edges()`)
+to access the incident edges in an undirected graph. Similarly, an undirected edge has
+no "source" and "target" but merely an unordered pair of vertices, but we still use
+`source()` and `target()` to access these vertices. The reason Boost.Graph does not
+provide a separate interface for undirected graphs is that many algorithms on directed
+graphs also work on undirected graphs, and it would be inconvenient to have to duplicate
+the algorithms just because of an interface difference. When using undirected graphs
+just mentally disregard the directionality in the function names. The example below
+demonstrates using the `out_edges()`, `source()`, and `target()` with an undirected
+graph. The source code for this example and the following one can be found in
+`examples/undirected.cpp`.
+
+
+    const int V = 2;
+    typedef ... UndirectedGraph;
+    UndirectedGraph graph(V);
+
+    std::cout << "the edges incident to v: ";
+    boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
+    boost::graph_traits<UndirectedGraph>::vertex_descriptor  s = vertex(0, graph);
+    for(tie(e, e_end) = out_edges(s, graph); e != e_end; ++e) {
+        std::cout << "(" << source(*e, graph)
+                  << "," << target(*e, graph)
+                  << ")" << endl;
+    }
+
+Even though the interface is the same for undirected graphs, there are some behavioral
+differences because edge equality is defined differently. In a directed graph,
+edge /(u,v)/ is never equal to edge /(v,u)/, but in an undirected graph they may
+be equal. If the undirected graph is a multigraph then /(u,v)/ and /(v,u)/ might be
+parallel edges. If the graph is not a multigraph then /(u,v)/ and /(v,u)/ must be the
+same edge.
+
+In the example below the edge equality test will return false for the directed graph
+and true for the undirected graph. The difference also affects the meaning of `add_edge()`.
+In the example below, if we had also written `add_add(v, u, graph)`, this would have
+added a parallel edge between `u` and `v` (provided the graph type allows parallel edges -
+which most do). The difference in edge equality also affects the association of edge
+properties. In the directed graph, the edges /(u,v)/ and /(v,u)/ can have distinct
+weight values, whereas in the undirected graph the weight of /(u,v)/ is the same as
+the weight of /(v,u)/ since they are the same edge.
+
+    typedef ... DirectedGraph;
+    typedef ... UndirectedGraph;
+
+    DirectedGraph digraph(V);
+    UndirectedGraph graph(V)
+
+    {
+        boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
+        u = vertex(0, digraph);
+        v = vertex(1, digraph);
+        add_edge(digraph, u, v, Weight(1.2));
+        add_edge(digraph, v, u, Weight(2.4));
+        boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
+        bool found;
+        tie(e1, found) = edge(u, v, digraph);
+        tie(e2, found) = edge(v, u, digraph);
+        std::cout << "in a directed graph is ";
+        std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+        property_map<DirectedGraph, edge_weight_t>::type
+        weight = get(edge_weight, digraph);
+        cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+        cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+    }
+
+    {
+        boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
+        u = vertex(0, graph);
+        v = vertex(1, graph);
+        add_edge(graph, u, v, Weight(3.1));
+        boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
+        bool found;
+        tie(e1, found) = edge(u, v, graph);
+        tie(e2, found) = edge(v, u, graph);
+        std::cout << "in an undirected graph is ";
+        std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+        property_map<UndirectedGraph, edge_weight_t>::type
+        weight = get(edge_weight, graph);
+        cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+        cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+    }
+
+The output is:
+
+[pre
+in a directed graph is (u,v) == (v,u) ? 0
+weight\[(u,v)\] = 1.2
+weight\[(v,u)\] = 2.4
+in an undirected graph is (u,v) == (v,u) ? 1
+weight\[(u,v)\] = 3.1
+weight\[(v,u)\] = 3.1
+]
+
+[h4 Multigraphs]
+A /multigraph/ is a graph (either directed or undirected) that has parallel edges
+between vertices. The Boost.Graph types are mostly unrestrictive about the addition
+of parallel edges, meaning that it is fairly easy to actually create multigraphs
+without any additional work.
+
+There are certain sets of graph types that do not allow the addition of parallel edges.
+Specifically, if the EdgeList and OutEdgeList of an [boost_adjacency_list] models an
+associative container, then the graph cannont be a multigraph.
+
+*Document this a little better*
+
 [h3 Indexed Graphs]
 Although not explicitly documented (yet), there's a concept of a Vertex-Indexed graph
 that has some valid expressions related specifically to operations on vertex index
 property of the graph. The [boost_undirected_graph] class has some addiitonal methods
 that can also be ported.
 
-[h3 Undirected Graphs]
-
-Lots of stuff here on undirected graphs...
 
 [endsect]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -6,6 +6,7 @@
  /]
 
 [section Connectivity Measures]
+
     size_t connectivity(
         _graph,
         _component_map,
@@ -13,8 +14,8 @@
         _vertex_index_map = not_given(),
         _components = not_given())
 
-The `connectivity()` algorithm is essentially a wrapper around the
-[boost_connected_components] algorithm, but provides additional (and optional)
+The `connectivity()` algorithm is a wrapper around the [boost_connected_components]
+algorithm, that provides some convenience for working with resultant concept maps.
 functionality for working with connected components. The parameters have, with
 the exeption of `_components`, the same purpose and requirements as
 documented in [boost_connected_components].

Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -47,3 +47,15 @@
     : <include>$BOOST_ROOT
     : <include>../../../
     ;
+
+exe exterior
+    : exterior.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;
+
+exe cycle
+    : cycle.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;

Added: sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -0,0 +1,94 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <vector>
+#include <map>
+#include <tr1/unordered_map>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/cycle.hpp>
+#include <boost/graph/generators/cycle_graph.hpp>
+#include <boost/graph/generators/prism_graph.hpp>
+#include <boost/graph/generators/complete_graph.hpp>
+
+using namespace std;
+using namespace boost;
+using namespace __cxxabiv1;
+
+struct cycle_printer : public cycle_visitor
+{
+    template <typename Path, typename Graph>
+    void cycle(const Path& p, const Graph& g)
+    {
+        cout << "path: ";
+        for(typename Path::const_iterator i = p.begin(); i != p.end(); ++i) {
+            cout << get(vertex_index, g, *i) << " ";
+        }
+        cout << "\n";
+    };
+};
+
+template <typename Graph>
+void build_graph(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+
+    static const unsigned N = 5;
+    vector<Vertex> v(N);
+
+    // add some vertices
+    for(size_t i = 0; i < N; ++i) {
+        // v[i] = add_vertex(g);
+        v[i] = add_vertex(g);
+    }
+
+    // add some edges (with weights)
+    add_edge(v[0], v[1], g);
+    add_edge(v[1], v[2], g);
+    add_edge(v[2], v[0], g);
+
+    add_edge(v[0], v[3], g);
+    add_edge(v[3], v[4], g);
+    add_edge(v[4], v[0], g);
+};
+
+void test_1()
+{
+    typedef directed_graph<> Graph;
+
+    Graph g;
+    // build_graph(g);
+    make_prism_graph(g, 4, 3, with_bidirected_cycle(), with_bidirected_spokes());
+    // make_complete_graph(g, 4);
+
+    visit_cycles(g, cycle_printer());
+    std::cout << "number of triangles: " << count_triangles(g) << "\n";
+}
+
+void test_2()
+{
+    typedef undirected_graph<> Graph;
+
+    Graph g;
+    // build_graph(g);
+    make_prism_graph(g, 3, 2);
+
+    visit_cycles(g, cycle_printer());
+    std::cout << "number of triangles: " << count_triangles(g) << "\n";
+}
+
+
+int
+main(int argc, char *argv[])
+{
+    test_1();
+    // test_2();
+}

Modified: sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp	2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -156,7 +156,9 @@
     test_wheel<Graph>();
     test_prism<Graph>();
     */
-    test_web<Graph>();
+    // test_web<Graph>();
+
+    test_prism<DiGraph>(with_clockwise_cycle(), with_bidirected_spokes());
 
     /*
     test_path<DiGraph>(with_forward_edges());