[Boost-commit] svn:boost r7044

From: asutton_at_[hidden]
Date: 2007-06-14 13:07:11

Author: asutton
Date: 2007-06-14 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	2007-06-14 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	2007-06-14 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 non-member 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 counter-intuitive 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 Re-indexing]
+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.
+
+# Non-continuous 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	2007-06-14 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	2007-06-14 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 breadth-first 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	2007-06-14 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	2007-06-14 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 shortest-path 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