|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-07-28 11:35:07
Author: asutton
Date: 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
New Revision: 7573
URL: http://svn.boost.org/trac/boost/changeset/7573
Log:
Commpletely rewrote the exterior property and geodesics code
Added:
sandbox/SOC/2007/graphs/boost/graph/detail/
Text files modified:
sandbox/SOC/2007/graphs/README | 53 +++++++--
sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp | 2
sandbox/SOC/2007/graphs/boost/graph/distance.hpp | 101 -----------------
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 224 ++++++++++++++++++++++++++++++---------
sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp | 5
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex | 2
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk | 200 +++++++++++++++++++---------------
sandbox/SOC/2007/graphs/libs/graph/test/components.cpp | 2
sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp | 203 +++++++++--------------------------
sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp | 129 ++++++++++++++--------
10 files changed, 467 insertions(+), 454 deletions(-)
Modified: sandbox/SOC/2007/graphs/README
==============================================================================
--- sandbox/SOC/2007/graphs/README (original)
+++ sandbox/SOC/2007/graphs/README 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -1,15 +1,44 @@
-Various Notes to Self
+= Notes =
-== Models of Concepts ==
-I didn't know this - or at least I hadn't thought about it, but it appears that
-undirected graphs model the BidirectionalGraph concept - at least they do with
-adjacency_list. Curious...
-
-== Nicities ==
-Apparently, that migrating into a new namespace isn't going to work too well
-since all the other algorithms are expecting functions in a particular namespace
-and (probably more importantly) with a particular signature.
+== Distances ==
+So there apparently, a lot of things that we can do with distance measures.
+A distance measure is some measure of distance between two vertices - whether
+it's based on edge weights, vertex weights, or just path length. Regardless,
+everything we do is either based on a DistanceMap or a DistanceMatrix.
-I think it would probably take a complete rewrite of Boost.Graph in order to
-successfully create the more familiar interfaces.
\ No newline at end of file
+There are a couple of interesting call profiles for these measures. The first,
+provides a vertex measure based on a DistanceMap. Models of this type simply
+take the Graph and the DistanceMap and return a scalar value (maybe). There
+can be other parameters to help genericize the operation. For example:
+
+ double mean_geodesic(g, dist);
+
+The second call profile is similar to that above except that it computes a
+measure over a distance matrix. For example, we might have:
+
+ double graph_mean_geodesic(g, dist);
+ double graph_closeness(g);
+
+These are actually kind of interesting since their operation varies a bit
+based on the type of graph. For example, for undirected graphs, the total
+number of possible edges is (n*(n-1)) / 2 so we'd average over that number. For
+directed graphs, it should be n^2.
+
+The third call profile takes a DistanceMatrix and computes a DistanceMap that
+provides a measure computed over each vertices in the matrix. For examples:
+
+ void eccentricities(g, dist, out);
+
+Where dist is the matrix and out is the map. Essentially, these types of
+functions are used to compute and assign computations of rows of values. The
+idea with these types of functions is that its faster to run all-pairs shortest
+paths than to brute force run shortest paths for each vertex (which would generally
+be pretty slow).
+
+== Property Matrices ==
+A property matrix is like a property map except that it's value type is
+another property map. Also like exterior properties, it's a two component
+system. The first component is a two-way associative mapping between two
+descriptors and a property value. The second part is the abstracted map
+interface.
Modified: sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -41,7 +41,7 @@
: m_value(copy.m_value)
{ }
- inline reference operator[](const key_type& v) const
+ inline reference operator [](const key_type& v) const
{ return m_value; }
Type m_value;
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-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -7,111 +7,12 @@
#ifndef BOOST_GRAPH_DISTANCE_HPP
#define BOOST_GRAPH_DISTANCE_HPP
-// boost includes
-#include <boost/graph/named_parameters.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/properties.hpp>
+#include <boost/graph/detail/combine_distances.hpp>
namespace boost
{
- namespace detail
- {
- template <typename Graph, typename DistanceMap>
- inline typename property_traits<DistanceMap>::value_type
- sum_distances(const Graph& g, DistanceMap dist)
- {
- size_t ret = 0;
- typename graph_traits<Graph>::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- ret += dist[*i];
- }
- return ret;
- }
- }
-
- // These measures operate on the first vertex given. This is to say that
- // closeness(g, v, dist) will return the closeness of the vertex v with
- // respect to all other vertices in the graph.
- //
- // Note that the target vertex in each algorithm is essentially a dummy
- // parameter (for now). If the distance map isn't supplied, then we
- // may shell to default computations.
- //
- // Vertex distance measures:
- // - geodesic_distance
- // - mean_geodesic_distance
- // - closeness
- // - eccentricity
- //
- // Graph distance measures:
- // - radius
- // - diameter
- //
- // Note that two versions of each algorithm exist. One takes a precomputed
- // distance map or matrix while the other computes it on the fly by trying
- // to guess an algorithm to use.
-
- template <typename Graph, typename DistanceMap>
- inline typename property_traits<DistanceMap>::value_type
- geodesic_distance(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- DistanceMap dist)
- {
- return dist[v];
- }
-
- template <typename Graph, typename DistanceMap>
- inline double
- mean_geodesic_distance(const Graph& g,
- DistanceMap dist)
- {
- return double(detail::sum_distances(g, dist)) / double(num_vertices(g));
- }
-
- // Arbitrary numeric version uses T as some numeric type.
- // T must be constructible from degree_size_type and
- // DistanceMap::value_type. Note that above T == double.
- /*
- template <typename Graph, typename DistanceMap, typename T>
- inline T
- mean_geodesic_distance(const Graph& g,
- DistanceMap dist,
- const T& dummy)
- {
- return T(detail::sum_distances(g, dist)) / T(num_vertices(g));
- }
- */
-
- template <typename T, typename Graph, typename DistanceMap>
- 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 double(1) / double(detail::sum_distances(g, dist));
- }
-
- // Arbitrary numeric version uses T as some numeric type.
- // T must be constructible from integral and DistanceMap::value_type.
- // Note that above T == double.
- template <typename Graph, typename DistanceMap, typename T>
- inline T
- closeness(const Graph& g,
- DistanceMap dist,
- const T& dummy)
- {
- return dummy(1) / double(detail::sum_distances(g, dist));
- }
- // Note that the DistanceMap::value_type must be constructible
- // as 0 - basically indicating an acceptable default value.
template <typename Graph, typename DistanceMap>
inline typename property_traits<DistanceMap>::value_type
eccentricity(const Graph& g,
Modified: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -12,77 +12,199 @@
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/if.hpp>
+#include <boost/property_map.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.
-
- // TODO: Edge descriptors are a little different. They may be required to
- // be in associative maps regardless of actual type (maybe). There's not
- // a single example of using exterior edge properties in Boost.Graph.
+ // These property map adapters are basically here to provide a common
+ // method for initializing the property maps. They also provide a
+ // cast operator for returning the underlying mapping type.
- template <typename Vertex, typename Value>
- struct choose_ext_vprop_container
+ // Do we really /need/ to do this. Not really. There are otherways
+ // to achieve syntactic conformity, but they're less graceful.
+
+ template <typename Graph, typename Container>
+ struct vector_property_map_adapter
+ : public boost::put_get_helper<
+ typename iterator_property_map<
+ typename Container::iterator,
+ typename property_map<Graph, vertex_index_t>::type
+ >::reference,
+ vector_property_map_adapter<Graph, Container>
+ >
{
- typedef typename mpl::if_<
- is_same<Vertex, std::size_t>,
- std::vector<Value>,
- std::tr1::unordered_map<Vertex, Value>
- >::type type;
+ typedef iterator_property_map<
+ typename Container::iterator,
+ typename property_map<Graph, vertex_index_t>::type
+ > map_type;
+ typedef typename map_type::key_type key_type;
+ typedef typename map_type::value_type value_type;
+ typedef typename map_type::reference reference;
+ typedef typename map_type::category category;
+
+ inline vector_property_map_adapter(Container& c)
+ : m_map(c.begin())
+ { }
+
+ inline vector_property_map_adapter(const vector_property_map_adapter& x)
+ : m_map(x.m_map)
+ { }
+
+ inline reference operator [](const key_type& k) const
+ { return m_map[k]; }
+
+ map_type m_map;
};
template <typename Graph, typename Container>
- struct choose_ext_vprop_map
+ struct hash_property_map_adapter
+ : public boost::put_get_helper<
+ typename associative_property_map<Container>::reference,
+ hash_property_map_adapter<Graph, Container>
+ >
{
- 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;
+ typedef associative_property_map<Container> map_type;
+ typedef typename map_type::key_type key_type;
+ typedef typename map_type::value_type value_type;
+ typedef typename map_type::reference reference;
+ typedef typename map_type::category category;
+
+ inline hash_property_map_adapter(Container& c)
+ : m_map(c)
+ { }
+
+ inline hash_property_map_adapter(const hash_property_map_adapter& x)
+ : m_map(x.m_map)
+ { }
+
+ inline reference operator[](const key_type& k) const
+ { return m_map[k]; }
+
+ operator map_type() const
+ { return m_map; }
+
+ map_type m_map;
};
- };
+ }
+
+ namespace detail
+ {
+ // These structures implement very, very basic matrices
+ // over vectors and hash tables. Like the adapters above, these
+ // classes provide a degree of syntactic uniformity for their
+ // declarations.
+
+ template <typename Graph, typename Value>
+ struct vector_matrix_adapter
+ {
+ typedef typename graph_traits<Graph>::vertices_size_type size_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+ typedef Value value_type;
+
+ typedef std::vector<value_type> container_type;
+ typedef std::vector<container_type> matrix_type;
+
+ inline vector_matrix_adapter(size_type n)
+ : m_matrix(n, container_type(n))
+ { }
+
+ inline typename matrix_type::reference operator [](key_type k)
+ { return m_matrix[k]; }
+
+ matrix_type m_matrix;
+ };
+
+ // There's a strange side-effect using the []'s of a hashtable in
+ // that it's a modifying operation. If the key isn't found, this
+ // will create a value for the key with the default value. However,
+ // since we know that all the keys exist in the map, it shouldn't
+ // be a big deal.
+ //
+ // Also, we can kind of skip the initialization of the underlying
+ // data structures. there's going to be a bunch of resizing, but
+ // in the long run, it may not hurt too much.
+ template <typename Graph, typename Value>
+ struct hash_matrix_adapter
+ {
+ typedef typename graph_traits<Graph>::vertices_size_type size_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+ typedef Value value_type;
+
+ typedef std::tr1::unordered_map<key_type, value_type> container_type;
+ typedef std::tr1::unordered_map<key_type, container_type> matrix_type;
+
+ inline hash_matrix_adapter(size_type n)
+ : m_matrix(n)
+ {
+ typename matrix_type::iterator i, end = m_matrix.end();
+ for(i = m_matrix.begin(); i != end; ++i) {
+ i->second.rehash(n);
+ }
+ }
+
+ inline typename matrix_type::mapped_type& operator [](key_type k)
+ { return m_matrix[k]; }
+
+ mutable matrix_type m_matrix;
+ };
+}
+
+ // This is very, very dirty. If the adjacency list implementation
+ // has not been included at this point, we need to define
+ // it's graph tag so we can specialize on it. I feel so unclean.
+ // A better solution would be to migrate commonly used graph tags
+ // like this to a separate header.
+#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
+ struct vec_adj_list_tag { };
+#endif
+
+ // These structures associate a preferred mapping style
+ // with a graph type.
+ struct vector_mapped_tag {};
+ struct hash_mapped_tag {};
template <typename Graph, typename Value>
- struct exterior_vertex_property
+ struct vector_mapped_vertex_property_traits
{
+ typedef vector_mapped_tag mapping_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor key_type;
typedef Value value_type;
+
+ typedef typename std::vector<Value> container_type;
+ typedef detail::vector_matrix_adapter<Graph, value_type> matrix_type;
+ typedef detail::vector_property_map_adapter<Graph, container_type> map_type;
+ };
+
+ template <typename Graph, typename Value>
+ struct hash_mapped_vertex_property_traits
+ {
+ typedef hash_mapped_tag mapping_type;
typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+ typedef Value value_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;
+ typedef typename std::tr1::unordered_map<key_type, value_type> container_type;
+ typedef detail::hash_matrix_adapter<Graph, value_type> matrix_type;
+ typedef detail::hash_property_map_adapter<Graph, container_type> map_type;
};
- // These functions are needed to abstract the initialization sequence.
- // If you know the actual container type of your exerior property, then
- // you skip these functions. If you don't and you're declaring these
- // generically, then you _must_ use these to ensure correct initialiation
- // of the property map.
-
- template <typename Key, typename Value>
- static inline std::tr1::unordered_map<Key, Value>&
- make_property_map(std::tr1::unordered_map<Key, Value>& c)
- { return c; }
-
- template <typename Value>
- static inline typename std::vector<Value>::iterator
- make_property_map(std::vector<Value>& c)
- { return c.begin(); }
+ template <typename Graph, typename Value>
+ struct exterior_vertex_property
+ {
+ typedef typename Graph::graph_tag graph_tag;
+ typedef typename mpl::if_<
+ is_same<graph_tag, vec_adj_list_tag>,
+ vector_mapped_vertex_property_traits<Graph, Value>,
+ hash_mapped_vertex_property_traits<Graph, Value>
+ >::type traits_type;
+
+ typedef typename traits_type::key_type key_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::container_type container_type;
+ typedef typename traits_type::matrix_type matrix_type;
+ typedef typename traits_type::map_type map_type;
+ };
}
#endif
Modified: sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -40,7 +40,10 @@
BOOST_PARAMETER_NAME(color_map)
BOOST_PARAMETER_NAME(vertex_index_map)
- struct not_given {};
+ // miscellaneous
+ BOOST_PARAMETER_NAME(combine)
+ BOOST_PARAMETER_NAME(distance_numbers)
+ BOOST_PARAMETER_NAME(output_numbers)
}
#endif
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -8,5 +8,5 @@
\pagestyle{empty}
\begin{document}
-$C(u) = \frac{1}{\sum_{u \in V}{d_G\left(u,v\right)}} $
+$C(u) = \frac{n}{\sum_{u \in V}{d_G\left(u,v\right)}} $
\end{document}
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -8,68 +8,97 @@
[section Geodesic Distances]
template <typename Graph, typename DistanceMap>
- typename property_traits<DistanceMap>::value_type
- geodesic_distance(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- DistanceMap dist)
+ double mean_geodesic(const Graph& g, DistanceMap dist)
+
+ template <typename T, typename Graph, typename DistanceMap>
+ T mean_geodesic(const Graph& g, DistanceMap dist)
+
+ template <typename T,
+ typename Graph,
+ typename DistanceMap,
+ typename DistanceType,
+ typename Combinator>
+ T mean_geodesic(
+ const Graph& g,
+ DistanceMap dist,
+ Combinator combine,
+ DistanceType zero,
+ DistanceType infinity = std::numeric_limits<T>::max())
+
+
template <typename Graph, typename DistanceMap>
- double
- mean_geodesic_distance(const Graph& g, DistanceMap dist)
+ double closeness(const Graph& g, DistanceMap dist)
+
+ template <typename T, typename Graph, typename DistanceMap>
+ T closeness(const Graph& g, DistanceMap dist)
+
+ template <typename T,
+ typename Graph,
+ typename DistanceMap,
+ typename DistanceType,
+ typename Combinator>
+ T closeness(
+ const Graph& g,
+ DistanceMap dist,
+ Combinator combine,
+ DistanceType zero,
+ DistanceType infinity = std::numeric_limits<T>::max())
- template <typename Graph, typename DistanceMap, typename T>
- T
- mean_geodesic_distance(const Graph& g, DistanceMap dist, const T& dummy)
These functions compute values based on the /geodesic distance/ between
vertices. The /geodesic distance/ between vertices /u/ and /v/ is defined
-as the shortest-length path between such vertices. It is important to note
-that these functions /do not/ compute these paths or record their distances.
+as the shortest-length path between such vertices. The shortest path can
+be defined in terms of the sum of edge, weights, the sum of vertex weights,
+or simply the number of "hops". It is important to notethat these functions
+/do not/ compute the paths or record their distances. Instead, they rely upon
+a previous computation.
Boost.Graph provides two shortest paths algorithms: [boost_dijkstra_shortest_paths]
and [boost_bellman_ford_shortest_paths]. Optionally, if the target graph is
-an unweighted, undirected graph, shortest paths can be recorded using
+an unweighted, undirected graph the shortest paths can be recorded using
[boost_breadth_first_search]. Each of these algorithms takes as an input a
vertex for which the shortest distances are being computed. The output of
each of these shortest paths algorithms is a `DistanceMap`, which is used as the
input to the geodesic distance functions. Note then, that these functions compute
measures of the vertex for which `dist` was computed.
-[note
-Get rid of `geodesic_distance()`.
-]
-
-The `geodesic_distance()` function returns the length of the shortest path
-between two vertices. The source vertex is that for which the `DistanceMap`
-was computed and the target vertex, `v`, is supplied as a parameter. This
-function is an alias for:
-
- dist[v];
-
-The `mean_geodesic_distance()` functions return the (arithmatic) mean
-of the geodesic distances between a vertex and all others in the graph. The
-vertex for which this is computed is that for which `dist` originally
-computed. The mean geodesic distance is implemeted as:
+The `mean_geodesic()` functions return the (arithmatic) mean of the geodesic
+distances between a vertex and all others in the graph. Intuitively, this gives
+the average distance from one vertex to every other. Vertices with low mean
+geodesic distance are more central to the graph. The `mean_geodesic()` for
+a vertex is given as:
[$images/eq/mean_geodesic.png]
-where ['d[sub G](u, v)] is the geodesic distance (shortest path) from /u/ to /v/.
+The `closeness()` functions effectively return the inverse (reciprocal) of the
+`mean_geodesic()` for a vertex. It is given as:
-The default (first) variant of this function computes and returns the
-average as a `double`. The second variant allows the average and return
-type to be computed as a user-defined type by passing a dummy instance.
-This is useful if the `value_type` of `DistanceMap` is a user-defined or
-otherwise non-trivial.
-
-Note that the geodesic distance between two unconnected vertices is infinite.
-This implies that the mean geodesic distance for an unconnected graph is
-also infinite.
+[$images/eq/closeness.png]
+
+In both of these formulas, /n/ is the number of vertices in the graph `G` and
+['d[sub G](u, v)] is the geodesic distance (shortest path) from /u/ to /v/. If
+/v/ is not reachable from /u/, then the distance between /u/ and /v/ is infinite.
+This implies that the `mean_geodesic()` for `u` is infinite and the `closeness()`
+is 0.
+
+There are three variants of these two sets of functions, allowing increasing
+genericity of usage.
+
+The first variant of this function computes and returns the average as a
+`double`. The second variant allows the average and return type to be computed
+as a user-defined type by passing a dummy instance. This is useful if the
+`value_type` of `DistanceMap` is a user-defined, but otherwise acts as a numeric
+type. The third variant allows the user to specify the type, the combination
+function for computing the sum, and the default values of 0 and infinity. This
+is useful when the computation is performed on a discrete or non-numeric type.
+Note that in this variant, the default value of `zero` must be explicitly
+passed as an argument.
[heading Where Defined]
`boost/graph/distance.hpp`
[heading Parameters]
-
[table
[[Type] [Parameter] [Description]]
[
@@ -80,13 +109,6 @@
]
]
[
- [required, in] [`vertex_descriptor v`]
- [
- The target vertex to which the geodisic distance is returned. The
- source vertex is made implicit by the `DistanceMap`.
- ]
- ]
- [
[required, in] [`DistanceMap dist`]
[
The `dist` parameter provides the distances of the shortest paths
@@ -96,42 +118,54 @@
]
]
[
- [required, in] [`const T& dummy`]
+ [optional, in] [`T`]
[
- An unused instance of the type returned by the `mean_geodesic_distance()`
- function. If specified, the measure will be computed as an average of
- this type. This type must essentially be numeric, as it is required to
- a) support division, b) be initialized with an integer type, and c)
- have a default of 0.
+ If used, the `T` template parameter must be explicitly given as a
+ template argument when invoking these functions. The type `T` must
+ be a `Regular` type (default and copy constructible, assignable).
+ Additionally, it must be `Divisible` and constructible from both
+ `vertices_size_type` of `Graph` and the `value_type` of `DistanceMap`.
+ Numeric types satisfy these requirements.
]
]
-]
+ [
+ [optional, in] [`Combinator combine`]
+ [
+ The `combine` parameter is a binary functor that is invoked to combine
+ distance values in the `DistanceMap`. The argument types and return
+ type of the function must be the same as the `value_type` of the
+ `DistanceMap`.
-[note
-The requirements on `T` indicate a particularly interesting problem because
-division is basically [SgiMonoid] operation - which is probably one of the
-more esoteric concepts in the STL. Curiously, the `identity_element()` operation
-which is an SGI extension and apparently not part of the actual standard.
-
-The correct implemention of `detail::sum_distances()` should take a monoid
-type and use `identity_element(f)` for initializaiton and `f` for the combination.
-
-There's also a sort of strange requirement that we need some testable notion
-of infinite. So, `T` is apparently some monoidic type that also has the notion
-of an infinite value.
-]
+ *Default:* `std::plus<T>()`
+ ]
+ ]
+ [
+ [optional, in] [`DistanceType zero`]
+ [
+ The `zero` parameter is used as an initial value for the combination
+ of distances in these computations. Distance must be the same type
+ as the `value_type` of the `DistanceMap` parameter.
-[h5 Return Value]
-The `geodesic_distance()` function returns the distance of the shortest
-path to `v`.
+ *Defaults:* `DistanceType()` (for numeric types, this is 0).
+ ]
+ ]
+ [
+ [optional, in] [`T infinity`]
+ [
+ The `infinity` parameter is used to indicate a value of `T` that
+ acts as an infinite value in these computations. Distance must be the
+ same type as the `value_type` of the `DistanceMap` parameter. Note that
+ if the shortest paths are computed using [boost_dijkstra_shortest_paths],
+ and the `inf` parameter is used, this must be the same value.
-The `mean_geodesic_distance()` function returns the (arithmatic) mean of
-the shortest distances to all other vertices.
+ *Default:* `std::numeric_limits<DistanceType>::max()`
+ ]
+ ]
+]
[h5 Complexity]
-The `geodesic_distance()` function has /O(1)/ time complexity.
-
-The `mean_geodesic_distance()` function has /O(V)/ time complexity.
+The `mean_geodesic()` and `closeness()` functions are linear with respect to
+`num_vertices(g)`.
[h5 Examples]
This example computes shows the construction of a simple undirected graph and
@@ -187,26 +221,14 @@
its mean geodesic distance.
Graph::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- cout << "geodesic distance to v[" << get(vertex_index, g, *i) << "] == "
- << geodesic_distance(g, *i, dist) << endl;
- }
- cout << "mean geodesic distance == " << mean_geodesic_distance(g, dist) << end;
+ cout << "mean geodesic == " << mean_geodesic(g, dist) << end;
+ cout << "closeness == " << closeness(g, dist) << end;
The output of this program is:
[pre
-geodesic distance to v\[0\] == 0
-geodesic distance to v\[1\] == 1
-geodesic distance to v\[2\] == 2
-geodesic distance to v\[3\] == 2
-geodesic distance to v\[4\] == 3
-geodesic distance to v\[5\] == 3
-geodesic distance to v\[6\] == 4
-geodesic distance to v\[7\] == 4
-geodesic distance to v\[8\] == 4
-geodesic distance to v\[9\] == 5
-mean geodesic distance == 2.8
+mean geodesic == 2.8
+closeness == .35
]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/components.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/components.cpp 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -56,7 +56,7 @@
ComponentContainer comps(num_vertices(g));
- ComponentMap comps_map(make_property_map(comps));
+ ComponentMap comps_map(comps);
size_t n = connected_components(g, comps_map);
Modified: sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -10,23 +10,28 @@
#include <vector>
#include <map>
#include <tr1/unordered_map>
+#include <cxxabi.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include <boost/graph/distance.hpp>
+#include <boost/graph/geodesic.hpp>
using namespace std;
using namespace boost;
-struct VertexProperty
+struct VertexProp
{
int dummy;
};
-struct EdgeProperty
+struct EdgeProp
{
int weight;
};
@@ -61,189 +66,91 @@
g[e[4]].weight = 1;
};
-template <typename Graph, typename DistanceMap>
-void dump_distance_map(const Graph& g, DistanceMap dists)
+template <typename Graph, typename PropertyMap>
+void print_map(const Graph& g, PropertyMap pm)
{
typename Graph::vertex_iterator i, end;
+ cout << "{ ";
for(tie(i, end) = vertices(g); i != end; ++i) {
- cout << dists[*i] << " ";
+ cout << pm[*i] << " ";
}
- cout << "\n";
+ cout << "}\n";
}
-template <typename Graph, typename DistanceMatrix>
-void dump_distance_matrix(const Graph& g, DistanceMatrix dists)
+template <typename Graph, typename Matrix>
+void print_matrix(const Graph& g, Matrix m)
{
+ cout << "[\n";
typename Graph::vertex_iterator i, j, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- for(j = vertices(g).first; j != end; ++j) {
- cout << dists[*i][*j] << " ";
- }
- cout << "\n";
+ print_map(g, m[*i]);
}
+ cout << "]\n";
}
-void test_1()
+template <typename Graph>
+void test()
{
- // because this is defined w/vecS's, we don't have to work very
- // hard on property maps
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
- typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
- typedef Graph::vertex_descriptor Vertex;
- typedef property_map<Graph, int EdgeProperty::*>::type WeightPropertyMap;
- typedef vector<int> DistanceMap;
- typedef iterator_property_map<DistanceMap::iterator,
- property_map<Graph, vertex_index_t>::type> DistancePropertyMap;
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::container_type DistanceContainer;
+ typedef typename DistanceProperty::map_type DistanceMap;
+ typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
Graph g;
build_graph(g);
- Vertex v = *vertices(g).first;
- WeightPropertyMap weights = get(&EdgeProperty::weight, g);
-
- cout << "\nadjacency_list<vecS, vecS...>\n";
+ // single-vertex computations
{
- DistanceMap distances(num_vertices(g));
- DistancePropertyMap dists(distances.begin());
+ DistanceContainer distances(num_vertices(g));
+ DistanceMap dists(distances);
+ WeightMap weights = get(&EdgeProp::weight, g);
- dijkstra_shortest_paths(g, v,
+ dijkstra_shortest_paths(g, *vertices(g).first,
weight_map(weights).
distance_map(dists));
- cout << "* dists: "; dump_distance_map(g, dists);
- cout << "* mean geo: " << mean_geodesic_distance(g, dists) << "\n";
- cout << "* mean geo: " << mean_geodesic_distance<float>(g, dists) << "\n";
- cout << "* closeness: " << closeness(g, dists) << "\n";
- cout << "* eccentricity: " << eccentricity(g, dists) << "\n";
- }
+ double total_geo = total_geodesic_distance(g, dists);
+ double mean_geo = mean_geodesic_distance(g, dists);
+ double inverse_geo = inverse_geodesic_distance(g, dists);
+ double close = closeness(g, dists);
- {
- typedef vector<DistanceMap> DistanceMatrix;
-
- DistanceMatrix dists(num_vertices(g), DistanceMap(num_vertices(g)));
-
- // compute all shortest paths
- floyd_warshall_all_pairs_shortest_paths(g, dists,
- weight_map(weights));
-
- // use the distances in all-pairs to compute eccentricities
- // for each vertex
- DistanceMap eccentrics(num_vertices(g));
- DistancePropertyMap eccs(eccentrics.begin());
- eccentricities(g, dists, eccs);
-
- cout << "* dists:\n"; dump_distance_matrix(g, dists);
- cout << "* eccs: "; dump_distance_map(g, eccs);
- cout << "* radius: " << radius(g, eccs) << "\n";
- cout << "* diameter: " << diameter(g, eccs) << "\n";
-
- vector<Vertex> cent;
- center(g, eccs, back_inserter(cent));
- cout << "center: ";
- for(size_t x = 0; x < cent.size(); ++x) {
- Vertex v = cent[x];
- cout << get(vertex_index, g, v) << " ";
- }
- cout << "\n";
-
- vector<Vertex> peri;
- periphery(g, eccs, back_inserter(peri));
- cout << "periphery: ";
- for(size_t x = 0; x < peri.size(); ++x) {
- Vertex v = peri[x];
- cout << get(vertex_index, g, v) << " ";
- }
- cout << "\n";
+ cout << "* geodesics: "; print_map(g, dists);
+ cout << "* total geo: " << total_geo << "\n";
+ cout << "* mean geo: " << mean_geo << "\n";
+ cout << "* inv geo: " << inverse_geo << "\n";
+ cout << "* closeness: " << close << "\n";
}
-}
-
-void test_2()
-{
-}
-
-void test_3()
-{
- typedef undirected_graph<VertexProperty, EdgeProperty> Graph;
- typedef Graph::vertex_descriptor Vertex;
- typedef property_map<Graph, int EdgeProperty::*>::type WeightPropertyMap;
-
- typedef tr1::unordered_map<Vertex, int> DistanceMap;
- typedef associative_property_map<DistanceMap> DistancePropertyMap;
-
- Graph g;
- build_graph(g);
-
- Vertex v = *vertices(g).first;
- WeightPropertyMap weights = get(&EdgeProperty::weight, g);
-
- cout << "\nundirected_graph<...>\n";
- {
- DistanceMap distances(num_vertices(g));
- DistancePropertyMap dists(distances);
-
- // compute shortest paths
- dijkstra_shortest_paths(g, v,
- weight_map(weights).
- distance_map(dists)
- );
-
- cout << "* dists: "; dump_distance_map(g, dists);
- cout << "* mean geo: " << mean_geodesic_distance(g, dists) << "\n";
- cout << "* closeness: " << closeness(g, dists) << "\n";
- cout << "* eccentricity: " << eccentricity(g, dists) << "\n";
- }
+ // all-vertices computation
{
- typedef tr1::unordered_map<Vertex, DistanceMap> DistanceMatrix;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ WeightMap weights = get(&EdgeProp::weight, g);
DistanceMatrix dists(num_vertices(g));
- Graph::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- dists[*i].rehash(num_vertices(g));
- }
- // compute all shortest paths
+ // compute all shortest paths so we can run some other stuff
floyd_warshall_all_pairs_shortest_paths(g, dists,
- weight_map(weights));
+ weight_map(weights));
+
+ print_matrix(g, dists);
- // use the distances in all-pairs to compute eccentricities
- // for each vertex
- DistanceMap eccentrics(num_vertices(g));
- DistancePropertyMap eccs(eccentrics);
- eccentricities(g, dists, eccs);
-
- int r, d;
- cout << "* dists:\n"; dump_distance_matrix(g, dists);
- cout << "* eccs: "; dump_distance_map(g, eccs);
- cout << "* radius: " << (r = radius(g, eccs)) << "\n";
- cout << "* diameter: " << (d = diameter(g, eccs)) << "\n";
-
- vector<Vertex> cent;
- center(g, eccs, back_inserter(cent));
- cout << "center: ";
- for(size_t x = 0; x < cent.size(); ++x) {
- Vertex v = cent[x];
- cout << get(vertex_index, g, v) << " ";
- }
- cout << "\n";
-
- vector<Vertex> peri;
- periphery(g, eccs, back_inserter(peri));
- cout << "periphery: ";
- for(size_t x = 0; x < peri.size(); ++x) {
- Vertex v = peri[x];
- cout << get(vertex_index, g, v) << " ";
- }
- cout << "\n";
}
}
-
int
main(int argc, char *argv[])
{
- test_1();
- // test_2();
- test_3();
+ typedef undirected_graph<VertexProp, EdgeProp> Graph;
+ typedef adjacency_list<vecS, vecS, undirectedS, VertexProp, EdgeProp> AdjList;
+
+ cout << "\n*** undirected_graph<> *** \n";
+ test<Graph>();
+
+ cout << "\n*** adjacency_list<> *** \n";
+ test<AdjList>();
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp 2007-07-28 11:35:06 EDT (Sat, 28 Jul 2007)
@@ -16,9 +16,12 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/constant_property_map.hpp>
#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/dijkstra_shortest_paths.hpp>
+
+#include <boost/graph/constant_property_map.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/visitors.hpp>
using namespace std;
using namespace boost;
@@ -38,11 +41,23 @@
return __cxa_demangle(typeid(T).name(), 0, 0, 0);
}
+struct VertexProp
+{
+ int x;
+};
+
+struct EdgeProp
+{
+ EdgeProp() : weight(1) { }
+
+ int weight;
+};
+
template <typename Graph>
void build_graph(Graph& g)
{
- typedef typename Graph::vertex_descriptor Vertex;
- typedef typename Graph::edge_descriptor Edge;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
static const unsigned N = 5;
vector<Vertex> v(N);
@@ -62,66 +77,80 @@
e.push_back(add_edge(v[4], v[0], g).first);
};
-void test_1()
+template <typename Graph>
+void test()
{
- typedef adjacency_list<vecS, vecS, undirectedS> Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef DistanceProperty::container_type DistanceContainer;
- typedef DistanceProperty::map_type DistanceMap;
- typedef constant_property_map<Edge, int> WeightMap;
-
Graph g;
build_graph(g);
- DistanceContainer distances(num_vertices(g));
- DistanceMap dists(make_property_map(distances));
- WeightMap weights(1);
-
- dijkstra_shortest_paths(g, *vertices(g).first,
- weight_map(weights).
- distance_map(dists));
-
- copy(distances.begin(), distances.end(), ostream_iterator<int>(cout, " "));
- cout << "\n";
-}
-void test_2()
-{
- typedef undirected_graph<> Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::edge_descriptor Edge;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef DistanceProperty::container_type DistanceContainer;
- typedef DistanceProperty::map_type DistanceMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
+ typedef typename DistanceProperty::container_type DistanceContainer;
+ typedef typename DistanceProperty::map_type DistanceMap;
- Graph g;
- build_graph(g);
+ // cout << typename_of<typename Graph::graph_tag>() << "\n";
+ // cout << typename_of<DistanceContainer>() << "\n";
+ cout << typename_of<DistanceMap>() << "\n";
+
+ {
+ DistanceContainer dc(num_vertices(g));
+ DistanceMap dm(dc);
+
+ breadth_first_search(g, *vertices(g).first,
+ visitor(make_bfs_visitor(record_distances(dm, on_tree_edge())))
+ );
+ }
- DistanceContainer distances(num_vertices(g));
- DistanceMap dists(make_property_map(distances));
- WeightMap weights(1);
-
- dijkstra_shortest_paths(g, *vertices(g).first,
- weight_map(weights).
- distance_map(dists));
-
- graph_traits<Graph>::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- cout << distances[*i] << " ";
+ // fun with matrices
+ {
+ typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+
+ DistanceMatrix dx(num_vertices(g));
+ WeightMap wm(get(&EdgeProp::weight, g));
+
+ floyd_warshall_all_pairs_shortest_paths(g, dx,
+ weight_map(wm));
+
+ VertexIterator i, j, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ for(j = vertices(g).first; j != end; ++j) {
+ Vertex u = *i, v = *j;
+ std::cout << dx[u][v] << " ";
+ }
+ std::cout << "\n";
+ }
+
+ // now comes the really fun part... slicing the matrix into
+ // a new property map... Good stuff.
+ std::cout << "slice:\n";
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ DistanceMap dm(dx[*i]);
+ for(tie(j, end) = vertices(g); j != end; ++j) {
+ std::cout << dm[*j] << " ";
+ }
+ std::cout << "\n";
+ }
}
- cout << "\n";
}
int
main(int argc, char *argv[])
{
- test_1();
- test_2();
+ typedef adjacency_list<vecS, vecS, undirectedS, VertexProp, EdgeProp> AdjVector;
+ typedef adjacency_list<listS, listS, undirectedS, VertexProp, EdgeProp> AdjList;
+ typedef undirected_graph<VertexProp, EdgeProp> Graph;
+
+ cout << "\n*** adjacency_list<vecS, vecS> ***\n";
+ test<AdjVector>();
+
+ // cout << "\n*** adjacency_list<listS, listS> ***\n";
+ // test<AdjList>();
+
+ cout << "\n*** undirected_graph<> ***\n";
+ test<Graph>();
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk