From: asutton_at_[hidden]
Date: 2007-07-25 12:06:13
Author: asutton
Date: 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
New Revision: 7537
URL: http://svn.boost.org/trac/boost/changeset/7537
Log:
Documentations
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/exterior_property.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/clique.hpp | 20 ++++++++++----------
sandbox/SOC/2007/graphs/boost/graph/cycle.hpp | 11 ++++-------
sandbox/SOC/2007/graphs/boost/graph/distance.hpp | 9 +++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk | 4 ++++
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk | 2 ++
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk | 1 +
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk | 3 +++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk | 11 ++---------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk | 12 ++++++++----
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 6 ++++++
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 36 +++++++++++++++++-------------------
sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp | 2 +-
sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp | 4 ++--
sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp | 1 +
14 files changed, 70 insertions(+), 52 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/clique.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clique.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/clique.hpp 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -71,20 +71,20 @@
{
template <typename Graph>
inline bool
- is_connected(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- typename graph_traits<Graph>::undirected_category)
+ is_connected_to_clique(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ typename graph_traits<Graph>::undirected_category)
{
return edge(u, v, g).second;
}
template <typename Graph>
inline bool
- is_connected(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- typename graph_traits<Graph>::directed_category)
+ is_connected_to_clique(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ typename graph_traits<Graph>::directed_category)
{
// Note that this could alternate between using an or to determine
// full connectivity. I believe that this should produce strongly
@@ -107,7 +107,7 @@
typename graph_traits<Graph>::directed_category cat;
typename Container::const_iterator i, end = in.end();
for(i = in.begin(); i != end; ++i) {
- if(is_connected(g, v, *i, cat)) {
+ if(is_connected_to_clique(g, v, *i, cat)) {
out.push_back(*i);
}
}
@@ -206,7 +206,7 @@
template <typename Graph, typename Visitor>
inline void
- visit_cliques(const Graph& g, Visitor vis)
+ bron_kerbosch_visit_cliques(const Graph& g, Visitor vis)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
Modified: sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/cycle.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/cycle.hpp 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -269,7 +269,6 @@
// each path investigation starts at the ith vertex
p.push_back(v);
- vis.start_vertex(v, g);
while(1) {
// extend the path until we've reached the end or the
@@ -290,17 +289,15 @@
break;
}
}
-
- vis.finish_vertex(v, g);
}
}
template <typename Graph, typename Visitor>
inline void
- visit_cycles(const Graph& g,
- Visitor vis,
- std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
- std::size_t minlen = 2)
+ tiernan_visit_cycles(const Graph& g,
+ Visitor vis,
+ std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
+ std::size_t minlen = 2)
{
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
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-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -71,6 +71,7 @@
// 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,
@@ -79,7 +80,15 @@
{
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
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -12,6 +12,7 @@
[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
+
[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
@@ -34,8 +35,11 @@
[template BoostDijkstraVisitor[] [link boost_graph.concepts.visitor_concepts.dijksta_visitor DijkstraVisitor]]
[template BoostBellmanfordVisitor[] [link boost_graph.concepts.visitor_concepts.bellmanford_visitor BellmanFordVisitor]]
[template BoostAStarVisitor[] [link boost_graph.concepts.visitor_concepts.a_star_visitor A\*Visitor]]
+[template BoostCliqueVisitor[] [link boost_graph.concepts.visitor_concepts.clique_visitor [^CliqueVisitor]]]
+[template BoostCycleVisitor[] [link boost_graph.concepts.visitor_concepts.cycle_visitor [^CycleVisitor]]]
[template BoostEventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
[template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
[/ A bunch of miscellaneus concepts]
[template BoostColorValue[] [link boost_graph.concepts.miscellaneous_concepts.color_value ColorValue]]
+[template BoostExteriorProperty[] [link boost_graph.concepts.utility.exterior_property [^ExteriorProperty]]]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -35,3 +35,5 @@
[template boost_connected_components[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
+
+[template boost_exterior_vertex_property[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,54 @@
+[/
+ / 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 Clique Visitor]
+The clique visitor concept defines requirements for types that act as visitors
+of clique-detection algorithms. Objects of this type are passed to these
+algorithms and are invoked when a clique is found within a graph.
+
+[heading Refinement Of]
+[BoostVisitor]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Visit Clique]
+ [`vis.clique(vs,g)`]
+ [`void`]
+ [
+ *Semantics:* The `clique()` member function of the visitor is invoked
+ when a fully connected subgraph is identified in the graph `g`.
+
+ *Requirements:* `g` is an object whose type `G` is a refinement of the
+ [BoostGraph] concept.
+
+ *Requirements:* `vs` is an object whose type `VS` is a refinement of the
+ [SgiContainer] concept. The `value_type` of `VS` must be the `vertex_descriptor`
+ of `G`.
+
+ *Precondition:* All vertices in the [SgiContainer] `vs` are connected.
+ If `g` is a directed graph, then all vertices, /u/ and /v/, are connected
+ by edges /(u,v)/ and /(v,u)/.
+ ]
+ ]
+]
+
+[heading C++0x]
+This concept is defined as:
+
+ concept CliqueVisitor<typename T>
+ {
+ Graph graph_type;
+
+ template<Container VertexSet>
+ requires SameType<VertexSet::value_type, graph_type::vertex_descriptor>
+ void
+ T::clique(const VertexSet&, graph_type&);
+ };
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -30,6 +30,7 @@
[[vis] [An object of type V]]
]
+[include utility.qbk]
[include graphs.qbk]
[include visitors.qbk]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,52 @@
+[/
+ / 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 Cycle Visitor]
+The cycle visitor concept defines requirements for types that act as visitors
+of cycle-detection algorithms. Objects of this type are passed to these
+algorithms and are invoked when a cycle is found within a graph.
+
+[heading Refinement Of]
+[BoostVisitor]
+
+[heading Valid Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Visit Cycle]
+ [`vis.cycle(vs,g)`]
+ [`void`]
+ [
+ *Semantics:* The `cycle()` member function of the visitor is invoked
+ when a cycle is identified in the graph `g`.
+
+ *Requirements:* `g` is an object whose type `G` is a refinement of the
+ [BoostGraph] concept.
+
+ *Requirements:* `vs` is an object whose type `VS` is a refinement of the
+ [SgiSequence] concept. The `value_type` of `VS` must be the `vertex_descriptor`
+ of `G`.
+
+ *Precondition:* The vertices in `vs` are arranged such that first vertex
+ is connected to the second, and that is connected to the third, etc. The
+ last vertex is connected to the the first.
+ ]
+ ]
+]
+
+[heading C++0x]
+This concept is defined as:
+
+ concept CycleVisitor<typename T>
+ {
+ typename graph_type;
+ typename vertex_set_type;
+
+ T::cycle(const vertex_set_type&, graph_type&);
+ };
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/exterior_property.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/exterior_property.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,101 @@
+[/
+ / 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 Exterior Property]
+The `ExteriorProperty` concept defines requirements for the generic
+declaration and initialization of exterior properties and their
+proeprty maps for graphs. Exterior properties consist of two components:
+a container that maps a descriptor to a property value and its property
+map - the abstracted interface used by most Boost.Graph algorithms
+for accessing vertex and edge properties.
+
+[heading Notation]
+The following expressions are used within this document:
+[table
+ [[Expression] [Description]]
+ [[P] [An type modeling the `ExteriorProperty` concept.]]
+]
+
+[heading Associated Types]
+[table
+ [[Name] [Type] [Description]]
+ [
+ [Value Type]
+ [`P::value_type`]
+ [
+ *Semantics:* The value type of the property map.
+
+ *Requirements:* `value_type` must be [SgiAssignable] and
+ [SgiDefaultConstructible].
+ ]
+ ]
+ [
+ [Value Type]
+ [`P::key_type`]
+ [
+ *Semantics:* The key type of the property map. This type must be
+ either an `edge_descriptor` or `vertex_descriptor`.
+
+ *Requirements:* `key_type` must be [SgiCopyConstructible].
+ ]
+ ]
+ [
+ [Container Type]
+ [`P::container_type`]
+ [
+ *Semantics:* The container type used to map objects of `key_type`
+ to their associated property values of type `value_type`.
+
+ *Requirements:* The container must be size-constructible in that
+ it must have a constructor that takes a single argument: the number
+ elements in the container.
+
+ *Requirements:* The container type must implement the `operator []`
+ function, taking an object of type `key_type` returning an object
+ of type `value_type`.
+ ]
+ ]
+ [
+ [Property Map Type]
+ [`P::map_type`]
+ [
+ *Semantics:* The property map type used to abstract the access
+ graph properties.
+
+ *Requirements:* `map_type` must model the [BoostReadWritePropertyMap]
+ concept.
+ ]
+ ]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Property Map Initializer]
+ [`make_property_map(c)`]
+ [['unspecified]]
+ [
+ *Semantics:* The initializer function returns a value suitable for
+ constructing the property map from the given container, `c`.
+
+ *Requirements:* `c` is of type `P::container_type`.
+
+ *Preconditions:* `c` is not empty.
+ ]
+ ]
+]
+
+[heading Complexity Guarantees]
+The `P::container_type::operator []()` function must return, on average, in
+constant time. The worst-case time is allowed to be linear with respect to
+the number of keys.
+
+[heading Models]
+[boost_exterior_vertex_property]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,14 @@
+[/
+ / 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 Concepts]
+This section describes utlity graph concepts - those that do not necessarily
+pertain explicitly to graphs or visitors for algorithms.
+
+[include exterior_property.qbk]
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -21,7 +21,10 @@
[include dfs_visitor.qbk]
[include dijkstra_visitor.qbk]
[include bellman_ford_visitor.qbk]
+[include clique_visitor.qbk]
+[include cycle_visitor.qbk]
[include event_visitor.qbk]
[include event_visitor_list.qbk]
+
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -7,19 +7,12 @@
[section Clique]
- struct clique_visitor
- {
- template <typename VertexSet>
- void clique(VertexSet)
- { }
- };
-
template <typename Graph, typename Visitor>
void
bron_kerbosch_visit_cliques(const Graph& g, Visitor vis)
These functions find all /cliques/ (maximal fully connected subgraphs) of the
-given graph, invoking a visitor when each clique is found. See the
+given graph, invoking a visitor when each clique is found.
The `bron_kerbosch_visit_cliques()` function is intended for use with undirected
graphs, but will work for directed graphs as well at added cost. In order for a
@@ -48,7 +41,7 @@
[required, in] [`Visitor vis`]
[
The visitor object to the algorithm. This `Visitor` class must
- model the `CliqueVisitor` class.
+ model the [BoostCliqueVisitor] class.
]
]
]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,61 @@
+[/
+ / 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 Clique]
+
+ template <typename Graph, typename Visitor>
+ void
+ tiernan_visit_cycles(const Graph& g, Visitor vis)
+
+These functions find all /cycles/ within of the given graph, invoking a visitor
+when each clique is found.
+
+The `tiernan_visit_cycles()` function is designed to work on directed graph, but
+works for undirected graphs as well. When running on undirected graphs, however,
+the algorithm treats each edge connecting two vertices /(u,v)/ as if it were
+two edges /(u,v)/ and /(v,u)/. As result the algorithm will report cycles in
+both directions.
+
+[heading Where Defined]
+`boost/graph/clique.hpp`
+
+[heading Parameters]
+
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which cliques are being visited. The `Graph` type must
+ /approximate/ the [BoostAdjacencyMatrix] in that it must implement
+ the `edge(u,v,g)` function. It is not, however, required to return
+ in constant time. Note that most graph types provide this function,
+ including [boost_adjacency_list], [boost_undirected_graph], and
+ [boost_directed_graph].
+ ]
+ ]
+ [
+ [required, in] [`Visitor vis`]
+ [
+ The visitor object to the algorithm. This `Visitor` class must
+ model the [BoostCliqueVisitor] class.
+ ]
+ ]
+]
+
+[h5 Return Value]
+This function does not return a value.
+
+[h5 Complexity]
+No complexity has been reported for this algorithm, but it is expected to
+run in /O(P(g))/ where /P(g)/ is the number of distinct simple paths in the
+graph /g/ (which can be very large).
+
+[h5 Examples]
+
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,140 @@
+[/
+ / 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 Eccentricity]
+
+ template <typename Graph, typename DistanceMap>
+ property_traits<DistanceMap>::value_type
+ eccentricity(const Graph&g, DistanceMap dist)
+
+This function computes the /eccentricity/ of a vertex in a graph. The eccentricity
+of a vertex is defined as the maximum geodesic distance (shortest paths) to any
+other vertex in the graph. 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_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 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.
+
+If the graph is unconnected, then the eccentricity of any vertex will be
+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 measure will be computed. The
+ `Graph` type is required to be a model of [BoostVertexListGraph].
+ ]
+ ]
+ [
+ [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.
+ ]
+ ]
+]
+
+[h5 Return Value]
+The `eccentricity()` function returns the closeness of the vertex for which
+`dist` was computed.
+
+[h5 Complexity]
+The `eccentricity()` function has /O(V)/ time complexity.
+
+[h5 Examples]
+This example computes shows the construction of a simple undirected graph and
+illustrates how to compute the `eccentricity()` for a vertex.
+
+[figure
+ images/reference/geodesic.png
+ [*Figure 1.] A simple undirected, unweighted graph.
+]
+
+This graph can be constructed programmatically as:
+
+ typedef undirected_graph<> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // Instantiate the graph and vector of vertices.
+ Graph g;
+ vector<Vertex> v(10);
+
+ // Add vertices to the graph, recording their descriptors into
+ // the vertex vector.
+ for(size_t i = 0; i < 10; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // Connect the vertices by adding edges to the graph. This builds
+ // the graph shown in Figure 1.
+ add_edge(v[0], v[1], g); add_edge(v[1], v[2], g);
+ add_edge(v[1], v[3], g); add_edge(v[2], v[4], g);
+ add_edge(v[3], v[5], g); add_edge(v[4], v[6], g);
+ add_edge(v[4], v[7], g); add_edge(v[4], v[8], g);
+ add_edge(v[5], v[8], g); add_edge(v[6], v[9], g);
+ add_edge(v[7], v[9], g); add_edge(v[8], v[9], g);
+
+ // Initialize an exterior property for recording the distances
+ // to every vertex in the graph.
+ typedef exterior_property<Graph, int> DistanceProperty;
+ typedef DistanceProperty::container_type DistanceContainer;
+ typedef DistanceProperty::map_type DistanceMap;
+ DistanceContainer distances(10);
+ DistanceMap dist(make_property_map(dists));
+
+ // Initialize the distance to-self of vertex 0 and run a breadth-first
+ // search on the graph to compute the distance of the shortest path
+ // from vertex 0 to all others.
+ dist[v[0]] = 0;
+ breadth_first_search(g, v[0],
+ visitor(make_bfs_visitor(record_distances(dist, on_tree_edge())))
+ );
+
+Computing the `eccentricity()` for vertex 0 is trivial.
+
+ cout << "eccentricity == " << eccentricity(g, dist) << end;
+
+The output of this program is:
+
+[pre
+mean geodesic distance == 5
+]
+
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -0,0 +1,106 @@
+[/
+ / 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 Exterior Vertex Property]
+
+ template <typename Graph, typename Value>
+ class exterior_vertex_property;
+
+The `exterior_vertex_property` class is a utility for generically creating
+and initializing exterior properties for graph classes.
+
+[note
+In fact, this class is the /only/ way to generically create exterior properties
+for graphs.
+]
+
+[heading Notation]
+The following expressions are used in this document:
+[table
+ [[Expression] [Description]]
+ [[`G`] [A graph type modeling a refinement of the [BoostGraph] concept.]]
+ [[`V`] [A value type that models the [SgiAssignable] concept.]]
+]
+
+[heading Model Of]
+[BoostExteriorProperty]
+
+[heading Template Parameters]
+[table
+ [[Parameter] [Description]]
+ [
+ [`Graph`]
+ [
+ *Semantics:* Specifies the type of graph for which the property
+ is being declared.
+
+ *Requirements:* `Graph` must model a refinement of the the
+ [BoostGraph] concept.
+ ]
+ ]
+ [
+ [`Value`]
+ [
+ *Semantics:* Specifies the value type of the exterior property.
+ ]
+ ]
+]
+
+[heading Where Defined]
+`boost/graph/exterior_property.hpp`
+
+[heading Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`P<G,V>::value_type`]
+ [
+ This is the same as the template parameter `Value`.
+ ]
+ ]
+ [
+ [`P<G,V>::key_type`]
+ [
+ This is the same as `graph_traits<G>::vertex_descriptor`.
+ ]
+ ]
+ [
+ [`P<G,V>::container_type`]
+ [
+ This type selects the preferred property container based on the
+ type of graph such that values are accessed in constant time
+ on average.
+ ]
+ ]
+ [
+ [`P<G,V>::map_type`]
+ [
+ This type selects the preferred property map type based on the
+ type of graph.
+ ]
+ ]
+]
+
+[heading Examples]
+Using the `exterior_vertex_property` it is possible to generically create
+exterior properties for a graph. Consider the following template function:
+
+ template <typename Graph, typename Weight>
+ void
+ do_shortest_paths(const Graph& g, Weight w = ())
+ {
+ typedef exterior_vertex_property<Graph, Weight> DistanceProperty;
+ typedef DistanceProperty::container_type DistanceContainer;
+ typedef DistanceProeprty::map_type DistanceMap;
+
+ DistanceContainer distances(num_vertices(g));
+ DistanceMap dist(make_property_map(distances));
+
+ dijkstra_shortest_paths(g, *vertices(g).first, distance_map(dist));
+ }
+
+[endsect]
\ 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-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -31,9 +31,13 @@
an unweighted, undirected graph, 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 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 `dist` was computed.
+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`
@@ -44,7 +48,7 @@
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 \
+vertex for which this is computed is that for which `dist` originally
computed. The mean geodesic distance is implemeted as:
[$images/eq/mean_geodesic.png]
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-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -15,6 +15,7 @@
[endsect]
[section Traits Classes]
+[include exterior_vertex_property.qbk]
[endsect]
[section Event Visitor List Adaptors]
@@ -50,6 +51,11 @@
[include connectivity.qbk]
[endsect]
+[section Subgraph Finding Algorithms]
+[include clique.qbk]
+[include cycle.qbk]
+[endsect]
+
[section Maximum Flow Algorithms]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -1,26 +1,31 @@
exe properties
- : properties.cpp
- : <include>../../../
- ;
+ : properties.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
exe mutable
- : mutable.cpp
- : <include>../../../
- ;
+ : mutable.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
exe index
- : index.cpp
- : <include>../../../
- ;
+ : index.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
exe range
- : range.cpp
- : <include>../../../
- ;
+ : range.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
exe misc
: misc.cpp
+ : <include>$BOOST_ROOT
: <include>../../../
;
@@ -65,10 +70,3 @@
: <include>$BOOST_ROOT
: <include>../../../
;
-
-# exe parameter
-# : parameter.cpp
-# : <include>$BOOST_ROOT
-# : <include>../../../
-# ;
-
Modified: sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -76,7 +76,7 @@
// make_prism_graph(g, 3, 2);
make_complete_graph(g, 5);
- visit_cliques(g, clique_printer<ostream>(cout));
+ bron_kerbosch_visit_cliques(g, clique_printer<ostream>(cout));
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp 2007-07-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -107,10 +107,10 @@
make_complete_graph(g, 4);
size_t count = 0;
- visit_cycles(g, count_cycles(count));
+ tiernan_visit_cycles(g, count_cycles(count));
std::cout << "number of cycles: " << count << "\n";
- visit_cycles(g, print_cycles(cout));
+ tiernan_visit_cycles(g, print_cycles(cout));
}
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-25 12:06:08 EDT (Wed, 25 Jul 2007)
@@ -112,6 +112,7 @@
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";
}