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
-