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
-