
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070720 09:35:17
Author: asutton
Date: 20070720 09:35:16 EDT (Fri, 20 Jul 2007)
New Revision: 7489
URL: http://svn.boost.org/trac/boost/changeset/7489
Log:
Writing docs
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk  6
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk  17 +++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk  173 +++++++++++++++++++
3 files changed, 104 insertions(+), 92 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk 20070720 09:35:16 EDT (Fri, 20 Jul 2007)
@@ 44,7 +44,7 @@
[figure
images/reference/connected_components_after.png
 Figure 1. Components found after running [boost_connected_components]
+ [*Figure 1.] Components found after running [boost_connected_components]
]
Assume that we have stored each vertex into a vector, `v`, such that `v[i]`
@@ 94,7 +94,7 @@
[table
[[Type] [Parameter] [Description]]
[
 [required, in] [`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
@@ 104,7 +104,7 @@
]
]
[
 [required, out] [`Components _components`]
+ [required, out] [`Components& _components`]
[
The components parameter provides storage for the assignment of
vertices to components. The `ComponentMap` parameter must be a
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk 20070720 09:35:16 EDT (Fri, 20 Jul 2007)
@@ 6,7 +6,24 @@
/]
[section Measures of Distances]
+This section contains references for a suite of functions related to the
+distance metrics on a graph.
+ template <typename Graph, typename DistanceMap>
+ typename property_traits<DistanceMap>::value_type
+ geodesic_distance(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ DistanceMap dist)
+
+ template <typename Graph, typename DistanceMap>
+ inline double
+ mean_geodesic_distance(const Graph& g, DistanceMap dist)
+
+ template <typename Graph, typename DistanceMap, typename T>
+ T
+ mean_geodesic_distance(const Graph& g,
+ DistanceMap dist,
+ const T& dummy)
[endsect]
\ No newline at end of file
Modified: 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/distributions.qbk 20070720 09:35:16 EDT (Fri, 20 Jul 2007)
@@ 6,49 +6,87 @@
/]
[section Degree Distributions]
 void degree_distribution(
 _graph,
 _distribution = not_given(),
 _out_distribution = not_given(),
 _in_distribution = not_given())
+ template <typename Graph, typename Histogram>
void degree_histogram(
 _graph,
 _histogram = not_given(),
 _out_histogram = not_given(),
 _in_histogram = not_given())

The degree distribution function compute distributions of the degrees
of vertices in a graph. A distribution is mapping of an observable property
to the number of occurences of that property. In this context, the observable
property is the degree of a vertex (or in and outdegree), which are in
the range \[0, /max{degree(v)}/\] Where /max{degree(v)}/ is the maximum degree
of any vertex in a graph /G/. Therefore, the output distribution is mapping
of vertex degree to its number of occurences in a graph.

This histogram functions are closely related to the degree distribution functions.
However, instead of computing a mapping from vertex degree to the number of
vertices, the histogram maps vertex degree to the /set of vertices/ that exhibit
that degree. This is very useful if you want to quickly find all vertices with
degree 0, or find the vertex with the highest degree.

In both of these functions, the computation of distribution or histogram
depends on which optional parameters are passed to the function. If called as:

 degree_distribution(g, _distribution = dist, _in_distribution = in_dist);

The algorithm will compute both the degree destribution and indegree distributions.
Note that for undirected graphs, all three distributions or histograms will be
identical.
+ 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);
[h5 Where Defined]
+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`
[h5 Parameters]
+[heading Parameters]
[table
[[Type] [Parameter] [Description]]
[
 [required, in] [`_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
@@ 60,11 +98,11 @@
[
[optional, out]
[
 `_distribution`
+ Histogram& `_histogram`
 `_out_distribution`
+ Histogram& `_out_histogram`
 `_in_distribution`
+ Histogram& `_in_histogram`
]
[
The distribution parameters maps instances of vertex degree to the
@@ 79,68 +117,32 @@
implying that no computation is performed.
]
]
 [
 [optional, out]
 [
 `_histogram`

 `_out_histogram`

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

 The histogram output parameter must be a model of both [SgiSequence]
 and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
 distribution must be the same as `degree_size_type`. Additionally `value_type`
 must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).

 If not supplied, these parameters assume the default value of `not_given`,
 implying that no computation is performed.
 ]
 ]
]
[h5 Return Value]
Both functions return `void`.
+This function does not return a value.
[h5 Complexity]
The time complexity of all these functions is /O(V)/.
The space complexity for the distributions functisons is /O(max{degree(v)})/ where
/max{degree(v)}/ is the maxmimum degree of all vertices in a graph /G/.

The space complexity for the histogram functions is /O(V + max{degree(v)})/.

[h5 Notes]
Because a graph may be a multigraph, there is no determinable upper bound on the
size of the distribution or histogram parameters. As such they are required to
be dynamically resized during the execution of the algorithm.
+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_type>::degree_size_type>

where `graph_type` is the type of the `_graph` parameter. This satisfies the type
requirements of the algorithms, and provides exceptional performance at the cost
of extra memory overhead.

The recommended type for the histogram parameters is:

 std::vector<std::vector<graph_traits<graph_type>::vertex_descriptor> >

Although this will consume more memory (due to the overhead of vector resizing),
it may perform better than using `std::list` to store vertices of the same degree.
This is because the `std::list::size()` function is not required to return in
constant time.
+ 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;
@@ 164,12 +166,5 @@
degree_histogram(g, hist);
cout << get_vertex_index(hist.back().back()) << "\n";
[h5 Rationale]
The use of these functions varies somewhat from typical use of named parameters
where default values are simply used to supply default information. Here, they
are used to control functionality. It should also be noted that if no parameters
are supplied, this algorithm still runs in linear time. However, there is no
additional overhead for not supplying a parameter because operations on the
`not_given` type are noopped (they are instantiated as empty functions).
[endsect]
\ No newline at end of file
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