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

Subject: [Boost-commit] svn:boost r64591 - in sandbox/SOC/2010/graph: . boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-04 05:38:34

Author: dbarbosa
Date: 2010-08-04 05:37:13 EDT (Wed, 04 Aug 2010)
New Revision: 64591
URL: http://svn.boost.org/trac/boost/changeset/64591

Log:
Disjoint union with named parameters (only vertex_copier and edge_copier).

Added:
   sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/graph/algorithms.org        |    15 +++++++--------                         
   sandbox/SOC/2010/graph/boost/graph/union.hpp |    40 +++++++++++++++++++++++++++++++++++++---
   sandbox/SOC/2010/graph/libs/test/test.cpp    |     2 +-                                      
   3 files changed, 45 insertions(+), 12 deletions(-)

Modified: sandbox/SOC/2010/graph/algorithms.org
==============================================================================
--- sandbox/SOC/2010/graph/algorithms.org	(original)
+++ sandbox/SOC/2010/graph/algorithms.org	2010-08-04 05:37:13 EDT (Wed, 04 Aug 2010)
@@ -31,15 +31,13 @@
     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.
+    Alternative name: merge_vertices
 *** 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.
@@ -49,9 +47,10 @@
     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.
+** Repeated Named Parameters
+   Some algorithms receives two of the same parameter...
+   For example, disjoint union will have two vertex_copy and two edge_copy.
+   How do we do this? We pass a pair instead of just one?
 * Algorithms
 ** Union (aka Sum)
 *** Methods
@@ -186,7 +185,7 @@
   - graph graph_disjoint_union(g1, g2)
   - void graph_disjoint_union(g1_out, g2)
 *** Input
-    g1 and g2.
+    g1 and g2, and named parameters: two vertex_copy, two edge_copy, two orig_to_copy and two vertex_index_map
 *** Precondition
     V(g1) intersection V(g2) = empty
     [don't appear in the implementation because we don't care about labels here]
@@ -267,7 +266,7 @@
   - graph graph_reflexive_complement(g_in)
   - void graph_reflexive_complement_inplace(g_in)
 *** Input
-    g_in
+    g_in, copy_vertex
 *** Description
     The graph with the same vertex set such that two vertices are
     adjacent if and only if they are not adjacent in the input.

Modified: sandbox/SOC/2010/graph/boost/graph/union.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/union.hpp	(original)
+++ sandbox/SOC/2010/graph/boost/graph/union.hpp	2010-08-04 05:37:13 EDT (Wed, 04 Aug 2010)
@@ -36,12 +36,46 @@
   }
 
   template <class VertexListGraph, class MutableGraph>
-  void old_graph_union(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+  void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph &g_out)
   {
-    copy_graph(G1, G);
-    copy_graph(G2, G);
+    copy_graph(g1, g_out);
+    copy_graph(g2, g_out);
   }
 
+  template <class VertexListGraph, class MutableGraph, class P, class T, class R>
+  void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph &g_out,
+                            const bgl_named_params<P, T, R>& params)
+  {
+    // still need to do the same with orig_to_copy and vertex_index_map
+    typedef typename detail::vertex_copier<VertexListGraph, MutableGraph> vertex_copier_t;
+    vertex_copier_t vc1 = detail::make_vertex_copier<VertexListGraph, MutableGraph>(g1, g_out);
+    vertex_copier_t vc2 = detail::make_vertex_copier<VertexListGraph, MutableGraph>(g2, g_out);
+    typedef typename detail::edge_copier<VertexListGraph, MutableGraph> edge_copier_t;
+    edge_copier_t ec1 = detail::make_edge_copier<VertexListGraph, MutableGraph>(g1, g_out);
+    edge_copier_t ec2 = detail::make_edge_copier<VertexListGraph, MutableGraph>(g2, g_out);
+
+    auto p = params
+      .vertex_copy (choose_param
+                    (get_param(params, vertex_copy_t()),
+                     std::pair<vertex_copier_t, vertex_copier_t>(vc1, vc2))
+                    )
+      .edge_copy (choose_param
+                  (get_param(params, edge_copy_t()),
+                   std::pair<edge_copier_t, edge_copier_t>(ec1, ec2))
+                  );
+
+    copy_graph
+      (g1, g_out,
+       p.vertex_copy(get_param(p, vertex_copy_t()).first).edge_copy(get_param(p,edge_copy_t()).first)
+       );
+
+    copy_graph
+      (g2, g_out,
+       p.vertex_copy(get_param(p, vertex_copy_t()).second).edge_copy(get_param(p,edge_copy_t()).second)
+       );
+  }
+
+
 } // namespace boost
 
 #endif // BOOST_GRAPH_UNION_HPP

Added: sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp	2010-08-04 05:37:13 EDT (Wed, 04 Aug 2010)
@@ -0,0 +1,140 @@
+#include <iostream>                  // for std::cout
+#include <utility>                   // for std::pair
+#include <algorithm>                 // for std::for_each
+
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/graph/random.hpp>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+#include <boost/graph/union.hpp>
+
+using namespace boost;
+using namespace std;
+
+struct VertexType1
+{
+  string name;
+  int id;
+  int value;
+};
+
+struct VertexType2
+{
+  string name;
+  int id;
+  float value;
+};
+
+typedef adjacency_list < vecS, vecS, bidirectionalS, VertexType1 > Graph1;
+typedef adjacency_list < vecS, vecS, bidirectionalS, VertexType2 > Graph2;
+
+typedef Graph1::vertex_descriptor Vertex1;
+typedef Graph2::vertex_descriptor Vertex2;
+typedef graph_traits<Graph1>::vertex_iterator VertexIterator1;
+typedef graph_traits<Graph2>::vertex_iterator VertexIterator2;
+
+template <typename G1, typename G2>
+struct vertex_copier {
+  vertex_copier(const G1& g1, G2& g2)
+    : vertex_all_map1(get(vertex_all, g1)), 
+      vertex_all_map2(get(vertex_all, g2)) { }
+  
+  template <typename Vertex1, typename Vertex2>
+  void operator()(const Vertex1& v1, Vertex2& v2) const {
+    //    cout << "Copying vertex " << v1 << endl;
+    put(vertex_all_map2, v2, get(vertex_all_map1, v1));
+  }
+  typename property_map<G1, vertex_all_t>::const_type vertex_all_map1;
+  mutable typename property_map<G2, vertex_all_t>::type vertex_all_map2;
+};
+
+
+template <typename G1, typename G2>
+struct mycopier {
+  mycopier(const G1& _g1, G2& _g2, int _add, float _factor)
+    : g1(_g1), g2(_g2), add(_add), factor(_factor) { }
+  
+  template <typename Vertex1, typename Vertex2>
+  void operator()(const Vertex1& v1, Vertex2& v2) const {
+    g2[v2].name = g1[v1].name;
+    g2[v2].id = g1[v1].id + add;
+    g2[v2].value = g1[v1].value*factor;
+  }
+  const G1& g1;
+  G2& g2;
+  int add;
+  float factor;
+};
+
+
+
+// print a graph showing vertex and edge names
+template <class Graph>
+void print(Graph &g) {
+  typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+  typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
+  typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
+  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+    cout << "Vertex " << index[*vi] << " [name: " << g[*vi].name << ", id: " << g[*vi].id << ", value: " << g[*vi].value << "] -->";
+    for (tie(out_i, out_end) = out_edges(*vi, g); out_i != out_end; ++out_i) {
+      cout << " " << index[target(*out_i, g)];
+    }
+    cout << endl;
+  }
+}
+
+template <class Graph>
+void auto_label(Graph &g, string name, int value_offset)
+{
+  typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+  int id = 0;
+
+  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+    stringstream tmp;
+    tmp << id;
+    g[*vi].name = name + tmp.str();
+    g[*vi].id = id;
+    g[*vi].value = id*id + value_offset;
+    id++;
+  }
+}
+
+
+int main(int,char*[])
+{
+  boost::mt19937 gen;
+  gen.seed(uint32_t(time(0)));
+
+  Graph1 g1, g2, g3, g4;
+  Graph2 h1, h2, h3;
+
+  generate_random_graph(g1, 3,  3, gen, false);
+  generate_random_graph(g2, 4,  6, gen, false);
+
+  auto_label(g1, "g1_", 100);
+  auto_label(g2, "g2_", 200);
+
+  cout << "g1:" << endl;
+  print(g1);
+  cout << "g2:" << endl;
+  print(g2);
+
+  graph_disjoint_union(g1, g2, g3);
+  cout << "g3:" << endl;
+  print(g3);
+
+  vertex_copier<Graph1, Graph1> c1(g1, g4), c2(g2, g4);
+  graph_disjoint_union(g1, g2, g4, vertex_copy(make_pair(c1, c2)));
+  cout << "g4:" << endl;
+  print(g4);
+
+  mycopier<Graph1, Graph2> cc1(g1, h1, 10, -2.1111), cc2(g2, h1, 100, 2);
+  graph_disjoint_union(g1, g2, h1, vertex_copy(make_pair(cc1, cc2)));
+  cout << "h1:" << endl;
+  print(h1);
+
+  return EXIT_SUCCESS;
+}

Modified: sandbox/SOC/2010/graph/libs/test/test.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/test.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/test.cpp	2010-08-04 05:37:13 EDT (Wed, 04 Aug 2010)
@@ -198,7 +198,7 @@
 
   Graph h_du;
   cout << "Disjoint union: (h1 union h2)" << endl;
-  old_graph_union(h1, h2, h_du);
+  graph_disjoint_union(h1, h2, h_du);
   prt(h_du);
   // is there any way to clear h_du and use the same variable for all?