[Boost-commit] svn:boost r48731 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: . test

Subject: [Boost-commit] svn:boost r48731 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: . test
From: asutton_at_[hidden]
Date: 2008-09-11 08:22:13

Author: asutton
Date: 2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
New Revision: 48731
URL: http://svn.boost.org/trac/boost/changeset/48731

Log:
Rewriting directory structure
Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile
      - copied, changed from r48390, /sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/adv_search.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/bfs.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/dfs.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/di.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/in_edge_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/incidence_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/map.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/out_edge_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/properties_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/propmaps.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/props.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/read.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/search.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/set.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/square.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_es.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_props.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_verts.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/typestr.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/un.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertices_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/visitors.cpp   (contents, props changed)
Removed:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
   sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/desc.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/dfs.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/in_edge_traits.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/properties_traits.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/read.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/search.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/vertices_traits.hpp
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot      |    10 +---------                              
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile |     9 +++++++++                               
   2 files changed, 10 insertions(+), 9 deletions(-)

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,24 +0,0 @@
-
-# exe set : set.cpp : <include>../../ <include>/usr/local/include ;
-# exe map : map.cpp : <include>../../ <include>/usr/local/include ;
-# exe props : props.cpp : <include>../../ <include>/usr/local/include ;
-# exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
-# exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
-
-exe test_verts : test_verts.cpp ;
-exe test_props : test_props.cpp ;
-exe test_incs : test_incs.cpp ;
-exe test_outs : test_outs.cpp ;
-exe test_ins : test_ins.cpp ;
-exe test_es : test_es.cpp  ;
-
-exe un : un.cpp ;
-exe di : di.cpp ;
-
-exe propmaps : propmaps.cpp ;
-
-# exe bfs : bfs.cpp ;
-# exe dfs : dfs.cpp ;
-# exe search : search.cpp ;
-exe adv_search : adv_search.cpp ;
-exe vis : visitors.cpp ;
\ No newline at end of file

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -3,7 +3,7 @@
 import path ;
 
 # Import a newer version of g++ and configure it for C++0x support.
-using gcc : 4.4 : g++-4.4 : <cxxflags>-std=c++0x ;
+using gcc : 4.4 : g++-4.4 : <cxxflags>--`std=c++0x ;
 
 # Define the boost root for this and nested projects. This shouold try to pull
 # a specification from the build.
@@ -29,11 +29,3 @@
         ECHO "Warning: couldn't find BOOST_ROOT in" $(boost-root) ;
     }
 }
-
-# Build all subrojects using g++-4.4
-project graphs
-    : requirements
-        <toolset>gcc-4.4
-        <include>$(boost-root)
-        <include>../..
-    ;

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,131 +0,0 @@
-
-#include <iostream>
-#include <fstream>
-#include <queue>
-
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-#include <boost/graphs/algorithms/breadth_first.hpp>
-
-#include "typestr.hpp"
-#include "read.hpp"
-
-using namespace std;
-
-struct edge_printer : bfs_visitor
-{
-    template <typename Graph, typename Edge>
-    void tree_edge(Graph const& g, Edge e)
-    {
-        typedef typename Graph::vertex_descriptor Vertex;
-        Vertex u = e.source();
-        Vertex v = e.target();
-        cout << "(" << g[u] << g[v] << ") ";
-    }
-};
-
-template <typename Graph, typename Walk>
-void iterate(Graph& g, Walk& walk)
-{
-    typedef typename Walk::vertex_descriptor Vertex;
-
-    typedef algorithm_iterator<Walk> Iterator;
-    typedef pair<Iterator, Iterator> Range;
-
-    Range rng(walk.begin(), walk.end());
-    for( ; rng.first != rng.second; ++rng.first) {
-        Vertex u = rng.first->source();
-        Vertex v = rng.first->target();
-        cout << "(" << g[u] << g[v] << ") ";
-    }
-    cout << endl;
-}
-
-template <typename Graph>
-void edge_walk(Graph& g)
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::edge_descriptor Edge;
-    typedef exterior_vertex_property<Graph, color> ColorProp;
-    typedef exterior_property_map<ColorProp> ColorMap;
-    typedef queue<Vertex> Queue;
-
-    {
-        typedef breadth_first_edge_walk<Graph> Walk;
-        cout << "--- default walk ----" << endl;
-        Walk walk(g, *g.begin_vertices());
-        iterate(g, walk);
-    }
-
-    {
-        typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
-        cout << "--- custom walk ---" << endl;
-        ColorProp color_prop(g, white_color);
-        ColorMap color(color_prop);
-        BreadthFirstWalk walk(g, *g.begin_vertices(), color);
-        iterate(g, walk);
-    }
-
-
-    {
-        typedef breadth_first_edge_traversal<Graph> Traversal;
-        cout << "--- default traversal ---" << endl;
-        Traversal trav(g);
-        iterate(g, trav);
-    }
-
-    {
-        typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
-        cout << "--- custom traversal ---" << endl;
-        ColorProp color_prop(g, white_color);
-        ColorMap color(color_prop);
-        BreadthFirstTraversal trav(g, color);
-        iterate(g, trav);
-    }
-
-    {
-        ColorProp colors(g, white_color);
-        ColorMap color(colors);
-
-        cout << "--- algo visit ---" << endl;
-        breadth_first_visit(g, *g.begin_vertices(), edge_printer());
-        cout << endl;
-
-        cout << "--- algo multi visit ---" << endl;
-        breadth_first_visit(g, g.begin_vertices(), next(g.begin_vertices(), 2), edge_printer());
-        cout << endl;
-
-        cout << "--- algo bfs ---" << endl;
-        breadth_first_search(g, edge_printer());
-        cout << endl;
-    }
-
-}
-
-int main(int, char* argv[])
-{
-    {
-        typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
-        Graph g;
-        ifstream f(argv[1]);
-        read(f, g);
-
-        cout << "=== undirected ===" << endl;
-        edge_walk(g);
-        cout << endl;
-    }
-
-    {
-        typedef directed_graph<string, string, vertex_set<>, edge_set<>> Graph;
-        Graph g;
-        ifstream f(argv[1]);
-        read(f, g);
-
-        cout << "=== directed ===" << endl;
-        edge_walk(g);
-        cout << endl;
-    }
-
-
-    return 0;
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/desc.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/desc.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,47 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/descriptor.hpp>
-
-#include "demangle.hpp"
-
-using namespace std;
-
-template <typename C>
-void test(C& c)
-{
-    typedef descriptor<C> D;
-    D a(c, c.begin());
-    D b(c, ++c.begin());
-    
-    cout << "--- " << demangle<C>() << " ---" << endl;
-    cout << "id a: " << hash_value(a) << endl;
-    cout << "id b: " << hash_value(b) << endl;
-    cout << (a != a) << std::endl;
-    cout << (a < b) << std::endl;
-}
-
-int main()
-{
-    std::vector<int> v;
-    v.push_back(10);
-    v.push_back(11);
-    test(v);
-    
-    std::list<int> l;
-    l.push_back(10);
-    l.push_back(11);
-    test(l);
-    
-    std::set<int> s;
-    s.insert(10);
-    s.insert(11);
-    test(s);
-    
-    std::map<int, int> m;
-    m[10] = 20;
-    m[11] = 21;
-    test(m);
-    
-    return 0;
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/dfs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/dfs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,139 +0,0 @@
-
-#include <iostream>
-#include <fstream>
-#include <queue>
-
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-#include <boost/graphs/algorithms/depth_first.hpp>
-
-#include "typestr.hpp"
-#include "read.hpp"
-
-using namespace std;
-
-struct edge_printer : dfs_visitor
-{
-    template <typename Graph, typename Vertex>
-    void discover_vertex(Graph const& g, Vertex v)
-    {
-        // cout << g[v] << " " << endl;
-    }
-
-    template <typename Graph, typename Edge>
-    void tree_edge(Graph const& g, Edge e)
-    {
-        typedef typename Graph::vertex_descriptor Vertex;
-        Vertex u = e.source();
-        Vertex v = e.target();
-        // cout << "(" << g[u] << g[v] << ") ";
-    }
-};
-
-template <typename Graph, typename Walk>
-void iterate(Graph& g, Walk& walk)
-{
-    typedef typename Walk::vertex_descriptor Vertex;
-
-    typedef algorithm_iterator<Walk> Iterator;
-    typedef pair<Iterator, Iterator> Range;
-
-    Range rng(walk.begin(), walk.end());
-    for( ; rng.first != rng.second; ++rng.first) {
-        Vertex u = rng.first->source();
-        Vertex v = rng.first->target();
-        cout << "(" << g[u] << g[v] << ") ";
-    }
-    cout << endl;
-}
-
-template <typename Graph>
-void edge_walk(Graph& g)
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::edge_descriptor Edge;
-    typedef exterior_vertex_property<Graph, color> ColorProp;
-    typedef exterior_property_map<ColorProp> ColorMap;
-    typedef stack<Vertex> Stack;
-
-    /*
-    {
-        typedef breadth_first_edge_walk<Graph> Walk;
-        cout << "--- default walk ----" << endl;
-        Walk walk(g, *g.begin_vertices());
-        iterate(g, walk);
-    }
-
-    {
-        typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
-        cout << "--- custom walk ---" << endl;
-        ColorProp color_prop(g, white_color);
-        ColorMap color(color_prop);
-        BreadthFirstWalk walk(g, *g.begin_vertices(), color);
-        iterate(g, walk);
-    }
-
-
-    {
-        typedef breadth_first_edge_traversal<Graph> Traversal;
-        cout << "--- default traversal ---" << endl;
-        Traversal trav(g);
-        iterate(g, trav);
-    }
-
-    {
-        typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
-        cout << "--- custom traversal ---" << endl;
-        ColorProp color_prop(g, white_color);
-        ColorMap color(color_prop);
-        BreadthFirstTraversal trav(g, color);
-        iterate(g, trav);
-    }
-    */
-
-    {
-        ColorProp colors(g, white_color);
-        ColorMap color(colors);
-
-        cout << "--- algo visit ---" << endl;
-        depth_first_visit(g, *g.begin_vertices(), edge_printer());
-        cout << endl;
-
-        cout << "--- algo multi visit ---" << endl;
-        // breadth_first_visit(g, g.begin_vertices(), next(g.begin_vertices(), 2), edge_printer());
-        cout << endl;
-
-        cout << "--- algo bfs ---" << endl;
-        // breadth_first_search(g, edge_printer());
-        cout << endl;
-    }
-
-}
-
-int main(int, char* argv[])
-{
-    {
-        typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
-        Graph g;
-        ifstream f(argv[1]);
-        read(f, g);
-
-        cout << "=== undirected ===" << endl;
-        edge_walk(g);
-        cout << endl;
-    }
-
-    {
-        typedef directed_graph<string, string, vertex_set<>, edge_set<>> Graph;
-        Graph g;
-        ifstream f(argv[1]);
-        read(f, g);
-
-        cout << "=== directed ===" << endl;
-        edge_walk(g);
-        cout << endl;
-    }
-
-
-    return 0;
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,412 +0,0 @@
-
-#include <iostream>
-#include <set>
-
-#include <boost/assert.hpp>
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-
-#include "typestr.hpp"
-#include "out_edge_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-typedef int City;
-typedef int Road;
-
-void list_list();
-void vec_vec();
-void set_set();
-
-namespace dispatch
-{
-    bool allows_parallel_edges(unique_associative_container_tag)
-    { return false; }
-
-    bool allows_parallel_edges(multiple_associative_container_tag)
-    { return false; }
-
-    bool allows_parallel_edges(sequence_tag)
-    { return true; }
-}
-
-template <typename Graph>
-bool allows_parallel_edges(Graph const& g)
-{
-    typedef typename Graph::out_store Store;
-    return dispatch::allows_parallel_edges(typename out_edge_traits<Store>::category());
-}
-
-
-template <typename Graph>
-void print_types(const Graph&)
-{
-    /*
-    cout << demangle(typeid(typename Graph::property_descriptor).name()) << endl;
-    cout << demangle(typeid(typename Graph::vertex_descriptor).name()) << endl;
-    cout << demangle(typeid(typename Graph::edge_descriptor).name()) << endl;
-    cout << demangle(typeid(typename Graph::property_store).name()) << endl;
-    cout << demangle(typeid(typename Graph::vertex_store).name()) << endl;
-    */
-}
-
-template <typename Graph>
-void test_add_vertices()
-{
-    Graph g;
-    cout << "  * adding vertices" << endl;
-    list<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 5; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-}
-
-template <typename Graph>
-void test_add_remove_vertices()
-{
-    Graph g;
-    cout << "  * adding vertices" << endl;
-    list<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 5; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-
-    cout << "  * removing vertices" << endl;
-    BOOST_ASSERT(g.num_vertices() == 5);
-    while(!V.empty()) {
-        g.remove_vertex(V.front());
-        V.pop_front();
-    }
-    BOOST_ASSERT(g.num_vertices() == 0);
-}
-
-template <typename Graph>
-void test_add_edges()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-
-    cout << "  * adding edges" << endl;
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-    BOOST_ASSERT(g.degree(V[0]) == 2);
-    BOOST_ASSERT(g.out_degree(V[0]) == 1);
-    BOOST_ASSERT(g.in_degree(V[0]) == 1);
-}
-
-template <typename Graph>
-void test_add_remove_edges()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-
-    cout << "  * adding edges" << endl;
-    E.push_back(g.add_edge(V[0], V[1]));
-    E.push_back(g.add_edge(V[1], V[2]));
-    E.push_back(g.add_edge(V[2], V[0]));
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-    BOOST_ASSERT(g.degree(V[0]) == 2);
-    BOOST_ASSERT(g.out_degree(V[0]) == 1);
-    BOOST_ASSERT(g.in_degree(V[0]) == 1);
-
-    cout << "  * removing edges" << endl;
-    g.remove_edge(E.front());
-    BOOST_ASSERT(g.degree(V[1]) == 1);
-    BOOST_ASSERT(g.out_degree(V[0]) == 0);
-    BOOST_ASSERT(g.in_degree(V[0]) == 1);
-    E.pop_front();
-
-    g.remove_edge(E.front());
-    BOOST_ASSERT(g.degree(V[1]) == 0);
-    E.pop_front();
-}
-
-template <typename Graph>
-void test_disconnect_vertex()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-
-    // Ensure that the graph is set up correctly.
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-    BOOST_ASSERT(g.out_degree(V[0]) == 1);
-    BOOST_ASSERT(g.out_degree(V[1]) == 1);
-    BOOST_ASSERT(g.out_degree(V[2]) == 1);
-    BOOST_ASSERT(g.in_degree(V[0]) == 1);
-    BOOST_ASSERT(g.in_degree(V[1]) == 1);
-    BOOST_ASSERT(g.in_degree(V[2]) == 1);
-    BOOST_ASSERT(g.edge(V[0], V[1]));
-    BOOST_ASSERT(g.edge(V[2], V[0]));
-
-    // Disconnect the vertex
-    g.remove_edges(V[0]);
-
-    // Assert that the graph structure is correct after cutting v0 out of the
-    // graph. The only remaining edge should be (v1, v2)
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 1);
-    BOOST_ASSERT(g.out_degree(V[0]) == 0);
-    BOOST_ASSERT(g.out_degree(V[1]) == 1);
-    BOOST_ASSERT(g.out_degree(V[2]) == 0);
-
-    BOOST_ASSERT(g.in_degree(V[0]) == 0);
-    BOOST_ASSERT(g.in_degree(V[1]) == 0);
-    BOOST_ASSERT(g.in_degree(V[2]) == 1);
-
-    // This isn't really part of this test. See the multi-edge removals.
-    g.remove_edges(V[1], V[2]);
-    BOOST_ASSERT(g.num_edges() == 0);
-    BOOST_ASSERT(g.out_degree(V[1]) == 0);
-    BOOST_ASSERT(g.in_degree(V[2]) == 0);
-}
-
-// This is a little different than above. We remove a vertex from the triangle,
-// which implicitly disconnects it.
-template <typename Graph>
-void test_implicit_disconnect_vertex()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-
-    cout << "  * implicit disconnect" << endl;
-    g.remove_vertex(V[1]);
-    BOOST_ASSERT(g.num_vertices() == 2);
-    BOOST_ASSERT(g.degree(V[0]) == 1);
-    BOOST_ASSERT(g.degree(V[2]) == 1);
-}
-
-template <typename Graph>
-void test_add_multi_edges()
-{
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-
-    cout << "  * adding multiple edge" << endl;
-    g.add_edge(u, v);
-    g.add_edge(v, u);
-    g.add_edge(u, v);
-    g.add_edge(v, u);
-
-    BOOST_ASSERT(g.num_vertices() == 2);
-    if(allows_parallel_edges(g)) {
-        BOOST_ASSERT(g.num_edges() == 4);
-    }
-    else {
-        // Two edges: (u,v) and (v,u)
-        BOOST_ASSERT(g.num_edges() == 2);
-    }
-}
-
-template <typename Graph>
-void test_remove_multi_edges()
-{
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-
-    g.add_edge(u, v);
-    g.add_edge(v, u);
-    g.add_edge(u, v);
-    g.add_edge(v, u);
-
-    cout << "  * removing multiple edges" << endl;
-    g.remove_edges(u, v);
-    BOOST_ASSERT(g.out_degree(u) == 0);
-    BOOST_ASSERT(g.in_degree(v) == 0);
-    BOOST_ASSERT(g.num_edges() == allows_parallel_edges(g) ? 2 : 1);
-    BOOST_ASSERT(g.out_degree(v) == allows_parallel_edges(g) ? 2 : 1);
-    BOOST_ASSERT(g.in_degree(u) == allows_parallel_edges(g) ? 2 : 1);
-}
-
-template <typename Graph>
-void test_edge()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-
-    cout << "  * find edges" << endl;
-    // Test for existence
-    BOOST_ASSERT(g.edge(V[0], V[1]));
-    BOOST_ASSERT(g.edge(V[1], V[2]));
-    BOOST_ASSERT(g.edge(V[2], V[0]));
-
-    // Test for inexstence
-    BOOST_ASSERT(!g.edge(V[1], V[0]));
-    BOOST_ASSERT(!g.edge(V[2], V[1]));
-    BOOST_ASSERT(!g.edge(V[0], V[2]));
-}
-
-template <typename Graph>
-void test_vertex_iterator()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-
-    cout << "  * testing vertex iterator" << endl;
-    typename Graph::vertex_range rng = g.vertices();
-    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
-    BOOST_ASSERT(*rng.first++ == V[0]);
-    BOOST_ASSERT(*rng.first++ == V[1]);
-    BOOST_ASSERT(*rng.first++ == V[2]);
-}
-
-template <typename Graph>
-void test_edge_iterator()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    vector<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    E.push_back(g.add_edge(V[0], V[1]));
-    E.push_back(g.add_edge(V[1], V[2]));
-    E.push_back(g.add_edge(V[2], V[0]));
-
-    cout << "  * testing edge iterator" << endl;
-    typename Graph::edge_range rng = g.edges();
-    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
-    BOOST_ASSERT(*rng.first++ == E[0]);
-    BOOST_ASSERT(*rng.first++ == E[1]);
-    BOOST_ASSERT(*rng.first++ == E[2]);
-}
-
-template <typename Graph>
-void test_incidence_iterator()
-{
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-    g.add_edge(u, v, 1);
-    g.add_edge(v, u, 2);
-    g.add_edge(u, v, 3);
-    g.add_edge(v, u, 4);
-
-    cout << "  * testing incident edges" << endl;
-    typename Graph::incident_edge_range rng = g.incident_edges(u);
-    for( ; rng.first != rng.second; ++rng.first) {
-        typename Graph::edge_descriptor e = *rng.first;
-        BOOST_ASSERT(e.source() == u);
-        BOOST_ASSERT(e.target() == v);
-    }
-}
-
-template <typename Graph>
-void test_adjacency_iterator()
-{
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-
-    g.add_edge(u, v, 1);
-    g.add_edge(v, u, 2);
-    g.add_edge(u, v, 3);
-    g.add_edge(v, u, 4);
-
-    cout << "  * testing adjacent vertices" << endl;
-    typename Graph::adjacent_vertex_range rng = g.adjacent_vertices(u);
-    for( ; rng.first != rng.second; ++rng.first) {
-        BOOST_ASSERT(*rng.first == v);
-    }
-}
-
-int main()
-{
-    vec_vec();
-    list_list();
-    set_set();
-
-    return 0;
-}
-
-void vec_vec()
-{
-    cout << "---- vec/vec ----" << endl;
-    typedef directed_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
-    test_add_vertices<Graph>();
-    test_add_edges<Graph>();
-    test_add_multi_edges<Graph>();
-    test_edge<Graph>();
-    test_vertex_iterator<Graph>();
-    test_edge_iterator<Graph>();
-    test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
-}
-
-void list_list()
-{
-    cout << "---- list/list ----" << endl;
-    typedef directed_graph<City, Road, vertex_list<>, edge_list<> > Graph;
-    test_add_remove_vertices<Graph>();
-    test_add_remove_edges<Graph>();
-    test_disconnect_vertex<Graph>();
-    test_implicit_disconnect_vertex<Graph>();
-    test_add_multi_edges<Graph>();
-    test_remove_multi_edges<Graph>();
-    test_edge<Graph>();
-    test_vertex_iterator<Graph>();
-    test_edge_iterator<Graph>();
-    test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
-}
-
-
-void set_set()
-{
-    cout << "---- set/set ----" << endl;
-    typedef directed_graph<City, Road, vertex_set<>, edge_set<> > Graph;
-    test_add_remove_vertices<Graph>();
-    test_add_remove_edges<Graph>();
-    test_disconnect_vertex<Graph>();
-    test_implicit_disconnect_vertex<Graph>();
-    test_add_multi_edges<Graph>();
-    test_remove_multi_edges<Graph>();
-    test_edge<Graph>();
-    test_vertex_iterator<Graph>();
-    test_edge_iterator<Graph>();
-    test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
-}
-

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,51 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-
-#include "demangle.hpp"
-#include "square.hpp"
-
-using namespace std;
-
-typedef vertex_vector<> vvec;
-typedef edge_vector<> evec;
-
-
-void directed();
-void undirected();
-
-int main()
-{
-    directed();
-    undirected();
-
-    return 0;
-}
-
-void directed()
-{
-    cout << "--- directed (vec/vec) ---" << endl;
-    typedef directed_graph<int, int, vvec, evec> Graph;
-    Graph g;
-    make_square(g);
-
-    Graph::edge_range rng = g.edges();
-    for(Graph::edge_iterator i = rng.first; i != rng.second; ++i) {
-        cout << *i << endl;
-    }
-}
-
-void undirected()
-{
-    cout << "--- undirected (vec/vec) ---" << endl;
-    typedef undirected_graph<int, int, vvec, evec> Graph;
-    Graph g;
-    make_square(g);
-
-    Graph::edge_range rng = g.edges();
-    for(Graph::edge_iterator i = rng.first ; i != rng.second; ++i) {
-        cout << *i << endl;
-    }
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/in_edge_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/in_edge_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,31 +0,0 @@
-
-#ifndef IN_EDGE_TRAITS_HPP
-#define IN_EDGE_TRAITS_HPP
-
-struct in_vector_tag : sequence_tag, unstable_remove_tag { };
-struct in_list_tag : sequence_tag, stable_mutators_tag { };
-struct in_set_tag : associative_container_tag, stable_mutators_tag { };
-
-template <typename Ins>
-struct in_edge_traits
-{ typedef typename Ins::category cateogry; };
-
-template <typename Ins>
-typename in_edge_traits<Ins>::category
-in_edge_category(Ins const&)
-{ return typename in_edge_traits<Ins>::category(); }
-
-
-template <typename Edge, typename Alloc>
-struct in_edge_traits<in_vector<Edge, Alloc>>
-{ typedef in_vector_tag category; };
-
-template <typename Edge, typename Alloc>
-struct in_edge_traits<in_list<Edge, Alloc>>
-{ typedef in_list_tag category; };
-
-template <typename Edge, typename Comp, typename Alloc>
-struct in_edge_traits<in_set<Edge, Comp, Alloc>>
-{ typedef in_set_tag category; };
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,30 +0,0 @@
-
-#ifndef INCIDENCE_TRAITS_HPP
-#define INCIDENCE_TRAITS_HPP
-
-struct incidence_vector_tag : virtual vector_tag, virtual unstable_remove_tag { };
-struct incidence_list_tag : virtual list_tag, virtual stable_mutators_tag { };
-struct incidence_set_tag : virtual unique_associative_container_tag, virtual stable_mutators_tag { };
-
-template <typename IncStore>
-struct incidence_traits
-{ typedef typename IncStore::category category; };
-
-template <typename IncStore>
-typename incidence_traits<IncStore>::category
-incidence_category(IncStore const&)
-{ return typename incidence_traits<IncStore>::category(); }
-
-template <typename Edge, typename Alloc>
-struct incidence_traits<incidence_vector<Edge, Alloc>>
-{ typedef incidence_vector_tag category; };
-
-template <typename Edge, typename Alloc>
-struct incidence_traits<incidence_list<Edge, Alloc>>
-{ typedef incidence_list_tag category; };
-
-template <typename Edge, typename Comp, typename Alloc>
-struct incidence_traits<incidence_set<Edge, Comp, Alloc>>
-{ typedef incidence_set_tag category; };
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,22 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjeceny_list/undirected_graph.hpp>
-
-using namespace std;
-using namespace boost;
-
-int main()
-{
-    typedef undirected_graph<int, none, vertex_map<string>, edge_set<> > Graph;
-    Graph g;
-    g.add_vertex("Jan", 1);
-    g.add_vertex("Feb", 2);
-    g.add_vertex("Mar", 3);
-    g.add_vertex("Apr", 4);
-    g.add_vertex("May", 5);
-
-    g.remove_vertex("Mar");
-
-    cout << g[g.find_vertex("Apr")] << endl;
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,31 +0,0 @@
-
-#ifndef OUT_EDGE_TRAITS_HPP
-#define OUT_EDGE_TRAITS_HPP
-
-struct out_vector_tag : vector_tag, unstable_remove_tag { };
-struct out_list_tag : list_tag, stable_mutators_tag { };
-struct out_set_tag : set_tag, stable_mutators_tag { };
-
-template <typename Outs>
-struct out_edge_traits
-{ typedef typename Outs::category cateogry; };
-
-template <typename Outs>
-typename out_edge_traits<Outs>::category
-out_edge_category(Outs const&)
-{ return typename out_edge_traits<Outs>::category(); }
-
-
-template <typename Edge, typename Alloc>
-struct out_edge_traits<out_vector<Edge, Alloc>>
-{ typedef out_vector_tag category; };
-
-template <typename Edge, typename Alloc>
-struct out_edge_traits<out_list<Edge, Alloc>>
-{ typedef out_list_tag category; };
-
-template <typename Edge, typename Comp, typename Alloc>
-struct out_edge_traits<out_set<Edge, Comp, Alloc>>
-{ typedef out_set_tag category; };
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/properties_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/properties_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,25 +0,0 @@
-#ifndef PROPERTIES_TRAITS_HPP
-#define PROPERTIES_TRAITS_HPP
-
-// These actually determine the mutability of the entire edge set.
-struct property_vector_tag : unstable_remove_tag { };
-struct property_list_tag : stable_mutators_tag { };
-
-template <typename Props>
-struct properties_traits
-{ typedef typename Props::category category; };
-
-template <typename Props>
-typename properties_traits<Props>::category
-properties_category(Props const&)
-{ return typename properties_traits<Props>::category(); }
-
-template <typename Edge, typename Alloc>
-struct properties_traits<property_vector<Edge, Alloc>>
-{ typedef property_vector_tag category; };
-
-template <typename Edge, typename Alloc>
-struct properties_traits<property_list<Edge, Alloc>>
-{ typedef property_list_tag category; };
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,145 +0,0 @@
-
-#include <iostream>
-#include <iterator>
-
-#include <boost/lexical_cast.hpp>
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-#include <boost/graphs/properties.hpp>
-
-#include "typestr.hpp"
-
-using namespace std;
-using namespace boost;
-
-template <typename Graph>
-void test_props()
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::vertex_properties VertexProps;
-    typedef typename Graph::edge_descriptor Edge;
-    typedef typename Graph::edge_properties EdgeProps;
-
-    Graph g;
-    cout << "--- " << typestr(g) << " ---" << endl;
-
-    // Create a fully connected graph.
-    const int N = 5;
-    for(int i = 0; i < N; ++i) {
-        Vertex u = g.add_vertex(i);
-    }
-    int x = 0;
-    typename Graph::vertex_range rng = g.vertices();
-    for( ; rng.first != rng.second; ++rng.first) {
-        typename Graph::vertex_iterator i = g.begin_vertices();
-        for( ; i != rng.first; ++i) {
-            Edge e = g.add_edge(*i, *rng.first, x++);
-        }
-    }
-    cout << g.num_vertices() << " x " << g.num_edges() << endl;
-
-    typedef exterior_vertex_property<Graph, double> VertexWeightProp;
-    typedef exterior_property_map<VertexWeightProp> VertexWeightMap;
-    VertexWeightProp vertex_weights(g, 6.28);
-    VertexWeightMap vw(vertex_weights);
-
-    typedef exterior_edge_property<Graph, double> EdgeWeightProp;
-    typedef exterior_property_map<EdgeWeightProp> EdgeWeightMap;
-    EdgeWeightProp edge_weights(g, 3.14);
-    EdgeWeightMap ew(edge_weights);
-
-    // Set and print the values of an exterior vertex property.
-    typename Graph::vertex_range vr = g.vertices();
-    for( ; vr.first != vr.second; ++vr.first) {
-        vw(*vr.first) = distance(g.begin_vertices(), vr.first) * 2;
-        cout << "vertex weight: " << vw(*vr.first) << endl;
-    }
-
-    // Set and print the values of an exterior edge property.
-    typename Graph::edge_range er = g.edges();
-    for( ; er.first != er.second; ++er.first) {
-        ew(*er.first) = distance(g.begin_edges(), er.first) * 10;
-        cout << "edge weight: " << ew(*er.first) << endl;
-    }
-
-    // If bundled, constructed over the entire bundle.
-
-    {
-        typedef interior_property_map<Graph, Vertex> PropMap;
-        typedef interior_property_map<Graph, Vertex, string VertexProps::*> NameMap;
-        PropMap props(g);
-        NameMap names(g, &VertexProps::name);
-        for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
-            Vertex v = *vr.first;
-            names(v) = "City " + lexical_cast<string>(props(v).id);
-            cout << names(v) << endl;
-        }
-    }
-
-    {
-        typedef interior_property_map<Graph, Edge> PropMap;
-        typedef interior_property_map<Graph, Edge, string EdgeProps::*> NameMap;
-        PropMap props(g);
-        NameMap names(g, &EdgeProps::name);
-        for(er.first = g.begin_edges(); er.first != er.second; ++er.first) {
-            Edge e = *er.first;
-            names(e) = "Road " + lexical_cast<string>(props(e).id);
-            cout << names(e) << endl;
-        }
-    }
-
-    {
-        // Generic stuff?
-        exterior_vertex_property<Graph, double> these_weights(g, 6.28);
-
-        optional_vertex_map<Graph, double> my_weights(g, 3.14);
-        optional_vertex_map<Graph, double> your_weights(these_weights);
-
-        for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
-            Vertex v = *vr.first;
-            cout << my_weights(v) << ", " << your_weights(v) << endl;
-        }
-    }
-}
-
-
-struct Object
-{
-    Object(int id)
-        : id(id), name()
-    { }
-
-    int id;
-    string name;
-
-    inline bool operator<(Object const& x) const
-    { return id < x.id; }
-};
-
-typedef Object City;
-typedef Object Road;
-
-int main()
-{
-    {
-        typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
-        typedef undirected_graph<City, Road, vertex_list<>, edge_list<>> G2;
-        typedef undirected_graph<City, Road, vertex_set<>, edge_set<>> G3;
-
-        test_props<G1>();
-        test_props<G2>();
-        test_props<G3>();
-    }
-
-    {
-        typedef directed_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
-        typedef directed_graph<City, Road, vertex_list<>, edge_list<>> G2;
-        typedef directed_graph<City, Road, vertex_set<>, edge_set<>> G3;
-
-        test_props<G1>();
-        test_props<G2>();
-        test_props<G3>();
-    }
-
-    return 0;
-}
\ No newline at end of file

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,72 +0,0 @@
-
-#include <iostream>
-#include <string>
-#include <list>
-
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-#include <boost/graphs/properties.hpp>
-
-#include "demangle.hpp"
-
-using namespace std;
-using namespace boost;
-
-void un_vec_vec();
-void un_list_list();
-
-template <typename Graph>
-void make_square(Graph& g)
-{
-    typename Graph::vertex_descriptor v[4];
-    v[0] = g.add_vertex(0);
-    v[1] = g.add_vertex(0);
-    v[2] = g.add_vertex(0);
-    v[3] = g.add_vertex(0);
-    g.add_edge(v[0], v[1]);
-    g.add_edge(v[1], v[2]);
-    g.add_edge(v[2], v[3]);
-    g.add_edge(v[3], v[0]);
-    g.add_edge(v[0], v[2]);
-    g.add_edge(v[1], v[3]);
-}
-
-template <typename Graph>
-void test_ext_vertex_props(Graph& g)
-{
-    typedef exterior_vertex_property<Graph, double> VertexWeight;
-    typedef exterior_edge_property<Graph, double> EdgeWeight;
-
-    VertexWeight vp(g, 5.0);
-    EdgeWeight ep(g, 1.0);
-
-    cout << "vertex using: " << demangle<typename VertexWeight::base_type>() << endl;
-    cout << "edge using: " << demangle<typename EdgeWeight::base_type>() << endl;
-
-    cout << ep[*g.begin_edges()] << endl;
-    cout << ep.data.size() << endl;
-}
-
-int main()
-{
-    un_vec_vec();
-    un_list_list();
-
-    return 0;
-}
-
-void un_vec_vec()
-{
-    typedef undirected_graph<int, int, vertex_vector<>, edge_vector<> > Graph;
-    Graph g;
-    make_square(g);
-    test_ext_vertex_props(g);
-}
-
-void un_list_list()
-{
-    typedef undirected_graph<int, int, vertex_list<>, edge_list<> > Graph;
-    Graph g;
-    make_square(g);
-    // test_ext_vertex_props(g);
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/read.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/read.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,35 +0,0 @@
-
-#ifndef READ_HPP
-#define READ_HPP
-
-#include <iostream>
-#include <sstream>
-
-/**
- * Populate the graph based on an incidence list. Here, we're assuming that the
- * given graph is simple and has properties for both vertices and edges.
- */
-template <typename Graph>
-void read(std::istream& is, Graph& g)
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::vertex_properties VertexLabel;
-    typedef typename Graph::edge_properties EdgeLabel;
-
-    for(string line; std::getline(is, line); ) {
-        if(line.empty() || line[0] == '#') continue;
-
-        // Force these to be default constructed.
-        VertexLabel ul = VertexLabel();
-        VertexLabel vl = VertexLabel();
-        EdgeLabel el = EdgeLabel();
-        std::stringstream ss(line);
-        ss >> ul >> vl >> el;
-
-        Vertex u = g.add_vertex(ul);
-        Vertex v = g.add_vertex(vl);
-        g.add_edge(u, v, el);
-    }
-}
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/search.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/search.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,192 +0,0 @@
-
-#include <iostream>
-#include <fstream>
-#include <string>
-#include <iterator>
-
-#include <boost/random.hpp>
-
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-#include <boost/graphs/adjacency_list/directed_graph.hpp>
-#include <boost/graphs/algorithms/breadth_first.hpp>
-
-#include "typestr.hpp"
-
-using namespace std;
-using namespace boost;
-
-typedef mt19937 Generator;
-typedef bernoulli_distribution<> Distribution;
-
-const int N = 10;
-const double P = 0.25;
-
-Generator rng;
-
-template <typename Graph, typename RootMap, typename TreeMap, typename TreeOrderMap>
-struct search_recorder : search_visitor
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::edge_descriptor Edge;
-    typedef directional_edge<Edge> SearchEdge;
-
-    search_recorder(Graph const& g, RootMap root, TreeMap tree, TreeOrderMap tord,
-                    int& tsize)
-        : root(root), tree(tree), tree_order(tord)
-        , tree_size(tsize)
-    { }
-
-    void start_vertex(Graph const& g, Vertex v)
-    { root(v) = true; }
-
-    void examine_vertex(Graph const& g, Vertex v)
-    { }
-
-    void discover_vertex(Graph const& g, Vertex v)
-    { }
-
-    void tree_edge(Graph const& g, SearchEdge e)
-    {
-        tree(e) = true;
-        tree_order(e) = ++tree_size;
-    }
-
-    RootMap root;
-    TreeMap tree;
-    TreeOrderMap tree_order;
-    int& tree_size;
-};
-
-template <typename Graph>
-struct graph_traits
-{ static const bool directed = false; };
-
-template <typename VP, typename EP, typename VS, typename ES>
-struct graph_traits<undirected_graph<VP,EP,VS,ES>>
-{ static const bool directed = false; };
-
-template <typename VP, typename EP, typename VS, typename ES>
-struct graph_traits<directed_graph<VP,EP,VS,ES>>
-{ static const bool directed = true; };
-
-// Create an Erdos-Renyi style random graphs with n vertices and p probability
-// of edge connection.
-template <typename Graph>
-void random_graph(Graph& g, int n, double p)
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::vertex_iterator VertexIterator;
-    typedef typename Graph::vertex_range VertexRange;
-    typedef typename Graph::edge_descriptor Edge;
-
-    // Start by adding all the required vertices.
-    for(int i = 0; i < N; ++i) {
-        g.add_vertex(i);
-    }
-
-    // Add edges with the given probability.
-    Distribution coin(p);
-    VertexRange verts = g.vertices();
-    for(VertexIterator i = verts.first; i != verts.second; ++i) {
-        for(VertexIterator j = verts.first; j != verts.second; ++j) {
-            if(i == j) continue;
-            if(coin(rng)) {
-                g.add_edge(*i, *j);
-            }
-        }
-    }
-}
-
-// Actually 
-template <typename Graph, typename Recorder>
-void draw_algorithm(Graph const& g, Recorder rec, string const& module, string const& alg)
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::vertex_range VertexRange;
-    typedef typename Graph::edge_descriptor Edge;
-    typedef typename Graph::edge_range EdgeRange;
-
-    // Open the given file for writing.
-    string name = module + "_" + alg + ".dot";
-    ofstream os(name.c_str());
-
-    string decl = graph_traits<Graph>::directed ? "digraph" : "graph";
-    string sym = graph_traits<Graph>::directed ? "->" : "--";
-
-    os << decl << " {" << endl;
-
-    VertexRange vr = g.vertices();
-    for( ; vr.first != vr.second; ++vr.first) {
-        Vertex v = *vr.first;
-        os << "  " << g[v];
-        if(rec.root(v)) {
-            os << " [color=blue]";
-        }
-        os << ";" << endl;
-    }
-
-    EdgeRange er = g.edges();
-    for( ; er.first != er.second; ++er.first) {
-        Edge e = *er.first;
-        Vertex u = e.first();
-        Vertex v = e.second();
-        os << "  " << g[u] << sym << g[v];
-        if(rec.tree(e)) {
-           os << " [color=red,label=\"" << rec.tree_order(e) << "\"]";
-        }
-        os << ";" << endl;
-    }
-    os << "}" << endl;
-}
-
-template <typename Graph>
-void test(string const& module)
-{
-    typedef exterior_vertex_property<Graph, bool> RootProp;
-    typedef exterior_edge_property<Graph, bool> TreeProp;
-    typedef exterior_edge_property<Graph, int> TreeOrderProp;
-    typedef exterior_property_map<RootProp> RootMap;
-    typedef exterior_property_map<TreeProp> TreeMap;
-    typedef exterior_property_map<TreeOrderProp> TreeOrderMap;
-    typedef search_recorder<Graph, RootMap, TreeMap, TreeOrderMap> Recorder;
-
-    Graph g;
-    cout << "--- " << typestr(g) << " ---" << endl;
-
-    // Generate a random graph
-    random_graph(g, N, P);
-
-    {
-        RootProp root(g, false);
-        TreeProp tree(g, false);
-        TreeOrderProp tord(g, 0);
-        int tsize = 0;
-        Recorder rec(g, RootMap(root), TreeMap(tree), TreeOrderMap(tord), tsize);
-        breadth_first_search(g, rec);
-        draw_algorithm(g, rec, module, string("bfs"));
-    }
-
-    // exterior_edge_property<Graph, bool> dtree(g, false);
-    // search_recorder<Graph> dfs(g, dtree);
-
-    // For each search, use the information recorded by the visitor to generate
-    // an approximate drawing of the algorithm.
-
-    // string dot = module + ".dot";
-    // ofstream f(dot.c_str());
-    // write_graphviz(f, g);
-}
-
-int main()
-{
-    typedef undirected_graph<int, int, vertex_set<>, edge_set<>> Graph;
-    typedef directed_graph<int, int, vertex_set<>, edge_set<>> Digraph;
-
-    rng.seed(time(0));
-
-    test<Graph>("graph");
-    test<Digraph>("digraph");
-
-    return 0;
-}
-

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,91 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-
-using namespace std;
-using namespace boost;
-
-/**
- * Dumb type that will cause common functions like std::less and std::greater
- * to call the custom operators.
- */
-struct Vertex
-{
-    Vertex(int x)
-        : value(x)
-    { }
-
-    int value;
-
-    inline bool operator<(Vertex const& x) const
-    {
-        cout << "    op< " << value << " " << x.value << endl;
-        return value < x.value;
-    }
-
-    inline bool operator>(Vertex const& x) const
-    {
-        cout << "    op> " << value << " " << x.value << endl;
-        return value > x.value;
-    }
-};
-
-template <typename Props>
-struct custom
-{
-    bool operator()(Props const& a, Props const& b) const
-    {
-        cout << "    custom " << a.value << " " << b.value << endl;
-        return a.value < b.value;
-    }
-};
-
-template <typename>
-struct non_template
-{
-    bool operator()(Vertex const& a, Vertex const& b) const
-    {
-        cout << "    custom " << a.value << " " << b.value << endl;
-        return a.value < b.value;
-    }
-};
-
-template <template <typename> class Compare>
-void test()
-{
-    typedef undirected_graph<Vertex, int, vertex_set<Compare>, edge_set<> > Graph;
-    Graph g;
-    cout << "inserting 1" << endl;
-    g.add_vertex(1);
-    cout << "inserting 2" << endl;
-    g.add_vertex(2);
-}
-
-void comps()
-{
-    cout << "LESS" << endl;
-    test<less>();
-
-    cout << "GREATER" << endl;
-    test<greater>();
-
-    cout << "CUSTOM" << endl;
-    test<custom>();
-
-    cout << "NON-TEMPLATE" << endl;
-    test<non_template>();
-}
-
-int main()
-{
-    typedef undirected_graph<string, none, vertex_set<>, edge_set<> > Graph;
-    Graph g;
-    g.add_vertex("Jan");
-    cout << g[g.find_vertex("Jan")] << endl;
-
-    typedef undirected_graph<none, int, vertex_list<>, edge_list<> > Tmp;
-    Tmp f;
-    f.remove_vertex(0);
-}
-

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,39 +0,0 @@
-
-#ifndef SQUARE_HPP
-#define SQUARE_HPP
-
-#include <boost/assert.hpp>
-
-// Make a K4 square
-template <typename G>
-void make_square(G& g)
-{
-    typename G::vertex_descriptor v[4];
-    for(int i = 0; i < 4; ++i) v[i] = g.add_vertex(i);
-    for(int i = 0; i < 3; ++i) g.add_edge(v[i], v[i + 1], i);
-    g.add_edge(v[3], v[0], 3);
-    g.add_edge(v[0], v[2], 4);
-    g.add_edge(v[1], v[3], 5);
-
-    // Check the basic structure...
-    BOOST_ASSERT(g.num_vertices() == 4);
-    BOOST_ASSERT(g.num_edges() == 6);
-
-    // Make sure that this actually does what I think it does. It should have
-    // the following edges:
-    // (0,1), (1,2), (2,3), (3,0), (0,2), and (1,3)
-    BOOST_ASSERT(g.edge(v[0], v[1]).second);
-    BOOST_ASSERT(g.edge(v[1], v[2]).second);
-    BOOST_ASSERT(g.edge(v[2], v[3]).second);
-    BOOST_ASSERT(g.edge(v[3], v[0]).second);
-    BOOST_ASSERT(g.edge(v[0], v[2]).second);
-    BOOST_ASSERT(g.edge(v[1], v[3]).second);
-
-    // Just to check again, assert that the degrees are correct.
-    BOOST_ASSERT(g.degree(v[0]) == 3);
-    BOOST_ASSERT(g.degree(v[1]) == 3);
-    BOOST_ASSERT(g.degree(v[2]) == 3);
-    BOOST_ASSERT(g.degree(v[3]) == 3);
-}
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,49 +0,0 @@
-
-#ifndef TEST_HPP
-#define TEST_HPP
-
-#include <list>
-#include <set>
-
-template <typename Graph>
-void test_add_vertices()
-{
-    Graph g;
-    std::list<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 5; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-}
-
-template <typename Graph>
-void test_add_remove_vertices()
-{
-    Graph g;
-    std::list<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 5; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    BOOST_ASSERT(g.num_vertices() == 5);
-    while(!V.empty()) {
-        g.remove_vertex(V.front());
-        V.pop_front();
-    }
-    BOOST_ASSERT(g.num_vertices() == 0);
-}
-
-template <typename Graph>
-void test_make_simple_triangle()
-{
-    Graph g;
-    std::vector<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-}
-
-#endif

Copied: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile (from r48390, /sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -1,4 +1,13 @@
 
+
+# Build all subrojects using g++-4.4
+project graphs
+    : requirements
+        <toolset>gcc-4.4
+        <include>$(boost-root)
+        <include>../..
+    ;
+
 # exe set : set.cpp : <include>../../ <include>/usr/local/include ;
 # exe map : map.cpp : <include>../../ <include>/usr/local/include ;
 # exe props : props.cpp : <include>../../ <include>/usr/local/include ;

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/adv_search.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/adv_search.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,207 @@
+
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <iterator>
+
+#include <boost/random.hpp>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/algorithms/search.hpp>
+#include <boost/graphs/algorithms/breadth_first.hpp>
+#include <boost/graphs/algorithms/depth_first.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef mt19937 Generator;
+typedef bernoulli_distribution<> Distribution;
+
+const int N = 10;
+const double P = 0.25;
+
+Generator rng;
+
+template <typename Graph, typename RootMap, typename TreeMap, typename TreeOrderMap>
+struct search_recorder : default_search_visitor
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef directional_edge<Edge> SearchEdge;
+
+    search_recorder(Graph const& g, RootMap root, TreeMap tree, TreeOrderMap tord,
+                    int& tsize)
+        : root(root), tree(tree), tree_order(tord)
+        , tree_size(tsize)
+    { }
+
+    void start_vertex(Graph const& g, Vertex v)
+    { root(v) = true; }
+
+    void examine_vertex(Graph const& g, Vertex v)
+    { }
+
+    void discover_vertex(Graph const& g, Vertex v)
+    { }
+
+    void tree_edge(Graph const& g, SearchEdge e)
+    {
+        tree(e) = true;
+        tree_order(e) = ++tree_size;
+    }
+
+    RootMap root;
+    TreeMap tree;
+    TreeOrderMap tree_order;
+    int& tree_size;
+};
+
+template <typename Graph>
+struct graph_traits
+{ static const bool directed = false; };
+
+template <typename VP, typename EP, typename VS, typename ES>
+struct graph_traits<undirected_graph<VP,EP,VS,ES>>
+{ static const bool directed = false; };
+
+template <typename VP, typename EP, typename VS, typename ES>
+struct graph_traits<directed_graph<VP,EP,VS,ES>>
+{ static const bool directed = true; };
+
+// Create an Erdos-Renyi style random graphs with n vertices and p probability
+// of edge connection.
+template <typename Graph>
+void random_graph(Graph& g, int n, double p)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::vertex_iterator VertexIterator;
+    typedef typename Graph::vertex_range VertexRange;
+    typedef typename Graph::edge_descriptor Edge;
+
+    // Start by adding all the required vertices.
+    for(int i = 0; i < N; ++i) {
+        g.add_vertex(i);
+    }
+
+    // Add edges with the given probability.
+    Distribution coin(p);
+    VertexRange verts = g.vertices();
+    for(VertexIterator i = verts.first; i != verts.second; ++i) {
+        for(VertexIterator j = verts.first; j != verts.second; ++j) {
+            if(i == j) continue;
+            if(coin(rng)) {
+                g.add_edge(*i, *j);
+            }
+        }
+    }
+}
+
+// Actually
+template <typename Graph, typename Recorder>
+void draw_algorithm(Graph const& g, Recorder rec, string const& module, string const& alg)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::vertex_range VertexRange;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef typename Graph::edge_range EdgeRange;
+
+    // Open the given file for writing.
+    string name = module + "_" + alg + ".dot";
+    ofstream os(name.c_str());
+
+    string decl = graph_traits<Graph>::directed ? "digraph" : "graph";
+    string sym = graph_traits<Graph>::directed ? "->" : "--";
+
+    os << decl << " {" << endl;
+
+    VertexRange vr = g.vertices();
+    for( ; vr.first != vr.second; ++vr.first) {
+        Vertex v = *vr.first;
+        os << "  " << g[v];
+        if(rec.root(v)) {
+            os << " [color=blue]";
+        }
+        os << ";" << endl;
+    }
+
+    EdgeRange er = g.edges();
+    for( ; er.first != er.second; ++er.first) {
+        Edge e = *er.first;
+        Vertex u = e.first();
+        Vertex v = e.second();
+        os << "  " << g[u] << sym << g[v];
+        if(rec.tree(e)) {
+           os << " [color=red,label=\"" << rec.tree_order(e) << "\"]";
+        }
+        os << ";" << endl;
+    }
+    os << "}" << endl;
+}
+
+template <typename Graph>
+void test(string const& module)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef exterior_vertex_property<Graph, color> ColorProp;
+    typedef exterior_vertex_property<Graph, bool> RootProp;
+    typedef exterior_edge_property<Graph, bool> TreeProp;
+    typedef exterior_edge_property<Graph, int> TreeOrderProp;
+    typedef exterior_property_map<ColorProp> ColorMap;
+    typedef exterior_property_map<RootProp> RootMap;
+    typedef exterior_property_map<TreeProp> TreeMap;
+    typedef exterior_property_map<TreeOrderProp> TreeOrderMap;
+    typedef search_recorder<Graph, RootMap, TreeMap, TreeOrderMap> Recorder;
+
+    Graph g;
+    cout << "--- " << typestr(g) << " ---" << endl;
+
+    // Generate a random graph
+    random_graph(g, N, P);
+
+    // Run a BFS (determined by the use of a queue).
+    {
+        ColorProp colors(g, white_color);
+        RootProp root(g, false);
+        TreeProp tree(g, false);
+        TreeOrderProp tord(g, 0);
+
+        ColorMap cm(colors);
+        queue<Vertex> q;
+        int tsize = 0;
+        Recorder rec(g, RootMap(root), TreeMap(tree), TreeOrderMap(tord), tsize);
+        breadth_first_search(g, rec);
+        draw_algorithm(g, rec, module, string("bfs"));
+    }
+
+    // Run a DFS (determined by the use of a stack).
+    {
+        ColorProp colors(g, white_color);
+        RootProp root(g, false);
+        TreeProp tree(g, false);
+        TreeOrderProp tord(g, 0);
+
+        ColorMap cm(colors);
+        stack<Vertex> q;
+        int tsize = 0;
+        Recorder rec(g, RootMap(root), TreeMap(tree), TreeOrderMap(tord), tsize);
+        depth_first_search(g, rec);
+        draw_algorithm(g, rec, module, string("dfs"));
+    }
+}
+
+int main()
+{
+    typedef undirected_graph<int, int, vertex_set<>, edge_set<>> Graph;
+    typedef directed_graph<int, int, vertex_set<>, edge_set<>> Digraph;
+
+    rng.seed(time(0));
+
+    test<Graph>("graph");
+    test<Digraph>("digraph");
+
+    return 0;
+}
+

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/bfs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/bfs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,131 @@
+
+#include <iostream>
+#include <fstream>
+#include <queue>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/algorithms/breadth_first.hpp>
+
+#include "typestr.hpp"
+#include "read.hpp"
+
+using namespace std;
+
+struct edge_printer : bfs_visitor
+{
+    template <typename Graph, typename Edge>
+    void tree_edge(Graph const& g, Edge e)
+    {
+        typedef typename Graph::vertex_descriptor Vertex;
+        Vertex u = e.source();
+        Vertex v = e.target();
+        cout << "(" << g[u] << g[v] << ") ";
+    }
+};
+
+template <typename Graph, typename Walk>
+void iterate(Graph& g, Walk& walk)
+{
+    typedef typename Walk::vertex_descriptor Vertex;
+
+    typedef algorithm_iterator<Walk> Iterator;
+    typedef pair<Iterator, Iterator> Range;
+
+    Range rng(walk.begin(), walk.end());
+    for( ; rng.first != rng.second; ++rng.first) {
+        Vertex u = rng.first->source();
+        Vertex v = rng.first->target();
+        cout << "(" << g[u] << g[v] << ") ";
+    }
+    cout << endl;
+}
+
+template <typename Graph>
+void edge_walk(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef exterior_vertex_property<Graph, color> ColorProp;
+    typedef exterior_property_map<ColorProp> ColorMap;
+    typedef queue<Vertex> Queue;
+
+    {
+        typedef breadth_first_edge_walk<Graph> Walk;
+        cout << "--- default walk ----" << endl;
+        Walk walk(g, *g.begin_vertices());
+        iterate(g, walk);
+    }
+
+    {
+        typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
+        cout << "--- custom walk ---" << endl;
+        ColorProp color_prop(g, white_color);
+        ColorMap color(color_prop);
+        BreadthFirstWalk walk(g, *g.begin_vertices(), color);
+        iterate(g, walk);
+    }
+
+
+    {
+        typedef breadth_first_edge_traversal<Graph> Traversal;
+        cout << "--- default traversal ---" << endl;
+        Traversal trav(g);
+        iterate(g, trav);
+    }
+
+    {
+        typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
+        cout << "--- custom traversal ---" << endl;
+        ColorProp color_prop(g, white_color);
+        ColorMap color(color_prop);
+        BreadthFirstTraversal trav(g, color);
+        iterate(g, trav);
+    }
+
+    {
+        ColorProp colors(g, white_color);
+        ColorMap color(colors);
+
+        cout << "--- algo visit ---" << endl;
+        breadth_first_visit(g, *g.begin_vertices(), edge_printer());
+        cout << endl;
+
+        cout << "--- algo multi visit ---" << endl;
+        breadth_first_visit(g, g.begin_vertices(), next(g.begin_vertices(), 2), edge_printer());
+        cout << endl;
+
+        cout << "--- algo bfs ---" << endl;
+        breadth_first_search(g, edge_printer());
+        cout << endl;
+    }
+
+}
+
+int main(int, char* argv[])
+{
+    {
+        typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
+        Graph g;
+        ifstream f(argv[1]);
+        read(f, g);
+
+        cout << "=== undirected ===" << endl;
+        edge_walk(g);
+        cout << endl;
+    }
+
+    {
+        typedef directed_graph<string, string, vertex_set<>, edge_set<>> Graph;
+        Graph g;
+        ifstream f(argv[1]);
+        read(f, g);
+
+        cout << "=== directed ===" << endl;
+        edge_walk(g);
+        cout << endl;
+    }
+
+
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,47 @@
+
+#include <iostream>
+
+#include <boost/graphs/descriptor.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+
+template <typename C>
+void test(C& c)
+{
+    typedef descriptor<C> D;
+    D a(c, c.begin());
+    D b(c, ++c.begin());
+    
+    cout << "--- " << demangle<C>() << " ---" << endl;
+    cout << "id a: " << hash_value(a) << endl;
+    cout << "id b: " << hash_value(b) << endl;
+    cout << (a != a) << std::endl;
+    cout << (a < b) << std::endl;
+}
+
+int main()
+{
+    std::vector<int> v;
+    v.push_back(10);
+    v.push_back(11);
+    test(v);
+    
+    std::list<int> l;
+    l.push_back(10);
+    l.push_back(11);
+    test(l);
+    
+    std::set<int> s;
+    s.insert(10);
+    s.insert(11);
+    test(s);
+    
+    std::map<int, int> m;
+    m[10] = 20;
+    m[11] = 21;
+    test(m);
+    
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/dfs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/dfs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,139 @@
+
+#include <iostream>
+#include <fstream>
+#include <queue>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/algorithms/depth_first.hpp>
+
+#include "typestr.hpp"
+#include "read.hpp"
+
+using namespace std;
+
+struct edge_printer : dfs_visitor
+{
+    template <typename Graph, typename Vertex>
+    void discover_vertex(Graph const& g, Vertex v)
+    {
+        // cout << g[v] << " " << endl;
+    }
+
+    template <typename Graph, typename Edge>
+    void tree_edge(Graph const& g, Edge e)
+    {
+        typedef typename Graph::vertex_descriptor Vertex;
+        Vertex u = e.source();
+        Vertex v = e.target();
+        // cout << "(" << g[u] << g[v] << ") ";
+    }
+};
+
+template <typename Graph, typename Walk>
+void iterate(Graph& g, Walk& walk)
+{
+    typedef typename Walk::vertex_descriptor Vertex;
+
+    typedef algorithm_iterator<Walk> Iterator;
+    typedef pair<Iterator, Iterator> Range;
+
+    Range rng(walk.begin(), walk.end());
+    for( ; rng.first != rng.second; ++rng.first) {
+        Vertex u = rng.first->source();
+        Vertex v = rng.first->target();
+        cout << "(" << g[u] << g[v] << ") ";
+    }
+    cout << endl;
+}
+
+template <typename Graph>
+void edge_walk(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef exterior_vertex_property<Graph, color> ColorProp;
+    typedef exterior_property_map<ColorProp> ColorMap;
+    typedef stack<Vertex> Stack;
+
+    /*
+    {
+        typedef breadth_first_edge_walk<Graph> Walk;
+        cout << "--- default walk ----" << endl;
+        Walk walk(g, *g.begin_vertices());
+        iterate(g, walk);
+    }
+
+    {
+        typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
+        cout << "--- custom walk ---" << endl;
+        ColorProp color_prop(g, white_color);
+        ColorMap color(color_prop);
+        BreadthFirstWalk walk(g, *g.begin_vertices(), color);
+        iterate(g, walk);
+    }
+
+
+    {
+        typedef breadth_first_edge_traversal<Graph> Traversal;
+        cout << "--- default traversal ---" << endl;
+        Traversal trav(g);
+        iterate(g, trav);
+    }
+
+    {
+        typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
+        cout << "--- custom traversal ---" << endl;
+        ColorProp color_prop(g, white_color);
+        ColorMap color(color_prop);
+        BreadthFirstTraversal trav(g, color);
+        iterate(g, trav);
+    }
+    */
+
+    {
+        ColorProp colors(g, white_color);
+        ColorMap color(colors);
+
+        cout << "--- algo visit ---" << endl;
+        depth_first_visit(g, *g.begin_vertices(), edge_printer());
+        cout << endl;
+
+        cout << "--- algo multi visit ---" << endl;
+        // breadth_first_visit(g, g.begin_vertices(), next(g.begin_vertices(), 2), edge_printer());
+        cout << endl;
+
+        cout << "--- algo bfs ---" << endl;
+        // breadth_first_search(g, edge_printer());
+        cout << endl;
+    }
+
+}
+
+int main(int, char* argv[])
+{
+    {
+        typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
+        Graph g;
+        ifstream f(argv[1]);
+        read(f, g);
+
+        cout << "=== undirected ===" << endl;
+        edge_walk(g);
+        cout << endl;
+    }
+
+    {
+        typedef directed_graph<string, string, vertex_set<>, edge_set<>> Graph;
+        Graph g;
+        ifstream f(argv[1]);
+        read(f, g);
+
+        cout << "=== directed ===" << endl;
+        edge_walk(g);
+        cout << endl;
+    }
+
+
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/di.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/di.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,412 @@
+
+#include <iostream>
+#include <set>
+
+#include <boost/assert.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+
+#include "typestr.hpp"
+#include "out_edge_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef int City;
+typedef int Road;
+
+void list_list();
+void vec_vec();
+void set_set();
+
+namespace dispatch
+{
+    bool allows_parallel_edges(unique_associative_container_tag)
+    { return false; }
+
+    bool allows_parallel_edges(multiple_associative_container_tag)
+    { return false; }
+
+    bool allows_parallel_edges(sequence_tag)
+    { return true; }
+}
+
+template <typename Graph>
+bool allows_parallel_edges(Graph const& g)
+{
+    typedef typename Graph::out_store Store;
+    return dispatch::allows_parallel_edges(typename out_edge_traits<Store>::category());
+}
+
+
+template <typename Graph>
+void print_types(const Graph&)
+{
+    /*
+    cout << demangle(typeid(typename Graph::property_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::vertex_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::edge_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::property_store).name()) << endl;
+    cout << demangle(typeid(typename Graph::vertex_store).name()) << endl;
+    */
+}
+
+template <typename Graph>
+void test_add_vertices()
+{
+    Graph g;
+    cout << "  * adding vertices" << endl;
+    list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+}
+
+template <typename Graph>
+void test_add_remove_vertices()
+{
+    Graph g;
+    cout << "  * adding vertices" << endl;
+    list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+
+    cout << "  * removing vertices" << endl;
+    BOOST_ASSERT(g.num_vertices() == 5);
+    while(!V.empty()) {
+        g.remove_vertex(V.front());
+        V.pop_front();
+    }
+    BOOST_ASSERT(g.num_vertices() == 0);
+}
+
+template <typename Graph>
+void test_add_edges()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+
+    cout << "  * adding edges" << endl;
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+    BOOST_ASSERT(g.degree(V[0]) == 2);
+    BOOST_ASSERT(g.out_degree(V[0]) == 1);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+}
+
+template <typename Graph>
+void test_add_remove_edges()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+
+    cout << "  * adding edges" << endl;
+    E.push_back(g.add_edge(V[0], V[1]));
+    E.push_back(g.add_edge(V[1], V[2]));
+    E.push_back(g.add_edge(V[2], V[0]));
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+    BOOST_ASSERT(g.degree(V[0]) == 2);
+    BOOST_ASSERT(g.out_degree(V[0]) == 1);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+
+    cout << "  * removing edges" << endl;
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 1);
+    BOOST_ASSERT(g.out_degree(V[0]) == 0);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+    E.pop_front();
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    E.pop_front();
+}
+
+template <typename Graph>
+void test_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+
+    // Ensure that the graph is set up correctly.
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+    BOOST_ASSERT(g.out_degree(V[0]) == 1);
+    BOOST_ASSERT(g.out_degree(V[1]) == 1);
+    BOOST_ASSERT(g.out_degree(V[2]) == 1);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+    BOOST_ASSERT(g.in_degree(V[1]) == 1);
+    BOOST_ASSERT(g.in_degree(V[2]) == 1);
+    BOOST_ASSERT(g.edge(V[0], V[1]));
+    BOOST_ASSERT(g.edge(V[2], V[0]));
+
+    // Disconnect the vertex
+    g.remove_edges(V[0]);
+
+    // Assert that the graph structure is correct after cutting v0 out of the
+    // graph. The only remaining edge should be (v1, v2)
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 1);
+    BOOST_ASSERT(g.out_degree(V[0]) == 0);
+    BOOST_ASSERT(g.out_degree(V[1]) == 1);
+    BOOST_ASSERT(g.out_degree(V[2]) == 0);
+
+    BOOST_ASSERT(g.in_degree(V[0]) == 0);
+    BOOST_ASSERT(g.in_degree(V[1]) == 0);
+    BOOST_ASSERT(g.in_degree(V[2]) == 1);
+
+    // This isn't really part of this test. See the multi-edge removals.
+    g.remove_edges(V[1], V[2]);
+    BOOST_ASSERT(g.num_edges() == 0);
+    BOOST_ASSERT(g.out_degree(V[1]) == 0);
+    BOOST_ASSERT(g.in_degree(V[2]) == 0);
+}
+
+// This is a little different than above. We remove a vertex from the triangle,
+// which implicitly disconnects it.
+template <typename Graph>
+void test_implicit_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    cout << "  * implicit disconnect" << endl;
+    g.remove_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 2);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+template <typename Graph>
+void test_add_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+
+    cout << "  * adding multiple edge" << endl;
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    BOOST_ASSERT(g.num_vertices() == 2);
+    if(allows_parallel_edges(g)) {
+        BOOST_ASSERT(g.num_edges() == 4);
+    }
+    else {
+        // Two edges: (u,v) and (v,u)
+        BOOST_ASSERT(g.num_edges() == 2);
+    }
+}
+
+template <typename Graph>
+void test_remove_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    cout << "  * removing multiple edges" << endl;
+    g.remove_edges(u, v);
+    BOOST_ASSERT(g.out_degree(u) == 0);
+    BOOST_ASSERT(g.in_degree(v) == 0);
+    BOOST_ASSERT(g.num_edges() == allows_parallel_edges(g) ? 2 : 1);
+    BOOST_ASSERT(g.out_degree(v) == allows_parallel_edges(g) ? 2 : 1);
+    BOOST_ASSERT(g.in_degree(u) == allows_parallel_edges(g) ? 2 : 1);
+}
+
+template <typename Graph>
+void test_edge()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    cout << "  * find edges" << endl;
+    // Test for existence
+    BOOST_ASSERT(g.edge(V[0], V[1]));
+    BOOST_ASSERT(g.edge(V[1], V[2]));
+    BOOST_ASSERT(g.edge(V[2], V[0]));
+
+    // Test for inexstence
+    BOOST_ASSERT(!g.edge(V[1], V[0]));
+    BOOST_ASSERT(!g.edge(V[2], V[1]));
+    BOOST_ASSERT(!g.edge(V[0], V[2]));
+}
+
+template <typename Graph>
+void test_vertex_iterator()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+
+    cout << "  * testing vertex iterator" << endl;
+    typename Graph::vertex_range rng = g.vertices();
+    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+    BOOST_ASSERT(*rng.first++ == V[0]);
+    BOOST_ASSERT(*rng.first++ == V[1]);
+    BOOST_ASSERT(*rng.first++ == V[2]);
+}
+
+template <typename Graph>
+void test_edge_iterator()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    vector<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    E.push_back(g.add_edge(V[0], V[1]));
+    E.push_back(g.add_edge(V[1], V[2]));
+    E.push_back(g.add_edge(V[2], V[0]));
+
+    cout << "  * testing edge iterator" << endl;
+    typename Graph::edge_range rng = g.edges();
+    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+    BOOST_ASSERT(*rng.first++ == E[0]);
+    BOOST_ASSERT(*rng.first++ == E[1]);
+    BOOST_ASSERT(*rng.first++ == E[2]);
+}
+
+template <typename Graph>
+void test_incidence_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    cout << "  * testing incident edges" << endl;
+    typename Graph::incident_edge_range rng = g.incident_edges(u);
+    for( ; rng.first != rng.second; ++rng.first) {
+        typename Graph::edge_descriptor e = *rng.first;
+        BOOST_ASSERT(e.source() == u);
+        BOOST_ASSERT(e.target() == v);
+    }
+}
+
+template <typename Graph>
+void test_adjacency_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    cout << "  * testing adjacent vertices" << endl;
+    typename Graph::adjacent_vertex_range rng = g.adjacent_vertices(u);
+    for( ; rng.first != rng.second; ++rng.first) {
+        BOOST_ASSERT(*rng.first == v);
+    }
+}
+
+int main()
+{
+    vec_vec();
+    list_list();
+    set_set();
+
+    return 0;
+}
+
+void vec_vec()
+{
+    cout << "---- vec/vec ----" << endl;
+    typedef directed_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
+    test_add_vertices<Graph>();
+    test_add_edges<Graph>();
+    test_add_multi_edges<Graph>();
+    test_edge<Graph>();
+    test_vertex_iterator<Graph>();
+    test_edge_iterator<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+}
+
+void list_list()
+{
+    cout << "---- list/list ----" << endl;
+    typedef directed_graph<City, Road, vertex_list<>, edge_list<> > Graph;
+    test_add_remove_vertices<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_edge<Graph>();
+    test_vertex_iterator<Graph>();
+    test_edge_iterator<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+}
+
+
+void set_set()
+{
+    cout << "---- set/set ----" << endl;
+    typedef directed_graph<City, Road, vertex_set<>, edge_set<> > Graph;
+    test_add_remove_vertices<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_edge<Graph>();
+    test_vertex_iterator<Graph>();
+    test_edge_iterator<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+}
+

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,51 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+
+#include "demangle.hpp"
+#include "square.hpp"
+
+using namespace std;
+
+typedef vertex_vector<> vvec;
+typedef edge_vector<> evec;
+
+
+void directed();
+void undirected();
+
+int main()
+{
+    directed();
+    undirected();
+
+    return 0;
+}
+
+void directed()
+{
+    cout << "--- directed (vec/vec) ---" << endl;
+    typedef directed_graph<int, int, vvec, evec> Graph;
+    Graph g;
+    make_square(g);
+
+    Graph::edge_range rng = g.edges();
+    for(Graph::edge_iterator i = rng.first; i != rng.second; ++i) {
+        cout << *i << endl;
+    }
+}
+
+void undirected()
+{
+    cout << "--- undirected (vec/vec) ---" << endl;
+    typedef undirected_graph<int, int, vvec, evec> Graph;
+    Graph g;
+    make_square(g);
+
+    Graph::edge_range rng = g.edges();
+    for(Graph::edge_iterator i = rng.first ; i != rng.second; ++i) {
+        cout << *i << endl;
+    }
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/in_edge_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/in_edge_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,31 @@
+
+#ifndef IN_EDGE_TRAITS_HPP
+#define IN_EDGE_TRAITS_HPP
+
+struct in_vector_tag : sequence_tag, unstable_remove_tag { };
+struct in_list_tag : sequence_tag, stable_mutators_tag { };
+struct in_set_tag : associative_container_tag, stable_mutators_tag { };
+
+template <typename Ins>
+struct in_edge_traits
+{ typedef typename Ins::category cateogry; };
+
+template <typename Ins>
+typename in_edge_traits<Ins>::category
+in_edge_category(Ins const&)
+{ return typename in_edge_traits<Ins>::category(); }
+
+
+template <typename Edge, typename Alloc>
+struct in_edge_traits<in_vector<Edge, Alloc>>
+{ typedef in_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct in_edge_traits<in_list<Edge, Alloc>>
+{ typedef in_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct in_edge_traits<in_set<Edge, Comp, Alloc>>
+{ typedef in_set_tag category; };
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/incidence_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/incidence_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,30 @@
+
+#ifndef INCIDENCE_TRAITS_HPP
+#define INCIDENCE_TRAITS_HPP
+
+struct incidence_vector_tag : virtual vector_tag, virtual unstable_remove_tag { };
+struct incidence_list_tag : virtual list_tag, virtual stable_mutators_tag { };
+struct incidence_set_tag : virtual unique_associative_container_tag, virtual stable_mutators_tag { };
+
+template <typename IncStore>
+struct incidence_traits
+{ typedef typename IncStore::category category; };
+
+template <typename IncStore>
+typename incidence_traits<IncStore>::category
+incidence_category(IncStore const&)
+{ return typename incidence_traits<IncStore>::category(); }
+
+template <typename Edge, typename Alloc>
+struct incidence_traits<incidence_vector<Edge, Alloc>>
+{ typedef incidence_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct incidence_traits<incidence_list<Edge, Alloc>>
+{ typedef incidence_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct incidence_traits<incidence_set<Edge, Comp, Alloc>>
+{ typedef incidence_set_tag category; };
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/map.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/map.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,22 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjeceny_list/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{
+    typedef undirected_graph<int, none, vertex_map<string>, edge_set<> > Graph;
+    Graph g;
+    g.add_vertex("Jan", 1);
+    g.add_vertex("Feb", 2);
+    g.add_vertex("Mar", 3);
+    g.add_vertex("Apr", 4);
+    g.add_vertex("May", 5);
+
+    g.remove_vertex("Mar");
+
+    cout << g[g.find_vertex("Apr")] << endl;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/out_edge_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/out_edge_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,31 @@
+
+#ifndef OUT_EDGE_TRAITS_HPP
+#define OUT_EDGE_TRAITS_HPP
+
+struct out_vector_tag : vector_tag, unstable_remove_tag { };
+struct out_list_tag : list_tag, stable_mutators_tag { };
+struct out_set_tag : set_tag, stable_mutators_tag { };
+
+template <typename Outs>
+struct out_edge_traits
+{ typedef typename Outs::category cateogry; };
+
+template <typename Outs>
+typename out_edge_traits<Outs>::category
+out_edge_category(Outs const&)
+{ return typename out_edge_traits<Outs>::category(); }
+
+
+template <typename Edge, typename Alloc>
+struct out_edge_traits<out_vector<Edge, Alloc>>
+{ typedef out_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct out_edge_traits<out_list<Edge, Alloc>>
+{ typedef out_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct out_edge_traits<out_set<Edge, Comp, Alloc>>
+{ typedef out_set_tag category; };
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/properties_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/properties_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,25 @@
+#ifndef PROPERTIES_TRAITS_HPP
+#define PROPERTIES_TRAITS_HPP
+
+// These actually determine the mutability of the entire edge set.
+struct property_vector_tag : unstable_remove_tag { };
+struct property_list_tag : stable_mutators_tag { };
+
+template <typename Props>
+struct properties_traits
+{ typedef typename Props::category category; };
+
+template <typename Props>
+typename properties_traits<Props>::category
+properties_category(Props const&)
+{ return typename properties_traits<Props>::category(); }
+
+template <typename Edge, typename Alloc>
+struct properties_traits<property_vector<Edge, Alloc>>
+{ typedef property_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct properties_traits<property_list<Edge, Alloc>>
+{ typedef property_list_tag category; };
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/propmaps.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/propmaps.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,145 @@
+
+#include <iostream>
+#include <iterator>
+
+#include <boost/lexical_cast.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/properties.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+template <typename Graph>
+void test_props()
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::vertex_properties VertexProps;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef typename Graph::edge_properties EdgeProps;
+
+    Graph g;
+    cout << "--- " << typestr(g) << " ---" << endl;
+
+    // Create a fully connected graph.
+    const int N = 5;
+    for(int i = 0; i < N; ++i) {
+        Vertex u = g.add_vertex(i);
+    }
+    int x = 0;
+    typename Graph::vertex_range rng = g.vertices();
+    for( ; rng.first != rng.second; ++rng.first) {
+        typename Graph::vertex_iterator i = g.begin_vertices();
+        for( ; i != rng.first; ++i) {
+            Edge e = g.add_edge(*i, *rng.first, x++);
+        }
+    }
+    cout << g.num_vertices() << " x " << g.num_edges() << endl;
+
+    typedef exterior_vertex_property<Graph, double> VertexWeightProp;
+    typedef exterior_property_map<VertexWeightProp> VertexWeightMap;
+    VertexWeightProp vertex_weights(g, 6.28);
+    VertexWeightMap vw(vertex_weights);
+
+    typedef exterior_edge_property<Graph, double> EdgeWeightProp;
+    typedef exterior_property_map<EdgeWeightProp> EdgeWeightMap;
+    EdgeWeightProp edge_weights(g, 3.14);
+    EdgeWeightMap ew(edge_weights);
+
+    // Set and print the values of an exterior vertex property.
+    typename Graph::vertex_range vr = g.vertices();
+    for( ; vr.first != vr.second; ++vr.first) {
+        vw(*vr.first) = distance(g.begin_vertices(), vr.first) * 2;
+        cout << "vertex weight: " << vw(*vr.first) << endl;
+    }
+
+    // Set and print the values of an exterior edge property.
+    typename Graph::edge_range er = g.edges();
+    for( ; er.first != er.second; ++er.first) {
+        ew(*er.first) = distance(g.begin_edges(), er.first) * 10;
+        cout << "edge weight: " << ew(*er.first) << endl;
+    }
+
+    // If bundled, constructed over the entire bundle.
+
+    {
+        typedef interior_property_map<Graph, Vertex> PropMap;
+        typedef interior_property_map<Graph, Vertex, string VertexProps::*> NameMap;
+        PropMap props(g);
+        NameMap names(g, &VertexProps::name);
+        for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
+            Vertex v = *vr.first;
+            names(v) = "City " + lexical_cast<string>(props(v).id);
+            cout << names(v) << endl;
+        }
+    }
+
+    {
+        typedef interior_property_map<Graph, Edge> PropMap;
+        typedef interior_property_map<Graph, Edge, string EdgeProps::*> NameMap;
+        PropMap props(g);
+        NameMap names(g, &EdgeProps::name);
+        for(er.first = g.begin_edges(); er.first != er.second; ++er.first) {
+            Edge e = *er.first;
+            names(e) = "Road " + lexical_cast<string>(props(e).id);
+            cout << names(e) << endl;
+        }
+    }
+
+    {
+        // Generic stuff?
+        exterior_vertex_property<Graph, double> these_weights(g, 6.28);
+
+        optional_vertex_map<Graph, double> my_weights(g, 3.14);
+        optional_vertex_map<Graph, double> your_weights(these_weights);
+
+        for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
+            Vertex v = *vr.first;
+            cout << my_weights(v) << ", " << your_weights(v) << endl;
+        }
+    }
+}
+
+
+struct Object
+{
+    Object(int id)
+        : id(id), name()
+    { }
+
+    int id;
+    string name;
+
+    inline bool operator<(Object const& x) const
+    { return id < x.id; }
+};
+
+typedef Object City;
+typedef Object Road;
+
+int main()
+{
+    {
+        typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
+        typedef undirected_graph<City, Road, vertex_list<>, edge_list<>> G2;
+        typedef undirected_graph<City, Road, vertex_set<>, edge_set<>> G3;
+
+        test_props<G1>();
+        test_props<G2>();
+        test_props<G3>();
+    }
+
+    {
+        typedef directed_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
+        typedef directed_graph<City, Road, vertex_list<>, edge_list<>> G2;
+        typedef directed_graph<City, Road, vertex_set<>, edge_set<>> G3;
+
+        test_props<G1>();
+        test_props<G2>();
+        test_props<G3>();
+    }
+
+    return 0;
+}
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/props.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/props.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,72 @@
+
+#include <iostream>
+#include <string>
+#include <list>
+
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/properties.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+using namespace boost;
+
+void un_vec_vec();
+void un_list_list();
+
+template <typename Graph>
+void make_square(Graph& g)
+{
+    typename Graph::vertex_descriptor v[4];
+    v[0] = g.add_vertex(0);
+    v[1] = g.add_vertex(0);
+    v[2] = g.add_vertex(0);
+    v[3] = g.add_vertex(0);
+    g.add_edge(v[0], v[1]);
+    g.add_edge(v[1], v[2]);
+    g.add_edge(v[2], v[3]);
+    g.add_edge(v[3], v[0]);
+    g.add_edge(v[0], v[2]);
+    g.add_edge(v[1], v[3]);
+}
+
+template <typename Graph>
+void test_ext_vertex_props(Graph& g)
+{
+    typedef exterior_vertex_property<Graph, double> VertexWeight;
+    typedef exterior_edge_property<Graph, double> EdgeWeight;
+
+    VertexWeight vp(g, 5.0);
+    EdgeWeight ep(g, 1.0);
+
+    cout << "vertex using: " << demangle<typename VertexWeight::base_type>() << endl;
+    cout << "edge using: " << demangle<typename EdgeWeight::base_type>() << endl;
+
+    cout << ep[*g.begin_edges()] << endl;
+    cout << ep.data.size() << endl;
+}
+
+int main()
+{
+    un_vec_vec();
+    un_list_list();
+
+    return 0;
+}
+
+void un_vec_vec()
+{
+    typedef undirected_graph<int, int, vertex_vector<>, edge_vector<> > Graph;
+    Graph g;
+    make_square(g);
+    test_ext_vertex_props(g);
+}
+
+void un_list_list()
+{
+    typedef undirected_graph<int, int, vertex_list<>, edge_list<> > Graph;
+    Graph g;
+    make_square(g);
+    // test_ext_vertex_props(g);
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/read.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/read.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,35 @@
+
+#ifndef READ_HPP
+#define READ_HPP
+
+#include <iostream>
+#include <sstream>
+
+/**
+ * Populate the graph based on an incidence list. Here, we're assuming that the
+ * given graph is simple and has properties for both vertices and edges.
+ */
+template <typename Graph>
+void read(std::istream& is, Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::vertex_properties VertexLabel;
+    typedef typename Graph::edge_properties EdgeLabel;
+
+    for(string line; std::getline(is, line); ) {
+        if(line.empty() || line[0] == '#') continue;
+
+        // Force these to be default constructed.
+        VertexLabel ul = VertexLabel();
+        VertexLabel vl = VertexLabel();
+        EdgeLabel el = EdgeLabel();
+        std::stringstream ss(line);
+        ss >> ul >> vl >> el;
+
+        Vertex u = g.add_vertex(ul);
+        Vertex v = g.add_vertex(vl);
+        g.add_edge(u, v, el);
+    }
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/search.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/search.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,192 @@
+
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <iterator>
+
+#include <boost/random.hpp>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/algorithms/breadth_first.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef mt19937 Generator;
+typedef bernoulli_distribution<> Distribution;
+
+const int N = 10;
+const double P = 0.25;
+
+Generator rng;
+
+template <typename Graph, typename RootMap, typename TreeMap, typename TreeOrderMap>
+struct search_recorder : search_visitor
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef directional_edge<Edge> SearchEdge;
+
+    search_recorder(Graph const& g, RootMap root, TreeMap tree, TreeOrderMap tord,
+                    int& tsize)
+        : root(root), tree(tree), tree_order(tord)
+        , tree_size(tsize)
+    { }
+
+    void start_vertex(Graph const& g, Vertex v)
+    { root(v) = true; }
+
+    void examine_vertex(Graph const& g, Vertex v)
+    { }
+
+    void discover_vertex(Graph const& g, Vertex v)
+    { }
+
+    void tree_edge(Graph const& g, SearchEdge e)
+    {
+        tree(e) = true;
+        tree_order(e) = ++tree_size;
+    }
+
+    RootMap root;
+    TreeMap tree;
+    TreeOrderMap tree_order;
+    int& tree_size;
+};
+
+template <typename Graph>
+struct graph_traits
+{ static const bool directed = false; };
+
+template <typename VP, typename EP, typename VS, typename ES>
+struct graph_traits<undirected_graph<VP,EP,VS,ES>>
+{ static const bool directed = false; };
+
+template <typename VP, typename EP, typename VS, typename ES>
+struct graph_traits<directed_graph<VP,EP,VS,ES>>
+{ static const bool directed = true; };
+
+// Create an Erdos-Renyi style random graphs with n vertices and p probability
+// of edge connection.
+template <typename Graph>
+void random_graph(Graph& g, int n, double p)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::vertex_iterator VertexIterator;
+    typedef typename Graph::vertex_range VertexRange;
+    typedef typename Graph::edge_descriptor Edge;
+
+    // Start by adding all the required vertices.
+    for(int i = 0; i < N; ++i) {
+        g.add_vertex(i);
+    }
+
+    // Add edges with the given probability.
+    Distribution coin(p);
+    VertexRange verts = g.vertices();
+    for(VertexIterator i = verts.first; i != verts.second; ++i) {
+        for(VertexIterator j = verts.first; j != verts.second; ++j) {
+            if(i == j) continue;
+            if(coin(rng)) {
+                g.add_edge(*i, *j);
+            }
+        }
+    }
+}
+
+// Actually 
+template <typename Graph, typename Recorder>
+void draw_algorithm(Graph const& g, Recorder rec, string const& module, string const& alg)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::vertex_range VertexRange;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef typename Graph::edge_range EdgeRange;
+
+    // Open the given file for writing.
+    string name = module + "_" + alg + ".dot";
+    ofstream os(name.c_str());
+
+    string decl = graph_traits<Graph>::directed ? "digraph" : "graph";
+    string sym = graph_traits<Graph>::directed ? "->" : "--";
+
+    os << decl << " {" << endl;
+
+    VertexRange vr = g.vertices();
+    for( ; vr.first != vr.second; ++vr.first) {
+        Vertex v = *vr.first;
+        os << "  " << g[v];
+        if(rec.root(v)) {
+            os << " [color=blue]";
+        }
+        os << ";" << endl;
+    }
+
+    EdgeRange er = g.edges();
+    for( ; er.first != er.second; ++er.first) {
+        Edge e = *er.first;
+        Vertex u = e.first();
+        Vertex v = e.second();
+        os << "  " << g[u] << sym << g[v];
+        if(rec.tree(e)) {
+           os << " [color=red,label=\"" << rec.tree_order(e) << "\"]";
+        }
+        os << ";" << endl;
+    }
+    os << "}" << endl;
+}
+
+template <typename Graph>
+void test(string const& module)
+{
+    typedef exterior_vertex_property<Graph, bool> RootProp;
+    typedef exterior_edge_property<Graph, bool> TreeProp;
+    typedef exterior_edge_property<Graph, int> TreeOrderProp;
+    typedef exterior_property_map<RootProp> RootMap;
+    typedef exterior_property_map<TreeProp> TreeMap;
+    typedef exterior_property_map<TreeOrderProp> TreeOrderMap;
+    typedef search_recorder<Graph, RootMap, TreeMap, TreeOrderMap> Recorder;
+
+    Graph g;
+    cout << "--- " << typestr(g) << " ---" << endl;
+
+    // Generate a random graph
+    random_graph(g, N, P);
+
+    {
+        RootProp root(g, false);
+        TreeProp tree(g, false);
+        TreeOrderProp tord(g, 0);
+        int tsize = 0;
+        Recorder rec(g, RootMap(root), TreeMap(tree), TreeOrderMap(tord), tsize);
+        breadth_first_search(g, rec);
+        draw_algorithm(g, rec, module, string("bfs"));
+    }
+
+    // exterior_edge_property<Graph, bool> dtree(g, false);
+    // search_recorder<Graph> dfs(g, dtree);
+
+    // For each search, use the information recorded by the visitor to generate
+    // an approximate drawing of the algorithm.
+
+    // string dot = module + ".dot";
+    // ofstream f(dot.c_str());
+    // write_graphviz(f, g);
+}
+
+int main()
+{
+    typedef undirected_graph<int, int, vertex_set<>, edge_set<>> Graph;
+    typedef directed_graph<int, int, vertex_set<>, edge_set<>> Digraph;
+
+    rng.seed(time(0));
+
+    test<Graph>("graph");
+    test<Digraph>("digraph");
+
+    return 0;
+}
+

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/set.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/set.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,91 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+/**
+ * Dumb type that will cause common functions like std::less and std::greater
+ * to call the custom operators.
+ */
+struct Vertex
+{
+    Vertex(int x)
+        : value(x)
+    { }
+
+    int value;
+
+    inline bool operator<(Vertex const& x) const
+    {
+        cout << "    op< " << value << " " << x.value << endl;
+        return value < x.value;
+    }
+
+    inline bool operator>(Vertex const& x) const
+    {
+        cout << "    op> " << value << " " << x.value << endl;
+        return value > x.value;
+    }
+};
+
+template <typename Props>
+struct custom
+{
+    bool operator()(Props const& a, Props const& b) const
+    {
+        cout << "    custom " << a.value << " " << b.value << endl;
+        return a.value < b.value;
+    }
+};
+
+template <typename>
+struct non_template
+{
+    bool operator()(Vertex const& a, Vertex const& b) const
+    {
+        cout << "    custom " << a.value << " " << b.value << endl;
+        return a.value < b.value;
+    }
+};
+
+template <template <typename> class Compare>
+void test()
+{
+    typedef undirected_graph<Vertex, int, vertex_set<Compare>, edge_set<> > Graph;
+    Graph g;
+    cout << "inserting 1" << endl;
+    g.add_vertex(1);
+    cout << "inserting 2" << endl;
+    g.add_vertex(2);
+}
+
+void comps()
+{
+    cout << "LESS" << endl;
+    test<less>();
+
+    cout << "GREATER" << endl;
+    test<greater>();
+
+    cout << "CUSTOM" << endl;
+    test<custom>();
+
+    cout << "NON-TEMPLATE" << endl;
+    test<non_template>();
+}
+
+int main()
+{
+    typedef undirected_graph<string, none, vertex_set<>, edge_set<> > Graph;
+    Graph g;
+    g.add_vertex("Jan");
+    cout << g[g.find_vertex("Jan")] << endl;
+
+    typedef undirected_graph<none, int, vertex_list<>, edge_list<> > Tmp;
+    Tmp f;
+    f.remove_vertex(0);
+}
+

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/square.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/square.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,39 @@
+
+#ifndef SQUARE_HPP
+#define SQUARE_HPP
+
+#include <boost/assert.hpp>
+
+// Make a K4 square
+template <typename G>
+void make_square(G& g)
+{
+    typename G::vertex_descriptor v[4];
+    for(int i = 0; i < 4; ++i) v[i] = g.add_vertex(i);
+    for(int i = 0; i < 3; ++i) g.add_edge(v[i], v[i + 1], i);
+    g.add_edge(v[3], v[0], 3);
+    g.add_edge(v[0], v[2], 4);
+    g.add_edge(v[1], v[3], 5);
+
+    // Check the basic structure...
+    BOOST_ASSERT(g.num_vertices() == 4);
+    BOOST_ASSERT(g.num_edges() == 6);
+
+    // Make sure that this actually does what I think it does. It should have
+    // the following edges:
+    // (0,1), (1,2), (2,3), (3,0), (0,2), and (1,3)
+    BOOST_ASSERT(g.edge(v[0], v[1]).second);
+    BOOST_ASSERT(g.edge(v[1], v[2]).second);
+    BOOST_ASSERT(g.edge(v[2], v[3]).second);
+    BOOST_ASSERT(g.edge(v[3], v[0]).second);
+    BOOST_ASSERT(g.edge(v[0], v[2]).second);
+    BOOST_ASSERT(g.edge(v[1], v[3]).second);
+
+    // Just to check again, assert that the degrees are correct.
+    BOOST_ASSERT(g.degree(v[0]) == 3);
+    BOOST_ASSERT(g.degree(v[1]) == 3);
+    BOOST_ASSERT(g.degree(v[2]) == 3);
+    BOOST_ASSERT(g.degree(v[3]) == 3);
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,49 @@
+
+#ifndef TEST_HPP
+#define TEST_HPP
+
+#include <list>
+#include <set>
+
+template <typename Graph>
+void test_add_vertices()
+{
+    Graph g;
+    std::list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+}
+
+template <typename Graph>
+void test_add_remove_vertices()
+{
+    Graph g;
+    std::list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    BOOST_ASSERT(g.num_vertices() == 5);
+    while(!V.empty()) {
+        g.remove_vertex(V.front());
+        V.pop_front();
+    }
+    BOOST_ASSERT(g.num_vertices() == 0);
+}
+
+template <typename Graph>
+void test_make_simple_triangle()
+{
+    Graph g;
+    std::vector<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_es.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_es.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,200 @@
+
+#include <iostream>
+
+#include <boost/next_prior.hpp>
+
+#include <boost/graphs/adjacency_list/edge_vector.hpp>
+#include <boost/graphs/adjacency_list/edge_list.hpp>
+#include <boost/graphs/adjacency_list/edge_set.hpp>
+
+#include <boost/graphs/adjacency_list/property_vector.hpp>
+#include <boost/graphs/adjacency_list/property_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_vector.hpp>
+#include <boost/graphs/adjacency_list/incidence_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_set.hpp>
+#include <boost/graphs/adjacency_list/out_vector.hpp>
+#include <boost/graphs/adjacency_list/out_list.hpp>
+#include <boost/graphs/adjacency_list/out_set.hpp>
+#include <boost/graphs/adjacency_list/in_vector.hpp>
+#include <boost/graphs/adjacency_list/in_list.hpp>
+#include <boost/graphs/adjacency_list/in_set.hpp>
+
+#include "typestr.hpp"
+#include "properties_traits.hpp"
+#include "incidence_traits.hpp"
+#include "out_edge_traits.hpp"
+#include "in_edge_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+// These are things that we can't do much about... Note that we can actually
+// generate all of these types prior to the definition of the edge store - it
+// seems a little odd since IncDesc is actually IN the edge store, but its
+// not instantiated until a little later.
+typedef int VertexProps;
+typedef int EdgeProps;
+typedef index_descriptor<size_t> VertexDesc;
+
+// Add an edge with the given properties to the implicit vertex.
+template <typename Props, typename Incs, typename Vertex, typename Edge>
+void undirected_add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep)
+{
+/*
+    typedef typename Props::property_descriptor PropDesc;
+    typedef typename Incs::incidence_descriptor IncDesc;
+    typedef insertion_result<IncDesc> Result;
+
+    size_t m = props.size();
+    size_t n = incs.size();
+
+    // Our global vertex.
+    Vertex u = VertexDesc(0);
+
+    // Insert algorithm: Try to stub out the edge locally first. If it succeeds,
+    // then add the global property, and finally bind the incidence and property
+    // descitpros into their respective "slots". Note that this is actually
+    // faster than the
+    Result r = incs.add(v);
+    if(r.succeeded()) {
+        PropDesc p = props.add(ep);
+        incs.bind(r.value, p);
+        props.bind(p, make_pair(u, v));
+
+        BOOST_ASSERT(props.size() == m + 1);
+        BOOST_ASSERT(incs.size() == n + 1);
+        cout << "  * added " << u << "," << v << " -> " << props.properties(p) << endl;
+    }
+    else if(r.retained()) {
+        PropDesc p = incs.properties(r.value);
+        cout << "  * exists " << u << "," << v << " -> " << props.properties(p) << endl;
+    }
+    else {
+        cout << "  * failed " << u << "," << v << endl;
+    }
+*/
+}
+
+template <typename Outs, typename Ins>
+void directed_add_edge(Outs& outs, Ins& ins, VertexDesc v, EdgeProps const& ep)
+{
+    typedef typename Outs::out_descriptor OutDesc;
+    typedef typename Ins::in_descriptor InDesc;
+    typedef insertion_result<OutDesc> Result;
+
+    size_t m = outs.size();
+
+    // Here, we're adding edge (u,v). Note that outs is implicitly a member of
+    // u and ins is a member of v.
+    VertexDesc u(0);
+
+    // Try to add the edge to the out list. If it succeeds then reciprocate the
+    // insertion for the in edge set and bind them together.
+    Result o = outs.add(v, ep);
+    if(o.succeeded()) {
+        Result i = ins.add(v, o.value);
+        outs.bind(o.value, i.value);
+
+        BOOST_ASSERT(outs.size() == m + 1);
+        BOOST_ASSERT(ins.size() == 1);
+        cout << "  * added " << u << "," << v << " -> " << outs.properties(o.value) << endl;
+    }
+    else if(o.retained()) {
+        cout << "  * exists " << u << "," << v << " -> " << outs.properties(o.value) << endl;
+    }
+}
+
+// Test the addition of edges as if we were adding them to an implicit vertex 0.
+template <typename Props, typename Incs>
+void undirected_add_edges(Props& props, Incs& incs)
+{
+    BOOST_ASSERT(props.empty());
+    BOOST_ASSERT(incs.empty());
+
+    // Add a bunch of implicit connections.
+    size_t const N = 5;
+    for(size_t i = 0; i < N; ++i) {
+        undirected_add_edge(props, incs, VertexDesc(i + 1), 2 * (i + 1));
+    }
+    BOOST_ASSERT(props.size() == N);
+    BOOST_ASSERT(incs.size() == N);
+
+    // Just for good measure, add antoher that duplicates the first.
+    undirected_add_edge(props, incs, VertexDesc(2), 1);
+}
+
+template <typename Outs, typename Ins>
+void directed_add_edges(Outs& outs, Ins&)
+{
+    BOOST_ASSERT(outs.empty());
+
+    // This is a little odd. The in edge set is actually specific to different
+    // vertices, so construct new, empty sets on the fly.
+
+    size_t const N = 5;
+    for(size_t i = 0; i < N; ++i) {
+        Ins ins;
+        directed_add_edge(outs, ins, VertexDesc(i + 1), 2 * (i + 1));
+    }
+
+    // Just for good measure, add antoher that duplicates the first.
+    Ins ins;
+    directed_add_edge(outs, ins, VertexDesc(2), 1);
+}
+
+template <typename EdgeStore>
+void
+undirected()
+{
+    cout << "--- undirected " << typestr<EdgeStore>() << " ---" << endl;
+
+    // Instantiate data structures related to the storage of edges and their
+    // properties.
+    typedef typename EdgeStore::template property_store<VertexDesc, EdgeProps>::type PropStore;
+    typedef typename EdgeStore::template incidence_store<VertexDesc>::type IncStore;
+
+    PropStore props;
+    IncStore incs;
+
+    cout << "  * " << typestr(properties_category(props)) << endl;
+    cout << "  * " << typestr(incidence_category(incs)) << endl;
+
+    cout << typestr<typename PropStore::vertex_descriptor>() << endl;
+    cout << typestr<typename PropStore::incidence_descriptor>() << endl;
+
+
+    undirected_add_edges(props, incs);
+}
+
+template <typename EdgeStore>
+void
+directed()
+{
+    cout << "--- directed " << typestr<EdgeStore>() << " ---" << endl;
+
+    // Instantiate data structures related to the storage of edges and their
+    // properties.
+    typedef typename EdgeStore::template out_store<VertexDesc, EdgeProps>::type OutStore;
+    typedef typename EdgeStore::template in_store<VertexDesc>::type InStore;
+
+    OutStore outs;
+    InStore ins;
+
+    cout << "  * " << typestr(out_edge_category(outs)) << endl;
+    cout << "  * " << typestr(in_edge_category(ins)) << endl;
+
+    directed_add_edges(outs, ins);
+}
+
+int main()
+{
+    undirected<edge_vector<>>();
+    undirected<edge_list<>>();
+    undirected<edge_set<>>();
+
+    directed<edge_vector<>>();
+    directed<edge_list<>>();
+    directed<edge_set<>>();
+
+   return 0;
+}
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,71 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/incidence_vector.hpp>
+#include <boost/graphs/adjacency_list/incidence_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_set.hpp>
+
+#include "typestr.hpp"
+#include "incidence_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> PropDesc;
+typedef std::pair<VertexDesc, PropDesc> Edge;
+typedef allocator<Edge> Alloc;
+typedef std::less<VertexDesc> Compare;
+
+template <typename IncStore, typename Vertex, typename Property>
+void add(IncStore& incs, Vertex v, Property p, associative_container_tag)
+{
+    typename IncStore::incidence_descriptor i = incs.add(v);
+    incs.bind(i, p);
+}
+
+template <typename IncStore, typename Vertex, typename Property>
+void add(IncStore& incs, Vertex v, Property p, sequence_tag)
+{
+    incs.add(v, p);
+}
+
+
+template <typename IncStore>
+void test_remove(IncStore& incs, stable_mutators_tag)
+{
+    // Kind of strange, but we can actually construct some types of descriptors
+    // withou an iterator.
+    size_t n = incs.size();
+    incs.remove(incs.find(VertexDesc(0)));
+    BOOST_ASSERT(incs.size() == n - 1);
+    cout << "  * num incs after removing " << incs.size() << endl;
+}
+
+template <typename IncStore>
+void test_remove(IncStore& incs, unstable_remove_tag)
+{ /* Can't remove elements. */ }
+
+template <typename IncStore>
+void test()
+{
+    IncStore incs;
+    cout << "--- " << typestr(incidence_category(incs)) << " ---" << endl;
+
+    // Add some edges
+    incs.add(VertexDesc(0), PropDesc(0));
+    incs.add(VertexDesc(1), PropDesc(1));
+    cout << "  * num incs after building: " << incs.size() << endl;
+
+    // Try to remove something
+    test_remove(incs, incidence_category(incs));
+}
+
+int main()
+{
+    test<incidence_vector<Edge, Alloc>>();
+    test<incidence_list<Edge, Alloc>>();
+    test<incidence_set<Edge, Compare, Alloc>>();
+
+    return 0;
+}
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,57 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/in_vector.hpp>
+#include <boost/graphs/adjacency_list/in_list.hpp>
+#include <boost/graphs/adjacency_list/in_set.hpp>
+
+#include "typestr.hpp"
+#include "in_edge_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> OutDesc;
+typedef pair<VertexDesc, OutDesc> InEdge;
+typedef allocator<InEdge> Alloc;
+typedef less<VertexDesc> Compare;
+
+template <typename Ins>
+void test_remove(Ins& ins, stable_mutators_tag)
+{
+    size_t n = ins.size();
+    ins.remove(ins.find(3));
+    BOOST_ASSERT(ins.size() == n - 1);
+    cout << "  * size after remove: " << ins.size() << endl;
+}
+
+template <typename Ins>
+void test_remove(Ins&, unstable_remove_tag)
+{ /* Don't do anything. */ }
+
+template <typename Ins>
+void test()
+{
+    Ins ins;
+    cout << "--- " << typestr(in_edge_category(ins)) << " ---" <<  endl;
+
+    // Add some vertices.
+    BOOST_ASSERT(ins.empty());
+    for(int i = 0; i < 5; ++i) {
+        ins.add(VertexDesc(i), OutDesc(i + 1));
+    }
+    BOOST_ASSERT(ins.size() == 5);
+    cout << "  * size after building: " << ins.size() << endl;
+
+    test_remove(ins, in_edge_category(ins));
+}
+
+int main()
+{
+    test<in_vector<InEdge, Alloc>>();
+    test<in_list<InEdge, Alloc>>();
+    test<in_set<InEdge, Compare, Alloc>>();
+
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,59 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/out_vector.hpp>
+#include <boost/graphs/adjacency_list/out_list.hpp>
+#include <boost/graphs/adjacency_list/out_set.hpp>
+
+#include "typestr.hpp"
+#include "out_edge_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> InDesc;
+typedef int EdgeProps;
+typedef pair<VertexDesc, pair<EdgeProps, InDesc>> OutEdge;
+typedef allocator<OutEdge> Alloc;
+typedef less<VertexDesc> Compare;
+
+template <typename Outs>
+void test_remove(Outs& outs, stable_mutators_tag)
+{
+    size_t n = outs.size();
+    outs.remove(outs.find(3));
+    BOOST_ASSERT(outs.size() == n - 1);
+    cout << "  * size after remove: " << outs.size() << endl;
+}
+
+template <typename Outs>
+void test_remove(Outs& outs, unstable_remove_tag)
+{ /* Don't do anything. */ }
+
+template <typename Outs>
+void test()
+{
+    Outs outs;
+    cout << "--- " << typestr(out_edge_category(outs)) << " ---" <<  endl;
+
+    // Add some vertices.
+    BOOST_ASSERT(outs.empty());
+    for(int i = 0; i < 5; ++i) {
+        outs.add(VertexDesc(i), i * i);
+    }
+    BOOST_ASSERT(outs.size() == 5);
+    cout << "  * size after building: " << outs.size() << endl;
+
+    test_remove(outs, out_edge_category(outs));
+}
+
+int main()
+{
+    test<out_vector<OutEdge, Alloc>>();
+    test<out_list<OutEdge, Alloc>>();
+    test<out_set<OutEdge, Compare, Alloc>>();
+
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_props.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_props.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,61 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/property_vector.hpp>
+#include <boost/graphs/adjacency_list/property_list.hpp>
+
+#include "typestr.hpp"
+#include "properties_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+
+typedef int EdgeProperties;
+typedef descriptor_traits<std::list<int>>::descriptor_type IncDesc;
+typedef descriptor_traits<std::list<int>>::descriptor_type VertexDesc;
+
+template <typename PropSet>
+void test_remove(PropSet& props, stable_mutators_tag)
+{
+    size_t n = props.size();
+    props.remove(props.find(5));
+    BOOST_ASSERT(props.size() == n - 1);
+    std::cout << "num props after remove: " << props.size() << endl;
+}
+
+template <typename PropSet>
+void test_remove(PropSet& props, unstable_remove_tag)
+{ /* Can't remove! */ }
+
+template <typename PropSet>
+void test()
+{
+    typedef typename PropSet::property_descriptor PropDesc;
+
+    cout << "--- " << typestr<PropSet>() << " ---" << endl;
+
+    // Add some properties
+    size_t const N = 10;
+    PropSet props;
+    for(size_t i = 0; i < N; ++i) {
+        props.add(i);
+    }
+    BOOST_ASSERT(props.size() == N);
+    cout << "num props after build: " << props.size() << endl;
+
+    test_remove(props, properties_category(props));
+}
+
+int main()
+{
+    typedef pair<VertexDesc, IncDesc> End;
+    typedef pair<End, End> EndPair;
+    typedef pair<EdgeProperties, EndPair> StoredEdge;
+    typedef allocator<StoredEdge> Allocator;
+
+    test<property_vector<StoredEdge, Allocator>>();
+    test<property_list<StoredEdge, Allocator>>();
+
+    return 0;
+}
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_verts.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_verts.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,88 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/vertex_vector.hpp>
+#include <boost/graphs/adjacency_list/vertex_list.hpp>
+#include <boost/graphs/adjacency_list/vertex_set.hpp>
+#include <boost/graphs/adjacency_list/vertex_map.hpp>
+
+#include "typestr.hpp"
+#include "vertices_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+struct unlabled_vertex_tag { };
+struct labeled_vertex_tag { };
+
+// A fake vertex type.
+struct Vertex
+{
+    typedef int vertex_properties;
+
+    Vertex(int x)
+        : value(x)
+    { }
+
+    int& properties()
+    { return value; }
+
+    int const& properties() const
+    { return value; }
+
+    int value;
+};
+
+template <typename Verts>
+void populate(Verts& verts, simple_vertex_store_tag)
+{
+    for(int i = 0; i < 5; ++i) {
+        verts.add(i);
+    }
+}
+template <typename Verts>
+void populate(Verts& verts, mapped_vertex_store_tag)
+{
+    for(int i = 0; i < 5; ++i) {
+        verts.add(i, 2 * i);
+    }
+}
+
+template <typename Verts>
+void test_remove(Verts& verts, stable_mutators_tag)
+{
+    verts.remove(3);
+    cout << "num verts after remove: " << verts.size() << endl;
+}
+
+template <typename Verts>
+void test_remove(Verts& vs, unstable_remove_tag)
+{ /* Noop for unstable removes */ }
+
+template <typename Verts>
+void test()
+{
+    typedef typename Verts::template store<Vertex>::type Store;
+    typedef typename Verts::vertex_descriptor Descriptor;
+
+    Store verts;
+    cout << "--- " << typestr(verts) << " ---" << endl;
+
+    populate(verts, vertices_category(verts));
+    cout << "num verts after building: " << verts.size() << endl;
+
+    Descriptor d = verts.find(3);
+    cout << "value of vertex properties: " << verts.properties(d) << endl;
+
+    test_remove(verts, vertices_category(verts));
+}
+
+int main()
+{
+    test<vertex_vector<>>();
+    test<vertex_list<>>();
+    test<vertex_set<>>();
+    test<vertex_map<int>>();
+
+    return 0;
+}
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/typestr.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/typestr.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,25 @@
+
+#ifndef DEMANGLE_HPP
+#define DEMANGLE_HPP
+
+#include <string>
+#include <cstring>
+#include <typeinfo>
+#include <cxxabi.h>
+
+template <typename T>
+std::string
+typestr()
+{
+    std::size_t n = 2048;
+    char buf[2048];
+    abi::__cxa_demangle(typeid(T).name(), buf, &n, 0);
+    return std::string(buf, ::strlen(buf));
+}
+
+template <typename T>
+inline std::string
+typestr(T const&)
+{ return typestr<T>(); }
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/un.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/un.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,375 @@
+
+#include <iostream>
+
+#include <boost/assert.hpp>
+#include <boost/utility.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+
+#include "typestr.hpp"
+#include "incidence_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef int City;
+typedef int Road;
+
+void list_list();
+void vec_vec();
+void set_set();
+
+namespace dispatch
+{
+    bool allows_parallel_edges(unique_associative_container_tag)
+    { return false; }
+
+    bool allows_parallel_edges(multiple_associative_container_tag)
+    { return false; }
+
+    bool allows_parallel_edges(sequence_tag)
+    { return true; }
+}
+
+template <typename Graph>
+bool allows_parallel_edges(Graph const& g)
+{
+    typedef typename Graph::incidence_store Store;
+    return dispatch::allows_parallel_edges(typename incidence_traits<Store>::category());
+}
+
+template <typename Graph>
+void print_types(const Graph&)
+{
+    // cout << typestr<typename Graph::property_descriptor>() << endl;
+    cout << "  * " << typestr<typename Graph::vertex_descriptor>() << endl;
+    cout << "  * " << typestr<typename Graph::edge_descriptor>() << endl;
+    // cout << typestr<typename Graph::property_store>() << endl;
+    // cout << typestr<typename Graph::vertex_store>() << endl;
+    // cout << typestr<typename Graph::incidence_store>() << endl;
+}
+
+template <typename Graph>
+void test_add_vertices()
+{
+    cout << "  * add verts" << endl;
+    Graph g;
+    list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+}
+
+template <typename Graph>
+void test_add_remove_vertices()
+{
+    cout << "  * add verts" << endl;
+    Graph g;
+    list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    BOOST_ASSERT(g.num_vertices() == 5);
+
+    cout << "  * remove verts" << endl;
+    while(!V.empty()) {
+        g.remove_vertex(V.front());
+        V.pop_front();
+    }
+    BOOST_ASSERT(g.num_vertices() == 0);
+}
+
+template <typename Graph>
+void test_add_edges()
+{
+    cout << "  * add edges" << endl;
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+    BOOST_ASSERT(g.degree(V[0]) == 2);
+}
+
+template <typename Graph>
+void test_add_remove_edges()
+{
+    Graph g;
+
+    cout << "  * add edges" << endl;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    E.push_back(g.add_edge(V[0], V[1]));
+    E.push_back(g.add_edge(V[1], V[2]));
+    E.push_back(g.add_edge(V[2], V[0]));
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    cout << "  * remove edges" << endl;
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.num_edges() == 2);
+    BOOST_ASSERT(g.degree(V[1]) == 1);
+    E.pop_front();
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    E.pop_front();
+}
+
+template <typename Graph>
+void test_disconnect_vertex()
+{
+    cout << "  * disconnecting vertex" << std::endl;
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_edges(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+// This is a little different than above. We remove a vertex from the triangle,
+// which implicitly disconnects it.
+template <typename Graph>
+void test_implicit_disconnect_vertex()
+{
+    cout << "  * removing conntected vertex" << endl;
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 2);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+template <typename Graph>
+void test_add_multi_edges()
+{
+    cout << "  * adding parallel edges" << endl;
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 10);
+    g.add_edge(v, u, 20);
+    g.add_edge(u, v, 30);
+    g.add_edge(v, u, 40);
+    BOOST_ASSERT(g.num_vertices() == 2);
+
+    // If there are no parallel edges, then there should only be one edge.
+    if(allows_parallel_edges(g)) {
+        BOOST_ASSERT(g.num_edges() == 4);
+    }
+    else {
+        BOOST_ASSERT(g.num_edges() == 1);
+    }
+}
+
+template <typename Graph>
+void test_remove_multi_edges()
+{
+    cout << "  * removing parallel edges" << endl;
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    g.remove_edges(u, v);
+    BOOST_ASSERT(g.num_edges() == 0);
+    BOOST_ASSERT(g.degree(u) == 0);
+    BOOST_ASSERT(g.degree(v) == 0);
+}
+
+
+template <typename Graph>
+void test_edge()
+{
+    cout << "  * find edges" << endl;
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 2);
+
+    // Test for existence
+    BOOST_ASSERT(g.edge(V[0], V[1]));
+    BOOST_ASSERT(g.edge(V[1], V[0]));
+    BOOST_ASSERT(g.edge(V[1], V[2]));
+    BOOST_ASSERT(g.edge(V[2], V[1]));
+
+    // Test for inexstence
+    BOOST_ASSERT(!g.edge(V[0], V[2]));
+    BOOST_ASSERT(!g.edge(V[2], V[0]));
+}
+
+template <typename Graph>
+void test_vertex_iterator()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+
+    cout << "  * testing vertex iterator" << endl;
+    typename Graph::vertex_range rng = g.vertices();
+    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+    BOOST_ASSERT(*rng.first++ == V[0]);
+    BOOST_ASSERT(*rng.first++ == V[1]);
+    BOOST_ASSERT(*rng.first++ == V[2]);
+}
+
+template <typename Graph>
+void test_edge_iterator()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    vector<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    E.push_back(g.add_edge(V[0], V[1], 10));
+    E.push_back(g.add_edge(V[1], V[2], 20));
+    E.push_back(g.add_edge(V[2], V[0], 30));
+
+    cout << "  * testing edge iterator" << endl;
+
+    typename Graph::edge_range rng = g.edges();
+    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+    BOOST_ASSERT(*rng.first++ == E[0]);
+    BOOST_ASSERT(*rng.first++ == E[1]);
+    BOOST_ASSERT(*rng.first++ == E[2]);
+}
+
+template <typename Graph>
+void test_incidence_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    cout << "  * incidence iterator" << endl;
+    typename Graph::incident_edge_range x = g.incident_edges(v);
+    typename Graph::incident_edge_iterator i = x.first;
+    for(typename Graph::incident_edge_iterator i = x.first; i != x.second; ++i) {
+        BOOST_ASSERT(*i);
+    }
+}
+
+template <typename Graph>
+void test_adjacency_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    cout << "  * adjacency iterator" << endl;
+    typename Graph::adjacent_vertex_range x = g.adjacent_vertices(u);
+    for( ; x.first != x.second; ++x.first) {
+        typename Graph::vertex_descriptor o = *x.first;
+        BOOST_ASSERT(o == v);
+    }
+}
+
+int main()
+{
+    vec_vec();
+    list_list();
+    set_set();
+
+    return 0;
+}
+
+void vec_vec()
+{
+    cout << "---- vec/vec ----" << endl;
+    typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
+    test_add_vertices<Graph>();
+    test_add_edges<Graph>();
+    test_add_multi_edges<Graph>();
+    test_edge<Graph>();
+    test_vertex_iterator<Graph>();
+    test_edge_iterator<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+}
+
+void list_list()
+{
+    cout << "---- list/list ----" << endl;
+    typedef undirected_graph<City, Road, vertex_list<>, edge_list<> > Graph;
+    test_add_remove_vertices<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_edge<Graph>();
+    test_vertex_iterator<Graph>();
+    test_edge_iterator<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+}
+
+
+void set_set()
+{
+    cout << "---- set/set ----" << endl;
+    typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
+    test_add_remove_vertices<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_edge<Graph>();
+    test_vertex_iterator<Graph>();
+    test_edge_iterator<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+}
+

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertices_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertices_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,39 @@
+
+#ifndef VERTICES_TRAITS_HPP
+#define VERTICES_TRAITS_HPP
+
+struct simple_vertex_store_tag { };
+struct mapped_vertex_store_tag { };
+
+struct vertex_vector_tag : simple_vertex_store_tag, unstable_remove_tag { };
+struct vertex_list_tag : simple_vertex_store_tag, stable_mutators_tag { };
+struct vertex_set_tag : simple_vertex_store_tag, stable_mutators_tag { };
+struct vertex_map_tag : mapped_vertex_store_tag, stable_mutators_tag { };
+
+template <typename Verts>
+struct vertices_traits
+{ typedef typename Verts::category category; };
+
+template <typename Verts>
+typename vertices_traits<Verts>::category
+vertices_category(Verts const&)
+{ return typename vertices_traits<Verts>::category(); }
+
+
+template <typename Vertex, typename Alloc>
+struct vertices_traits<vertices_vector<Vertex, Alloc>>
+{ typedef vertex_vector_tag category; };
+
+template <typename Vertex, typename Alloc>
+struct vertices_traits<vertices_list<Vertex, Alloc>>
+{ typedef vertex_list_tag category; };
+
+template <typename Vertex, typename Compare, typename Alloc>
+struct vertices_traits<vertices_set<Vertex, Compare, Alloc>>
+{ typedef vertex_set_tag category; };
+
+template <typename Vertex, typename Key, typename Compare, typename Alloc>
+struct vertices_traits<vertices_map<Vertex, Key, Compare, Alloc>>
+{ typedef vertex_map_tag category; };
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/visitors.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/visitors.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
@@ -0,0 +1,92 @@
+
+#include <iostream>
+
+#include <boost/function.hpp>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/algorithms/search.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+
+
+struct v1 : default_search_visitor
+{
+    int n;
+    v1() : n(0) { }
+    v1(int n) : n(n) { }
+
+    template <typename G, typename V>
+    void start_vertex(G const&, V)
+    { cout << "v1 - " << n << endl; }
+};
+
+struct v2 : default_search_visitor
+{
+    int n;
+    v2() : n(0) { }
+    v2(int n) : n(n) { }
+
+    template <typename G, typename V>
+    void start_vertex(G const&, V)
+    { cout << "v2 - " << n << endl; }
+};
+
+struct v3 : default_search_visitor
+{
+    int n;
+    v3() : n(0) { }
+    v3(int n) : n(n) { }
+
+    template <typename G, typename V>
+    void start_vertex(G const&, V)
+    { cout << "v3 - " << n << endl; }
+};
+
+struct my_start_visitor
+{
+    template <typename G, typename V>
+    void operator()(G const&, V)
+    { cout << "visiting function object" << endl; }
+};
+
+void test(int, int)
+{ cout << "visiting free function" << endl; }
+
+
+void another_test(int, int)
+{ cout << "visiting wrapped function" << endl; }
+
+
+int main()
+{
+    v1 a(1);
+    v2 b(2);
+    v3 c(3);
+
+    search_visitor<v1, v2, v3> p;
+    p.start_vertex(0, 0);
+    cout << endl;
+
+    search_visitor<v1, v2, v3> q(a, b, c);
+    q.start_vertex(0, 0);
+    cout << endl;
+
+    search_visitor<start_vertex_visitor<void (*)(int, int)>, v1> r(test, a);
+    r.start_vertex(0, 0);
+    cout << endl;
+
+    // Make a fairly complex search visitor.
+    function<void (int, int)> func = another_test;
+    make_search_visitor(
+            on_start_vertex(test),
+            on_start_vertex(my_start_visitor()),
+            on_start_vertex(func),
+            v2(1),
+            v3(2)
+        ).start_vertex(0, 0);
+    cout << endl;
+
+    return 0;
+}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,200 +0,0 @@
-
-#include <iostream>
-
-#include <boost/next_prior.hpp>
-
-#include <boost/graphs/adjacency_list/edge_vector.hpp>
-#include <boost/graphs/adjacency_list/edge_list.hpp>
-#include <boost/graphs/adjacency_list/edge_set.hpp>
-
-#include <boost/graphs/adjacency_list/property_vector.hpp>
-#include <boost/graphs/adjacency_list/property_list.hpp>
-#include <boost/graphs/adjacency_list/incidence_vector.hpp>
-#include <boost/graphs/adjacency_list/incidence_list.hpp>
-#include <boost/graphs/adjacency_list/incidence_set.hpp>
-#include <boost/graphs/adjacency_list/out_vector.hpp>
-#include <boost/graphs/adjacency_list/out_list.hpp>
-#include <boost/graphs/adjacency_list/out_set.hpp>
-#include <boost/graphs/adjacency_list/in_vector.hpp>
-#include <boost/graphs/adjacency_list/in_list.hpp>
-#include <boost/graphs/adjacency_list/in_set.hpp>
-
-#include "typestr.hpp"
-#include "properties_traits.hpp"
-#include "incidence_traits.hpp"
-#include "out_edge_traits.hpp"
-#include "in_edge_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-// These are things that we can't do much about... Note that we can actually
-// generate all of these types prior to the definition of the edge store - it
-// seems a little odd since IncDesc is actually IN the edge store, but its
-// not instantiated until a little later.
-typedef int VertexProps;
-typedef int EdgeProps;
-typedef index_descriptor<size_t> VertexDesc;
-
-// Add an edge with the given properties to the implicit vertex.
-template <typename Props, typename Incs, typename Vertex, typename Edge>
-void undirected_add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep)
-{
-/*
-    typedef typename Props::property_descriptor PropDesc;
-    typedef typename Incs::incidence_descriptor IncDesc;
-    typedef insertion_result<IncDesc> Result;
-
-    size_t m = props.size();
-    size_t n = incs.size();
-
-    // Our global vertex.
-    Vertex u = VertexDesc(0);
-
-    // Insert algorithm: Try to stub out the edge locally first. If it succeeds,
-    // then add the global property, and finally bind the incidence and property
-    // descitpros into their respective "slots". Note that this is actually
-    // faster than the
-    Result r = incs.add(v);
-    if(r.succeeded()) {
-        PropDesc p = props.add(ep);
-        incs.bind(r.value, p);
-        props.bind(p, make_pair(u, v));
-
-        BOOST_ASSERT(props.size() == m + 1);
-        BOOST_ASSERT(incs.size() == n + 1);
-        cout << "  * added " << u << "," << v << " -> " << props.properties(p) << endl;
-    }
-    else if(r.retained()) {
-        PropDesc p = incs.properties(r.value);
-        cout << "  * exists " << u << "," << v << " -> " << props.properties(p) << endl;
-    }
-    else {
-        cout << "  * failed " << u << "," << v << endl;
-    }
-*/
-}
-
-template <typename Outs, typename Ins>
-void directed_add_edge(Outs& outs, Ins& ins, VertexDesc v, EdgeProps const& ep)
-{
-    typedef typename Outs::out_descriptor OutDesc;
-    typedef typename Ins::in_descriptor InDesc;
-    typedef insertion_result<OutDesc> Result;
-
-    size_t m = outs.size();
-
-    // Here, we're adding edge (u,v). Note that outs is implicitly a member of
-    // u and ins is a member of v.
-    VertexDesc u(0);
-
-    // Try to add the edge to the out list. If it succeeds then reciprocate the
-    // insertion for the in edge set and bind them together.
-    Result o = outs.add(v, ep);
-    if(o.succeeded()) {
-        Result i = ins.add(v, o.value);
-        outs.bind(o.value, i.value);
-
-        BOOST_ASSERT(outs.size() == m + 1);
-        BOOST_ASSERT(ins.size() == 1);
-        cout << "  * added " << u << "," << v << " -> " << outs.properties(o.value) << endl;
-    }
-    else if(o.retained()) {
-        cout << "  * exists " << u << "," << v << " -> " << outs.properties(o.value) << endl;
-    }
-}
-
-// Test the addition of edges as if we were adding them to an implicit vertex 0.
-template <typename Props, typename Incs>
-void undirected_add_edges(Props& props, Incs& incs)
-{
-    BOOST_ASSERT(props.empty());
-    BOOST_ASSERT(incs.empty());
-
-    // Add a bunch of implicit connections.
-    size_t const N = 5;
-    for(size_t i = 0; i < N; ++i) {
-        undirected_add_edge(props, incs, VertexDesc(i + 1), 2 * (i + 1));
-    }
-    BOOST_ASSERT(props.size() == N);
-    BOOST_ASSERT(incs.size() == N);
-
-    // Just for good measure, add antoher that duplicates the first.
-    undirected_add_edge(props, incs, VertexDesc(2), 1);
-}
-
-template <typename Outs, typename Ins>
-void directed_add_edges(Outs& outs, Ins&)
-{
-    BOOST_ASSERT(outs.empty());
-
-    // This is a little odd. The in edge set is actually specific to different
-    // vertices, so construct new, empty sets on the fly.
-
-    size_t const N = 5;
-    for(size_t i = 0; i < N; ++i) {
-        Ins ins;
-        directed_add_edge(outs, ins, VertexDesc(i + 1), 2 * (i + 1));
-    }
-
-    // Just for good measure, add antoher that duplicates the first.
-    Ins ins;
-    directed_add_edge(outs, ins, VertexDesc(2), 1);
-}
-
-template <typename EdgeStore>
-void
-undirected()
-{
-    cout << "--- undirected " << typestr<EdgeStore>() << " ---" << endl;
-
-    // Instantiate data structures related to the storage of edges and their
-    // properties.
-    typedef typename EdgeStore::template property_store<VertexDesc, EdgeProps>::type PropStore;
-    typedef typename EdgeStore::template incidence_store<VertexDesc>::type IncStore;
-
-    PropStore props;
-    IncStore incs;
-
-    cout << "  * " << typestr(properties_category(props)) << endl;
-    cout << "  * " << typestr(incidence_category(incs)) << endl;
-
-    cout << typestr<typename PropStore::vertex_descriptor>() << endl;
-    cout << typestr<typename PropStore::incidence_descriptor>() << endl;
-
-
-    undirected_add_edges(props, incs);
-}
-
-template <typename EdgeStore>
-void
-directed()
-{
-    cout << "--- directed " << typestr<EdgeStore>() << " ---" << endl;
-
-    // Instantiate data structures related to the storage of edges and their
-    // properties.
-    typedef typename EdgeStore::template out_store<VertexDesc, EdgeProps>::type OutStore;
-    typedef typename EdgeStore::template in_store<VertexDesc>::type InStore;
-
-    OutStore outs;
-    InStore ins;
-
-    cout << "  * " << typestr(out_edge_category(outs)) << endl;
-    cout << "  * " << typestr(in_edge_category(ins)) << endl;
-
-    directed_add_edges(outs, ins);
-}
-
-int main()
-{
-    undirected<edge_vector<>>();
-    undirected<edge_list<>>();
-    undirected<edge_set<>>();
-
-    directed<edge_vector<>>();
-    directed<edge_list<>>();
-    directed<edge_set<>>();
-
-   return 0;
-}
\ No newline at end of file

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,71 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/incidence_vector.hpp>
-#include <boost/graphs/adjacency_list/incidence_list.hpp>
-#include <boost/graphs/adjacency_list/incidence_set.hpp>
-
-#include "typestr.hpp"
-#include "incidence_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> PropDesc;
-typedef std::pair<VertexDesc, PropDesc> Edge;
-typedef allocator<Edge> Alloc;
-typedef std::less<VertexDesc> Compare;
-
-template <typename IncStore, typename Vertex, typename Property>
-void add(IncStore& incs, Vertex v, Property p, associative_container_tag)
-{
-    typename IncStore::incidence_descriptor i = incs.add(v);
-    incs.bind(i, p);
-}
-
-template <typename IncStore, typename Vertex, typename Property>
-void add(IncStore& incs, Vertex v, Property p, sequence_tag)
-{
-    incs.add(v, p);
-}
-
-
-template <typename IncStore>
-void test_remove(IncStore& incs, stable_mutators_tag)
-{
-    // Kind of strange, but we can actually construct some types of descriptors
-    // withou an iterator.
-    size_t n = incs.size();
-    incs.remove(incs.find(VertexDesc(0)));
-    BOOST_ASSERT(incs.size() == n - 1);
-    cout << "  * num incs after removing " << incs.size() << endl;
-}
-
-template <typename IncStore>
-void test_remove(IncStore& incs, unstable_remove_tag)
-{ /* Can't remove elements. */ }
-
-template <typename IncStore>
-void test()
-{
-    IncStore incs;
-    cout << "--- " << typestr(incidence_category(incs)) << " ---" << endl;
-
-    // Add some edges
-    incs.add(VertexDesc(0), PropDesc(0));
-    incs.add(VertexDesc(1), PropDesc(1));
-    cout << "  * num incs after building: " << incs.size() << endl;
-
-    // Try to remove something
-    test_remove(incs, incidence_category(incs));
-}
-
-int main()
-{
-    test<incidence_vector<Edge, Alloc>>();
-    test<incidence_list<Edge, Alloc>>();
-    test<incidence_set<Edge, Compare, Alloc>>();
-
-    return 0;
-}
\ No newline at end of file

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,57 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/in_vector.hpp>
-#include <boost/graphs/adjacency_list/in_list.hpp>
-#include <boost/graphs/adjacency_list/in_set.hpp>
-
-#include "typestr.hpp"
-#include "in_edge_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> OutDesc;
-typedef pair<VertexDesc, OutDesc> InEdge;
-typedef allocator<InEdge> Alloc;
-typedef less<VertexDesc> Compare;
-
-template <typename Ins>
-void test_remove(Ins& ins, stable_mutators_tag)
-{
-    size_t n = ins.size();
-    ins.remove(ins.find(3));
-    BOOST_ASSERT(ins.size() == n - 1);
-    cout << "  * size after remove: " << ins.size() << endl;
-}
-
-template <typename Ins>
-void test_remove(Ins&, unstable_remove_tag)
-{ /* Don't do anything. */ }
-
-template <typename Ins>
-void test()
-{
-    Ins ins;
-    cout << "--- " << typestr(in_edge_category(ins)) << " ---" <<  endl;
-
-    // Add some vertices.
-    BOOST_ASSERT(ins.empty());
-    for(int i = 0; i < 5; ++i) {
-        ins.add(VertexDesc(i), OutDesc(i + 1));
-    }
-    BOOST_ASSERT(ins.size() == 5);
-    cout << "  * size after building: " << ins.size() << endl;
-
-    test_remove(ins, in_edge_category(ins));
-}
-
-int main()
-{
-    test<in_vector<InEdge, Alloc>>();
-    test<in_list<InEdge, Alloc>>();
-    test<in_set<InEdge, Compare, Alloc>>();
-
-    return 0;
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,59 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/out_vector.hpp>
-#include <boost/graphs/adjacency_list/out_list.hpp>
-#include <boost/graphs/adjacency_list/out_set.hpp>
-
-#include "typestr.hpp"
-#include "out_edge_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-
-typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> InDesc;
-typedef int EdgeProps;
-typedef pair<VertexDesc, pair<EdgeProps, InDesc>> OutEdge;
-typedef allocator<OutEdge> Alloc;
-typedef less<VertexDesc> Compare;
-
-template <typename Outs>
-void test_remove(Outs& outs, stable_mutators_tag)
-{
-    size_t n = outs.size();
-    outs.remove(outs.find(3));
-    BOOST_ASSERT(outs.size() == n - 1);
-    cout << "  * size after remove: " << outs.size() << endl;
-}
-
-template <typename Outs>
-void test_remove(Outs& outs, unstable_remove_tag)
-{ /* Don't do anything. */ }
-
-template <typename Outs>
-void test()
-{
-    Outs outs;
-    cout << "--- " << typestr(out_edge_category(outs)) << " ---" <<  endl;
-
-    // Add some vertices.
-    BOOST_ASSERT(outs.empty());
-    for(int i = 0; i < 5; ++i) {
-        outs.add(VertexDesc(i), i * i);
-    }
-    BOOST_ASSERT(outs.size() == 5);
-    cout << "  * size after building: " << outs.size() << endl;
-
-    test_remove(outs, out_edge_category(outs));
-}
-
-int main()
-{
-    test<out_vector<OutEdge, Alloc>>();
-    test<out_list<OutEdge, Alloc>>();
-    test<out_set<OutEdge, Compare, Alloc>>();
-
-    return 0;
-}

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,61 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/property_vector.hpp>
-#include <boost/graphs/adjacency_list/property_list.hpp>
-
-#include "typestr.hpp"
-#include "properties_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-
-typedef int EdgeProperties;
-typedef descriptor_traits<std::list<int>>::descriptor_type IncDesc;
-typedef descriptor_traits<std::list<int>>::descriptor_type VertexDesc;
-
-template <typename PropSet>
-void test_remove(PropSet& props, stable_mutators_tag)
-{
-    size_t n = props.size();
-    props.remove(props.find(5));
-    BOOST_ASSERT(props.size() == n - 1);
-    std::cout << "num props after remove: " << props.size() << endl;
-}
-
-template <typename PropSet>
-void test_remove(PropSet& props, unstable_remove_tag)
-{ /* Can't remove! */ }
-
-template <typename PropSet>
-void test()
-{
-    typedef typename PropSet::property_descriptor PropDesc;
-
-    cout << "--- " << typestr<PropSet>() << " ---" << endl;
-
-    // Add some properties
-    size_t const N = 10;
-    PropSet props;
-    for(size_t i = 0; i < N; ++i) {
-        props.add(i);
-    }
-    BOOST_ASSERT(props.size() == N);
-    cout << "num props after build: " << props.size() << endl;
-
-    test_remove(props, properties_category(props));
-}
-
-int main()
-{
-    typedef pair<VertexDesc, IncDesc> End;
-    typedef pair<End, End> EndPair;
-    typedef pair<EdgeProperties, EndPair> StoredEdge;
-    typedef allocator<StoredEdge> Allocator;
-
-    test<property_vector<StoredEdge, Allocator>>();
-    test<property_list<StoredEdge, Allocator>>();
-
-    return 0;
-}
\ No newline at end of file

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,88 +0,0 @@
-
-#include <iostream>
-
-#include <boost/graphs/adjacency_list/vertex_vector.hpp>
-#include <boost/graphs/adjacency_list/vertex_list.hpp>
-#include <boost/graphs/adjacency_list/vertex_set.hpp>
-#include <boost/graphs/adjacency_list/vertex_map.hpp>
-
-#include "typestr.hpp"
-#include "vertices_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-struct unlabled_vertex_tag { };
-struct labeled_vertex_tag { };
-
-// A fake vertex type.
-struct Vertex
-{
-    typedef int vertex_properties;
-
-    Vertex(int x)
-        : value(x)
-    { }
-
-    int& properties()
-    { return value; }
-
-    int const& properties() const
-    { return value; }
-
-    int value;
-};
-
-template <typename Verts>
-void populate(Verts& verts, simple_vertex_store_tag)
-{
-    for(int i = 0; i < 5; ++i) {
-        verts.add(i);
-    }
-}
-template <typename Verts>
-void populate(Verts& verts, mapped_vertex_store_tag)
-{
-    for(int i = 0; i < 5; ++i) {
-        verts.add(i, 2 * i);
-    }
-}
-
-template <typename Verts>
-void test_remove(Verts& verts, stable_mutators_tag)
-{
-    verts.remove(3);
-    cout << "num verts after remove: " << verts.size() << endl;
-}
-
-template <typename Verts>
-void test_remove(Verts& vs, unstable_remove_tag)
-{ /* Noop for unstable removes */ }
-
-template <typename Verts>
-void test()
-{
-    typedef typename Verts::template store<Vertex>::type Store;
-    typedef typename Verts::vertex_descriptor Descriptor;
-
-    Store verts;
-    cout << "--- " << typestr(verts) << " ---" << endl;
-
-    populate(verts, vertices_category(verts));
-    cout << "num verts after building: " << verts.size() << endl;
-
-    Descriptor d = verts.find(3);
-    cout << "value of vertex properties: " << verts.properties(d) << endl;
-
-    test_remove(verts, vertices_category(verts));
-}
-
-int main()
-{
-    test<vertex_vector<>>();
-    test<vertex_list<>>();
-    test<vertex_set<>>();
-    test<vertex_map<int>>();
-
-    return 0;
-}
\ No newline at end of file

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,25 +0,0 @@
-
-#ifndef DEMANGLE_HPP
-#define DEMANGLE_HPP
-
-#include <string>
-#include <cstring>
-#include <typeinfo>
-#include <cxxabi.h>
-
-template <typename T>
-std::string
-typestr()
-{
-    std::size_t n = 2048;
-    char buf[2048];
-    abi::__cxa_demangle(typeid(T).name(), buf, &n, 0);
-    return std::string(buf, ::strlen(buf));
-}
-
-template <typename T>
-inline std::string
-typestr(T const&)
-{ return typestr<T>(); }
-
-#endif

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,375 +0,0 @@
-
-#include <iostream>
-
-#include <boost/assert.hpp>
-#include <boost/utility.hpp>
-#include <boost/graphs/adjacency_list/undirected_graph.hpp>
-
-#include "typestr.hpp"
-#include "incidence_traits.hpp"
-
-using namespace std;
-using namespace boost;
-
-typedef int City;
-typedef int Road;
-
-void list_list();
-void vec_vec();
-void set_set();
-
-namespace dispatch
-{
-    bool allows_parallel_edges(unique_associative_container_tag)
-    { return false; }
-
-    bool allows_parallel_edges(multiple_associative_container_tag)
-    { return false; }
-
-    bool allows_parallel_edges(sequence_tag)
-    { return true; }
-}
-
-template <typename Graph>
-bool allows_parallel_edges(Graph const& g)
-{
-    typedef typename Graph::incidence_store Store;
-    return dispatch::allows_parallel_edges(typename incidence_traits<Store>::category());
-}
-
-template <typename Graph>
-void print_types(const Graph&)
-{
-    // cout << typestr<typename Graph::property_descriptor>() << endl;
-    cout << "  * " << typestr<typename Graph::vertex_descriptor>() << endl;
-    cout << "  * " << typestr<typename Graph::edge_descriptor>() << endl;
-    // cout << typestr<typename Graph::property_store>() << endl;
-    // cout << typestr<typename Graph::vertex_store>() << endl;
-    // cout << typestr<typename Graph::incidence_store>() << endl;
-}
-
-template <typename Graph>
-void test_add_vertices()
-{
-    cout << "  * add verts" << endl;
-    Graph g;
-    list<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 5; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-}
-
-template <typename Graph>
-void test_add_remove_vertices()
-{
-    cout << "  * add verts" << endl;
-    Graph g;
-    list<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 5; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    BOOST_ASSERT(g.num_vertices() == 5);
-
-    cout << "  * remove verts" << endl;
-    while(!V.empty()) {
-        g.remove_vertex(V.front());
-        V.pop_front();
-    }
-    BOOST_ASSERT(g.num_vertices() == 0);
-}
-
-template <typename Graph>
-void test_add_edges()
-{
-    cout << "  * add edges" << endl;
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-    BOOST_ASSERT(g.degree(V[0]) == 2);
-}
-
-template <typename Graph>
-void test_add_remove_edges()
-{
-    Graph g;
-
-    cout << "  * add edges" << endl;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    E.push_back(g.add_edge(V[0], V[1]));
-    E.push_back(g.add_edge(V[1], V[2]));
-    E.push_back(g.add_edge(V[2], V[0]));
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-
-    cout << "  * remove edges" << endl;
-    g.remove_edge(E.front());
-    BOOST_ASSERT(g.num_edges() == 2);
-    BOOST_ASSERT(g.degree(V[1]) == 1);
-    E.pop_front();
-
-    g.remove_edge(E.front());
-    BOOST_ASSERT(g.degree(V[1]) == 0);
-    E.pop_front();
-}
-
-template <typename Graph>
-void test_disconnect_vertex()
-{
-    cout << "  * disconnecting vertex" << std::endl;
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-
-    g.remove_edges(V[1]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.degree(V[1]) == 0);
-    BOOST_ASSERT(g.degree(V[0]) == 1);
-    BOOST_ASSERT(g.degree(V[2]) == 1);
-}
-
-// This is a little different than above. We remove a vertex from the triangle,
-// which implicitly disconnects it.
-template <typename Graph>
-void test_implicit_disconnect_vertex()
-{
-    cout << "  * removing conntected vertex" << endl;
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    g.add_edge(V[2], V[0]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 3);
-
-    g.remove_vertex(V[1]);
-    BOOST_ASSERT(g.num_vertices() == 2);
-    BOOST_ASSERT(g.degree(V[0]) == 1);
-    BOOST_ASSERT(g.degree(V[2]) == 1);
-}
-
-template <typename Graph>
-void test_add_multi_edges()
-{
-    cout << "  * adding parallel edges" << endl;
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-    g.add_edge(u, v, 10);
-    g.add_edge(v, u, 20);
-    g.add_edge(u, v, 30);
-    g.add_edge(v, u, 40);
-    BOOST_ASSERT(g.num_vertices() == 2);
-
-    // If there are no parallel edges, then there should only be one edge.
-    if(allows_parallel_edges(g)) {
-        BOOST_ASSERT(g.num_edges() == 4);
-    }
-    else {
-        BOOST_ASSERT(g.num_edges() == 1);
-    }
-}
-
-template <typename Graph>
-void test_remove_multi_edges()
-{
-    cout << "  * removing parallel edges" << endl;
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-    g.add_edge(u, v);
-    g.add_edge(v, u);
-    g.add_edge(u, v);
-    g.add_edge(v, u);
-
-    g.remove_edges(u, v);
-    BOOST_ASSERT(g.num_edges() == 0);
-    BOOST_ASSERT(g.degree(u) == 0);
-    BOOST_ASSERT(g.degree(v) == 0);
-}
-
-
-template <typename Graph>
-void test_edge()
-{
-    cout << "  * find edges" << endl;
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    g.add_edge(V[0], V[1]);
-    g.add_edge(V[1], V[2]);
-    BOOST_ASSERT(g.num_vertices() == 3);
-    BOOST_ASSERT(g.num_edges() == 2);
-
-    // Test for existence
-    BOOST_ASSERT(g.edge(V[0], V[1]));
-    BOOST_ASSERT(g.edge(V[1], V[0]));
-    BOOST_ASSERT(g.edge(V[1], V[2]));
-    BOOST_ASSERT(g.edge(V[2], V[1]));
-
-    // Test for inexstence
-    BOOST_ASSERT(!g.edge(V[0], V[2]));
-    BOOST_ASSERT(!g.edge(V[2], V[0]));
-}
-
-template <typename Graph>
-void test_vertex_iterator()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    list<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-
-    cout << "  * testing vertex iterator" << endl;
-    typename Graph::vertex_range rng = g.vertices();
-    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
-    BOOST_ASSERT(*rng.first++ == V[0]);
-    BOOST_ASSERT(*rng.first++ == V[1]);
-    BOOST_ASSERT(*rng.first++ == V[2]);
-}
-
-template <typename Graph>
-void test_edge_iterator()
-{
-    Graph g;
-    vector<typename Graph::vertex_descriptor> V;
-    vector<typename Graph::edge_descriptor> E;
-    for(int i = 0; i < 3; ++i) {
-        V.push_back(g.add_vertex(i));
-    }
-    E.push_back(g.add_edge(V[0], V[1], 10));
-    E.push_back(g.add_edge(V[1], V[2], 20));
-    E.push_back(g.add_edge(V[2], V[0], 30));
-
-    cout << "  * testing edge iterator" << endl;
-
-    typename Graph::edge_range rng = g.edges();
-    BOOST_ASSERT(distance(rng.first, rng.second) == 3);
-    BOOST_ASSERT(*rng.first++ == E[0]);
-    BOOST_ASSERT(*rng.first++ == E[1]);
-    BOOST_ASSERT(*rng.first++ == E[2]);
-}
-
-template <typename Graph>
-void test_incidence_iterator()
-{
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-    g.add_edge(u, v, 1);
-    g.add_edge(v, u, 2);
-    g.add_edge(u, v, 3);
-    g.add_edge(v, u, 4);
-
-    cout << "  * incidence iterator" << endl;
-    typename Graph::incident_edge_range x = g.incident_edges(v);
-    typename Graph::incident_edge_iterator i = x.first;
-    for(typename Graph::incident_edge_iterator i = x.first; i != x.second; ++i) {
-        BOOST_ASSERT(*i);
-    }
-}
-
-template <typename Graph>
-void test_adjacency_iterator()
-{
-    Graph g;
-    typename Graph::vertex_descriptor u = g.add_vertex(1);
-    typename Graph::vertex_descriptor v = g.add_vertex(2);
-    g.add_edge(u, v, 1);
-    g.add_edge(v, u, 2);
-    g.add_edge(u, v, 3);
-    g.add_edge(v, u, 4);
-
-    cout << "  * adjacency iterator" << endl;
-    typename Graph::adjacent_vertex_range x = g.adjacent_vertices(u);
-    for( ; x.first != x.second; ++x.first) {
-        typename Graph::vertex_descriptor o = *x.first;
-        BOOST_ASSERT(o == v);
-    }
-}
-
-int main()
-{
-    vec_vec();
-    list_list();
-    set_set();
-
-    return 0;
-}
-
-void vec_vec()
-{
-    cout << "---- vec/vec ----" << endl;
-    typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
-    test_add_vertices<Graph>();
-    test_add_edges<Graph>();
-    test_add_multi_edges<Graph>();
-    test_edge<Graph>();
-    test_vertex_iterator<Graph>();
-    test_edge_iterator<Graph>();
-    test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
-}
-
-void list_list()
-{
-    cout << "---- list/list ----" << endl;
-    typedef undirected_graph<City, Road, vertex_list<>, edge_list<> > Graph;
-    test_add_remove_vertices<Graph>();
-    test_add_remove_edges<Graph>();
-    test_disconnect_vertex<Graph>();
-    test_implicit_disconnect_vertex<Graph>();
-    test_add_multi_edges<Graph>();
-    test_remove_multi_edges<Graph>();
-    test_edge<Graph>();
-    test_vertex_iterator<Graph>();
-    test_edge_iterator<Graph>();
-    test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
-}
-
-
-void set_set()
-{
-    cout << "---- set/set ----" << endl;
-    typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
-    test_add_remove_vertices<Graph>();
-    test_add_remove_edges<Graph>();
-    test_disconnect_vertex<Graph>();
-    test_implicit_disconnect_vertex<Graph>();
-    test_add_multi_edges<Graph>();
-    test_remove_multi_edges<Graph>();
-    test_edge<Graph>();
-    test_vertex_iterator<Graph>();
-    test_edge_iterator<Graph>();
-    test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
-}
-

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/vertices_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/vertices_traits.hpp	2008-09-11 08:22:07 EDT (Thu, 11 Sep 2008)
+++ (empty file)
@@ -1,39 +0,0 @@
-
-#ifndef VERTICES_TRAITS_HPP
-#define VERTICES_TRAITS_HPP
-
-struct simple_vertex_store_tag { };
-struct mapped_vertex_store_tag { };
-
-struct vertex_vector_tag : simple_vertex_store_tag, unstable_remove_tag { };
-struct vertex_list_tag : simple_vertex_store_tag, stable_mutators_tag { };
-struct vertex_set_tag : simple_vertex_store_tag, stable_mutators_tag { };
-struct vertex_map_tag : mapped_vertex_store_tag, stable_mutators_tag { };
-
-template <typename Verts>
-struct vertices_traits
-{ typedef typename Verts::category category; };
-
-template <typename Verts>
-typename vertices_traits<Verts>::category
-vertices_category(Verts const&)
-{ return typename vertices_traits<Verts>::category(); }
-
-
-template <typename Vertex, typename Alloc>
-struct vertices_traits<vertices_vector<Vertex, Alloc>>
-{ typedef vertex_vector_tag category; };
-
-template <typename Vertex, typename Alloc>
-struct vertices_traits<vertices_list<Vertex, Alloc>>
-{ typedef vertex_list_tag category; };
-
-template <typename Vertex, typename Compare, typename Alloc>
-struct vertices_traits<vertices_set<Vertex, Compare, Alloc>>
-{ typedef vertex_set_tag category; };
-
-template <typename Vertex, typename Key, typename Compare, typename Alloc>
-struct vertices_traits<vertices_map<Vertex, Key, Compare, Alloc>>
-{ typedef vertex_map_tag category; };
-
-#endif