[Boost-commit] svn:boost r52915 - trunk/libs/graph/test

Subject: [Boost-commit] svn:boost r52915 - trunk/libs/graph/test
From: asutton_at_[hidden]
Date: 2009-05-11 13:43:25

Author: asutton
Date: 2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
New Revision: 52915
URL: http://svn.boost.org/trac/boost/changeset/52915

Log:
Added a legitimate graph testing framework.

Added:
   trunk/libs/graph/test/test_construction.hpp   (contents, props changed)
   trunk/libs/graph/test/test_destruction.hpp   (contents, props changed)
   trunk/libs/graph/test/test_direction.hpp   (contents, props changed)
   trunk/libs/graph/test/test_graph.hpp   (contents, props changed)
   trunk/libs/graph/test/test_iteration.hpp   (contents, props changed)
   trunk/libs/graph/test/test_properties.hpp   (contents, props changed)
Text files modified: 
   trunk/libs/graph/test/Jamfile.v2      |     1                                         
   trunk/libs/graph/test/index_graph.cpp |    59 ++++++++++---                           
   trunk/libs/graph/test/test_graphs.cpp |   168 +++++++++++++++++++++++++++++++-------- 
   3 files changed, 181 insertions(+), 47 deletions(-)

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -27,6 +27,7 @@
     # and implementation of graph data structures and adaptors.
     [ run test_graphs.cpp ]
     [ run index_graph.cpp ]     # TODO: Make this part of the test_graphs framework
+    [ run labeled_graph.cpp ]
 
     [ run transitive_closure_test.cpp ]
     [ compile adj_list_cc.cpp ]

Modified: trunk/libs/graph/test/index_graph.cpp
==============================================================================
--- trunk/libs/graph/test/index_graph.cpp	(original)
+++ trunk/libs/graph/test/index_graph.cpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -6,23 +6,24 @@
 
 #include <iostream>
 #include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
 
 using namespace std;
 using namespace boost;
 
-typedef undirected_graph<> Graph;
-typedef Graph::vertex_descriptor Vertex;
-typedef property_map<Graph, vertex_index_t>::type IndexMap;
-
-int main(int, char*[])
+template <typename Graph>
+void test()
 {
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
+
     static const size_t N = 5;
-    Graph g;
-    Vertex v[N];
 
+    Graph g;
     IndexMap x = get(vertex_index, g);
 
     // build up the graph
+    Vertex v[N];
     for(size_t i = 0; i < N; ++i) {
         v[i] = add_vertex(g);
     }
@@ -33,29 +34,61 @@
         BOOST_ASSERT(get_vertex_index(v[i], g) == i);
     }
 
-    // remove some vertices and re-add them...
+    // Remove all vertices and then re-add them.
     for(size_t i = 0; i < N; ++i) remove_vertex(v[i], g);
     BOOST_ASSERT(num_vertices(g) == 0);
-
     for(size_t i = 0; i < N; ++i) {
         v[i] = add_vertex(g);
     }
+    BOOST_ASSERT(num_vertices(g) == N);
 
-    // before renumbering, our vertices should be off by
-    // about N...
+    // Before renumbering, our vertices should be off by N. In other words,
+    // we're not in a good state.
     BOOST_ASSERT(max_vertex_index(g) == 10);
     for(size_t i = 0; i < N; ++i) {
         BOOST_ASSERT(get_vertex_index(v[i], g) == N + i);
     }
 
-    // renumber vertices
+    // Renumber vertices
     renumber_vertex_indices(g);
 
-    // and we should be back to the initial condition
+    // And we should be back to the initial condition
     BOOST_ASSERT(max_vertex_index(g) == N);
     for(size_t i = 0; i < N; ++i) {
         BOOST_ASSERT(get_vertex_index(v[i], g) == i);
     }
+}
+
+// Make sure that graphs constructed over n vertices will actually number
+// their vertices correctly.
+template <typename Graph>
+void build()
+{
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename graph_traits<Graph>::vertex_iterator Iterator;
+    typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
+
+    static const size_t N = 5;
+
+    Graph g(N);
+    BOOST_ASSERT(max_vertex_index(g) == N);
+
+    IndexMap x = get(vertex_index, g);
+
+    // Each vertex should be numbered correctly.
+    Iterator i, end;
+    tie(i, end) = vertices(g);
+    for(size_t x = 0; i != end; ++i, ++x) {
+        BOOST_ASSERT(get_vertex_index(*i, g) == x);
+    }
+}
+
+int main(int, char*[])
+{
+    test< undirected_graph<> >();
+    test< directed_graph<> >();
+
+    build< undirected_graph<> >();
 
     return 0;
 }

Added: trunk/libs/graph/test/test_construction.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/test_construction.hpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -0,0 +1,76 @@
+
+#ifndef TEST_CONSTRUCTION_HPP
+#define TEST_CONSTRUCTION_HPP
+
+#include <utility>
+
+/** @name Build Graph
+ * Build the standard graph structure used in the remaining tests. Depending
+ * on the mutability traits of the graph G, this may or may not add N vertices
+ * to graph. The Add and Label type parameters are used to dispatch a build
+ * method for normal or labeled graphs.
+ */
+//@{
+// This will basically catch adjacency matrices, which don't get built.
+template <typename Graph, typename Add, typename Label>
+void build_graph(Graph& g, Add, Label)
+{ }
+
+// This matches MutableGraph, so just add some vertices.
+template <typename Graph>
+void build_graph(Graph& g, boost::mpl::true_, boost::mpl::false_) {
+    for(std::size_t i = 0; i < N; ++i) {
+        boost::add_vertex(g);
+    }
+}
+
+// This will match labeled graphs.
+template <typename Graph>
+void build_graph(Graph& g, boost::mpl::false_, boost::mpl::true_) {
+    // Add each vertex labeled with the number i.
+    for(std::size_t i = 0; i < N; ++i) {
+        boost::add_vertex(i, g);
+    }
+}
+//@}
+
+
+/** @name Connect Graph
+ * Given a constructed graph, connect the edges to create a the standard
+ * testing graph. To facilitate ease of use, we pass a vector of vertices
+ * along with the graph such that v[0] -> *vertices(g).first, etc. The
+ * Labeled type parameter is used to dispatch connection techniques for
+ * normal or labled graphs.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::false_) {
+    Pair *f, *l;
+    for(boost::tie(f, l) = edge_pairs(); f != l; ++f) {
+        Pair const& e = *f;
+        boost::add_edge(verts[e.first], verts[e.second], g);
+    }
+
+    // Is the lollipop connected? Is the lollipop not connected to the roof?
+    BOOST_ASSERT(boost::edge(verts[5], verts[3], g).second == true);
+    BOOST_ASSERT(boost::edge(verts[5], verts[0], g).second == false);
+}
+
+template <typename Graph, typename VertexSet>
+void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::true_) {
+    // With labeled graphs, we want to operate directly on the edge numbers
+    // rather than looking up the correct vertex index. This is because the
+    // vertices are already mapped to indices.
+    Pair* p = edge_pairs().first;
+    for(std::size_t i = 0; i < M; ++i) {
+        Pair const& e = p[i];
+        boost::add_edge_by_label(e.first, e.second, g);
+    }
+
+    // Is the lollipop connected?
+    BOOST_ASSERT(boost::edge_by_label(5, 3, g).second == true);
+    BOOST_ASSERT(boost::edge_by_label(5, 0, g).second == false);
+}
+//@}
+
+#endif

Added: trunk/libs/graph/test/test_destruction.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/test_destruction.hpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -0,0 +1,89 @@
+
+#ifndef TEST_DESTRUCTION_HPP
+#define TEST_DESTRUCTION_HPP
+
+#include <utility>
+
+/** @name Destroy Graph
+ * Destroy the graph by removing vertices (if possible).
+ */
+//@{
+// This will basically catch adjacency matrices, which don't get torn down.
+template <typename Graph, typename VertexSet, typename Remove, typename Label>
+void destroy_graph(Graph& g, VertexSet const& verts, Remove, Label)
+{ }
+
+// This matches MutableGraph, so just remove a vertex and then clear.
+template <typename Graph, typename VertexSet>
+void destroy_graph(Graph& g, VertexSet const& verts, boost::mpl::true_, boost::mpl::false_) {
+    // Remove the roof vertex
+    boost::remove_vertex(verts[0], g);
+    BOOST_ASSERT(boost::num_vertices(g) == N - 1);
+}
+
+// This will match labeled graphs.
+template <typename Graph, typename VertexSet>
+void destroy_graph(Graph& g, VertexSet const& verts, boost::mpl::false_, boost::mpl::true_) {
+    // Remove the roof vertex
+    boost::remove_vertex(0, g);
+    BOOST_ASSERT(boost::num_vertices(g) == N - 1);
+}
+//@}
+
+
+/** @name Disconnect Graph
+ * Disconnect edges in the graph. Note that this doesn't fully disconnect the
+ * graph. It simply determines if we can disconnect an edge or two and verify
+ * that the resulting graph is valid. The Labeled type parameter is used to
+ * dispatch for unlabeled and labeled graphs.
+ *
+ * @todo This doesn't quite work for multigraphs...
+ */
+//@{
+
+template <typename Graph, typename VertexSet>
+void disconnect_graph(Graph& g, VertexSet const& verts, boost::mpl::false_) {
+    typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+
+    // Disconnect the "lollipop" from the house.
+    Edge e = boost::edge(verts[5], verts[3], g).first;
+    boost::remove_edge(e, g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 1);
+
+    // Remove the "floor" edge from the house.
+    boost::remove_edge(verts[3], verts[2], g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 2);
+
+    // Fully disconnect the roof vertex.
+    clear_vertex(verts[0], g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 4);
+
+    // What happens if we try to remove an edge that doesn't exist?
+    boost::remove_edge(verts[5], verts[0], g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 4);
+}
+
+template <typename Graph, typename VertexSet>
+void disconnect_graph(Graph& g, VertexSet const& verts, boost::mpl::true_) {
+    typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+
+    // Disconnect the "lollipop" from the house.
+    Edge e = boost::edge_by_label(5, 3, g).first;
+    boost::remove_edge(e, g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 1);
+
+    // Remove the "floor" edge from the house.
+    boost::remove_edge_by_label(3, 2, g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 2);
+
+    // Fully disconnect the roof vertex.
+    clear_vertex_by_label(0, g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 4);
+
+    // What happens if we try to remove an edge that doesn't exist?
+    boost::remove_edge_by_label(5, 0, g);
+    BOOST_ASSERT(boost::num_edges(g) == M - 4);
+}
+//@}
+
+#endif

Added: trunk/libs/graph/test/test_direction.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/test_direction.hpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -0,0 +1,112 @@
+
+#ifndef TEST_DIRECTION_HPP
+#define TEST_DIRECTION_HPP
+
+#include <algorithm>
+#include <boost/range.hpp>
+
+/** @name Test Out-Directed Graph
+ * Test all graphs that have directed out edges.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_outdirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::true_) {
+    typedef typename boost::graph_traits<Graph>::out_edge_iterator OutIter;
+    typedef std::pair<OutIter, OutIter> OutRange;
+    typedef std::vector<OutRange> OutSet;
+
+    // Collect all of the out edge ranges from the graph.
+    OutSet outs(verts.size());
+    for(size_t i = 0; i < verts.size(); ++i) {
+        outs[i] = boost::out_edges(verts[i], g);
+    }
+
+    BOOST_ASSERT(boost::distance(outs[0]) == 0);
+    BOOST_ASSERT(boost::distance(outs[1]) == 1);
+    BOOST_ASSERT(boost::distance(outs[2]) == 1);
+    BOOST_ASSERT(boost::distance(outs[3]) == 2);
+    BOOST_ASSERT(boost::distance(outs[4]) == 2);
+    BOOST_ASSERT(boost::distance(outs[5]) == 1);
+
+    // Verify that the edges are actually correct.
+    // TODO: Find a better way of testing connectivity with multiple edges.
+    BOOST_ASSERT(has_target(g, *outs[1].first, verts[0]));
+    BOOST_ASSERT(has_target(g, *outs[2].first, verts[1]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
+    BOOST_ASSERT(has_target(g, *outs[5].first, verts[3]));
+}
+
+template <typename Graph, typename VertexSet>
+void test_outdirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::false_)
+{ }
+//@}
+
+/** @name Test In-Directed Graph
+ * Test all graphs that support in-directed edges.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_indirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::true_) {
+    typedef typename boost::graph_traits<Graph>::in_edge_iterator InIter;
+    typedef std::pair<InIter, InIter> InRange;
+    typedef std::vector<InRange> InSet;
+
+    // Collect all of the in edges from the graph.
+    InSet ins(verts.size());
+    for(size_t i = 0; i < verts.size(); ++i) {
+        ins[i] = boost::in_edges(verts[i], g);
+    }
+
+    BOOST_ASSERT(distance(ins[0]) == 2);
+    BOOST_ASSERT(distance(ins[1]) == 2);
+    BOOST_ASSERT(distance(ins[2]) == 1);
+    BOOST_ASSERT(distance(ins[3]) == 1);
+    BOOST_ASSERT(distance(ins[4]) == 1);
+    BOOST_ASSERT(distance(ins[5]) == 0);
+
+    // Verify that the connected edges are correct.
+    // TODO: Find a better way of testing connectivity with multiple edges.
+    BOOST_ASSERT(has_source(g, *ins[2].first, verts[3]));
+    BOOST_ASSERT(has_source(g, *ins[3].first, verts[5]));
+    BOOST_ASSERT(has_source(g, *ins[4].first, verts[3]));
+}
+
+template <typename Graph, typename VertexSet>
+void test_indirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::false_)
+{ }
+//@}
+
+/** @name Undirected Graphs
+ * Test all graphs that have undirected edges.
+ */
+template <typename Graph, typename VertexSet>
+void test_undirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::true_) {
+    typedef typename boost::graph_traits<Graph>::out_edge_iterator OutIter;
+    typedef std::pair<OutIter, OutIter> OutRange;
+    typedef std::vector<OutRange> OutSet;
+
+    // The set of out edges is the same as the set of incident edges.
+    OutSet outs(verts.size());
+    for(size_t i = 0; i < verts.size(); ++i) {
+        outs[i] = boost::out_edges(verts[i], g);
+    }
+
+    // TODO: Actually test the end connections to ensure that these are
+    // definitely correct.
+    BOOST_ASSERT(boost::distance(outs[0]) == 2);
+    BOOST_ASSERT(boost::distance(outs[1]) == 3);
+    BOOST_ASSERT(boost::distance(outs[2]) == 2);
+    BOOST_ASSERT(boost::distance(outs[3]) == 3);
+    BOOST_ASSERT(boost::distance(outs[4]) == 3);
+    BOOST_ASSERT(boost::distance(outs[5]) == 1);
+}
+
+template <typename Graph, typename VertexSet>
+void test_undirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::false_)
+{ }
+//@}
+
+#endif

Added: trunk/libs/graph/test/test_graph.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/test_graph.hpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -0,0 +1,124 @@
+
+#ifndef TEST_GRAPH_HPP
+#define TEST_GRAPH_HPP
+
+/** @file test_graph.hpp
+ * This file houses the generic graph testing framework, which is essentially
+ * run using the test_graph function. This function is called, passing a
+ * graph object that be constructed and exercised according to the concepts
+ * that the graph models. This test is extensively metaprogrammed in order to
+ * differentiate testable features of graph instances.
+ */
+
+#include <utility>
+#include <vector>
+#include <boost/assert.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_mutability_traits.hpp>
+
+#include "typestr.hpp"
+
+#define BOOST_META_ASSERT(x) BOOST_ASSERT(x::value)
+
+typedef std::pair<std::size_t, std::size_t> Pair;
+
+static const std::size_t N = 6;
+static const std::size_t M = 7;
+
+// A helper function that globally defines the graph being constructed. Note
+// that this graph shown here: http://en.wikipedia.org/wiki/Graph_theory.
+std::pair<Pair*, Pair*> edge_pairs() {
+    static Pair pairs[] = {
+        Pair(5, 3), Pair(3, 4), Pair(3, 2), Pair(4, 0), Pair(4, 1),
+        Pair(2, 1), Pair(1, 0)
+    };
+    Pair* f = &pairs[0];
+    Pair* l = f + M;
+    return std::make_pair(f, l);
+}
+
+// Return true if the vertex v is the target of the edge e.
+template <typename Graph, typename Edge, typename Vertex>
+bool has_target(Graph const& g, Edge e, Vertex v)
+{ return boost::target(e, g) == v; }
+
+// Return true if the vertex v is the source of the edge e.
+template <typename Graph, typename Edge, typename Vertex>
+bool has_source(Graph const& g, Edge e, Vertex v)
+{ return boost::source(e, g) == v; }
+
+/** @name Property Bundles
+ * Support testing with bundled properties. Note that the vertex bundle and
+ * edge bundle MAY NOT be the same if you want to use the property map type
+ * generator to define property maps.
+ */
+//@{
+struct VertexBundle {
+    VertexBundle() : value() { }
+    VertexBundle(int n) : value(n) { }
+
+    bool operator==(VertexBundle const& x) const { return value == x.value; }
+    bool operator<(VertexBundle const& x) const { return value < x.value; }
+
+    int value;
+};
+
+struct EdgeBundle {
+    EdgeBundle() : value() { }
+    EdgeBundle(int n) : value(n) { }
+
+    bool operator==(EdgeBundle const& x) const { return value == x.value; }
+    bool operator<(EdgeBundle const& x) const { return value < x.value; }
+
+    int value;
+};
+//@}
+
+#include "test_construction.hpp"
+#include "test_destruction.hpp"
+#include "test_iteration.hpp"
+#include "test_direction.hpp"
+#include "test_properties.hpp"
+
+template <typename Graph>
+void test_graph(Graph& g) {
+    // Define a bunch of tags for the graph.
+    typename boost::graph_has_add_vertex<Graph>::type can_add_vertex;
+    typename boost::graph_has_remove_vertex<Graph>::type can_remove_vertex;
+    typename boost::is_labeled_graph<Graph>::type is_labeled;
+    typename boost::is_directed_unidirectional_graph<Graph>::type is_directed;
+    typename boost::is_directed_bidirectional_graph<Graph>::type is_bidirectional;
+    typename boost::is_undirected_graph<Graph>::type is_undirected;
+
+    // Test constrution and vertex list.
+    build_graph(g, can_add_vertex, is_labeled);
+    test_vertex_list_graph(g);
+
+    // Collect the vertices for an easy method of "naming" them.
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename boost::graph_traits<Graph>::vertex_iterator VertexIterator;
+    std::vector<Vertex> verts;
+    std::pair<VertexIterator, VertexIterator> rng = vertices(g);
+    for( ; rng.first != rng.second; ++rng.first) {
+        verts.push_back(*rng.first);
+    }
+
+    // Test connection and edge list
+    connect_graph(g, verts, is_labeled);
+    test_edge_list_graph(g);
+
+    // Test properties
+    test_properties(g, verts);
+
+    // Test directionality.
+    test_outdirected_graph(g, verts, is_directed);
+    test_indirected_graph(g, verts, is_bidirectional);
+    test_undirected_graph(g, verts, is_undirected);
+
+    // Test disconnection
+    disconnect_graph(g, verts, is_labeled);
+    destroy_graph(g, verts, can_remove_vertex, is_labeled);
+}
+
+
+#endif

Modified: trunk/libs/graph/test/test_graphs.cpp
==============================================================================
--- trunk/libs/graph/test/test_graphs.cpp	(original)
+++ trunk/libs/graph/test/test_graphs.cpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -6,47 +6,147 @@
 
 #include <iostream>
 
+#define BOOST_NO_HASH
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/adjacency_matrix.hpp>
 #include <boost/graph/undirected_graph.hpp>
 #include <boost/graph/directed_graph.hpp>
+#include <boost/graph/labeled_graph.hpp>
 
-// TODO: Finish implementing this test module. In theory, this will become a
-// generic testing facility for any kind of graph declaration.
-
-using namespace std;
-using namespace boost;
+#include "test_graph.hpp"
 
-struct node
-{
-    node() : n() { }
-    node(int n) : n(n) { }
+// This test module is a testing ground to determine if graphs and graph
+// adaptors actually implement the graph concepts correctly.
 
-    bool operator==(node const& x) const    { return n == x.n; }
-    bool operator<(node const& x) const     { return n < x.n; }
-
-    int n;
-};
-
-struct arc
-{
-    arc() : n() { }
-    arc(int n) : n(n) { }
-
-    bool operator==(arc const& x) const     { return n == x.n; }
-
-    int n;
-};
-
-template <typename Graph>
-void test()
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    Graph g;
-    BOOST_ASSERT(num_vertices(g) == 0);
-}
+using namespace boost;
 
 int main()
 {
-    test< undirected_graph<node, arc> >();
-    test< directed_graph<node, arc> >();
+    // Bootstrap all of the tests by declaring a kind graph and  asserting some
+    // basic properties about it.
+    {
+        typedef undirected_graph<VertexBundle, EdgeBundle> Graph;
+        BOOST_META_ASSERT(is_undirected_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_mutable_graph<Graph>);
+        BOOST_META_ASSERT(is_mutable_property_graph<Graph>);
+        Graph g;
+        test_graph(g);
+    }
+    {
+        typedef directed_graph<VertexBundle, EdgeBundle> Graph;
+        BOOST_META_ASSERT(is_directed_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_mutable_graph<Graph>);
+        BOOST_META_ASSERT(is_mutable_property_graph<Graph>);
+        Graph g;
+        test_graph(g);
+    }
+    {
+        typedef adjacency_list<vecS, vecS, undirectedS, VertexBundle, EdgeBundle> Graph;
+        BOOST_META_ASSERT(is_undirected_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_add_only_property_graph<Graph>);
+        Graph g;
+        test_graph(g);
+    }
+    {
+        typedef adjacency_list<vecS, vecS, directedS, VertexBundle, EdgeBundle> Graph;
+        Graph g;
+        BOOST_META_ASSERT(is_directed_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(!is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(is_directed_unidirectional_graph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_add_only_property_graph<Graph>);
+        test_graph(g);
+    }
+    {
+        // Common bidi adjlist
+        typedef adjacency_list<vecS, vecS, bidirectionalS, VertexBundle, EdgeBundle> Graph;
+        BOOST_META_ASSERT(is_directed_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_add_only_property_graph<Graph>);
+        Graph g;
+        test_graph(g);
+    }
+    {
+        // Same as above, but testing VL==listS
+        typedef adjacency_list<vecS, listS, bidirectionalS, VertexBundle, EdgeBundle> Graph;
+        BOOST_META_ASSERT(is_directed_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_mutable_property_graph<Graph>);
+        Graph g;
+        test_graph(g);
+    }
+    {
+        // TODO: What other kinds of graphs do we have here...
+        typedef adjacency_matrix<directedS, VertexBundle, EdgeBundle> Graph;
+        BOOST_META_ASSERT(is_directed_graph<Graph>);
+        BOOST_META_ASSERT(!is_multigraph<Graph>);
+        BOOST_META_ASSERT(has_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(has_edge_property<Graph>);
+        BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_mutable_edge_graph<Graph>);
+        BOOST_META_ASSERT(is_mutable_edge_property_graph<Graph>);
+        Graph g(N);
+        test_graph(g);
+    }
+    {
+        typedef labeled_graph<directed_graph<>, unsigned> Graph;
+        BOOST_META_ASSERT(is_directed_graph<Graph>);
+        BOOST_META_ASSERT(is_multigraph<Graph>);
+        BOOST_META_ASSERT(is_incidence_graph<Graph>);
+        BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+        BOOST_META_ASSERT(is_labeled_mutable_property_graph<Graph>);
+        BOOST_META_ASSERT(is_labeled_graph<Graph>);
+        BOOST_META_ASSERT(!has_vertex_property<Graph>);
+        BOOST_META_ASSERT(!has_bundled_vertex_property<Graph>);
+        BOOST_META_ASSERT(!has_edge_property<Graph>);
+        BOOST_META_ASSERT(!has_bundled_edge_property<Graph>);
+        BOOST_META_ASSERT(is_labeled_mutable_graph<Graph>);
+        Graph g;
+        test_graph(g);
+    }
 }
 

Added: trunk/libs/graph/test/test_iteration.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/test_iteration.hpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -0,0 +1,41 @@
+
+#ifndef TEST_ITERATION_HPP
+#define TEST_ITERATION_HPP
+
+#include <algorithm>
+
+/** @name Test Vertex List
+ * Test the vertex list interface. Note that there are currently no graphs that
+ * do not expose this interface.
+ */
+//@{
+template <typename Graph>
+void test_vertex_list_graph(Graph const& g) {
+    typedef typename boost::graph_traits<Graph>::vertex_iterator Iterator;
+    typedef std::pair<Iterator, Iterator> Range;
+
+    Range rng = vertices(g);
+    BOOST_ASSERT(num_vertices(g) == N);
+    BOOST_ASSERT(rng.first != rng.second);
+    BOOST_ASSERT(std::distance(rng.first, rng.second) == int(N));
+}
+//@}
+
+/** @name Test Edge List
+ * Test the edge list interface. Note that there are currently no graphs that
+ * do not expose this interface.
+ */
+//@{
+template <typename Graph>
+void test_edge_list_graph(Graph const& g) {
+    typedef typename boost::graph_traits<Graph>::edge_iterator Iterator;
+    typedef std::pair<Iterator, Iterator> Range;
+
+    Range rng = edges(g);
+    BOOST_ASSERT(boost::num_edges(g) == M);
+    BOOST_ASSERT(rng.first != rng.second);
+    BOOST_ASSERT(std::distance(rng.first, rng.second) == int(M));
+}
+//@}
+
+#endif

Added: trunk/libs/graph/test/test_properties.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/test_properties.hpp	2009-05-11 13:43:24 EDT (Mon, 11 May 2009)
@@ -0,0 +1,79 @@
+
+#ifndef TEST_PROPERTIES_HPP
+#define TEST_PROPERTIES_HPP
+
+/** @name Test Vertex Bundle
+ * Exercise the vertex bundle. Note that this is expected to be of type
+ * VertexBundle.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_vertex_bundle(Graph& g, VertexSet const& verts, boost::mpl::true_) {
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+
+    // This just has to compile. You can't actually get this map.
+    typedef typename boost::property_map<Graph, boost::vertex_bundle_t>::type TestMap;
+
+    // Test bundling via the graph object on the lollipop vertex.
+    Vertex v = verts[5];
+    VertexBundle& b = g[v];
+    b.value = 10;
+    BOOST_ASSERT(g[v].value == 10);
+
+    // Test bundling via the property map.
+    typedef typename boost::property_map<Graph, int VertexBundle::*>::type BundleMap;
+    BundleMap map = get(&VertexBundle::value, g);
+    put(map, v, 5);
+    BOOST_ASSERT(get(map, v) == 5);
+}
+
+template <typename Graph, typename VertexSet>
+void test_vertex_bundle(Graph&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+/** @name Test Edge Bundle
+ * Exercise the edge bundle. Note that this is expected to be of type
+ * EdgeBundle.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_edge_bundle(Graph& g, VertexSet const& verts, boost::mpl::true_) {
+    // This just has to compile. You can't actually get this map.
+    typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+    typedef typename boost::property_map<Graph, boost::edge_bundle_t>::type TestMap;
+
+    // Test bundling via the graph object on the lollipop edge.
+    Edge e = boost::edge(verts[5], verts[3], g).first;
+    EdgeBundle& b = g[e];
+    b.value = 10;
+    BOOST_ASSERT(g[e].value == 10);
+
+    // Test bundling via the property map.
+    typedef typename boost::property_map<Graph, int EdgeBundle::*>::type BundleMap;
+    BundleMap map = get(&EdgeBundle::value, g);
+    put(map, e, 5);
+    BOOST_ASSERT(get(map, e) == 5);
+}
+
+template <typename Graph, typename VertexSet>
+void test_edge_bundle(Graph&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+/**
+ * Test the properties of a graph. Basically, we expect these to be one of
+ * bundled or not. This test could also be expanded to test non-bundled
+ * properties. This just bootstraps the tests.
+ */
+template <typename Graph, typename VertexSet>
+void test_properties(Graph& g, VertexSet const& verts) {
+    typename boost::has_bundled_vertex_property<Graph>::type vertex_bundled;
+    typename boost::has_bundled_edge_property<Graph>::type edge_bundled;
+
+    test_vertex_bundle(g, verts, vertex_bundled);
+    test_edge_bundle(g, verts, edge_bundled);
+}
+//@}
+
+#endif