
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070810 12:16:25
Author: asutton
Date: 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
New Revision: 38571
URL: http://svn.boost.org/trac/boost/changeset/38571
Log:
Lots of documentary changes.
Actually finished degree centrality (pending review)
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk  13 ++
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk  15 ++
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk  104 ++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk  81 +++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk  5
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk  209 +++++++++++++++++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk  2
9 files changed, 313 insertions(+), 120 deletions()
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 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 29,7 +29,7 @@
[
The result type of the computation. Note that unlike
`graph_traits<G>::degree_size_type`, the `degree_type` is not
 required to be numerice.
+ required to be numeric.
]
]
]
@@ 48,4 +48,15 @@
]
]
+[heading C++0x]
+
+ concept DegreeMeasure<M>
+ {
+ typename Graph;
+ typename Vertex;
+ typename M::degree_type;
+
+ degree_type M::operator(Vertex v, const Graph& g)
+ };
+
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 22,7 +22,7 @@
[heading Notes]
Note that because both model the [SgiLessThanComparable] concept, they can be used as
keys in any associative container modeling the [SgiAssociativeContainer] concepte
+keys in any associative container modeling the [SgiAssociativeContainer] concept
(e.g., `std::map`, `std::set`, etc).
[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 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 56,10 +56,23 @@
[`m(d, g)`]
[`M::result_type`]
[
 Invoke the measure on the sum of distances `d`, with respect
+ Invoke the measure on the sum distance `d`, with respect
to the graph `g`. This returns the result as type `result_type`.
+ Note that in many computations `d` is given as the sum of distances
+ from one vertex to all others in the graph and may be infinite.
]
]
]
+[heading C++0x]
+
+ concept DistanceMeasure<M>
+ {
+ typename Graph;
+ typename M::distance_type;
+ typename M::result_type;
+
+ result_type M::operator(distance_type, const Graph&);
+ };
+
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 6,17 +6,9 @@
/]
[section Property Map]
The [BoostPropertyMap] concept provides additional requirements for other Boost
property map objects. Specifically, this concept requires that property maps
be constructed in a syntactically similar manner.

[note
Of the two most common property maps (iterator and associative), only the
associative property map can satisfy these requirements. The only way to guarantee
that generically cretead exterior property maps are correctly adapted to their
underlying containers is to declare them using the [boost_exterior_vertex_property]
or [boost_exterior_edge_property] types.
]
+The [BoostPropertyMap] concept is a refinement of the concepts in the Boost.PropertyMap
+library this concept requires that property maps modeling this concept are required
+to be constructed with a graph object.
[heading Refinement Of]
[BoostReadWritePropertyMap]
@@ 27,8 +19,9 @@
[[Expression] [Description]]
[[M] [A type modeling the [BoostPropertyMap] concept.]]
[[m] [An object of type `M`.]]
 [[c] [An object whose type models the [SgiContainer] concept.]]
 [[k] [A key to the property map.]]
+ [[c] [An object whose type models the [SgiRandomAccessContainer] concept.]]
+ [[k] [An object of the property map's `key_type`.]]
+ [[x] [An object of the property map's `value_type`.]]
]
[heading Expressions]
@@ 47,54 +40,67 @@
This constructor is mainly used to convey type information to
generic functions since it cannot function without the container.
 *Postconditions:* `m[k]` is invalid.
+ *Postconditions:* `m[k]`, `get(m, k)`, and `put(m, k, x)` have
+ undefined behavior (i.e., are likely to crash the program).
]
]
[
 [Container Contructor]
+ [Property Graph Constructor]
[
 `M m(c);`

 `M m = c;`
+ `M m(c, g);`
 `M(c)`
+ `M(c, g)`
]
[]
[
 Construct a property map `m` over the container `c`.
+ Construct a property map `m` over the container `c` with reference
+ to the graph `g`.
+
+ *Requirements*: The container type of `c` must be a model of the
+ [SgiRandomAccessContainer] concept.
+
+ *Postconditions:* if `k` is a valid vertex or edge descriptor of `g`
+ then `m[k]`, `get(m, k)`, and `put(m, k, x)` are all valid operations,
+ that either return or set the value `x` associated with the key `k`.
+
+ *Complexity:* The property map is constructed in constant time.
]
]
]
[heading Notes]
This concept is imoprtant for two reasons. First, it provides a common way
of declaring and constructing property maps, especially when using the exterior
property declartive facilities. Second, it provides a mechanism for "slicing"
a [BoostPropertyMatrix] using row access. The following example shows how
both features can be used in a template function:

 template<typename Graph>
 void shortest_paths(const Graph&)
 {
 // Define some useful types
 typedef typename exterior_vertex_property<Graph, int> Property;
 typedef typename Property::matrix_type Matrix;
 typedef typename Property::map_type Map;
 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

 // Get the first vertex for later
 Vertex u = *vertices(g).first;

 // Construct a matrix and a map on the first row
 Matrix matrix(num_vertices(g));
 Map map = matrix[u]; // Note: map[v] == matrix[u][v]

 // Run a shortest paths algorithm.
 dijkstra_shortest_paths(g, matrix);

 BOOST_ASSERT(matrix[u][u] == 0); // distance to self == 0
 BOOST_ASSERT(map[u] == 0); // same as above
 BOOST_ASSERT(matrix[u][u] == map[u]); // just making sure
 }
+This concept exists primarily to help enforce best practice for declaring and
+using exterior properties. Note that none of the property maps implemented
+in the Boost.PropertyMap library satisfy the requirements of this concept.
+The only type that does satisfy these requirements is the `map_type` of the
+[boost_exterior_property] template.
+
+This concept is generally not used to impose requirements on property maps
+passed to generic graph algorithms.
+
+Also note that because the container `c` over which the property map is constructed
+must be a model of the [SgiRandomAccessContainer] type. This is a fairly stringent
+requirement, but if satisfied (e.g., via a `std::vector`) implies the property
+map implements constanttime property access.
+
+[heading Example]
+
+ typedef undirected_graph<> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+
+ Graph g;
+ // add vertices and edges
+
+ typedef exterior_property<Graph, Vertex, std::size_t> DistanceProperty;
+ typedef DistanceProperty::container_type DistanceContainer;
+ typedef DistanceProperty::map_type DistanceMap;
+
+ DistanceContainer distances(num_verticse(g), 0);
+ DistanceMap dm(distances, g);
+
+ Vertex v = *vertices(g).first;
+ put(dm, v, 3); // set v's distance to 3
+ get(dm, v); // returns 3
+ dm[v]; // same as above, returns 3
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 7,28 +7,30 @@
[section Property Matrix]
The [BoostPropertyMatrix] concept requires types that model it to allow
twodimensional arraylike access to its values using descriptor objects. Types
that model this concepts are typically nested containers that use the vertex
or edge desctipors of a graph to access the elements of the matrix.
+twodimensional array access to its values using descriptors. Types that model
+this concepts are typically nested containers that use the vertex or edge
+desctipors of a graph to access the elements of the matrix.
Note that the term "matrix" can be misleading since types that model this
concept are not required to have a "square" structure. The term "matrix" applies
to the use of doubleindexing to access its elements (i.e., m[u][v]).

[note
The two most common possible models of this type (nested vectors and unordered maps)
cannot model this concept due to initialization requirements. The best way to
ensure that a matrix models this type is to use the [boost_exterior_vertex_property]
or [boost_exterior_edge_property] types.
]
+concept are not necessarily required to have a "square" memory structure. The
+term "matrix" applies to the use of doubleindexing to access its elements
+(i.e., m[u][v]).
+
+Despite the relative simplicity of this concept, it should be noted that
+types such as nested vectors cannot implicitly model this concept due to the
+additional type requirements of the `property_matrix_types` template. Hoever,
+that template can be specialized such that the requirements are met. In general,
+however, it is far easier to use the `matrix_type` of the [boost_exterior_property]
+template to declare types that model his concept.
[heading Notation]
The following expressions are used within this document:
[table
[[Expression] [Description]]
[[M] [A type modeling the [BoostPropertyMatrix] concept.]]
 [[m] [An object of type `M`]]
 [[n] [An unsigned integer]]
+ [[m] [An object of type `M`.]]
+ [[n] [An unsigned integer.]]
+ [[g] [An object whose type is a model of the [BoostGraph] concept.]]
]
[heading Associated Types]
@@ 58,7 +60,21 @@
[Container Type]
[`property_matrix_traits<M>::container_type`]
[
 The nested container that implements storage of the value type.
+ The nested container that stores the values of each column in the
+ matrix.
+
+ *Requirements:* The `container_type` is a [SgiContainer] such that
+ the `value_type` of the container is the same as the `value_type`
+ of the matrix. The container must be [NoConcept Idexable] with the
+ index type being the same as the `key_type` of the matrix.
+ ]
+ ]
+ [
+ [Map Type]
+ [`property_matrix_traits<M>::map_type`]
+ [
+ The type of property map that can be constructed over the `container_type`
+ of the matrix.
*Requirements:* The `container_type` is a [SgiContainer] such that
the `value_type` of the container is the same as the `value_type`
@@ 70,9 +86,8 @@
[Matrix Type]
[`property_matrix_traits<M>::matrix_type`]
[
 The type of the matrix.

 *Requirements:* The `matrix_type` must be the same type as `M`.
+ The type of the underlying matrix. This may not be the same type
+ as `M`.
]
]
]
@@ 81,29 +96,33 @@
[table
[[Name] [Expression] [Result Type] [Description]]
[
 [Fill Contructor]
 []
+ [Fill Constructor]
[
 `M m(n)`
+ `M m(n, g)`
 `M(n)`
+ `M(n, g)`
]
+ []
[
 Contstruct the matrix with `n` elements. After construction,
+ Contstruct the matrix with `nxn` elements. After construction,
accessing elements with the range defined by the square matrix
is guaranteed to succeed.
 *Postcondition:* `m[k][k]` is valid if `k` is mapped to an element
 within the matrix.
+ *Preconditions:* `n >= num_vertices(g)`.
+
+ *Postcondition:* If `i` and `j` are valid vertex or edge descriptors
+ of `g`, then `m[i][j]` returns the value associated with the descriptor
+ pair.
]
]
[
[Element Access]
+ [`m[u][v]`]
[
`property_matrix_traits<M>::value_type&`
+
`const property_matrix_traits<M>::value_type&`
]
 [`m[u][v]`]
[
Returns the element corresponding to the pair `u`, `v` in the
matrix.
@@ 117,16 +136,16 @@
]
[
[Row Access]
+ [`m[u]`]
[
 `property_matrix_traits<M>::container_type&`
 `const property_matrix_traits<M>::container_type&`
+ An [StdIndexable] type.
]
 [`m[u]`]
[
 Returns the row (or nested container) associated with the key `u`.
+ Returns the row associated with the key `u`.
*Requirements:* The key `u` must be the same as the `key_type`
 for the matrix.
+ for the matrix. The return type is guaranteed to be indexable with
+ the key type `k`.
*Preconditions:* The key `u` must be valid vertex or edge descriptor
of the graph to which the matrix applies.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 39,8 +39,6 @@
'''
]


[include sgi_concepts.qbk]
[include boost_concepts.qbk]
[include boost_reference.qbk]
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 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 58,8 +58,9 @@
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,
or as the result of many breadth first searches (if the graph is unweighted).
+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
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 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 8,33 +8,55 @@
[section Degree Centrality]
template <typename Graph, typename CentralityMap>
 void degree_centrality(const Graph& g, CentralityMap cent)
+ 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)
+ void degree_centrality(const Graph& g, CentralityMap cent, Measure measure);
 template <typename Graph>
+ template <typename Graph, typename Vertex>
typename graph_traits<Graph>::degree_size_type
 vertex_degree_centrality(const Graph& g,
 typename graph_traits<Graph>::vertex_descriptor v)
+ vertex_degree_centrality(const Graph& g, Vertex v);
 template <typename Graph, typename Measure>
+ template <typename Graph, typename Vertex, typename Measure>
typename Measure::degree_type
 vertex_degree_centrality(const Graph& g,
 typename graph_traits<Graph>::vertex_descriptor v,
 Measure measure)
+ vertex_degree_centrality(const Graph& g, Vertex v, Measure measure);
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 the network. Degree centrality is computed over the number of
connections that a vertex has. For undirected graphs, the degree centrality of
a vertex is typically equivalent to its degree. For directed graphs the outdegree
is measured for its degree centrality.

There are related two interpretations of degree centrality for directed graphs.
When this measure is computed over the outdegree of a vertex, the measure is
sometimes called /influence/. When the indegree is considered, the measure is
called /prestige/.
+or important to a network. Degree centrality of a vertex is computed over the number
+of connections (adjacent vertices) of that vertex. This definition varies for
+undirected and directed graphs. For undirected graphs, the degree centrality of a
+vertex is equivalent to its degree. For directed graphs it is equivalent to either
+its in or outdegree.
+
+Consider the social network represented by an undirected graph in Figure 1.
+
+[figure
+ images/reference/social_network.png
+ *Figure 1.* A network of friends.
+]
+
+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 (five friends each), whereas Laurie
+has the lowest degree centrality since she has only one friend.
+
+For directed graphs, there are related two interpretations of degree centrality.
+When degree centrality is measured over the outdegree of a vertex, it is called
+/influence/. When the indegree is measured, the measure is called /prestige/.
+Consider the information network represented by the directed graph in Figure 2.
+
+[figure
+ images/reference/information_network.png
+ *Figure 2.* A network of informational websites.
+]
+
+This graph represents links between information websites, presumably regarding a
+specific topic. The most influential (outdegree centrality) is blogger with
+three outgoing links while wikipedia is the least influential. The most prestigous
+(indegree centrality) is wikipedia with five incoming references. The least
+prestigous websites are myspace, blogger, and blogspot each of which have no
+incoming links.
This module provides two generic functions for measuring degree centrality.
The first function, `degree_centrality()` computes this measure for each vertex
@@ 43,10 +65,21 @@
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 alternate /measure/
functors. These funtors are called to actually compute the degree centraltiy
of a vertex. For exmaple, it is possible to redefine the detault notion of
degree centrality for a directed graph to return /prestige/ instead of /influence/.
+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.
+
+ 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&);
+
+The `influence_measure` returns the outdegre of a vertex and provides the
+default computation for degree centrality of both directed and undirected
+graphs. The `prestige_measure` returns the indegree of a vertex.
[heading Where Defined]
`boost/graph/degree_centrality.hpp`
@@ 59,14 +92,20 @@
[
The graph object for which the degree centralities will be computed.
 *Requirements:* The `Graph` type must be a model of the
 [BoostIncidenceGraph] concept.
+ *Requirements:* The `Graph` type must be a model of the [BoostIncidenceGraph]
+ 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.
]
]
[
 [required, in] [`vertex_descriptor v`]
+ [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.
]
]
[
@@ 104,16 +143,120 @@
the `Measure`.
[heading Complexity]
The default measure is a constanttime function. Replacing the default measure
with a nonconstanttime function will affect the complexity of the computations.
+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 `vertex_degree_centrality()` returns in /O(M)/ where /M/ is a measure of
+a vertex. 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.
+
+[heading Example (Degree Centrality)]
+[import ../../examples/degree_centrality.cpp]
+
+This example reads a graph from standard input (in a simple edgelist format),
+computes the degreecentrality of each vertex, and prints them to standard
+output. The edgelist format is simply a commadelimited listing of vertex pairs.
+For example:
+
+[pre
+Scott,Bill
+Frank,Anne
+]
The `degree_centrality()` function is ['O(n * O(measure))]. This is linear by
default.
+To make typing easier, we define some aliases for the types used in this program
+in the global scope. Specifically, we define names for the graph and vertex types,
+types used to record the centralities of a social network, and a mapping of name
+to vertex (which is used to help build the graph).
+[declare_social_network]
+Note that the value type of the centrality property is `size_t` (an unsigned
+integer). This type must be the same as the `degree_size_type` of `Graph`, which
+is required to be an unsigned integer.
+
+The graph and a `VertexMap` object are declared in the main program as:
+[setup_social_network]
+The graph object `g` is the data structure which this program will construct
+and measure. The vertex map `verts` is used to ensure that vertices are uniquely
+associated with a name in the social network.
+
+The program starts by reading the input and buiding the graph.
+[build_social_network]
+This snippet uses the `add_named_vertex()` to ensure that each vertex added
+to the graph corresponds to exactly one name in the input data. The `add_named_vertex()`
+function is not part of the Boost.Graph library, but provided as a helper function
+for many of these examples. See ... for its implementation.
+
+The program can now measure the degree centrality of the graph or social network.
+[measure_social_network]
+The `CentralityContainer` is the underlying container for the abstract `CentralityMap`
+accessor. It is constructed to be the same size as the number of vertices in the
+graph, and the centrality map is constructed over the container with respect to the
+graph `g`. The `degree_centrality()` function is called to populate the centrality
+map with measured values.
+
+Finally, we iterate over the vertices, printing the degree centrality of each
+person in the network.
+[print_social_network]
+
+If given the `social_network.graph` file as input, the program will produce the
+following output:
+
+[pre
+Scott: 4
+Jill: 2
+Mary: 2
+Bill: 2
+Josh: 2
+Frank: 5
+Laurie: 1
+Anne: 2
+Howard: 2
+]
The `vertex_degree_centrality()` is ['O(O(measure))]. This is constant by
default.
+[heading Example (Influence and Prestige)]
+[import ../../examples/influence_prestige.cpp]
[heading Example]
Write an example.
+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.
+
+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<Person> 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.
+[measure_information_network]
+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.
+
+Finally, print the results for each vertex in the graph.
+[print_information_network]
+
+If given the `information_network.graph` file as input, the program will produce
+the following output where the second column is influence and the third is prestige:
+
+[pre
+myspace 1 0
+digg 2 2
+blogger 3 0
+slahsdot 0 1
+wikipedia 0 5
+slashdot 2 2
+blogspot 2 0
+bbc 1 1
+]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk 20070810 12:16:23 EDT (Fri, 10 Aug 2007)
@@ 40,3 +40,5 @@
[template SgiPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
[template SgiMonoid[] [@http://www.sgi.com/tech/stl/Monoid.html Monoid]]
+
+[template StdIndexable[] [link boostgraph [^Indexable]]]
BoostCommit 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