[Boost-commit] svn:boost r4477

From: asutton_at_[hidden]
Date: 2007-06-06 19:24:13

Author: asutton
Date: 2007-06-06 19:24:13 EDT (Wed, 06 Jun 2007)
New Revision: 4477
URL: http://svn.boost.org/trac/boost/changeset/4477

Log:
Renamed the files I just added. oops.

Added:
   sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
      - copied unchanged from r4476, /sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hxx
   sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp
      - copied unchanged from r4476, /sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hxx
   sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
      - copied unchanged from r4476, /sandbox/SOC/2007/graphs/boost/graph/diameter.hxx
Removed:
   sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hxx
   sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hxx
   sandbox/SOC/2007/graphs/boost/graph/diameter.hxx

Deleted: sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hxx
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hxx	2007-06-06 19:24:13 EDT (Wed, 06 Jun 2007)
+++ (empty file)
@@ -1,164 +0,0 @@
-
-#ifndef CLUSTERING_COEFFICIENT_HXX
-#define 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);
-
-    // 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)
-{
-    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;
-		}
-	    }
-	}
-    }
-
-    return count;
-}
-
-
-/**
- * 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;
-
-	// increment the index!
-	++ix;
-    }
-
-    return acc / (double)num_vertices(g);
-}
-
-#endif

Deleted: sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hxx
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hxx	2007-06-06 19:24:13 EDT (Wed, 06 Jun 2007)
+++ (empty file)
@@ -1,50 +0,0 @@
-// (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_DEGREE_DISTRIBUTION_HXX
-#define BOOST_GRAPH_DEGREE_DISTRIBUTION_HXX
-
-namespace boost
-{
-    template <
-	typename BidirectionalGraph,
-	typename Container
-	>
-    typename graph_traits<BindirectionalGraph>::degree_size_type
-    degree_distribution(BidirectionalGraph &g, Container &dist)
-    {
-	typedef BidirectionalGraph graph;
-	typedef typename graph_traits<Graph>::vertex_descriptor vertex;
-	typedef typename graph_traits<Graph>::degree_size_type degree;
-
-	// stash the degree of each vertex into its bucket - degree 1
-	// goes into index 1, degree 90 goes into index 90, etc.
-	degree max = 0;
-	vertex_iterator i, j;
-	for(tie(i, j) = vertices(g); i != j; ++i) {
-	    degree d = degree(*i, g);
-
-	    // we may need to resize the array to accomodate the
-	    // incrementation of this degrees bucket.
-	    if(d >= dist.size()) {
-		dist.resize(d + 1);
-	    }
-
-	    // remember the max degree that we've seen
-	    if(d > max) {
-		max = d;
-	    }
-
-	    // increment the count in that bucket
-	    dist[d] += 1;
-	}
-	return max;
-    }
-}
-
-#endif
-
-

Deleted: sandbox/SOC/2007/graphs/boost/graph/diameter.hxx
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/diameter.hxx	2007-06-06 19:24:13 EDT (Wed, 06 Jun 2007)
+++ (empty file)
@@ -1,71 +0,0 @@
-
-#ifndef DIAMETER_HXX
-#define DIAMETER_HXX
-
-// std includes
-#include <vector>
-#include <limits>
-
-// boost includes
-#include <boost/graph/johnson_all_pairs_shortest.hpp>
-
-/**
- * Compute the diameter of the graoh - which is essentially the longest
- * of all shortest paths (or the longest geodesic). At the moment, this
- * algorithm uses johnson's variant which runs in O(n*m*log n). Note that
- * when the graph is dense (i.e., m -> n^2), this takes O(n^3 * log n)
- * which is actually worse than floyd warshall. However, this should run
- * fine on power-law graphs since they're relatively sparse. Normally
- * distributed graphs might not be so lucky.
- *
- * There's some strange variations of this algorithm. For example,
- * if the graph is unconnected, then it really doesn't have an actual
- * diameter. If we igore infinite lenghts, then we are computing the
- * diameter of the largest connected component - which may actually
- * by acceptable.
- */
-template <
-    typename Graph,
-    typename Matrix
-    >
-int
-diameter(Graph &g, Matrix &d)
-{
-    using namespace std;
-    using namespace boost;
-
-    // various graph types
-    typedef Graph graph;
-    typedef typename graph_traits<graph>::vertex_descriptor vertex;
-
-    // matrix types
-
-    // for convenience, get the number of vertices
-    size_t n = num_vertices(g);
-
-    // find all pairs of shortest paths
-    int ret = 0;
-    bool success = johnson_all_pairs_shortest_paths(g, d);
-    if(success) {
-	// compute the maximum distance of elements in graph
-	for(size_t i = 0; i < n; ++i) {
-	    for(size_t j = 0; j < n; ++j) {
-		int dist = d[i][j];
-
-		// don't compute distances for disconnected
-		// vertices - this is kind of a weird point
-		// of logic
-		if(dist != numeric_limits<int>::max()) {
-		    if(dist > ret) {
-			ret = dist;
-		    }
-		}
-	    }
- 	}
-    }
-
-    return ret;
-}
-
-#endif
-