|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-26 13:45:27
Author: asutton
Date: 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
New Revision: 7174
URL: http://svn.boost.org/trac/boost/changeset/7174
Log:
Started porting reference documentation.
Wrote new reference docs for degree distributions - needs review
Imported connectivity header (and then erased everything within it)
Implemented prototype connectivity - needs to be bgl-parameterized
Fixed movie_stats to dump more information (distribution,
most-connected actor)
Added:
sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp | 77 ++++++++++++++++++++++++---------------
sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp | 6 +--
sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp | 6 +--
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk | 2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk | 2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk | 32 ++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp | 19 +++++++--
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 5 ++
sandbox/SOC/2007/graphs/libs/graph/test/index.cpp | 29 +++++++-------
sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp | 1
10 files changed, 120 insertions(+), 59 deletions(-)
Added: sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,23 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_CONNECTIVITY_HPP
+#define BOOST_GRAPH_CONNECTIVITY_HPP
+
+// std includes
+#include <vector>
+#include <map>
+
+// boost includes
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/connected_components.hpp>
+
+namespace boost
+{
+ // TODO: implement me!
+}
+
+#endif
Modified: sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -9,38 +9,55 @@
namespace boost
{
- template <
- typename BidirectionalGraph,
- typename Container
- >
- typename graph_traits<BidirectionalGraph>::degree_size_type
- degree_distribution(BidirectionalGraph &g, Container &dist)
+ template <typename Graph, typename Distribution>
+ void
+ degree_distribution(const Graph &g, Distribution &dist)
{
- typedef BidirectionalGraph Graph;
- typedef typename graph_traits<Graph>::degree_size_type Degree;
+ typedef typename graph_traits<Graph>::degree_size_type Degree;
- // stash the degree of each vertex into its bucket - degree 1
- // goes into index 1, degree 90 goes into index 90, etc.
- Degree max = 0;
- typename Graph::vertex_iterator i, j;
- for(tie(i, j) = vertices(g); i != j; ++i) {
- Degree d = degree(*i, g);
-
- // we may need to resize the array to accomodate the
- // incrementation of this degrees bucket.
- if(d >= dist.size()) {
- dist.resize(d + 1);
- }
-
- // remember the max degree that we've seen
- if(d > max) {
- max = d;
- }
-
- // increment the count in that bucket
- dist[d] += 1;
- }
- return max;
+ // stash the degree of each vertex into its bucket - degree 1
+ // goes into index 1, degree 90 goes into index 90, etc.
+ typename Graph::vertex_iterator i, j;
+ for(tie(i, j) = vertices(g); i != j; ++i) {
+ Degree d = degree(*i, g);
+
+ // we may need to resize the array to accomodate the
+ // incrementation of this degrees bucket. this only looks
+ // like its an inefficient resize, but its just fine with
+ // a vector for the distribution.
+ if(d >= dist.size()) {
+ dist.resize(d + 1);
+ }
+
+ // increment the count in that bucket
+ dist[d] += 1;
+ }
+ }
+
+
+ template <typename Graph, typename Histogram>
+ void
+ degree_histogram(const Graph &g, Histogram &hist)
+ {
+ typedef typename graph_traits<Graph>::degree_size_type Degree;
+
+ // stash the degree of each vertex into its bucket - degree 1
+ // goes into index 1, degree 90 goes into index 90, etc.
+ typename Graph::vertex_iterator i, j;
+ for(tie(i, j) = vertices(g); i != j; ++i) {
+ Degree d = degree(*i, g);
+
+ // we may need to resize the array to accomodate the
+ // incrementation of this degrees bucket. this only looks
+ // like its an inefficient resize, but its just fine with
+ // a vector for the distribution.
+ if(d >= hist.size()) {
+ hist.resize(d + 1);
+ }
+
+ // increment the count in that bucket
+ hist[d].push_back(*i);
+ }
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -609,11 +609,9 @@
template <class VP, class EP, class GP>
void
- renumber_vertex_indices(
- typename directed_graph<VP,EP,GP>::vertex_iterator i,
- directed_graph<VP,EP,GP>& g)
+ renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
{
- g.renumber_vertex_indices(i);
+ g.renumber_vertex_indices();
}
template <class VP, class EP, class GP>
Modified: sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -629,11 +629,9 @@
template <class VP, class EP, class GP>
void
- renumber_vertex_indices(
- typename undirected_graph<VP,EP,GP>::vertex_iterator i,
- undirected_graph<VP,EP,GP>& g)
+ renumber_vertex_indices(undirected_graph<VP,EP,GP>& g)
{
- g.renumber_vertex_indices(i);
+ g.renumber_vertex_indices();
}
template <class VP, class EP, class GP>
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -5,7 +5,7 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Adjacency List Reference]
+[section Adjacency List]
[warning
This reference is missing documentation for a number of associated types and
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,95 @@
+[/
+ / 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 Connected Components]
+
+ template <class Graph, class ComponentMap, class P, class T, class R>
+ typename property_traits<ComponentMap>::value_type
+ connected_components(const Graph &g, ComponentMap c,
+ const bgl_named_params<P,T,R>& params = ``/defaults/``);
+
+
+The connected_components() functions compute the connected components of an undirected
+graph using a DFS-based approach. A connected component of an undirected graph is a
+set of vertices that are all reachable from each other. If the connected components
+need to be maintained while a graph is growing the disjoint-set based approach of
+function `incremental_components()` is faster. For "static" graphs this DFS-based
+approach is faster \[8\].
+
+The output of the algorithm is recorded in the component property map, which will
+contain numbers giving the component number assigned to each vertex. This algorithm
+returns the total number of connected components in the graph.
+
+[heading Where Defined]
+`boost/graph/connected_components.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`const Graph& g`]
+ [
+ The /undirected/ graph for which connected components are being found.
+ This graph must be a model of VertexListGraph and Incidence Graph.
+ ]
+ ]
+ [
+ [out] [`ComponentMap c`]
+ [
+ The algorithm computes how many connected components are in the graph,
+ and assigning each component an integer label. The algorithm then records
+ which component each vertex in the graph belongs to by recording the
+ component number in the component property map. The ComponentMap type
+ must be a model of WritablePropertyMap. The value type shouch be an
+ integer type, preferably the same as the `vertices_size_type` of the
+ graph. The key type must be the graph's `vertex_descriptor` type.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VertexIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+]
+
+[heading Complexity]
+This algorithm runs in /O(V + E)/.
+
+[heading Notes]
+This algorithm will not compile if passed a /directed/ graph.
+
+[heading Examples]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,28 @@
+[/
+ / 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 Connectivity Measures]
+
+Reference for connectivity measures. Apparently, these are just going to be
+simple wrappers around connected_components or strong_components to provide
+some extra information. These might include:
+
+* `is_connected()`, `is_strongly_connected()`
+* `largest_connected_component()`, `largest_strong_component()`
+
+We might extend these for biconnected components also. Essentially, these
+functions take the component map computed by the connectivity stuff as
+an input and produce results. If the connectivity map isn't provided,
+we could compute it on the fly.
+
+[Examples]
+
+``
+ connected_comp
+``
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,756 @@
+[/
+ / 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 Directed Graph]
+This section provides detailed information about the `directed_graph` class,
+its associated types, member functions and non-member interface.
+
+[h4 Notation]
+The following notation is used in this documentation. The following type names
+are generally meant to mean the following:
+[table
+ [[Used Type] [Actual Type]]
+ [
+ [`directed_graph`]
+ [
+ `directed_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
+ arguments that correspond to user-defined or default verex properties,
+ edge properties, and graph properties.
+ ]
+ ]
+ [
+ [`vertex_descriptor`]
+ [`directed_graph<VP,EP,GP>::vertex_descriptor`]
+ ]
+ [
+ [`edge_descriptor`]
+ [`directed_graph<VP,EP,GP>::edge_descriptor`]
+ ]
+ [
+ [`vertex_iterator`]
+ [`directed_graph<VP,EP,GP>::vertex_iterator`]
+ ]
+ [
+ [`edge_iterator`]
+ [`directed_graph<VP,EP,GP>::edge_iterator`]
+ ]
+]
+
+Moreover, objects with the following names are generally expected to have the
+following types.
+
+[table
+ [[Object Name] [Type]]
+ [[`g`] [`directed_graph`]]
+ [[`u`, `v`] [`vertex_descriptor`]]
+ [[`e`] [`edge_descriptor`]]
+ [[`i`] [`vertex_iterator` or `edge_iterator`]]
+ [[`p`] [A property tag (usually a template parameter)]]
+ [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
+ [[`v`] [The value of a property (usually a template parameter)]]
+]
+
+[h4 Vertex and Edge Storage]
+The `directed` graph class has four distinct storage compontents: one for each
+of vertices, edges, out-edges per vertex, and in-edges per vertex. Each of these
+storage components uses a `std::list`. This is important to remember when
+considering the performance of oeprations on these graphs.
+
+Note that mutating (modifying) edge operations on a graph must operate on three
+different lists. For example, adding an edge to the graph will insert the edge
+or descriptors into the edge list, the out-edge list of the source vertex, and
+the in-edge list of the target vertex. These lists are accessible via the
+`edges(g)`, `out_edges(v,g)`, and `in_edges(v,g)` respectively.
+
+[h4 Descriptor and Iterator Stability]
+With the `directed_graph` class, descriptors and iterators remain stable after
+most operations. This is to say that removing a vertex or edge will not invalidate
+descriptors and iterators to other vertices or edges except for the edge or
+vertex that was actually removed.
+
+[h4 Vertex Indexing and Stability]
+The `directed_graph` class provides a built-in internal properties for vertex
+types, and will provide some degree of automated index management. Algorithms
+that use vertex indices generally assume that they are in the range
+\[0, `num_vertices(g)`). With the `directed_graph` class vertex indices will
+be in this continuous range until a vertex is removed from the graph. This is
+the only operation that invalidates vertex indices, but the vertices will need
+to be renumbered using the `renumber_vertex_indices()` function.
+
+[h4 Template Parameters]
+There are three parameters to the `directed_graph` class.
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`VertexProperties`]
+ [Specifies internal properties for vertices of the graph.]
+ [`no_property`]
+ ]
+ [
+ [`EdgeProperties`]
+ [Specifies internal properties for edges of the graph.]
+ [`no_property`]
+ ]
+ [
+ [`GraphProperties`]
+ [Specifies internal properties for the graph itself.]
+ [`no_property`]
+ ]
+]
+
+[h5 Model Of]
+VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
+
+[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 `graph_traits` or other template classes.
+For convenience these types have been grouped by purpose.
+
+[h5 Descriptor Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<directed_graph>::vertex_descriptor`]
+ [
+ The type for the vertex descriptors associated with the graph.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_descriptor`]
+ [
+ The type for the edge descriptors associated with the graph.
+ ]
+ ]
+]
+
+[h5 Iterator Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<directed_graph>::vertex_iterator`]
+ [
+ The type for iterators returned by `vertices()`. Verex iterators are
+ models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_iterator`]
+ [
+ The type for iterators returned by `edges()`. Edge iterators are
+ models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::out_edge_iterator`]
+ [
+ The type for iterators returned by `out_edges()`. Out-edge iterators
+ are models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::in_edge_iterator`]
+ [
+ The type for iterators returned by `in_edges()`. In-edge iterators
+ are models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::adjacency_iterator`]
+ [
+ The type for iterators returned by `adjacent_vertices`. Adjacency
+ iterators are models of the `BidirectionalIterator` concept.
+ ]
+ ]
+]
+
+[h5 Miscellaneous Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<directed_graph>::vertices_size_type`]
+ [The type used for dealing with the number of vertices in the graph.]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_size_type`]
+ [The type used for dealing with the number of edges in the graph.]
+ ]
+ [
+ [`graph_traits<directed_graph>::degree_size_type`]
+ [The type used for dealing with the number of edges incident to a vertex in the graph.]
+ ]
+ [
+ [`directed_graph::vertex_index_type`]
+ [The integral type representing vertex indices (generally `unsigned int`).]
+ ]
+ [
+ [
+ `property_map<directed_graph, Property>::type`
+
+ `property_map<directed_graph, Property>::const_type`
+ ]
+ [
+ The property map type for vertex or edge properties in the graph. The specific
+ property is specified by the `Property` template argument, and must match one of
+ the properties specified in the `VertexProperties` or `EdgeProperties` for the
+ graph.
+ ]
+ ]
+ [
+ [`graph_property<directed_graph, Property>::type`]
+ [
+ The value type for the graph property specified by the `Property` parameter.
+ `Property` must be one of the types in the `GraphProperties` template argument.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::directed_category`]
+ [
+ This is always `bidirectional_tag`, indicating that the graph supports in- and
+ out-edge operations.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_parallel_category`]
+ [
+ This is always `allow_parallel_edges_tag`, indicating that multiple edges
+ may be added between two vertices (i.e., graphs can be /multigraphs/).
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+directed_graph(const GraphProperties& p = GraphProperties())
+``
+ ]
+ [The default constructor creates a graph with no vertices or edges.]
+ ]
+ [
+ [
+``directed_graph(const directed_graph& g)
+``
+ ]
+ [The copy constructor creates a copy of the given graph `g`.]
+ ]
+ [
+ [
+``
+directed_graph(vertices_size_type n,
+ const GraphProperties& p = GraphProperties())
+``
+ ]
+ [The default constructor creates a graph with `n` vertices and no edges.]
+ ]
+ [
+ [
+``directed_graph& operator =(const directed_graph& g)
+``
+ ]
+ [Copies the edges and vertices of the graph `g`.]
+ ]
+]
+
+[h4 Non-member Functions]
+[h5 Non-member Accessors]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+std::pair<vertex_iterator, vertex_iterator>
+vertices(const directed_graph& g)
+``
+ ]
+ [Returns an iterator range providing access to the vertex list of `g`.]
+ ]
+ [
+ [
+``
+std::pair<edge_iterator, edge_iterator>
+edges(const directed_graph& g)
+``
+ ]
+ [Returns an iterator range providing access to the edge list of `g`.]
+ ]
+ [
+ [
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+out_edges(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the out-edges of
+ vertex `v` in the graph `g`.
+ ]
+ ]
+ [
+ [
+``
+std::pair<in_edge_iterator, in_edge_iterator>
+in_edges(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the in-edges of
+ vertex `v` in the graph `g`.
+ ]
+ ]
+ [
+ [
+``
+std::pair<adjacency_iterator, adjacency_iterator>
+adjacent_vertices(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the adjacenct vertices
+ of vertex `v` in the graph `g`. Note that this is functionally
+ equivalent to iterating over the targets of all out-edges of `v`.
+ ]
+ ]
+ [
+ [
+``
+vertices_size_type
+num_vertices(const directed_graph& g)
+``
+ ]
+ [Returns the number of vertices in the graph `g`.]
+ ]
+ [
+ [
+``
+edge_size_type
+num_edges(const directed_graph& g)
+``
+ ]
+ [Returns the number of edges the graph `g`.]
+ ]
+ [
+ [
+``
+degree_size_type
+degree(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the total degree of vertex `v` in the graph `g`. This is
+ functionally equivalent `out_degree(v,g) + in_degree(v,g)`.
+ ]
+ ]
+ [
+ [
+``
+degree_size_type
+out_degree(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the out-degree of vertex `v` in the graph `g`. In an
+ `directed_graph` this is equal to `in_degree(v, g)`.
+ ]
+ ]
+ [
+ [
+``
+degree_size_type
+in_degree(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the in-degree of vertex `v` in the graph `g`. In an
+ `directed_graph` this is equal to `out_degree(v, g)`.
+ ]
+ ]
+ [
+ [
+``
+vertex_descriptor
+vertex(vertices_size_type n
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the /nth/ vertex in the graph `g`. With directed graphs,
+ this method is /O(n)/. As such its use with this type of graph is
+ discouraged.
+ ]
+ ]
+ [
+ [
+``
+std::pair<edge_descriptor, bool>
+edge(vertex_descriptor u,
+ vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ If the edge /(u,v)/ is in `g`, then this function returns the
+ descriptor for the edge connecting `u` and `v` with boolean value
+ set to `true`. Otherwise, the boolean value is `false` and the
+ edge descriptor is invalid.
+ ]
+ ]
+ [
+ [
+``
+vertex_size_type
+get_vertex_index(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the vertex index of the given vertex descriptor v. Note
+ that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+ This function is an alias for `get(vertex_index,g,v)`.
+ ]
+ ]
+ [
+ [
+``
+vertex_size_type
+max_vertex_index(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the vertex index of the given vertex descriptor v. Note
+ that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+ This function is an alias for `get(vertex_index,g,v)`.
+ ]
+ ]
+]
+
+[h5 Non-member Modifiers]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+vertex_descriptor
+add_vertex(directed_graph& g)
+``
+ ]
+ [Adds a vertex to `g` and returns a descriptors for the new vertex.]
+ ]
+ [
+ [
+``
+void
+clear_vertex(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all in- and out-edges of `v`, but leaves `v` in the graph `g`.
+ This is functioanlly equivalent to invoking `remove_edge()` on all
+ in- or out-edges of `v`, invalidating descriptors and iterators that
+ reference edges incident to `v`.
+ ]
+ ]
+ [
+ [
+``
+void
+clear_out_edges(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all out-edges from vertex `v`, but does not remove the vertex
+ itself. This is functionally equivalent to calling `remove_edge()` for
+ all out-edges of `v`, invalidating any descriptors and iterators that
+ reference edges incident to that vertex.
+ ]
+ ]
+ [
+ [
+``
+void
+clear_in_edges(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all in-edges from vertex `v`, but does not remove the vertex
+ itself. This is functionally equivalent to calling `remove_edge()` for
+ all in-edges of `v`, invalidating any descriptors and iterators that
+ reference edges incident to that vertex.
+ ]
+ ]
+ [
+ [
+``
+vertex_descriptor
+remove_vertex(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes vertex `v` from the graph `g`. It is assumed that `v` has no
+ incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
+ before removing it.
+
+ Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
+ before calling this method, this operation will invalidate all vertex indices
+ in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
+ be renumbered using the `renumber_vertex_indices(g)` method. If possible,
+ prefer to remove groups of vertices at one time before renumbering since
+ renumbering is a /O(n)/ time operation.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_vertex_and_renumber_indices(vertex_iterator i,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes the vertex indicated by the iterator `i` from the graph `g`. Like
+ the `remove_vertex(v,g)` function, it is expected that `*i` have no
+ incident edges at the time of removal.
+
+ As indicated by the name, this method will also renumber vertex indices
+ after the removal of `*i`. This operation iterates over vertices after
+ `i`, decrementing their index by 1. If your program removes several
+ vertices at once, prefer to call several `remove_vertex(v,g)` methods,
+ followed by `renumber_vertices(g)` before using `g` in an algorithm.
+ ]
+ ]
+ [
+ [
+``
+void
+renumber_vertex_indices(directed_graph& g)
+``
+ ]
+ [
+ Renumbers all interior vertex indices such that each vertex has an index
+ in the range \[0, `num_vertices(g)`). Generally, this function needs to
+ be called after removing vertices and before invoking different graph
+ algorithms.
+ ]
+ ]
+ [
+ [
+``
+std::pair<edge_descriptor, bool>
+add_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
+ edge. For `directed_graph`s, the boolean value of the pair will always
+ be true.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes the edge /(u,v)/from the graph. This operation invalidates any
+ descriptors or iterators referencing the edge. Note that `u` and `v` must
+ be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
+ (with multiple edges between /(u,v)/, this mehtod will cause the removal of
+ all such edges connecting `u` and `v`.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(edge_descriptor e,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes the edge `e` from the graph. If multuple edges exist from
+ /(`source(e,g)`, `target(e,g)`)/, then this method will remove only
+ the single, specified edge.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(out_edge_iterator i,
+ directed_graph& g)
+``
+ ]
+ [
+ This is functionally equivalent to `remove_edge(*i, g)`.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge_if(Predicate p,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all edges from the graph that satisfy `predicate`. That is, if
+ `p()` returns true when applied to an edge, then that edge is removed.
+ The affect on descriptor and iterator is the same as that of invoking
+ `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+ [
+ [
+``
+template <class Predicate>
+void
+remove_out_edge_if(vertex_descriptor v,
+ Predicate p,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all edges out-edges from vertex`v` that satisfy `predicate`.
+ That is, if `p()` returns true when applied to an edge, then that edge
+ is removed. The affect on descriptor and iterator is the same as that
+ of invoking `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+ [
+ [
+``
+template <class Predicate>
+void
+remove_in_edge_if(vertex_descriptor v,
+ Predicate p,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all edges in-edges from vertex`v` that satisfy `predicate`.
+ That is, if `p()` returns true when applied to an edge, then that edge
+ is removed. The affect on descriptor and iterator is the same as that
+ of invoking `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+]
+
+[h5 Proprety Map Acessors]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class Property>
+property_map<directed_graph, Property>::type
+get(Property, directed_graph& g)
+``
+
+``
+template <class Property>
+property_map<directed_graph, Property>::const_type
+get(Property, const directed_graph& g)
+``
+ ]
+ [
+ Returns the property map object for the vertex property specified by the
+ type `Property`. This type must match one of the properties specified in
+ the `VertexProperties` template argument.
+ ]
+ ]
+ [
+ [
+``
+template <class Property, class Descriptor>
+typename
+ property_traits<
+ property_map<directed_graph, Property>::const_type
+ >::value_type
+get(Property,
+ const directed_graph& g,
+ Descriptor d)
+``
+ ]
+ [
+ Returns the property value specified by the type `Property` for either
+ the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
+ ]
+ ]
+ [
+ [
+``
+template <class Property, class Descriptor, class Value>
+void
+put(Property,
+ const directed_graph& g,
+ Descriptor d,
+ Value v)
+``
+ ]
+ [
+ Sets the property value denoted by the type `Property` for either edge
+ or vertex descriptor `d` to the given value `v`.
+ ]
+ ]
+ [
+ [
+``
+template <class GraphProprety>
+typename graph_property<directed_graph, GraphProperty>::type&
+get_property(directed_graph& g, GraphProperty)
+``
+
+``
+template <class GraphProprety>
+const typename graph_property<directed_graph, GraphProperty>::type&
+get_property(const directed_graph& g, GraphProperty)
+``
+ ]
+ [
+ Returns the graph property specified by the type `GraphProperty` for
+ the graph `g`.
+ ]
+ ]
+ [
+ [
+``
+template <class GraphProprety, class Value>
+void
+set_property(const directed_graph& g, GraphProperty, Value v)
+``
+ ]
+ [
+ Sets the graph proeprty specified by the type `GraphProperty` to
+ the given value `v`. Note that `GraphProperty` must be one of
+ the properties in the `GraphProperties` template argument.
+ ]
+ ]
+]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,128 @@
+[/
+ / 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 <class Graph, class DistributionMap>
+ void degree_distribution(const Graph &g, DistributionMap& dist);
+
+ template <class Graph, class DistributionMap>
+ void in_degree_distribution(const Graph &g, DistributionMap& dist);
+
+ template <class Graph, class DistributionMap>
+ void out_degree_distribution(const Graph &g, DistributionMap& dist);
+
+
+ template <class Graph, class HistogramMap>
+ void degree_histogram(const Graph &g, HistogramMap& dist);
+
+ template <class Graph, class HistogramMap>
+ void in_degree_histogram(const Graph &g, HistogramMap& dist);
+
+ template <class Graph, class HistogramMap>
+ void out_degree_histogram(const Graph &g, HistogramMap& dist);
+
+The degree distribution functions compute statistical distributions of the degrees
+of vertices in a graph. In addition to the degree distribution, different algorithms
+allow for the computation in-degree and out-degree distributions.
+
+The histogramming functions compute historgrams, associating each vertex in
+the graph with its degree in the distribution.
+
+[heading Where Defined]
+`boost/graph/degree_distribution.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`const Graph& g`]
+ [
+ The graph object for which the distribution will be computed. For
+ `degree_distributions()` and `in_degree_distribution()`, `g` must
+ be a model of a BidirectionalGraph. For `out_degree_distribution()`,
+ `g`, must model the IncidenceGraph concept.
+ ]
+ ]
+ [
+ [out] [`DistributionMap& dist`]
+ [
+ The distribution parameter maps instances of degrees (numerically)
+ to the number of vertices in the graph that exhibit that degree.
+
+ The distribution output parameter has a number of strict typ requirements.
+ First, it must be a model of the Sequence concept, specifically providing
+ a `resize()` member function. They key (or index) type of this parameter
+ should be the same as `degree_size_type` of the graph. Finally, the
+ `value_type` of this method should be an integer type (preferrably
+ unsigned). It is recommended to use `std::vector<degree_size_type>` for
+ this parameter.
+ ]
+ ]
+ [
+ [out] [`HistogramMap& hist`]
+ [
+ The histogram parameter maps instances of degrees (numerically) to the
+ set of vertices that exhibit that degree.
+
+ The histogram parameter has fairly stringent type requirements due to
+ its structure. First, the parameter must model the Sequence concept,
+ providing a `resize()` member function. Seocnd, the key (index) of
+ the type should be the same as `degree_size_type` of the graph. The
+ `value_type` of this is required to model the BackInsertionSequence,
+ and the `value_type` of that /must/ be the same as the `vertex_descriptor`
+ of the graph parameter.
+ ]
+ ]
+]
+
+[heading Complexity]
+The complexity of this function is /O(V)/.
+
+[heading 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.
+
+For the distribution parameter, we recommend `std::vector<size_t>`. This satisfies
+all the requirements. For the histogram, we recommend using a `std::vector<Sequence<Vertex> >`
+where `Sequence` is one of `std::list`, `std::vector`, `std::deque`, or `std::queue`. The
+choice doesn't make much difference except that a `std::list` will require more allocations,
+but a `std::vector` will require more space. The `Vertex` type must be
+`graph_traits<Graph>::vertex_descriptor`.
+
+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 non-zero value.
+
+[heading Examples]
+The first example show how to compute and print the degree distribution. Each
+element in the returned distribution corresponds to the number of instances
+of
+
+ 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::list<vertex_type> vertex_list;
+
+ std::vector<vertex_list> hist;
+ degree_histogram(g, hist);
+ cout << get_vertex_index(hist.back().back()) << "\n";
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,116 @@
+[/
+ / 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 Strongly Connected Components]
+
+ template <class Graph, class ComponentMap, class P, class T, class R>
+ typename property_traits<ComponentMap>::value_type
+ strong_components(const Graph &g, ComponentMap c,
+ const bgl_named_params<P,T,R>& params = ``/defaults/``);
+
+The `strong_components()` functions compute the strongly connected components of a
+directed graph using Tarjan's algorithm based on DFS \[41\].
+
+The output of the algorithm is recorded in the component property map, which will
+contain numbers giving the component number assigned to each vertex. This algorithm
+returns the number of strongly connected components in the graph.
+
+[heading Where Defined]
+`boost/graph/strong_components.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`const Graph& g`]
+ [
+ The /directed/ graph for which connected components are being found.
+ This graph must be a model of VertexListGraph and Incidence Graph.
+ ]
+ ]
+ [
+ [out] [`ComponentMap c`]
+ [
+ The algorithm computes how many connected components are in the graph,
+ and assigning each component an integer label. The algorithm then records
+ which component each vertex in the graph belongs to by recording the
+ component number in the component property map. The ComponentMap type
+ must be a model of WritablePropertyMap. The value type shouch be an
+ integer type, preferably the same as the `vertices_size_type` of the
+ graph. The key type must be the graph's `vertex_descriptor` type.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [util] [`root_map(RootMap root_map)`]
+ [
+ This is used by the algorithm to record the candidate root vertex for each
+ vertex. By the end of the algorithm, there is a single root vertex for each
+ component and `get(root_map, v)` returns the root vertex for whichever
+ component vertex `v` is a member. The `RootMap` must be a ReadWritePropertyMap,
+ where the key type and the value type are the vertex descriptor type of the
+ graph.
+
+ *Default* An iterator_property_map created from a `std::vector` of
+ `vertex_descriptor`s of size `num_vertices(g)` and using the `index_map`
+ for accessing root vertices.
+ ]
+ ]
+ [
+ [util] [`discover_time_map(TimeMap time_map)`]
+ [
+ This is used by the algorithm to keep track of the DFS ordering of the vertices.
+ The `TimeMap` must be a model of ReadWritePropertyMap and its value type must
+ be an integer type. The key type must be the vertex descriptor type of the graph.
+
+ *Default* An iterator_property_map created from a `std::vector` of integers
+ of size `num_vertices(g)` and using the `index_map` for accessing root vertices.
+ ]
+ ]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VertexIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+]
+
+[heading Complexity]
+This algorithm runs in /O(V + E)/.
+
+[heading Notes]
+This algorithm will not compile if passed a /directed/ graph.
+
+[heading Examples]
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -5,7 +5,7 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Undirected Graph Reference]
+[section Undirected Graph]
This section provides detailed information about the `undirected_graph` class,
its associated types, member functions and non-member interface.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -7,8 +7,40 @@
[section Reference Guide]
+[section Graph Types]
[include ref_undirected_graph.qbk]
[include ref_directed_graph.qbk]
[include ref_adjacency_list.qbk]
+[endsect]
+
+[section Algorithms]
+[section Core Algorithms]
+[endsect]
+
+[section Shortest Path Algorithms]
+[endsect]
+
+[section Minimum Spanning Tree Algorithms]
+[endsect]
+
+[section Connectivity Algorithms]
+[include ref_connected_components.qbk]
+[include ref_strong_components.qbk]
+[include ref_connectivity.qbk]
+[endsect]
+
+[section Maximum Flow Algorithms]
+[endsect]
+
+[section Sparse Matrix Ordering Algorithms]
+[endsect]
+
+[section Layout Algorithms]
+[endsect]
+
+[section Graph Measures]
+[include ref_distributions.qbk]
+[endsect]
+[endsect]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -10,12 +10,17 @@
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/degree_distribution.hpp>
+#include <boost/graph/connectivity.hpp>
#include "movies.hpp"
using namespace std;
using namespace boost;
+typedef vector<graph_traits<Graph>::degree_size_type> Distribution;
+typedef list<Vertex> VectorList;
+typedef vector<VectorList> Histogram;
+
int
main(int argc, char *argv[])
{
@@ -25,12 +30,18 @@
// build the movie graph from std input
build_movie_graph(cin, g, actors);
- // compute the degree distribution
- vector<size_t> dist;
+ Distribution dist;
+ Histogram hist;
degree_distribution(g, dist);
- copy(dist.begin(), dist.end(),
- ostream_iterator<size_t>(cout, " "));
+ degree_histogram(g, hist);
+
+ cout << "vertices: " << num_vertices(g) << "\n";
+ cout << "edges: " << num_edges(g) << "\n";
+ cout << "degree distribution: ";
+ copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
cout << "\n";
+ cout << "max degree: " << (dist.size() - 1) << "\n";
+ cout << "most-connected actor: " << g[hist.back().back()].name << "\n";
return 0;
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -18,3 +18,8 @@
: range.cpp
: <include>../../../
;
+
+exe misc
+ : misc.cpp
+ : <include>../../../
+ ;
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/test/index.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/index.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/index.cpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -18,43 +18,44 @@
int test_main(int, char*[])
{
+ static const size_t N = 5;
Graph g;
- Vertex v[5];
+ Vertex v[N];
IndexMap x = get(vertex_index, g);
// build up the graph
- for(int i = 0; i < 5; ++i) {
- v[i] = add_vertex(g);
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
}
// after the first build, we should have these conditions
- BOOST_CHECK(max_vertex_index(g) == 5);
- for(int i = 0; i < 5; ++i) {
- BOOST_CHECK(get_vertex_index(v[i], g) == i);
+ BOOST_CHECK(max_vertex_index(g) == N);
+ for(size_t i = 0; i < N; ++i) {
+ BOOST_CHECK(get_vertex_index(v[i], g) == i);
}
// remove some vertices and re-add them...
- for(int i = 0; i < 5; ++i) remove_vertex(v[i], g);
+ for(size_t i = 0; i < N; ++i) remove_vertex(v[i], g);
BOOST_CHECK(num_vertices(g) == 0);
- for(int i = 0; i < 5; ++i) {
+ for(size_t i = 0; i < N; ++i) {
v[i] = add_vertex(g);
}
// before renumbering, our vertices should be off by
- // about 5...
+ // about N...
BOOST_CHECK(max_vertex_index(g) == 10);
- for(int i = 0; i < 5; ++i) {
- BOOST_CHECK(get_vertex_index(v[i], g) == 5 + i);
+ for(size_t i = 0; i < N; ++i) {
+ BOOST_CHECK(get_vertex_index(v[i], g) == N + i);
}
- // renumber them.
+ // renumber vertices
renumber_vertex_indices(g);
// and we should be back to the initial condition
- BOOST_CHECK(max_vertex_index(g) == 5);
- for(int i = 0; i < 5; ++i) {
+ BOOST_CHECK(max_vertex_index(g) == N);
+ for(size_t i = 0; i < N; ++i) {
BOOST_CHECK(get_vertex_index(v[i], g) == i);
}
Added: sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -0,0 +1,93 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <vector>
+#include <tr1/unordered_map>
+#include <boost/utility.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/connected_components.hpp>
+#include <boost/graph/strong_components.hpp>
+
+using namespace std;
+using namespace boost;
+
+namespace std
+{
+ namespace tr1
+ {
+ template <>
+ struct hash<boost::detail::edge_desc_impl<undirected_tag, void*> >
+ : public std::unary_function<
+ boost::detail::edge_desc_impl<undirected_tag, void*>,
+ std::size_t>
+ {
+ typedef boost::detail::edge_desc_impl<undirected_tag, void*> Edge;
+ std::size_t operator ()(Edge e)
+ {
+ std::tr1::hash<Edge::property_type*> hasher;
+ return hasher(e.get_property());
+ }
+ };
+ }
+}
+
+static void undirected_test()
+{
+ typedef undirected_graph<> Graph;
+ typedef Graph::vertex_descriptor Vertex;
+ typedef Graph::edge_descriptor Edge;
+ typedef tr1::unordered_map<Vertex, int> component_map_type;
+ typedef associative_property_map<component_map_type> component_map;
+
+ const size_t N = 5;
+ undirected_graph<> g;
+
+ vector<Vertex> verts(N);
+ for(size_t i = 0; i < N; ++i) {
+ verts[i] = add_vertex(g);
+ }
+ add_edge(verts[0], verts[1], g);
+ add_edge(verts[1], verts[2], g);
+ add_edge(verts[3], verts[4], g);
+
+ component_map_type mapping(num_vertices(g));
+ component_map comps(mapping);
+ size_t c = connected_components(g, comps);
+
+ cout << c << "\n";
+
+ Graph::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << *i << "\t" << comps[*i] << "\n";
+ }
+}
+
+static void directed_test()
+{
+ typedef directed_graph<> Graph;
+ typedef Graph::vertex_descriptor Vertex;
+ typedef Graph::edge_descriptor Edge;
+ typedef tr1::unordered_map<Vertex, int> component_map_type;
+ typedef associative_property_map<component_map_type> component_map;
+
+ Graph g;
+ Vertex u = add_vertex(g);
+ Vertex v = add_vertex(g);
+ add_edge(u, v, g);
+
+ component_map_type mapping(num_vertices(g));
+ component_map comps(mapping);
+ strong_components(g, comps);
+}
+
+int
+main()
+{
+ undirected_test();
+ directed_test();
+}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp 2007-06-26 13:45:25 EDT (Tue, 26 Jun 2007)
@@ -1,4 +1,3 @@
-
// (C) Copyright Andrew Sutton 2007
//
// Use, modification and distribution are subject to the
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