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

Subject: [Boost-commit] svn:boost r64559 - in sandbox/SOC/2010/graph: . boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-03 05:20:45

Author: dbarbosa
Date: 2010-08-03 05:20:44 EDT (Tue, 03 Aug 2010)
New Revision: 64559
URL: http://svn.boost.org/trac/boost/changeset/64559

Log:
added named parameters to graph_complement
added named parameters description

Text files modified: 
   sandbox/SOC/2010/graph/algorithms.org              |    37 ++++++++++++++++++                      
   sandbox/SOC/2010/graph/boost/graph/complement.hpp  |    78 ++++++++++++++++++++++++++++++--------- 
   sandbox/SOC/2010/graph/libs/test/property_test.cpp |    42 ++++++++++++++++++--                    
   3 files changed, 133 insertions(+), 24 deletions(-)

Modified: sandbox/SOC/2010/graph/algorithms.org
==============================================================================
--- sandbox/SOC/2010/graph/algorithms.org	(original)
+++ sandbox/SOC/2010/graph/algorithms.org	2010-08-03 05:20:44 EDT (Tue, 03 Aug 2010)
@@ -16,6 +16,42 @@
    NetworkX (python)
 ** http://www.jgrapht.org/javadoc/org/jgrapht/graph/GraphUnion.html
    JGraphT (Java)
+* Parameters/Named parameters
+  Some of the algorithms needs a "labeled graph" (e.g. intersection)
+  to identify vertices and edges that appears in two (or more) input
+  graphs.
+** Named Parameters
+*** vertex_copy
+*** edge_copy
+*** vertex_merge_copy
+    Let v1 and v2 be vertices in g1 and g2. 
+    If we identify that v1 == v2 (using the label) and this vertex
+    should be in the output, we should copy this vertex, but there are
+    two inputs.
+    This function will be like vertex_copy but taking two inputs. The
+    default behaviour will be use vertex_copier for the first input
+    and ignore the second.
+*** edge_merge_copy
+    same as above
+*** orig2out (orig_to_copy)
+    For algorithms with one input. The name orig_to_copy is used in
+    copy, transitive closure, transpose... Should we continue using
+    it?
+    To think: How we do with disjoint union and join? They
+    have two disjoint graphs in the input, so they should had two
+    orig_to_copy, one for each input.
+*** vertex_index_map
+    Already in use by copy, transitive closure, etc. I still need to
+    understand exactly why we need it and where we need it.
+*** create_new_edge (edge visitor ?)
+    My suggestion. When we create a brand new edge, we could call this
+    function. The default behaviour would be do nothing. This can be
+    useful in complement (all edges are new), join (which copy all
+    edges from the inputs but also create new ones), cartesian
+    product, k-th power, closures and reductions, etc.
+*** create_new_vertex (vertex visitor ?)
+    Same as above. Probably none of these algorithms creates brand new
+    vertices.
 * Algorithms
 ** Union (aka Sum)
 *** Methods
@@ -279,6 +315,7 @@
       (why and where is it needed?)
     - http://www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml
 ** TODO Transitive Reduction
+   Implemented (sort of beta?)
 *** Methods
   - void graph_transitive_reduction(g_in, g_out)
   - graph graph_transitive_reduction(g_in)

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-03 05:20:44 EDT (Tue, 03 Aug 2010)
@@ -15,29 +15,28 @@
 #include <utility>
 #include <boost/graph/global_vertex_mapping.hpp>
 #include <boost/graph/graph_traits.hpp>
+#include <boost/graph/copy.hpp>
 
 namespace boost {
   namespace detail {
-    template <class VertexListGraph, class MutableGraph> 
-    void graph_complement_impl(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
+    template <class Graph, class MutableGraph,
+              typename CopyVertex,
+              typename Orig2OutVertexIndexMap>
+    void graph_complement_impl(const Graph& g_in, MutableGraph& g_out,
+                               CopyVertex copy_vertex, Orig2OutVertexIndexMap orig2out,
+                               bool reflexive)
     {
-      typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+      typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
       typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
 
-      detail::vertex_copier<VertexListGraph, MutableGraph> copy_vertex = detail::make_vertex_copier(g_in, g_out);
-
-      auto & gl_in  = get_property(g_in,  graph_label).hack->vertices;
-      auto & gl_out = get_property(g_out, graph_label).hack->vertices;
-
-      typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
-      typename graph_traits < VertexListGraph >::vertex_iterator ui, ui_end;
+      typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+      typename graph_traits < Graph >::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);
         copy_vertex(*vi, new_v);
-        assert( g_out[new_v].name == g_in[*vi].name); // copy_vertex already did it
-        gl_out[ g_in[*vi].name ] = new_v;
       }
 
       // create edges
@@ -46,7 +45,9 @@
           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(*ui, *vi, g_out);
+            boost::tie(new_e, inserted) = add_edge(get(orig2out, *ui),
+                                                   get(orig2out, *vi),
+                                                   g_out);
             assert(inserted);
           }
         }
@@ -54,18 +55,57 @@
     }
   }// namespace detail
 
-  template <class VertexListGraph, class MutableGraph> 
-  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+  template <typename VertexListGraph, typename MutableGraph>
+  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
   {
-    detail::graph_complement_impl(g_in, g_out, false);
+    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]),
+       reflexive
+       );
   }
 
-  template <class VertexListGraph, class MutableGraph> 
-  void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+  template <typename VertexListGraph, typename MutableGraph,
+    class P, class T, class R>
+  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out,
+                        const bgl_named_params<P, T, R>& params, bool reflexive)
   {
-    detail::graph_complement_impl(g_in, g_out, true);
+    typename std::vector<T>::size_type n;
+    n = is_default_param(get_param(params, orig_to_copy_t()))
+      ? num_vertices(g_in) : 1;
+    std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
+      orig2out(n);
+
+    detail::graph_complement_impl
+      (g_in, g_out,
+       detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
+                                    g_in, g_out),
+       make_iterator_property_map(orig2out.begin(),
+                                  get(vertex_index, g_in), orig2out[0]),
+       reflexive
+       );
   }
 
+//  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> 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
+//       );
+//  }
+
 } // namespace boost
 
 #endif // BOOST_GRAPH_COMPLEMENT_HPP

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-03 05:20:44 EDT (Tue, 03 Aug 2010)
@@ -42,6 +42,31 @@
   unordered_map<size_t, Edge> edges;
 };
 
+
+
+// copier that sets the name mapping
+template <typename G1, typename G2>
+struct my_copier {
+  my_copier(const G1& _g1, G2& _g2)
+    : g1(_g1),
+      g2(_g2),
+      vertex_all_map1(get(vertex_all, _g1)), 
+      vertex_all_map2(get(vertex_all, _g2))
+  { }
+  
+  template <typename Vertex1, typename Vertex2>
+  void operator()(const Vertex1& v1, Vertex2& v2) const {
+    auto & gl2 = get_property(g2, graph_label).hack->vertices;
+    put(vertex_all_map2, v2, get(vertex_all_map1, v1));
+    gl2[ g1[v1].name ] = v2;
+  }
+  const G1& g1;
+  G2& g2;
+  typename property_map<G1, vertex_all_t>::const_type vertex_all_map1;
+  mutable typename property_map<G2, vertex_all_t>::type vertex_all_map2;
+};
+
+
 // name vertices and edges
 template <class Graph>
 void auto_label(Graph &g) {
@@ -119,7 +144,7 @@
   boost::mt19937 gen;
   gen.seed(uint32_t(time(0)));
 
-  Graph g1, g2, g_compl, g_rcompl, g_int, g_sum, g_union, g_join;
+  Graph g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_union, g_join;
 
   get_property(g1,       graph_label).hack = new(Graph_Label);
   get_property(g2,       graph_label).hack = new(Graph_Label);
@@ -147,15 +172,22 @@
   cout << endl;
 
   cout << "Complement of g1:" << endl;
-  graph_complement(g1, g_compl);
-  check(g_compl, false); // graph_complement is not setting edge names (yet ?)
+  graph_complement(g1, g_simple_compl, false); // ignore name mapping (but copy vertex properties)
+  print(g_simple_compl);
+  cout << endl;
+
+  cout << "Complement of g1:" << endl;
+  my_copier<Graph, Graph> c(g1, g_compl);
+  graph_complement(g1, g_compl, vertex_copy(c), false);
+  check(g_compl, false); // graph_complement don't set edge names
   print(g_compl);
   cout << endl;
 
   cout << "Reflexive complement of g1:" << endl;
-  graph_reflexive_complement(g1, g_rcompl);
-  check(g_rcompl, false); // graph_reflexive_complement is not setting edge names (yet ?)
+  my_copier<Graph, Graph> cc(g1, g_rcompl);
+  graph_complement(g1, g_rcompl, vertex_copy(cc), true);
   print(g_rcompl);
+  check(g_rcompl, false); // graph_complement don't set edge names
   cout << endl;
 
   cout << "Intersection of g1 and g2:" << endl;