[Boost-commit] svn:boost r7399

From: asutton_at_[hidden]
Date: 2007-07-09 11:45:36

Author: asutton
Date: 2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
New Revision: 7399
URL: http://svn.boost.org/trac/boost/changeset/7399

Log:
Implemented a clustering coefficient measure for both vertices and
the graph as a whole (it could be faster for the graph, there's lots
of recomputations).
Implmented a bunch of generators for standard graphs (I got kind of
bored and wanted something different to do).

Added:
   sandbox/SOC/2007/graphs/boost/graph/generators/
   sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp
   sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp
   sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp
   sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp
   sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp
   sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp
   sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp |   248 +++++++++++++++------------------------ 
   sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2             |    11 +                                       
   2 files changed, 109 insertions(+), 150 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-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -1,164 +1,112 @@
+// (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 CLUSTERING_COEFFICIENT_HXX
-#define CLUSTERING_COEFFICIENT_HXX
+#ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HXX
+#define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HXX
 
-// std includes
-#include <utility>
-#include <algorithm>
-
-/**
- * The num_centered_triples() method computes the number of connected triples
- * centered at the given vertex. This can also be described as the number
- * of length 2 paths through the given vertex. This value is actually easy
- * to compute as choose(k, 2) where k is the size of the vertices neighborhood.
- *
- * This could be written a little more correctly since the vertex type is
- * actually an associated type of the graph. I'm lazy and the parameter list
- * looked a little long.
- */
-template <
-    typename AdjacencyGraph,
-    typename AdjacencyVertex
-    >
-size_t
-num_centered_triples(AdjacencyVertex const& v, AdjacencyGraph const& g)
-{
-    using namespace std;
-    using namespace boost;
-
-    typedef AdjacencyGraph graph;
-    typedef AdjacencyVertex vertex;
-    typedef typename graph_traits<graph>::adjacency_iterator adjacency_iterator;
-
-    // find all of the adjacent vertices
-    adjacency_iterator i, j;
-    tie(i, j) = adjacent_vertices(v, g);
+#include <boost/utility.hpp>
+#include <boost/graph/graph_traits.hpp>
 
-    // compute the size of the neighborhood
-    size_t k = distance(i, j);
-
-    // use that to compute choose(k, 2)
-    return (k * (k - 1)) / 2;
-}
-
-/**
- * The num_centered_trianges() method is used to compute the number of triangles
- * centered on this point - not really centered, but rather triangles in which
- * this point participates. This is actually closely related to the computation
- * of cenetered triples. Note that a triange at vertex v is formed if two neighbors
- * i and j share a common edge. Therefore, if we examine neighbors of i and find
- * j, we can increment the number of triangles. after examing each neigbor, we
- * should never need to consider it again (otherwise, we'll get too many triangles).
- *
- * The runtime of this function is proportional to the N^2 (neigborhood squared)
- * of vertex v. That is to say, that for each adjacent vertex i of v, we also
- * have to loook at adjacent vertices j of i.
- */
-template <
-    typename AdjacencyGraph,
-    typename AdjacencyVertex,
-    typename TriangleVector
-    >
-size_t
-num_centered_triangles(AdjacencyVertex const& v,
-		       TriangleVector &tris,
-		       AdjacencyGraph const& g)
+namespace boost
 {
-    using namespace std;
-    using namespace boost;
-
-    // graph types
-    typedef AdjacencyGraph graph;
-    typedef AdjacencyVertex vertex;
-    typedef typename graph_traits<graph>::adjacency_iterator adjacency_iterator;
-
-    // triangle types
-    typedef typename TriangleVector::value_type triangle;
-
-    // outer loop - iterate over all adjacent vertices of v
-    size_t count = 0;
-    adjacency_iterator i, j;
-    for(tie(i, j) = adjacent_vertices(v, g); i != j; ++i) {
-	adjacency_iterator k, l;
-	for(tie(k, l) = adjacent_vertices(*i, g); k != l; ++k) {
-	    // once again... we're going to look at the adjacent vertices
-	    // of v. this time we start at the vertex after i and go to
-	    // the end. this is all vertices m > i
-	    for(adjacency_iterator m = next(i); m != j; ++m) {
-		// if k (vertex in N^2) is the same as m (vertex in N)
-		// thin this is a triangle {v,i,k}.
-		if(*k == *m) {
-		    tris.push_back(triangle(v, *i, *k));
-		    ++count;
-		}
-	    }
-	}
+    namespace detail
+    {
+        template <class Graph>
+        inline size_t
+        num_possible_edges(const Graph& g, size_t k, directed_tag)
+        {
+            return k * (k - 1);
+        }
+
+        template <class Graph>
+        inline size_t
+        num_possible_edges(const Graph& g, size_t k, undirected_tag)
+        {
+            return k * (k - 1) / 2;
+        }
+
+        // This template matches directedS and bidirectionalS.
+        template <class Graph>
+        inline size_t
+        count_edges(const Graph& g,
+                    typename Graph::vertex_descriptor u,
+                    typename Graph::vertex_descriptor v,
+                    directed_tag)
+
+        {
+            return (edge(u, v, g).second ? 1 : 0) + (edge(v, u, g).second ? 1 : 0);
+        }
+
+        // This template matches undirectedS
+        template <class Graph>
+        inline size_t
+        count_edges(const Graph& g,
+                    typename Graph::vertex_descriptor u,
+                    typename Graph::vertex_descriptor v,
+                    undirected_tag)
+        {
+            return edge(u, v, g).second ? 1 : 0;
+        }
     }
 
-    return count;
-}
+    template <typename Graph>
+    inline size_t
+    num_centered_triples(const Graph& g,
+                        typename Graph::vertex_descriptor v)
+    {
+        // find all of the adjacent vertices
+        typename graph_traits<Graph>::directed_category cat;
+        typename graph_traits<Graph>::adjacency_iterator i, end;
+        tie(i, end) = adjacent_vertices(v, g);
+        size_t k = std::distance(i, end);
 
+        size_t ret = detail::num_possible_edges(g, k, cat);
+        return ret;
+    }
 
-/**
- * Compute the clustering coefficient for the entire graph. This is
- * done by averaging, for each node, the proportion of triangles centered
- * at each node and the number of triples (lenght 2 paths through) each
- * node.
- *
- * Note that the triangle vector must store vertex triples because we're
- * actually going to store all the triangles formed by the graph.
- */
-template <
-    typename AdjacencyGraph,
-    typename GraphTriangles,
-    typename VertexTriangles,
-    typename VertexTriples,
-    typename VertexCluster
-    >
-double
-clustering_coefficient(AdjacencyGraph &g,
-		       GraphTriangles &tri_vec,
-		       VertexTriangles &tri_count,
-		       VertexTriples &trip_count,
-		       VertexCluster &cluster_coef)
-{
-    using namespace std;
-    using namespace boost;
-
-    // graph types
-    typedef AdjacencyGraph graph;
-    typedef typename graph_traits<graph>::vertex_descriptor vertex;
-    typedef typename graph_traits<graph>::vertex_iterator vertex_iterator;
-
-    // iterate over each vertex and compute its clustering coefficient
-    double acc = 0.0;
-    size_t ix = 0;
-    vertex_iterator i, j;
-    for(tie(i, j) = vertices(g); i != j; ++i) {
-	vertex const& v = *i;
-
-	// first, compute the number of triples because its easy
-	size_t tris = num_centered_triangles(v, tri_vec, g);
-	size_t trips = num_centered_triples(v, g);
-
-	double ci = 0.0;
-	if(trips > 0) {
-	  ci = (double)tris / (double)trips;
-	}
-
-	// remember these values
-	tri_count[ix] = tris;
-	trip_count[ix] = trips;
-	cluster_coef[ix] = ci;
-
-	// accumulate the sum of ci's.
-	acc += ci;
+    template <typename Graph>
+    inline size_t
+    num_centered_triangles(const Graph& g,
+                           typename Graph::vertex_descriptor v)
+    {
+        size_t count = 0;
+        typename graph_traits<Graph>::directed_category cat;
+        typename graph_traits<Graph>::adjacency_iterator i, j, end;
+        for(tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
+            for(j = next(i); j != end; ++j) {
+                count += detail::count_edges(g, *i, *j, cat);
+            }
+        }
+        return count;
+    }
 
-	// increment the index!
-	++ix;
+    template <typename Graph>
+    double
+    clustering_coefficient(const Graph& g,
+                           typename Graph::vertex_descriptor v)
+    {
+        double ret = 0.0;
+        double triples = (double)num_centered_triples(g, v);
+        if(triples > 0.0) {
+            ret = (double)num_centered_triangles(g, v) / triples;
+        }
+        return ret;
     }
 
-    return acc / (double)num_vertices(g);
+    template <typename Graph>
+    double
+    clustering_coefficient(const Graph& g)
+    {
+        double cc = 0.0;
+        typename Graph::vertex_iterator i, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            cc += clustering_coefficient(g, *i);
+        }
+        return cc / (double)num_vertices(g);
+    }
 }
 
 #endif

Added: sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,66 @@
+// (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_GENERATORS_COMPLETE_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_COMPLETE_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost
+{
+    namespace detail
+    {
+        template <typename Graph>
+        inline void
+        complete_edge(Graph& g,
+                      typename graph_traits<Graph>::vertex_descriptor u,
+                      typename graph_traits<Graph>::vertex_descriptor v,
+                      directed_tag)
+        {
+            add_edge(u, v, g);
+            add_edge(v, u, g);
+        }
+
+        template <typename Graph>
+        inline void
+        complete_edge(Graph& g,
+                      typename graph_traits<Graph>::vertex_descriptor u,
+                      typename graph_traits<Graph>::vertex_descriptor v,
+                      undirected_tag)
+        {
+            add_edge(u, v, g);
+        }
+    }
+
+    template <class Graph, class RandomAccessContainer>
+    inline void
+    make_complete_graph(Graph& g, size_t k, RandomAccessContainer& verts)
+    {
+        typename graph_traits<Graph>::directed_category cat;
+        for(size_t i = 0; i < k; ++i) {
+            verts[i] = add_vertex(g);
+        }
+        for(size_t i = 0; i < k; ++i) {
+            for(size_t j = i + 1; j < k; ++j) {
+                detail::complete_edge(g, verts[i], verts[j], cat);
+            }
+        }
+    }
+
+    template <class Graph>
+    inline void
+    make_complete_graph(Graph& g, size_t k)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_complete_graph(g, k, verts);
+    }
+
+}
+
+#endif

Added: sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,56 @@
+// (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_GENERATORS_CYCLE_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_CYCLE_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/generators/options.hpp>
+
+namespace boost
+{
+    template <
+        class Graph,
+        class RandomAccessContainer,
+        class CycleDirection
+    >
+    inline void
+    make_cycle_graph(Graph& g, size_t k,
+                     RandomAccessContainer& verts,
+                     CycleDirection cycle)
+    {
+        for(size_t i = 0; i < k; ++i) {
+            verts[i] = add_vertex(g);
+        }
+        for(size_t i = 0; i < k - 1; ++i) {
+            detail::connect_cycle_vertices(g, verts[i], verts[i + 1], cycle);
+        }
+        detail::connect_cycle_vertices(g, verts[k - 1], verts[0], cycle);
+    }
+
+    template <class Graph, class CycleDirection>
+    inline void
+    make_cycle_graph(Graph& g, size_t k, CycleDirection cycle)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_cycle_graph(g, k, verts, cycle);
+    }
+
+    template <class Graph>
+    inline void
+    make_cycle_graph(Graph& g, size_t k)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_cycle_graph(g, k, verts, with_clockwise_cycle());
+    }
+}
+
+#endif

Added: sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,95 @@
+// (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_GENERATORS_OPTIONS_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_OPTIONS_GRAPH_HXX
+
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost
+{
+    // These options control the direction of edges added to
+    // graphs that have a peripheral cycle as a subgraph. These
+    // option only apply to directed graphs
+    struct with_clockwise_cycle { };
+    struct with_counterclockwise_cycle { };
+    struct with_bidirected_cycle
+        : public with_clockwise_cycle
+        , public with_counterclockwise_cycle
+    { };
+
+    // These options control the direction of edges added to
+    // graphs that have form star with a central vertex. These
+    // options only apply to directed graphs.
+    struct with_inward_spokes { };
+    struct with_outward_spokes { };
+    struct with_bidirected_spokes
+        : public with_inward_spokes
+        , public with_outward_spokes
+    { };
+
+    namespace detail
+    {
+        // Helper functions for connecting vertices
+
+        template <typename Graph>
+        inline void
+        connect_cycle_vertices(Graph& g,
+                               typename graph_traits<Graph>::vertex_descriptor u,
+                               typename graph_traits<Graph>::vertex_descriptor v,
+                               with_clockwise_cycle)
+        { add_edge(u, v, g); }
+
+        template <typename Graph>
+        inline void
+        connect_cycle_vertices(Graph& g,
+                               typename graph_traits<Graph>::vertex_descriptor u,
+                               typename graph_traits<Graph>::vertex_descriptor v,
+                               with_counterclockwise_cycle)
+        { add_edge(v, u, g); }
+
+        template <typename Graph>
+        inline void
+        connect_cycle_vertices(Graph& g,
+                               typename graph_traits<Graph>::vertex_descriptor u,
+                               typename graph_traits<Graph>::vertex_descriptor v,
+                               with_bidirected_cycle)
+        {
+            add_edge(u, v, g);
+            add_edge(v, u, g);
+        }
+
+
+        template <typename Graph>
+        inline void
+        connect_spoke_vertices(Graph& g,
+                               typename graph_traits<Graph>::vertex_descriptor u,
+                               typename graph_traits<Graph>::vertex_descriptor v,
+                               with_outward_spokes)
+        { add_edge(u, v, g); }
+
+        template <typename Graph>
+        inline void
+        connect_spoke_vertices(Graph& g,
+                               typename graph_traits<Graph>::vertex_descriptor u,
+                               typename graph_traits<Graph>::vertex_descriptor v,
+                               with_inward_spokes)
+        { add_edge(v, u, g); }
+
+        template <typename Graph>
+        inline void
+        connect_spoke_vertices(Graph& g,
+                               typename graph_traits<Graph>::vertex_descriptor u,
+                               typename graph_traits<Graph>::vertex_descriptor v,
+                               with_bidirected_spokes)
+        {
+            add_edge(u, v, g);
+            add_edge(v, u, g);
+        }
+    }
+}
+
+#endif

Added: sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,56 @@
+// (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_GENERATORS_STAR_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_STAR_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/generators/options.hpp>
+
+namespace boost
+{
+    template <
+        class Graph,
+        class RandomAccessContainer,
+        class SpokeDirection
+    >
+    inline void
+    make_star_graph(Graph& g, size_t k,
+                    RandomAccessContainer& verts,
+                    SpokeDirection spokes)
+    {
+        for(size_t i = 0; i < k; ++i) {
+            verts[i] = add_vertex(g);
+        }
+        for(size_t i = 1; i < k - 1; ++i) {
+            detail::connect_spoke_vertices(g, verts[0], verts[i], spokes);
+        }
+        detail::connect_spoke_vertices(g, verts[0], verts[k - 1], spokes);
+    }
+
+    template <class Graph, class SpokeDirection>
+    inline void
+    make_star_graph(Graph& g, size_t k, SpokeDirection spokes)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_star_graph(g, k, verts, spokes);
+    }
+
+    template <class Graph>
+    inline void
+    make_star_graph(Graph& g, size_t k)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_star_graph(g, k, verts, with_outward_spokes());
+    }
+}
+
+#endif

Added: sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,68 @@
+// (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_GENERATORS_WHEEL_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_WHEEL_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/generators/options.hpp>
+
+namespace boost
+{
+    template <
+        class Graph,
+        class RandomAccessContainer,
+        class CycleDirection,
+        class SpokeDirection
+    >
+    inline void
+    make_wheel_graph(Graph& g, size_t k,
+                     RandomAccessContainer& verts,
+                     CycleDirection cycle,
+                     SpokeDirection spokes)
+    {
+        for(size_t i = 0; i < k; ++i) {
+            verts[i] = add_vertex(g);
+        }
+        for(size_t i = 1; i < k - 1; ++i) {
+            detail::connect_spoke_vertices(g, verts[0], verts[i], spokes);
+            detail::connect_cycle_vertices(g, verts[i], verts[i + 1], cycle);
+        }
+        detail::connect_spoke_vertices(g, verts[0], verts[k - 1], spokes);
+        detail::connect_cycle_vertices(g, verts[k - 1], verts[1], cycle);
+    }
+
+    template <
+        class Graph,
+        class CycleDirection,
+        class SpokeDirection
+    >
+    inline void
+    make_wheel_graph(Graph& g, size_t k,
+                     CycleDirection cycle,
+                     SpokeDirection spokes)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_wheel_graph(g, k, verts, cycle, spokes);
+    }
+
+    template <class Graph>
+    inline void
+    make_wheel_graph(Graph& g, size_t k)
+    {
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        std::vector<Vertex> verts(k);
+        make_wheel_graph(g, k, verts,
+                         with_clockwise_cycle(),
+                         with_outward_spokes());
+    }
+}
+
+#endif

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-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -36,3 +36,14 @@
     : <include>../../../
     ;
 
+exe cluster
+    : cluster.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;
+
+exe generate
+    : generate.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;

Added: sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,86 @@
+// (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/adjacency_list.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/clustering_coefficient.hpp>
+
+using namespace std;
+using namespace boost;
+
+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);
+    vector<Edge> e;
+
+    // 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[3], v[4], g);
+    add_edge(v[4], v[0], g);
+};
+
+
+void test_1()
+{
+    typedef undirected_graph<> Graph;
+
+    Graph g;
+    build_graph(g);
+
+    Graph::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        cerr << get_vertex_index(*i, g) << "\n";
+        cerr << "  triples: " << num_centered_triples(g, *i) << "\n";
+        cerr << "  triangles: " << num_centered_triangles(g, *i) << "\n";
+        cerr << "  coef: " << clustering_coefficient(g, *i) << "\n\n";
+    }
+    cerr << "cc: " << clustering_coefficient(g) << "\n";
+}
+
+void test_2()
+{
+    typedef directed_graph<> Graph;
+
+    Graph g;
+    build_graph(g);
+
+    Graph::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        cerr << get_vertex_index(*i, g) << "\n";
+        cerr << "  triples: " << num_centered_triples(g, *i) << "\n";
+        cerr << "  triangles: " << num_centered_triangles(g, *i) << "\n";
+        cerr << "  coef: " << clustering_coefficient(g, *i) << "\n\n";
+    }
+    cerr << "cc: " << clustering_coefficient(g) << "\n";
+}
+
+int
+main(int argc, char *argv[])
+{
+    test_1();
+    test_2();
+}

Added: sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp	2007-07-09 11:45:35 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,102 @@
+// (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/adjacency_list.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/generators/complete_graph.hpp>
+#include <boost/graph/generators/cycle_graph.hpp>
+#include <boost/graph/generators/star_graph.hpp>
+#include <boost/graph/generators/wheel_graph.hpp>
+#include <boost/graph/graphviz.hpp>
+
+using namespace std;
+using namespace boost;
+
+static const int N = 10;
+
+template <class Graph, class Cycle, class Spoke>
+void test_complete(Cycle cycle, Spoke spoke)
+{
+    Graph g;
+    make_complete_graph(g, N);
+    write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle, class Spoke>
+void test_cycle(Cycle cycle, Spoke spoke)
+{
+    Graph g;
+    make_cycle_graph(g, N, cycle);
+    write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle, class Spoke>
+void test_star(Cycle cycle, Spoke spoke)
+{
+    Graph g;
+    make_star_graph(g, N, spoke);
+    write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle, class Spoke>
+void test_wheel(Cycle cycle, Spoke spoke)
+{
+    Graph g;
+    make_wheel_graph(g, N, cycle, spoke);
+    write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle, class Spoke>
+void test(Cycle cycle, Spoke spoke)
+{
+    test_complete<Graph>(cycle, spoke);
+    test_cycle<Graph>(cycle, spoke);
+    test_star<Graph>(cycle, spoke);
+    test_wheel<Graph>(cycle, spoke);
+}
+
+template <class Graph>
+void test()
+{
+    with_clockwise_cycle cycle;
+    with_outward_spokes spoke;
+    test<Graph>(cycle, spoke);
+}
+
+
+int
+main(int argc, char *argv[])
+{
+    typedef undirected_graph<> Graph;
+    typedef directed_graph<> DiGraph;
+
+    with_clockwise_cycle clockwise;
+    with_counterclockwise_cycle counterclockwise;
+    with_bidirected_cycle bothwise;
+
+    with_outward_spokes outward;
+    with_inward_spokes inward;
+    with_bidirected_spokes iospokes;
+
+    test<Graph>();
+    test<DiGraph>(clockwise, outward);
+    test<DiGraph>(counterclockwise, outward);
+    test<DiGraph>(bothwise, outward);
+    test<DiGraph>(clockwise, inward);
+    test<DiGraph>(counterclockwise, inward);
+    test<DiGraph>(bothwise, inward);
+    test<DiGraph>(clockwise, iospokes);
+    test<DiGraph>(counterclockwise, iospokes);
+    test<DiGraph>(bothwise, iospokes);
+}