|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-10 12:16:25
Author: asutton
Date: 2007-08-10 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 2007-08-10 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 2007-08-10 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 2007-08-10 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 2007-08-10 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 constant-time 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 2007-08-10 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
-two-dimensional array-like 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.
+two-dimensional 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 double-indexing 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 double-indexing 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 2007-08-10 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 2007-08-10 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 2007-08-10 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 out-degree
-is measured for its degree centrality.
-
-There are related two interpretations of degree centrality for directed graphs.
-When this measure is computed over the out-degree of a vertex, the measure is
-sometimes called /influence/. When the in-degree 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 out-degree.
+
+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 out-degree of a vertex, it is called
+/influence/. When the in-degree 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 (out-degree centrality) is blogger with
+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.
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 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.
[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 constant-time function. Replacing the default measure
-with a non-constant-time 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 edge-list format),
+computes the degree-centrality of each vertex, and prints them to standard
+output. The edge-list format is simply a comma-delimited 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 2007-08-10 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]]]
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