|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-07-20 12:36:54
Author: asutton
Date: 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
New Revision: 7490
URL: http://svn.boost.org/trac/boost/changeset/7490
Log:
Working on reference docs.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
- copied, changed from r7489, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp | 4
sandbox/SOC/2007/graphs/boost/graph/distance.hpp | 10 --
sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp | 12 +++
sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk | 5 -
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk | 124 ++++++++++++++++++++++++++++++++++++++-
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 3
sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk | 3
8 files changed, 138 insertions(+), 29 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-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -139,14 +139,12 @@
(graph, *)
(out(components), *))
(optional
- // (number, std::size_t, 0)
+ (number, (std::size_t), 0)
(component_map, *, parameter::void_())
(out(color_map), *, parameter::void_())
(vertex_index_map, *, get(vertex_index, graph)))
)
{
- typename graph_traits<graph_type>::vertices_size_type number(0);
-
// step 1, get the components (maybe), returning the number
return detail::fetch_connected_components(graph,
components,
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-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -9,6 +9,7 @@
// boost includes
#include <boost/graph/named_parameters.hpp>
+#include <boost/graph/exterior_property.hpp>
#include <boost/graph/properties.hpp>
namespace boost
@@ -28,7 +29,6 @@
}
}
-
// 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.
@@ -51,14 +51,13 @@
// 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[get(vertex_index, g, v)];
+ return dist[v];
}
template <typename Graph, typename DistanceMap>
@@ -102,11 +101,6 @@
return dummy(1) / double(detail::sum_distances(g, dist));
}
- // Can we abstract the computation of max on distances to max of
- // something else that we can put into a distance map? For example,
- // this is the max of geodesics... What if we wanted some other
- // operator?
-
// Note that the DistanceMap::value_type must be constructible
// as 0 - basically indicating an acceptable default value.
template <typename Graph, typename DistanceMap>
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-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -7,8 +7,16 @@
#ifndef BOOST_GRAPH_NAMED_PARAMETERS_HPP
#define BOOST_GRAPH_NAMED_PARAMETERS_HPP
-// TODO: There's a problem with Boost.Parameter library - it just
-// doesn't like > 5 parameters.
+#ifndef BOOST_GRAPH_REQUIRED_PARAMA_ARITY
+# define BOOST_GRAPH_REQUIRED_PARAM_ARITY 10
+#endif
+
+#if defined(BOOST_PARAMETER_MAX_ARITY) && \
+ (BOOST_PARAMETER_MAX_ARIT < BOOST_GRAPH_REQUIRED_PARAM_ARITY)
+# warning "BOOST_PARAMETER_MAX_ARITY is too small for Boost.Graph"
+#else
+# define BOOST_PARAMETER_MAX_ARITY BOOST_GRAPH_REQUIRED_PARAM_ARITY
+#endif
#include <boost/parameter.hpp>
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -23,8 +23,8 @@
]
[/ Templates /]
-[template super[x] '''<superscript>'''[x]'''</superscript>''']
-[template sub[x] '''<subscript>'''[x]'''</subscripts>''']
+[template super[x]'''<superscript>'''[x]'''</superscript>''']
+[template sub[x]'''<subscript>'''[x]'''</subscript>''']
[template figure[path caption]
'''
@@ -33,7 +33,7 @@
<imagedata fileref="'''[path]'''" align="center"/>
</imageobject>
<caption>
- <para style="text-align: center">'''[caption]'''</para>
+ <para>'''[caption]'''</para>
</caption>
</mediaobject>
'''
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -199,9 +199,4 @@
// write some code to that effect.
-[h5 Details]
-The signature of this function may change in the future to include a new parameter, `_number`,
-which indicates the number of components computed by [boost_connected_components]. This
-introduces a new calling "profile" that would bypass the computation of the number of components.
-
[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
+++ (empty file)
@@ -1,29 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Measures of Distances]
-This section contains references for a suite of functions related to the
-distance metrics on a graph.
-
- 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)
-
- template <typename Graph, typename DistanceMap>
- inline double
- mean_geodesic_distance(const Graph& g, DistanceMap dist)
-
- template <typename Graph, typename DistanceMap, typename T>
- T
- mean_geodesic_distance(const Graph& g,
- DistanceMap dist,
- const T& dummy)
-
-
-[endsect]
\ No newline at end of file
Copied: sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk (from r7489, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -5,9 +5,7 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Measures of Distances]
-This section contains references for a suite of functions related to the
-distance metrics on a graph.
+[section Geodesic Distances]
template <typename Graph, typename DistanceMap>
typename property_traits<DistanceMap>::value_type
@@ -21,9 +19,123 @@
template <typename Graph, typename DistanceMap, typename T>
T
- mean_geodesic_distance(const Graph& g,
- DistanceMap dist,
- const T& dummy)
+ 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.
+
+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
+[boost_breadh_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 algorithms is a `DistanceMap`, which is (in turn) used as the
+input of these functions. Note then, that these functions compute measures
+of the vertex for which the `DistanceMap` was computed.
+
+The `geodesic_distance(g,dist)` 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(g,dist,T())` 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 the `DistanceMap` was
+originally computed. The mean geodesic distance is often given as:
+
+[$images/eq/mean_geodesic.png]
+
+where ['d[sub G](u, v)] is the geodesic distance (shortest path) from vertices
+/u/ to /v/.
+
+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.
+
+[heading Where Defined]
+`boost/graph/distance.hpp`
+
+[heading Parameters]
+
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph object for which the distribution will be computed. If
+ the `_distribution` or `_in_distribution` arguments are supplied
+ when calling this function then `_graph` must be a model of
+ [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+ then `_graph` must be a model of [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [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
+ from one source vertex to all others in the graph. The `DistanceMap`
+ must be a model of [BoostReadWritePropertyMap], they `key_type` must
+ be the `vertex_descriptor` of `Graph`.
+ ]
+ ]
+ [
+ [required, in] [`const T& dummy`]
+ [
+ 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.
+ ]
+ ]
+]
+
+[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.
+]
+
+[h5 Return Value]
+The `geodesic_distance(g,v,dist)` function returns the distance of the shortest
+path to `v`.
+
+The `mean_geodesic_distance(g,dist)` function returns the (arithmatic) mean of
+the shortest distances to all other vertices.
+
+[h5 Complexity]
+The `geodesic_distance(g,v,dist)` has O(1) time complexity.
+
+The `mean_geodesic_distance(g,dist)` has O(n) time complexity.
+
+[h5 Examples]
+[note
+Write some examples...
+]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -61,7 +61,8 @@
[section Graph Measures]
[include distributions.qbk]
-[include distance.qbk]
+[include geodesic.qbk]
+[include closeness.qbk]
[endsect]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk 2007-07-20 12:36:52 EDT (Fri, 20 Jul 2007)
@@ -38,4 +38,5 @@
[template SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html BidirectionalIterator]]
[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html RandomAccessIterator]]
-[template SgPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
+[template SgiPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
+[template SgiMonoid[] [@http://www.sgi.com/tech/stl/Monoid.html Monoid]]
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