|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-17 15:24:47
Author: asutton
Date: 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
New Revision: 38752
URL: http://svn.boost.org/trac/boost/changeset/38752
Log:
Changed the names of almost everry template and propagated those changes
to just about every file.
Also, finished breaking apart most of the measure functions
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2 | 11
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk | 65 +++---
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk | 121 ++++++-----
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk | 12
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk | 8
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk | 12
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk | 10
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk | 16
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk | 34 +-
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk | 16
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk | 24 +-
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk | 12
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk | 9
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk | 8
sandbox/SOC/2007/graphs/libs/graph/doc/images/reference/Makefile | 2
sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk | 24 +-
sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk | 14
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk | 293 +++++++++++++---------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk | 410 +++++++++++++++++++++++++++++----------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk | 10
sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk | 12
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk | 14
sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk | 370 +++++++++++++++++++++++------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk | 6
sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk | 389 +++++++++++++++++++++++--------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk | 14
sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk | 14
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 2
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk | 14
sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk | 12
40 files changed, 1195 insertions(+), 815 deletions(-)
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -15,15 +15,20 @@
# Use graphics not text for navigation:
<xsl:param>navig.graphics=1
# How far down we chunk nested sections, basically all of them:
- <xsl:param>chunk.section.depth=10
+ # Setting this to 4 will put all reference functions into the
+ # same page... and make all external links to those pages bounce
+ # to the top of them.
+ <xsl:param>chunk.section.depth=5
# Don't put the first section on the same page as the TOC:
<xsl:param>chunk.first.sections=1
# How far down sections get TOC's
- <xsl:param>toc.section.depth=10
+ <xsl:param>toc.section.depth=5
# Max depth in each TOC:
+ # I could increase this, but that makes the top-level ToC
+ # extremely long.
<xsl:param>toc.max.depth=3
# How far down we go with TOC's
- <xsl:param>generate.section.toc.level=10
+ <xsl:param>generate.section.toc.level=5
# Logo location:
<xsl:param>boost.logo=../boost.png
<xsl:param>annotation.support=1
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-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -10,61 +10,62 @@
/]
-[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
+[template MultiPassInputIterator[] [@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]]
+[template ReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html [^ReadablePropertyMap]]]
+[template WritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html [^WritablePropertyMap]]]
+[template ReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html [^ReadWritePropertyMap]]]
-[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph [^Graph]]]
-[template BoostIncidenceGraph[] [link
+
+[template Graph[] [link boost_graph.concepts.graph_concepts.graph [^Graph]]]
+[template IncidenceGraph[] [link
boost_graph.concepts.graph_concepts.incidence_graph
[^IncidenceGraph]]]
-[template BoostBidirectionalGraph[] [link
+[template BidirectionalGraph[] [link
boost_graph.concepts.graph_concepts.bidirectional_graph
[^BidirectionalGraph]]]
-[template BoostVertexListGraph[] [link
+[template VertexListGraph[] [link
boost_graph.concepts.graph_concepts.vertex_list_graph
[^VertexListGraph]]]
-[template BoostEdgeListGraph[] [link
+[template EdgeListGraph[] [link
boost_graph.concepts.graph_concepts.edge_list_graph
[^EdgeListGraph]]]
-[template BoostAdjacencyGraph[] [link
+[template AdjacencyGraph[] [link
boost_graph.concepts.graph_concepts.adjacency_graph
[^AdjacencyGraph]]]
-[template BoostAdjacencyMatrix[] [link
+[template AdjacencyMatrix[] [link
boost_graph.concepts.graph_concepts.adjacency_matrix
[^AdjacencyMatrix]]]
-[template BoostMutableGraph[] [link
+[template MutableGraph[] [link
boost_graph.concepts.graph_concepts.mutable_graph
[^MutableGraph]]]
-[template BoostPropertyGraph[] [link
+[template PropertyGraph[] [link
boost_graph.concepts.graph_concepts.property_graph
[^PropertyGraph]]]
-[template BoostMutablePropertyGraph[] [link
+[template MutablePropertyGraph[] [link
boost_graph.concepts.graph_concepts.mutable_property_graph
[^MutablePropertyGraph]]]
-[template BoostVertexIndexGraph[] [link
+[template VertexIndexGraph[] [link
boost_graph.concepts.graph_concepts
[^VertexIndexGraph]]]
-[template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
-[template BoostBFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
-[template BoostDFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
-[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]]
+[template Visitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
+[template BFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
+[template DFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
+[template DijkstraVisitor[] [link boost_graph.concepts.visitor_concepts.dijksta_visitor DijkstraVisitor]]
+[template BellmanfordVisitor[] [link boost_graph.concepts.visitor_concepts.bellmanford_visitor BellmanFordVisitor]]
+[template AStarVisitor[] [link boost_graph.concepts.visitor_concepts.a_star_visitor A\*Visitor]]
+[template CliqueVisitor[] [link boost_graph.concepts.visitor_concepts.clique_visitor [^CliqueVisitor]]]
+[template CycleVisitor[] [link boost_graph.concepts.visitor_concepts.cycle_visitor [^CycleVisitor]]]
+[template EventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
+[template EventVisitorList[] [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 BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor [^Descriptor]]]
-[template BoostNumericValue[] [link boost_graph.concepts.general_concepts.numeric_value [^NumericValue]]]
-[template BoostPropertyMap[] [link boost_graph.concepts.general_concepts.property_map [^PropertyMap]]]
-[template BoostPropertyMatrix[] [link boost_graph.concepts.general_concepts.property_matrix [^PropertyMatrix]]]
-[template BoostDegreeMeasure[] [link boost_graph.concepts.general_concepts.degree_measure [^DegreeMeasure]]]
-[template BoostDistanceMeasure[] [link boost_graph.concepts.general_concepts.distance_measure [^DistanceMeasure]]]
+[template ColorValue[] [link boost_graph.concepts.miscellaneous_concepts.color_value ColorValue]]
+[template Descriptor[] [link boost_graph.concepts.graph_concepts.descriptor [^Descriptor]]]
+[template NumericValue[] [link boost_graph.concepts.general_concepts.numeric_value [^NumericValue]]]
+[template PropertyMap[] [link boost_graph.concepts.general_concepts.property_map [^PropertyMap]]]
+[template PropertyMatrix[] [link boost_graph.concepts.general_concepts.property_matrix [^PropertyMatrix]]]
+[template DegreeMeasure[] [link boost_graph.concepts.general_concepts.degree_measure [^DegreeMeasure]]]
+[template DistanceMeasure[] [link boost_graph.concepts.general_concepts.distance_measure [^DistanceMeasure]]]
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-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -10,98 +10,113 @@
/]
-[template boost_constant_property_map[] [link
- boost_graph
+[template constant_property_map[] [link
+ graph
[^constant_property_map]]]
[/ Graph traits and types /]
-[template boost_graph_traits[] [link boost_graph.reference_guide.traits_classes.graph_traits [^graph_traits]]]
-[template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph [^undirected_graph]]]
-[template boost_directed_graph[] [link boost_graph.reference_guide.graph_types.directed_graph [^directed_graph]]]
-[template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list [^adjacecncy_list]]]
-[template boost_edge_list[] [link boost_graph.reference_guide.graph_types.edge_list [^edge_list]]]
+[template graph_traits[] [link boost_graph.reference.traits_classes.graph_traits [^graph_traits]]]
+[template undirected_graph[] [link boost_graph.reference.graph_types.undirected_graph [^undirected_graph]]]
+[template directed_graph[] [link boost_graph.reference.graph_types.directed_graph [^directed_graph]]]
+[template adjacency_list[] [link boost_graph.reference.graph_types.adjacency_list [^adjacecncy_list]]]
+[template edge_list[] [link boost_graph.reference.graph_types.edge_list [^edge_list]]]
[/ Visitor types /]
-[template boost_null_visitor[] [link boost_graph.reference_guide.visitor_types.null_visitor [^null_visitor]]]
-[template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor [^bfs_visitor]]]
-[template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor [^dfs_visitor]]]
-[template boost_predecessor_recorder[] [link boost_graph.reference_guide.event_visitors.predecessor_recorder [^predecessor_recorder]]]
-[template boost_distance_recorder[] [link boost_graph.reference_guide.event_visitors.distance_recorder [^distance_recorder]]]
-[template boost_time_stamper[] [link boost_graph.reference_guide.event_visitors.time_stamper [^time_stamper]]]
-[template boost_property_writer[] [link boost_graph.reference_guide.event_visitors.property_writer [^property_writer]]]
+[template null_visitor[] [link boost_graph.reference.visitor_types.null_visitor [^null_visitor]]]
+[template bfs_visitor[] [link boost_graph.reference.visitor_types.bfs_visitor [^bfs_visitor]]]
+[template dfs_visitor[] [link boost_graph.reference.visitor_types.dfs_visitor [^dfs_visitor]]]
+[template predecessor_recorder[] [link boost_graph.reference.event_visitors.predecessor_recorder [^predecessor_recorder]]]
+[template distance_recorder[] [link boost_graph.reference.event_visitors.distance_recorder [^distance_recorder]]]
+[template time_stamper[] [link boost_graph.reference.event_visitors.time_stamper [^time_stamper]]]
+[template property_writer[] [link boost_graph.reference.event_visitors.property_writer [^property_writer]]]
[/ Fundamental /]
-[template boost_breadth_first_search[] [link
- boost_graph.reference_guide.algorithms.fundamental.breadth_first_search
+[template breadth_first_search[] [link
+ boost_graph.reference.algorithms.fundamental.breadth_first_search
[^breadth_first_search()]]]
-[template boost_depth_first_search[] [link
- boost_graph.reference_guide.algorithms.fundamental.depth_first_search
+[template depth_first_search[] [link
+ boost_graph.reference.algorithms.fundamental.depth_first_search
[^depth_first_search()]]]
[/ Shortest Path /]
-[template boost_dijkstra_shortest_paths[] [link
- boost_graph.reference_guide.algorithms.shortest_paths.dijkstra_shortest_paths
+[template dijkstra_shortest_paths[] [link
+ boost_graph.reference.algorithms.shortest_paths.dijkstra_shortest_paths
[^dijkstra_shortest_paths()]]]
-[template boost_bellman_ford_shortest_paths[] [link
- boost_graph.reference_guide.algorithms.shortest_paths.bellman_ford_shortest_paths
+[template bellman_ford_shortest_paths[] [link
+ boost_graph.reference.algorithms.shortest_paths.bellman_ford_shortest_paths
[^bellman_ford_shortest_paths()]]]
-[template boost_floyd_warshall_all_pairs_shortest_paths[] [link
- boost_graph.reference_guide.algorithms.shortest_paths.floyd_warshall_all_pairs_shortest_paths
+[template floyd_warshall_all_pairs_shortest_paths[] [link
+ boost_graph.reference.algorithms.shortest_paths.floyd_warshall_all_pairs_shortest_paths
[^floyd_warshall_all_pairs_shortest_paths()]]]
-[template boost_johnson_all_pairs_shortest_paths[] [link
- boost_graph.reference_guide.algorithms.shortest_paths.johnson_all_pairs_shortest_paths
+[template johnson_all_pairs_shortest_paths[] [link
+ boost_graph.reference.algorithms.shortest_paths.johnson_all_pairs_shortest_paths
[^johnson_all_pairs_shortest_paths()]]]
[/ Connectivity /]
-[template boost_connected_components[] [link
- boost_graph.reference_guide.algorithms.connectivity.connected_components
+[template connected_components[] [link
+ boost_graph.reference.algorithms.connectivity.connected_components
[^connected_components()]]]
-[template boost_strong_connected_components[] [link
- boost_graph.reference_guide.algorithms.connectivity.strongly_connected_components
+[template strong_connected_components[] [link
+ boost_graph.reference.algorithms.connectivity.strongly_connected_components
[^strongly_connected_components]]]
[/ Subgraph/ ]
-[template boost_bron_kerbosch_visit_cliques[] [link
- boost_graph.reference_guide.algorithms.subgraph.bron_kerbosch_all_cliques
+[template bron_kerbosch_visit_cliques[] [link
+ boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques
[^bron_kerbosch_all_cliques()]]]
-[template boost_tiernan_find_cycles[] [link
- boost_graph.reference_guide.algorithms.subgraph.tiernan_all_cycles
+[template tiernan_find_cycles[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles
[^tiernan_all_cycles()]]]
[/ Measures /]
-[template boost_degree_centrality[] [link
- boost_graph.reference_guide.algorithms.graph_measures.degree_centrality
+[template degree_centrality[] [link
+ boost_graph.reference.algorithms.measures.degree_centrality.__degree_centrality__
[^degree_centrality()]]]
-[template boost_closeness_centrality[] [link
- boost_graph.reference_guide.algorithms.graph_measures.closeness_centrality
+[template all_degree_centralities[] [link
+ boost_graph.reference.algorithms.measures.degree_centrality.__all_degree_centralities___
+ [^all_degree_centralities()]]]
+[template closeness_centrality[] [link
+ boost_graph.reference.algorithms.measures.closeness_centrality.__closeness_centrality___
[^closeness_centrality()]]]
-[template boost_mean_geodesic[] [link
- boost_graph.reference_guide.algorithms.graph_measures.mean_geodesic
+[template all_closeness_centralities[] [link
+ boost_graph.reference.algorithms.measures.closeness_centrality.__all_closeness_centralities___
+ [^all_closeness_centralities()]]]
+[template mean_geodesic[] [link
+ boost_graph.reference.algorithms.measures.mean_geodesic.__mean_geodesic___
[^mean_geodesic()]]]
-[template boost_eccentricity[] [link
- boost_graph.reference_guide.algorithms.graph_measures.eccentricity
+[template all_mean_geodesics[] [link
+ boost_graph.reference.algorithms.measures.mean_geodesic.__all_mean_geodesics___
+ [^all_mean_geodesics()]]]
+[template small_world_distance[] [link
+ boost_graph.reference.algorithms.measures.mean_geodesic.__small_world_distance___
+ [^small_world_distance()]]]
+
+[template eccentricity[] [link
+ boost_graph.reference.algorithms.measures.eccentricity.__eccentricity___
[^eccentricity()]]]
-[template boost_graph_radius[] [link
- boost_graph.reference_guide.algorithms.graph_measures.eccentricity
+[template eccentricities[] [link
+ boost_graph.reference.algorithms.measures.eccentricity.__eccentricities___
+ [^eccentricities()]]]
+[template radius[] [link
+ boost_graph.reference.algorithms.measures.eccentricity.__radius___
[^radius()]]]
-[template boost_graph_diameter[] [link
- boost_graph.reference_guide.algorithms.graph_measures.eccentricity
+[template diameter[] [link
+ boost_graph.reference.algorithms.measures.eccentricity.__diameter___
[^diameter()]]]
-[template boost_exterior_vertex_property[] [link
- boost_graph
+[template exterior_vertex_property[] [link
+ graph
[^exterior_vertex_property]]]
-[template boost_exterior_edge_property[] [link
- boost_graph
+[template exterior_edge_property[] [link
+ graph
[^exterior_edge_property]]]
[/ Import lots of examples to build code templates]
-[import ../examples/social_network.hpp]
-[import ../examples/flow_network.hpp]
[import ../examples/degree_centrality.cpp]
[import ../examples/influence_prestige.cpp]
[import ../examples/closeness_centrality.cpp]
-[import ../examples/norm_closeness_centrality.cpp]
+[import ../examples/scaled_closeness_centrality.cpp]
[import ../examples/mean_geodesic.cpp]
+[import ../examples/inclusive_mean_geodesic.cpp]
[import ../examples/eccentricity.cpp]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -12,7 +12,7 @@
concern for the vertices, whereas in other contexts the edges are also important.
[h4 Refinement Of]
-[BoostGraph]
+[Graph]
[h4 Associated Types]
[table
@@ -28,7 +28,7 @@
[
An adjacency iterator for a vertex v provides access to the vertices adjacent to v.
As such, the value type of an adjacency iterator is the vertex descriptor type of its
- graph. An adjacency iterator must meet the requirements of [BoostMultiPassInputIterator].
+ graph. An adjacency iterator must meet the requirements of [MultiPassInputIterator].
]
]
]
@@ -51,7 +51,7 @@
The `adjacent_vertices(v,g)` function must return in constant time.
[h4 Design Rationale]
-The AdjacencyGraph concept is somewhat frivolous since [BoostIncidenceGraph] really covers the same
+The AdjacencyGraph concept is somewhat frivolous since [IncidenceGraph] really covers the same
functionality (and more). The AdjacencyGraph concept exists because there are situations when
`adjacent_vertices()` is more convenient to use than `out_edges()`. If you are constructing a graph
class and do not want to put in the extra work of creating an adjacency iterator, have no fear. There
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -12,7 +12,7 @@
would require this concept.
[h4 Refinement Of]
-[BoostGraph]
+[Graph]
[h4 Associated Types]
[table
@@ -43,8 +43,8 @@
The `edge(u,v,g)` function must return in constant time.
[h4 Notes]
-A number of graph classes (notably [boost_undirected_graph], [boost_directed_graph] and
-[boost_adjacency_list]) provide non-constant time implementations of this interface. Although
+A number of graph classes (notably [undirected_graph], [directed_graph] and
+[adjacency_list]) provide non-constant time implementations of this interface. Although
the function exists, none of these classes are documented as modeling this concept.
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,13 +6,13 @@
/]
[section Bellman Ford Visitor]
-This concept defines the visitor interface for [boost_bellman_ford_shortest_paths]. Users
+This concept defines the visitor interface for [bellman_ford_shortest_paths]. Users
can define a class with the Bellman Ford Visitor interface and pass and object of the
-class to [boost_bellman_ford_shortest_paths], thereby augmenting the actions taken during the
+class to [bellman_ford_shortest_paths], thereby augmenting the actions taken during the
graph search.
[h4 Refinement Of]
-[BoostVisitor]
+[Visitor]
[h4 Valid Expressions]
[table
@@ -29,7 +29,7 @@
[`vis.edge_relaxed(e,g)`]
[
If the relaxation predicate holds for this given edge then this method is invoked.
- See [boost_dijkstra_shortest_paths] for more information on relaxation.
+ See [dijkstra_shortest_paths] for more information on relaxation.
*Returns* `void`
]
@@ -38,7 +38,7 @@
[`vis.edge_not_relaxed(e,g)`]
[
If the relaxation predicate does not hold for this edge, then this method is invoked.
- See [boost_dijkstra_shortest_paths] for more information on relaxation.
+ See [dijkstra_shortest_paths] for more information on relaxation.
*Returns* `void`
]
@@ -65,6 +65,6 @@
]
[h4 Models]
-* [boost_bellman_ford_visitor]
+* [bellman_ford_visitor]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -8,10 +8,10 @@
[section Breadth-First Search Visitor]
This concept defines the visitor interface for [booost_breadth_first_search] algorithm. Users
can define a class with the BFS Visitor interface and pass and object of the class to
-[boost_breadth_first_search], thereby augmenting the actions taken during the graph search.
+[breadth_first_search], thereby augmenting the actions taken during the graph search.
[h4 Refinement Of]
-[BoostVisitor]
+[Visitor]
[h4 Valid Expressions]
[table
@@ -100,6 +100,6 @@
]
[h4 Models]
-* [boost_bfs_visitor]
+* [bfs_visitor]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -14,7 +14,7 @@
the vertex.
[heading Refinement Of]
-[BoostIncidenceGraph]
+[IncidenceGraph]
[h4 Associated Types]
[table
@@ -61,9 +61,9 @@
]
[h4 Models]
-* [boost_undirected_graph]
-* [boost_directed_graph]
-* [boost_adjacency_list] with the `Directed` template parameter as `bidirectionalS` or
+* [undirected_graph]
+* [directed_graph]
+* [adjacency_list] with the `Directed` template parameter as `bidirectionalS` or
`undirectedS`.
[h4 Complexity Guarantees]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -11,7 +11,7 @@
algorithms and are invoked when a clique is found within a graph.
[heading Refinement Of]
-[BoostVisitor]
+[Visitor]
[heading Expressions]
[table
@@ -25,7 +25,7 @@
connected subgraph is identified in the graph `g`.
*Requirements:* `g` is an object whose type `G` is a refinement of the
- [BoostGraph] concept.
+ [Graph] 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`
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-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -14,7 +14,7 @@
[table
[[Object] [Type]]
- [[G] [A type that is a model of a [BoostGraph] (or refinement thereof)]]
+ [[G] [A type that is a model of a [Graph] (or refinement thereof)]]
[[g] [An object of type G]]
[[u,v] [Objects of type `graph_traits<G>::vertex_descriptor`]]
[[e] [An object of type `graph_traits<G>::edge_descriptor`]]
@@ -26,7 +26,7 @@
[[p] [An object of type Property]]
[[Predicate] [A function that, given an argument, returns true or false]]
[[pred] [An object of type [SgiPredicate]]]
- [[V] [A type that is a model of a [BoostVisitor] (or refinement thereof)]]
+ [[V] [A type that is a model of a [Visitor] (or refinement thereof)]]
[[vis] [An object of type V]]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -11,7 +11,7 @@
algorithms and are invoked when a cycle is found within a graph.
[heading Refinement Of]
-[BoostVisitor]
+[Visitor]
[heading Valid Expressions]
[table
@@ -28,7 +28,7 @@
to form a cycle.
*Requirements:* `g` is an object whose type `G` is a model of the
- [BoostGraph] concept.
+ [Graph] concept.
*Requirements:* `vs` is an object whose type `VertexSet` is a model
of the [SgiContainer] concept. The `value_type` of `VS` must be the
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,16 +6,16 @@
/]
[section Degree Measure]
-The [BoostDegreeMeasure] concept defines requirements for function objects
+The [DegreeMeasure] concept defines requirements for function objects
that are used in computations on the degree of a vertex.
[heading Notation]
The following expressions are used within this document:
[table
[[Expression] [Description]]
- [[M] [A type modeling the [BoostDegreeMeasure] concept.]]
+ [[M] [A type modeling the [DegreeMeasure] concept.]]
[[m] [An object of type `M`.]]
- [[G] [A type modeling the [BoostGraph] concept.]]
+ [[G] [A type modeling the [Graph] concept.]]
[[g] [An object of type `G`.]]
[[v] [An object of type `graph_traits<G>::vertex_descriptor`.]]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,13 +6,13 @@
/]
[section Dijkstra Visitor]
-This concept defines the visitor interface for [boost_dijkstra_shortest_paths] and related
+This concept defines the visitor interface for [dijkstra_shortest_paths] and related
algorithms. The user can create a class that matches this interface, and then pass objects
-of the class into [boost_dijkstra_shortest_paths] to augment the actions taken during the
+of the class into [dijkstra_shortest_paths] to augment the actions taken during the
search.
[h4 Refinement Of]
-[BoostVisitor]
+[Visitor]
[h4 Valid Expressions]
[table
@@ -55,7 +55,7 @@
[`vis.edge_relaxed(e,g)`]
[
If the relaxation predicate holds for this given edge then this method is invoked.
- See [boost_dijkstra_shortest_paths] for more information on relaxation.
+ See [dijkstra_shortest_paths] for more information on relaxation.
*Returns* `void`
]
@@ -64,7 +64,7 @@
[`vis.edge_not_relaxed(e,g)`]
[
If the relaxation predicate does not hold for this edge, then this method is invoked.
- See [boost_dijkstra_shortest_paths] for more information on relaxation.
+ See [dijkstra_shortest_paths] for more information on relaxation.
*Returns* `void`
]
@@ -82,6 +82,6 @@
]
[h4 Models]
-* [boost_dijkstra_visitor]
+* [dijkstra_visitor]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,17 +6,17 @@
/]
[section Distance Measure]
-The [BoostDistanceMeasure] concept defines requirements for function objects
+The [DistanceMeasure] concept defines requirements for function objects
that are used in computations of distances.
[heading Notation]
The following expressions are used within this document:
[table
[[Expression] [Description]]
- [[M] [A type modeling the [BoostDistanceMeasure] concept.]]
+ [[M] [A type modeling the [DistanceMeasure] concept.]]
[[m] [An object of type `M`.]]
[[d] [An object of type `M::distance_type`.]]
- [[G] [A type modeling the [BoostGraph] concept.]]
+ [[G] [A type modeling the [Graph] concept.]]
[[g] [An object of type `G`.]]
]
@@ -33,7 +33,7 @@
required.
*Requirements:* The `distance_type` must be a model of the
- [BoostNumericValue] concept.
+ [NumericValue] concept.
]
]
[
@@ -43,7 +43,7 @@
The type being computed as the measure.
*Requirements:* The `result_type` must be a model of the
- [BoostNumericValue] concept.
+ [NumericValue] concept.
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,11 +6,11 @@
/]
[section Edge List Graph]
-The EdgeListGraph concept refines the [BoostGraph] concept, and adds the requirement
+The EdgeListGraph concept refines the [Graph] concept, and adds the requirement
for efficient access to all the edges in a graph.
[h4 Refinement Of]
-[BoostGraph]
+[Graph]
[h4 Associated Types]
[table
@@ -26,7 +26,7 @@
[
An edge iterator (obtained via edges(g)) provides access to all of the edges
in a graph. An edge iterator type must meet the requirements of
- [BoostMultiPassInputIterator]. The value type of the edge iterator must be the
+ [MultiPassInputIterator]. The value type of the edge iterator must be the
same as the edge descriptor of the graph.
]
]
@@ -76,17 +76,17 @@
]
[h4 Models]
-* [boost_undirected_graph]
-* [boost_directed_graph]
-* [boost_adjacency_list]
-* [boost_edge_list]
+* [undirected_graph]
+* [directed_graph]
+* [adjacency_list]
+* [edge_list]
[h4 Complexity Guarantees]
The `edges(g)`, `source(e,g)`, and `target(e,g)` functions must return in constant time.
[h4 Design Rationale]
One issue in the design of this concept is whether to include the refinement from the
-[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+[IncidenceGraph] and [AdjacencyGraph] concepts. The ability to traverse the vertices
of a graph is orthogonal to traversing out-edges, so it would make sense to have a edgeListGraph
concept that only includes edge traversal. However, such a concept would no longer really be a
graph, but would just be a set, and the STL already has concepts for dealing with such things.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -9,11 +9,11 @@
This concept defines the interface for single-event visitors. An EventVisitor has an
/apply/ member function (`operator()`) which is invoked within the graph algorithm
at the event-point specified by the `event_filter` typedef within the type modeling
-the EventVisitor concept. EventVisitors can be combined into an [BoostEventVistorList].
+the EventVisitor concept. EventVisitors can be combined into an [EventVistorList].
The following is the list of event tags that can be invoked in Boost.Graph algorithms.
Each tag corresponds to a member function of the visitor for an algorithm. For example,
-the [BoostBFSVisitor] of [boost_breadth_first_search] has a `cycle_edge()` member function.
+the [BFSVisitor] of [[breadth_first_search] has a `cycle_edge()` member function.
The corresponding tag is `on_cycle_edge`. The first argument in the event visitor's
`operator()` must be either an edge or vertex depending on the event tag.
@@ -55,7 +55,7 @@
[on_tree_edge]
[
For algorithms whose iterations of a vertex set implicitly define a
- tree (such as [boost_breadth_first_search] or [boost_depth_first_search]),
+ tree (such as [[breadth_first_search] or [[depth_first_search]),
this event tag corresponds to the identification of an edge that acts
as an edge in the search tree. The parameter type associated with this
event is `edge_descriptor`.
@@ -65,7 +65,7 @@
[on_cycle_edge]
[
For algorithms capable of detecting cycles in graphs such as
- [boost_depth_first_search], this event tag is associated with discovery
+ [[depth_first_search], this event tag is associated with discovery
of an edge that creates a cycle within the graph. The parameter type
associated with this event is `edge_descriptor`.
]
@@ -74,7 +74,7 @@
[on_forward_or_cross_edge]
[
Forward and cross edges refer to types of edges that can be found by
- different types of searches on graph (e.g., [boost_depth_first_search]).
+ different types of searches on graph (e.g., [[depth_first_search]).
This event tag corresponds to the identification of such an edge by
the algorithm. The parameter type associated with this event is
`edge_descriptor`.
@@ -84,8 +84,8 @@
[on_back_edge]
[
Back edges refer to types of edges that can be found by different types
- of searches on a graph (e.g., [boost_breadth_first_search] and
- [boost_depth_first_search]). This event tag corresponds to the identification
+ of searches on a graph (e.g., [[breadth_first_search] and
+ [[depth_first_search]). This event tag corresponds to the identification
of such an edge by the algorithm. The parameter type associated with this
event is `edge_descriptor`.
]
@@ -102,7 +102,7 @@
[on_edge_relaxed]
[
For algorithms implementing edge relaxation (e.g.,
- [boost_dijkstra_shortest_paths]), this event corresponds to the case
+ [[dijkstra_shortest_paths]), this event corresponds to the case
where an edge is relaxed. The parameter type associated with this event
is `edge_descriptor`.
]
@@ -111,7 +111,7 @@
[on_edge_not_relaxed]
[
For algorithms implementing edge relaxation (e.g.,
- [boost_dijkstra_shortest_paths]), this event corresponds to the case
+ [[dijkstra_shortest_paths]), this event corresponds to the case
where an edge is not relaxed. The parameter type associated with this
event is `edge_descriptor`.
]
@@ -120,7 +120,7 @@
[on_edge_minimized]
[
For algorithms implementing edge minimization (e.g.,
- [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+ [[bellman_ford_shortest_paths]), this event corresponds to the case
where an edge is minimized. The parameter type associated with this event
is `edge_descriptor`.
]
@@ -129,7 +129,7 @@
[on_edge_not_minimized]
[
For algorithms implementing edge minimization (e.g.,
- [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+ [[bellman_ford_shortest_paths]), this event corresponds to the case
where an edge is not minimized. The parameter type associated with this
event is `edge_descriptor`.
]
@@ -137,7 +137,7 @@
]
[h4 Refinement Of]
-[BoostVisitor]
+[Visitor]
[h4 Associated Types]
[table
@@ -166,10 +166,10 @@
]
[h4 Models]
-* [boost_predecessor_recorder]
-* [boost_distance_recorder]
-* [boost_time_stamper]
-* [boost_property_writer]
-* [boost_null_visitor]
+* [[predecessor_recorder]
+* [[distance_recorder]
+* [[time_stamper]
+* [[property_writer]
+* [[null_visitor]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,18 +6,18 @@
/]
[section Event Visitor List]
-An EventVisitorList is either an [BoostEventVisitor], or a list of [BoostEventVisitor]
+An EventVisitorList is either an [EventVisitor], or a list of [EventVisitor]
combined using `std::pair`. Each graph algorithm defines visitor adaptors that convert an
EventVisitorList into the particular kind of visitor needed by the algorithm. In the
following example we will show how to combine event visitors into a list using `std::pair`
and how to use an algorithm's visitor adaptor class.
Suppose we would like to print out the parenthesis structure of the discover/finish times
-of vertices in a depth-first search. We can use the Boost.Graph algorithm [boost_depth_first_search]
+of vertices in a depth-first search. We can use the Boost.Graph algorithm [depth_first_search]
and two event visitors to accomplish this. The complete source code for the following example
is in `examples/dfs_parenthesis.cpp`. First we define the two event visitors. We use
`on_discover_vertex` and `on_finish_vertex` as the event points, selected from the list of
-event points specified in [BoostDFSVisitor].
+event points specified in [DFSVisitor].
struct open_paren : public base_visitor<open_paren>
{
@@ -47,14 +47,14 @@
make_pair(open_paren(), close_paren());
-Next we want to pass this list into [boost_depth_first_search], but it is
-expecting a [BoostDFSVisitor], not a [EventVisitorList]. We therefore use the [boost_dfs_visitor]
-adaptor which turns an [BoostEventVisitor] list into a [BoostDFSVisitor]. Like all of the visitor
-adaptors, [dfs_visitor] has a creation function called [boost_make_dfs_visitor].
+Next we want to pass this list into [[depth_first_search], but it is
+expecting a [DFSVisitor], not a [EventVisitorList]. We therefore use the [[dfs_visitor]
+adaptor which turns an [EventVisitor] list into a [DFSVisitor]. Like all of the visitor
+adaptors, [dfs_visitor] has a creation function called [[make_dfs_visitor].
make_dfs_visitor((open_paren(), close_paren()));
-Now we can pass the resulting visitor object into [boost_depth_first_search] as follows.
+Now we can pass the resulting visitor object into [[depth_first_search] as follows.
depth_first_search(
G,
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -35,42 +35,42 @@
[table
[[Expression] [Return Type or Description]]
- [[[*[BoostGraph]]]]
+ [[[*[Graph]]]]
[[`graph_traits<G>::vertex_descriptor`] [The type for vertex representative objects.]]
[[`graph_traits<G>::edge_descriptor`] [The type for edge representative objects.]]
[[`graph_traits<G>::directed_category`] [Graph is directed or undirected?]]
[[`graph_traits<G>::edge_parallel_category`] [Graph allows parallel edges?]]
[[`graph_traits<G>::traversal_category`] [The ways in which the vertices and edges can be traversed.]]
- [[[*[BoostIncidenceGraph]]]]
+ [[[*[IncidenceGraph]]]]
[[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
[[`graph_traits<G>::out_edge_iterator`] [Type for iterating over out edges.]]
[[`out_edges(v,g)`] [`std::pair<out_edge_iterator, out_edge_iterator>`]]
[[`out_degree(v,g)`] [`degree_size_type`]]
[[`source(e,g)`] [`vertex_descriptor`]]
[[`target(e,g)`] [`vertex_descriptor`]]
- [[[*[BoostBidirectionalGraph]]]]
+ [[[*[BidirectionalGraph]]]]
[[`graph_traits<G>::in_edge_iterator`] [Type for iterating over in edges.]]
[[`in_edges(v,g)`] [`std::pair<in_edge_iterator,in_edge_iterator>`]]
[[`in_degree(v,g)`] [`degree_size_type`]]
[[`degree(v,g)`] [`degree_size_type`]]
- [[[*[BoostAdjacencyGraph]]]]
+ [[[*[AdjacencyGraph]]]]
[[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
[[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
- [[[*[BoostVertexListGraph]]]]
+ [[[*[VertexListGraph]]]]
[[`graph_traits<G>::vertex_iterator`] [Type for iterating over vertices.]]
[[`graph_traits<G>::vertices_size_type`] [Unsigned integer type for the number of vertices.]]
[[`vertices(g)`] [`std::pair<vertex_iterator,vertex_iterator>`]]
[[`num_vertices(g)`] [`vertices_size_type`]]
- [[[*[BoostEdgeListGraph]]]]
+ [[[*[EdgeListGraph]]]]
[[`graph_traits<G>::edge_iterator`] [Type for iterating over edges.]]
[[`graph_traits<G>::edges_size_type`] [Unsigned integer type for the number of edges.]]
[[`edges(g)`] [`std::pair<edge_iterator, edge_iterator>`]]
[[`num_edges(g)`] [`edges_size_type`]]
[[`source(e,g)`] [`vertex_descriptor`]]
[[`target(e,g)`] [`vertex_descriptor`]]
- [[[*[BoostAdjacencyMatrix]]]]
+ [[[*[AdjacencyMatrix]]]]
[[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
- [[[*[BoostMutableGraph]]]]
+ [[[*[MutableGraph]]]]
[[`add_vertex(g)`] [`vertex_descriptor`]]
[[`clear_vertex(v,g)`] [`void`]]
[[`clear_out_edges(v,g)`] [`void`]]
@@ -82,13 +82,13 @@
[[`remove_edge_if(pred,g)`] [`void`]]
[[`remove_out_edge_if(v,pred,g)`] [`void`]]
[[`remove_in_edge_if(v,pred,g)`] [`void`]]
- [[[*[BoostPropertyGraph]]]]
+ [[[*[PropertyGraph]]]]
[[`property_map<G,Property>::type`] [Type for a mutable property map.]]
[[`property_map<G,Property>::const_type`] [Type for a non-mutable property map.]]
[[`get(p,g)`] [Function to get a property map.]]
[[`get(p,g,x)`] [Get the property value for vertex or edge `x`]]
[[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
- [[[*[BoostMutablePropertyGraph]]]]
+ [[[*[MutablePropertyGraph]]]]
[[`add_vertex(vp,g)`] [`vertex_descriptor`]]
[[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
]
@@ -218,7 +218,7 @@
without any additional work.
There are certain sets of graph types that do not allow the addition of parallel edges.
-Specifically, if the EdgeList and OutEdgeList of an [boost_adjacency_list] models an
+Specifically, if the EdgeList and OutEdgeList of an [adjacency_list] models an
associative container, then the graph cannont be a multigraph.
*Document this a little better*
@@ -226,7 +226,7 @@
[h3 Indexed Graphs]
Although not explicitly documented (yet), there's a concept of a Vertex-Indexed graph
that has some valid expressions related specifically to operations on vertex index
-property of the graph. The [boost_undirected_graph] class has some addiitonal methods
+property of the graph. The [undirected_graph] class has some addiitonal methods
that can also be ported.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -1,4 +1,4 @@
-[/
+b[/
/ Copyright (c) 2007 Andrew Sutton
/
/ Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -9,7 +9,7 @@
A MutableGraph can be changed via the addition or removal of edges and vertices.
[h4 Refinement Of]
-[BoostGraph]
+[Graph]
[h4 Valid Expressions]
[table
@@ -123,7 +123,7 @@
[`remove_edge(ei,g)`]
[
Remove the edge pointed to by the edge iterator `ei` from the graph. This expression is only required
- when `g` also models [BoostIncidenceGraph].
+ when `g` also models [IncidenceGraph].
*Returns* `void`
@@ -167,8 +167,8 @@
* Edge removal is guaranteed to be /O(E)/.
[h4 Models]
-* [boost_undirected_graph]
-* [boost_directed_graph]
-* [boost_adjacency_list]
+* [undirected_graph]
+* [directed_graph]
+* [adjacency_list]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,7 +6,7 @@
/]
[section Numeric Value]
-The [BoostNumericValue] concept describes requirements for a type to behave
+The [NumericValue] concept describes requirements for a type to behave
as if it were numeric. This concept is generally used by algorithms that
typically operate on numeric types, but can be specialized to operate on
user-defined numerics or discrete types that emulate numerics.
@@ -30,7 +30,7 @@
The following expressions are used within this document:
[table
[[Expression] [Description]]
- [[N] [A type modeling the [BoostNumericValue] concept.]]
+ [[N] [A type modeling the [NumericValue] concept.]]
]
[heading Associated Types]
@@ -42,7 +42,7 @@
[
The underlying type of the numeric value.
- *Requirements:* `N` is a [BoostNumericValue], and the `value_type`
+ *Requirements:* `N` is a [NumericValue], and the `value_type`
and `N` must be the same type.
]
]
@@ -74,7 +74,4 @@
]
]
-[heading Models]
-[boost_numeric_value]
-
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -13,7 +13,7 @@
indicated property.
[h4 Refinement Of]
-[BoostGraph]
+[Graph]
[h4 Associated Types]
[table
@@ -22,7 +22,7 @@
[`property_map<G, Property>::type`]
[
The type of the property map for the property specified by `Property`. This type must
- be a model of [BoostReadWritePropertyMap] with a key type the same as the graph's
+ be a model of [ReadWritePropertyMap] with a key type the same as the graph's
`vertex_descriptor` or `edge_descriptor` types.
]
]
@@ -30,7 +30,7 @@
[`property_map<G, Property>::const_type`]
[
The type of the property map for the property specified by `Property`. This type must
- be a model of [BoostReadablePropertyMap] with a key type the same as the graph\'s
+ be a model of [ReadablePropertyMap] with a key type the same as the graph\'s
`vertex_descriptor` or `edge_descriptor` types.
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,11 +6,11 @@
/]
[section Vertex List Graph]
-The VertexListGraph concept refines the [BoostGraph] concept, and adds the requirement
+The VertexListGraph concept refines the [Graph] concept, and adds the requirement
for efficient traversal of all the vertices in a graph.
[h4 Refinement Of]
-[BoostGraph]
+[Graph]
[h4 Associated Types]
[table
@@ -25,7 +25,7 @@
[`graph_traits<G>::vertex_iterator`]
[
A vertex iterator (obtained via vertices(g)) provides access to all of the vertices in
- a graph. A vertex iterator type must meet the requirements of [BoostMultiPassInputIterator].
+ a graph. A vertex iterator type must meet the requirements of [MultiPassInputIterator].
The value type of the vertex iterator must be the vertex descriptor of the graph.
]
]
@@ -63,7 +63,7 @@
[h4 Design Rationale]
One issue in the design of this concept is whether to include the refinement from the
-[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+[IncidenceGraph] and [AdjacencyGraph] concepts. The ability to traverse the vertices
of a graph is orthogonal to traversing out-edges, so it would make sense to have a VertexListGraph
concept that only includes vertex traversal. However, such a concept would no longer really be a
graph, but would just be a set, and the STL already has concepts for dealing with such things.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/images/reference/Makefile
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/images/reference/Makefile (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/reference/Makefile 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -5,7 +5,7 @@
connected_components_before.dot \
connected_components_after.dot \
geodesic.dot \
- information_network.dot
+ info_network.dot
circo_src = \
distribution_undirected.circo \
distribution_directed.circo
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -69,9 +69,9 @@
The graph for which the betweenness centrality of vertices or edges
is being computed.
- *Requirements:* The `Graph` type must be a model of the [BoostVertexListGraph]
- and [BoostIncidenceGraph] concepts. If the `EdgeCentralityMap` parameter
- is present, this parameter type must also model the [BoostEdgeListGraph].
+ *Requirements:* The `Graph` type must be a model of the [VertexListGraph]
+ and [IncidenceGraph] concepts. If the `EdgeCentralityMap` parameter
+ is present, this parameter type must also model the [EdgeListGraph].
]
]
[
@@ -90,10 +90,10 @@
shortest path between a vertex `u` and `v`. The vertex `u` is the
vertex for which the distance map was initially computed.
- *Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance map must be the same as the `vertex_descriptor`
of the `Graph` parameter. The `value_type` is required to be a model of
- [BoostNumericValue].
+ [NumericValue].
]
]
[
@@ -103,11 +103,11 @@
of the shortest path between the two vertices. Note that the
distance between a vertex and itself should be 0 (i.e., `dm[u][u] == 0`).
- *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMatrixMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
- of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
+ of the `Graph` parameter. The `value_type` must be a [ReadWritePropertyMap]
whose `key_type` is also the `vertex_descriptor` of the `Graph` and
- whose `value_type` is a model of [BoostNumericValue].
+ whose `value_type` is a model of [NumericValue].
]
]
[
@@ -116,10 +116,10 @@
The cm parameter stores the output of the computed closeness (or
distance) for each vertex in `g`.
- *Requirements:* The type of `close` must be model the [BoostWritablePropertyMap]
+ *Requirements:* The type of `close` must be model the [WritablePropertyMap]
concepts. The `key_type` of the property map must be the same as the
`vertex_descriptor` of the `Graph`, and the `value_type` must be a model
- of [BoostNumericValue].
+ of [NumericValue].
]
]
[
@@ -128,10 +128,10 @@
The 'measure' parameter is an instance of a closeness measure that
performs the final operation (the reciprocal) for this computation.
- *Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
+ *Requirements:* The `Measure` type must be a model of the [DistanceMeasure]
concept. The `distance_type` must be the same type as the `value_type`
of the `DistanceMap` or `DistanceMatrixMap`. The `result_type` of the
- `Measure` must model the [BoostNumericValue] concept.
+ `Measure` must model the [NumericValue] concept.
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -76,8 +76,8 @@
[
[in] [`Graph& g`]
[
- A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
- and [BoostIncidenceGraph].
+ A directed or undirected graph. The graph type must be a model of [VertexListGraph]
+ and [IncidenceGraph].
]
]
[
@@ -96,7 +96,7 @@
[in] [`visitor(Visitor vis)`]
[
A visitor object that is inovked inside the algorithm at event points specified by the
- [BoostBFSVisitor]. The `vis` object must be model the [BoostBFSVisitor] concept.
+ [BFSVisitor]. The `vis` object must be model the [BFSVisitor] concept.
*Default* `bfs_visitor<null_visitor>`.
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -37,11 +37,11 @@
*Preconditions:* The indices of vertices in the graph must be
in the range \[0, `num_vertices(g)`).
- *Requirements:* The `Graph` type must be a model of the [BoostAdjacencyMatrix],
- [BoostIncidenceGraph] concept and the [BoostVertexIndexGraph]
+ *Requirements:* The `Graph` type must be a model of the [AdjacencyMatrix],
+ [IncidenceGraph] concept and the [VertexIndexGraph]
concepts[footnote Any `Graph` typen that implements the `edge()`
function will satisfy the expression requirements for the
- [BoostAdjacencyMatrix], but may incur additional overhead due non-constant
+ [AdjacencyMatrix], but may incur additional overhead due non-constant
implementations.].
]
]
@@ -51,7 +51,7 @@
The visitor object to the algorithm.
*Requirements:* This `Visitor` class must model the
- [BoostCliqueVisitor] class.
+ [CliqueVisitor] class.
]
]
]
@@ -65,10 +65,10 @@
The original publication, however, approximates the runtime of the algorithm as
being proportional to ['O(3.14[super n])].
-Graphs that do not meet the constant-time requirements of the [BoostAdjacencyMatrix]
+Graphs that do not meet the constant-time requirements of the [AdjacencyMatrix]
concept will incur additional runtime costs during execution (usually by a small linear
-factor). Examples of such graphs include the [boost_undirected_graph],
-[boost_directed_graph], and the [boost_adjacency_list] classes.
+factor). Examples of such graphs include the [undirected_graph],
+[directed_graph], and the [adjacency_list] classes.
[h5 Examples]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,45 +6,32 @@
/]
[section Closeness Centrality]
+[template ex_closeness_centrality[] [link
+ boost_graph.reference.algorithms.measures.closeness_centrality.examples.closeness_centrality
+ Closeness Centrality Example]]
+[template ex_scaled_closeness[] [link
+ boost_graph.reference.algorithms.measures.closeness_centrality.examples.scaled_closeness_centrality
+ Scaled Closeness Centrality Example]]
- template <typename Graph, typename DistanceMatrixMap, typename ClosenessMap>
- void closeness_centrality(const Graph& g,
- DistanceMatrixMap dm,
- ClosenessMap cm)
-
- template <typename Graph, typename DistanceMatrixMap, typename ClosenessMap, typename Measure>
- void closeness_centrality(const Graph& g,
- DistanceMatrixMap dm,
- ClosenessMap cm,
- Measure m)
-
-
- template <typename Graph, typename DistanceMap>
- float vertex_closeness_centrality(const Graph& g, DistanceMap dm)
-
- template <typename ResultType, typename Graph, typename DistanceMap>
- ResultType vertex_closeness_centrality(const Graph& g, DistanceMap dm)
-
- template <typename Graph, typename DistanceMap, typename Measure>
- typename Measure::result_type
- vertex_closeness_centrality(const Graph& g, DistanceMap dm, Measure m)
-
+[heading Overview]
The /closeness centrality/ measure is commonly used in network analysis to identify
vertices (also called actors) that are "close" to all others. To phrase differently,
-actors that are "closer" to all others have a greater reach, making them more
+actors that are closer to all others have a greater reach, making them more
influential in the network. The closeness measure is defined as the inverse of the
-sum of all geodesic distances (lengths of shortest path) from one vertex to all
-others (excluding itself). Closeness is computed as:
+sum of all geodesic distances (lengths of shortest paths) from one vertex to all
+others (excluding itself) in the graph. Closeness is computed as:
[$images/eq/closeness.png]
-Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/. Note that
-the distance of /(u,u)/ is neither
+Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/.
+
Note that if any vertex in the graph is unreachable from any other, then distance
between those two unonnected vertices is infinite. This imlplies that the closeness
of that vertex is zero. If an undirected graph has unconnected components, then
all vertices will have a closeness of zero. This is not necessarily true for
-directed graphs.
+unconnected directed graphs since some vertex might reach all others, but may
+not itself be reachable by any others. An example of such a graph is a tree whose
+direted edges from from the root toward the leaves.
Consider the following social network represented by an undirected graph in
Figure 1.
@@ -57,7 +44,9 @@
Computing the closeness for each person in the graph, we find that Frank is the
most central person in the network, with a closeness centrality of approximiately
0.091 (1/11). We also find that Jill, Mary, and Laurie are the least central
-people in the network (with closeness centralities of .056 or 1/18).
+people in the network (with closeness centralities of .056 or 1/18). See the
+[ex_closeness_centrality] for details on computing the closeness centralites of
+undirected graphs.
The same measure can also be applied to directed graphs, but has dubious meaning
if the graph is not /strongly connected/. Consider the communication networks
@@ -80,28 +69,33 @@
This is to say that distance is defined and computed before closeness centrality
can be computed.
-This module defines a flexible framework for computing the closeness centrality
-of vertices in a graph for previously computed geodesics by providing two generic
-functions. The first function, `closeness_centrality()` computes the closeness of
-each vertex in a graph given a matrix containing the distances between vertices.
-This matrix can be computed as the output of an "all pairs shortest path" algorithm
-(e.g, [boost_floyd_warshall_all_pairs_shortest_paths] or [boost_johnson_all_pairs_shortest_paths])
-or as the result of a [boost_breadth_first_search] (if the graph is unweighted).
-
-The second function, `vertex_closeness_centrality()` can be used to compute the
-closeness of a single vertex. This function requires a distance map that contains
-the distance from one vertex (the source) to all others in the graph. This
-distance map can be computed as the result of a "shortest paths" algorithm (e.g.,
-[boost_dijkstra_shortest_paths], [boost_bellman_ford_shortest_paths], or
-[boost_dag_shortest_paths]), or recording distances from a [boost_breadth_first_search].
-
This framework also allows for a specialization of the measure through the use
of a function object. This measure defaults to the reciprocal in the equation
above, but can be easily redefined to perform alternative computations or, in
the case of non-trivial types, re-define the notion of reciprocal.
-[heading Where Defined]
-`boost/graph/closeness_centrality.hpp`
+See the [ex_scaled_closeness] for an example of how to overload the
+default measures used to compute closeness centrality.
+
+[section [^closeness_centrality()]]
+ #include <boost/graph/closeness_centrality.hpp>
+
+ template <typename Graph, typename DistanceMap>
+ float closeness_centrality(const Graph& g, DistanceMap dm)
+
+ template <typename ResultType, typename Graph, typename DistanceMap>
+ ResultType closeness_centrality(const Graph& g, DistanceMap dm)
+
+ template <typename Graph, typename DistanceMap, typename Measure>
+ typename Measure::result_type
+ closeness_centrality(const Graph& g, DistanceMap dm, Measure m)
+
+The `vertex_closeness_centrality()` function can be used to compute the closeness
+centrality of a single vertex. This function requires a distance map that contains
+the distance from one vertex (the source) to all others in the graph. This
+distance map can be computed as the result of a "shortest paths" algorithm (e.g.,
+[dijkstra_shortest_paths], [bellman_ford_shortest_paths], or [dag_shortest_paths]),
+or recording distances from a [breadth_first_search].
[heading Parameters]
[table
@@ -114,7 +108,7 @@
given, the return type is `float`.
*Requirements:* The return type is required to model the
- [BoostNumericValue] concept.
+ [NumericValue] concept.
]
]
[
@@ -123,7 +117,7 @@
The graph for which vertex measures are being comptued.
*Requirements:* The `Graph` type must be a model of the
- [BoostVertexListGraph] concept.
+ [VertexListGraph] concept.
]
]
[
@@ -133,10 +127,64 @@
shortest path between a vertex `u` and `v`. The vertex `u` is the
vertex for which the distance map was initially computed.
- *Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance map must be the same as the `vertex_descriptor`
of the `Graph` parameter. The `value_type` is required to be a model of
- [BoostNumericValue].
+ [NumericValue].
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The 'measure' parameter is an instance of a closeness measure that
+ performs the final operation (the reciprocal) for this computation.
+
+ *Requirements:* The `Measure` type must be a model of the [DistanceMeasure]
+ concept. The `distance_type` must be the same type as the `value_type`
+ of the `DistanceMap` or `DistanceMatrixMap`. The `result_type` of the
+ `Measure` must model the [NumericValue] concept.
+ ]
+ ]
+]
+
+[heading Return]
+The `closeness_centrality()` function returns the closeness of a vertex.
+If the source vertex is disconnected from any vertices in the graph, this value is 0.
+
+[heading Complexity]
+The `closeness_centrality()` function returns in ['O(n*O(M))]. This is linear by
+default where /n/ is the number of vertices is in the graph and /O(M)/ is the
+omplexity of the measure. If no measure is given, this function returns in linear
+time.
+[endsect]
+
+[section [^all_closeness_centralities()]]
+ #include <boost/graph/closeness_centrality.hpp>
+
+ template <typename Graph, typename DistanceMatrixMap, typename ClosenessMap>
+ void all_closeness_centralities(const Graph& g, DistanceMatrixMap dm, ClosenessMap cm)
+
+ template <typename Graph, typename DistanceMatrixMap, typename ClosenessMap, typename Measure>
+ void all_closeness_centralities(const Graph& g, DistanceMatrixMap dm, ClosenessMap cm, Measure m)
+
+This module defines a flexible framework for computing the closeness centrality
+of vertices in a graph for previously computed geodesics by providing two generic
+functions. The first function, `closeness_centrality()` computes the closeness of
+each vertex in a graph given a matrix containing the distances between vertices.
+This matrix can be computed as the output of an "all pairs shortest path" algorithm
+(e.g, [floyd_warshall_all_pairs_shortest_paths] or [johnson_all_pairs_shortest_paths])
+or as the result of a [breadth_first_search] (if the graph is unweighted).
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which closeness centrality values are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concept.
]
]
[
@@ -146,11 +194,11 @@
of the shortest path between the two vertices. Note that the
distance between a vertex and itself should be 0 (i.e., `dm[u][u] == 0`).
- *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMatrixMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
- of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
+ of the `Graph` parameter. The `value_type` must be a [ReadWritePropertyMap]
whose `key_type` is also the `vertex_descriptor` of the `Graph` and
- whose `value_type` is a model of [BoostNumericValue].
+ whose `value_type` is a model of [NumericValue].
]
]
[
@@ -159,10 +207,10 @@
The cm parameter stores the output of the computed closeness (or
distance) for each vertex in `g`.
- *Requirements:* The type of `close` must be model the [BoostWritablePropertyMap]
+ *Requirements:* The type of `close` must be model the [WritablePropertyMap]
concepts. The `key_type` of the property map must be the same as the
`vertex_descriptor` of the `Graph`, and the `value_type` must be a model
- of [BoostNumericValue].
+ of [NumericValue].
]
]
[
@@ -171,149 +219,84 @@
The 'measure' parameter is an instance of a closeness measure that
performs the final operation (the reciprocal) for this computation.
- *Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
+ *Requirements:* The `Measure` type must be a model of the [DistanceMeasure]
concept. The `distance_type` must be the same type as the `value_type`
of the `DistanceMap` or `DistanceMatrixMap`. The `result_type` of the
- `Measure` must model the [BoostNumericValue] concept.
+ `Measure` must model the [NumericValue] concept.
]
]
]
-[heading Return]
-The `vertex_closeness_centrality()` function returns the closeness of a vertex.
-If the source vertex is disconnected from any vertices in the graph, this value is 0.
-
[heading Complexity]
-The `closenesss_centrality()` function returns in ['O(n[super 2]*O(M))] where /n/
-is the number of vertices in the graph and /M/ is the complexity of the given distance
-measure. This is ['O(n[super 2])] by default
-
-The `vertex_closeness_centrality()` function returns in ['O(n*O(M))]. This is
-linear by default.
+The `all_closenesss_centralities()` function returns in ['O(n[super 2]*O(M))] where /n/
+is the number of vertices in the graph and /O(M)/ is the complexity of the distance
+measure. If no distance measure is given, this functions returns in ['O(n[super 2])]
+time.
+[endsect]
-[heading Example (Closeness Centrality)]
+[section Examples]
+[heading Closeness Centrality]
This example computes the closeness centrality for all vertices (people) a social
network such as the one pictured in Figure 1. The program also sorts the vertices by
their corresponding closeness in descending order. This example includes the
following files:
* [^examples/closeness_centrality.hpp]
-* [^examples/social_network.hpp]
* [^examples/helper.hpp]
-First, we define the graph and its associated types.
-[social_network_types]
-Here, we use the `Actor` to store an actor name with each vertex. We also need to
-define a number of related property types to support property maps for the algorithms
-called in the program.
-
-Since this program will call [boost_floyd_warshall_all_pairs_shortest_paths] to
-compute distances between vertices, we need a matrix to store the distances.
-[distance_matrix_types]
-
-We also need a property map that assigns weights to each edge. Since our graph is
-unweighted, we can use the [boost_constant_property_map] to return a constant value
-for each edge. [constant_weight_map_types]
-
-We also need an output property map to store the closeness centrality for each
-vertex.
-[closeness_map_types]
-
-In the main program, we instantiate the graph and an extra `std::map` that we
-use during graph construction.
-[setup_social_network]
-
-The graph is read from standard input. This process uses the `add_named_vertex()`
-function, which is not part of the Boost.Graph library but defined in the file
-`examples/helper.hpp`.
-[build_social_network]
-
-The next step is to compute the distance. This is done using the
-[boost_floyd_warshall_all_pairs_shortest_paths] function. This could also be done
-using [boost_johnson_all_pairs_shortest_paths]. This is done by first constructing
-a matrix to hold the distance values, and a property map over the matrix. Additionally,
-we use a [boost_constant_property_map] to return the value `1` for all edge weights.
-Both the distance matrix and edge-weight maps are used as inputs to the distance
-algorithm.
-[compute_constant_distances]
-
-After computing the distance, we can use the resulting distance matrix to compute
-the property maps for each vertex. This is done by constructing a container for
-the closeness values and a property map accessor for it. The previously computed
-distance map and closeness map are passed as inputs to the computation.
-[compute_closeness_centrality]
-
-In the next step, we sort the vertices of the graph into the given vector. For
-this sort, we use the values in the property map as the sort keys. The resulting
-vector will contain the vertices of the graph in descending order of closeness.
-The `sort_vertices()` function is given in the `helper.hpp` file.
-[closeness_sort_vertices]
-
-Finally, we iterate over the sorted vector of vertices and print them to standard
-output.
-[print_sorted_closeness]
+[closeness_centrality_example]
If this program is given the `social_network.graph` file as input, the output
will be:
[pre
-Frank 0.0909091
-Scott 0.0833333
-Josh 0.0625
-Bill 0.0588235
-Anne 0.0588235
-Howard 0.0588235
-Jill 0.0555556
-Mary 0.0555556
-Laurie 0.0555556
+Scott 0.0833333
+Jill 0.0588235
+Mary 0.0625
+Bill 0.0588235
+Josh 0.0625
+Frank 0.0909091
+Laurie 0.0666667
+Anne 0.0588235
+Howard 0.0588235
]
Note that this program can be easily modified to work on directed graphs. In the
file `social_network.hpp`, simply replace `typedef undirected_graph<Actor> ...` to
`typedef directed_graph<Actor> ...`.
-[heading Example (Normalized Closeness)]
+[heading Scaled Closeness Centrality]
In some literature, closeness is defined as the number of vertices divided by the
sum of distances, or more formally.
-[$images/eq/norm_closeness.png]
+[$images/eq/scaled_closeness.png]
Where /n/ is the number of vertices in the graph. While this example demonstrates
-the implementation of a [BoostDistanceMeasure], the resulting value can be also
+the implementation of a [DistanceMeasure], the resulting value can be also
obtained by multiplying the default result by the number of vertices in the graph.
This example uses the following files:
-* [^examples/norm_closeness_centrality.hpp]
-* [^examples/social_network.hpp]
+* [^examples/scaled_closeness_centrality.hpp]
* [^examples/helper.hpp]
-Defining the a distance measure that models the [BoostDistanceMeasure] type is
-fairly simple, and is similar to providing custom function objects for algorithms
-in the Standard Library. Our custom measure is defined as:
-[normalized_closeness_measure]
-
-Using this measure requires that we instantiate it. Since we did not provide
-any convenience functions for instantiating the type, it must be explicitly
-declared before its use. The distance and result types are given as `int` and
-`float` respectively. Once constructed, it is simply passed to the computation
-as an argument.
-[compute_normalized_closeness]
+[scaled_closeness_centrality_example]
If given the same social network as input, the output of this program will be:
[pre
-Frank 0.818182
-Scott 0.75
-Josh 0.5625
-Bill 0.529412
-Anne 0.529412
-Howard 0.529412
-Jill 0.5
-Mary 0.5
-Laurie 0.5
+Scott 0.75
+Jill 0.529412
+Mary 0.5625
+Bill 0.529412
+Josh 0.5625
+Frank 0.818182
+Laurie 0.6
+Anne 0.529412
+Howard 0.529412
]
It is relatively easy to verify that each of these values is nine times the values
given in the previous example.
+[endsect]
-[endsect]
\ No newline at end of file
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,21 +6,17 @@
/]
[section Degree Centrality]
+[template ex_degree_centrality[] [link
+ boost_graph.reference.algorithms.measures.degree_centrality.examples.degree_centrality
+ Degree Centrality Example]]
+[template ex_influence_prestige[] [link
+ boost_graph.reference.algorithms.measures.degree_centrality.examples.influence_and_prestige
+ Influence and Prestige Example]]
+[template degree_centrality_measures[] [link
+ boost_graph.reference.algorithms.measures.degree_centrality.measures
+ Measures Section]]
- template <typename Graph, typename CentralityMap>
- void degree_centrality(const Graph& g, CentralityMap cent)
-
- template <typename Graph, typename CentralityMap, typename Measure>
- void degree_centrality(const Graph& g, CentralityMap cent, Measure measure)
-
- template <typename Graph, typename Vertex>
- typename graph_traits<Graph>::degree_size_type
- vertex_degree_centrality(const Graph& g, Vertex v)
-
- template <typename Graph, typename Vertex, typename Measure>
- typename Measure::degree_type
- vertex_degree_centrality(const Graph& g, Vertex v, Measure measure)
-
+[heading Overview]
The /degree centrality/ measure is used in social network analysis to help
determine which vertices (or more specifically actors) are the most central
or important to a network. Degree centrality of a vertex is computed over the number
@@ -39,11 +35,16 @@
This graph depicts a set of friends and their relationships (friendship, dating, etc.)
The degree centrality of each person in this graph is their number of friends.
Here, Frank has the highest degree centrality with five friends, whereas Laurie,
-Jill, Bill, Anne, and Howard are the least central with two friends apiece.
+Jill, Bill, Anne, and Howard are the least central with two friends apiece. See
+the [ex_degree_centrality] for details on computing the degree centrality of
+undirected graphs.
For directed graphs, there are related two interpretations of degree centrality.
When degree centrality is measured over the out-degree of a vertex, it is called
/influence/. When the in-degree is measured, the measure is called /prestige/.
+See the [degree_centrality_measures] for information types and functions related
+to the computation of influence and prestige.
+
Consider the information network represented by the directed graph in Figure 2.
[figure
@@ -56,33 +57,24 @@
three outgoing links while wikipedia is the least influential. The most prestigous
(in-degree centrality) is wikipedia with five incoming references. The least
prestigous websites are myspace, blogger, and blogspot each of which have no
-incoming links.
+incoming links. See the [ex_influence_prestige] for details on computing the
+influence and prestige of directed graphs.
-This module provides two generic functions for measuring degree centrality.
-The first function, `degree_centrality()` computes this measure for each vertex
-in the graph, assigning the values to an output property map.
-
-The second funtion, `vertex_degree_centrality()` computes this measure for
-a single vertex, returning the value to the caller.
-
-These functions can be specialized throught the use of different /measure/
-functors. These funtors are called to compute the degree centraltiy of a vertex
-within the computational framework. This module provides the two default measures
-for /influence/ and /prestige/ and functions to help instantiate them. Custom
-measures can also be easily implemented and used.
+[section [^degree_centrality()]]
+ #include <boost/graph/degree_centrality.hpp>
- template <typename Graph> struct influence_measure;
- template <typename Graph> influence_measure<Graph> measure_influence(const Graph&);
-
- template <typename Graph> struct prestige_measure;
- template <typename Graph> prestige_measure<Graph> measure_prestige(const Graph&);
+ template <typename Graph, typename Vertex>
+ typename graph_traits<Graph>::degree_size_type
+ degree_centrality(const Graph& g, Vertex v);
-The `influence_measure` returns the out-degre of a vertex and provides the
-default computation for degree centrality of both directed and undirected
-graphs. The `prestige_measure` returns the in-degree of a vertex.
+ template <typename Graph, typename Vertex, typename Measure>
+ typename Measure::degree_type
+ degree_centrality(const Graph& g, Vertex v, Measure measure);
-[heading Where Defined]
-`boost/graph/degree_centrality.hpp`
+The `degree_centrality()` function computes this measure for a single vertex,
+returning the value to the caller. Optionally, a degree measure can be given,
+specializing the computation of degree centrality. See the [degree_centrality_measures]
+section for more details on the influence and prestige measures.
[heading Parameters]
[table
@@ -92,11 +84,9 @@
[
The graph object for which the degree centralities will be computed.
- *Requirements:* The `Graph` type must be a model of the [BoostIncidenceGraph]
+ *Requirements:* The `Graph` type must be a model of the [IncidenceGraph]
concept. If the `Measure` parameter is given as `prestige_measure`,
- then the graph must be a model of the [BoostBidirectionalGraph] concept.
- For the `degree_centrality()` functions, the Graph must also model
- the [BoostVertexListGraph] concept.
+ then the graph must be a model of the [BidirectionalGraph] concept.
]
]
[
@@ -109,15 +99,69 @@
]
]
[
+ [optional, in] [`Measure measure`]
+ [
+ The `measure` parameter allows the caller to override the default
+ computation of degree centrality for a vertex.
+
+ *Requirements:* The `Measure` type must be a model of the
+ [DegreeMeasure] concept. The `degree_type` of `Measure` must
+ be the same as the `value_type` of the `CentralityMap` type.
+ ]
+ ]
+]
+
+[heading Return Value]
+The `degree_centrality()` function returns the centrality of a vertex.
+If no `measure` parameter is given, the return type is the same as the
+`degree_size_type` of the `Graph`. Otherwise, it is the `degree_type` of
+the `Measure`.
+
+[heading Complexity]
+The `degree_centrality()` returns in /O(M)/. If the measure is not given,
+or the measure is given as `influence_measure` or `prestige_measure`, this function
+returns in constant time.
+[endsect]
+
+[section [^all_degree_centralities()]]
+ #include <boost/graph/degree_centrality.hpp>
+
+ template <typename Graph, typename CentralityMap>
+ void all_degree_centralities(const Graph& g, CentralityMap cent);
+
+ template <typename Graph, typename CentralityMap, typename Measure>
+ void all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure);
+
+The `all_degree_centralities()` computes the degree centrality for each vertex in the
+graph, assigning the values to an output property map. Optionally, a degree measure
+can be given, specializing the computation of degree centrality. See the
+[degree_centrality_measures] section for more details on the influence and
+prestige measures.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& graph`]
+ [
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must model the [VertexListGraph]
+ and [IncidenceGraph] concepts. If the `Measure` parameter is given
+ as `prestige_measure`, then the graph must be a model of the
+ [BidirectionalGraph] concept.
+ ]
+ ]
+ [
[required, out] [`CentralityMap cent`]
[
The property map that contains the degree centralities of all vertices
in a graph after calling the `degree_centrality()` function.
*Requirements:* The `CentralityMap` type must be a model of the
- [BoostWritablePropertyMap] concept. The `key_type` of the map must
+ [WritablePropertyMap] concept. The `key_type` of the map must
be the same as the `vertex_descriptor` of the `Graph` type. If the
- `measure` parameter is given in the call, then the `value_type`
+ `Measure` parameter is given in the call, then the `value_type`
of `CentralityMap` must be the same as `Measure::degree_type`.
Otherwise, the `value_type` must be the same as the `degree_size_type`
of the graph.
@@ -130,67 +174,227 @@
computation of degree centrality for a vertex.
*Requirements:* The `Measure` type must be a model of the
- [BoostDegreeMeasure] concept. The `degree_type` of `Measure` must
+ [DegreeMeasure] concept. The `degree_type` of `Measure` must
be the same as the `value_type` of the `CentralityMap` type.
]
]
]
+[heading Complexity]
+The `all_degree_centralities()` function returns in /O(n*O(M))/ where /n/ is the
+number of vertices in the graph and /M/ is a measure of a vertex. If the measure
+is not specified or is `influence_measure` or `prestige_measure`, this function
+returns in linear time.
+[endsect]
+
+[section [^influence()]]
+ template <typename Graph, typename Vertex>
+ typename graph_traits<Graph>::degree_size_type
+ influence(const Graph& g, Vertex v);
+
+The `influence()` function the influence of the vertex to the caller. The influence
+of a vertex is the same as its out-degree.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& graph`]
+ [
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must be a model of the [IncidenceGraph]
+ concept. If the `Measure` parameter is given as `prestige_measure`,
+ then the graph must be a model of the [BidirectionalGraph] concept.
+ ]
+ ]
+ [
+ [required, in] [`Vertex v`]
+ [
+ The vertex descriptor for which the degree centrality is computed.
+
+ *Requirements:* The `Vertex` type must be the same as the `vertex_descriptor`
+ of the `Graph` parameter.
+ ]
+ ]
+]
+
[heading Return Value]
-The `vertex_degree_centrality()` function returns the centrality of a vertex.
-If no `measure` parameter is given, the return type is the same as the
-`degree_size_type` of the `Graph`. Otherwise, it is the `degree_type` of
-the `Measure`.
+The `influence()` function returns the influence of the vertex, which is the same
+as its out-degree.
[heading Complexity]
-The `degree_centrality()` function returns in /O(n*O(M))/ where /n/ is the
-number of vertices in the graph and /M/ is a measure of a vertex. This is
-linear for both the `influence_measure` and `prestige_measure`.
+The `influence()` function returns in constant time.
+[endsect]
+
+[section [^all_influence_values()]]
+ #include <boost/graph/degree_centrality.hpp>
+
+ template <typename Graph, typename CentralityMap>
+ void all_influence_values(const Graph& g, CentralityMap cent);
-The `vertex_degree_centrality()` returns in /O(M)/. This is constant for both
-the `influence_measure` and `prestige_measure`.
-The complexity of the `influence_measure` and `prestige_measure` functions are
-both constant time.
+The `all_influence_values()` function computes the influence of each vertex in the
+graph, assigning the values to an output property map.
-[heading Example (Degree Centrality)]
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& graph`]
+ [
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must model the [VertexListGraph]
+ and [IncidenceGraph] concepts. If the `Measure` parameter is given
+ as `prestige_measure`, then the graph must be a model of the
+ [BidirectionalGraph] concept.
+ ]
+ ]
+ [
+ [required, out] [`CentralityMap cent`]
+ [
+ The property map that contains the degree centralities of all vertices
+ in a graph after calling the `degree_centrality()` function.
+
+ *Requirements:* The `CentralityMap` type must be a model of the
+ [WritablePropertyMap] concept. The `key_type` of the map must
+ be the same as the `vertex_descriptor` of the `Graph` type. If the
+ `Measure` parameter is given in the call, then the `value_type`
+ of `CentralityMap` must be the same as `Measure::degree_type`.
+ Otherwise, the `value_type` must be the same as the `degree_size_type`
+ of the graph.
+ ]
+ ]
+]
+
+[heading Complexity]
+The `all_influence_values()` function returns linear time with respect to the
+number of vertices in the graph.
+[endsect]
+
+[section [^prestige()]]
+ template <typename Graph, typename Vertex>
+ typename graph_traits<Graph>::degree_size_type
+ prestige(const Graph& g, Vertex v);
+
+The `prestige()` function the prestige of the vertex to the caller. The prestige
+of a vertex is the same as its in-degree.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& graph`]
+ [
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must be a model of the [IncidenceGraph]
+ concept. If the `Measure` parameter is given as `prestige_measure`,
+ then the graph must be a model of the [BidirectionalGraph] concept.
+ ]
+ ]
+ [
+ [required, in] [`Vertex v`]
+ [
+ The vertex descriptor for which the degree centrality is computed.
+
+ *Requirements:* The `Vertex` type must be the same as the `vertex_descriptor`
+ of the `Graph` parameter.
+ ]
+ ]
+]
+
+[heading Return Value]
+The `prestige()` function returns the influence of the vertex, which is the same
+as its out-degree.
+
+[heading Complexity]
+The `prestige()` returns in constant time.
+[endsect]
+
+[section [^all_prestige_values()]]
+ #include <boost/graph/degree_centrality.hpp>
+
+ template <typename Graph, typename CentralityMap>
+ void all_prestige_values(const Graph& g, CentralityMap cent);
+
+
+The `all_prestige_values()` function computes the prestige of each vertex in the
+graph, assigning the values to an output property map.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& graph`]
+ [
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must model the [VertexListGraph]
+ and [IncidenceGraph] concepts. If the `Measure` parameter is given
+ as `prestige_measure`, then the graph must be a model of the
+ [BidirectionalGraph] concept.
+ ]
+ ]
+ [
+ [required, out] [`CentralityMap cent`]
+ [
+ The property map that contains the degree centralities of all vertices
+ in a graph after calling the `degree_centrality()` function.
+
+ *Requirements:* The `CentralityMap` type must be a model of the
+ [WritablePropertyMap] concept. The `key_type` of the map must
+ be the same as the `vertex_descriptor` of the `Graph` type. If the
+ `Measure` parameter is given in the call, then the `value_type`
+ of `CentralityMap` must be the same as `Measure::degree_type`.
+ Otherwise, the `value_type` must be the same as the `degree_size_type`
+ of the graph.
+ ]
+ ]
+]
+
+[heading Complexity]
+The `all_prestige_values()` function returns linear time with respect to the
+number of vertices in the graph.
+[endsect]
+
+[section Measures]
+ template <typename Graph> struct influence_measure;
+ template <typename Graph> struct prestige_measure;
+
+ template <typename Graph>
+ influence_measure<Graph> measure_influence(const Graph&);
+
+ template <typename Graph>
+ prestige_measure<Graph> measure_prestige(const Graph&);
+
+These functions in this module can be specialized throught the use of different
+/measure/ functors. These funtors are called to compute the degree centraltiy of a
+vertex within the computational framework. This module provides the two default
+measures for /influence/ and /prestige/ and functions to help instantiate them.
+Custom measures can also be used.
+
+The `influence_measure` returns the out-degree of a vertex. Using this measure
+requires the `Graph` to model the [IncidenceGraph] concept.
+
+The `prestige_measure` returns the in-degree of a vertex. Using this measure
+requires the `Graph` to model the [BidirectionalGraph] concept.
+
+The `measure_influence()` and `measure_prestige()` functions can be used to
+create the corresponding measure objects.
+[endsect]
+
+[section Examples]
+[heading Degree Centrality]
This example reads a graph from standard input (in a simple edge-list format),
computes the degree-centrality of each vertex, and prints them to standard
output. This example includes of the following files:
-* [^examples/closeness_centrality.hpp]
-* [^examples/social_network.hpp]
+* [^examples/degreee_centrality.hpp]
* [^examples/helper.hpp]
-To make typing easier, we define some aliases for the types used in this program
-in the global scope. This defines a social network as an undirected graph whose
-vertices are `Actor` properties. The `Actor` type simply stores an associated name
-for each vertex.
-[social_network_types]
-
-We also need a property map that will store the degree centrality as an output
-of the measure. The value type is given as `unsigned` because vertices do
-have negative degree.
-[centrality_map_types]
-
-In the main program, we construct an empty graph, and an associated mapping of
-names to vertices. This mapping is used in the construction of the graph.
-[setup_social_network]
-
-Building the network requires reading graph data from standard input. Here, the
-`add_named_vertex()` function is used to ensure that each name corresponds to
-a single vertex. This function is defined in `helper.hpp`.
-[build_social_network]
-
-Having built the graph, we can now compute the degree centrality of each vertex.
-This is done by constructing a container for the centrality values and a property
-map over it. This map is passed to the `degree_centrality()` function to store
-the computed values.
-[compute_degree_centrality]
-
-Finally, we iterate over the vertices, printing the degree centrality of each
-person in the network.
-[print_social_network]
+[degree_centrality_example]
If given the `social_network.graph` file as input, the program will produce the
following output:
@@ -207,33 +411,16 @@
Howard: 2
]
-[heading Example (Influence and Prestige)]
+[heading Influence and Prestige]
This example is nearly identical to the previous in that it computes the degree
centrality over vertices in a graph. However, this example constructs a directed
-graph and computes both influence and prestige.
+graph and computes both influence and prestige. This example consist of the following
+files:
-In this example, the only type definition that varies from the previous is that
-of the graph itself. Specifically, we declare this as a direted graph to help
-capture the semantics of information flow.
-
- typedef directed_graph<Actor> Graph;
-
-Even the code that builds the graph is identical. Since the graph is directed, however,
-the order in which vertices are listed determine directionality of the edge. For
-example, a vertex pair given as "=myspace,slashdot=" in the input file will generate
-an edge from the vertex named =myspace= to that named =slashdot=.
-
-Computing the influence and prestige requires the allocation of two property maps,
-and two calls to the `degree_centrality()` function. The calls to `measure_influence()`
-and `measure_prestige()` create temporary measure functions that are responsible
-for those values respectively.
-[compute_influence_prestige]
-Note that the `measure_influence()` call can be ommitted to compute the influence
-of vertices. If not given, `degree_centrality()` and `vertex_degree_centrality()`
-will compute influence by default.
+* [^examples/influence_prestige.hpp]
+* [^examples/helper.hpp]
-Finally, print the results for each vertex in the graph.
-[print_influence_prestige]
+[influence_prestige_example]
If given the `info_network.graph` file as input, the program will produce
the following output where the second column is influence and the third is prestige:
@@ -248,5 +435,6 @@
blogspot 2 0
bbc 1 1
]
+[endsect]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -39,10 +39,10 @@
to the many situations in which it can be used. In the pseudo-code below, the event
points for DFS are indicated in by the triangles and labels on the right. The user-defined
actions must be provided in the form of a visitor object, that is, an object whose type
-meets the requirements for a [BoostDFSVisitor]. In the pseudo-code we show the algorithm
+meets the requirements for a [DFSVisitor]. In the pseudo-code we show the algorithm
computing predecessors /p/, discovery time /d/ and finish time /t/. By default, the
`depth_first_search()` function does not compute these properties, however there are
-pre-defined visitors such as [boost_predecessor_recorder] and [boost_time_stamper] that
+pre-defined visitors such as [predecessor_recorder] and [time_stamper] that
can be used to do this.
[pre
@@ -90,8 +90,8 @@
[
[in] [`Graph& g`]
[
- A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
- and [BoostIncidenceGraph].
+ A directed or undirected graph. The graph type must be a model of [VertexListGraph]
+ and [IncidenceGraph].
]
]
[
@@ -110,7 +110,7 @@
[in] [`visitor(Visitor vis)`]
[
A visitor object that is inovked inside the algorithm at event points specified by the
- [BoostDFSVisitor]. The `vis` object must be model the [BoostDFSVisitor] concept.
+ [DFSVisitor]. The `vis` object must be model the [DFSVisitor] concept.
*Default* `bfs_visitor<null_visitor>`.
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -113,15 +113,15 @@
]
[h5 Model Of]
-[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
-[BoostMutableGraph], and [BoostPropertyGraph].
+[IncidenceGraph], [VertexListGraph], [EdgeListGraph], [AdjacencyGraph],
+[MutableGraph], and [PropertyGraph].
[h5 Where Defined]
`boost/graph/directed_graph.hpp`
[h4 Associated Types]
There are a number of useful types associated with the `directed_graph` class.
-Most of these are accessed through [boost_graph_traits] or other template classes.
+Most of these are accessed through [graph_traits] or other template classes.
For convenience these types have been grouped by purpose.
[h5 Descriptor Types]
@@ -131,14 +131,14 @@
[`graph_traits<directed_graph>::vertex_descriptor`]
[
The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
- models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ models the [Descriptor] and [NoConcept Hashable] concepts.
]
]
[
[`graph_traits<directed_graph>::edge_descriptor`]
[
The type for the edge descriptors associated with the graph. The `edge_descriptor`
- models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ models the [Descriptor] and [NoConcept Hashable] concepts.
]
]
]
@@ -772,7 +772,7 @@
[h4 Rationale]
Unlike most graph classes in Boost.Graph, the `directed_graph` does not model the
-[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+[MutablePropertyGraph] concept. The reason for this is that it is relatively
difficult from a usability standpoint to easily deduce the type to be passed as a
property when adding vertices and edges - but especially vertices.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -10,19 +10,19 @@
template <class DistanceMap, class EventTag>
class distance_recorder;
-This is an [BoostEventVisitor] that records the distance of a vertex (using a property
+This is an [EventVisitor] that records the distance of a vertex (using a property
map) from some source vertex during a graph search. When applied to edge /e = (u,v)/,
the distance of /v/ is recorded to be one more than the distance of /u/. The distance
recorder is typically used with the `on_tree_edge` or `on_relax_edge` events, and cannot
be used with vertex events.
-The [boost_distance_recorder] class can be used with graph algorithms by wrapping it with
-the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also,
+The [distance_recorder] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [bfs_visitor] and [dfs_visitor]. Also,
this event visitor can be combined with other event visitors using `std::pair` to form
-an [BoostEventVisitorList].
+an [EventVisitorList].
[h4 Model Of]
-[BoostEventVisitor]
+[EventVisitor]
[h4 Where Defined]
`boost/graph/visitors.hpp`
@@ -33,7 +33,7 @@
[
[`DistanceMap`]
[
- A [BoostWritablePropertyMap] where the key type is of type `vertex_descriptor`
+ A [WritablePropertyMap] where the key type is of type `vertex_descriptor`
and the value type is numeric (usually an integer or the same type as the
edge weight).
]
@@ -91,7 +91,7 @@
``
]
[
- A convenience function for creating [boost_distance_recorder] instances.
+ A convenience function for creating [distance_recorder] instances.
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,29 +6,11 @@
/]
[section Eccentricity]
+[template ex_eccentricity[] [link
+ boost_graph.reference.algorithms.measures.eccentricity.examples.eccentricity__radius__and_diameter
+ Eccentricity Example]]
- template <typename Graph, typename DistanceMap>
- typename property_traits<DistanceMap>::value_type
- vertex_eccentricity(const Graph& g, DistanceMap dm)
-
- template <typename Graph, typename DistanceMatrixMap, typename EccentricityMap>
- void eccentricity(const Graph& g, DistanceMatrixMap dm, EccentricityMap em)
-
-
- template <typename Graph, typename EccentricityMap>
- inline typename property_traits<EccentricityMap>::value_type
- graph_radius(const Graph& g, EccentricityMap ecc)
-
-
- template <typename Graph, typename EccentricityMap>
- inline typename property_traits<EccentricityMap>::value_type
- graph_diameter(const Graph& g, EccentricityMap ecc)
-
- template <typename Graph, typename EccentricityMap>
- inline std::pair<typename property_traits<EccentricityMap>::value_type,
- typename property_traits<EccentricityMap>::value_type>
- graph_radius_diameter(const Graph& g, EccentricityMap ecc)
-
+[heading Overview]
The /eccentricity/ of a vertex is the maximum geodesic distance (shortest path) from
that vertex to any other vertex in the graph. Intuitively, vertices with low
eccentricity can reach all other vertices in the graph more "quickly" than vertices
@@ -50,31 +32,20 @@
Because the graph is small and relatively well, connected the eccentricies are
exaclty 2 or 3 for all vertices. The radius (the smaller of these numbers)
-is 2, and the diameter is 3.
+is 2, and the diameter is 3. See the [ex_eccentricity] for details on computing
+eccentricity and related measures.
+
+[section [^eccentricity()]]
+ #include <boost/graph/eccentricity.hpp>
-This module provide a set of generic functions for computing eccentricities and
-related measures. The first function, `eccentricity()` computes this values for all
-vertices in the graph, given a matrix that provides the shortest paths between all
-pairs of vertices. This matrix can be computed as the output of an "all-pairs shortest
-paths "algorithm (e.g., [boost_floyd_warshall_all_pairs_shortest_paths]) or repeated
-application of a [boost_breadth_first_search] (if the graph is unweighted). The
-output of this function is stored in the eccentricity property map.
-
-The second function, `vertex_eccentricity()` computes the eccentricty of a
-single vertex given the shortest paths to every other vertex in the graph. The
-distance map can be computed using a shortest paths algorithms (e.g., [boost_dijkstra_shortest_paths]
-or a [boost_breadth_first_search]. The output of this function is returned to the
-caller.
-
-This module also provides a set of functions for computing the related measures
-of a graph's radius and diameter. These functions take as input, the previously
-computed eccentricity values output by the `eccentricity()` function, and return
-the computed value to the caller. The `graph_radius_and_diameter()` function
-combines both computations to a single iteratation and returns the values as a
-pair. The `first` value in the pair is the radius and the `second` is the diameter.
+ template <typename Graph, typename DistanceMap>
+ typename property_traits<DistanceMap>::value_type
+ eccentricity(const Graph& g, DistanceMap dm)
-[heading Where Defined]
-`boost/graph/eccentricity.hpp`
+The `eccentricity()` function computes the eccentricty of a single vertex
+given the shortest paths to every other vertex in the graph. The distance map can
+be computed using a shortest paths algorithms (e.g., [dijkstra_shortest_paths] or a
+[breadth_first_search]. The output of this function is returned to the caller.
[heading Parameters]
[table
@@ -85,7 +56,7 @@
The graph for which the eccentricity measures are being comptued.
*Requirements:* The `Graph` type must be a model of the
- [BoostVertexListGraph] concepts.
+ [VertexListGraph] concepts.
]
]
[
@@ -95,10 +66,50 @@
shortest path between a vertex `u` and `v`. The vertex `u` is the
vertex for which the distance map was initially computed.
- *Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance map must be the same as the `vertex_descriptor`
of the `Graph` parameter. The `value_type` is required to be a model of
- [BoostNumericValue].
+ [NumericValue].
+ ]
+ ]
+]
+
+[heading Return Value]
+The `eccentricity()` function returns the eccentricity of the vertex. If the graph
+is unconnected, this returns the infinite value of the distance map's `value_type`.
+
+[heading Complexity]
+The `eccentricity()` returns in linear with respect to the number of vertices
+in the graph.
+[endsect]
+
+[section [^eccentricities()]]
+ #include <boost/graph/eccentricity.hpp>
+
+ template <typename Graph, typename DistanceMatrixMap, typename EccentricityMap>
+ std::pair<typename property_traits<EccentricityMap>::value_type,
+ typename property_traits<EccentricityMap>::value_type>
+ eccentricity(const Graph& g, DistanceMatrixMap dm, EccentricityMap em)
+
+The `eccentricities()` function computes the eccentricity of each vertix in the graph,
+given a matrix that provides the shortest paths between all pairs of vertices. This
+matrix can be computed as the output of an all-pairs shortest paths algorithm (e.g., [floyd_warshall_all_pairs_shortest_paths]) or repeated application of a
+[breadth_first_search] (if the graph is unweighted). Theoutput of this function is
+stored in the eccentricity property map.
+
+This function also computes the radius and diameter of the graph, returning those
+values in a pair.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the eccentricity measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concepts.
]
]
[
@@ -108,122 +119,219 @@
of the shortest path between the two vertices. Note that the
distance between a vertex and itself should be 0 (i.e., `dm[u][u] == 0`).
- *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMatrixMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
- of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
+ of the `Graph` parameter. The `value_type` must be a [ReadWritePropertyMap]
whose `key_type` is also the `vertex_descriptor` of the `Graph` and
- whose `value_type` is a model of [BoostNumericValue].
+ whose `value_type` is a model of [NumericValue].
]
]
[
[required, out] [`EccentricityMap em`]
[
- When used with the `eccentricity()` function, the `em` parameter stores
- the eccentricity of each vertex in the graph. When used with the
- `radius()` or `diameter()` functions, `em` provides the input to compute
- the given graph property.
-
- [*Requirements - [^eccentricity()]:] The `EccentricityMap` must be a model
- of the [BoostWritablePropertyMap] concept.
+ The eccentricity map `em` stores the computed eccentricity values for
+ each vertex in the graph.
- [*Requirements - [^graph_radius()]/[^graph_diameter()]:] The `EccentricityMap` must
- be a model of the [BoostReadablePropertyMap] concept.
-
- *Requirements:* The `key_type` of the property map must be the `vertex_descriptor`
+ *Requirements:* The `EccentricityMap` type must model the [WritablePropertyMap]
+ concept. The `key_type` of the property map must be the `vertex_descriptor`
of the `Graph` parameter. The `value_type` must be the same type as the
`value_type` of the `DistanceMatrixMap` parameter.
]
]
]
+[heading Return]
+The `eccentricities()` function returns a pair containing the radius and diameter
+as the `first` and `second` elements respectively.
+
+[heading Complexity]
+The `eccentricities()` function returns in ['O(n[super 2])] where /n/ is the number
+of vertices in the graph.
+[endsect]
+
+[section [^radius()]]
+ #include <boost/graph/eccentricity.hpp>
+
+ template <typename Graph, typename EccentricityMap>
+ inline typename property_traits<EccentricityMap>::value_type
+ radius(const Graph& g, EccentricityMap ecc)
+
+The `radius()` function returns the radius of the graph, which is defined as the
+minimum eccentricity of any vertex in the graph. The radius is computed from the
+eccentricities that have been previously computed using the [eccentricity] function.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the eccentricity measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concepts.
+ ]
+ ]
+ [
+ [required, out] [`EccentricityMap em`]
+ [
+ The eccentricity map `em` provides access to the previously computed
+ eccentricities of all vertices in the graph.
+
+ *Requirements:* The `EccentricityMap` type must model the [ReadablePropertyMap]
+ concept. The `key_type` of the property map must be the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must model the [NumericValue]
+ concept.
+ ]
+ ]
+]
+
[heading Return Value]
-The `vertex_eccentricity()` function returns the eccentricity of the vertex.
-If the graph is unconnected, this returns the infinite value of the distance
-map's `value_type`.
-
-The `graph_radius()` and `graph_diameter()` functions return their respective measures.
-The return type of these functions is the same as the `value_type` of the `EccentricityMap`
-parameter.
+The `radius()` function return the radius of the graph. The return type of
+this function is the same as the `value_type` of the `EccentricityMap` parameter.
-The `graph_radius_diameter()` funtion returns a pair containing both the radius (`first`)
-and diameter (`second`) of the graph. The types of these values are the same as the
-`value_type` of the `EccentricityMap`.
+[heading Complexity]
+The `radius()` function returns in linear time with respect to the number
+of vertices in the graph.
+[endsect]
+
+[section [^diameter()]]
+ #include <boost/graph/eccentricity.hpp>
+
+ template <typename Graph, typename EccentricityMap>
+ inline typename property_traits<EccentricityMap>::value_type
+ diameter(const Graph& g, EccentricityMap ecc)
+
+The `diameter()` function returns the diameter of the graph, which is defined as the
+maximum eccentricity of any vertex in the graph. The diameter is computed from the
+eccentricities that have been previously computed using the [eccentricity] function.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the eccentricity measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concepts.
+ ]
+ ]
+ [
+ [required, out] [`EccentricityMap em`]
+ [
+ The eccentricity map `em` provides access to the previously computed
+ eccentricities of all vertices in the graph.
+
+ *Requirements:* The `EccentricityMap` type must model the [ReadablePropertyMap]
+ concept. The `key_type` of the property map must be the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must model the [NumericValue]
+ concept.
+ ]
+ ]
+]
+
+[heading Return Value]
+The `diameter()` function return the diameter of the graph. If any vertices
+are disconnected from the graph, the diameter will be infinite. The return type of
+this function is the same as the `value_type` of the `EccentricityMap` parameter.
[heading Complexity]
-The `eccentricity()` function returns in ['O(n[super 2])] where /n/ is the number
+The `diameter()` function returns in linear time with respect to the number
of vertices in the graph.
+[endsect]
-The `vertex_eccentricity()` is linear with respect to the number of vertices in
-the graph.
+[section [^radius_diameter()]]
+ #include <boost/graph/eccentricity.hpp>
-The `graph_diameter()`, `graph_radius()`, and `graph_radius_diameter()` function are
-all linear with respect to the number of vertices in the graph.
+ template <typename Graph, typename EccentricityMap>
+ std::pair<typename property_traits<EccentricityMap>::value_type,
+ typename property_traits<EccentricityMap>::value_type>
+ radius_diameter(const Graph& g, EccentricityMap ecc)
+
+The `radius_diameter()` function returns both the radius and diameter of the
+graph as a pair such that the `first` element of the pair is the radius and the
+`second` element is the diameter. These values are computed from the eccentricities
+that have been previously computed using the [eccentricity] function.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the eccentricity measures are being comptued.
-[heading Examples]
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concepts.
+ ]
+ ]
+ [
+ [required, out] [`EccentricityMap em`]
+ [
+ The eccentricity map `em` provides access to the previously computed
+ eccentricities of all vertices in the graph.
+
+ *Requirements:* The `EccentricityMap` type must model the [ReadablePropertyMap]
+ concept. The `key_type` of the property map must be the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must model the [NumericValue]
+ concept.
+ ]
+ ]
+]
+
+[heading Return Value]
+The `radius_diameter()` funtion returns a pair containing both the radius (`first`)
+and diameter (`second`) of the graph. The types of these values are the same as the
+`value_type` of the `EccentricityMap`.
+
+[heading Complexity]
+The `radius_diameter()` returns in linear time with respect to the number of vertices
+in the graph.
+[endsect]
+
+[section Examples]
+[heading Eccentricity, Radius, and Diameter]
This example computes the eccentricities for all vertices in a graph, and the radius
and diameter of the graph itself. This example includes the following files:
-* [^examples/closeness_centrality.hpp]
-* [^examples/social_network.hpp]
+* [^examples/eccentricity.cpp]
* [^examples/helper.hpp]
-First, we define the graph and its associated types.
-[social_network_types]
-Here, we use the `Actor` to store an actor name with each vertex. We also need to
-define a number of related property types to support property maps for the algorithms
-called in the program.
-
-Since this program will call [boost_floyd_warshall_all_pairs_shortest_paths] to
-compute distances between vertices, we need a matrix to store the distances.
-[distance_matrix_types]
-
-We also need a property map that assigns weights to each edge. Since our graph is
-unweighted, we can use the [boost_constant_property_map] to return a constant value
-for each edge. [constant_weight_map_types]
-
-We also need an output property map to store the eccentricities of each vertex.
-[eccentricity_map_types]
-
-In the main program, we instantiate the graph and an extra `std::map` that we
-use during graph construction.
-[setup_social_network]
-
-The graph is read from standard input. This process uses the `add_named_vertex()`
-function, which is not part of the Boost.Graph library but defined in the file
-`examples/helper.hpp`.
-[build_social_network]
-
-The next step is to compute the distance. This is done using the
-[boost_floyd_warshall_all_pairs_shortest_paths] function. This could also be done
-using [boost_johnson_all_pairs_shortest_paths]. This is done by first constructing
-a matrix to hold the distance values, and a property map over the matrix. Additionally,
-we use a [boost_constant_property_map] to return the value `1` for all edge weights.
-Both the distance matrix and edge-weight maps are used as inputs to the distance
-algorithm.
-[compute_constant_distances]
-
-After computing the distance, we can use the resulting distance matrix to compute
-the eccentricity of each vertex. This is done by constructing a container for
-the eccentricity values and a property map accessor for it. The previously computed
-distance map and eccentricity map are passed as inputs to the computation. The
-eccentricity map is also used as an input to the `graph_radius()` and `graph_diameter()`
-functions.
-[compute_eccentricity]
-
-If the input graph is large, it would be better to compute the radius and diameter
-in a single call. The last two lines above could be repaced with:
+[eccentricity_example]
- int radius, diameter;
- tie(radius, diameter) = graph_radius_diameter(g, em);
+Note that we can also compute the radius and diameter separatel. For exmaple:
-Finally, we can print the radius and diameter of the graph.
-[print_radius_diameter]
+ // Compute the radius and diameter after computing eccentricites,
+ // but separately.
+ int r = radius(g, em);
+ int d = diameter(g, em);
+
+ // Compute the radius and diameter after computing eccentricities,
+ // but in one step.
+ int r, d;
+ tie(r, d) = radius_diameter(g, em);
+
+For small graphs, choosing one method over the other makes little difference. For
+large graphs, however, multiple iterations over the vertex set may result in lower
+performance.
If given the `social_network.graph` file as input, the output will be:
[pre
-radius 2
-diameter 3
+Scott 2
+Jill 3
+Mary 3
+Bill 3
+Josh 3
+Frank 2
+Laurie 3
+Anne 3
+Howard 3
+radius: 2
+diamter: 3
]
+[endsect]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/exterior_vertex_property.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -22,12 +22,12 @@
The following expressions are used in this document:
[table
[[Expression] [Description]]
- [[`G`] [A graph type modeling a refinement of the [BoostGraph] concept.]]
+ [[`G`] [A graph type modeling a refinement of the [Graph] concept.]]
[[`V`] [A value type that models the [SgiAssignable] concept.]]
]
[heading Model Of]
-[BoostExteriorProperty]
+[ExteriorProperty]
[heading Template Parameters]
[table
@@ -39,7 +39,7 @@
is being declared.
*Requirements:* `Graph` must model a refinement of the the
- [BoostGraph] concept.
+ [Graph] concept.
]
]
[
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -6,39 +6,16 @@
/]
[section Mean Geodesic]
+[template ex_mean_geodesic[] [link
+ boost_graph.reference.algorithms.measures.mean_geodesic.examples.mean_geodesic_distance
+ Mean Geodesic Example]]
+[template ex_inclusive_mean_geodesic[] [link
+ boost_graph.reference.algorithms.measures.mean_geodesic.examples.inclusive_mean_geodesic_distance
+ Inclusive Mean Geodesic Example]]
- template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap>
- void mean_geodesic(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
-
- template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap, typename Measure>
- void mean_geodesic(const Graph& g,
- DistanceMatrixMap dm,
- GeodesicMap gm,
- Measure m)
-
-
- template <typename Graph, typename DistanceMap>
- float vertex_mean_geodesic(const Graph& g, DistanceMap dm)
-
- template <typename ResultType, typename Graph, typename DistanceMap>
- ResultType vertex_mean_geodesic(const Graph& g, DistanceMap dm)
-
- template <typename Graph, typename DistanceMap, typename Measure>
- typename Measure::result_type
- vertex_mean_geodesic(const Graph& g, DistanceMap dm, Measure m)
-
-
- template <typename Graph, typename GeodesicMap, typename Measure>
- typename Measure::result_type
- graph_mean_geodesic(const Graph& g, GeodesicMap gm, Measure m)
-
- template <typename Graph, typename GeodesicMap>
- typename property_traits<GeodesicMap>::value_type
- graph_mean_geodesic(const Graph& g, GeodesicMap gm)
-
-
+[heading Overview]
The /mean geodesic distance/ measure is used in large network analysis to identify
-central vertices and as a measure of the /small world phenomenon/. The mean geodesic
+central vertices and as a measure of the /small-world phenomenon/. The mean geodesic
distance of a vertex is defined as the average of geodesic distances from that
vertex every /other/ vertex in the graph. It is computed as:
@@ -56,14 +33,14 @@
the so-called small-world phenomenon. If the mean geodesic distance of a graph is
small with respect to its density (the ratio of vertices to edges), then the graph
is said to exhibit the small-world phenomenon. This implies that vertices are
-The mean geodesic distance of a graph is the average of the mean geodesics for
-each vertex. It is computed as:
+The mean geodesic distance of a graph, it's so-called /small-world distance/, is
+the average of the mean geodesics for each vertex. It is computed as:
-[$images/eq/graph_mean_geodesic.png]
+[$images/eq/small_world.png]
-Note that computing the measure in this fashion means that the mean geodesic distance
-of the graph may lie outside the minimum and maximum mean geodesic distances of
-its vertices.
+Note that computing the measure in this fashion means that the small-world distance
+of the graph may lie outside the minimum and maximum mean geodesic distances of its
+vertices.
Consider a social network of friends, which is represented by an undirected graph.
@@ -74,34 +51,37 @@
In this network, Frank has the lowest mean geodesic distance with an average of
1.375. Scott and Laurie have the second lowest distances with values of 1.5 and
-1.875 respectively.
+1.875 respectively. The small-world distance of this graph is approximately 1.92.
+See the [ex_mean_geodesic] for details on computing the mean geodesic and small
+world distances of undirected graphs.
+
+This framework also allows for a specialization of measures used to compute these
+values. The default measures used in this framework implement the formulas given
+above. In some instances, it may be worthwhile to redefine the measure. For example,
+if a graph has meaningful non-zero distance-to-self, the averages should be computed
+over all vertices instead of excluding the vertex for which distances are being
+averaged. See the [ex_inclusive_mean_geodesic] for details on defining alternative
+measures, and using weighted graphs to find shortest paths.
-This module defines a flexible framework for computing the mean geodesic distance
-of vertices in a graph for previously computed geodesics by providing thrtee generic
-functions. The first function, `mean_geodesic()` computes the average distance of
-each vertex in a graph from a matrix containing the distances between vertices.
-This matrix can be computed as the output of an "all pairs shortest path" algorithm
-(e.g., [boost_floyd_warshall_all_pairs_shortest_paths] or [boost_johnson_all_pairs_shortest_paths])
-or as the result repeated [boost_breadth_first_search]s (if the graph is unweighted).
-
-The second function, `vertex_mean_geodesic()` can be used to compute the
-closeness of a single vertex. This function requires a distance map that contains
-the distance from one vertex (the source) to all others in the graph. This
-distance map can be computed as the result of a "shortest paths" algorithm such
-as [boost_dijkstra_shortest_paths] or [boost_bellman_ford_shortest_paths]. If the
-graph is unweighted, distances can be recorded from a [boost_breadth_first_search].
+[section [^mean_geodesic()]]
+ #include <boost/graph/geodesic_distance.hpp>
-The third function, `graph_mean_geodesic()` computes the mean geodesic distance
-for the graph by averaging the mean geodesic distances of each vertex in the geodesic
-distance map. Note that this function does not compute the mean geodesic distances
-of each vertex. Those values must be computed by using one of the functions above.
+ template <typename Graph, typename DistanceMap>
+ float mean_geodesic(const Graph& g, DistanceMap dm)
-This framework also allows for a specialization of measures used to compute
-these values. The default measures used in this framework implement the formulas
-given above.
+ template <typename ResultType, typename Graph, typename DistanceMap>
+ ResultType mean_geodesic(const Graph& g, DistanceMap dm)
-[heading Where Defined]
-`boost/graph/geodesic_distance.hpp`
+ template <typename Graph, typename DistanceMap, typename Measure>
+ typename Measure::result_type
+ mean_geodesic(const Graph& g, DistanceMap dm, Measure m)
+
+The `mean_geodesic()` function can be used to compute the mean geodesic distance
+(its average distance to all other vertices) for a single vertex. This function
+requires a distance map that contains the distance from one vertex (the source) to
+all others in the graph. This distance map can be computed as the result of a
+shortest paths algorithm such as [dijkstra_shortest_paths] or [bellman_ford_shortest_paths].
+If the graph is unweighted, distances can be recorded from a [breadth_first_search].
[heading Parameters]
[table
@@ -114,7 +94,7 @@
given, the return type is `float`.
*Requirements:* The return type is required to model the
- [BoostNumericValue] concept.
+ [NumericValue] concept.
]
]
[
@@ -123,7 +103,7 @@
The graph for which vertex measures are being comptued.
*Requirements:* The `Graph` type must be a model of the
- [BoostVertexListGraph] concepts.
+ [VertexListGraph] concepts.
]
]
[
@@ -133,10 +113,68 @@
shortest path between a vertex `u` and `v`. The vertex `u` is the
vertex for which the distance map was initially computed.
- *Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance map must be the same as the `vertex_descriptor`
of the `Graph` parameter. The `value_type` is required to be a model of
- [BoostNumericValue].
+ [NumericValue].
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The 'measure' parameter is an instance of a closeness measure that
+ performs the final division for this computation.
+
+ *Requirements:* The `Measure` type must be a model of the [DistanceMeasure]
+ concept. The `distance_type` must be the same type as the `value_type`
+ of the `DistanceMap` parameter. The `result_type` of the `Measure` must
+ model the [NumericValue] concept.
+ ]
+ ]
+]
+
+[heading Return]
+The `mean_geodesic()` function returns the average of geodesic distances
+to other vertices from a source. If the source vertex is not connected to one other
+in the graph, this value is infinite.
+
+[heading Complexity]
+The `mean_geodesic()` function returns in /O(n*O(M))/ where /n/ is the number of
+vertices in the graph and /O(M)/ is the complexity of the given measure. If no
+measure is given, this function returns in linear time.
+[endsect]
+
+[section [^all_mean_geodesics()]]
+ #include <boost/graph/geodesic_distance.hpp>
+
+ template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap>
+ typename property_traits<GeodesicMap>::value_type
+ all_mean_geodesics(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
+
+ template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap, typename Measure>
+ typename property_traits<GeodesicMap>::value_type
+ all_mean_geodesics(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm, Measure m)
+
+The `all_mean_geodesics()` function computes the average distance of each vertex in a
+graph to every other vertex using a matrix that contains the distances between
+each pair of vertices. This matrix can be computed as the output of an all-pairs shortest
+path algorithm (e.g., [floyd_warshall_all_pairs_shortest_paths] or [johnson_all_pairs_shortest_paths])
+or as the result of repeated [breadth_first_search]s (if the graph is unweighted).
+
+This function returns the average of all mean geodesic distances, also known as the
+small-world distance. If any vertices have infinite mean geodesic distance, this
+return value will be infinite.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which vertex measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concepts.
]
]
[
@@ -145,134 +183,179 @@
Given vertices /u/ and /v/, the `dm` parameter provides the length
of the shortest path between the two vertices.
- *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ *Requirements:* `DistanceMatrixMap` must be a model of [ReadablePropertyMap].
The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
- of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
- whose `key_type` is also the `vertex_descriptor` of the `Graph` and
- whose `value_type` is a model of [BoostNumericValue].
+ of the `Graph` parameter. The `value_type` must be a [ReadWritePropertyMap]
+ whose `key_type` is also the `vertex_descriptor` of the `Graph` and whose
+ `value_type` is a model of [NumericValue].
]
]
[
[required, both] [`GeodesicMap gm`]
[
- When used with the `mean_geodesic()` function, the `gm` parameter stores
- the computed mean geodesic distances for each vertex pair in the matrix.
- When used with the `graph_mean_geodesic()` function, the parameter provides
- the input required to compute the mean distance for the graph.
-
- [*Requirements - [^mean_geodesic()]:] The `GeodesicMap` type is required
- to model the [BoostReadablePropertyMap] concept.
-
- [*Requirements - [^graph_mean_geodesic()]:] The `GeodesicMap` type is
- required to model the [BoostWritablePropertyMap] concept.
-
- *Requirements:* The `key_type` of this parameter must be the
- same as the `vertex_descriptor` of the `Graph` parameter, and the
- `value_type` must be a model of the [BoostNumericValue] concept.
+ The geodesic map `gm` stores the resulting mean geodesic distances for
+ each vertex in the graph.
+
+ *Requirements:* The `GeodesicMap` type must be a model of the
+ [WritablePropertyMap] concept. The `key_type` of this parameter
+ must be the same as the `vertex_descriptor` of the `Graph` parameter,
+ and the `value_type` must be a model of the [NumericValue] concept.
]
]
[
[optional, in] [`Measure measure`]
[
- The 'measure' parameter is an instance of a closeness measure that
- performs the final division for this computation.
+ The 'measure' parameter is an instance of a closeness measure operates
+ on the sum of distances of a vertex.
- *Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
+ *Requirements:* The `Measure` type must be a model of the [DistanceMeasure]
concept. The `distance_type` must be the same type as the `value_type`
of the `DistanceMap` or `DistanceMatrixMap`. The `result_type` of the
- `Measure` must model the [BoostNumericValue] concept.
+ `Measure` must model the [NumericValue] concept.
]
]
]
[heading Return]
-The `vertex_mean_geodesic()` function returns the average of geodesic distances
-to other vertices from a source. If the source vertex is not connected to one other
-in the graph, this value is infinite.
-
-The `graph_mean_geodesic()` function returns the mean geodesic distance for the
-entire graph - a common measure of the small world property. If the graph is
-unconnected, the mean geodesic distance is infinite.
+The `all_mean_geodesics()` function returns the small-world distance for the graph.
+This is the average of the mean geodesic distances of all vertices in the graph.
+If any vertices have infinite mean geodesic distance, then the small-world distance
+will also be infinite.
[heading Complexity]
-The `mean_geodesic()` function returns in ['O(n[super 2]*O(M))] where /n/ is the
-number of vertices in the graph, and /M/ is the complexity of the measure. By
-defualt, /M/ is constant.
+The `all_mean_geodesics()` function returns in ['O(n[super 2]*O(M))] where /n/ is the
+number of vertices in the graph, and /O(M)/ is the complexity of the given measure.
+If no measure is given, this function returns in quadratic time.
+[endsect]
+
+[section [^small_world_distance()]]
+ #include <boost/graph/geodesic_distance.hpp>
+
+ template <typename Graph, typename GeodesicMap, typename Measure>
+ typename Measure::result_type
+ small_world_distance(const Graph& g, GeodesicMap gm, Measure m)
+
+ template <typename Graph, typename GeodesicMap>
+ typename property_traits<GeodesicMap>::value_type
+ small_world_distance(const Graph& g, GeodesicMap gm)
-The `vertex_mean_geodesic()` function returns in /O(n*O(M))/. By default /M/ is
-constant.
+The `small_world_distance()` function computes the mean geodesic distance for the
+entire graph by averaging the mean geodesic distances of each vertex in the geodesic
+distance map. Note that this function does not compute the mean geodesic distances
+of each vertex. Those values must be computed by using the [mean_goedesic] function.
-The `graph_mean_geodesic()` function returns in /O(n*O(M))/. By default /M/ is
-constant.
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which vertex measures are being comptued.
-[heading Example]
+ *Requirements:* The `Graph` type must be a model of the
+ [VertexListGraph] concepts.
+ ]
+ ]
+ [
+ [required, both] [`GeodesicMap gm`]
+ [
+ The geodesic map `gm` contains the previously computed mean geodesic
+ distances for each vertex in the graph.
+
+ *Requirements:* The `GeodesicMap` type must model the [ReadablePropertyMap]
+ concept. The `key_type` of this parameter must be the same as the
+ `vertex_descriptor` of the `Graph` parameter, and the `value_type` must
+ be a model of the [NumericValue] concept.
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The 'measure' parameter is an instance of a closeness measure that
+ performs the final division for this computation.
+
+ *Requirements:* The `Measure` type must be a model of the [DistanceMeasure]
+ concept. The `distance_type` must be the same type as the `value_type`
+ of the `GeodesicMap`. The `result_type` must model the [NumericValue]
+ concept.
+ ]
+ ]
+]
+
+[heading Return]
+The `small_world_distance()` function returns the mean geodesic distance for the
+entire graph - a common measure of the small-world property. If the graph is
+unconnected, the mean geodesic distance is infinite.
+
+[heading Complexity]
+The `small_world_distance()` function returns in /O(n*O(M))/ where /n/ is the number
+of vertices in the graph and /O(M)/ is the complexity of the measure. If not measure
+is given, then this function returns in linear time.
+[endsect]
+
+[section Examples]
+[heading Mean Geodesic Distance]
This example shows how to compute the mean geodesic distance for each vertex
in a social network, and the mean geodesic distance for the graph as a whole.
This example includes the files
* [^examples/mean_geodesic.hpp]
-* [^examples/social_network.hpp]
* [^examples/helper.hpp]
-First, we define the graph and its associated types.
-[social_network_types]
-Here, we use the `Actor` to store an actor name with each vertex. We also need to
-define a number of related property types to support property maps for the algorithms
-called in the program.
-
-Since this program will call [boost_floyd_warshall_all_pairs_shortest_paths] to
-compute distances between vertices, we need a matrix to store the distances.
-[distance_matrix_types]
-
-We also need a property map that assigns weights to each edge. Since our graph is
-unweighted, we can use the [boost_constant_property_map] to return a constant value
-for each edge. [constant_weight_map_types]
-
-We also need an output property map to store the mean geodesic distance of each
-vertex.
-[geodesic_map_types]
-
-In the main program, we instantiate the graph and an extra `std::map` that we
-use during graph construction.
-
-[setup_social_network]
-
-The graph is read from standard input. This process uses the `add_named_vertex()`
-function, which is not part of the Boost.Graph library but defined in the file
-`examples/helper.hpp`.
-
-[build_social_network]
-
-The next step is to compute the distance. This is done using the
-[boost_floyd_warshall_all_pairs_shortest_paths] function. This could also be done
-using [boost_johnson_all_pairs_shortest_paths]. This is done by first constructing
-a matrix to hold the distance values, and a property map over the matrix. Additionally,
-we use a [boost_constant_property_map] to return the value `1` for all edge weights.
-Both the distance matrix and edge-weight maps are used as inputs to the distance
-algorithm.
-[compute_constant_distances]
-
-After computing the distance, we can use the resulting distance matrix to compute
-the mean geodesic distance of each vertex. This is done by constructing a container
-for the distance values and a property map accessor for it. The previously computed
-distance map and geodesic map are passed as inputs to `mean_geodesic()` function.
-The geodesic map, once computed, is then used as an input to the `graph_mean_geodesic()`
-function, which returns the mean geodesic distance of the graph.
-[compute_mean_geodesics]
+[mean_geodesic_example]
+
+In this example, the small world distance (`sw`) can be computed separetly from
+the mean geodesic distances if need be.
-As a final step, we print the mean geodesic distance of the graph.
-[print_graph_mean_geodesic]
+ // Compute the small-world distance after computing mean geodesics
+ float sw = small_world_distance(g, gm);
-If this program is given the `social_network.graph` file as input, the output
-will be:
+If given the file `social_network.graph` as input, the output of this program will
+be:
[pre
-mean geodesic distance: 1.91667
+Scott 1.5
+Jill 2.125
+Mary 2
+Bill 2.125
+Josh 2
+Frank 1.375
+Laurie 1.875
+Anne 2.125
+Howard 2.125
+small world distance: 1.91667
]
Note that this program can be easily modified to work on directed graphs. In the
file `social_network.hpp`, simply replace `typedef undirected_graph<Actor> ...` to
`typedef directed_graph<Actor> ...`.
+[heading Inclusive Mean Geodesic Distance]
+This example shows how to implement alternative measures for the [mean_geodesic]
+and [graph_mean_geodesic] functions to account for non-zero length self-loop
+distances. Mean geodesic distances are computed both ways and the results printed
+to standard output. This example includes the files:
+
+* [^examples/mean_geodesic.hpp]
+* [^examples/helper.hpp]
+
+[inclusive_mean_geodesic_example]
+
+If given the file `prob_network.graph` as input, the output of this program will
+be:
+
+[pre
+vertex excluding including
+myspace 0.941667 0.807143
+digg 0.538333 0.461429
+blogger 0.496667 0.425714
+slashdot 0.721667 0.618571
+wikipedia 0.498333 0.427143
+blogspot 0.763333 0.654286
+bbc 0.818333 0.701429
+small world (excluding self-loops): 0.682619
+small world (including self-loops): 0.585102
+]
+[endsect]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -10,15 +10,15 @@
template <class PredecessorMap, class EventTag>
class predecessor_recorder;
-This is an [BoostEventVisitor] that records the predecessor (or parent) of a vertex in
+This is an [EventVisitor] that records the predecessor (or parent) of a vertex in
a predecessor property map. This is particularly useful in graph search algorithms where
recording the predecessors is an efficient way to encode the search tree that was traversed
during the search. The predecessor recorder is typically used with the `on_tree_edge` or
`on_relax_edge events`, and cannot be used with vertex events.
-[boost_predecessor_recorder] can be used with graph algorithms by wrapping it with the
-algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also, this
-event visitor can be combined with other event visitors using `std::pair` to form an [BoostEventVisitorList].
+[predecessor_recorder] can be used with graph algorithms by wrapping it with the
+algorithm specific adaptor, such as [bfs_visitor] and [dfs_visitor]. Also, this
+event visitor can be combined with other event visitors using `std::pair` to form an [EventVisitorList].
Algorithms such as Dijkstra's and breadth-first search will not assign a predecessor
to the source vertex (which is the root of the search tree). Often times it is useful to
@@ -28,7 +28,7 @@
of every vertex to itself, so that all the root nodes can be distinguished.
[h4 Model Of]
-[BoostEventVisitor]
+[EventVisitor]
[h4 Where Defined]
`boost/graph/visitors.hpp`
@@ -39,7 +39,7 @@
[
[`PredecessorMap`]
[
- A [BoostWritablePropertyMap] where the key type and value type are of type
+ A [WritablePropertyMap] where the key type and value type are of type
`vertex_descriptor`.
]
]
@@ -95,7 +95,7 @@
``
]
[
- A convenience function for creating [boost_predecessor_recorder] instances.
+ A convenience function for creating [predecessor_recorder] instances.
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -10,16 +10,16 @@
template <class PropertyMap, class OutputIterator, class EventTag>
class property_writer;
-This is an [BoostEventVisitor] that can be used to output the property of a vertex
+This is an [EventVisitor] that can be used to output the property of a vertex
or edge at some event-point within an algorithm.
-The [boost_property_writer] class can be used with graph algorithms by wrapping it with
-the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor].
+The [property_writer] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [bfs_visitor] and [dfs_visitor].
Also, this event visitor can be combined with other event visitors using `std::pair` to
-form an [BoostEventVisitorList].
+form an [EventVisitorList].
[h4 Model Of]
-[BoostEventVisitor]
+[EventVisitor]
[h4 Where Defined]
`boost/graph/visitors.hpp`
@@ -30,7 +30,7 @@
[
[`PropertyMap`]
[
- A [BoostReadablePropertyMap] where the `key_type` is of type `vertex_descriptor`
+ A [ReadablePropertyMap] where the `key_type` is of type `vertex_descriptor`
of `edge_descriptor` (depending on the event tag) and the `value_type` type is
of the property is convertible to the `value_type` of the `OutputIterator`.
]
@@ -95,7 +95,7 @@
``
]
[
- A convenience function for creating [boost_property_writer] instances.
+ A convenience function for creating [property_writer] instances.
]
]
]
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-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -5,7 +5,7 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Reference Guide]
+[section Reference]
[section Graph Types]
[include undirected_graph.qbk]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -57,7 +57,7 @@
in the range \[0, `num_vertices(g)`).
*Requirements:* The `Graph` type must be a model of the
- [BoostIncidenceGraph] and [BoostVertexIndexGraph] concepts.
+ [IncidenceGraph] and [VertexIndexGraph] concepts.
]
]
[
@@ -66,7 +66,7 @@
The visitor object to the algorithm.
*Requirements:* This `Visitor` class must model the
- [BoostCliqueVisitor] class.
+ [CliqueVisitor] class.
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -10,17 +10,17 @@
template <class TimeMap, class TimeT, class EventTag>
class time_stamper;
-This is an [BoostEventVisitor] that can be used to "stamp" a time at some event-point
+This is an [EventVisitor] that can be used to "stamp" a time at some event-point
within an algorithm. An example of this is recording the discover or finish time of
a vertex during a graph search.
-The [boost_time_stamper] class can be used with graph algorithms by wrapping it with
-the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also,
+The [time_stamper] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [bfs_visitor] and [dfs_visitor]. Also,
this event visitor can be combined with other event visitors using `std::pair` to
-form an [BoostEventVisitorList].
+form an [EventVisitorList].
[h4 Model Of]
-[BoostEventVisitor]
+[EventVisitor]
[h4 Where Defined]
`boost/graph/visitors.hpp`
@@ -31,7 +31,7 @@
[
[`TimeMap`]
[
- A [BoostWritablePropertyMap] where the key type is of type `vertex_descriptor`
+ A [WritablePropertyMap] where the key type is of type `vertex_descriptor`
of `edge_descriptor` (depending on the event tag) and `TimeT` must be convertible
to the value type.
]
@@ -96,7 +96,7 @@
``
]
[
- A convenience function for creating [boost_time_stamper] instances.
+ A convenience function for creating [time_stamper] instances.
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk 2007-08-17 15:24:43 EDT (Fri, 17 Aug 2007)
@@ -118,8 +118,8 @@
function to access out-edges since it is guaranteed by every other graph class.
[h5 Model Of]
-[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
-[BoostMutableGraph], and [BoostPropertyGraph].
+[IncidenceGraph], [VertexListGraph], [EdgeListGraph], [AdjacencyGraph],
+[MutableGraph], and [PropertyGraph].
[h4 Template Parameters]
There are only three parameters to the `undirected_graph` class.
@@ -143,7 +143,7 @@
]
Additionally, the `undirected_graph` class provides a non-constant time implementation
-of the [BoostAdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
+of the [AdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
the concept.
[h4 Where Defined]
@@ -161,14 +161,14 @@
[`graph_traits<undirected_graph>::vertex_descriptor`]
[
The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
- models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ models the [Descriptor] and [NoConcept Hashable] concepts.
]
]
[
[`graph_traits<undirected_graph>::edge_descriptor`]
[
The type for the edge descriptors associated with the graph. The `edge_descriptor`
- models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ models the [Descriptor] and [NoConcept Hashable] concepts.
]
]
]
@@ -736,7 +736,7 @@
[h4 Rationale]
Unlike most graph classes in Boost.Graph, the `undirected_graph` does not model the
-[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+[MutablePropertyGraph] concept. The reason for this is that it is relatively
difficult (from a usability standpoint) to easily deduce the type to be passed as a
property when adding vertices and edges - but especially vertices.
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