[Boost-commit] svn:boost r7374

From: asutton_at_[hidden]
Date: 2007-07-06 08:23:09

Author: asutton
Date: 2007-07-06 08:23:09 EDT (Fri, 06 Jul 2007)
New Revision: 7374
URL: http://svn.boost.org/trac/boost/changeset/7374

Log:
Renamed diameter.hpp to geodesic.hpp

Added:
   sandbox/SOC/2007/graphs/boost/graph/geodesic.hpp
      - copied unchanged from r7373, /sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
Removed:
   sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp        |    90 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp |    65 ++++++++++++----------------            
   2 files changed, 112 insertions(+), 43 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp	2007-07-06 08:23:09 EDT (Fri, 06 Jul 2007)
@@ -7,17 +7,97 @@
 #ifndef BOOST_GRAPH_CONNECTIVITY_HPP
 #define BOOST_GRAPH_CONNECTIVITY_HPP
 
-// std includes
-#include <vector>
-#include <map>
-
 // boost includes
+#include <boost/graph/named_parameters.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/connected_components.hpp>
 
 namespace boost
 {
-    // TODO: implement me!
+    namespace detail
+    {
+        template <
+            typename Graph,
+            typename CompMap,
+            typename ColorMap,
+            typename IndexMap>
+        inline size_t
+        forward_connected_components(const Graph& g,
+                                     CompMap comps,
+                                     ColorMap colors,
+                                     IndexMap indices)
+        {
+            return connected_components(g, comps,
+                color_map(colors).
+                vertex_index_map(indices));
+        }
+
+        template <
+            typename Graph,
+            typename CompMap,
+            typename IndexMap>
+        inline size_t
+        forward_connected_components(const Graph& g,
+                                     CompMap comps,
+                                     not_given,
+                                     IndexMap indices)
+        {
+            return connected_components(g, comps,
+                vertex_index_map(indices));
+        }
+
+        template <
+            typename Graph,
+            typename CompMap,
+            typename Components>
+        inline void allocate_components(const Graph& g,
+                                        size_t n,
+                                        CompMap comp_map,
+                                        Components& comps)
+        {
+            comps.resize(n);
+            typename Graph::vertex_iterator i, end;
+            for(tie(i, end) = vertices(g); i != end; ++i) {
+                comps[comp_map[*i]].push_back(*i);
+            }
+        }
+
+        template <
+            typename Graph,
+            typename CompMap>
+        inline void allocate_components(const Graph& g,
+                                        size_t n,
+                                        CompMap comp_map,
+                                        not_given)
+        { }
+    }
+
+
+    // connected_components_2 is forwarded to the appropriate
+    // "legacy" function. we have to have a different name due
+    // to ambiguities.
+    BOOST_PARAMETER_FUNCTION(
+        (std::size_t),
+        connectivity, tag,
+        (required
+            (graph, *)
+            (out(component_map), *))
+        (optional
+            (color_map, *, not_given())
+            (vertex_index_map, *, get(vertex_index, graph))
+            (out(components), *, not_given()))
+        )
+    {
+        size_t n = detail::forward_connected_components(graph,
+            component_map,
+            color_map,
+            vertex_index_map);
+
+        // possibly allocate components, could be a non-call
+        detail::allocate_components(graph, n, component_map, components);
+
+        return n;
+    }
 }
 
 #endif

Modified: sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp	2007-07-06 08:23:09 EDT (Fri, 06 Jul 2007)
@@ -7,20 +7,11 @@
 #ifndef BOOST_GRAPH_DEGREE_DISTRIBUTION_HXX
 #define BOOST_GRAPH_DEGREE_DISTRIBUTION_HXX
 
-#include <boost/parameter.hpp>
+#include <boost/graph/named_parameters.hpp>
+#include <boost/graph/adjacency_list.hpp>
 
 namespace boost
 {
-    BOOST_PARAMETER_NAME(graph)
-    BOOST_PARAMETER_NAME(distribution)
-    BOOST_PARAMETER_NAME(in_distribution)
-    BOOST_PARAMETER_NAME(out_distribution)
-    BOOST_PARAMETER_NAME(histogram)
-    BOOST_PARAMETER_NAME(in_histogram)
-    BOOST_PARAMETER_NAME(out_histogram)
-
-    struct not_given {};
-
     // Helper functions for computing degree distributions, histograms. Note
     // that when passed a not_given argumemt, all of these operations are
     // no-ops. The effect is that the actual computations shouldn't add hidden
@@ -68,8 +59,8 @@
         { }
 
 
-        template <typename Dist, typename Graph>
-        inline void observe_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        template <typename Hist, typename Graph>
+        inline void observe_degree(Hist& d, typename Graph::vertex_descriptor v, const Graph& g)
         { d[boost::degree(v, g)] += 1; }
 
         template <typename Graph>
@@ -77,8 +68,8 @@
         { }
 
 
-        template <typename Dist, typename Graph>
-        inline void observe_out_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        template <typename Hist, typename Graph>
+        inline void observe_out_degree(Hist& d, typename Graph::vertex_descriptor v, const Graph& g)
         { d[boost::out_degree(v, g)] += 1; }
 
         template <typename Graph>
@@ -95,27 +86,27 @@
         { }
 
 
-        template <typename Dist, typename Graph>
-        inline void record_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
-        { d[boost::degree(v, g)] += 1; }
+        template <typename Hist, typename Graph>
+        inline void record_degree(Hist& h, typename Graph::vertex_descriptor v, const Graph& g)
+        { h[boost::degree(v, g)].push_back(v); }
 
         template <typename Graph>
         inline void record_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
         { }
 
 
-        template <typename Dist, typename Graph>
-        inline void record_out_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
-        { d[boost::out_degree(v, g)] += 1; }
+        template <typename Hist, typename Graph>
+        inline void record_out_degree(Hist& h, typename Graph::vertex_descriptor v, const Graph& g)
+        { h[boost::out_degree(v, g)].push_back(v); }
 
         template <typename Graph>
         inline void record_out_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
         { }
 
 
-        template <typename Dist, typename Graph>
-        inline void record_in_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
-        { d[boost::in_degree(v, g)] += 1; }
+        template <typename Hist, typename Graph>
+        inline void record_in_degree(Hist& h, typename Graph::vertex_descriptor v, const Graph& g)
+        { h[boost::in_degree(v, g)].push_back(v); }
 
         template <typename Graph>
         inline void record_in_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
@@ -129,14 +120,14 @@
         (optional
             (out(distribution), *, not_given())
             (out(in_distribution), *, not_given())
-            (out(out_distribution), *, not_given())
-            )
+            (out(out_distribution), *, not_given()))
         )
     {
         typename graph_type::vertex_iterator i, end;
 
         // part 1: find the max observable degrees for the graph so we
-        // only have to resize once.
+        // only have to resize once. note that this relaxes requirements on
+        // the distribution type - it just needs to be resizable.
         size_t max_d = 0, max_od = 0, max_id = 0;
         for(tie(i, end) = vertices(graph); i != end; ++i) {
             typename graph_type::vertex_descriptor v = *i;
@@ -156,8 +147,7 @@
         (optional
             (out(distribution), *, not_given())
             (out(out_distribution), *, not_given())
-            (out(in_distribution), *, not_given())
-            )
+            (out(in_distribution), *, not_given()))
         )
     {
         typename graph_type::vertex_iterator i, end;
@@ -177,31 +167,30 @@
         }
     }
 
-    // the actual degree_distribution function
+    // the actual degree_histogram function
     BOOST_PARAMETER_FUNCTION(
         (void), degree_histogram, tag,
         (required (graph, *))
         (optional
             (out(histogram), *, not_given())
             (out(out_histogram), *, not_given())
-            (out(in_histogram), *, not_given())
-            )
+            (out(in_histogram), *, not_given()))
         )
     {
         typename graph_type::vertex_iterator i, end;
 
         // part 1: initialize distributions
         initialize_distribution(graph,
-            _distribution = distribution,
-            _out_distribution = out_distribution,
-            _in_distribution = in_distribution);
+            _distribution = histogram,
+            _out_distribution = out_histogram,
+            _in_distribution = in_histogram);
 
         // part 2: record observed distributions
         for(tie(i, end) = vertices(graph); i != end; ++i) {
             typename graph_type::vertex_descriptor v = *i;
-            detail::record_degree(distribution, v, graph);
-            detail::record_out_degree(out_distribution, v, graph);
-            detail::record_in_degree(in_distribution, v, graph);
+            detail::record_degree(histogram, v, graph);
+            detail::record_out_degree(out_histogram, v, graph);
+            detail::record_in_degree(in_histogram, v, graph);
         }
     }
 }

Deleted: sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/diameter.hpp	2007-07-06 08:23:09 EDT (Fri, 06 Jul 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
-