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

Subject: [Boost-commit] svn:boost r64736 - in sandbox/SOC/2010/graph: boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-11 05:09:55

Author: dbarbosa
Date: 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
New Revision: 64736
URL: http://svn.boost.org/trac/boost/changeset/64736

Log:
- Updating properties.hpp and making the code work with the new graph bundled property
- Default copy, merge and visitor parameter functions in default.hpp
- New parameter functions: set_vertex_label and set_edge_label; default functions in default.hpp
- Encapsulating my version of copy vertex and edge (with 4 parameters) to 2 paramters to be passed to copy_graph
- All algorithms working with Named Parameters, but there is still some work to be done (they reiceve at most one copy_vertex and one copy_edge, and disjoint union and join are not yet receiving orig_to_copy_t and vertex_index)
- Fixing copyright info
- Etc

Added:
   sandbox/SOC/2010/graph/boost/graph/default.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/graph/boost/graph/complement.hpp            |    55 ++++------                              
   sandbox/SOC/2010/graph/boost/graph/difference.hpp            |    85 ++++++++++++++++                        
   sandbox/SOC/2010/graph/boost/graph/intersection.hpp          |   164 ++++++++++++++++----------------        
   sandbox/SOC/2010/graph/boost/graph/join.hpp                  |   126 +++++++++++++++++++-----                
   sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp |     8 +                                       
   sandbox/SOC/2010/graph/boost/graph/properties.hpp            |    93 ++++++++++++------                      
   sandbox/SOC/2010/graph/boost/graph/sum.hpp                   |   202 ++++++++++++++++++++++++++------------- 
   sandbox/SOC/2010/graph/boost/graph/union.hpp                 |    76 +++++---------                          
   sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp          |    49 +++++----                               
   sandbox/SOC/2010/graph/libs/test/property_test.cpp           |   169 ++++++++++++++------------------        
   sandbox/SOC/2010/graph/libs/test/test.cpp                    |    10 +                                       
   11 files changed, 629 insertions(+), 408 deletions(-)

Modified: sandbox/SOC/2010/graph/boost/graph/complement.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/complement.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/complement.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
 //
 //=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -13,28 +12,21 @@
 #define BOOST_GRAPH_COMPLEMENT_HPP
 
 #include <utility>
-#include <boost/graph/global_vertex_mapping.hpp>
 #include <boost/graph/graph_traits.hpp>
-#include <boost/graph/copy.hpp>
+#include <boost/graph/default.hpp>
 
 namespace boost {
   namespace detail {
 
-    template <typename EdgeDescriptor, typename Graph>
-    struct default_edge_visitor {
-      void operator()(const EdgeDescriptor &, Graph &) { }
-    };
-
     template <typename Graph, typename MutableGraph,
               typename CopyVertex,
-              typename Orig2OutVertexIndexMap,
-              typename NewEdgeVisitor>
+              typename NewEdgeVisitor,
+              typename Orig2OutVertexIndexMap>
     void graph_complement_impl(const Graph& g_in, MutableGraph& g_out,
-                               CopyVertex copy_vertex, Orig2OutVertexIndexMap orig2out,
-                               NewEdgeVisitor edge_visitor,
+                               CopyVertex copy_vertex, NewEdgeVisitor edge_visitor,
+                               Orig2OutVertexIndexMap orig2out,
                                bool reflexive)
     {
-      typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
       typename graph_traits < Graph >::vertex_iterator vi, vi_end;
@@ -44,7 +36,7 @@
       for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
         OutVertex new_v = add_vertex(g_out);
         put(orig2out, *vi, new_v);
-        copy_vertex(*vi, new_v);
+        copy_vertex(*vi, g_in, new_v, g_out);
       }
 
       // create edges
@@ -62,31 +54,29 @@
         }
       }
     }
-  }// namespace detail
+  } // namespace detail
 
-  template <typename VertexListGraph, typename MutableGraph>
-  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
+  template <typename Graph, typename MutableGraph>
+  void graph_complement(const Graph& g_in, MutableGraph& g_out, bool reflexive)
   {
     typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
-    typedef typename graph_traits<MutableGraph>::edge_descriptor edge_t;
     std::vector<vertex_t> orig2out(num_vertices(g_in));
 
     detail::graph_complement_impl
       (g_in, g_out,
-       detail::make_vertex_copier(g_in, g_out),
+       detail::default_vertex_copy<Graph, MutableGraph>(),
+       detail::default_edge_visitor<MutableGraph>(),
        make_iterator_property_map(orig2out.begin(),
                                   get(vertex_index, g_in), orig2out[0]),
-       detail::default_edge_visitor<edge_t, MutableGraph>(),
        reflexive
        );
   }
 
-  template <typename VertexListGraph, typename MutableGraph,
+  template <typename Graph, typename MutableGraph,
             typename P, typename T, typename R>
-  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out,
+  void graph_complement(const Graph& g_in, MutableGraph& g_out,
                         const bgl_named_params<P, T, R>& params, bool reflexive)
   {
-    typedef typename graph_traits<MutableGraph>::edge_descriptor edge_t;
     typename std::vector<T>::size_type n;
     n = is_default_param(get_param(params, orig_to_copy_t()))
       ? num_vertices(g_in) : 1;
@@ -95,18 +85,21 @@
 
     detail::graph_complement_impl
       (g_in, g_out,
-       detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
-                                    g_in, g_out),
-       make_iterator_property_map(orig2out.begin(),
-                                  get(vertex_index, g_in), orig2out[0]),
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<Graph, MutableGraph>()),
        choose_param(get_param(params, edge_visitor_t()),
-                    detail::default_edge_visitor<edge_t, MutableGraph>()),
+                    detail::default_edge_visitor<MutableGraph>()),
+       choose_param(get_param(params, orig_to_copy_t()),
+                    make_iterator_property_map
+                    (orig2out.begin(),
+                     choose_const_pmap(get_param(params, vertex_index),
+                                       g_in, vertex_index), orig2out[0])),
        reflexive
        );
   }
 
-//  template <typename VertexListGraph, typename MutableGraph>
-//  void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+//  template <typename Graph, typename MutableGraph>
+//  void graph_reflexive_complement(const Graph& g_in, MutableGraph& g_out)
 //  {
 //    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
 //    std::vector<vertex_t> orig2out(num_vertices(g_in));

Added: sandbox/SOC/2010/graph/boost/graph/default.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/boost/graph/default.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,162 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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_DEFAULT_HPP
+#define BOOST_GRAPH_DEFAULT_HPP
+
+#include <utility>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost {
+  namespace detail {
+    // To visit brand new edges. Default behavior: it does nothing
+    template <typename Graph>
+    struct default_edge_visitor {
+      typedef typename graph_traits<Graph>::edge_descriptor EdgeDescriptor;
+      void operator()(const EdgeDescriptor &, Graph &) const { }
+    };
+
+    // To set labels
+    template <typename Graph>
+    struct default_set_vertex_label {
+      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+      void operator()(size_t label, Vertex& v, Graph& g) const {
+        g[v].name = label;
+        get_property(g).vertices[ label ] = v;
+      }
+    };
+
+    template <typename Graph>
+    struct default_set_edge_label {
+      typedef typename graph_traits<Graph>::edge_descriptor Edge;
+      void operator()(size_t label, Edge& e, Graph& g) const {
+        g[e].name = label;
+        get_property(g).edges[ label ] = e;
+      }
+    };
+
+    // Merge two vertices or two edges that are identified as the same (using the label)
+    // Default behavior is to copy the properties from the first input, ignoring the second
+    template <typename InGraph, typename OutGraph>
+    struct default_vertices_merge {
+      typedef typename graph_traits<InGraph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+      void operator()(const InVertex& v1, const InGraph&g1,
+                      const InVertex& v2, const InGraph&g2,
+                      OutVertex& v_out, OutGraph& g_out) const
+      {
+        put(get(vertex_all, g_out), v_out, get(get(vertex_all, g1), v1));
+      }
+    };
+
+    template <typename InGraph, typename OutGraph>
+    struct default_edges_merge {
+      typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
+      typedef typename graph_traits<OutGraph>::edge_descriptor OutEdge;
+      void operator()(const InEdge& e1, const InGraph&g1,
+                      const InEdge& e2, const InGraph&g2,
+                      OutEdge& e_out, OutGraph& g_out) const
+      {
+        put(get(edge_all, g_out), e_out, get(get(edge_all, g1), e1));
+      }
+    };
+
+    // 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>
+    struct default_vertex_copy {
+      typedef typename graph_traits<InGraph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+      void operator()(const InVertex& v_in, const InGraph&g_in,
+                      OutVertex& v_out, OutGraph& g_out) const
+      {
+        put(get(vertex_all, g_out), v_out, get(get(vertex_all, g_in), v_in));
+      }
+    };
+
+    template <typename InGraph, typename OutGraph>
+    struct default_edge_copy {
+      typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
+      typedef typename graph_traits<OutGraph>::edge_descriptor OutEdge;
+      void operator()(const InEdge& e_in, const InGraph&g_in,
+                      OutEdge& e_out, OutGraph& g_out) const
+      {
+        put(get(edge_all, g_out), e_out, get(get(edge_all, g_in), e_in));
+      }
+    };
+
+    // Encapsulation of copier interface taking four arguments
+    // (including both graphs - as defined above) to an interface used
+    // by copy.hpp (taking only two arguments).
+
+    template <typename GraphIn, typename GraphOut, typename Copier>
+    struct encapsulate_vertex_copier {
+      encapsulate_vertex_copier(const GraphIn& g_in, GraphOut& g_out, Copier copier)
+        : g_in(g_in), g_out(g_out), copier(copier) { }
+
+      template <typename VertexIn, typename VertexOut>
+      inline void operator()(const VertexIn& v_in, VertexOut& v_out) {
+        copier(v_in, g_in, v_out, g_out);
+      }
+    private:
+      const GraphIn& g_in;
+      GraphOut& g_out;
+      Copier copier;
+    };
+
+    template <typename Copier, typename GraphIn, typename GraphOut>
+    inline typename detail::encapsulate_vertex_copier<GraphIn, GraphOut, Copier>
+    to_two_parameters_vertex_copier(const GraphIn& g1, GraphOut& g2, Copier c)
+    {
+      return detail::encapsulate_vertex_copier<GraphIn, GraphOut, Copier> (g1, g2, c);
+    }
+
+    template <typename GraphIn, typename GraphOut, typename Copier>
+    struct encapsulate_edge_copier {
+      encapsulate_edge_copier(const GraphIn& g_in, GraphOut& g_out, Copier copier)
+        : g_in(g_in), g_out(g_out), copier(copier) { }
+
+      template <typename EdgeIn, typename EdgeOut>
+      inline void operator()(const EdgeIn& e_in, EdgeOut& e_out) {
+        copier(e_in, g_in, e_out, g_out);
+      }
+    private:
+      const GraphIn& g_in;
+      GraphOut& g_out;
+      Copier copier;
+    };
+
+    template <typename Copier, typename GraphIn, typename GraphOut>
+    inline typename detail::encapsulate_edge_copier<GraphIn, GraphOut, Copier>
+    to_two_parameters_edge_copier(const GraphIn& g1, GraphOut& g2, Copier c)
+    {
+      return detail::encapsulate_edge_copier<GraphIn, GraphOut, Copier> (g1, g2, c);
+    }
+
+//    template <typename Param, typename GraphIn, typename GraphOut>
+//    inline typename detail::encapsulate_edge_copier<GraphIn, GraphOut, Param>
+//    disjoint_union_choose_edge_copier(const GraphIn& g1, GraphOut& g2, Param param)
+//    {
+//      return detail::encapsulate_edge_copier<GraphIn, GraphOut, Param> (g1, g2, param);
+//    }
+//
+//    template <typename GraphIn, typename GraphOut>
+//    inline typename detail::encapsulate_edge_copier<GraphIn, GraphOut, typename detail::default_edge_copy<GraphIn, GraphOut> >
+//    disjoint_union_choose_edge_copier(const GraphIn& g1, GraphOut& g2, detail::error_property_not_found)
+//    {
+//      return detail::encapsulate_edge_copier<GraphIn, GraphOut, typename detail::default_edge_copy<GraphIn, GraphOut> >
+//        (g1, g2, detail::default_edge_copy<GraphIn, GraphOut>());
+//    }
+
+
+  } // namespace detail
+} // namespace boost
+
+#endif // BOOST_GRAPH_DEFAULT_HPP

Modified: sandbox/SOC/2010/graph/boost/graph/difference.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/difference.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/difference.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
 //
 //=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -15,12 +14,90 @@
 #include <utility>
 #include <boost/graph/global_vertex_mapping.hpp>
 #include <boost/graph/graph_traits.hpp>
-#include <boost/graph/copy.hpp>
+#include <boost/graph/default.hpp>
 
 namespace boost {
+  namespace detail {
+    template <typename Graph, typename MutableGraph,
+              typename CopyVertex, typename SetVertexLabel,
+              typename CopyEdge, typename SetEdgeLabel>
+    void graph_difference_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+                               CopyVertex copy_vertex,
+                               SetVertexLabel set_vertex_label,
+                               CopyEdge copy_edge,
+                               SetEdgeLabel set_edge_label)
+    {
+      typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+      auto & gl1 = get_property(g1);
+      auto & gl2 = get_property(g2);
+      auto & gl_out = get_property(g_out);
+
+      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+      // copy vertices from g1
+      for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+        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
+      }
+
+      // copy edges from g1 that are not in g2
+      typename graph_traits < Graph >::edge_iterator ei, ei_end;
+      for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+        auto src  = g1[source(*ei, g1)].name;
+        auto 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
+          typename graph_traits<MutableGraph>::edge_descriptor new_e;
+          bool inserted;
+          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
+        }
+      }
+    }
+  } // namespace detail
+
+  template <typename Graph, typename MutableGraph>
+  void graph_difference(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  {
+    detail::graph_difference_impl
+      (g1, g2, g_out,
+       detail::default_vertex_copy<Graph, MutableGraph>(),
+       detail::default_set_vertex_label<MutableGraph>(),
+       detail::default_edge_copy<Graph, MutableGraph>(),
+       detail::default_set_edge_label<MutableGraph>()
+       );
+  }
+
+  template <typename Graph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_difference(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+                        const bgl_named_params<P, T, R>& params)
+  {
+    detail::graph_difference_impl
+      (g1, g2, g_out,
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<Graph, MutableGraph>()),
+       choose_param(get_param(params, set_vertex_label_t()),
+                    detail::default_set_vertex_label<MutableGraph>()),
+       choose_param(get_param(params, edge_copy_t()),
+                    detail::default_edge_copy<Graph, MutableGraph>()),
+       choose_param(get_param(params, set_edge_label_t()),
+                    detail::default_set_edge_label<MutableGraph>())
+       );
+  }
 
   // Version with globalVertexMapping
-  template <class VertexListGraph, class MutableGraph, class globalVertexMapping> 
+  template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
   void gvm_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
   {
     typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;

Modified: sandbox/SOC/2010/graph/boost/graph/intersection.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/intersection.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/intersection.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
 //
 //=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -15,100 +14,103 @@
 #include <utility>
 #include <boost/graph/global_vertex_mapping.hpp>
 #include <boost/graph/graph_traits.hpp>
+#include <boost/graph/default.hpp>
 
 namespace boost {
-
-  // Question:
-  // Should we have a function to iterate over vertex making a copy if a predicates holds and another one for edges?
-  // This code pattern appears everywhere.
-
-  template <class VertexListGraph, class MutableGraph> 
-  void graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
-  {
-    typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
-    typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
-
-    // we only copy properties from g1
-    detail::vertex_copier<VertexListGraph, MutableGraph> copy_vertex = detail::make_vertex_copier(g1, g_out);
-    detail::edge_copier<VertexListGraph, MutableGraph> copy_edge = detail::make_edge_copier(g1, g_out);
-
-    auto & gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
-    auto & gl2 = get_property(g2, graph_label).hack->vertices;
-    auto & gl_out = get_property(g_out, graph_label).hack->vertices;
-
-    // copy vertices from (g1 intersection g2)
-    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
-    for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
-      if ( gl2.find( g1[*vi].name ) != gl2.end() ) { // if vi is in g2
-        OutVertex new_v = add_vertex(g_out);
-        copy_vertex(*vi, new_v);
-        assert( g_out[new_v].name == g1[*vi].name ); // copy_vertex already did it
-        gl_out[ g1[*vi].name ] = new_v;
+  namespace detail {
+    template <typename Graph, typename MutableGraph,
+              typename MergeVertices, typename SetVertexLabel,
+              typename MergeEdges, typename SetEdgeLabel>
+    void graph_intersection_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+                                 MergeVertices merge_vertices,
+                                 SetVertexLabel set_vertex_label,
+                                 MergeEdges merge_edges,
+                                 SetEdgeLabel set_edge_label)
+    {
+      typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+      auto & gl1 = get_property(g1);
+      auto & gl2 = get_property(g2);
+      auto & gl_out = get_property(g_out);
+
+      // copy vertices from (g1 intersection g2)
+      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+      for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+        if ( gl2.vertices.find( g1[*vi].name ) != gl2.vertices.end() ) { // if vi is in g2
+          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 edges from (g1 intersection g2)
-    // *not* using the edge name! (but checking with an assert)
-    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
-    for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
-      auto src  = g1[source(*ei, g1)].name;
-      auto targ = g1[target(*ei, g1)].name;
-      auto g2_s = gl2.find(src);
-      auto g2_t = gl2.find(targ);
-
-      if ( (g2_s != gl2.end() && g2_t != gl2.end() && edge(g2_s->second, g2_t->second, g2).second) ) {
-        assert( gl_out.find(src)  != gl_out.end() );
-        assert( gl_out.find(targ) != gl_out.end() );
-        assert( g1[ *ei ].name == g2[ edge(g2_s->second, g2_t->second, g2).first ].name );
-
-        typename graph_traits<MutableGraph>::edge_descriptor new_e;
-        bool inserted;
-        boost::tie(new_e, inserted) = add_edge(gl_out[src], gl_out[targ], g_out);
-        copy_edge(*ei, new_e);
-        assert( g_out[new_e].name == g1[*ei].name ); // copy_edge already did it
-        get_property(g_out, graph_label).hack->edges[ g1[*ei].name ] = new_e;
+      typename graph_traits < Graph >::edge_iterator ei, ei_end;
+      typename graph_traits < MutableGraph >::edge_descriptor new_e;
+      bool inserted;
+      // copy edges from (g1 intersection g2)
+      for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+        auto src  = g1[source(*ei, g1)].name;
+        auto 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 in g2
+          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[ g1[*ei].name ], g2, new_e, g_out); // Does not compile! Why?
+          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
+        }
       }
     }
+  } // namespace detail
 
-#if 0
-    // if we use the edge name, the code is the following:
-    // copy edges from (g1 intersection g2)
-    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
-    for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
-      auto gl2e = get_property(g2, graph_label).hack->edges;
-
-      if ( gl2e.find( g1[*ei].name ) != gl2e.end() ) {
-        auto out_s = gl_out.find( g1[source(*ei, g1)].name );
-        auto out_t = gl_out.find( g1[target(*ei, g1)].name );
-
-        assert(out_s != gl_out.end() && out_t != gl_out.end());
-        assert( g2[ source(gl2e[g1[*ei].name], g2) ].name == g1[ source(*ei, g1) ].name);
-        assert( g2[ target(gl2e[g1[*ei].name], g2) ].name == g1[ target(*ei, g1) ].name);
-
-        typename graph_traits<MutableGraph>::edge_descriptor new_e;
-        bool inserted;
-        boost::tie(new_e, inserted) = add_edge(out_s->second, out_t->second, g_out);
-        copy_edge(*ei, new_e);
-        assert( g_out[new_e].name == g1[*ei].name ); // copy_edge already did it
-        get_property(g_out, graph_label).hack->edges[ g1[*ei].name ] = new_e;
-      }
-    }
-#endif // if 0
+  template <typename Graph, typename MutableGraph>
+  void graph_intersection(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  {
+    detail::graph_intersection_impl
+      (g1, g2, g_out,
+       detail::default_vertices_merge<Graph, MutableGraph>(),
+       detail::default_set_vertex_label<MutableGraph>(),
+       detail::default_edges_merge<Graph, MutableGraph>(),
+       detail::default_set_edge_label<MutableGraph>()
+       );
   }
 
+  template <typename Graph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_intersection(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+                          const bgl_named_params<P, T, R>& params)
+  {
+    detail::graph_intersection_impl
+      (g1, g2, g_out,
+       choose_param(get_param(params, vertices_merge_t()),
+                    detail::default_vertices_merge<Graph, MutableGraph>()),
+       choose_param(get_param(params, set_vertex_label_t()),
+                    detail::default_set_vertex_label<MutableGraph>()),
+       choose_param(get_param(params, edges_merge_t()),
+                    detail::default_edges_merge<Graph, MutableGraph>()),
+       choose_param(get_param(params, set_edge_label_t()),
+                    detail::default_set_edge_label<MutableGraph>())
+       );
+  }
 
   // Version with globalVertexMapping
-  template <class VertexListGraph, class MutableGraph, class globalVertexMapping> 
-  void gvm_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+  template <class Graph, class MutableGraph, class globalVertexMapping> 
+  void gvm_graph_intersection(const Graph& g1, const Graph& g2, globalVertexMapping m, MutableGraph& g_out)
   {
-    typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+    typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
     typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-    detail::vertex_copier<VertexListGraph, MutableGraph> copy_vertex = detail::make_vertex_copier(g1, g_out);
-    detail::edge_copier<VertexListGraph, MutableGraph> copy_edge = detail::make_edge_copier(g1, g_out);
+    detail::vertex_copier<Graph, MutableGraph> copy_vertex = detail::make_vertex_copier(g1, g_out);
+    detail::edge_copier<Graph, MutableGraph> copy_edge = detail::make_edge_copier(g1, g_out);
 
     // copy vertices from (g1 intersection g2)
-    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+    typename graph_traits < Graph >::vertex_iterator vi, vi_end;
     for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
       std::pair < InVertex, bool > v = m.find_vertex( g1, *vi, g2 ); // search for vi in g2
       if (v.second == true) { // vi is also in g2
@@ -121,7 +123,7 @@
     }
 
     // copy edges from (g1 intersection g2)
-    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+    typename graph_traits < Graph >::edge_iterator ei, ei_end;
     for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
       std::pair < InVertex,  bool > g2_s, g2_t;
       std::pair < OutVertex, bool > out_s, out_t;

Modified: sandbox/SOC/2010/graph/boost/graph/join.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/join.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/join.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
 //
 //=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -9,6 +8,9 @@
 //=======================================================================
 //
 
+// Todo:
+// - Make it use orig_to_copy_t and vertex_index Named Parameters
+
 #ifndef BOOST_GRAPH_JOIN_HPP
 #define BOOST_GRAPH_JOIN_HPP
 
@@ -17,35 +19,105 @@
 #include <boost/graph/union.hpp>
 
 namespace boost {
+  namespace detail {
+    template <typename Graph, typename MutableGraph,
+              typename CopyVertex, typename CopyEdge,
+              typename NewEdgeVisitor,
+              typename In2OutVertexIndexMap>
+    void graph_join_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+                         CopyVertex copy_vertex,
+                         CopyEdge copy_edge,
+                         NewEdgeVisitor edge_visitor,
+                         In2OutVertexIndexMap g1_to_out, In2OutVertexIndexMap g2_to_out)
+    {
+      bool directed = is_convertible<typename MutableGraph::directed_category, directed_tag>::value;
+      // if disjoint union was receiving two In2OutVertexIndexMap, then we could just call disjoint union here
+
+      copy_graph
+        (g1, g_out,
+         orig_to_copy(g1_to_out)
+         .vertex_copy(detail::to_two_parameters_vertex_copier(g1, g_out, copy_vertex))
+         .edge_copy(detail::to_two_parameters_edge_copier(g1, g_out, copy_edge))
+         );
+
+      copy_graph
+        (g2, g_out,
+         orig_to_copy(g2_to_out)
+         .vertex_copy(detail::to_two_parameters_vertex_copier(g2, g_out, copy_vertex))
+         .edge_copy(detail::to_two_parameters_edge_copier(g2, g_out, copy_edge))
+         );
+
+      typename graph_traits < Graph >::vertex_iterator vi, vi_end, ui, ui_end;
+      for (tie(ui, ui_end) = vertices(g1); ui != ui_end; ++ui) {
+        for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+          typename graph_traits<MutableGraph>::edge_descriptor new_e;
+          bool inserted;
+          boost::tie(new_e, inserted) = add_edge(get(g1_to_out, *ui),
+                                                 get(g2_to_out, *vi),
+                                                 g_out);
+          assert(inserted);
+          edge_visitor(new_e, g_out);
+
+          if (directed) {
+            boost::tie(new_e, inserted) = add_edge(get(g2_to_out, *vi),
+                                                   get(g1_to_out, *ui),
+                                                   g_out);
+            assert(inserted);
+            edge_visitor(new_e, g_out);
+          }
+        }
+      }
+    }
+  } // namespace detail
+
 
-  template <class VertexListGraph, class MutableGraph> 
-  void graph_join(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  template <class Graph, class MutableGraph>
+  void graph_join(const Graph& g1, const Graph& g2, MutableGraph& g_out)
   {
-    typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
+    std::vector<vertex_t> g1_to_out(num_vertices(g1));
+    std::vector<vertex_t> g2_to_out(num_vertices(g2));
+    detail::graph_join_impl
+      (g1, g2, g_out,
+       detail::default_vertex_copy<Graph, MutableGraph>(),
+       detail::default_edge_copy<Graph, MutableGraph>(),
+       detail::default_edge_visitor<MutableGraph>(),
+       make_iterator_property_map(g1_to_out.begin(),
+                                  get(vertex_index, g1), g1_to_out[0]),
+       make_iterator_property_map(g2_to_out.begin(),
+                                  get(vertex_index, g2), g2_to_out[0])
+       );
+  }
 
-    auto & gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
-    auto & gl2 = get_property(g2, graph_label).hack->vertices;
-    auto & gl_out  = get_property(g_out, graph_label).hack->vertices;
-
-    typename graph_traits < MutableGraph >::vertex_iterator vi, vi_end;
-    typename graph_traits < MutableGraph >::vertex_iterator ui, ui_end;
-
-    typedef typename VertexListGraph::directed_category Dr;
-    bool directed = is_convertible<Dr, directed_tag>::value;
-
-    graph_union(g1, g2, g_out);
-
-    for (tie(ui, ui_end) = vertices(g1); ui != ui_end; ++ui) {
-      for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
-        OutVertex u = gl_out [ g1[*ui].name ];
-        OutVertex v = gl_out [ g2[*vi].name ];
-        typename graph_traits<MutableGraph>::edge_descriptor new_e;
-        bool inserted;
-        boost::tie(new_e, inserted) = add_edge(u, v, g_out);
-        if (directed)
-          boost::tie(new_e, inserted) = add_edge(v, u, g_out);
-      }
+  template <typename Graph, typename MutableGraph, typename P, typename T, typename R>
+  void graph_join(const Graph& g1, const Graph& g2, MutableGraph &g_out,
+                            const bgl_named_params<P, T, R>& params)
+  {
+    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
+    typename std::vector<T>::size_type n1, n2;
+    if (is_default_param(get_param(params, orig_to_copy_t()))) {
+      n1 = num_vertices(g1);
+      n2 = num_vertices(g2);
+    } else {
+      n1 = n2 = 1;
     }
+    std::vector<vertex_t> g1_to_out(n1);
+    std::vector<vertex_t> g2_to_out(n2);
+
+    detail::graph_join_impl
+      (g1, g2, g_out,
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<Graph, MutableGraph>()),
+       //     detail::default_edge_copy<Graph, MutableGraph>(),
+       choose_param(get_param(params, edge_copy_t()),
+                    detail::default_edge_copy<Graph, MutableGraph>()),
+       choose_param(get_param(params, edge_visitor_t()),
+                    detail::default_edge_visitor<MutableGraph>()),
+       make_iterator_property_map(g1_to_out.begin(),
+                                  get(vertex_index, g1), g1_to_out[0]),
+       make_iterator_property_map(g2_to_out.begin(),
+                                  get(vertex_index, g2), g2_to_out[0])
+       );
   }
 
 } // namespace boost

Modified: sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -31,6 +31,10 @@
   struct edge_copy_t { };
   struct vertex_copy_t { };
   struct edge_visitor_t { };
+  struct vertices_merge_t { };
+  struct edges_merge_t { };
+  struct set_vertex_label_t { };
+  struct set_edge_label_t { };
   struct vertex_isomorphism_t { };
   struct vertex_invariant_t { };
   struct vertex_invariant1_t { };
@@ -81,6 +85,10 @@
     BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \
     BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \
     BOOST_BGL_ONE_PARAM_CREF(edge_visitor, edge_visitor) \
+    BOOST_BGL_ONE_PARAM_CREF(vertices_merge, vertices_merge) \
+    BOOST_BGL_ONE_PARAM_CREF(edges_merge, edges_merge) \
+    BOOST_BGL_ONE_PARAM_CREF(set_vertex_label, set_vertex_label) \
+    BOOST_BGL_ONE_PARAM_CREF(set_edge_label, set_edge_label) \
     BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \
     BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \
     BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \

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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -88,7 +88,6 @@
   BOOST_DEF_PROPERTY(vertex, all);
   BOOST_DEF_PROPERTY(edge, all);
   BOOST_DEF_PROPERTY(graph, all);
-  BOOST_DEF_PROPERTY(graph, label);
   BOOST_DEF_PROPERTY(vertex, index);
   BOOST_DEF_PROPERTY(vertex, index1);
   BOOST_DEF_PROPERTY(vertex, index2);
@@ -127,6 +126,7 @@
   BOOST_DEF_PROPERTY(graph, visitor);
 
   // These tags are used for property bundles
+  BOOST_DEF_PROPERTY(graph, bundle);
   BOOST_DEF_PROPERTY(vertex, bundle);
   BOOST_DEF_PROPERTY(edge, bundle);
 
@@ -200,6 +200,7 @@
     };
     template <class Graph, class PropertyTag>
     class vertex_property_map {
+    public:
       typedef typename vertex_property_type<Graph>::type Property;
       typedef typename graph_tag_or_void<Graph>::type graph_tag;
       typedef typename vertex_property_selector<graph_tag>::type Selector;
@@ -243,7 +244,7 @@
 
   template <class Graph, class Property>
   struct property_map {
-  private:
+  // private:
     typedef typename property_kind<Property>::type Kind;
     typedef typename detail::property_map_kind_selector<Kind>::type Selector;
     typedef typename Selector::template bind_<Graph, Property> Bind;
@@ -264,8 +265,9 @@
   template <class Graph, class Property>
   class graph_property {
   public:
-    typedef typename property_value<typename Graph::graph_property_type,
-      Property>::type type;
+    typedef typename property_value<
+      typename Graph::graph_property_type, Property
+    >::type type;
   };
 
   template <class Graph>
@@ -433,44 +435,71 @@
 // These metafunctions help implement the process of determining the vertex
 // and edge properties of a graph.
 namespace graph_detail {
-    template <typename Retag>
+    template<typename Retag>
     struct retagged_property {
         typedef typename Retag::type type;
     };
 
-    template <typename Retag, typename With, typename Without>
+    // Search the normalized PropList (as returned by retagged<>::type) for
+    // the given bundle. Return the type error if no such bundle can be found.
+    template <typename PropList, typename Bundle>
     struct retagged_bundle {
-        typedef typename mpl::if_<
-            is_same<typename Retag::retagged, no_property>,
-            Without,
-            With
-        >::type type;
-    };
-
-    template <typename Prop>
-    struct vertex_prop {
-    private:
-        typedef detail::retag_property_list<vertex_bundle_t, Prop> Retag;
-    public:
-        typedef typename retagged_property<Retag>::type type;
-        typedef typename retagged_bundle<
-            Retag, Prop, no_vertex_bundle
-        >::type bundle;
+      typedef typename property_value<PropList, Bundle>::type Value;
+      typedef typename mpl::if_<
+        is_same<Value, detail::error_property_not_found>, no_bundle, Value
+      >::type type;
     };
 
-    template <typename Prop>
-    struct edge_prop {
-//     private:
-        typedef detail::retag_property_list<edge_bundle_t, Prop> Retag;
+    template<typename Prop, typename Bundle>
+    class normal_property {
+      // Normalize the property into a property list.
+      typedef detail::retag_property_list<Bundle, Prop> List;
     public:
-        typedef typename Retag::retagged retagged;
-        typedef typename retagged_property<Retag>::type type;
-        typedef typename retagged_bundle<
-            Retag, Prop, no_edge_bundle
-        >::type bundle;
-    };
+      // Extract the normalized property and bundle types.
+      typedef typename retagged_property<List>::type property;
+      typedef typename retagged_bundle<property, Bundle>::type bundle;
+    };
+
+    template<typename Prop>
+    struct graph_prop : normal_property<Prop, graph_bundle_t>
+    { };
+
+    template<typename Prop>
+    struct vertex_prop : normal_property<Prop, vertex_bundle_t>
+    { };
+
+    template<typename Prop>
+    struct edge_prop : normal_property<Prop, edge_bundle_t>
+    { };
 } // namespace graph_detail
 
+// NOTE: These functions are declared, but never defined since they need to
+// be overloaded by graph implementations. However, we need them to be
+// declared for the functions below.
+template<typename Graph, typename Tag>
+typename graph_property<Graph, graph_bundle_t>::type&
+get_property(Graph& g, Tag);
+
+template<typename Graph, typename Tag>
+typename graph_property<Graph, graph_bundle_t>::type const&
+get_property(Graph const& g, Tag);
+
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+// NOTE: This operation is a simple adaptor over the overloaded get_property
+// operations.
+template<typename Graph>
+inline typename graph_property<Graph, graph_bundle_t>::type&
+get_property(Graph& g) {
+  return get_property(g, graph_bundle);
+}
+
+template<typename Graph>
+inline typename graph_property<Graph, graph_bundle_t>::type const&
+get_property(Graph const& g) {
+  return get_property(g, graph_bundle);
+}
+#endif
+
 } // namespace boost
 
 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
 //
 //=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -14,93 +13,158 @@
 
 #include <utility>
 #include <boost/graph/global_vertex_mapping.hpp>
+#include <boost/graph/default.hpp>
 #include <boost/graph/graph_traits.hpp>
 
 namespace boost {
+  namespace detail {
+    template <typename Graph, typename MutableGraph,
+              typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
+              typename CopyEdge, typename MergeEdges, typename SetEdgeLabel>
+    void graph_sum_impl(const Graph& g1, const Graph& 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<Graph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+      auto & gl1 = get_property(g1);
+      auto & gl2 = get_property(g2);
+      auto & gl_out = get_property(g_out);
+
+      typename graph_traits < Graph >::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);
+          InVertex v1 = *vi;
+          //          merge_vertices(v1, g1, gl2.vertices[ g1[*vi].name ], g2, new_v, g_out); // Does not compile! Why?
+          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
+        }
+      }
 
-  template <class VertexListGraph, class MutableGraph> 
-  void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
-  {
-    typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
-    typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
-    
-    detail::vertex_copier<VertexListGraph, MutableGraph>
-      copy_vertex1 = detail::make_vertex_copier(g1, g_out), copy_vertex2 = detail::make_vertex_copier(g2, g_out);
-    detail::edge_copier<VertexListGraph, MutableGraph>
-      copy_edge1 = detail::make_edge_copier(g1, g_out), copy_edge2 = detail::make_edge_copier(g2, g_out);
-
-    auto & gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
-    auto & gl2 = get_property(g2, graph_label).hack->vertices;
-    auto & gl_out  = get_property(g_out, graph_label).hack->vertices;
-    auto & gl_oute = get_property(g_out, graph_label).hack->edges;
+      typename graph_traits < Graph >::edge_iterator ei, ei_end;
+      typename graph_traits < MutableGraph >::edge_descriptor new_e;
+      bool inserted;
 
-    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
-    // copy vertices from g1
-    for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
-      OutVertex new_v = add_vertex(g_out);
-      copy_vertex1(*vi, new_v);
-      assert( g_out[new_v].name == g1[*vi].name); // copy_vertex already did it
-      gl_out[ g1[*vi].name ] = new_v;
-    }
-    // copy vertices from (g2 - g1)
-    for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
-      if ( gl1.find ( g2[*vi].name ) == gl1.end() ) { // if vi is not in g1
-        OutVertex new_v = add_vertex(g_out);
-        copy_vertex2(*vi, new_v);
-        assert( g_out[new_v].name == g2[*vi].name ); // copy_vertex already did it
-        gl_out[ g2[*vi].name ] = new_v;
+      // copy edges from g1
+      for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+        auto src  = g1[source(*ei, g1)].name;
+        auto 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
+        } 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[ g1[*ei].name ], g2, new_e, g_out); // Does not compile! Why?
+          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
+        }
+      }
+      // copy edges from g2 if it is *not* already there
+      for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
+        auto src  = g2[source(*ei, g2)].name;
+        auto 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
+        }
       }
     }
+  } // namespace detail
 
-    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) {
-      auto src  = g1[source(*ei, g1)].name;
-      auto targ = g1[target(*ei, g1)].name;
-
-      assert( gl_out.find(src)  != gl_out.end() );
-      assert( gl_out.find(targ) != gl_out.end() );
 
-      boost::tie(new_e, inserted) = add_edge(gl_out[src], gl_out[targ], g_out);
-      copy_edge1(*ei, new_e);
-      assert( g_out[new_e].name == g1[*ei].name ); // copy_edge already did it
-      get_property(g_out, graph_label).hack->edges[ g1[*ei].name ] = new_e;
-    }
-    // copy edges from g2 if it is *not* already there
-    for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
-      auto src  = g2[source(*ei, g2)].name;
-      auto targ = g2[target(*ei, g2)].name;
-
-      assert( gl_out.find(src)  != gl_out.end() );
-      assert( gl_out.find(targ) != gl_out.end() );
+  template <typename Graph, typename MutableGraph>
+  void graph_sum(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  {
+    detail::graph_sum_impl
+      (g1, g2, g_out,
+       detail::default_vertex_copy<Graph, MutableGraph>(),
+       detail::default_vertices_merge<Graph, MutableGraph>(),
+       detail::default_set_vertex_label<MutableGraph>(),
+       detail::default_edge_copy<Graph, MutableGraph>(),
+       detail::default_edges_merge<Graph, MutableGraph>(),
+       detail::default_set_edge_label<MutableGraph>()
+       );
+  }
 
-      if ( gl_oute.find( g2[*ei].name ) == gl_oute.end() ) { // ei is not yet in g_out
-        boost::tie(new_e, inserted) = add_edge(gl_out[src], gl_out[targ], g_out);
-        copy_edge2(*ei, new_e);
-        assert( g_out[new_e].name == g2[*ei].name ); // copy_edge already did it
-        get_property(g_out, graph_label).hack->edges[ g2[*ei].name ] = new_e;
-      }
-    }
+  template <typename Graph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_sum(const Graph& g1, const Graph& 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()),
+                    detail::default_vertex_copy<Graph, MutableGraph>()),
+       choose_param(get_param(params, vertices_merge_t()),
+                    detail::default_vertices_merge<Graph, MutableGraph>()),
+       choose_param(get_param(params, set_vertex_label_t()),
+                    detail::default_set_vertex_label<MutableGraph>()),
+       choose_param(get_param(params, edge_copy_t()),
+                    detail::default_edge_copy<Graph, MutableGraph>()),
+       choose_param(get_param(params, edges_merge_t()),
+                    detail::default_edges_merge<Graph, MutableGraph>()),
+       choose_param(get_param(params, set_edge_label_t()),
+                    detail::default_set_edge_label<MutableGraph>())
+       );
   }
 
   // Version with globalVertexMapping
-  template <class VertexListGraph, class MutableGraph, class globalVertexMapping> 
-  void gvm_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+  template <typename Graph, typename MutableGraph, typename globalVertexMapping>
+  void gvm_graph_sum(const Graph& g1, const Graph& g2, globalVertexMapping m, MutableGraph& g_out)
   {
-    typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+    typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
     typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
     typedef typename globalVertexMapping::global_id_type id_type;
 
-    detail::vertex_copier<VertexListGraph, MutableGraph>
+    detail::vertex_copier<Graph, MutableGraph>
       copy_vertex1 = detail::make_vertex_copier(g1, g_out), copy_vertex2 = detail::make_vertex_copier(g2, g_out);
-    detail::edge_copier<VertexListGraph, MutableGraph>
+    detail::edge_copier<Graph, MutableGraph>
       copy_edge1 = detail::make_edge_copier(g1, g_out), copy_edge2 = detail::make_edge_copier(g2, g_out);
 
 
-    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+    typename graph_traits < Graph >::vertex_iterator vi, vi_end;
     // copy vertices from g1
     for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
       OutVertex new_v = add_vertex(g_out);
@@ -121,7 +185,7 @@
       }
     }
 
-    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+    typename graph_traits < Graph >::edge_iterator ei, ei_end;
     // copy edges from g1
     for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
       std::pair < OutVertex, bool > out_s, out_t;

Modified: sandbox/SOC/2010/graph/boost/graph/union.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/union.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/union.hpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
 //
 //=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -9,74 +8,57 @@
 //=======================================================================
 //
 
+// Todo:
+// - Make it use orig_to_copy_t and vertex_index Named Parametersparameters
+
 #ifndef BOOST_GRAPH_UNION_HPP
 #define BOOST_GRAPH_UNION_HPP
 
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/copy.hpp>
-#include <boost/graph/sum.hpp>
+#include <boost/graph/default.hpp>
 
 namespace boost {
-
-  // This is also disjoint! But it uses graph_sum and vertice/edge names
-  template <class VertexListGraph, class MutableGraph> 
-  void graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
-  {
-    auto gl2  = get_property(g2, graph_label).hack->vertices;
-    auto gl2e = get_property(g2, graph_label).hack->edges;
-    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
-    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
-
-    for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
-      assert( gl2.find( g1[*vi].name ) == gl2.end() );
-    }
-    for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
-      assert( gl2e.find( g1[*ei].name ) == gl2e.end() );
-    }
-    graph_sum(g1, g2, g_out);
-  }
-
-  template <class VertexListGraph, class MutableGraph>
+  template <typename VertexListGraph, typename MutableGraph>
   void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph &g_out)
   {
     copy_graph(g1, g_out);
     copy_graph(g2, g_out);
   }
 
-  template <class VertexListGraph, class MutableGraph, class P, class T, class R>
-  void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph &g_out,
+  template <typename Graph, typename MutableGraph, typename P, typename T, typename R>
+  void graph_disjoint_union(const Graph& g1, const Graph& g2, MutableGraph &g_out,
                             const bgl_named_params<P, T, R>& params)
   {
-    // still need to do the same with orig_to_copy and vertex_index_map
-    typedef typename detail::vertex_copier<VertexListGraph, MutableGraph> vertex_copier_t;
-    vertex_copier_t vc1 = detail::make_vertex_copier<VertexListGraph, MutableGraph>(g1, g_out);
-    vertex_copier_t vc2 = detail::make_vertex_copier<VertexListGraph, MutableGraph>(g2, g_out);
-    typedef typename detail::edge_copier<VertexListGraph, MutableGraph> edge_copier_t;
-    edge_copier_t ec1 = detail::make_edge_copier<VertexListGraph, MutableGraph>(g1, g_out);
-    edge_copier_t ec2 = detail::make_edge_copier<VertexListGraph, MutableGraph>(g2, g_out);
-
-    auto p = params
-      .vertex_copy (choose_param
-                    (get_param(params, vertex_copy_t()),
-                     std::pair<vertex_copier_t, vertex_copier_t>(vc1, vc2))
-                    )
-      .edge_copy (choose_param
-                  (get_param(params, edge_copy_t()),
-                   std::pair<edge_copier_t, edge_copier_t>(ec1, ec2))
-                  );
-
     copy_graph
       (g1, g_out,
-       p.vertex_copy(get_param(p, vertex_copy_t()).first).edge_copy(get_param(p,edge_copy_t()).first)
+       vertex_copy(detail::to_two_parameters_vertex_copier
+                   (g1, g_out,
+                    choose_param
+                    (get_param(params, vertex_copy_t()),
+                     detail::default_vertex_copy<Graph, MutableGraph>())))
+       .edge_copy(
+                  detail::to_two_parameters_edge_copier
+                  (g1, g_out,
+                   choose_param
+                   (get_param(params, edge_copy_t()),
+                    detail::default_edge_copy<Graph, MutableGraph>())))
        );
 
     copy_graph
       (g2, g_out,
-       p.vertex_copy(get_param(p, vertex_copy_t()).second).edge_copy(get_param(p,edge_copy_t()).second)
+       vertex_copy(detail::to_two_parameters_vertex_copier
+                   (g2, g_out,
+                    choose_param
+                    (get_param (params, vertex_copy_t()),
+                     detail::default_vertex_copy<Graph, MutableGraph>())))
+       .edge_copy(detail::to_two_parameters_edge_copier
+                  (g2, g_out,
+                   choose_param
+                   (get_param (params, edge_copy_t()),
+                    detail::default_edge_copy<Graph, MutableGraph>())))
        );
   }
-
-
 } // namespace boost
 
 #endif // BOOST_GRAPH_UNION_HPP

Modified: sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,3 +1,13 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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)
+//=======================================================================
+//
+
 #include <iostream>                  // for std::cout
 #include <utility>                   // for std::pair
 #include <algorithm>                 // for std::for_each
@@ -9,6 +19,7 @@
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/graph_utility.hpp>
 
+#include <boost/graph/copy.hpp>
 #include <boost/graph/union.hpp>
 
 using namespace boost;
@@ -37,34 +48,25 @@
 typedef graph_traits<Graph2>::vertex_iterator VertexIterator2;
 
 template <typename G1, typename G2>
-struct vertex_copier {
-  vertex_copier(const G1& g1, G2& g2)
-    : vertex_all_map1(get(vertex_all, g1)), 
-      vertex_all_map2(get(vertex_all, g2)) { }
-  
-  template <typename Vertex1, typename Vertex2>
-  void operator()(const Vertex1& v1, Vertex2& v2) const {
-    //    cout << "Copying vertex " << v1 << endl;
-    put(vertex_all_map2, v2, get(vertex_all_map1, v1));
+struct my_copier {
+  typedef typename graph_traits<G1>::vertex_descriptor Vertex1;
+  typedef typename graph_traits<G2>::vertex_descriptor Vertex2;
+  void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) {
+    put(get(vertex_all, g2), v2, get(get(vertex_all, g1), v1));
   }
-  typename property_map<G1, vertex_all_t>::const_type vertex_all_map1;
-  mutable typename property_map<G2, vertex_all_t>::type vertex_all_map2;
 };
 
-
 template <typename G1, typename G2>
-struct mycopier {
-  mycopier(const G1& _g1, G2& _g2, int _add, float _factor)
-    : g1(_g1), g2(_g2), add(_add), factor(_factor) { }
-  
+struct my_copier2 {
+  my_copier2(int _add, float _factor)
+    : add(_add), factor(_factor) { }
+
   template <typename Vertex1, typename Vertex2>
-  void operator()(const Vertex1& v1, Vertex2& v2) const {
+  void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) {
     g2[v2].name = g1[v1].name;
     g2[v2].id = g1[v1].id + add;
     g2[v2].value = g1[v1].value*factor;
   }
-  const G1& g1;
-  G2& g2;
   int add;
   float factor;
 };
@@ -126,13 +128,14 @@
   cout << "g3:" << endl;
   print(g3);
 
-  vertex_copier<Graph1, Graph1> c1(g1, g4), c2(g2, g4);
-  graph_disjoint_union(g1, g2, g4, vertex_copy(make_pair(c1, c2)));
+  graph_disjoint_union(g1, g2, g4, vertex_copy(my_copier<Graph1, Graph1>()));
   cout << "g4:" << endl;
   print(g4);
 
-  mycopier<Graph1, Graph2> cc1(g1, h1, 10, -2.1111), cc2(g2, h1, 100, 2);
-  graph_disjoint_union(g1, g2, h1, vertex_copy(make_pair(cc1, cc2)));
+  graph_disjoint_union(g1, g2, g4, vertex_copy(my_copier<Graph1, Graph1>()));
+
+
+  graph_disjoint_union(g1, g2, h1, vertex_copy(my_copier2<Graph1, Graph2>(100, 10)));
   cout << "h1:" << endl;
   print(h1);
 

Modified: sandbox/SOC/2010/graph/libs/test/property_test.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/property_test.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/property_test.cpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,3 +1,13 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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)
+//=======================================================================
+//
+
 #include <iostream>                  // for std::cout
 #include <utility>                   // for std::pair
 #include <algorithm>                 // for std::for_each
@@ -9,10 +19,11 @@
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/graph_utility.hpp>
 
-#include <boost/graph/complement.hpp>
-#include <boost/graph/intersection.hpp>
 #include <boost/graph/sum.hpp>
+#include <boost/graph/difference.hpp>
+#include <boost/graph/intersection.hpp>
 #include <boost/graph/union.hpp>
+#include <boost/graph/complement.hpp>
 #include <boost/graph/join.hpp>
 
 using namespace boost;
@@ -22,14 +33,13 @@
 struct Edge_Label;
 struct Graph_Label;
 
-struct Graph_Label_Hack {
-  struct Graph_Label * hack;
-};
-
-typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Label, Edge_Label, property<graph_label_t, Graph_Label_Hack> > Graph;
+typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Label, Edge_Label, Graph_Label, listS > Graph;
 
-typedef Graph::vertex_descriptor Vertex;
-typedef Graph::edge_descriptor Edge;
+// Hack: Instead of using Graph definition here to define the
+// descriptors, we define them using the same parameters used to
+// define Graph:
+typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::vertex_descriptor Vertex;
+typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::edge_descriptor Edge;
 
 struct Vertex_Label {
   size_t name;
@@ -42,30 +52,31 @@
   unordered_map<size_t, Edge> edges;
 };
 
-
 // First look at main()
 // These are auxiliary functions
 
-// copier that sets the name mapping
+// Vertex copier that sets the name mapping
 template <typename G1, typename G2>
-struct my_copier {
-  my_copier(const G1& _g1, G2& _g2)
-    : g1(_g1),
-      g2(_g2),
-      vertex_all_map1(get(vertex_all, _g1)), 
-      vertex_all_map2(get(vertex_all, _g2))
-  { }
-  
-  template <typename Vertex1, typename Vertex2>
-  void operator()(const Vertex1& v1, Vertex2& v2) const {
-    auto & gl2 = get_property(g2, graph_label).hack->vertices;
-    put(vertex_all_map2, v2, get(vertex_all_map1, v1));
+struct my_vertex_copier {
+  typedef typename graph_traits<G1>::vertex_descriptor Vertex1;
+  typedef typename graph_traits<G2>::vertex_descriptor Vertex2;
+  void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) const {
+    auto & gl2 = get_property(g2).vertices;
+    put(get(vertex_all, g2), v2, get(get(vertex_all, g1), v1));
     gl2[ g1[v1].name ] = v2;
   }
-  const G1& g1;
-  G2& g2;
-  typename property_map<G1, vertex_all_t>::const_type vertex_all_map1;
-  mutable typename property_map<G2, vertex_all_t>::type vertex_all_map2;
+};
+
+// Edge copier that sets the name mapping
+template <typename G1, typename G2>
+struct my_edge_copier {
+  typedef typename graph_traits<G1>::edge_descriptor Edge1;
+  typedef typename graph_traits<G2>::edge_descriptor Edge2;
+  void operator()(const Edge1& e1, const G1& g1, Edge2& e2, G2& g2) const {
+    auto & gl2 = get_property(g2).edges;
+    put(get(edge_all, g2), e2, get(get(edge_all, g1), e1));
+    gl2[ g1[e1].name ] = e2;
+  }
 };
 
 // edge visitor for new edges
@@ -73,68 +84,44 @@
 struct my_edge_visitor {
   void operator()(const EdgeDescriptor &e, Graph &g)
   {
-    typename graph_traits<Graph>::vertex_descriptor u, v;
-    u = source(e, g);
-    v = target(e, g);
+    typename graph_traits<Graph>::vertex_descriptor
+      u = source(e, g), v = target(e, g);
     g[e].name = g[u].name * 100 + g[v].name;
-    get_property(g, graph_label).hack->edges[ g[e].name ] = e;
+    get_property(g).edges[ g[e].name ] = e;
   }
 };
 
 // name vertices and edges
 template <class Graph>
-void auto_label(Graph &g) {
+void auto_label(Graph &g, size_t start_vertex_label = 10, size_t delta_edge_label = 0) {
   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
   typename graph_traits<Graph>::edge_iterator ei, ei_end;
-  size_t label = 10; // just to make vertex name != vertex index
+  size_t label = start_vertex_label; // just to make vertex name != vertex index
   // vertices
   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
     g[*vi].name = label;
-    get_property(g, graph_label).hack->vertices[label] = *vi;
+    get_property(g).vertices[label] = *vi;
     label++;
   }
   // edges (does not work for parallel edges - they will have the same name)
   for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
-    size_t src, targ;
-    src  = g[source(*ei, g)].name - 10;
-    targ = g[target(*ei, g)].name - 10;
-    label = 100 + 10 * src + targ;
+    size_t src = g[source(*ei, g)].name, targ = g[target(*ei, g)].name;
+    label = delta_edge_label + 100 * src + targ;
     g[*ei].name = label;
-    get_property(g, graph_label).hack->edges[label] = *ei;
-  }
-}
-
-
-// rename vertices and edges (only because of union! To make the sets disjoint)
-template <class Graph>
-void relabel(Graph &g, size_t delta_v, size_t delta_e) {
-  typename graph_traits<Graph>::vertex_iterator vi, vi_end;
-  typename graph_traits<Graph>::edge_iterator ei, ei_end;
-  // vertices
-  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
-    get_property(g, graph_label).hack->vertices.erase( g[*vi].name );
-    g[*vi].name += delta_v;
-    get_property(g, graph_label).hack->vertices[ g[*vi].name ] = *vi;
-  }
-  // edges (does not work for parallel edges - they will have the same name)
-  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
-    get_property(g, graph_label).hack->edges.erase( g[*ei].name );
-    g[*ei].name += delta_e;
-    get_property(g, graph_label).hack->edges[ g[*ei].name ] = *ei;
+    get_property(g).edges[label] = *ei;
   }
 }
 
-
 // check to see if the naming is ok
 template <class Graph>
 void check(Graph &g, bool check_edges = true) {
   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
   typename graph_traits<Graph>::edge_iterator ei, ei_end;
   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
-    assert( get_property(g, graph_label).hack->vertices[ g[*vi].name ] == *vi);
+    assert( get_property(g).vertices[ g[*vi].name ] == *vi);
   if ( check_edges )
     for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
-      assert( get_property(g, graph_label).hack->edges[ g[*ei].name ] == *ei);
+      assert( get_property(g).edges[ g[*ei].name ] == *ei);
 }
 
 // print a graph showing vertex and edge names
@@ -152,22 +139,12 @@
   }
 }
 
-
 int main(int,char*[])
 {
   boost::mt19937 gen;
   gen.seed(uint32_t(time(0)));
 
-  Graph g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_union, g_join;
-
-  get_property(g1,       graph_label).hack = new(Graph_Label);
-  get_property(g2,       graph_label).hack = new(Graph_Label);
-  get_property(g_compl,  graph_label).hack = new(Graph_Label);
-  get_property(g_rcompl, graph_label).hack = new(Graph_Label);
-  get_property(g_int,    graph_label).hack = new(Graph_Label);
-  get_property(g_sum,    graph_label).hack = new(Graph_Label);
-  get_property(g_union,  graph_label).hack = new(Graph_Label);
-  get_property(g_join,   graph_label).hack = new(Graph_Label);
+  Graph g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_diff, g_union, g_join, g_join2;
 
   generate_random_graph(g1, 3,  5, gen, false);
   generate_random_graph(g2, 4, 10, gen, false);
@@ -192,17 +169,16 @@
   cout << endl;
 
   cout << "Complement of g1:" << endl;
-  my_copier<Graph, Graph> c(g1, g_compl);
+  my_vertex_copier<Graph, Graph> c;
   graph_complement(g1, g_compl, vertex_copy(c), false);
-  check(g_compl, false); // graph_complement don't set edge names in graph_label, but my_copier do it for vertices
+  check(g_compl, false); // graph_complement don't set edge names in graph_label, but my_vertex_copier do it for vertices
   print(g_compl);
   cout << endl;
 
   cout << "Reflexive complement of g1:" << endl;
-  my_copier<Graph, Graph> cc(g1, g_rcompl);
-  graph_complement(g1, g_rcompl, vertex_copy(cc).edge_visitor(my_edge_visitor<Edge, Graph>()), true);
-  print(g_rcompl);
+  graph_complement(g1, g_rcompl, vertex_copy(c).edge_visitor(my_edge_visitor<Edge, Graph>()), true);
   check(g_rcompl);
+  print(g_rcompl);
   cout << endl;
 
   cout << "Intersection of g1 and g2:" << endl;
@@ -217,29 +193,34 @@
   print(g_sum);
   cout << endl;
 
-  // Gives an error because g1 and g2 are not disjoint:
-  // graph_union(g1, g2, g_union);
-  // graph_join(g1, g2, g_join);
-
-  // for union and join, the vertex and edge set needs to be disjoint.
-  relabel(g2, 80, 800); // to make them disjoint
-
-  cout << "Graph 2 with new names (g2'):" << endl;
-  check(g2);
-  print(g2);
+  cout << "Difference of g1 and g2:" << endl;
+  graph_difference(g1, g2, g_diff);
+  check(g_diff);
+  print(g_diff);
   cout << endl;
 
-  cout << "Disjoint union of g1 and g2':" << endl;
-  graph_union(g1, g2, g_union);
-  check(g_union);
+  // For union and join, the vertex and edge set are considered to be disjoint.
+  // They ignore the vertex and edge names
+
+  cout << "Disjoint union of g1 and g2:" << endl;
+  graph_disjoint_union(g1, g2, g_union);
   print(g_union);
   cout << endl;
 
-  cout << "Join of g1 and g2':" << endl;
+  cout << "Join of g1 and g2:" << endl;
   graph_join(g1, g2, g_join);
-  check(g_join, false); // graph_join is not (yet ?) setting edge names for new edges
   print(g_join);
-  // cout << endl;
+  cout << endl;
+
+  cout << "Another join of g1 and g2: (g2 with new labels)" << endl;
+  auto_label(g2, 20, 200);
+  graph_join(g1, g2, g_join2,
+             vertex_copy(my_vertex_copier<Graph, Graph>())
+             .edge_copy(my_edge_copier<Graph, Graph>())
+             .edge_visitor(my_edge_visitor<Edge, Graph>()));
+  check(g_join2); // passes the test because we are using our own functions
+  print(g_join2);
+  //  cout << endl;
 
   return EXIT_SUCCESS;
 }

Modified: sandbox/SOC/2010/graph/libs/test/test.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/test.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/test.cpp	2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,3 +1,13 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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)
+//=======================================================================
+//
+
 #include <iostream>                  // for std::cout
 #include <utility>                   // for std::pair
 #include <algorithm>                 // for std::for_each