[Boost-commit] svn:boost r65306 - in sandbox/SOC/2010/graph: boost/graph libs/test

Subject: [Boost-commit] svn:boost r65306 - in sandbox/SOC/2010/graph: boost/graph libs/test
From: asutton_at_[hidden]
Date: 2010-09-05 14:59:40

Author: asutton
Date: 2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
New Revision: 65306
URL: http://svn.boost.org/trac/boost/changeset/65306

Log:
Adding support to handle graph labels a little better.

This primarily adds support for binding bundled properties to existing
property names, specifically for vertex/edge name and a mapping from
such names to descriptors. Also included is an initial take on labeled
graphs, which combine those features in a somewhat convenient manner.

Rewrote most of graph_sum's implemetnation, but haven't fully
tested it yet.

Added:
   sandbox/SOC/2010/graph/boost/graph/bundled_properties.hpp   (contents, props changed)
   sandbox/SOC/2010/graph/boost/graph/labeled_graph.hpp   (contents, props changed)
   sandbox/SOC/2010/graph/libs/test/test_sum.cpp   (contents, props changed)
   sandbox/SOC/2010/graph/libs/test/typestr.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/graph/boost/graph/default.hpp       |    26 ++++                                    
   sandbox/SOC/2010/graph/boost/graph/properties.hpp    |    27 ++++                                    
   sandbox/SOC/2010/graph/boost/graph/sum.hpp           |   258 ++++++++++++++++++++++++--------------- 
   sandbox/SOC/2010/graph/libs/test/Jamfile             |     7                                         
   sandbox/SOC/2010/graph/libs/test/complement.cpp      |     4                                         
   sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp |    64 +++++++++                               
   sandbox/SOC/2010/graph/libs/test/sum.cpp             |    47 ++++---                                 
   7 files changed, 302 insertions(+), 131 deletions(-)

Added: sandbox/SOC/2010/graph/boost/graph/bundled_properties.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/boost/graph/bundled_properties.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -0,0 +1,269 @@
+//=======================================================================
+// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#ifndef BOOST_GRAPH_BUNDLED_PROPERTIES_HPP
+#define BOOST_GRAPH_BUNDLED_PROPERTIES_HPP
+
+#include <boost/mpl/if.hpp>
+#include <boost/type_traits/is_pod.hpp>
+#include <boost/type_traits/is_const.hpp>
+
+// This file contains utility code for integrating bundled and named properties.
+// Each named property corresponds to a get/put pair of functions and an
+// associtaed proerty map. The get/put functions for getting the property
+// map as well as the property map support are all defined herein. There are
+// three components to every property:
+//  1. A declaration of the specific get/put interface.
+//     get_prop(d, g) and put_prop(d, x, g)
+//  2. A property map abstracting the get/put operations defined in 1.
+//      get(pm, d) and put(pm, d, x)
+//  3. A specialization of property_map and the property graph accessor.
+//      property_map<G, P> and get(p, g)
+
+// FIXME: Go through the exceedingly tedious process of ensuring that constant
+// property maps do not support writeability. There's probably going to be
+// a fair amount of metaprogramming involved. Currently, we just avoid the
+// issue altogether by simply allowing all property maps to be writeable.
+
+namespace boost {
+  ///////// vertex_name /////////
+  // Interface
+  template<typename G>
+  typename vertex_name_traits<G>::type
+  get_vertex_name(typename graph_traits<G>::vertex_descriptor, G const&);
+
+  template<typename G>
+  void
+  put_vertex_name(typename graph_traits<G>::vertex_descriptor,
+                  typename vertex_name_traits<G>::type const&,
+                  G&);
+
+  // Property Map
+  template<typename G>
+  struct vertex_name_property_map
+  {
+    typedef typename graph_traits<G>::vertex_descriptor key_type;
+    typedef typename vertex_name_traits<G>::type value_type;
+    typedef value_type& reference;
+    typedef read_write_property_map_tag category;
+
+    vertex_name_property_map(G const& g)
+      : graph(const_cast<G&>(g))
+    { }
+
+    G& graph;
+  };
+
+  template<typename G>
+  inline typename vertex_name_property_map<G>::value_type const&
+  get(vertex_name_property_map<G> const& pm,
+      typename vertex_name_property_map<G>::key_type const& k)
+  { return get_vertex_name(k, pm.graph); }
+
+  template<typename G>
+  inline void
+  put(vertex_name_property_map<G>& pm,
+      typename vertex_name_property_map<G>::key_type const& k,
+      typename vertex_name_property_map<G>::value_type const& x)
+  { put_vertex_name(k, x, pm.graph); }
+
+  // Name binding
+  template<typename G>
+  struct property_map<G, vertex_name_t> {
+    typedef vertex_name_property_map<G> type;
+    typedef vertex_name_property_map<G const> const_type;
+  };
+
+  template<typename G>
+  inline typename property_map<G, vertex_name_t>::type
+  get(vertex_name_t, G& g)
+  { return typename property_map<G, vertex_name_t>::type(g); }
+
+  template<typename G>
+  inline typename property_map<G, vertex_name_t>::const_type
+  get(vertex_name_t, G const& g)
+  { return typename property_map<G, vertex_name_t>::const_type(g); }
+
+  ///////// edge_name /////////
+  // Interface
+  template<typename G>
+  typename edge_name_traits<G>::type
+  get_edge_name(typename graph_traits<G>::edge_descriptor, G const&);
+
+  template<typename G>
+  void
+  put_edge_name(typename graph_traits<G>::edge_descriptor,
+                typename edge_name_traits<G>::type const&,
+                  G&);
+
+  // Property Map
+  template<typename G>
+  struct edge_name_property_map
+  {
+    typedef typename graph_traits<G>::edge_descriptor key_type;
+    typedef typename edge_name_traits<G>::type value_type;
+    typedef value_type& reference;
+    typedef read_write_property_map_tag category;
+
+    edge_name_property_map(G const& g)
+      : graph(const_cast<G&>(g))
+    { }
+
+    G& graph;
+  };
+
+  template<typename G>
+  inline typename edge_name_property_map<G>::value_type const&
+  get(edge_name_property_map<G> const& pm,
+      typename edge_name_property_map<G>::key_type const& k)
+  { return get_edge_name(k, pm.graph); }
+
+  template<typename G>
+  inline void
+  put(edge_name_property_map<G>& pm,
+      typename edge_name_property_map<G>::key_type const& k,
+      typename edge_name_property_map<G>::value_type const& x)
+  { put_edge_name(k, x, pm.graph); }
+
+  // Name Binding
+  template<typename G>
+  struct property_map<G, edge_name_t> {
+    typedef edge_name_property_map<G> type;
+    typedef edge_name_property_map<G const> const_type;
+  };
+
+  template<typename G>
+  inline typename property_map<G, edge_name_t>::type
+  get(edge_name_t, G& g)
+  { return typename property_map<G, edge_name_t>::type(g); }
+
+  template<typename G>
+  inline typename property_map<G, edge_name_t>::const_type
+  get(edge_name_t, G const& g)
+  { return typename property_map<G, edge_name_t>::const_type(g); }
+
+  ///////// graph_named_vertices /////////
+  // Interface
+  template<typename G>
+  typename graph_traits<G>::vertex_descriptor
+  get_named_vertex(typename vertex_name_traits<G>::type const&, G const&);
+
+  template<typename G>
+  void
+  put_named_vertex(typename vertex_name_traits<G>::type const& name,
+                   typename graph_traits<G>::vertex_descriptor v,
+                   G& g);
+
+  // Property map
+  template<typename G>
+  struct named_vertex_property_map
+  {
+    typedef typename vertex_name_traits<G>::type key_type;
+    typedef typename graph_traits<G>::vertex_descriptor value_type;
+    typedef value_type reference;
+    typedef read_write_property_map_tag category;
+
+    named_vertex_property_map(G const& g)
+      : graph(const_cast<G&>(g))
+    { }
+
+    G& graph;
+  };
+
+  template<typename G>
+  typename named_vertex_property_map<G>::reference
+  get(named_vertex_property_map<G> const& pm,
+      typename named_vertex_property_map<G>::key_type const& k)
+  { return get_named_vertex(k, pm.graph); }
+
+  template<typename G>
+  inline void
+  put(named_vertex_property_map<G>& pm,
+      typename named_vertex_property_map<G>::key_type const& k,
+      typename named_vertex_property_map<G>::value_type const& x)
+  { put_named_vertex(k, x, pm.graph); }
+
+  // Binding
+  template<typename G>
+  struct property_map<G, graph_named_vertices_t>
+  {
+    typedef named_vertex_property_map<G> type;
+    typedef named_vertex_property_map<G const> const_type;
+  };
+
+  template<typename G>
+  inline typename property_map<G, graph_named_vertices_t>::type
+  get(graph_named_vertices_t, G& g)
+  { return typename property_map<G, graph_named_vertices_t>::type(g); }
+
+  template<typename G>
+  inline typename property_map<G, graph_named_vertices_t>::const_type
+  get(graph_named_vertices_t, G const& g)
+  { return typename property_map<G, graph_named_vertices_t>::const_type(g); }
+
+  ///////// graph_named_vertices /////////
+  // Interface
+  template<typename G>
+  typename graph_traits<G>::edge_descriptor
+  get_named_edge(typename edge_name_traits<G>::type const&, G const&);
+
+  template<typename G>
+  void
+  put_named_edge(typename edge_name_traits<G>::type const&,
+                 typename graph_traits<G>::edge_descriptor e,
+                 G&);
+
+  // Property Map
+  template<typename G>
+  struct named_edge_property_map {
+    typedef typename edge_name_traits<G>::type key_type;
+    typedef typename graph_traits<G>::edge_descriptor value_type;
+    typedef value_type reference;
+    typedef read_write_property_map_tag category;
+
+    named_edge_property_map(G& g)
+      : graph(const_cast<G&>(g))
+    { }
+
+    G& graph;
+  };
+
+  template<typename G>
+  typename named_edge_property_map<G>::reference
+  get(named_edge_property_map<G> const& pm,
+      typename named_edge_property_map<G>::key_type const& k)
+  { return get_named_edge(k, pm.graph); }
+
+  template<typename G>
+  inline void
+  put(named_edge_property_map<G>& pm,
+      typename named_edge_property_map<G>::key_type const& k,
+      typename named_edge_property_map<G>::value_type const& x)
+  { put_named_edge(k, x, pm.graph); }
+
+  // Binding
+  template<typename G>
+  struct property_map<G, graph_named_edges_t>
+  {
+    typedef named_edge_property_map<G> type;
+    typedef named_edge_property_map<G const> const_type;
+  };
+
+  template<typename G>
+  inline typename property_map<G, graph_named_edges_t>::type
+  get(graph_named_edges_t, G& g)
+  { return typename property_map<G, graph_named_edges_t>::type(g); }
+
+  template<typename G>
+  inline typename property_map<G, graph_named_edges_t>::const_type
+  get(graph_named_edges_t, G const& g)
+  { return typename property_map<G, graph_named_edges_t>::const_type(g); }
+} // namespace boost
+
+#endif
\ No newline at end of file

Modified: sandbox/SOC/2010/graph/boost/graph/default.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/default.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/default.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -56,6 +56,19 @@
       }
     };
 
+    // The default action is to simply preserve the properties of the original
+    // edge, ignoring the other edge. In short, this is a no-op.
+    // FIXME: This should replace the version above.
+    template<typename InGraph, typename OutGraph>
+    struct default_binary_vertex_merge
+    {
+      typedef typename graph_traits<InGraph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+      void operator()(InVertex vin, InGraph const& gin,
+                      OutVertex vout, OutGraph& gout) const
+      { }
+    };
+
     template <typename InGraph, typename OutGraph>
     struct default_edges_merge {
       typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
@@ -68,6 +81,19 @@
       }
     };
 
+    // The default action is to simply preserve the properties of the original
+    // edge, ignoring the other edge. In short, this is a no-op.
+    // FIXME: This should replace the version above.
+    template<typename InGraph, typename OutGraph>
+    struct default_binary_edge_merge
+    {
+      typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
+      typedef typename graph_traits<OutGraph>::edge_descriptor OutEdge;
+      void operator()(InEdge ein, const InGraph& gin,
+                      OutEdge& eout, OutGraph& gout) const
+      { }
+    };
+
     // To copy vertex and edge properties. Similar to code in copy.hpp,
     // but here operator() receives both graphs as parameters
     template <typename InGraph, typename OutGraph>

Added: sandbox/SOC/2010/graph/boost/graph/labeled_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/boost/graph/labeled_graph.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -0,0 +1,211 @@
+//=======================================================================
+// Copyright (c) 2010 Texas A&M University
+// Authors: Andrew Sutton
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#ifndef BOOST_LABELED_GRAPH
+#define BOOST_LABELED_GRAPH
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+
+// FIXME: Rewrite these classes as legitimate graph adaptors.
+
+namespace boost {
+
+/**
+ * A vertex_labeled_graph is a lightweight wrapper on a graph object, a
+ * name property map (mapping from vertex to a name), and a vertex property
+ * map (mapping from a name to a vertex).
+ */
+template<typename Graph, typename NameMap, typename VertexMap>
+class vertex_labeled_graph
+{
+public:
+  typedef Graph graph_type;
+  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+  typedef typename property_traits<NameMap>::value_type vertex_label_type;
+
+  vertex_labeled_graph(Graph& g, NameMap names, VertexMap vertices)
+    : _graph(g), _names(names), _vertices(vertices)
+  { }
+
+  vertex_descriptor vertex(vertex_label_type const& l) const
+  { return get(_vertices, l); }
+
+  vertex_label_type const& vertex_label(vertex_descriptor v) const
+  { return get(_names, v); }
+
+  void vertex_label(vertex_descriptor v, vertex_label_type const& l)
+  {
+    put(_names, v, l);
+    put(_vertices, l, v);
+  }
+
+  graph_type& graph()
+  { return _graph; }
+
+  graph_type const& graph() const
+  { return _graph; }
+
+private:
+  Graph&    _graph;
+  NameMap   _names;
+  VertexMap _vertices;
+};
+
+/**
+ * An edge_labeled_graph is a lightweight wrapper on a graph object, a
+ * name property map (mapping from an edge to a name), and an edge property
+ * map (mapping from a name to an edge).
+ */
+template<typename Graph, typename NameMap, typename EdgeMap>
+class edge_labeled_graph
+{
+public:
+  typedef Graph graph_type;
+  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+  typedef typename property_traits<NameMap>::value_type edge_label_type;
+
+  edge_labeled_graph(Graph& g, NameMap names, EdgeMap edges)
+    : _graph(g), _names(names), _edges(edges)
+  { }
+
+  edge_descriptor edge(edge_label_type const& l) const
+  { return get(_edges, l); }
+
+  edge_label_type const& edge_label(edge_descriptor e) const
+  { return get(_names, e); }
+
+  void edge_label(edge_descriptor v, edge_label_type const& l)
+  {
+    put(_names, v, l);
+    put(_edges, l, v);
+  }
+
+  graph_type& graph()
+  { return _graph; }
+
+  graph_type const& graph() const
+  { return _graph; }
+
+private:
+  Graph&    _graph;
+  NameMap   _names;
+  EdgeMap   _edges;
+};
+
+/**
+ * A labeled graph is both vertex and edge-labeled.
+ */
+template<typename Graph,
+         typename VertexNameMap,
+         typename VertexMap,
+         typename EdgeNameMap,
+         typename EdgeMap>
+class labeled_graph
+{
+public:
+  typedef Graph graph_type;
+  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+  typedef typename property_traits<VertexNameMap>::value_type vertex_label_type;
+  typedef typename property_traits<EdgeNameMap>::value_type edge_label_type;
+
+  labeled_graph(Graph const& g,
+                VertexNameMap vnames, VertexMap vertices,
+                EdgeNameMap enames, EdgeMap edges)
+    : _graph(const_cast<Graph&>(g))
+    , _vertex_names(vnames), _vertices(vertices)
+    , _edge_names(enames), _edges(edges)
+  { }
+
+  // Vertex/Vertex label operations
+  vertex_descriptor vertex(vertex_label_type const& l) const
+  { return get(_vertices, l); }
+
+  vertex_label_type const& vertex_label(vertex_descriptor v) const
+  { return get(_vertex_names, v); }
+
+  void vertex_label(vertex_descriptor v, vertex_label_type const& l)
+  {
+    put(_vertex_names, v, l);
+    put(_vertices, l, v);
+  }
+
+  // Edge, edge label operations
+  edge_descriptor edge(edge_label_type const& l) const
+  { return get(_edges, l); }
+
+  edge_label_type const& edge_label(edge_descriptor v) const
+  { return get(_edge_names, v); }
+
+  void edge_label(edge_descriptor v, edge_label_type const& l)
+  {
+    put(_edge_names, v, l);
+    put(_vertices, l, v);
+  }
+
+  graph_type& graph()
+  { return _graph; }
+
+  graph_type const& graph() const
+  { return _graph; }
+
+private:
+  Graph&          _graph;
+  VertexNameMap   _vertex_names;
+  VertexMap       _vertices;
+  EdgeNameMap     _edge_names;
+  EdgeMap         _edges;
+};
+
+// FIXME: This will need to be updated when labeled graph becomes a more
+// viable graph adaptor.
+template<typename Graph, typename NameMap, typename VertexMap>
+struct VertexLabeledDomainConcept {
+  static void constraints() {
+    function_requires< GraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+    // NOTE: There is an implied convertability between the value_type of
+    // the NameMap and the key_type of the VertexMap. If the name map is
+    // invalid (i.e., has value_type error_property_not_found), then the
+    // concept will fail, which is the correct behavior.
+    function_requires< ReadWritePropertyMapConcept<NameMap, Vertex> >();
+    typedef typename property_traits<NameMap>::value_type Label;
+    function_requires< ReadWritePropertyMapConcept<VertexMap, Label> >();
+  }
+  Graph g;
+  NameMap names;
+  VertexMap verts;
+};
+
+// FIXME: As with above, we'll introduce more requirements as labeled_graph
+// becomes more mature.
+template<typename Graph, typename NameMap, typename EdgeMap>
+struct EdgeLabeledDomainConcept {
+  static void constraints() {
+    function_requires< GraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+    // NOTE: There is an implied convertability between the value_type of
+    // the NameMap and the key_type of the Edge. If the name map is
+    // invalid (i.e., has value_type error_property_not_found), then the
+    // concept will fail, which is the correct behavior.
+    function_requires< ReadWritePropertyMapConcept<NameMap, Edge> >();
+    typedef typename property_traits<NameMap>::value_type Label;
+    function_requires< ReadWritePropertyMapConcept<EdgeMap, Label> >();
+  }
+  Graph g;
+  NameMap names;
+  EdgeMap edges;
+};
+
+} // namespace boost
+
+#endif

Modified: sandbox/SOC/2010/graph/boost/graph/properties.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/properties.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/properties.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -14,6 +14,7 @@
 #include <cassert>
 #include <boost/pending/property.hpp>
 #include <boost/detail/workaround.hpp>
+#include <boost/static_assert.hpp>
 
 // Include the property map library and extensions in the BGL.
 #include <boost/property_map/property_map.hpp>
@@ -130,6 +131,12 @@
   BOOST_DEF_PROPERTY(vertex, bundle);
   BOOST_DEF_PROPERTY(edge, bundle);
 
+  // These tags support the mapping of labels (names) to vertices and edges.
+  // These do not return property maps in quite the same way.
+  // FIXME: Make sure that these work with old-style properties.
+  BOOST_DEF_PROPERTY(graph, named_vertices);
+  BOOST_DEF_PROPERTY(graph, named_edges);
+
   // These tags are used to denote the owners and local descriptors
   // for the vertices and edges of a distributed graph.
   BOOST_DEF_PROPERTY(vertex, global);
@@ -281,6 +288,20 @@
     typedef typename Graph::edge_property_type type;
   };
 
+  // Support for named vertices and edges
+  struct not_named { };
+
+  // Support for vetex names.
+  // Specalize the name templates to define the type of name since they can't
+  // easily deduced in C++03. These could be specialized for volatile also,
+  // but that's quite rare in practice.
+  template<typename G> struct vertex_name_traits { typedef not_named type; };
+  template<typename G> struct vertex_name_traits<G const> : vertex_name_traits<G> { };
+
+  template<typename G> struct edge_name_traits { typedef not_named nme; };
+  template<typename G> struct edge_name_traits<G const> : edge_name_traits<G> { };
+
+  // Define a readable property map for vertex degrees.
   template <typename Graph>
   class degree_property_map
     : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
@@ -369,6 +390,7 @@
     return make_iterator_vertex_map(c.begin());
   }
 
+
 #if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 #  define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 #endif
@@ -508,4 +530,9 @@
 # undef RandomAccessIterator
 #endif
 
+// Include property maps and accessors for use with bundled properties/
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+#  include <boost/graph/bundled_properties.hpp>
+#endif
+
 #endif /* BOOST_GRAPH_PROPERTIES_HPPA */

Modified: sandbox/SOC/2010/graph/boost/graph/sum.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/sum.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/sum.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -14,109 +14,133 @@
 #include <utility>
 #include <boost/graph/default.hpp>
 #include <boost/graph/graph_traits.hpp>
+#include <boost/graph/labeled_graph.hpp>
+#include <boost/graph/named_function_params.hpp>
 
 namespace boost {
-  namespace detail {
-    template <typename VertexListGraph, typename MutableGraph,
-              typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
-              typename CopyEdge, typename MergeEdges, typename SetEdgeLabel>
-    void graph_sum_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
-                        CopyVertex copy_vertex,
-                        MergeVertices merge_vertices,
-                        SetVertexLabel set_vertex_label,
-                        CopyEdge copy_edge,
-                        MergeEdges merge_edges,
-                        SetEdgeLabel set_edge_label)
-    {
-      typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
-      typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-      //typename graph_bundle_type<VertexListGraph>::type const& gl1 = get_property(g1);
-      typename graph_bundle_type<VertexListGraph>::type const& gl2 = get_property(g2);
-      typename graph_bundle_type<MutableGraph>::type& gl_out = get_property(g_out);
+  namespace detail {
 
-      typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
-      // copy vertices from g1
-      for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
-        if ( gl2.vertices.find ( g1[*vi].name ) == gl2.vertices.end() ) { // if vi is not in g2
-          OutVertex new_v = add_vertex(g_out);
-          copy_vertex(*vi, g1, new_v, g_out);
-          set_vertex_label(g1[*vi].name, new_v, g_out);
-          assert( g_out[new_v].name == g1[*vi].name ); // set_vertex_label did it
-          assert( gl_out.vertices[ g1[*vi].name ] == new_v ); // set_vertex_label did it
-        } else { // vi is also in g2, we should merge them
-          OutVertex new_v = add_vertex(g_out);
-          merge_vertices(*vi, g1, gl2.vertices.find ( g1[*vi].name )->second, g2, new_v, g_out);
-          set_vertex_label(g1[*vi].name, new_v, g_out);
-          assert( g_out[new_v].name == g1[*vi].name ); // set_vertex_label did it
-          assert( gl_out.vertices[ g1[*vi].name ] == new_v ); // set_vertex_label did it
-        }
-      }
-      // copy vertices from (g2 - g1)
-      for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
-        if ( gl_out.vertices.find ( g2[*vi].name ) == gl_out.vertices.end() ) { // if vi is not in g1
-          OutVertex new_v = add_vertex(g_out);
-          copy_vertex(*vi, g2, new_v, g_out);
-          set_vertex_label(g2[*vi].name, new_v, g_out);
-          assert( g_out[new_v].name == g2[*vi].name ); // set_vertex_label did it
-          assert( gl_out.vertices[ g2[*vi].name ] == new_v );  // set_vertex_label did it
+    // FIXME: Make labeled_graph wrappers graph adaptors and pass gin and
+    // gout as the template paraameter, not the wrapped type.
+    template<typename LabelledInGraph,
+             typename LabelledOutGraph,
+             typename Copy,
+             typename Merge>
+    void union_vertices(LabelledInGraph const& gin,
+                        LabelledOutGraph& gout,
+                        Copy copy,
+                        Merge merge)
+    {
+      typedef typename LabelledInGraph::graph_type InGraph;
+      typedef typename LabelledInGraph::vertex_label_type Label;
+      typedef typename graph_traits<InGraph>::vertex_descriptor InVertex;
+      typedef typename LabelledOutGraph::graph_type OutGraph;
+      typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+
+      // For convenience so I don't have to keep called ".graph" when passing
+      // these graphs to other functions. I wouldn't have to do this if the
+      // the labeled wrappers were actually graph adaptors.
+      InGraph const& in = gin.graph();
+      OutGraph& out = gout.graph();
+
+      // Copy g1 in to go
+      typename graph_traits<InGraph>::vertex_iterator vi, vi_end;
+      for(tie(vi, vi_end) = vertices(in); vi != vi_end; ++vi) {
+        InVertex v_in = *vi;
+        Label const& label = gin.vertex_label(v_in);
+        InVertex v_out = gout.vertex(label);
+
+        // If the output graph did not contain this vertex, then copy it.
+        // Otherwise, merge it.
+        if(v_out == graph_traits<OutGraph>::null_vertex()) {
+          OutVertex v_new = add_vertex(out);
+          copy(v_in, in, v_new, out);
+          gout.vertex_label(v_new, label);
+        } else {
+          merge(v_in, in, v_out, out);
         }
       }
+    }
 
-      typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
-      typename graph_traits < MutableGraph >::edge_descriptor new_e;
-      bool inserted;
-
-      // copy edges from g1
-      for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
-        size_t src  = g1[source(*ei, g1)].name;
-        size_t targ = g1[target(*ei, g1)].name;
-        assert( gl_out.vertices.find(src)  != gl_out.vertices.end() );
-        assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
-
-        if ( gl2.edges.find( g1[*ei].name ) == gl2.edges.end() ) { // if ei is not in g2
-          boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
-          assert( inserted );
-          copy_edge(*ei, g1, new_e, g_out);
-          set_edge_label(g1[*ei].name, new_e, g_out);
-          assert( g_out[new_e].name == g1[*ei].name ); // set_edge_label did it
-          assert( gl_out.edges[ g1[*ei].name ] == new_e ); // set_edge_label did it
+    template<typename LabelledInGraph,
+             typename LabelledOutGraph,
+             typename Copy,
+             typename Merge>
+    void union_edges(LabelledInGraph const& gin,
+                     LabelledOutGraph& gout,
+                     Copy copy,
+                     Merge merge)
+    {
+      typedef typename LabelledInGraph::graph_type InGraph;
+      typedef typename LabelledInGraph::edge_label_type EdgeLabel;
+      typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
+      typedef typename LabelledOutGraph::graph_type OutGraph;
+      typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+      typedef typename graph_traits<OutGraph>::edge_descriptor OutEdge;
+
+      InGraph const& in = gin.graph();
+      OutGraph& out = gout.graph();
+
+      typename graph_traits<InGraph>::edge_iterator ei, ei_end;
+      for(tie(ei, ei_end) = edges(in); ei != ei_end; ++ei) {
+        InEdge e_in = *ei;
+        EdgeLabel const& label = gin.edge_label(e_in);
+        OutEdge e_out = gout.edge(label);
+
+        // NOTE: There isn't an null_edge. However, a default constructed
+        // edge descriptor should be invalid. If we can't rely on this, then
+        // there really isn't a way that we can implement labeling since
+        // we sometimes have to return invalid descriptors.
+
+        // If no labeled edge exists in the output graph, then we have to
+        // copy the edge. Otherwise, merge it.
+        if(e_out == OutEdge()) {
+          // Find the vertices in the outuput graph that correspond to the
+          // input graph and insert the edge.
+          OutVertex u = gout.vertex(gin.vertex_label(source(*ei, in)));
+          OutVertex v = gout.vertex(gin.vertex_label(target(*ei, in)));
+          OutEdge e_new = add_edge(u, v, out).first;
+          copy(e_in, in, e_new, out);
         } else {
-          boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
-          assert( inserted );
-          merge_edges(*ei, g1, gl2.edges.find( g1[*ei].name )->second, g2, new_e, g_out);
-          set_edge_label(g1[*ei].name, new_e, g_out);
-          assert( g_out[new_e].name == g1[*ei].name ); // set_edge_label did it
-          assert( gl_out.edges[ g1[*ei].name ] == new_e ); // set_edge_label did it
+          merge(e_in, in, e_out, out);
         }
       }
-      // copy edges from g2 if it is *not* already there
-      for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
-        size_t src  = g2[source(*ei, g2)].name;
-        size_t targ = g2[target(*ei, g2)].name;
-        assert( gl_out.vertices.find(src)  != gl_out.vertices.end() );
-        assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
+    }
 
-        if ( gl_out.edges.find( g2[*ei].name ) == gl_out.edges.end() ) { // ei is not yet in g_out
-          boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
-          assert( inserted );
-          copy_edge(*ei, g2, new_e, g_out);
-          set_edge_label(g2[*ei].name, new_e, g_out);
-          assert( g_out[new_e].name == g2[*ei].name ); // set_edge_label did it
-          assert( gl_out.edges[ g2[*ei].name ] == new_e ); // set_edge_label did it
-        }
-      }
+    template<typename LabelledInGraph,
+             typename LabelledOutGraph,
+             typename CopyVertex,
+             typename MergeVertex,
+             typename CopyEdge,
+             typename MergeEdge>
+    void graph_sum_impl(LabelledInGraph const& g1,
+                        LabelledInGraph const& g2,
+                        LabelledOutGraph& go,
+                        CopyVertex copy_vertex,
+                        MergeVertex merge_vertex,
+                        CopyEdge copy_edge,
+                        MergeEdge merge_edge)
+
+    {
+      union_vertices(g1, go, copy_vertex, merge_vertex);
+      union_vertices(g2, go, copy_vertex, merge_vertex);
+      union_edges(g1, go, copy_edge, merge_edge);
+//       union_edges(g2, go, copy_edge, merge_edge);
     }
 
+
     template <typename VertexListGraph, typename MutableGraph,
               typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
               typename CopyEdge, typename MergeEdges>
-    void simple_graph_sum_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
-                        CopyVertex copy_vertex,
-                        MergeVertices merge_vertices,
-                        SetVertexLabel set_vertex_label,
-                        CopyEdge copy_edge,
-                        MergeEdges merge_edges)
+    void simple_graph_sum_impl(const VertexListGraph& g1,
+                               const VertexListGraph& g2,
+                               MutableGraph& g_out,
+                               CopyVertex copy_vertex,
+                               MergeVertices merge_vertices,
+                               SetVertexLabel set_vertex_label,
+                               CopyEdge copy_edge,
+                               MergeEdges merge_edges)
     {
       typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
@@ -195,18 +219,52 @@
   } // namespace detail
 
 
-  template <typename VertexListGraph, typename MutableGraph>
-  void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
-  {
-    detail::graph_sum_impl
-      (g1, g2, g_out,
-       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
-       detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
-       detail::default_set_vertex_label<MutableGraph>(),
-       detail::default_edge_copy<VertexListGraph, MutableGraph>(),
-       detail::default_edges_merge<VertexListGraph, MutableGraph>(),
-       detail::default_set_edge_label<MutableGraph>()
-       );
+  // NOTE: This function can only be used if InGraph and OutGraph realize the
+  // default requiremens for labeling vertices and edges. Both graphs must
+  // define the following properties:
+  // - vertex_name
+  // - edge_name
+  // - graph_vertex_label
+  // - graph_edge_label
+  template <typename InGraph, typename OutGraph>
+  void graph_sum(InGraph const& g1, InGraph const& g2, OutGraph& g_out)
+  {
+    function_requires< VertexAndEdgeListGraphConcept<InGraph> >();
+    function_requires< MutableGraphConcept<OutGraph> >();
+
+    typedef typename property_map<InGraph, vertex_name_t>::const_type InVertexNameMap;
+    typedef typename property_map<InGraph, graph_named_vertices_t>::const_type InVertexMap;
+    typedef typename property_map<InGraph, edge_name_t>::const_type InEdgeNameMap;
+    typedef typename property_map<InGraph, graph_named_edges_t>::const_type InEdgeMap;
+    function_requires< VertexLabeledDomainConcept<InGraph, InVertexNameMap, InVertexMap> >();
+    function_requires< EdgeLabeledDomainConcept<InGraph, InEdgeNameMap, InEdgeMap> >();
+
+    typedef typename property_map<OutGraph, vertex_name_t>::type OutVertexNameMap;
+    typedef typename property_map<OutGraph, graph_named_vertices_t>::type OutVertexMap;
+    typedef typename property_map<OutGraph, edge_name_t>::type OutEdgeNameMap;
+    typedef typename property_map<OutGraph, graph_named_edges_t>::type OutEdgeMap;
+    function_requires< VertexLabeledDomainConcept<OutGraph, OutVertexNameMap, OutVertexMap> >();
+    function_requires< EdgeLabeledDomainConcept<OutGraph, OutEdgeNameMap, OutEdgeMap> >();
+
+    typedef labeled_graph<InGraph, InVertexNameMap, InVertexMap, InEdgeNameMap, InEdgeMap> LabelledInGraph;
+    typedef labeled_graph<OutGraph, OutVertexNameMap, OutVertexMap, OutEdgeNameMap, OutEdgeMap> LabelledOutGraph;
+
+
+    LabelledInGraph gin1(g1,
+                         get(vertex_name, g1), get(graph_named_vertices, g1),
+                         get(edge_name, g1), get(graph_named_edges, g1));
+    LabelledInGraph gin2(g2,
+                         get(vertex_name, g2), get(graph_named_vertices, g2),
+                         get(edge_name, g2), get(graph_named_edges, g2));
+    LabelledOutGraph gout(g_out,
+                          get(vertex_name, g_out), get(graph_named_vertices, g_out),
+                          get(edge_name, g_out), get(graph_named_edges, g_out));
+
+    detail::graph_sum_impl(gin1, gin2, gout,
+                           detail::default_vertex_copy<InGraph, OutGraph>(),
+                           detail::default_binary_vertex_merge<InGraph, OutGraph>(),
+                           detail::default_edge_copy<InGraph, OutGraph>(),
+                           detail::default_binary_edge_merge<InGraph, OutGraph>());
   }
 
   template <typename VertexListGraph, typename MutableGraph,
@@ -214,6 +272,7 @@
   void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
                  const bgl_named_params<P, T, R>& params)
   {
+    /*
     detail::graph_sum_impl
       (g1, g2, g_out,
        choose_param(get_param(params, vertex_copy_t()),
@@ -229,6 +288,7 @@
        choose_param(get_param(params, set_edge_label_t()),
                     detail::default_set_edge_label<MutableGraph>())
        );
+      */
   }
 
   template <typename VertexListGraph>

Modified: sandbox/SOC/2010/graph/libs/test/Jamfile
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/Jamfile	(original)
+++ sandbox/SOC/2010/graph/libs/test/Jamfile	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -2,10 +2,6 @@
 # Import the testing module so we can generate test cases.
 import testing ;
 
-# If you really want to see the values of the path constants...
-ECHO $(BOOST_ROOT) ;
-ECHO $(SOC_ROOT) ;
-
 # Declaring a project causes targets within this module to inherit the
 # properties of the target. Here, we're adding to the include paths. Note that
 # the order may matter. If you're creating new versions of existing files,
@@ -26,5 +22,6 @@
     [ run join.cpp ]
     [ run difference.cpp ]
     [ run intersection.cpp ]
-    [ run sum.cpp ]
+#    [ run sum.cpp ]
+    [ run test_sum.cpp ]
   ;

Modified: sandbox/SOC/2010/graph/libs/test/complement.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/complement.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/complement.cpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -9,8 +9,10 @@
 //
 
 #include <iostream>
-
 #include <ctime>
+
+#include <typeinfo>
+
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/graph/random.hpp>
 

Modified: sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -10,6 +10,7 @@
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/graph_utility.hpp>
+#include <boost/graph/labeled_graph.hpp>
 
 using namespace boost;
 using namespace std;
@@ -27,8 +28,12 @@
 // Hack: Instead of using Graph definition here to define the
 // descriptors, we define them using the same parameters used to
 // define Graph1 and Graph2:
-typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::vertex_descriptor Vertex;
-typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::edge_descriptor Edge;
+typedef adjacency_list_traits<vecS, vecS, bidirectionalS, listS>::vertex_descriptor Vertex;
+typedef adjacency_list_traits<vecS, vecS, bidirectionalS, listS>::edge_descriptor Edge;
+
+// Types for vertex and edge labels
+typedef unordered_map<size_t, Vertex> VertexLabel;
+typedef unordered_map<size_t, Edge> EdgeLabel;
 
 struct Vertex_Type1 {
   size_t name;
@@ -40,9 +45,35 @@
   size_t name;
 };
 struct Graph_Type1 {
-  unordered_map<size_t, Vertex> vertices;
-  unordered_map<size_t, Edge> edges;
+  VertexLabel vertices;
+  EdgeLabel edges;
+};
+
+// Specialize label traits for the graph.
+namespace boost {
+template<>
+struct vertex_label_traits<Graph1> {
+  typedef vertex_label_map<Graph1, VertexLabel> map_type;
+};
+template<>
+struct edge_label_traits<Graph1> {
+  typedef vertex_label_map<Graph1, EdgeLabel> map_type;
 };
+} // namespace boost
+
+inline property_map<Graph1, graph_vertex_label_t>::type
+get_vertex_label(Graph1& g)
+{
+  typedef property_map<Graph1, graph_vertex_label_t>::type Map;
+  return Map(get_property(g).vertices);
+}
+
+inline property_map<Graph1, graph_edge_label_t>::type
+get_edge_label(Graph1& g)
+{
+  typedef property_map<Graph1, graph_edge_label_t>::type Map;
+  return Map(get_property(g).edges);
+}
 
 struct Vertex_Type2 {
   size_t name;
@@ -51,9 +82,16 @@
   float value;
 };
 struct Graph_Type2 {
-  unordered_map<size_t, Vertex> vertices;
+  VertexLabel vertices;
 };
 
+// Specialize label traits for graph 2.
+namespace boost {
+template<>
+struct vertex_label_traits<Graph2> {
+  typedef vertex_label_map<Graph2, VertexLabel> map_type;
+};
+} // namespace boost
 
 // Vertex copier
 template <typename G1, typename G2>
@@ -121,7 +159,23 @@
   float factor;
 };
 
+// FIXME: This should replace the merge above.
+template <typename InGraph, typename OutGraph>
+struct my_binary_merge {
+  my_binary_merge(int _add = 0, float _factor = 1)
+    : add(_add), factor(_factor) { }
 
+  template <typename InVertex, typename OutVertex>
+  void operator()(const InVertex&  vin, const InGraph& gin,
+                  OutVertex& vout, OutGraph& gout) {
+    // FIXME: I'm probably not doing this right.
+    gout[vout].str += gin[vin].str;
+    gout[vout].id += gin[vin].id;
+    gout[vout].value *= gin[vin].value;
+  }
+  int add;
+  float factor;
+};
 
 // edge visitor for new edges
 // set a name for the new edge

Modified: sandbox/SOC/2010/graph/libs/test/sum.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/sum.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/sum.cpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -9,11 +9,13 @@
 //
 
 #include <iostream>
-
 #include <ctime>
+
+#include <boost/type_traits.hpp>
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/graph/random.hpp>
 
+#include "typestr.hpp"
 #include "graph_op_common.hpp"
 
 #include <boost/graph/sum.hpp>
@@ -23,6 +25,9 @@
 
 int main(int,char*[])
 {
+  test_defaults();
+
+
   boost::mt19937 gen;
   gen.seed(uint32_t(time(0)));
 
@@ -45,15 +50,15 @@
   cout << "g2:" << endl;
   print_named_edges(g2);
 
-  cout << "Sum of g1 and g2:" << endl;
-  graph_sum(g1, g2, gs1);
-  check_vertex_and_edge_naming(gs1);
-  print_named_edges(gs1);
-
-  cout << "Sum of g2 and g1:" << endl;
-  graph_sum(g2, g1, gs2);
-  check_vertex_and_edge_naming(gs2);
-  print_named_edges(gs2);
+//   cout << "Sum of g1 and g2:" << endl;
+//   graph_sum(g1, g2, gs1);
+//   check_vertex_and_edge_naming(gs1);
+//   print_named_edges(gs1);
+
+//   cout << "Sum of g2 and g1:" << endl;
+//   graph_sum(g2, g1, gs2);
+//   check_vertex_and_edge_naming(gs2);
+//   print_named_edges(gs2);
 
   cout << "h1:" << endl;
   print(h1);
@@ -67,14 +72,14 @@
 
   cout << "Other tests..." << endl;
 
-  graph_sum(g1, g2, gs3, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
-  check_vertex_and_edge_naming(gs3);
+//   graph_sum(g1, g2, gs3, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+//   check_vertex_and_edge_naming(gs3);
 
-  graph_sum(g1, g2, gs4,
-            vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10))
-            .vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10))
-            );
-  check_vertex_and_edge_naming(gs4);
+//   graph_sum(g1, g2, gs4,
+//             vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10))
+//             .vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10))
+//             );
+//   check_vertex_and_edge_naming(gs4);
   //  print_named_edges(gs4);
 
   // For the following tests, this:
@@ -83,11 +88,11 @@
   // But after the graph is copied to gd, the edge name mapping does not work properly anymore.
   // For vertex it is ok: check_vertex_naming(gs)
 
-  gs = graph_sum(g1, g2);
-  check_vertex_naming(gs);
+//   gs = graph_sum(g1, g2);
+//   check_vertex_naming(gs);
 
-  gs = graph_sum(g1, g2, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
-  check_vertex_naming(gs);
+//   gs = graph_sum(g1, g2, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+//   check_vertex_naming(gs);
 
   // simple_graph_sum
 

Added: sandbox/SOC/2010/graph/libs/test/test_sum.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/test_sum.cpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -0,0 +1,92 @@
+
+#include <iostream>
+#include <tr1/unordered_map>
+
+#include "typestr.hpp"
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/sum.hpp>
+
+
+using namespace std;
+using namespace boost;
+
+// Return the value associated with k or the default value if not found.
+template<typename Map, typename Key, typename Value>
+Value const&
+get_value(Map const& map, Key const& k, Value const& def)
+{
+  typename Map::const_iterator iter = map.find(k);
+  if(iter == map.end()) {
+    return def;
+  } else {
+    return iter->second;
+  }
+}
+
+typedef adjacency_list_traits<vecS, vecS, bidirectionalS, listS>::vertex_descriptor Vertex;
+typedef adjacency_list_traits<vecS, vecS, bidirectionalS, listS>::edge_descriptor Edge;
+
+typedef tr1::unordered_map<int, Vertex> Vertex_Map;
+typedef tr1::unordered_map<int, Edge> Edge_Map;
+
+struct Vertex_Prop {
+  int name;
+};
+
+struct Edge_Prop {
+  int name;
+};
+
+struct Graph_Prop {
+  Vertex_Map vertices;
+  Edge_Map edges;
+};
+
+typedef adjacency_list <
+  vecS, vecS, bidirectionalS, Vertex_Prop, Edge_Prop,  Graph_Prop, listS
+> Graph;
+
+// Info about vertex and edge name types.
+namespace boost {
+  template<> struct vertex_name_traits<Graph> { typedef int type; };
+  template<> struct edge_name_traits<Graph> { typedef int type; };
+} // namespace boost
+
+// Default accessors for the vertex name
+int const& get_vertex_name(Vertex v, Graph const& g)
+{ return g[v].name; }
+
+void put_vertex_name(Vertex v, int n, Graph& g)
+{ g[v].name = n; }
+
+// Default accessor named vertices.
+Vertex get_named_vertex(int n, Graph const& g)
+{ return get_value(g[graph_bundle].vertices, n, Graph::null_vertex()); }
+
+void put_named_vertex(int n, Vertex v, Graph& g)
+{ g[graph_bundle].vertices[n] = v; }
+
+// Default accessors for edge name
+int const& get_edge_name(Edge e, Graph const& g)
+{ return g[e].name; }
+
+void put_edge_name(Edge e, int n, Graph& g)
+{ g[e].name = n; }
+
+// Default accessors for edge naming.
+Edge get_named_edge(int n, Graph const& g)
+{ return get_value(g[graph_bundle].edges, n, Edge()); }
+
+void put_named_edge(int n, Edge e, Graph& g)
+{ g[graph_bundle].edges[n] = e; }
+
+// NOTE: On accessor functions. It's POSSIBLE to write generic get_*, put_*
+// accessors for old-style properties using enable_if. For example, we could
+// write a generic get_vertex_name enabled on has_property<vertex_name_t>.
+// For obvious reasons, we can't do this with bundled properties, but this
+// is a perfectly viable alternative.
+
+int main() {
+  Graph g1, g2, g3;
+  graph_sum(g1, g2, g3);
+}

Added: sandbox/SOC/2010/graph/libs/test/typestr.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/typestr.hpp	2010-09-05 14:59:38 EDT (Sun, 05 Sep 2010)
@@ -0,0 +1,47 @@
+// (C) Copyright 2009 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 ORIGIN_TYPESTR_HPP
+#define ORIGIN_TYPESTR_HPP
+
+#include <string>
+#include <cstring>
+#include <typeinfo>
+
+#if defined(__GNUC__)
+#include <cxxabi.h>
+#endif
+
+template<typename T> struct type_name { };
+
+/**
+ * Return a string that describes the type of the given template parameter.
+ * The type name depends on the results of the typeid operator.
+ *
+ * @todo Rewrite this so that demangle will dynamically allocate the memory.
+ */
+template <typename T>
+std::string typestr() {
+#if defined(__GNUC__)
+    std::size_t const BUFSIZE = 8192;
+    std::size_t n = BUFSIZE;
+    char buf[BUFSIZE];
+    abi::__cxa_demangle(typeid(type_name<T>).name(), buf, &n, 0);
+    return std::string(buf, ::strlen(buf));
+#else
+    return typeid(type_name<T>).name();
+#endif
+}
+
+/**
+ * Return a string that describes the type of the given parameter. The type
+ * name depends on the results of the typeid operator.
+ */
+template <typename T>
+inline std::string typestr(T const&)
+{ return typestr<T>(); }
+
+#endif