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

Subject: [Boost-commit] svn:boost r64459 - in sandbox/SOC/2010/graph: boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-07-30 03:53:48

Author: dbarbosa
Date: 2010-07-30 03:53:46 EDT (Fri, 30 Jul 2010)
New Revision: 64459
URL: http://svn.boost.org/trac/boost/changeset/64459

Log:
Adding join and complement.
They still don't work with edge names.

Added:
   sandbox/SOC/2010/graph/boost/graph/complement.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/graph/boost/graph/intersection.hpp |     4 +-                                      
   sandbox/SOC/2010/graph/boost/graph/join.hpp         |    34 ++++++++++++++++-------                 
   sandbox/SOC/2010/graph/libs/test/property_test.cpp  |    57 ++++++++++++++++++++++++++++++--------- 
   sandbox/SOC/2010/graph/libs/test/test.cpp           |     1                                         
   4 files changed, 68 insertions(+), 28 deletions(-)

Added: sandbox/SOC/2010/graph/boost/graph/complement.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/boost/graph/complement.hpp	2010-07-30 03:53:46 EDT (Fri, 30 Jul 2010)
@@ -0,0 +1,71 @@
+//
+//=======================================================================
+// Copyright 1997-2001 University of Notre Dame.
+// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+//
+
+#ifndef BOOST_GRAPH_COMPLEMENT_HPP
+#define BOOST_GRAPH_COMPLEMENT_HPP
+
+#include <utility>
+#include <boost/graph/global_vertex_mapping.hpp>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost {
+  namespace detail {
+    template <class VertexListGraph, class MutableGraph> 
+    void graph_complement_impl(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
+    {
+      typedef typename graph_traits<VertexListGraph>::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;
+
+      // copy vertices from g_in
+      for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
+        OutVertex new_v = add_vertex(g_out);
+        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
+      for (tie(ui, ui_end) = vertices(g_in); ui != ui_end; ++ui) {
+        for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
+          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);
+            assert(inserted);
+          }
+        }
+      }
+    }
+  }// namespace detail
+
+  template <class VertexListGraph, class MutableGraph> 
+  void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+  {
+    detail::graph_complement_impl(g_in, g_out, false);
+  }
+
+  template <class VertexListGraph, class MutableGraph> 
+  void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+  {
+    detail::graph_complement_impl(g_in, g_out, true);
+  }
+
+} // namespace boost
+
+#endif // BOOST_GRAPH_COMPLEMENT_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-07-30 03:53:46 EDT (Fri, 30 Jul 2010)
@@ -53,8 +53,8 @@
     for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
       auto src  = g1[source(*ei, g1)].name;
       auto targ = g1[target(*ei, g1)].name;
-      auto g2_s  = gl2.find(src);
-      auto g2_t  = gl2.find(targ);
+      auto g2_s = gl2.find(src);
+      auto g2_t = gl2.find(targ);
 
       if ( (g2_s != gl2.end() && g2_t != gl2.end() && edge(g2_s->second, g2_t->second, g2).second) ) {
         assert( gl_out.find(src)  != gl_out.end() );

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-30 03:53:46 EDT (Fri, 30 Jul 2010)
@@ -14,26 +14,38 @@
 
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/copy.hpp>
+#include <boost/graph/union.hpp>
 
 namespace boost {
 
   template <class VertexListGraph, class MutableGraph> 
-  void old_graph_join(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+  void graph_join(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
   {
+    typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+    auto & gl1 = get_property(g1, graph_label).hack->vertices; // c++ 0x
+    auto & gl2 = get_property(g2, graph_label).hack->vertices;
+    auto & gl_out  = get_property(g_out, graph_label).hack->vertices;
+
     typename graph_traits < MutableGraph >::vertex_iterator vi, vi_end;
     typename graph_traits < MutableGraph >::vertex_iterator ui, ui_end;
-    copy_graph(G1, G);
-    copy_graph(G2, G);
-    
-    for (tie(vi, vi_end) = vertices(G1); vi != vi_end; ++vi) {
-      for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) {
-        if (vertex(*ui, G1) == true) // not working
-          std::cout << "Vertex: " << *ui << " is in G1" << std::endl;
-        else
-          std::cout << "Vertex: " << *ui << " is NOT in G1 (G - G1)" << std::endl;
+
+    typedef typename VertexListGraph::directed_category Dr;
+    bool directed = is_convertible<Dr, directed_tag>::value;
+
+    graph_union(g1, g2, g_out);
+
+    for (tie(ui, ui_end) = vertices(g1); ui != ui_end; ++ui) {
+      for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+        OutVertex u = gl_out [ g1[*ui].name ];
+        OutVertex v = gl_out [ g2[*vi].name ];
+        typename graph_traits<MutableGraph>::edge_descriptor new_e;
+        bool inserted;
+        boost::tie(new_e, inserted) = add_edge(u, v, g_out);
+        if (directed)
+          boost::tie(new_e, inserted) = add_edge(v, u, g_out);
       }
     }
-
   }
 
 } // namespace boost

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-30 03:53:46 EDT (Fri, 30 Jul 2010)
@@ -9,9 +9,11 @@
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/graph_utility.hpp>
 
+#include <boost/graph/complement.hpp>
 #include <boost/graph/intersection.hpp>
 #include <boost/graph/sum.hpp>
 #include <boost/graph/union.hpp>
+#include <boost/graph/join.hpp>
 
 using namespace boost;
 using namespace std;
@@ -86,13 +88,14 @@
 
 // check to see if the naming is ok
 template <class Graph>
-void check(Graph &g) {
+void check(Graph &g, bool check_edges = true) {
   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
   typename graph_traits<Graph>::edge_iterator ei, ei_end;
   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
     assert( get_property(g, graph_label).hack->vertices[ g[*vi].name ] == *vi);
-  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
-    assert( get_property(g, graph_label).hack->edges[ g[*ei].name ] == *ei);
+  if ( check_edges )
+    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
+      assert( get_property(g, graph_label).hack->edges[ g[*ei].name ] == *ei);
 }
 
 // print a graph showing vertex and edge names
@@ -116,16 +119,19 @@
   boost::mt19937 gen;
   gen.seed(uint32_t(time(0)));
 
-  Graph g1, g2, g_int, g_sum, g_union;
+  Graph g1, g2, g_compl, g_rcompl, g_int, g_sum, g_union, g_join;
 
-  get_property(g1, graph_label).hack = new(Graph_Label);
-  get_property(g2, graph_label).hack = new(Graph_Label);
-  get_property(g_int,   graph_label).hack = new(Graph_Label);
-  get_property(g_sum,   graph_label).hack = new(Graph_Label);
-  get_property(g_union, graph_label).hack = new(Graph_Label);
+  get_property(g1,       graph_label).hack = new(Graph_Label);
+  get_property(g2,       graph_label).hack = new(Graph_Label);
+  get_property(g_compl,  graph_label).hack = new(Graph_Label);
+  get_property(g_rcompl, graph_label).hack = new(Graph_Label);
+  get_property(g_int,    graph_label).hack = new(Graph_Label);
+  get_property(g_sum,    graph_label).hack = new(Graph_Label);
+  get_property(g_union,  graph_label).hack = new(Graph_Label);
+  get_property(g_join,   graph_label).hack = new(Graph_Label);
 
-  generate_random_graph(g1, 4,  8, gen, false);
-  generate_random_graph(g2, 5, 13, gen, false);
+  generate_random_graph(g1, 3,  5, gen, false);
+  generate_random_graph(g2, 4, 10, gen, false);
 
   auto_label(g1);
   auto_label(g2);
@@ -140,6 +146,18 @@
   print(g2);
   cout << endl;
 
+  cout << "Complement of g1:" << endl;
+  graph_complement(g1, g_compl);
+  check(g_compl, false); // graph_complement is not setting edge names (yet ?)
+  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 ?)
+  print(g_rcompl);
+  cout << endl;
+
   cout << "Intersection of g1 and g2:" << endl;
   graph_intersection(g1, g2, g_int);
   check(g_int);
@@ -152,17 +170,28 @@
   print(g_sum);
   cout << endl;
 
-  // for union, the vertex and edge set needs to be disjoint.
-  relabel(g2, 80, 800);
+  // Gives an error because g1 and g2 are not disjoint:
+  // graph_union(g1, g2, g_union);
+  // graph_join(g1, g2, g_join);
+
+  // for union and join, the vertex and edge set needs to be disjoint.
+  relabel(g2, 80, 800); // to make them disjoint
+
   cout << "Graph 2 with new names (g2'):" << endl;
   check(g2);
   print(g2);
   cout << endl;
 
-  cout << "Union of g1 and g2':" << endl;
+  cout << "Disjoint union of g1 and g2':" << endl;
   graph_union(g1, g2, g_union);
   check(g_union);
   print(g_union);
+  cout << endl;
+
+  cout << "Join of g1 and g2':" << endl;
+  graph_join(g1, g2, g_join);
+  check(g_join, false); // graph_join is not (yet ?) setting edge names for new edges
+  print(g_join);
   // cout << endl;
 
   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-30 03:53:46 EDT (Fri, 30 Jul 2010)
@@ -11,7 +11,6 @@
 #include <boost/graph/sum.hpp>
 #include <boost/graph/intersection.hpp>
 #include <boost/graph/difference.hpp>
-#include <boost/graph/join.hpp>
 
 
 using namespace boost;