
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070614 13:07:11
Author: asutton
Date: 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
New Revision: 7044
URL: http://svn.boost.org/trac/boost/changeset/7044
Log:
Added a rationale document in quickbook.
Implemented vertex and edge counting for the undirected graph class.
Also, fixed the property map typing issue I've been having. Undirected
graphs now work like normal adjacency lists. Examples have not been
updated, so this build will probably break.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk
sandbox/SOC/2007/graphs/libs/graph/test/
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk  2 +
sandbox/SOC/2007/graphs/libs/graph/examples/imdb/imdb.cpp  15 ++++++++
sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp  7 +
sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp  11 ++++
sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp  11 +
5 files changed, 15 insertions(+), 31 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
@@ 46,5 +46,5 @@
[include guide.qbk]

+[include rationale.qbk]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
@@ 0,0 +1,98 @@
+ [/
+ / 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 Design Rationale]
+At the moment this is a somewhat rambling document that describes reasons why
+certain code is written the way that it is. Hopefully, it will one day become
+a much more organized collection of excuses.
+
+[h3 Complexity of Size Functions]
+It turns out  and some people probably knew this already  that the `list::size()`
+function is not required to be run in constant time. Under GCC's STL it's *linear*.
+This is a huge "gotcha" if you're using lists and calling the `size()` function
+repeatedly  as I was in my IMDb example. In fact, I was calling it every time
+a vertex was added to a 3 million vertex graph to generate vertex indices. Doing
+the math, it looks like I managed to write a single line of code that /looked/
+constant time, but was in fact O(n^2). Wow.
+
+After a discussion with Jeremey Siek, we decided that the easiest way to address
+this was to manually maintain the number of vertices and edges inside the new
+`undirected_graph` and `directed_graph` classes.
+
+To implement this, I made every mutable graph concept method a member function that
+was called by its nonmember counterpart. This means I don't have to have lots of
+ugly friend functions, and the logic is nicely encapsulated.
+
+[h3 Vertex Indices]
+Since the `undirected_graph` and `directed_graph` use list storage selectors rather
+than vectors, I've been having to manually build vertex indices for my examples.
+Contrast this with almost every other example, where using vector storage results
+in vertex indices being automatically generated (since they correlate directly
+with the vertex_descriptor). My interim solution had been to simply add a member
+variable to each bundled property that acted as the index  works great.
+
+However, this is somewhat counterintuitive for new developers. Indices shouldn't
+necessarily be something that new programmers really need to worry about. An
+alternative would be to define a hidden index property for vertices and then
+use the `VertexProperties` template argument as the property parameter for
+that property. Like this:
+
+ property<vertex_index_t, int, VertexProperties>
+
+Works great.
+
+[h4 Automatic Indexing and Reindexing]
+If the `undirected_graph` and `directed_graph` classes have implicit index
+properties, It would make sense that we try to automatically manage those indices.
+This is actually relatively trivial at this point since we already have member
+functions responsible for maintaining the number of vertices and edges. We can
+add index management to those methods.
+
+Unfortunately, automatic indexing only really works well if we never remove
+vertices or edges from the graph. Because indices are assigned in a monotonically
+increasing fashion, removing a vertex will create gaps in the assignment, and
+probably wreak havoc with any algorithms requiring indices in the range
+\[0, num_vertices(g)).
+
+One solution to this is to provide a new function, renumber_vertices() or something
+similar. This simply iterates over vertices in the graph, assigning new monotonically
+increasing values to them. This obviously runs in linear time, but has the nice
+property of creating a continuous index for working with external properties in
+different algorithms.
+
+Another solution might be to provide another new method max_vertex_index() that
+returns the highest indexed vertex so algorithms could be designed to operate
+on vectors of size \[0, max_vertex_index(g)). There are two problems with this
+approach.
+
+# Noncontinuous indexing (1, 3, 5) as the result of removes() will cause "gaps"
+in a vector used as an external property. Algorithms need to be aware that accessing
+a "gap" is probably some kind of boundary error since they're refering to a vertex
+that doesn't really exist. A special "does not exist" property value may need to
+be created in some cases.
+# Related to the problem above, these "gaps" introduce memory overhead. Over time,
+external property maps can grow and potentially consume significant amounts of
+memory. Consider the following:
+
+ for( ; ; ) {
+ vertex_descriptor v = add_vertex(g);
+ vector<color> colors(max_vertex_index(g));
+ remove_vertex(v);
+ }
+
+Although the example is entirely contrived, it shows how the size of a graph might
+remain stable over time while an external property map might not.
+
+Interestingly, we actually have some of the tools for managing these problems
+available to us. Specifically, we can use the renumber_vertices() method to
+a) create a continous numbering and b) reset the max_vertex_index() to
+num_vertices(). This could be managed either externally by the user or, we
+could implement some heuristic such when `max_vertex_index > 2 * num_vertices`
+we automatically renumber vertices on the next vertex removal (or something
+like that).
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/imdb/imdb.cpp
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/examples/imdb/imdb.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/imdb/imdb.cpp 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
@@ 57,8 +57,8 @@
struct VertexProperty;
struct EdgeProperty;
// typedef undirected_graph<VertexProperty, EdgeProperty> Graph;
typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
+typedef undirected_graph<VertexProperty, EdgeProperty> Graph;
+// typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
typedef Graph::vertex_descriptor Vertex;
typedef Graph::edge_descriptor Edge;
@@ 107,10 +107,11 @@
};
// property maps
typedef property_map<Graph, int VertexProperty::*>::type VertexIndexMap;
typedef property_map<Graph, int VertexProperty::*>::type VertexDistanceMap;
typedef property_map<Graph, Vertex VertexProperty::*>::type VertexParentMap;
typedef property_map<Graph, int EdgeProperty::*>::type EdgeWeightMap;
+typedef property_map<Graph::graph_type, vertex_index_t>::type VertexIndexMap;
+
+typedef property_map<Graph::graph_type, int VertexProperty::*>::type VertexDistanceMap;
+typedef property_map<Graph::graph_type, Vertex VertexProperty::*>::type VertexParentMap;
+typedef property_map<Graph::graph_type, int EdgeProperty::*>::type EdgeWeightMap;
RolePtr
parse_movie(const string& str)
@@ 383,7 +384,7 @@
// start accumulating property maps for dijkstra's algorithm.
// these references never change even though the contents of them might.
 VertexIndexMap indices = get(&VertexProperty::index, g);
+ VertexIndexMap indices = get(vertex_index, g);
VertexDistanceMap distances = get(&VertexProperty::distance, g);
VertexParentMap parents = get(&VertexProperty::parent, g);
EdgeWeightMap weights = get(&EdgeProperty::weight, g);
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
@@ 68,7 +68,6 @@
build_movie_graph(cin, g, actors);
// get the bacon number map associated with the graph
 ActorIndexMap indices = get(&Actor::index, g);
ActorDistanceMap dists = get(&Actor::distance, g);
// pick a starting vertex (kevin bacon, obviously) and set his
@@ 78,11 +77,7 @@
// run a breadthfirst search on the graph and record
// the kevin bacon numbers for each actor
 breadth_first_search(g, kevin,
 // named parameters
 vertex_index_map(indices)
 .visitor(record_actor_distances(dists))
 );
+ breadth_first_search(g, kevin, visitor(record_actor_distances(dists)));
// just run over the vertices and print the back numbers
Graph::vertex_iterator i, j;
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
@@ 51,20 +51,17 @@
// These property maps index information in the Actor and Movie
// structures, respectively. They are used to access specific pieces
// of information inside the graph.
typedef boost::property_map<Graph::type, int Actor::*>::type ActorIndexMap;
typedef boost::property_map<Graph::type, int Actor::*>::type ActorDistanceMap;
typedef boost::property_map<Graph::type, Vertex Actor::*>::type ActorParentMap;
typedef boost::property_map<Graph::type, std::string Actor::*>::type ActorNameMap;
+typedef boost::property_map<Graph::graph_type, int Actor::*>::type ActorDistanceMap;
+typedef boost::property_map<Graph::graph_type, Vertex Actor::*>::type ActorParentMap;
+typedef boost::property_map<Graph::graph_type, std::string Actor::*>::type ActorNameMap;
typedef boost::property_map<Graph::type, unsigned Movie::*>::type MovieWeightMap;
typedef boost::property_map<Graph::type, std::string Movie::*>::type MovieNameMap;
+typedef boost::property_map<Graph::graph_type, std::string Movie::*>::type MovieNameMap;
// we use an extra map to help dynamically populate the graph.
// this maps actor names to the vertices that they're inserted as
typedef std::map<std::string, Vertex> ActorMap;
void build_movie_graph(std::istream &, Graph&, ActorMap&);
void build_vertex_index_map(Graph&, ActorIndexMap &);
Vertex find_actor_vertex(const Graph&, const ActorMap&, const std::string&);
#endif
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp 20070614 13:07:10 EDT (Thu, 14 Jun 2007)
@@ 90,21 +90,12 @@
return 1;
}
 // Get the index map
 // WARNING: The current method for implementing this is highly unstable
 // if any of the vertices are removed  basically, you'd have to reassign
 // the indices after a sequence of removals.
 ActorIndexMap indices = get(&Actor::index, g);

// The predeceessor map records, for the vertex at each index, the
// predecessor (or parent) in the shortestpath tree. By iterating
// from predecessor to predecessor, we can find the shortest path
ActorParentMap parents = get(&Actor::parent, g);
 breadth_first_search(g, u,
 vertex_index_map(indices)
 .visitor(record_actor_parents(parents))
 );
+ breadth_first_search(g, u, visitor(record_actor_parents(parents)));
// print the movies in which the actors appear by iterating over
// the elements in the predecessor map
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