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

Subject: [Boost-commit] svn:boost r65048 - in sandbox/SOC/2010/graph: . boost/graph libs/doc libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-27 00:11:31

Author: dbarbosa
Date: 2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
New Revision: 65048
URL: http://svn.boost.org/trac/boost/changeset/65048

Log:
First version of documentation
Added edge and vertex symmetric difference
All algorithms with an overloaded version that returns a new graph
Sum and union are alias, and disjoint union is very explicit now
Etc

Added:
   sandbox/SOC/2010/graph/boost/graph/disjoint_union.hpp
      - copied, changed from r64839, /sandbox/SOC/2010/graph/boost/graph/union.hpp
   sandbox/SOC/2010/graph/libs/doc/graph_complement.html   (contents, props changed)
   sandbox/SOC/2010/graph/libs/doc/graph_difference.html   (contents, props changed)
   sandbox/SOC/2010/graph/libs/doc/graph_disjoint_union.html   (contents, props changed)
   sandbox/SOC/2010/graph/libs/doc/graph_intersection.html   (contents, props changed)
   sandbox/SOC/2010/graph/libs/doc/graph_join.html   (contents, props changed)
   sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html   (contents, props changed)
   sandbox/SOC/2010/graph/libs/doc/graph_union.html   (contents, props changed)
Removed:
   sandbox/SOC/2010/graph/boost/graph/union.hpp
Text files modified: 
   sandbox/SOC/2010/graph/algorithms.org                        |     3                                         
   sandbox/SOC/2010/graph/boost/graph/complement.hpp            |   138 +++++++++++++-----                      
   sandbox/SOC/2010/graph/boost/graph/default.hpp               |    43 +----                                   
   sandbox/SOC/2010/graph/boost/graph/difference.hpp            |   293 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2010/graph/boost/graph/disjoint_union.hpp        |   125 ++++++++++++----                        
   sandbox/SOC/2010/graph/boost/graph/intersection.hpp          |    47 ++++--                                  
   sandbox/SOC/2010/graph/boost/graph/join.hpp                  |    82 ++++++----                              
   sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp |     6                                         
   sandbox/SOC/2010/graph/boost/graph/sum.hpp                   |    83 ++++++++--                              
   sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp          |     2                                         
   sandbox/SOC/2010/graph/libs/test/property_test.cpp           |    16 +                                       
   11 files changed, 646 insertions(+), 192 deletions(-)

Modified: sandbox/SOC/2010/graph/algorithms.org
==============================================================================
--- sandbox/SOC/2010/graph/algorithms.org	(original)
+++ sandbox/SOC/2010/graph/algorithms.org	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -117,6 +117,7 @@
     Copy all vertices from g1 & g2
     Copy all edges from g1 & g2
 *** Questions
+    - Only intersection of edges or intersection of vertices and edges?
     - How to copy properties?
 *** Links
     - http://graph-theory-algorithms-book.googlecode.com/files/graph-theory-0.3.pdf [page 18]
@@ -149,7 +150,6 @@
     - Does it make sense to have an in-place version?
 *** Links
     - http://graph-theory-algorithms-book.googlecode.com/files/graph-theory-0.3.pdf [page 18-19]
-    - http://books.google.com/books?id=0ghuqEYf25YC&lpg=PA76&ots=cr4vXOlk5g&dq=symmetric%20difference%20graph&pg=PA76#v=onepage&q=symmetric%20difference%20graph&f=false
 ** Edge symmetric difference
 *** Methods
   - void graph_edge_symmetric_difference(g1, g2, g_out)
@@ -179,6 +179,7 @@
 *** Links
     - http://graph-theory-algorithms-book.googlecode.com/files/graph-theory-0.3.pdf [page 18-19]
     - http://networkx.lanl.gov/reference/generated/networkx.symmetric_difference.html
+    - http://books.google.com/books?id=0ghuqEYf25YC&lpg=PA76&ots=cr4vXOlk5g&dq=symmetric%20difference%20graph&pg=PA76#v=onepage&q=symmetric%20difference%20graph&f=false
 ** Disjoint union
 *** Methods
   - void graph_disjoint_union(g1, g2, g_out)

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -18,24 +18,24 @@
 namespace boost {
   namespace detail {
 
-    template <typename Graph, typename MutableGraph,
+    template <typename VertexListGraph, typename MutableGraph,
               typename CopyVertex,
               typename NewEdgeVisitor,
-              typename Orig2OutVertexIndexMap>
-    void graph_complement_impl(const Graph& g_in, MutableGraph& g_out,
+              typename In2OutVertexIndexMap>
+    void graph_complement_impl(const VertexListGraph& g_in, MutableGraph& g_out,
                                CopyVertex copy_vertex, NewEdgeVisitor edge_visitor,
-                               Orig2OutVertexIndexMap orig2out,
+                               In2OutVertexIndexMap in2out,
                                bool reflexive)
     {
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
-      typename graph_traits < Graph >::vertex_iterator ui, ui_end;
+      typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+      typename graph_traits < VertexListGraph >::vertex_iterator ui, ui_end;
 
       // copy vertices from g_in
       for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
         OutVertex new_v = add_vertex(g_out);
-        put(orig2out, *vi, new_v);
+        put(in2out, *vi, new_v);
         copy_vertex(*vi, g_in, new_v, g_out);
       }
 
@@ -45,8 +45,8 @@
           if ( (reflexive || ui != vi) && edge(*ui, *vi, g_in).second == false ) {
             typename graph_traits<MutableGraph>::edge_descriptor new_e;
             bool inserted;
-            boost::tie(new_e, inserted) = add_edge(get(orig2out, *ui),
-                                                   get(orig2out, *vi),
+            boost::tie(new_e, inserted) = add_edge(get(in2out, *ui),
+                                                   get(in2out, *vi),
                                                    g_out);
             assert(inserted);
             edge_visitor(new_e, g_out);
@@ -56,63 +56,121 @@
     }
   } // namespace detail
 
-  template <typename Graph, typename MutableGraph>
-  void graph_complement(const Graph& g_in, MutableGraph& g_out, bool reflexive)
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out)
   {
     typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
-    std::vector<vertex_t> orig2out(num_vertices(g_in));
+    std::vector<vertex_t> in2out(num_vertices(g_in));
 
     detail::graph_complement_impl
       (g_in, g_out,
-       detail::default_vertex_copy<Graph, MutableGraph>(),
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
        detail::default_edge_visitor<MutableGraph>(),
-       make_iterator_property_map(orig2out.begin(),
-                                  get(vertex_index, g_in), orig2out[0]),
-       reflexive
+       make_iterator_property_map(in2out.begin(),
+                                  get(vertex_index, g_in), in2out[0]),
+       false
        );
   }
 
-  template <typename Graph, typename MutableGraph,
+  template <typename VertexListGraph, typename MutableGraph,
             typename P, typename T, typename R>
-  void graph_complement(const Graph& g_in, MutableGraph& g_out,
-                        const bgl_named_params<P, T, R>& params, bool reflexive)
+  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out,
+                        const bgl_named_params<P, T, R>& params)
   {
     typename std::vector<T>::size_type n;
-    n = is_default_param(get_param(params, orig_to_copy_t()))
+    n = is_default_param(get_param(params, in_to_out_t()))
       ? num_vertices(g_in) : 1;
     std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
-      orig2out(n);
+      in2out(n);
 
     detail::graph_complement_impl
       (g_in, g_out,
        choose_param(get_param(params, vertex_copy_t()),
-                    detail::default_vertex_copy<Graph, MutableGraph>()),
+                    detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, edge_visitor_t()),
                     detail::default_edge_visitor<MutableGraph>()),
-       choose_param(get_param(params, orig_to_copy_t()),
+       choose_param(get_param(params, in_to_out_t()),
                     make_iterator_property_map
-                    (orig2out.begin(),
+                    (in2out.begin(),
                      choose_const_pmap(get_param(params, vertex_index),
-                                       g_in, vertex_index), orig2out[0])),
-       reflexive
+                                       g_in, vertex_index), in2out[0])),
+       false
        );
   }
 
-//  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));
-//
-//    detail::graph_complement_impl
-//      (g_in, g_out,
-//       detail::make_vertex_copier(g_in, g_out),
-//       make_iterator_property_map(orig2out.begin(),
-//                                  get(vertex_index, g_in), orig2out[0]),
-//       true
-//       );
-//  }
+  template <typename VertexListGraph>
+  VertexListGraph graph_complement(const VertexListGraph& g_in)
+  {
+    VertexListGraph g_out;
+    graph_complement(g_in, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_complement(const VertexListGraph& g_in, const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_complement(g_in, g_out, params);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+  {
+    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
+    std::vector<vertex_t> in2out(num_vertices(g_in));
+
+    detail::graph_complement_impl
+      (g_in, g_out,
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+       detail::default_edge_visitor<MutableGraph>(),
+       make_iterator_property_map(in2out.begin(),
+                                  get(vertex_index, g_in), in2out[0]),
+       true
+       );
+  }
 
+  template <typename VertexListGraph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out,
+                                  const bgl_named_params<P, T, R>& params)
+  {
+    typename std::vector<T>::size_type n;
+    n = is_default_param(get_param(params, in_to_out_t()))
+      ? num_vertices(g_in) : 1;
+    std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
+      in2out(n);
+
+    detail::graph_complement_impl
+      (g_in, g_out,
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
+       choose_param(get_param(params, edge_visitor_t()),
+                    detail::default_edge_visitor<MutableGraph>()),
+       choose_param(get_param(params, in_to_out_t()),
+                    make_iterator_property_map
+                    (in2out.begin(),
+                     choose_const_pmap(get_param(params, vertex_index),
+                                       g_in, vertex_index), in2out[0])),
+       true
+       );
+  }
+
+  template <typename VertexListGraph>
+  VertexListGraph graph_reflexive_complement(const VertexListGraph& g_in)
+  {
+    VertexListGraph g_out;
+    graph_reflexive_complement(g_in, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_reflexive_complement(const VertexListGraph& g_in, const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_reflexive_complement(g_in, g_out, params);
+    return g_out;
+  }
 } // namespace boost
 
 #endif // BOOST_GRAPH_COMPLEMENT_HPP

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-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -92,13 +92,13 @@
       }
     };
 
-    // Encapsulation of copier interface taking four arguments
-    // (including both graphs - as defined above) to an interface used
-    // by copy.hpp (taking only two arguments).
+    // Wraps the copier interface taking four arguments (including
+    // both graphs - as defined above) to the 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)
+    struct wrap_vertex_copier {
+      wrap_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>
@@ -112,15 +112,15 @@
     };
 
     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)
+    inline typename detail::wrap_vertex_copier<GraphIn, GraphOut, Copier>
+    make_vertex_copier_wrapper(const GraphIn& g1, GraphOut& g2, Copier c)
     {
-      return detail::encapsulate_vertex_copier<GraphIn, GraphOut, Copier> (g1, g2, c);
+      return detail::wrap_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)
+    struct wrap_edge_copier {
+      wrap_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>
@@ -134,28 +134,11 @@
     };
 
     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)
+    inline typename detail::wrap_edge_copier<GraphIn, GraphOut, Copier>
+    make_edge_copier_wrapper(const GraphIn& g1, GraphOut& g2, Copier c)
     {
-      return detail::encapsulate_edge_copier<GraphIn, GraphOut, Copier> (g1, g2, c);
+      return detail::wrap_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
 

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -17,23 +17,23 @@
 
 namespace boost {
   namespace detail {
-    template <typename Graph, typename MutableGraph,
+    template <typename VertexListGraph, typename MutableGraph,
               typename CopyVertex, typename SetVertexLabel,
               typename CopyEdge, typename SetEdgeLabel>
-    void graph_difference_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+    void graph_difference_impl(const VertexListGraph& g1, const VertexListGraph& 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<VertexListGraph>::vertex_descriptor InVertex;
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-      //typename graph_bundle_type<Graph>::type const& gl1 = get_property(g1);
-      typename graph_bundle_type<Graph>::type const& gl2 = get_property(g2);
+      //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);
 
-      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+      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);
@@ -44,7 +44,7 @@
       }
 
       // copy edges from g1 that are not in g2
-      typename graph_traits < Graph >::edge_iterator ei, ei_end;
+      typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
       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;
@@ -63,37 +63,300 @@
         }
       }
     }
+
+    template <typename VertexListGraph, typename MutableGraph,
+              typename CopyVertex, typename SetVertexLabel,
+              typename CopyEdge, typename SetEdgeLabel>
+    void graph_vertex_symmetric_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+                                         CopyVertex copy_vertex,
+                                         SetVertexLabel set_vertex_label,
+                                         CopyEdge copy_edge,
+                                         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);
+
+      typename graph_traits < VertexListGraph >::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 *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
+        }
+      }
+      for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+        if ( gl1.vertices.find( g2[*vi].name ) == gl1.vertices.end() ) { // if vi is 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
+        }
+      }
+
+      typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+      typename graph_traits < MutableGraph >::edge_descriptor new_e;
+      bool inserted;
+      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;
+
+        if (gl_out.vertices.find( src  ) != gl_out.vertices.end() &&
+            gl_out.vertices.find( targ ) != gl_out.vertices.end()) {
+          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
+        }
+      }
+      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;
+
+        if (gl_out.vertices.find( src  ) != gl_out.vertices.end() &&
+            gl_out.vertices.find( targ ) != gl_out.vertices.end()) {
+          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 VertexListGraph, typename MutableGraph,
+              typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
+              typename CopyEdge, typename SetEdgeLabel>
+    void graph_edge_symmetric_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+                                              CopyVertex copy_vertex,
+                                              MergeVertices merge_vertices,
+                                              SetVertexLabel set_vertex_label,
+                                              CopyEdge copy_edge,
+                                              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);
+
+      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
+        }
+      }
+
+      typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+      typename graph_traits < MutableGraph >::edge_descriptor new_e;
+      bool inserted;
+
+      // copy edges from g1 - g2
+      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
+        }
+      }
+      // copy edges from g2 - g1
+      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 ( gl1.edges.find( g2[*ei].name ) == gl1.edges.end() ) { // if ei is not in g1
+          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
 
-  template <typename Graph, typename MutableGraph>
-  void graph_difference(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
   {
     detail::graph_difference_impl
       (g1, g2, g_out,
-       detail::default_vertex_copy<Graph, MutableGraph>(),
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
        detail::default_set_vertex_label<MutableGraph>(),
-       detail::default_edge_copy<Graph, MutableGraph>(),
+       detail::default_edge_copy<VertexListGraph, MutableGraph>(),
        detail::default_set_edge_label<MutableGraph>()
        );
   }
 
-  template <typename Graph, typename MutableGraph,
+  template <typename VertexListGraph, typename MutableGraph,
             typename P, typename T, typename R>
-  void graph_difference(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+  void graph_difference(const VertexListGraph& g1, const VertexListGraph& 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>()),
+                    detail::default_vertex_copy<VertexListGraph, 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<VertexListGraph, MutableGraph>()),
+       choose_param(get_param(params, set_edge_label_t()),
+                    detail::default_set_edge_label<MutableGraph>())
+       );
+  }
+
+  template <typename VertexListGraph>
+  VertexListGraph graph_difference(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_difference(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+                                   const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_difference(g1, g2, g_out, params);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  {
+    detail::graph_vertex_symmetric_difference_impl
+      (g1, g2, g_out,
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+       detail::default_set_vertex_label<MutableGraph>(),
+       detail::default_edge_copy<VertexListGraph, MutableGraph>(),
+       detail::default_set_edge_label<MutableGraph>()
+       );
+  }
+
+  template <typename VertexListGraph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+                                  const bgl_named_params<P, T, R>& params)
+  {
+    detail::graph_vertex_symmetric_difference_impl
+      (g1, g2, g_out,
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<VertexListGraph, 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>()),
+                    detail::default_edge_copy<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, set_edge_label_t()),
                     detail::default_set_edge_label<MutableGraph>())
        );
   }
+
+  template <typename VertexListGraph>
+  VertexListGraph graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_vertex_symmetric_difference(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+                                             const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_vertex_symmetric_difference(g1, g2, g_out, params);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  {
+    detail::graph_edge_symmetric_difference_impl
+      (g1, g2, g_out,
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+       detail::default_set_vertex_label<MutableGraph>(),
+       detail::default_edge_copy<VertexListGraph, MutableGraph>(),
+       detail::default_set_edge_label<MutableGraph>()
+       );
+  }
+
+  template <typename VertexListGraph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+                                  const bgl_named_params<P, T, R>& params)
+  {
+    detail::graph_edge_symmetric_difference_impl
+      (g1, g2, g_out,
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<VertexListGraph, 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<VertexListGraph, MutableGraph>()),
+       choose_param(get_param(params, set_edge_label_t()),
+                    detail::default_set_edge_label<MutableGraph>())
+       );
+  }
+
+  template <typename VertexListGraph>
+  VertexListGraph graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_edge_symmetric_difference(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+                                             const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_edge_symmetric_difference(g1, g2, g_out, params);
+    return g_out;
+  }
 } // namespace boost
 
 #endif // BOOST_GRAPH_DIFFERENCE_HPP

Copied: sandbox/SOC/2010/graph/boost/graph/disjoint_union.hpp (from r64839, /sandbox/SOC/2010/graph/boost/graph/union.hpp)
==============================================================================
--- /sandbox/SOC/2010/graph/boost/graph/union.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/disjoint_union.hpp	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -9,56 +9,111 @@
 //
 
 // Todo:
-// - Make it use orig_to_copy_t and vertex_index Named Parametersparameters
+// - Make it use in_to_out_t and vertex_index Named Parameters
 
-#ifndef BOOST_GRAPH_UNION_HPP
-#define BOOST_GRAPH_UNION_HPP
+#ifndef BOOST_GRAPH_DISJOINT_UNION_HPP
+#define BOOST_GRAPH_DISJOINT_UNION_HPP
 
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/copy.hpp>
 #include <boost/graph/default.hpp>
 
 namespace boost {
+  namespace detail {
+    template <typename VertexListGraph, typename MutableGraph,
+              typename CopyVertex, typename CopyEdge,
+              typename In2OutVertexIndexMap,
+              typename VertexIndexMap>
+    void graph_disjoint_union_impl(const VertexListGraph& g1, const VertexListGraph& g2,
+                                   MutableGraph& g_out,
+                                   CopyVertex copy_vertex,
+                                   CopyEdge copy_edge,
+                                   In2OutVertexIndexMap g1_to_out, In2OutVertexIndexMap g2_to_out,
+                                   VertexIndexMap vertex_index1, VertexIndexMap vertex_index2)
+    {
+      copy_graph
+        (g1, g_out,
+         orig_to_copy(g1_to_out)
+         .vertex_index_map(vertex_index1)
+         .vertex_copy(detail::make_vertex_copier_wrapper(g1, g_out, copy_vertex))
+         .edge_copy(detail::make_edge_copier_wrapper(g1, g_out, copy_edge))
+         );
+
+      copy_graph
+        (g2, g_out,
+         orig_to_copy(g2_to_out)
+         .vertex_index_map(vertex_index2)
+         .vertex_copy(detail::make_vertex_copier_wrapper(g2, g_out, copy_vertex))
+         .edge_copy(detail::make_edge_copier_wrapper(g2, g_out, copy_edge))
+         );
+    }
+  } // namespace detail
+
   template <typename VertexListGraph, typename MutableGraph>
-  void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph &g_out)
+  void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
   {
-    copy_graph(g1, g_out);
-    copy_graph(g2, g_out);
+    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_disjoint_union_impl
+      (g1, g2, g_out,
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+       detail::default_edge_copy<VertexListGraph, 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]),
+       get(vertex_index, g1),
+       get(vertex_index, g2)
+       );
   }
 
-  template <typename Graph, typename MutableGraph, typename P, typename T, typename R>
-  void graph_disjoint_union(const Graph& g1, const Graph& g2, MutableGraph &g_out,
+  template <typename VertexListGraph, typename MutableGraph,
+            typename P, typename T, typename R>
+  void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2,
+                            MutableGraph& g_out,
                             const bgl_named_params<P, T, R>& params)
   {
-    copy_graph
-      (g1, g_out,
-       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>())))
+    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
+    typename std::vector<T>::size_type n1, n2;
+    n1 = is_default_param(get_param(params, in1_to_out_t())) ? num_vertices(g1) : 1;
+    n2 = is_default_param(get_param(params, in2_to_out_t())) ? num_vertices(g2) : 1;
+    std::vector<vertex_t> g1_to_out(n1);
+    std::vector<vertex_t> g2_to_out(n2);
+
+    detail::graph_disjoint_union_impl
+      (g1, g2, g_out,
+       choose_param(get_param(params, vertex_copy_t()),
+                    detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
+       choose_param(get_param(params, edge_copy_t()),
+                    detail::default_edge_copy<VertexListGraph, MutableGraph>()),
+       choose_param(get_param(params, in1_to_out_t()),
+                    make_iterator_property_map(g1_to_out.begin(),
+                                               get(vertex_index, g1), g1_to_out[0])),
+       choose_param(get_param(params, in2_to_out_t()),
+                    make_iterator_property_map(g2_to_out.begin(),
+                                               get(vertex_index, g2), g2_to_out[0])),
+       choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index),
+       choose_const_pmap(get_param(params, vertex_index1), g2, vertex_index)
        );
+  }
 
-    copy_graph
-      (g2, g_out,
-       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>())))
-       );
+  template <typename VertexListGraph>
+  VertexListGraph graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_disjoint_union(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2,
+                                       const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_disjoint_union(g1, g2, g_out, params);
+    return g_out;
   }
 } // namespace boost
 
-#endif // BOOST_GRAPH_UNION_HPP
+#endif // BOOST_GRAPH_DISJOINT_UNION_HPP

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -17,24 +17,24 @@
 
 namespace boost {
   namespace detail {
-    template <typename Graph, typename MutableGraph,
+    template <typename VertexListGraph, typename MutableGraph,
               typename MergeVertices, typename SetVertexLabel,
               typename MergeEdges, typename SetEdgeLabel>
-    void graph_intersection_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+    void graph_intersection_impl(const VertexListGraph& g1, const VertexListGraph& 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<VertexListGraph>::vertex_descriptor InVertex;
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-      //typename graph_bundle_type<Graph>::type const& gl1 = get_property(g1);
-      typename graph_bundle_type<Graph>::type const& gl2 = get_property(g2);
+      //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);
 
       // copy vertices from (g1 intersection g2)
-      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+      typename graph_traits < VertexListGraph >::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);
@@ -45,7 +45,7 @@
         }
       }
 
-      typename graph_traits < Graph >::edge_iterator ei, ei_end;
+      typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
       typename graph_traits < MutableGraph >::edge_descriptor new_e;
       bool inserted;
       // copy edges from (g1 intersection g2)
@@ -67,35 +67,52 @@
     }
   } // namespace detail
 
-  template <typename Graph, typename MutableGraph>
-  void graph_intersection(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
   {
     detail::graph_intersection_impl
       (g1, g2, g_out,
-       detail::default_vertices_merge<Graph, MutableGraph>(),
+       detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
        detail::default_set_vertex_label<MutableGraph>(),
-       detail::default_edges_merge<Graph, MutableGraph>(),
+       detail::default_edges_merge<VertexListGraph, MutableGraph>(),
        detail::default_set_edge_label<MutableGraph>()
        );
   }
 
-  template <typename Graph, typename MutableGraph,
+  template <typename VertexListGraph, typename MutableGraph,
             typename P, typename T, typename R>
-  void graph_intersection(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+  void graph_intersection(const VertexListGraph& g1, const VertexListGraph& 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>()),
+                    detail::default_vertices_merge<VertexListGraph, 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>()),
+                    detail::default_edges_merge<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, set_edge_label_t()),
                     detail::default_set_edge_label<MutableGraph>())
        );
   }
+
+  template <typename VertexListGraph>
+  VertexListGraph graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_intersection(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2,
+                                     const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_intersection(g1, g2, g_out, params);
+    return g_out;
+  }
 } // namespace boost
 
 #endif // BOOST_GRAPH_INTERSECTION_HPP

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -9,26 +9,27 @@
 //
 
 // Todo:
-// - Make it use orig_to_copy_t and vertex_index Named Parameters
+// - Make it use in_to_out_t and vertex_index Named Parameters
 
 #ifndef BOOST_GRAPH_JOIN_HPP
 #define BOOST_GRAPH_JOIN_HPP
 
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/copy.hpp>
-#include <boost/graph/union.hpp>
 
 namespace boost {
   namespace detail {
-    template <typename Graph, typename MutableGraph,
+    template <typename VertexListGraph, typename MutableGraph,
               typename CopyVertex, typename CopyEdge,
               typename NewEdgeVisitor,
-              typename In2OutVertexIndexMap>
-    void graph_join_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+              typename In2OutVertexIndexMap,
+              typename VertexIndexMap>
+    void graph_join_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
                          CopyVertex copy_vertex,
                          CopyEdge copy_edge,
                          NewEdgeVisitor edge_visitor,
-                         In2OutVertexIndexMap g1_to_out, In2OutVertexIndexMap g2_to_out)
+                         In2OutVertexIndexMap g1_to_out, In2OutVertexIndexMap g2_to_out,
+                         VertexIndexMap vertex_index1, VertexIndexMap vertex_index2)
     {
       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
@@ -36,18 +37,20 @@
       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))
+         .vertex_index_map(vertex_index1)
+         .vertex_copy(detail::make_vertex_copier_wrapper(g1, g_out, copy_vertex))
+         .edge_copy(detail::make_edge_copier_wrapper(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))
+         .vertex_index_map(vertex_index2)
+         .vertex_copy(detail::make_vertex_copier_wrapper(g2, g_out, copy_vertex))
+         .edge_copy(detail::make_edge_copier_wrapper(g2, g_out, copy_edge))
          );
 
-      typename graph_traits < Graph >::vertex_iterator vi, vi_end, ui, ui_end;
+      typename graph_traits < VertexListGraph >::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;
@@ -71,55 +74,72 @@
   } // namespace detail
 
 
-  template <class Graph, class MutableGraph>
-  void graph_join(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  template <class VertexListGraph, class MutableGraph>
+  void graph_join(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
   {
     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_vertex_copy<VertexListGraph, MutableGraph>(),
+       detail::default_edge_copy<VertexListGraph, 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])
+                                  get(vertex_index, g2), g2_to_out[0]),
+       get(vertex_index, g1),
+       get(vertex_index, g2)
        );
   }
 
-  template <typename Graph, typename MutableGraph, typename P, typename T, typename R>
-  void graph_join(const Graph& g1, const Graph& g2, MutableGraph &g_out,
+  template <typename VertexListGraph, typename MutableGraph, typename P, typename T, typename R>
+  void graph_join(const VertexListGraph& g1, const VertexListGraph& 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;
-    }
+    n1 = is_default_param(get_param(params, in1_to_out_t())) ? num_vertices(g1) : 1;
+    n2 = is_default_param(get_param(params, in2_to_out_t())) ? num_vertices(g2) : 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>(),
+                    detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, edge_copy_t()),
-                    detail::default_edge_copy<Graph, MutableGraph>()),
+                    detail::default_edge_copy<VertexListGraph, 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])
+       choose_param(get_param(params, in1_to_out_t()),
+                    make_iterator_property_map(g1_to_out.begin(),
+                                               get(vertex_index, g1), g1_to_out[0])),
+       choose_param(get_param(params, in2_to_out_t()),
+                    make_iterator_property_map(g2_to_out.begin(),
+                                               get(vertex_index, g2), g2_to_out[0])),
+       choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index),
+       choose_const_pmap(get_param(params, vertex_index1), g2, vertex_index)
        );
   }
 
+  template <class VertexListGraph>
+  VertexListGraph graph_join(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_join(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_join(const VertexListGraph& g1, const VertexListGraph& g2,
+                             const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_join(g1, g2, g_out, params);
+    return g_out;
+  }
 } // namespace boost
 
 #endif // BOOST_GRAPH_JOIN_HPP

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -42,6 +42,9 @@
   struct edge_compare_t { };
   struct vertex_max_invariant_t { };
   struct orig_to_copy_t { };
+  struct in_to_out_t { };
+  struct in1_to_out_t { };
+  struct in2_to_out_t { };
   struct root_vertex_t { };
   struct polling_t { };
   struct lookahead_t { };
@@ -91,6 +94,9 @@
     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(in_to_out, in_to_out) \
+    BOOST_BGL_ONE_PARAM_CREF(in1_to_out, in1_to_out) \
+    BOOST_BGL_ONE_PARAM_CREF(in2_to_out, in2_to_out) \
     BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \
     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \
     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -17,10 +17,10 @@
 
 namespace boost {
   namespace detail {
-    template <typename Graph, typename MutableGraph,
+    template <typename VertexListGraph, 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,
+    void graph_sum_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
                         CopyVertex copy_vertex,
                         MergeVertices merge_vertices,
                         SetVertexLabel set_vertex_label,
@@ -28,14 +28,14 @@
                         MergeEdges merge_edges,
                         SetEdgeLabel set_edge_label)
     {
-      typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-      //typename graph_bundle_type<Graph>::type const& gl1 = get_property(g1);
-      typename graph_bundle_type<Graph>::type const& gl2 = get_property(g2);
+      //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);
 
-      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+      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
@@ -63,7 +63,7 @@
         }
       }
 
-      typename graph_traits < Graph >::edge_iterator ei, ei_end;
+      typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
       typename graph_traits < MutableGraph >::edge_descriptor new_e;
       bool inserted;
 
@@ -110,41 +110,86 @@
   } // namespace detail
 
 
-  template <typename Graph, typename MutableGraph>
-  void graph_sum(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+  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<Graph, MutableGraph>(),
-       detail::default_vertices_merge<Graph, MutableGraph>(),
+       detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+       detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
        detail::default_set_vertex_label<MutableGraph>(),
-       detail::default_edge_copy<Graph, MutableGraph>(),
-       detail::default_edges_merge<Graph, MutableGraph>(),
+       detail::default_edge_copy<VertexListGraph, MutableGraph>(),
+       detail::default_edges_merge<VertexListGraph, MutableGraph>(),
        detail::default_set_edge_label<MutableGraph>()
        );
   }
 
-  template <typename Graph, typename MutableGraph,
+  template <typename VertexListGraph, typename MutableGraph,
             typename P, typename T, typename R>
-  void graph_sum(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+  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()),
-                    detail::default_vertex_copy<Graph, MutableGraph>()),
+                    detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, vertices_merge_t()),
-                    detail::default_vertices_merge<Graph, MutableGraph>()),
+                    detail::default_vertices_merge<VertexListGraph, 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>()),
+                    detail::default_edge_copy<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, edges_merge_t()),
-                    detail::default_edges_merge<Graph, MutableGraph>()),
+                    detail::default_edges_merge<VertexListGraph, MutableGraph>()),
        choose_param(get_param(params, set_edge_label_t()),
                     detail::default_set_edge_label<MutableGraph>())
        );
   }
+
+  template <typename VertexListGraph>
+  VertexListGraph graph_sum(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    VertexListGraph g_out;
+    graph_sum(g1, g2, g_out);
+    return g_out;
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  VertexListGraph graph_sum(const VertexListGraph& g1, const VertexListGraph& g2,
+                 const bgl_named_params<P, T, R>& params)
+  {
+    VertexListGraph g_out;
+    graph_sum(g1, g2, g_out, params);
+    return g_out;
+  }
+
+  // graph_union is an alias to graph_sum
+  template <typename VertexListGraph, typename MutableGraph>
+  inline void graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  {
+    graph_sum(g1, g2, g_out);
+  }
+
+  template <typename VertexListGraph, typename MutableGraph,
+            typename P, typename T, typename R>
+  inline void graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+                          const bgl_named_params<P, T, R>& params)
+  {
+    graph_sum(g1, g2, g_out, params);
+  }
+
+  template <typename VertexListGraph>
+  inline VertexListGraph graph_union(const VertexListGraph& g1, const VertexListGraph& g2)
+  {
+    return graph_sum(g1, g2);
+  }
+
+  template <typename VertexListGraph, typename P, typename T, typename R>
+  inline VertexListGraph graph_union(const VertexListGraph& g1, const VertexListGraph& g2,
+                                     const bgl_named_params<P, T, R>& params)
+  {
+    return graph_sum(g1, g2, params);
+  }
 } // namespace boost
 
 #endif // BOOST_GRAPH_SUM_HPP

Deleted: sandbox/SOC/2010/graph/boost/graph/union.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/union.hpp	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
+++ (empty file)
@@ -1,64 +0,0 @@
-//
-//=======================================================================
-// 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)
-//=======================================================================
-//
-
-// 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/default.hpp>
-
-namespace boost {
-  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 <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)
-  {
-    copy_graph
-      (g1, g_out,
-       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,
-       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

Added: sandbox/SOC/2010/graph/libs/doc/graph_complement.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_complement.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,126 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Complement</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_complement</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_complement(const VertexListGraph&amp; g_in, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_complement(const VertexListGraph&amp; g_in,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_reflexive_complement(const VertexListGraph&amp; g1, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_reflexive_complement(const VertexListGraph&amp; g1,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+The result graph is the complement of the input graph <tt>g_in</tt>,
+i.e., the graph with the same vertex set of <tt>g_in</tt> but whose
+edges are not present in <tt>g_in</tt>. The reflexive version creates
+self-loops.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/complement.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g_in</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The complement of <tt>g_in</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertex_copy(VertexCopier vc)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in the original graph
+into the corresponding vertex in the output.<br>
+
+<b>Default:</b> default_vertex_copier which uses the property tag
+<tt>vertex_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>edge_visitor(EdgeVisitor ev)</tt>
+<blockquote>
+
+This is a function that is called for brand new edges in the output,
+making it possible to set the edge property.<br>
+
+<b>Default:</b> default_edge_visitor which does nothing.
+</blockquote>
+
+IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
+<blockquote>
+The vertex index map type must be a model of <a
+href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+Map</a> and must map the vertex descriptors of <tt>g_in</tt> to the
+integers in the half-open range <tt>[0,num_vertices(g_in))</tt>.<br>
+
+<b>Default:</b> <tt>get(vertex_index, g_in)</tt>.
+Note: if you use this default, make sure your graph has
+an internal <tt>vertex_index</tt> property. For example,
+<tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+
+UTIL/OUT: <tt>in_to_out(In2OutMap c)</tt>
+<blockquote>
+This maps vertices in the original graph to vertices in the output.
+
+<b>Default:</b> an <a
+  href="../../property_map/doc/iterator_property_map.html">
+  </tt>iterator_property_map</tt></a> created from a
+  <tt>std::vector</tt> of the output graph's vertex descriptor type of size
+  <tt>num_vertices(g_in)</tt> and using the <tt>i_map</tt> for the index
+  map.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V&sup2;)</i>.
+
+
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<!-- TODO! Fill up this information:-->
+<A HREF="">Davi M. J. Barbosa</A>, State University of Campinas (<A HREF="mailto:.."></A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Added: sandbox/SOC/2010/graph/libs/doc/graph_difference.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_difference.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,120 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Difference</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_difference</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_difference(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_difference(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+The result graph is <tt>g1</tt> without the edges of graph
+<tt>g2</tt>.
+
+The graphs must contain name properties for vertices and edges with
+type <tt>size_t</tt> and two maps in the graph properties,
+<tt>map&lt;size_t, Vertex&gt; vertices</tt> and <tt>map&lt;size_t,
+Edge&gt; edges</tt>, mapping names to descriptors.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/difference.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g1</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+IN: <tt>const VertexListGraph&amp; g2</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The difference graph between <tt>g1</tt> and <tt>g2</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertex_copy(VertexCopier vc)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in the input graphs
+into the corresponding vertex in the output.<br>
+
+<b>Default:</b> default_vertex_copier which uses the property tag
+<tt>vertex_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>set_vertex_label(SetVertexLabel set_vertex_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a vertex.<br>
+
+<b>Default:</b> default_set_vertex_label which sets the name in the
+vertex property and also the map from names to vertex descriptors
+in the graph property.
+</blockquote>
+
+IN: <tt>edge_copy(EdgeCopier ec)</tt>
+<blockquote>
+This is a function that copies the properties of an edge in the input graphs
+into the corresponding edge in the output.<br>
+
+<b>Default:</b> default_edge_copier which uses the property tag
+<tt>edge_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>set_edge_label(SetEdgeLabel set_edge_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a edge.<br>
+
+<b>Default:</b> default_set_edge_label which sets the name in the
+edge property and also the map from names to edge descriptors
+in the graph property.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V+E*R_E)</i>, where <i>R_E</i> is the
+vertex lookup time.
+
+
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<!-- TODO! Fill up this information:-->
+<A HREF="">Davi M. J. Barbosa</A>, State University of Campinas (<A HREF="mailto:.."></A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Added: sandbox/SOC/2010/graph/libs/doc/graph_disjoint_union.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_disjoint_union.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,124 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Disjoint Union</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_disjoint_union</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_disjoint_union(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_disjoint_union(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+The result graph contains all vertices and edges from <tt>g1</tt> and
+<tt>g2</tt>, which are considered to be disjoint.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/disjoint_union.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g1</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+IN: <tt>const VertexListGraph&amp; g2</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The disjoint union of <tt>g1</tt> and <tt>g2</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertex_copy(VertexCopier vc)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in the original graph
+into the corresponding vertex in the copy.<br>
+
+<b>Default:</b> default_vertex_copier which uses the property tag
+<tt>vertex_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>edge_copy(EdgeCopier ec)</tt>
+<blockquote>
+This is a function that copies the properties of an edge in the original graph
+into the corresponding edge in the copy.<br>
+
+<b>Default:</b> default_edge_copier which uses the property tag
+<tt>edge_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>vertex_index_map1(VertexIndexMap vertex_index1)</tt> and
+    <tt>vertex_index_map2(VertexIndexMap vertex_index2)</tt>
+<blockquote>
+The vertex index map type must be a model of <a
+href="../../property_map/doc/ReadablePropertyMap.html">Readable
+Property Map</a> and must map the vertex descriptors of <tt>g1</tt>
+(for <tt>vertex_index1</tt>) and <tt>g2</tt> (for
+<tt>vertex_index2</tt>) to the integers in the half-open range
+<tt>[0,num_vertices(g1))</tt> and <tt>[0,num_vertices(g2))</tt>
+respectively.<br>
+
+<b>Default:</b> <tt>get(vertex_index, g1)</tt> and <tt>get(vertex_index, g2)</tt>.
+Note: if you use this default, make sure your graph has
+an internal <tt>vertex_index</tt> property. For example,
+<tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+
+UTIL/OUT: <tt>in_to_out1(In2OutMap c1)</tt> and
+          <tt>in_to_out2(In2OutMap c2)</tt>
+<blockquote>
+This maps vertices in the input graphs (<tt>g1</tt> and <tt>g2</tt>
+respectively) to vertices in the output.
+
+<b>Default:</b> an <a
+  href="../../property_map/doc/iterator_property_map.html">
+  </tt>iterator_property_map</tt></a> created from a
+  <tt>std::vector</tt> of the output graph's vertex descriptor type of size
+  <tt>num_vertices(g1)</tt> (<tt>num_vertices(g2)</tt>) and using the
+  <tt>vertex_index1</tt> (<tt>vertex_index2</tt>) for the index map.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V+E)</i>.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<A HREF=""></A>, University .. (<A HREF="mailto:..">..</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Added: sandbox/SOC/2010/graph/libs/doc/graph_intersection.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_intersection.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,120 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Intersection</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_intersection</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_intersection(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_intersection(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+The result graph contains only vertices and edges present both in
+<tt>g1</tt> and <tt>g2</tt>.
+
+The graphs must contain name properties for vertices and edges with
+type <tt>size_t</tt> and two maps in the graph properties,
+<tt>map&lt;size_t, Vertex&gt; vertices</tt> and <tt>map&lt;size_t,
+Edge&gt; edges</tt>, mapping names to descriptors.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/intersection.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g1</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+IN: <tt>const VertexListGraph&amp; g2</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The intersection of <tt>g1</tt> and <tt>g2</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertices_merge(MergeVertices merge_vertices)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in both input graphs
+into the corresponding vertex in the output.<br>
+
+<b>Default:</b> default_vertices_merge which uses the property tag
+<tt>vertex_all</tt> to access a property map from <tt>g1</tt>, ignoring <tt>g2</tt>.
+</blockquote>
+
+IN: <tt>set_vertex_label(SetVertexLabel set_vertex_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a vertex.<br>
+
+<b>Default:</b> default_set_vertex_label which sets the name in the
+vertex property and also the map from names to vertex descriptors
+in the graph property.
+</blockquote>
+
+IN: <tt>edges_merge(MergeEdges merge_edges)</tt>
+<blockquote>
+
+This is a function that copies the properties of an edge in both input graphs
+into the corresponding edge in the output.<br>
+
+<b>Default:</b> default_vertices_merge which uses the property tag
+<tt>vertex_all</tt> to access a property map from <tt>g1</tt>, ignoring <tt>g2</tt>.
+</blockquote>
+
+IN: <tt>set_edge_label(SetEdgeLabel set_edge_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a edge.<br>
+
+<b>Default:</b> default_set_edge_label which sets the name in the
+edge property and also the map from names to edge descriptors
+in the graph property.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V*R_V+E*R_E)</i>, where <i>R_V</i> and
+<i>R_E</i> are the vertex and edge lookup time.
+
+
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<A HREF=""></A>, University .. (<A HREF="mailto:..">..</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Added: sandbox/SOC/2010/graph/libs/doc/graph_join.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_join.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,135 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Join</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_join</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_join(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_join(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+The result graph contains all vertices and edges from <tt>g1</tt> and
+<tt>g2</tt>, which are considered to be disjoint, together with all
+possible edges joining vertices from distinct input graphs.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/join.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g1</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+IN: <tt>const VertexListGraph&amp; g2</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The join graph of <tt>g1</tt> and <tt>g2</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertex_copy(VertexCopier vc)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in the original graph
+into the corresponding vertex in the copy.<br>
+
+<b>Default:</b> default_vertex_copier which uses the property tag
+<tt>vertex_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>edge_copy(EdgeCopier ec)</tt>
+<blockquote>
+This is a function that copies the properties of an edge in the original graph
+into the corresponding edge in the copy.<br>
+
+<b>Default:</b> default_edge_copier which uses the property tag
+<tt>edge_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>edge_visitor(EdgeVisitor ev)</tt>
+<blockquote>
+
+This is a function that is called for brand new edges in the output,
+making it possible to set the edge property.<br>
+
+<b>Default:</b> default_edge_visitor which does nothing.
+</blockquote>
+
+IN: <tt>vertex_index_map1(VertexIndexMap vertex_index1)</tt> and
+    <tt>vertex_index_map2(VertexIndexMap vertex_index2)</tt>
+<blockquote>
+The vertex index map type must be a model of <a
+href="../../property_map/doc/ReadablePropertyMap.html">Readable
+Property Map</a> and must map the vertex descriptors of <tt>g1</tt>
+(for <tt>vertex_index1</tt>) and <tt>g2</tt> (for
+<tt>vertex_index2</tt>) to the integers in the half-open range
+<tt>[0,num_vertices(g1))</tt> and <tt>[0,num_vertices(g2))</tt>
+respectively.<br>
+
+<b>Default:</b> <tt>get(vertex_index, g1)</tt> and <tt>get(vertex_index, g2)</tt>.
+Note: if you use this default, make sure your graph has
+an internal <tt>vertex_index</tt> property. For example,
+<tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+
+UTIL/OUT: <tt>in_to_out1(In2OutMap c1)</tt> and
+          <tt>in_to_out2(In2OutMap c2)</tt>
+<blockquote>
+This maps vertices in the input graphs (<tt>g1</tt> and <tt>g2</tt>
+respectively) to vertices in the output.
+
+<b>Default:</b> an <a
+  href="../../property_map/doc/iterator_property_map.html">
+  </tt>iterator_property_map</tt></a> created from a
+  <tt>std::vector</tt> of the output graph's vertex descriptor type of size
+  <tt>num_vertices(g1)</tt> (<tt>num_vertices(g2)</tt>) and using the
+  <tt>vertex_index1</tt> (<tt>vertex_index2</tt>) for the index map.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V&sup2;+E)</i>.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<!-- TODO! Fill up this information:-->
+<A HREF="">Davi M. J. Barbosa</A>, State University of Campinas (<A HREF="mailto:.."></A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Added: sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,141 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Symmetric Difference</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_symmetric_difference</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_edge_symmetric_difference(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_edge_symmetric_difference(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_vertex_symmetric_difference(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_vertex_symmetric_difference(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+The edge symmetric difference is the graph containing the union of
+vertices in <tt>g1</tt> and <tt>g2</tt> whose edges appear i exactly
+on of either graph <tt>g1</tt> or <tt>g2</tt>. The vertex symmetric
+difference is the graph generated by the symmetric difference of
+vertices, having all edges from <tt>g1</tt> and <tt>g2</tt> whose
+source and target vertices are both in the output (a subset of the
+symmetric difference of edges).
+
+The graphs must contain name properties for vertices and
+edges with type <tt>size_t</tt> and two maps in the graph properties,
+<tt>map&lt;size_t, Vertex&gt; vertices</tt> and <tt>map&lt;size_t,
+Edge&gt; edges</tt>, mapping names to descriptors.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/difference.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g1</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+IN: <tt>const VertexListGraph&amp; g2</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The difference graph between <tt>g1</tt> and <tt>g2</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertex_copy(VertexCopier vc)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in the input graphs
+into the corresponding vertex in the output.<br>
+
+<b>Default:</b> default_vertex_copier which uses the property tag
+<tt>vertex_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>vertices_merge(MergeVertices merge_vertices)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in both input graphs
+into the corresponding vertex in the output.<br>
+
+<b>Default:</b> default_vertices_merge which uses the property tag
+<tt>vertex_all</tt> to access a property map from <tt>g1</tt>, ignoring <tt>g2</tt>.
+</blockquote>
+
+IN: <tt>set_vertex_label(SetVertexLabel set_vertex_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a vertex.<br>
+
+<b>Default:</b> default_set_vertex_label which sets the name in the
+vertex property and also the map from names to vertex descriptors
+in the graph property.
+</blockquote>
+
+IN: <tt>edge_copy(EdgeCopier ec)</tt>
+<blockquote>
+This is a function that copies the properties of an edge in the input graphs
+into the corresponding edge in the output.<br>
+
+<b>Default:</b> default_edge_copier which uses the property tag
+<tt>edge_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>set_edge_label(SetEdgeLabel set_edge_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a edge.<br>
+
+<b>Default:</b> default_set_edge_label which sets the name in the
+edge property and also the map from names to edge descriptors
+in the graph property.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V*R_V+E*R_E)</i>, where <i>R_V</i> and
+<i>R_E</i> are the vertex and edge lookup time.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<!-- TODO! Fill up this information:-->
+<A HREF="">Davi M. J. Barbosa</A>, State University of Campinas (<A HREF="mailto:.."></A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Added: sandbox/SOC/2010/graph/libs/doc/graph_union.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/doc/graph_union.html	2010-08-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -0,0 +1,150 @@
+<HTML>
+<!--
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Graph Union (aka Graph Sum)</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+        ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+     ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><TT>graph_union</TT></H1>
+
+<PRE>
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_union(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_union(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph, class MutableGraph&gt;
+void graph_sum(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2, MutableGraph&amp; g_out,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+template &lt;class VertexListGraph&gt;
+VertexListGraph graph_sum(const VertexListGraph&amp; g1, const VertexListGraph&amp; g2,
+    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+</PRE>
+
+Union and sum are synonyms. The result graph contains vertices and
+edges present in at least one of the inputs (<tt>g1</tt> and
+<tt>g2</tt>). In other words, it does the union of vertices and edges
+from <tt>g1</tt> and <tt>g2</tt>.
+
+The graphs must contain name properties for vertices and edges with
+type <tt>size_t</tt> and two maps in the graph properties,
+<tt>map&lt;size_t, Vertex&gt; vertices</tt> and <tt>map&lt;size_t,
+Edge&gt; edges</tt>, mapping names to descriptors.
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/sum.hpp
+
+<P>
+
+<H3>Parameters</H3>
+
+IN: <tt>const VertexListGraph&amp; g1</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+IN: <tt>const VertexListGraph&amp; g2</tt>
+<blockquote>
+A directed or undirected graph. The graph type must be a model of Vertex List Graph.
+</blockquote>
+
+OUT: <tt>MutableGraph&amp; g_out</tt>
+<blockquote>
+The union of <tt>g1</tt> and <tt>g2</tt>. The graph type must be a model of Mutable Graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>vertex_copy(VertexCopier vc)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in the original graph
+into the corresponding vertex in the copy.<br>
+
+<b>Default:</b> default_vertex_copier which uses the property tag
+<tt>vertex_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>vertices_merge(MergeVertices merge_vertices)</tt>
+<blockquote>
+
+This is a function that copies the properties of a vertex in both input graphs
+into the corresponding vertex in the output.<br>
+
+<b>Default:</b> default_vertices_merge which uses the property tag
+<tt>vertex_all</tt> to access a property map from <tt>g1</tt>, ignoring <tt>g2</tt>.
+</blockquote>
+
+IN: <tt>set_vertex_label(SetVertexLabel set_vertex_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a vertex.<br>
+
+<b>Default:</b> default_set_vertex_label which sets the name in the
+vertex property and also the map from names to vertex descriptors
+in the graph property.
+</blockquote>
+
+IN: <tt>edge_copy(EdgeCopier ec)</tt>
+<blockquote>
+This is a function that copies the properties of an edge in the original graph
+into the corresponding edge in the copy.<br>
+
+<b>Default:</b> default_edge_copier which uses the property tag
+<tt>edge_all</tt> to access a property map from the graph.
+</blockquote>
+
+IN: <tt>edges_merge(MergeEdges merge_edges)</tt>
+<blockquote>
+
+This is a function that copies the properties of an edge in both input graphs
+into the corresponding edge in the output.<br>
+
+<b>Default:</b> default_vertices_merge which uses the property tag
+<tt>vertex_all</tt> to access a property map from <tt>g1</tt>, ignoring <tt>g2</tt>.
+</blockquote>
+
+IN: <tt>set_edge_label(SetEdgeLabel set_edge_label)</tt>
+<blockquote>
+
+This is a function that sets the name of a edge.<br>
+
+<b>Default:</b> default_set_edge_label which sets the name in the
+edge property and also the map from names to edge descriptors
+in the graph property.
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V*R_V+E*R_E)</i>, where <i>R_V</i> and
+<i>R_E</i> are the vertex and edge lookup time.
+
+
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy; 2010</TD><TD>
+<!-- TODO! Fill up this information:-->
+<A HREF="">Davi M. J. Barbosa</A>, State University of Campinas (<A HREF="mailto:.."></A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -20,7 +20,7 @@
 #include <boost/graph/graph_utility.hpp>
 
 #include <boost/graph/copy.hpp>
-#include <boost/graph/union.hpp>
+#include <boost/graph/disjoint_union.hpp>
 
 using namespace boost;
 using namespace std;

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-27 00:11:28 EDT (Fri, 27 Aug 2010)
@@ -22,7 +22,7 @@
 #include <boost/graph/sum.hpp>
 #include <boost/graph/difference.hpp>
 #include <boost/graph/intersection.hpp>
-#include <boost/graph/union.hpp>
+#include <boost/graph/disjoint_union.hpp>
 #include <boost/graph/complement.hpp>
 #include <boost/graph/join.hpp>
 
@@ -142,7 +142,7 @@
   boost::mt19937 gen;
   gen.seed(uint32_t(time(0)));
 
-  Graph g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_diff, g_union, g_join, g_join2;
+  Graph g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_diff, g_sym_diff, g_union, g_join, g_join2;
 
   generate_random_graph(g1, 3,  5, gen, false);
   generate_random_graph(g2, 4, 10, gen, false);
@@ -161,20 +161,20 @@
   cout << endl;
 
   cout << "Complement of g1:" << endl;
-  graph_complement(g1, g_simple_compl, false); // ignore name mapping (but copy vertex properties)
+  graph_complement(g1, g_simple_compl); // ignore name mapping (but copy vertex properties)
   // check(g_compl); // graph_complement don't set graph_label
   print(g_simple_compl);
   cout << endl;
 
   cout << "Complement of g1:" << endl;
   my_vertex_copier<Graph, Graph> c;
-  graph_complement(g1, g_compl, vertex_copy(c), false);
+  g_compl = graph_complement(g1, vertex_copy(c));
   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;
-  graph_complement(g1, g_rcompl, vertex_copy(c).edge_visitor(my_edge_visitor<Edge, Graph>()), true);
+  graph_reflexive_complement(g1, g_rcompl, vertex_copy(c).edge_visitor(my_edge_visitor<Edge, Graph>()));
   check(g_rcompl);
   print(g_rcompl);
   cout << endl;
@@ -197,6 +197,12 @@
   print(g_diff);
   cout << endl;
 
+  cout << "Vertex Symmetric Difference of g1 and g2:" << endl;
+  graph_vertex_symmetric_difference(g1, g2, g_sym_diff);
+  check(g_sym_diff);
+  print(g_sym_diff);
+  cout << endl;
+
   // For union and join, the vertex and edge set are considered to be disjoint.
   // They ignore the vertex and edge names