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

Subject: [Boost-commit] svn:boost r64430 - in sandbox/SOC/2010/graph: boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-07-29 05:52:07

Author: dbarbosa
Date: 2010-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
New Revision: 64430
URL: http://svn.boost.org/trac/boost/changeset/64430

Log:
sum and union working with vertex/edge/graph properties
updating function names (prefix gvm_ for functions using globalVertexMapping, and old_ for old code)
some code cleaning

Text files modified: 
   sandbox/SOC/2010/graph/boost/graph/difference.hpp   |     3                                         
   sandbox/SOC/2010/graph/boost/graph/intersection.hpp |    40 +++++++++++--------                     
   sandbox/SOC/2010/graph/boost/graph/join.hpp         |     2                                         
   sandbox/SOC/2010/graph/boost/graph/sum.hpp          |    72 ++++++++++++++++++++++++++++++++++      
   sandbox/SOC/2010/graph/boost/graph/union.hpp        |    20 +++++++++                               
   sandbox/SOC/2010/graph/libs/test/globalid.cpp       |     6 +-                                      
   sandbox/SOC/2010/graph/libs/test/property_test.cpp  |    82 +++++++++++++++++++++++++++++++++------ 
   sandbox/SOC/2010/graph/libs/test/test.cpp           |     8 +-                                      
   8 files changed, 191 insertions(+), 42 deletions(-)

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-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -19,8 +19,9 @@
 
 namespace boost {
 
+  // Version with globalVertexMapping
   template <class VertexListGraph, class MutableGraph, class globalVertexMapping> 
-  void difference(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+  void gvm_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
   {
     typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
     typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;

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-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -18,26 +18,31 @@
 
 namespace boost {
 
+  // Question:
+  // Should we have a function to iterate over vertex making a copy if a predicates holds and another one for edges?
+  // This code pattern appears everywhere.
+
   template <class VertexListGraph, class MutableGraph> 
-  void intersec(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  void graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
   {
     typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
     typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
-    
+
+    // we only copy properties from g1
     detail::vertex_copier<VertexListGraph, MutableGraph> copy_vertex = detail::make_vertex_copier(g1, g_out);
     detail::edge_copier<VertexListGraph, MutableGraph> copy_edge = detail::make_edge_copier(g1, g_out);
 
-    auto gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
-    auto gl2 = get_property(g2, graph_label).hack->vertices;
-    auto gl_out = get_property(g_out, graph_label).hack->vertices;
+    auto & gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
+    auto & gl2 = get_property(g2, graph_label).hack->vertices;
+    auto & gl_out = get_property(g_out, graph_label).hack->vertices;
 
     // copy vertices from (g1 intersection g2)
     typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
     for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
-      if ( gl2.find( g1[*vi].name ) != gl2.end() ) {
+      if ( gl2.find( g1[*vi].name ) != gl2.end() ) { // if vi is in g2
         OutVertex new_v = add_vertex(g_out);
         copy_vertex(*vi, new_v);
-        // g_out[new_v].name = g1[*vi].name; // copy_vertex already did it
+        assert( g_out[new_v].name == g1[*vi].name ); // copy_vertex already did it
         gl_out[ g1[*vi].name ] = new_v;
       }
     }
@@ -46,21 +51,21 @@
     // *not* using the edge name! (but checking with an assert)
     typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
     for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
-      auto g2_s  = gl2.find( g1[source(*ei, g1)].name );
-      auto g2_t  = gl2.find( g1[target(*ei, g1)].name );
+      auto src  = g1[source(*ei, g1)].name;
+      auto targ = g1[target(*ei, g1)].name;
+      auto g2_s  = gl2.find(src);
+      auto g2_t  = gl2.find(targ);
 
       if ( (g2_s != gl2.end() && g2_t != gl2.end() && edge(g2_s->second, g2_t->second, g2).second) ) {
-        auto out_s = gl_out.find( g1[source(*ei, g1)].name );
-        auto out_t = gl_out.find( g1[target(*ei, g1)].name );
-
-        assert(out_s != gl_out.end() && out_t != gl_out.end());
+        assert( gl_out.find(src)  != gl_out.end() );
+        assert( gl_out.find(targ) != gl_out.end() );
         assert( g1[ *ei ].name == g2[ edge(g2_s->second, g2_t->second, g2).first ].name );
 
         typename graph_traits<MutableGraph>::edge_descriptor new_e;
         bool inserted;
-        boost::tie(new_e, inserted) = add_edge(out_s->second, out_t->second, g_out);
+        boost::tie(new_e, inserted) = add_edge(gl_out[src], gl_out[targ], g_out);
         copy_edge(*ei, new_e);
-        // g_out[new_e].name = g1[*ei].name; // copy_edge already did it
+        assert( g_out[new_e].name == g1[*ei].name ); // copy_edge already did it
         get_property(g_out, graph_label).hack->edges[ g1[*ei].name ] = new_e;
       }
     }
@@ -84,7 +89,7 @@
         bool inserted;
         boost::tie(new_e, inserted) = add_edge(out_s->second, out_t->second, g_out);
         copy_edge(*ei, new_e);
-        // g_out[new_e].name = g1[*ei].name; // copy_edge already did it
+        assert( g_out[new_e].name == g1[*ei].name ); // copy_edge already did it
         get_property(g_out, graph_label).hack->edges[ g1[*ei].name ] = new_e;
       }
     }
@@ -92,8 +97,9 @@
   }
 
 
+  // Version with globalVertexMapping
   template <class VertexListGraph, class MutableGraph, class globalVertexMapping> 
-  void intersection(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+  void gvm_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
   {
     typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
     typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;

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-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -18,7 +18,7 @@
 namespace boost {
 
   template <class VertexListGraph, class MutableGraph> 
-  void graph_join(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+  void old_graph_join(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
   {
     typename graph_traits < MutableGraph >::vertex_iterator vi, vi_end;
     typename graph_traits < MutableGraph >::vertex_iterator ui, ui_end;

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-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -17,8 +17,78 @@
 #include <boost/graph/graph_traits.hpp>
 
 namespace boost {
+
+  template <class VertexListGraph, class MutableGraph> 
+  void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  {
+    typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+    typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+    
+    detail::vertex_copier<VertexListGraph, MutableGraph>
+      copy_vertex1 = detail::make_vertex_copier(g1, g_out), copy_vertex2 = detail::make_vertex_copier(g2, g_out);
+    detail::edge_copier<VertexListGraph, MutableGraph>
+      copy_edge1 = detail::make_edge_copier(g1, g_out), copy_edge2 = detail::make_edge_copier(g2, g_out);
+
+    auto & gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
+    auto & gl2 = get_property(g2, graph_label).hack->vertices;
+    auto & gl_out  = get_property(g_out, graph_label).hack->vertices;
+    auto & gl_oute = get_property(g_out, graph_label).hack->edges;
+
+    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+    // copy vertices from g1
+    for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+      OutVertex new_v = add_vertex(g_out);
+      copy_vertex1(*vi, new_v);
+      assert( g_out[new_v].name == g1[*vi].name); // copy_vertex already did it
+      gl_out[ g1[*vi].name ] = new_v;
+    }
+    // copy vertices from (g2 - g1)
+    for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+      if ( gl1.find ( g2[*vi].name ) == gl1.end() ) { // if vi is not in g1
+        OutVertex new_v = add_vertex(g_out);
+        copy_vertex2(*vi, new_v);
+        assert( g_out[new_v].name == g2[*vi].name ); // copy_vertex already did it
+        gl_out[ g2[*vi].name ] = new_v;
+      }
+    }
+
+    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+    typename graph_traits < MutableGraph >::edge_descriptor new_e;
+    bool inserted;
+
+    // copy edges from g1
+    for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+      auto src  = g1[source(*ei, g1)].name;
+      auto targ = g1[target(*ei, g1)].name;
+
+      assert( gl_out.find(src)  != gl_out.end() );
+      assert( gl_out.find(targ) != gl_out.end() );
+
+      boost::tie(new_e, inserted) = add_edge(gl_out[src], gl_out[targ], g_out);
+      copy_edge1(*ei, new_e);
+      assert( g_out[new_e].name == g1[*ei].name ); // copy_edge already did it
+      get_property(g_out, graph_label).hack->edges[ g1[*ei].name ] = new_e;
+    }
+    // copy edges from g2 if it is *not* already there
+    for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
+      auto src  = g2[source(*ei, g2)].name;
+      auto targ = g2[target(*ei, g2)].name;
+
+      assert( gl_out.find(src)  != gl_out.end() );
+      assert( gl_out.find(targ) != gl_out.end() );
+
+      if ( gl_oute.find( g2[*ei].name ) == gl_oute.end() ) { // ei is not yet in g_out
+        boost::tie(new_e, inserted) = add_edge(gl_out[src], gl_out[targ], g_out);
+        copy_edge2(*ei, new_e);
+        assert( g_out[new_e].name == g2[*ei].name ); // copy_edge already did it
+        get_property(g_out, graph_label).hack->edges[ g2[*ei].name ] = new_e;
+      }
+    }
+  }
+
+  // Version with globalVertexMapping
   template <class VertexListGraph, class MutableGraph, class globalVertexMapping> 
-  void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+  void gvm_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
   {
     typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
     typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;

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-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -14,11 +14,29 @@
 
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/copy.hpp>
+#include <boost/graph/sum.hpp>
 
 namespace boost {
 
   template <class VertexListGraph, class MutableGraph> 
-  void disjoint_union(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+  void graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+  {
+    auto gl2  = get_property(g2, graph_label).hack->vertices;
+    auto gl2e = get_property(g2, graph_label).hack->edges;
+    typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+    typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+
+    for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+      assert( gl2.find( g1[*vi].name ) == gl2.end() );
+    }
+    for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+      assert( gl2e.find( g1[*ei].name ) == gl2e.end() );
+    }
+    graph_sum(g1, g2, g_out);
+  }
+
+  template <class VertexListGraph, class MutableGraph>
+  void old_graph_union(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
   {
     copy_graph(G1, G);
     copy_graph(G2, G);

Modified: sandbox/SOC/2010/graph/libs/test/globalid.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/globalid.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/globalid.cpp	2010-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -121,17 +121,17 @@
 
   cout << "g1 + g2:" << endl;
   Graph gs;
-  graph_sum(g1, g2, globalId, gs);
+  gvm_graph_sum(g1, g2, globalId, gs);
   print_graph(gs);
 
   cout << "g1 - g2:" << endl;
   Graph gd;
-  difference(g1, g2, globalId, gd);
+  gvm_graph_difference(g1, g2, globalId, gd);
   print_graph(gd);
 
   cout << "g1 intersection g2:" << endl;
   Graph gi;
-  intersection(g1, g2, globalId, gi);
+  gvm_graph_intersection(g1, g2, globalId, gi);
   print_graph(gi);
 
   return 0;

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-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -10,6 +10,8 @@
 #include <boost/graph/graph_utility.hpp>
 
 #include <boost/graph/intersection.hpp>
+#include <boost/graph/sum.hpp>
+#include <boost/graph/union.hpp>
 
 using namespace boost;
 using namespace std;
@@ -38,8 +40,9 @@
   unordered_map<size_t, Edge> edges;
 };
 
+// name vertices and edges
 template <class Graph>
-void auto_label(Graph &g) { // to name vertices and edges
+void auto_label(Graph &g) {
   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
   typename graph_traits<Graph>::edge_iterator ei, ei_end;
   size_t label = 10; // just to make vertex name != vertex index
@@ -60,15 +63,41 @@
   }
 }
 
+
+// rename vertices and edges (only because of union! To make the sets disjoint)
 template <class Graph>
-void check(Graph &g) { // simple check to see if the naming is ok
+void relabel(Graph &g, size_t delta_v, size_t delta_e) {
   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+  typename graph_traits<Graph>::edge_iterator ei, ei_end;
+  // vertices
+  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+    get_property(g, graph_label).hack->vertices.erase( g[*vi].name );
+    g[*vi].name += delta_v;
+    get_property(g, graph_label).hack->vertices[ g[*vi].name ] = *vi;
+  }
+  // edges (does not work for parallel edges - they will have the same name)
+  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
+    get_property(g, graph_label).hack->edges.erase( g[*ei].name );
+    g[*ei].name += delta_e;
+    get_property(g, graph_label).hack->edges[ g[*ei].name ] = *ei;
+  }
+}
+
+
+// check to see if the naming is ok
+template <class Graph>
+void check(Graph &g) {
+  typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+  typename graph_traits<Graph>::edge_iterator ei, ei_end;
   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
-    assert(get_property(g, graph_label).hack->vertices[g[*vi].name] == *vi);
+    assert( get_property(g, graph_label).hack->vertices[ g[*vi].name ] == *vi);
+  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
+    assert( get_property(g, graph_label).hack->edges[ g[*ei].name ] == *ei);
 }
 
+// print a graph showing vertex and edge names
 template <class Graph>
-void print(Graph &g) { // print a graph showing vertex and edge names
+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;
@@ -87,29 +116,54 @@
   boost::mt19937 gen;
   gen.seed(uint32_t(time(0)));
 
-  Graph g1, g2, g_out;
+  Graph g1, g2, g_int, g_sum, g_union;
 
   get_property(g1, graph_label).hack = new(Graph_Label);
   get_property(g2, graph_label).hack = new(Graph_Label);
-  get_property(g_out, graph_label).hack = new(Graph_Label);
+  get_property(g_int,   graph_label).hack = new(Graph_Label);
+  get_property(g_sum,   graph_label).hack = new(Graph_Label);
+  get_property(g_union, graph_label).hack = new(Graph_Label);
 
-  generate_random_graph(g1, 5, 10, gen, false);
-  generate_random_graph(g2, 6, 16, gen, false);
+  generate_random_graph(g1, 4,  8, gen, false);
+  generate_random_graph(g2, 5, 13, gen, false);
 
   auto_label(g1);
   auto_label(g2);
 
+  cout << "Graph 1 (g1):" << endl;
   check(g1);
-  check(g2);
-
-  cout << "Graph 1:" << endl;
   print(g1);
-  cout << "Graph 2:" << endl;
+  cout << endl;
+
+  cout << "Graph 2 (g2):" << endl;
+  check(g2);
   print(g2);
+  cout << endl;
 
   cout << "Intersection of g1 and g2:" << endl;
-  intersec(g1, g2, g_out);
-  print(g_out);
+  graph_intersection(g1, g2, g_int);
+  check(g_int);
+  print(g_int);
+  cout << endl;
+
+  cout << "Sum of g1 and g2:" << endl;
+  graph_sum(g1, g2, g_sum);
+  check(g_sum);
+  print(g_sum);
+  cout << endl;
+
+  // for union, the vertex and edge set needs to be disjoint.
+  relabel(g2, 80, 800);
+  cout << "Graph 2 with new names (g2'):" << endl;
+  check(g2);
+  print(g2);
+  cout << endl;
+
+  cout << "Union of g1 and g2':" << endl;
+  graph_union(g1, g2, g_union);
+  check(g_union);
+  print(g_union);
+  // cout << endl;
 
   return EXIT_SUCCESS;
 }

Modified: sandbox/SOC/2010/graph/libs/test/test.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/test.cpp	(original)
+++ sandbox/SOC/2010/graph/libs/test/test.cpp	2010-07-29 05:52:05 EDT (Thu, 29 Jul 2010)
@@ -199,7 +199,7 @@
 
   Graph h_du;
   cout << "Disjoint union: (h1 union h2)" << endl;
-  disjoint_union(h1, h2, h_du);
+  old_graph_union(h1, h2, h_du);
   prt(h_du);
   // is there any way to clear h_du and use the same variable for all?
 
@@ -224,17 +224,17 @@
   // because x and y are the considered as the same
   Graph h_s;
   cout << "Graph sum: (h1 + h2)" << endl;
-  graph_sum(h1, h2, globalId, h_s);
+  gvm_graph_sum(h1, h2, globalId, h_s);
   prt(h_s);
 
   Graph h_i;
   cout << "Graph intersection: (h1 intersection h2)" << endl;
-  intersection(h1, h2, globalId, h_i);
+  gvm_graph_intersection(h1, h2, globalId, h_i);
   prt(h_i);
 
   Graph h_diff;
   cout << "Graph difference: (h1 - h2)" << endl;
-  difference(h1, h2, globalId, h_diff);
+  gvm_graph_difference(h1, h2, globalId, h_diff);
   prt(h_diff);
 
   return 0;