From: asutton_at_[hidden]
Date: 2007-07-12 09:46:53
Author: asutton
Date: 2007-07-12 09:46:52 EDT (Thu, 12 Jul 2007)
New Revision: 7415
URL: http://svn.boost.org/trac/boost/changeset/7415
Log:
Added a constant_property_map that returns the same value regardless
of key type.
Added a helper class, exterior_vertex_property that provides typedefs,
allowing a usr to "cleanly" declare and implement external properties.
Added:
sandbox/SOC/2007/graphs/boost/graph/constant_property.hpp
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp | 42 +++++++++++--------------------
sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp | 19 ++++++-------
sandbox/SOC/2007/graphs/boost/graph/distance.hpp | 52 ++++++++++++++++++++++-----------------
3 files changed, 53 insertions(+), 60 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-12 09:46:52 EDT (Thu, 12 Jul 2007)
@@ -20,7 +20,8 @@
typename Graph,
typename CompMap,
typename ColorMap,
- typename IndexMap>
+ typename IndexMap
+ >
inline size_t
forward_connected_components(const Graph& g,
CompMap comps,
@@ -32,10 +33,7 @@
vertex_index_map(indices));
}
- template <
- typename Graph,
- typename CompMap,
- typename IndexMap>
+ template <typename Graph, typename CompMap, typename IndexMap>
inline size_t
forward_connected_components(const Graph& g,
CompMap comps,
@@ -46,39 +44,29 @@
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)
+ template <typename Graph, typename CompMap, typename Components>
+ inline void assign_vertices_to_components(const Graph& g, size_t n,
+ CompMap comp_map,
+ Components& comps)
{
comps.resize(n);
- typename Graph::vertex_iterator i, end;
+ typename graph_traits<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)
+ template <typename Graph, typename CompMap>
+ inline void assign_vertices_to_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.
+ // the connectivity function
BOOST_PARAMETER_FUNCTION(
- (std::size_t),
- connectivity, tag,
+ (std::size_t), connectivity, tag,
(required
(graph, *)
(out(component_map), *))
@@ -94,7 +82,7 @@
vertex_index_map);
// possibly allocate components, could be a non-call
- detail::allocate_components(graph, n, component_map, components);
+ detail::assign_vertices_to_components(graph, n, component_map, components);
return n;
}
Added: sandbox/SOC/2007/graphs/boost/graph/constant_property.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/constant_property.hpp 2007-07-12 09:46:52 EDT (Thu, 12 Jul 2007)
@@ -0,0 +1,58 @@
+// (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_CONSTANT_PROPERTY_HPP
+#define BOOST_GRAPH_CONSTANT_PROPERTY_HPP
+
+#include <boost/property_map.hpp>
+
+namespace boost
+{
+ // A constant property is one, that regardless of the
+ // edge or vertex given, will always return a constant
+ // value.
+
+ // The key is pretty much anything it doesn't matter. The
+ // value has to be default and copy constructible.
+
+ template <typename Key, typename Type>
+ struct constant_property_map
+ : public boost::put_get_helper<
+ const Type&,
+ constant_property_map<Key, Type> >
+ {
+ typedef Key key_type;
+ typedef Type value_type;
+ typedef const Type& reference;
+ typedef boost::readable_property_map_tag category;
+
+ constant_property_map()
+ : m_value()
+ { }
+
+ constant_property_map(const value_type &value)
+ : m_value(value)
+ { }
+
+ constant_property_map(const constant_property_map& copy)
+ : m_value(copy.m_value)
+ { }
+
+ inline reference operator[](const key_type& v) const
+ { return m_value; }
+
+ Type m_value;
+ };
+
+ template <typename Key, typename Type>
+ inline constant_property_map<Key, Type>
+ make_constant_property(const Type& value)
+ {
+ return constant_property_map<Key, Type>(value);
+ }
+}
+
+#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-12 09:46:52 EDT (Thu, 12 Jul 2007)
@@ -8,7 +8,6 @@
#define BOOST_GRAPH_DEGREE_DISTRIBUTION_HXX
#include <boost/graph/named_parameters.hpp>
-#include <boost/graph/adjacency_list.hpp>
namespace boost
{
@@ -24,7 +23,7 @@
typename graph_traits<Graph>::degree_size_type& m,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { m = max(m, boost::degree(v, g)); }
+ { m = max(m, degree(v, g)); }
template <typename Graph>
inline void
@@ -41,7 +40,7 @@
typename graph_traits<Graph>::degree_size_type& m,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { m = max(m, boost::out_degree(v, g)); }
+ { m = max(m, out_degree(v, g)); }
template <typename Graph>
inline void
@@ -58,7 +57,7 @@
typename graph_traits<Graph>::degree_size_type& m,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { m = max(m, boost::in_degree(v, g)); }
+ { m = max(m, in_degree(v, g)); }
template <typename Graph>
inline void
@@ -81,7 +80,7 @@
inline void observe_degree(Hist& d,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { d[boost::degree(v, g)] += 1; }
+ { d[degree(v, g)] += 1; }
template <typename Graph>
inline void observe_degree(not_given,
@@ -94,7 +93,7 @@
inline void observe_out_degree(Hist& d,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { d[boost::out_degree(v, g)] += 1; }
+ { d[out_degree(v, g)] += 1; }
template <typename Graph>
inline void observe_out_degree(not_given,
@@ -107,7 +106,7 @@
inline void observe_in_degree(Dist& d,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { d[boost::in_degree(v, g)] += 1; }
+ { d[in_degree(v, g)] += 1; }
template <typename Graph>
inline void observe_in_degree(not_given,
@@ -120,7 +119,7 @@
inline void record_degree(Hist& h,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { h[boost::degree(v, g)].push_back(v); }
+ { h[degree(v, g)].push_back(v); }
template <typename Graph>
inline void record_degree(not_given,
@@ -133,7 +132,7 @@
inline void record_out_degree(Hist& h,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { h[boost::out_degree(v, g)].push_back(v); }
+ { h[out_degree(v, g)].push_back(v); }
template <typename Graph>
inline void record_out_degree(not_given,
@@ -146,7 +145,7 @@
inline void record_in_degree(Hist& h,
typename graph_traits<Graph>::vertex_descriptor v,
const Graph& g)
- { h[boost::in_degree(v, g)].push_back(v); }
+ { h[in_degree(v, g)].push_back(v); }
template <typename Graph>
inline void record_in_degree(not_given,
Modified: sandbox/SOC/2007/graphs/boost/graph/distance.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/distance.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/distance.hpp 2007-07-12 09:46:52 EDT (Thu, 12 Jul 2007)
@@ -10,7 +10,6 @@
// boost includes
#include <boost/graph/named_parameters.hpp>
#include <boost/graph/properties.hpp>
-#include <boost/graph/adjacency_list.hpp>
namespace boost
{
@@ -67,15 +66,25 @@
mean_geodesic_distance(const Graph& g,
DistanceMap dist)
{
- return (double)detail::sum_distances(g, dist) / (double)num_vertices(g);
+ return double(detail::sum_distances(g, dist)) / double(num_vertices(g));
}
+ /*
+ template <typename Graph, typename DistanceMap, typename T = double>
+ inline T
+ mean_geodesic_distance(const Graph& g,
+ DistanceMap dist)
+ {
+ return T(detail::sum_distances(g, dist)) / T(num_vertices(g));
+ }
+ */
+
template <typename Graph, typename DistanceMap>
inline double
closeness(const Graph& g,
DistanceMap dist)
{
- return 1.0 / (double)detail::sum_distances(g, dist);
+ return double(1.0) / double(detail::sum_distances(g, dist));
}
// Can we abstract the computation of max on distances to max of
@@ -105,7 +114,7 @@
void
eccentricities(const Graph& g, DistanceMatrix& dist, EccentricityMap ecc)
{
- typename Graph::vertex_iterator i, j, end;
+ typename graph_traits<Graph>::vertex_iterator i, j, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
// compute the max eccentricity "in-place"
typename property_traits<EccentricityMap>::value_type& ei = ecc[*i];
@@ -122,7 +131,7 @@
typedef typename property_traits<EccentricityMap>::value_type eccentricity;
eccentricity ret = ecc[*vertices(g).first];
- typename Graph::vertex_iterator i, end;
+ typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
ret = std::min(ret, ecc[*i]);
}
@@ -136,7 +145,7 @@
typedef typename property_traits<EccentricityMap>::value_type eccentricity;
eccentricity ret = ecc[*vertices(g).first];
- typename Graph::vertex_iterator i, end;
+ typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
ret = std::max(ret, ecc[*i]);
}
@@ -147,20 +156,17 @@
// some of the other properties (like eccentricities, radius, and
// diameter).
- namespace detail
+ template <typename Graph, typename EccentricityMap, typename Inserter>
+ inline void
+ radial_group(const Graph& g,
+ EccentricityMap ecc,
+ Inserter ins,
+ typename property_traits<EccentricityMap>::value_type level)
{
- template <typename Graph, typename EccentricityMap, typename Inserter>
- inline void
- radial_grouping(const Graph& g,
- EccentricityMap ecc,
- Inserter ins,
- typename property_traits<EccentricityMap>::value_type level)
- {
- typename Graph::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- if(ecc[*i] == level) {
- *ins++ = *i;
- }
+ typename Graph::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ if(ecc[*i] == level) {
+ *ins++ = *i;
}
}
}
@@ -172,7 +178,7 @@
EccentricityMap ecc,
Inserter ins)
{
- return detail::radial_grouping(g, ecc, ins, r);
+ radial_group(g, ecc, ins, r);
}
template <typename Graph, typename EccentricityMap, typename Inserter>
@@ -181,7 +187,7 @@
EccentricityMap ecc,
Inserter ins)
{
- return detail::radial_grouping(g, ecc, ins, radius(g, ecc));
+ radial_group(g, ecc, ins, radius(g, ecc));
}
@@ -192,7 +198,7 @@
EccentricityMap ecc,
Inserter ins)
{
- return detail::radial_grouping(g, ecc, ins, d);
+ radial_group(g, ecc, ins, d);
}
template <typename Graph, typename EccentricityMap, typename Inserter>
@@ -201,7 +207,7 @@
EccentricityMap ecc,
Inserter ins)
{
- return detail::radial_grouping(g, ecc, ins, diameter(g, ecc));
+ radial_group(g, ecc, ins, diameter(g, ecc));
}
}
Added: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp 2007-07-12 09:46:52 EDT (Thu, 12 Jul 2007)
@@ -0,0 +1,71 @@
+// (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_EXTERIOR_PROPERTY_HPP
+#define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
+
+#include <vector>
+#include <tr1/unordered_map>
+
+#include <boost/type_traits/is_same.hpp>
+#include <boost/mpl/if.hpp>
+
+namespace boost
+{
+ namespace detail
+ {
+ // These metafunctions are used to decipher the associative strategy
+ // of graphs (i.e., how to associate a vertex or edge with a property).
+ // Unfortunatly, this isn't made explicit through any means I know of.
+ // However, we do know that vector-based storage (at least for vertices)
+ // tends to favor std::size as descriptors and uses those to index
+ // property vectors. Otherwise, the descriptor is generally a void-cast
+ // pointer to the stored element.
+
+ // Edge descriptors are a little different. They may be required to
+ // be in associative maps.
+
+ template <typename Vertex, typename Value>
+ struct choose_ext_vprop_container
+ {
+ typedef typename mpl::if_<
+ is_same<Vertex, std::size_t>,
+ std::vector<Value>,
+ std::tr1::unordered_map<Vertex, Value>
+ >::type type;
+ };
+
+ template <typename Graph, typename Container>
+ struct choose_ext_vprop_map
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
+ typedef typename mpl::if_<
+ is_same<vertex_type, std::size_t>,
+ iterator_property_map<
+ typename Container::iterator,
+ typename property_map<Graph, vertex_index_t>::type>,
+ associative_property_map<Container>
+ >::type type;
+ };
+ };
+
+ template <typename Graph, typename Value>
+ struct exterior_vertex_property
+ {
+ typedef Value value_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+
+ typedef typename
+ detail::choose_ext_vprop_container<key_type, value_type>::type
+ container_type;
+
+ typedef typename
+ detail::choose_ext_vprop_map<Graph, container_type>::type
+ map_type;
+ };
+}
+
+#endif