# Boost-Commit :

From: asutton_at_[hidden]
Date: 2007-06-06 19:22:38

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

Log:
Added some algorithms - unfortunately, I'm going to rename them soon

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

==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hxx 2007-06-06 19:22:38 EDT (Wed, 06 Jun 2007)
@@ -0,0 +1,164 @@
+
+#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 <
+ >
+size_t
+{
+ using namespace std;
+ using namespace boost;
+
+
+ // find all of the adjacent vertices
+ 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 TriangleVector
+ >
+size_t
+ TriangleVector &tris,
+{
+ using namespace std;
+ using namespace boost;
+
+ // graph types
+
+ // triangle types
+ typedef typename TriangleVector::value_type triangle;
+
+ // outer loop - iterate over all adjacent vertices of v
+ size_t count = 0;
+ for(tie(i, j) = adjacent_vertices(v, g); i != j; ++i) {
+ 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 GraphTriangles,
+ typename VertexTriangles,
+ typename VertexTriples,
+ typename VertexCluster
+ >
+double
+ GraphTriangles &tri_vec,
+ VertexTriangles &tri_count,
+ VertexTriples &trip_count,
+ VertexCluster &cluster_coef)
+{
+ using namespace std;
+ using namespace boost;
+
+ // graph types
+ 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

==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hxx 2007-06-06 19:22:38 EDT (Wed, 06 Jun 2007)
@@ -0,0 +1,50 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+
+#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
+
+

==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/diameter.hxx 2007-06-06 19:22:38 EDT (Wed, 06 Jun 2007)
@@ -0,0 +1,71 @@
+
+#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
+