
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070801 10:44:27
Author: asutton
Date: 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
New Revision: 38336
URL: http://svn.boost.org/trac/boost/changeset/38336
Log:
Rewrote degree distribution docs as degree centrality
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk
 copied, changed from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk  3
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk  8 +
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk  1
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk  213 +++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk  2
6 files changed, 91 insertions(+), 138 deletions()
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 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 12,12 +12,10 @@
[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]

[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]

[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
@@ 46,4 +44,5 @@
[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]]]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,51 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section Degree Measure]
+The [BoostDegreeMeasure] 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] [An object of type `M`.]]
+ [[G] [A type modeling the [BoostGraph] concept.]]
+ [[g] [An object of type `G`.]]
+ [[v] [An object of type `graph_traits<G>::vertex_descriptor`.]]
+]
+
+[heading Associated Types]
+[table
+ [[Name] [Type] [Description]]
+ [
+ [Degree Type]
+ [`M::degree_type`]
+ [
+ The result type of the computation. Note that unlike
+ `graph_traits<G>::degree_size_type`, the `degree_type` is not
+ required to be numerice.
+ ]
+ ]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Function Call]
+ [`m(v, g)`]
+ [`M::degree_type`]
+ [
+ Invoke the measure on the vertex `v`, with respect
+ to the graph `g`. This returns the result as type `degree_type`.
+ ]
+ ]
+]
+
+[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 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 16,7 +16,8 @@
[[M] [A type modeling the [BoostDistanceMeasure] concept.]]
[[m] [An object of type `M`.]]
[[d] [An object of type `M::distance_type`.]]
 [[g] [An object whose type models the [BoostGraph] concept.]]
+ [[G] [A type modeling the [BoostGraph] concept.]]
+ [[g] [An object of type `G`.]]
]
[heading Associated Types]
@@ 26,7 +27,10 @@
[Distance Type]
[`M::distance_type`]
[
 The type used to measure distances in graphs.
+ The type used to measure distances in graphs. The `distance_type`
+ is typically derived from the value type of a distance map or
+ the edgeweight type of a graph type `G`. However, this is not
+ required.
*Requirements:* The `distance_type` must be a model of the
[BoostNumericValue] concept.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 13,6 +13,7 @@
[include numeric_value.qbk]
[include property_map.qbk]
[include property_matrix.qbk]
+[include degree_measure.qbk]
[include distance_measure.qbk]
[endsect]
Copied: sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk (from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk)
==============================================================================
 /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 5,166 +5,115 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
[section Degree Distributions]
+[section Degree Centrality]
 template <typename Graph, typename Histogram>
 void degree_histogram(
 const Graph& _graph,
 Histogram& _histogram = ``['nothing]``,
 Histogram& _out_histogram = ``['nothing]``,
 Histogram& _in_histogram = ``['nothing]``)

The degree histogram function computes /histograms/ of the degrees
of vertices in a graph. A histogram is table that records the frequency
of occurence of some event. With regards to this function, the computed
histograms record the occurence of each degree of vertices in the graph.

Specifically, each `_histogram` parameter describes a sequence of possible
vertexdegrees in the graph and his size \[0, /max{degree(v,g)} + 1}\] where
/max{degree(v,g)}/ is the maximum degree of any vertex in `_graph`. In this
sequence, the ['i[super th]] element corresponds to the number of vertices
in `_graph` with degree /i/.

[figure
 images/reference/distributions_undirected.png
 [*Figure 1.] A simple undirected graph.
]

Consider the example in Figure 1. The assignment of frequencies (number of
vertices with degree /i/) in the histogram will be:

 _histogram[0] == 0;
 _histogram[1] == 1; // vertex 0
 _histogram[2] == 0;
 _histogram[3] == 5; // vertices 1, 2, 3, 4, 5

For directed graphs, it is also possible to compute histograms for both the in
and outdegrees of the vertices of a graph.

[figure
 images/reference/distributions_directed.png
 [*Figure 2.] A simple directed graph.
]

For Figure 2, the in and outdegree distributions will be:

 _in_histogram[0] == 1; _out_histogram[0] == 0;
 _in_histogram[1] == 2; _out_histogram[1] == 4;
 _in_histogram[2] == 3; _out_histogram[2] == 2;

Note that the cumulative degree histogram for an directed graph is the
same as it would be if we treated edges as undirected. The cumulative
histogram for the graph in Figure 2 is:

 _histogram[0] == 1;
 _histogram[0] == 0;
 _histogram[0] == 5;

Note that computing the in or out degree for an undirected graph will yield
the same histogram as the cumulative.

[note
The /histogram/ is different than a /distribution/, which is commonly used as a
synonym for /probability distribution/. The probability of a histogram
can be computed by dividing each element of the `_histogram` by the number
of vertices in the graph.
]
+ template <typename Graph, typename CentralityMap>
+ void degree_centrality(const Graph& g, CentralityMap cent)
In both of these functions, the computation of histograms depends on the
parameters passed to the function. For example, if called as:
+ template <typename Graph, typename CentralityMap, typename Measure>
+ void degree_centrality(const Graph& g, CentralityMap cent, Measure measure)
 degree_distribution(g, _histogram = hist, _in_histogram = in_hist);

The algorithm will compute both the degree histogram and indegree histogram,
but not the outdegree histogram. If not arguments are supplied, the algorithm
performs no computations (but does so in linear time).
+ template <typename Graph>
+ typename graph_traits<Graph>::degree_size_type
+ vertex_degree_centrality(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v)
+
+ template <typename Graph, typename Measure>
+ typename Measure::degree_type
+ vertex_degree_centrality(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor 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/.
+
+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 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/.
[heading Where Defined]
`boost/graph/degree_distribution.hpp`
+`boost/graph/degree_centrality.hpp`
[heading Parameters]
[table
[[Type] [Parameter] [Description]]
[
 [required, in] [`const Graph& _graph`]
+ [required, in] [`const Graph& graph`]
[
 The graph object for which the distribution will be computed. If
 the `_distribution` or `_in_distribution` arguments are supplied
 when calling this function then `_graph` must be a model of
 [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
 then `_graph` must be a model of [BoostIncidenceGraph].
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostIncidenceGraph] concept.
]
]
[
 [optional, out]
+ [required, in] [`vertex_descriptor v`]
[
 Histogram& `_histogram`

 Histogram& `_out_histogram`

 Histogram& `_in_histogram`
+ The vertex descriptor for which the degree centrality is computed.
]
+ ]
+ [
+ [required, out] [`CentralityMap cent`]
[
 The distribution parameters maps instances of vertex degree to the
 number of observed vertices in the graph with that degree.
+ The property map that contains the degree centralities of all vertices
+ in a graph after calling the `degree_centrality()` function.
 These parameters must model both the [SgiSequence] and
 [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
 distribution must be the same as `degree_size_type`. The `value_type` must
 be integral (preferably unsigned).
+ *Requirements:* The `CentralityMap` type must be a model of the
+ [BoostWritablePropertyMap] 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.
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The `measure` parameter allows the caller to override the default
+ computation of degree centrality for a vertex.
 If not supplied, these parameters assume the default value of `not_given`,
 implying that no computation is performed.
+ *Requirements:* The `Measure` type must be a model of the
+ [BoostDegreeMeasure] concept. The `degree_type` of `Measure` must
+ be the same as the `value_type` of the `CentralityMap` type.
]
]
]
[h5 Return Value]
This function does not return a 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`.
[h5 Complexity]
The time complexity of all these functions is /O(V)/.

[h5 Notes]
Because a graph may be a multigraph, there is no determinable upper bound on the
size of the histogram parameters. As such they are required to be dynamically resized
during the execution of the algorithm.

The recommended type for the distribution parameters is:

 std::vector<graph_traits<Graph>::degree_size_type>

Note that if `dist` is the name of the output distribution after a call to
`degree_distribution()` then the maximum degree is `dist.size()  1`. The
minimum degree corresponds to the index in `dist` with the first nonzero value.

[h5 Examples]
[note
 Expand these a bit... Perhaps show computations based on the previous.
]

The first example show how to compute and print the degree distribution.

 undirected_graph<> g;
 // add vertices and edges to g

 std::vector<size_t> dist;
 degree_distribution(g, dist);
 copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));

The following example shows how to access the vertex (or vertices) with the maximum
degree by using the `degree_histogram()` algorithm. This prints the index of that
vertex.

 undirected_graph<> g;
 // add vertice and edges to g
+The default measure is a constanttime function. Replacing the default measure
+with a nonconstanttime function will affect the complexity of the computations.
 typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
 typedef std::vector<vertex_type> vertex_vector;
+The `degree_centrality()` function is ['O(n * O(measure))]. This is linear by
+default.
 std::vector<vertex_vector> hist;
 degree_histogram(g, hist);
 cout << get_vertex_index(hist.back().back()) << "\n";
+The `vertex_degree_centrality()` is ['O(O(measure))]. This is constant by
+default.
+[heading Example]
+Write an example.
[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ 1,170 +0,0 @@
[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section Degree Distributions]

 template <typename Graph, typename Histogram>
 void degree_histogram(
 const Graph& _graph,
 Histogram& _histogram = ``['nothing]``,
 Histogram& _out_histogram = ``['nothing]``,
 Histogram& _in_histogram = ``['nothing]``)

The degree histogram function computes /histograms/ of the degrees
of vertices in a graph. A histogram is table that records the frequency
of occurence of some event. With regards to this function, the computed
histograms record the occurence of each degree of vertices in the graph.

Specifically, each `_histogram` parameter describes a sequence of possible
vertexdegrees in the graph and his size \[0, /max{degree(v,g)} + 1}\] where
/max{degree(v,g)}/ is the maximum degree of any vertex in `_graph`. In this
sequence, the ['i[super th]] element corresponds to the number of vertices
in `_graph` with degree /i/.

[figure
 images/reference/distributions_undirected.png
 [*Figure 1.] A simple undirected graph.
]

Consider the example in Figure 1. The assignment of frequencies (number of
vertices with degree /i/) in the histogram will be:

 _histogram[0] == 0;
 _histogram[1] == 1; // vertex 0
 _histogram[2] == 0;
 _histogram[3] == 5; // vertices 1, 2, 3, 4, 5

For directed graphs, it is also possible to compute histograms for both the in
and outdegrees of the vertices of a graph.

[figure
 images/reference/distributions_directed.png
 [*Figure 2.] A simple directed graph.
]

For Figure 2, the in and outdegree distributions will be:

 _in_histogram[0] == 1; _out_histogram[0] == 0;
 _in_histogram[1] == 2; _out_histogram[1] == 4;
 _in_histogram[2] == 3; _out_histogram[2] == 2;

Note that the cumulative degree histogram for an directed graph is the
same as it would be if we treated edges as undirected. The cumulative
histogram for the graph in Figure 2 is:

 _histogram[0] == 1;
 _histogram[0] == 0;
 _histogram[0] == 5;

Note that computing the in or out degree for an undirected graph will yield
the same histogram as the cumulative.

[note
The /histogram/ is different than a /distribution/, which is commonly used as a
synonym for /probability distribution/. The probability of a histogram
can be computed by dividing each element of the `_histogram` by the number
of vertices in the graph.
]

In both of these functions, the computation of histograms depends on the
parameters passed to the function. For example, if called as:

 degree_distribution(g, _histogram = hist, _in_histogram = in_hist);

The algorithm will compute both the degree histogram and indegree histogram,
but not the outdegree histogram. If not arguments are supplied, the algorithm
performs no computations (but does so in linear time).

[heading Where Defined]
`boost/graph/degree_distribution.hpp`

[heading Parameters]
[table
 [[Type] [Parameter] [Description]]
 [
 [required, in] [`const Graph& _graph`]
 [
 The graph object for which the distribution will be computed. If
 the `_distribution` or `_in_distribution` arguments are supplied
 when calling this function then `_graph` must be a model of
 [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
 then `_graph` must be a model of [BoostIncidenceGraph].
 ]
 ]
 [
 [optional, out]
 [
 Histogram& `_histogram`

 Histogram& `_out_histogram`

 Histogram& `_in_histogram`
 ]
 [
 The distribution parameters maps instances of vertex degree to the
 number of observed vertices in the graph with that degree.

 These parameters must model both the [SgiSequence] and
 [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
 distribution must be the same as `degree_size_type`. The `value_type` must
 be integral (preferably unsigned).

 If not supplied, these parameters assume the default value of `not_given`,
 implying that no computation is performed.
 ]
 ]
]

[h5 Return Value]
This function does not return a value.

[h5 Complexity]
The time complexity of all these functions is /O(V)/.

[h5 Notes]
Because a graph may be a multigraph, there is no determinable upper bound on the
size of the histogram parameters. As such they are required to be dynamically resized
during the execution of the algorithm.

The recommended type for the distribution parameters is:

 std::vector<graph_traits<Graph>::degree_size_type>

Note that if `dist` is the name of the output distribution after a call to
`degree_distribution()` then the maximum degree is `dist.size()  1`. The
minimum degree corresponds to the index in `dist` with the first nonzero value.

[h5 Examples]
[note
 Expand these a bit... Perhaps show computations based on the previous.
]

The first example show how to compute and print the degree distribution.

 undirected_graph<> g;
 // add vertices and edges to g

 std::vector<size_t> dist;
 degree_distribution(g, dist);
 copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));

The following example shows how to access the vertex (or vertices) with the maximum
degree by using the `degree_histogram()` algorithm. This prints the index of that
vertex.

 undirected_graph<> g;
 // add vertice and edges to g

 typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
 typedef std::vector<vertex_type> vertex_vector;

 std::vector<vertex_vector> hist;
 degree_histogram(g, hist);
 cout << get_vertex_index(hist.back().back()) << "\n";


[endsect]
\ No newline at end of file
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 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 107,7 +107,7 @@
for large graphs, this difference is negligible.
[heading Where Defined]
`boost/graph/closeness_centrality.hpp`
+`boost/graph/mean_geodesic.hpp`
[heading Parameters]
[table
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 20070801 10:44:25 EDT (Wed, 01 Aug 2007)
@@ 66,7 +66,7 @@
[endsect]
[section Graph Measures]
[include distributions.qbk]
+[include degree_centrality.qbk]
[include closeness_centrality.qbk]
[include mean_geodesic.qbk]
[include eccentricity.qbk]
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