[Boost-commit] svn:boost r38721 - sandbox/SOC/2007/graphs/libs/graph/test/concept

From: asutton_at_[hidden]
Date: 2007-08-16 12:12:06

Author: asutton
Date: 2007-08-16 12:12:04 EDT (Thu, 16 Aug 2007)
New Revision: 38721
URL: http://svn.boost.org/trac/boost/changeset/38721

Log:
Completely rewrote most of the archetypes for concept coverage
Added archetypes for edge list and bidirectional concepts
property graphs are a little screwy

Added:
   sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp   (contents, props changed)
   sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2                  |     1                                         
   sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp              |    16 --------                                
   sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp |    75 +++++++++++++++++++++------------------ 
   3 files changed, 42 insertions(+), 50 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2	2007-08-16 12:12:04 EDT (Thu, 16 Aug 2007)
@@ -8,6 +8,7 @@
     ;
 
 test-suite graph_test :
+    [ compile test_new_archetypes.cpp ]
     [ compile degree_centrality_check.cpp ]
     [ compile closeness_centrality_check.cpp ]
     [ compile mean_geodesic_check.cpp ]

Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp	2007-08-16 12:12:04 EDT (Thu, 16 Aug 2007)
@@ -8,24 +8,10 @@
 #ifndef BOOST_GRAPH_CONCEPT_CHECK_ARCHETYPES_HPP
 #define BOOST_GRAPH_CONCEPT_CHECK_ARCHETYPES_HPP
 
-#include <utility>
-#include <boost/graph/properties.hpp>
-#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/graph_archetypes.hpp>
+#include "new_archetypes.hpp"
 
 namespace boost
 {
-    struct descriptor_archetype
-        : public
-            default_constructible_archetype<
-                copy_constructible_archetype<
-                    sgi_assignable_archetype<
-                        equality_comparable_archetype<> > > >
-    {
-        descriptor_archetype() { }
-        descriptor_archetype(detail::dummy_constructor) { }
-    };
-
     template <typename Graph>
     struct degree_measure_archetype
     {

Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp	2007-08-16 12:12:04 EDT (Thu, 16 Aug 2007)
@@ -14,22 +14,20 @@
 main(int argc, char *argv[])
 {
     {
-        typedef descriptor_archetype Vertex;
         typedef incidence_graph_archetype<
-                Vertex,
                 undirected_tag,
                 allow_parallel_edge_tag
             > IncidenceGraph;
         typedef vertex_list_graph_archetype<
-                Vertex,
                 undirected_tag,
                 allow_parallel_edge_tag,
                 IncidenceGraph
-            > Graph;
+            > VertexListGraph;
+        typedef VertexListGraph::vertex_descriptor Vertex;
         typedef writable_property_map_archetype<Vertex, size_t> CentralityMap;
-        typedef degree_measure_archetype<Graph> Measure;
+        typedef degree_measure_archetype<VertexListGraph> Measure;
 
-        Graph& g = static_object<Graph>::get();
+        VertexListGraph& g = static_object<VertexListGraph>::get();
         CentralityMap cm;
         Measure m;
 
@@ -38,15 +36,37 @@
     }
 
     {
-        typedef descriptor_archetype Vertex;
+        typedef vertex_list_graph_archetype<
+                directed_tag,
+                allow_parallel_edge_tag
+            > VertexListGraph;
+        typedef bidirectional_graph_archetype<
+                directed_tag,
+                allow_parallel_edge_tag,
+                VertexListGraph
+            > BidirectionalGraph;
+        typedef BidirectionalGraph::vertex_descriptor Vertex;
+        typedef read_write_property_map_archetype<Vertex, size_t> CentralityMap;
+        typedef degree_measure_archetype<BidirectionalGraph> Measure;
+
+        BidirectionalGraph& g = static_object<BidirectionalGraph>::get();
+        CentralityMap cm;
+        Measure m;
+
+        degree_centrality(g, cm, measure_influence(g));
+        degree_centrality(g, cm, measure_prestige(g));
+        degree_centrality(g, cm, m);
+    }
+
+    {
         typedef incidence_graph_archetype<
-                Vertex,
                 undirected_tag,
                 allow_parallel_edge_tag
-            > Graph;
-        typedef degree_measure_archetype<Graph> Measure;
+            > IncidenceGraph;
+        typedef IncidenceGraph::vertex_descriptor Vertex;
+        typedef degree_measure_archetype<IncidenceGraph> Measure;
 
-        Graph& g = static_object<Graph>::get();
+        IncidenceGraph& g = static_object<IncidenceGraph>::get();
         Vertex v = static_object<Vertex>::get();
         Measure m;
 
@@ -54,36 +74,21 @@
         vertex_degree_centrality(g, v, m);
     }
 
-    // There isn't a bidirectional graph archetype so I don't really know
-    // how to test this. Even If I build one, it won't compile very
-    // easily.
     {
-        /*
-        typedef descriptor_archetype Vertex;
         typedef bidirectional_graph_archetype<
-                Vertex,
-                directed_tag,
+                undirected_tag,
                 allow_parallel_edge_tag
             > BidirectionalGraph;
-        typedef vertex_list_graph_archetype<
-                Vertex,
-                directed_tag,
-                allow_parallel_edge_tag,
-                BidirectionalGraph
-            > graph_type;
-        typedef read_write_property_map_archetype<Vertex, size_t> CentralityMap;
-        */
+        typedef BidirectionalGraph::vertex_descriptor Vertex;
+        typedef degree_measure_archetype<BidirectionalGraph> Measure;
 
-        // These don't actually work - apparently, it's not very easy
-        // to generate archetypes across concept hierarchies and have
-        // them concept-checked very easily.
-
-        // graph_type& g = static_object<graph_type>::get();
-        // centrality_map_type cm;
+        BidirectionalGraph& g = static_object<BidirectionalGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        Measure m;
 
-        // degree_centrality(g, cm);
-        // degree_centrality(g, cm, measure_prestige(g));
+        vertex_degree_centrality(g, v, measure_influence(g));
+        vertex_degree_centrality(g, v, measure_prestige(g));
+        vertex_degree_centrality(g, v, m);
     }
-
     return 0;
 }

Added: sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp	2007-08-16 12:12:04 EDT (Thu, 16 Aug 2007)
@@ -0,0 +1,341 @@
+// (C) Copyright 2002 Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+//
+// (C) Copyright 2007 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_NEW_ARCHETYPES_HPP
+#define BOOST_GRAPH_NEW_ARCHETYPES_HPP
+
+#include <boost/property_map.hpp>
+#include <boost/concept_archetype.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+
+namespace boost
+{
+    // The regular_archetype is basically a collection of interfaces  that makes
+    // the archetype operate like most built-in types. It is  default and copy
+    // constructible, assignable, and equality and less-than comparable.
+    template <typename Base = null_archetype<> >
+    struct regular_archetype
+        : public
+            default_constructible_archetype<
+                copy_constructible_archetype<
+                    sgi_assignable_archetype<
+                        equality_comparable_archetype<
+                            less_than_comparable_archetype<Base> > > > >
+    {
+        regular_archetype() { }
+        regular_archetype(detail::dummy_constructor) { }
+    };
+
+    namespace detail
+    {
+        struct null_graph_archetype : public null_archetype<>
+        {
+            // Graph concepts
+            typedef void vertex_descriptor;
+            typedef void edge_descriptor;
+            typedef void directed_category;
+            struct traversal_category { };
+
+            // IncidenceGraph concepts
+            typedef void degree_size_type;
+            typedef void out_edge_iterator;
+
+            // BidirectionalGraph concepts
+            typedef void in_edge_iterator;
+
+            // AdjacencyGraph concepts
+            typedef void adjacency_iterator;
+
+            // VertexListGraph concepts
+            typedef void vertex_iterator;
+            typedef void vertices_size_type;
+
+            // EdgeListGraph concepts
+            typedef void edge_iterator;
+            typedef void edges_size_type;
+        };
+    }
+
+    struct descriptor_archetype
+        : public regular_archetype<>
+    {
+        descriptor_archetype() { }
+        descriptor_archetype(detail::dummy_constructor) { }
+    };
+
+    //
+    // Graph
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype>
+    struct graph_archetype
+        : public Base
+    {
+        typedef descriptor_archetype vertex_descriptor;
+        typedef descriptor_archetype edge_descriptor;
+        typedef Directed directed_category;
+        typedef Parallel edge_parallel_category;
+        typedef typename Base::traversal_category traversal_category;
+
+        static vertex_descriptor null_vertex()
+        { return static_object<vertex_descriptor>::get(); }
+    };
+
+    //
+    // IncidenceGraph
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype>
+    struct incidence_graph_archetype
+        : public graph_archetype<Directed, Parallel, Base>
+    {
+        typedef graph_archetype<Directed,Parallel,Base> BaseType;
+        typedef unsigned degree_size_type;
+        typedef input_iterator_archetype<typename BaseType::edge_descriptor> out_edge_iterator;
+        struct traversal_category : incidence_graph_tag, Base::traversal_category { };
+    };
+
+    template <typename D, typename P, typename B>
+    typename incidence_graph_archetype<D,P,B>::vertex_descriptor
+    source(typename incidence_graph_archetype<D,P,B>::edge_descriptor,
+           const incidence_graph_archetype<D,P,B>&)
+    {
+        typedef typename incidence_graph_archetype<D,P,B>::vertex_descriptor Vertex;
+        return static_object<Vertex>::get();
+    }
+
+    template <typename D, typename P, typename B>
+    typename incidence_graph_archetype<D,P,B>::vertex_descriptor
+    target(typename incidence_graph_archetype<D,P,B>::edge_descriptor,
+           const incidence_graph_archetype<D,P,B>& )
+    {
+        typedef typename incidence_graph_archetype<D,P,B>::vertex_descriptor Vertex;
+        return static_object<Vertex>::get();
+    }
+
+    template <typename D, typename P, typename B>
+    std::pair<typename incidence_graph_archetype<D,P,B>::out_edge_iterator,
+              typename incidence_graph_archetype<D,P,B>::out_edge_iterator>
+    out_edges(typename incidence_graph_archetype<D,P,B>::vertex_descriptor,
+              const incidence_graph_archetype<D,P,B>& )
+    {
+        typedef typename incidence_graph_archetype<D,P,B>::out_edge_iterator Iterator;
+        return std::make_pair(Iterator(), Iterator());
+    }
+
+    template <typename D, typename P, typename B>
+    typename incidence_graph_archetype<D,P,B>::degree_size_type
+    out_degree(typename incidence_graph_archetype<D,P,B>::vertex_descriptor,
+               const incidence_graph_archetype<D,P,B>&)
+    { return 0; }
+
+    //
+    // BidirectionalGraph
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype>
+    struct bidirectional_graph_archetype
+        : public incidence_graph_archetype<Directed, Parallel, Base>
+    {
+        typedef incidence_graph_archetype<Directed,Parallel,Base> BaseType;
+        typedef input_iterator_archetype<typename BaseType::edge_descriptor> in_edge_iterator;
+        struct traversal_category : bidirectional_graph_tag, Base::traversal_category { };
+    };
+
+    template <typename D, typename P, typename B>
+    std::pair<typename bidirectional_graph_archetype<D,P,B>::in_edge_iterator,
+              typename bidirectional_graph_archetype<D,P,B>::in_edge_iterator>
+    in_edges(typename bidirectional_graph_archetype<D,P,B>::vertex_descriptor,
+             const bidirectional_graph_archetype<D,P,B>& )
+    {
+        typedef typename bidirectional_graph_archetype<D,P,B>::in_edge_iterator Iterator;
+        return std::make_pair(Iterator(), Iterator());
+    }
+
+    template <typename D, typename P, typename B>
+    typename bidirectional_graph_archetype<D,P,B>::degree_size_type
+    in_degree(typename bidirectional_graph_archetype<D,P,B>::vertex_descriptor,
+              const bidirectional_graph_archetype<D,P,B>&)
+    { return 0; }
+
+    //
+    // AdjacencyGraph
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype>
+    struct adjacency_graph_archetype
+        : public graph_archetype<Directed, Parallel, Base>
+    {
+        typedef graph_archetype<Directed,Parallel,Base> BaseType;
+        typedef input_iterator_archetype<typename BaseType::vertex_descriptor> adjacency_iterator;
+        struct traversal_category : adjacency_graph_tag, Base::traversal_category { };
+    };
+
+    template <typename D, typename P, typename B>
+    std::pair<typename adjacency_graph_archetype<D,P,B>::adjacency_iterator,
+              typename adjacency_graph_archetype<D,P,B>::adjacency_iterator>
+    adjacent_vertices(typename adjacency_graph_archetype<D,P,B>::vertex_descriptor,
+                      const adjacency_graph_archetype<D,P,B>&)
+    {
+        typedef typename adjacency_graph_archetype<D,P,B>::adjacency_iterator Iterator;
+        return std::make_pair(Iterator(), Iterator());
+    }
+
+    //
+    // VertexListGraph
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype >
+    struct vertex_list_graph_archetype
+        : public graph_archetype<Directed, Parallel, Base>
+    {
+        typedef graph_archetype<Directed,Parallel,Base> BaseType;
+        typedef unsigned vertices_size_type;
+        typedef input_iterator_archetype<typename BaseType::vertex_descriptor> vertex_iterator;
+        struct traversal_category : public vertex_list_graph_tag, Base::traversal_category { };
+    };
+
+    template <typename D, typename P, typename B>
+    std::pair<typename vertex_list_graph_archetype<D,P,B>::vertex_iterator,
+              typename vertex_list_graph_archetype<D,P,B>::vertex_iterator>
+    vertices(const vertex_list_graph_archetype<D,P,B>&)
+    {
+        typedef typename vertex_list_graph_archetype<D,P,B>::vertex_iterator Iterator;
+        return std::make_pair(Iterator(), Iterator());
+    }
+
+    template <typename D, typename P, typename B>
+    typename vertex_list_graph_archetype<D,P,B>::vertices_size_type
+    num_vertices(const vertex_list_graph_archetype<D,P,B>& )
+    { return 0; }
+
+    //
+    // EdgeListGraph
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype >
+    struct edge_list_graph_archetype
+        : public graph_archetype<Directed, Parallel, Base>
+    {
+        typedef graph_archetype<Directed,Parallel,Base> BaseType;
+        typedef unsigned edges_size_type;
+        typedef input_iterator_archetype<typename BaseType::edge_descriptor> edge_iterator;
+        struct traversal_category : public edge_list_graph_tag, Base::traversal_category { };
+    };
+
+    template <typename D, typename P, typename B>
+    std::pair<typename edge_list_graph_archetype<D,P,B>::edge_iterator,
+              typename edge_list_graph_archetype<D,P,B>::edge_iterator>
+    edges(const edge_list_graph_archetype<D,P,B>&)
+    {
+        typedef typename edge_list_graph_archetype<D,P,B>::edge_iterator Iterator;
+        return std::make_pair(Iterator(), Iterator());
+    }
+
+    template <typename D, typename P, typename B>
+    typename edge_list_graph_archetype<D,P,B>::edges_size_type
+    num_edges(const edge_list_graph_archetype<D,P,B>& )
+    { return 0; }
+
+
+    //
+    // ProprertyGraph
+    //
+    // I don't know how this works for bundled properties. I might need to
+    // build a separate archetype for building bundled properties - and it
+    // might be really ugly.
+
+    // This little tag type here is used to associate the binding of graphs
+    // of this type to the appropriate property map types.
+    struct property_graph_archetype_tag { };
+
+    template <typename GraphArchetype, typename Property, typename ValueArch>
+    struct property_graph_archetype : public GraphArchetype
+    {
+        typedef property_graph_archetype_tag graph_tag;
+        typedef ValueArch vertex_property_type;
+        typedef ValueArch edge_property_type;
+    };
+
+    struct choose_edge_property_map_archetype
+    {
+        template <typename Graph, typename Property, typename Tag>
+        struct bind_ {
+            typedef typename graph_traits<Graph>::edge_descriptor Edge;
+            typedef mutable_lvalue_property_map_archetype<Edge, Property> type;
+            typedef lvalue_property_map_archetype<Edge, Property> const_type;
+        };
+    };
+
+    template <>
+    struct edge_property_selector<property_graph_archetype_tag>
+    {
+        typedef choose_edge_property_map_archetype type;
+    };
+
+    struct choose_vertex_property_map_archetype
+    {
+        template <typename Graph, typename Property, typename Tag>
+        struct bind_
+        {
+            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+            typedef mutable_lvalue_property_map_archetype<Vertex, Property> type;
+            typedef lvalue_property_map_archetype<Vertex, Property> const_type;
+        };
+    };
+
+    template <>
+    struct vertex_property_selector<property_graph_archetype_tag>
+    {
+        typedef choose_vertex_property_map_archetype type;
+    };
+
+    template <typename G, typename P, typename V>
+    typename property_map<property_graph_archetype<G,P,V>, P>::type
+    get(P, property_graph_archetype<G,P,V>&)
+    {
+        typename property_map<property_graph_archetype<G,P,V>, P>::type pmap;
+        return pmap;
+    }
+
+    template <typename G, typename P, typename V>
+    typename property_map<property_graph_archetype<G,P,V>, P>::const_type
+    get(P, const property_graph_archetype<G,P,V>&)
+    {
+        typename property_map<property_graph_archetype<G,P,V>, P>::const_type pmap;
+        return pmap;
+    }
+
+    template <typename G, typename P, typename K, typename V>
+    typename property_traits<
+            typename property_map<property_graph_archetype<G,P,V>, P>::const_type
+        >::value_type
+    get(P p, const property_graph_archetype<G,P,V>& g, K k)
+    {
+        return get(get(p, g), k);
+    }
+
+    template <typename G, typename P, typename V, typename K>
+    void
+    put(P p, property_graph_archetype<G,P,V>& g, K k, const V& v)
+    {
+        typedef typename boost::property_map<property_graph_archetype<G,P,V>, P>::type Map;
+        put(get(p, g), k, v);
+    }
+}
+
+
+#endif // BOOST_GRAPH_ARCHETYPES_HPP

Added: sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp	2007-08-16 12:12:04 EDT (Thu, 16 Aug 2007)
@@ -0,0 +1,309 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include "new_archetypes.hpp"
+#include <boost/graph/graph_traits.hpp>
+
+using namespace std;
+using namespace boost;
+
+bool is_incident(const incidence_graph_tag&)
+{ return true; }
+
+bool is_bidirectional(const bidirectional_graph_tag&)
+{ return true; }
+
+bool is_adjacent(const adjacency_graph_tag&)
+{ return true; }
+
+bool is_vertex_list(const vertex_list_graph_tag&)
+{ return true; }
+
+bool is_edge_list(const edge_list_graph_tag&)
+{ return true; }
+
+int
+main(int argc, char *argv[])
+{
+    // test the base-most graph concept
+    {
+        typedef graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > Graph;
+        typedef graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef graph_traits<Graph>::edge_descriptor Edge;
+        typedef graph_traits<Graph>::directed_category Directed;
+        typedef graph_traits<Graph>::edge_parallel_category Parallel;
+        typedef graph_traits<Graph>::traversal_category Traversal;
+
+        graph_traits<Graph>::null_vertex();
+    }
+
+    // an incidence graph allows access to the out-edges of a vertex
+    {
+        typedef incidence_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > IncidenceGraph;
+        typedef IncidenceGraph::vertex_descriptor Vertex;
+        typedef IncidenceGraph::edge_descriptor Edge;
+        typedef IncidenceGraph::directed_category Directed;
+        typedef IncidenceGraph::edge_parallel_category Parallel;
+        typedef IncidenceGraph::traversal_category Traversal;
+        typedef IncidenceGraph::degree_size_type Degree;
+        typedef IncidenceGraph::out_edge_iterator OutEdgeIterator;
+
+        is_incident(Traversal());
+        IncidenceGraph& g = static_object<IncidenceGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        out_edges(v, g);
+        out_degree(v, g);
+        Edge e = static_object<Edge>::get();
+        source(e, g);
+        target(e, g);
+    }
+
+    // bidirectional graphs provide accesst to both the out and in edges
+    {
+        typedef bidirectional_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > BidirectionalGraph;
+        typedef BidirectionalGraph::vertex_descriptor Vertex;
+        typedef BidirectionalGraph::edge_descriptor Edge;
+        typedef BidirectionalGraph::directed_category Directed;
+        typedef BidirectionalGraph::edge_parallel_category Parallel;
+        typedef BidirectionalGraph::traversal_category Traversal;
+        typedef BidirectionalGraph::degree_size_type Degree;
+        typedef BidirectionalGraph::out_edge_iterator OutEdgeIterator;
+        typedef BidirectionalGraph::in_edge_iterator InEdgeIterator;
+
+        is_incident(Traversal());
+        is_bidirectional(Traversal());
+        BidirectionalGraph& g = static_object<BidirectionalGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        out_edges(v, g);
+        out_degree(v, g);
+        in_edges(v, g);
+        in_degree(v, g);
+        Edge e = static_object<Edge>::get();
+        source(e, g);
+        target(e, g);
+    }
+
+    // This instantiates the non-compound adjacency list archetype
+    // It shouldn't be implementing any of the other graph concepts
+    {
+        typedef adjacency_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > AdjacencyGraph;
+        typedef AdjacencyGraph::vertex_descriptor Vertex;
+        typedef AdjacencyGraph::edge_descriptor Edge;
+        typedef AdjacencyGraph::directed_category Directed;
+        typedef AdjacencyGraph::edge_parallel_category Parallel;
+        typedef AdjacencyGraph::traversal_category Traversal;
+        typedef AdjacencyGraph::adjacency_iterator AdjacencyIterator;
+
+        is_adjacent(Traversal());
+        AdjacencyGraph& g = static_object<AdjacencyGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        adjacent_vertices(v, g);
+    }
+
+    // Make a bidirectional adjacency list (this is like part of a
+    // bidirected graph).
+    {
+        typedef bidirectional_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > BidirectionalGraph;
+        typedef adjacency_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag,
+                BidirectionalGraph
+            > AdjacencyGraph;
+        typedef AdjacencyGraph::traversal_category Traversal;
+        typedef AdjacencyGraph::vertex_descriptor Vertex;
+        typedef AdjacencyGraph::edge_descriptor Edge;
+
+        // test to see if these hold
+        is_incident(Traversal());
+        is_bidirectional(Traversal());
+        is_adjacent(Traversal());
+        AdjacencyGraph& g = static_object<AdjacencyGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        out_edges(v, g);
+        out_degree(v, g);
+        in_edges(v, g);
+        in_degree(v, g);
+        adjacent_vertices(v, g);
+        Edge e = static_object<Edge>::get();
+        source(e, g);
+        target(e, g);
+    }
+
+    // test a solo vertex list graph
+    {
+        typedef vertex_list_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > VertexListGraph;
+        typedef VertexListGraph::vertex_descriptor Vertex;
+        typedef VertexListGraph::edge_descriptor Edge;
+        typedef VertexListGraph::directed_category Directed;
+        typedef VertexListGraph::edge_parallel_category Parallel;
+        typedef VertexListGraph::traversal_category Traversal;
+        typedef VertexListGraph::vertices_size_type Vertices;
+        typedef VertexListGraph::vertex_iterator VertexIterator;
+
+        is_vertex_list(Traversal());
+        VertexListGraph& g = static_object<VertexListGraph>::get();
+        vertices(g);
+        num_vertices(g);
+    }
+
+    // test an incident vertex list graph (common requirements for a
+    // number of measures).
+    {
+        typedef incidence_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > IncidenceGraph;
+        typedef vertex_list_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag,
+                IncidenceGraph
+            > VertexListGraph;
+        typedef VertexListGraph::vertex_descriptor Vertex;
+        typedef VertexListGraph::edge_descriptor Edge;
+        typedef VertexListGraph::directed_category Directed;
+        typedef VertexListGraph::edge_parallel_category Parallel;
+        typedef VertexListGraph::traversal_category Traversal;
+        typedef VertexListGraph::vertices_size_type Vertices;
+        typedef VertexListGraph::vertex_iterator VertexIterator;
+
+        is_incident(Traversal());
+        is_vertex_list(Traversal());
+        VertexListGraph& g = static_object<VertexListGraph>::get();
+        vertices(g);
+        num_vertices(g);
+        Vertex v = static_object<Vertex>::get();
+        out_edges(v, g);
+        out_degree(v, g);
+        Edge e = static_object<Edge>::get();
+        source(e, g);
+        target(e, g);
+    }
+
+    // test a solo edge list graph
+    {
+        typedef edge_list_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > EdgeListGraph;
+        typedef EdgeListGraph::vertex_descriptor Vertex;
+        typedef EdgeListGraph::edge_descriptor Edge;
+        typedef EdgeListGraph::directed_category Directed;
+        typedef EdgeListGraph::edge_parallel_category Parallel;
+        typedef EdgeListGraph::traversal_category Traversal;
+        typedef EdgeListGraph::vertices_size_type Edges;
+        typedef EdgeListGraph::edge_iterator EdgeIterator;
+
+        is_edge_list(Traversal());
+        EdgeListGraph& g = static_object<EdgeListGraph>::get();
+        edges(g);
+        num_edges(g);
+    }
+
+    // test a bidirected, vertex/edge list graph
+    {
+        typedef bidirectional_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > BidirectionalGraph;
+        typedef edge_list_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag,
+                BidirectionalGraph
+            > EdgeListGraph;
+        typedef vertex_list_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag,
+                EdgeListGraph
+            > VertexListGraph;
+        typedef VertexListGraph::vertex_descriptor Vertex;
+        typedef VertexListGraph::edge_descriptor Edge;
+        typedef VertexListGraph::directed_category Directed;
+        typedef VertexListGraph::edge_parallel_category Parallel;
+        typedef VertexListGraph::traversal_category Traversal;
+        typedef VertexListGraph::vertices_size_type Edges;
+        typedef VertexListGraph::edge_iterator EdgeIterator;
+
+        is_incident(Traversal());
+        is_bidirectional(Traversal());
+        is_vertex_list(Traversal());
+        is_edge_list(Traversal());
+        VertexListGraph& g = static_object<VertexListGraph>::get();
+        vertices(g);
+        num_vertices(g);
+        edges(g);
+        num_edges(g);
+        Vertex v = static_object<Vertex>::get();
+        out_edges(v, g);
+        out_degree(v, g);
+        in_edges(v, g);
+        in_degree(v, g);
+        Edge e = static_object<Vertex>::get();
+        source(e, g);
+        target(e, g);
+    }
+
+    // test a mutable property graph
+    {
+        typedef bidirectional_graph_archetype <
+                undirected_tag,
+                allow_parallel_edge_tag
+            > BidirectionalGraph;
+        typedef property_graph_archetype <
+                BidirectionalGraph,
+                vertex_index_t,     // the property type
+                size_t              // the value type of the property (should be archetype?)
+            > IndexedGraph;
+        typedef IndexedGraph::vertex_descriptor Vertex;
+
+        IndexedGraph& g = static_object<IndexedGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        get(vertex_index, g);
+        get(vertex_index, g, v);
+        put(vertex_index, g, v, size_t());
+    }
+
+    // test a mutable property graph
+    {
+        typedef bidirectional_graph_archetype <
+                undirected_tag,
+                allow_parallel_edge_tag
+            > BidirectionalGraph;
+        typedef property_graph_archetype <
+                BidirectionalGraph,
+                vertex_index_t,     // the property type
+                size_t              // the value type of the property (should be archetype?)
+            > IndexedGraph;
+        typedef IndexedGraph::vertex_descriptor Vertex;
+
+        const IndexedGraph& g = static_object<IndexedGraph>::get();
+        Vertex v = static_object<Vertex>::get();
+        get(vertex_index, g);
+        get(vertex_index, g, v);
+
+        // This causes a compiler error if uncommented (as it should!)
+        // put(vertex_index, g, v, size_t());
+    }
+
+    return 0;
+}