|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r64079 - in sandbox/SOC/2010/graph: boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-07-17 01:43:29
Author: dbarbosa
Date: 2010-07-17 01:43:28 EDT (Sat, 17 Jul 2010)
New Revision: 64079
URL: http://svn.boost.org/trac/boost/changeset/64079
Log:
First version of a global identification for graph vertices (global_vertex_mapping.hpp).
Sum, difference and intersection modified to use global_vertex_mapping.
Added:
sandbox/SOC/2010/graph/boost/graph/global_vertex_mapping.hpp (contents, props changed)
sandbox/SOC/2010/graph/libs/test/globalid.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/graph/boost/graph/difference.hpp | 50 ++++++++++++++++++++++-------
sandbox/SOC/2010/graph/boost/graph/intersection.hpp | 51 +++++++++++++++++++++--------
sandbox/SOC/2010/graph/boost/graph/join.hpp | 5 --
sandbox/SOC/2010/graph/boost/graph/sum.hpp | 68 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2010/graph/boost/graph/union.hpp | 5 --
sandbox/SOC/2010/graph/libs/test/Jamfile | 5 +-
sandbox/SOC/2010/graph/libs/test/test.cpp | 50 ++++++++++++++++++-----------
7 files changed, 164 insertions(+), 70 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-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -12,24 +12,50 @@
#ifndef BOOST_GRAPH_DIFFERENCE_HPP
#define BOOST_GRAPH_DIFFERENCE_HPP
-#include <boost/config.hpp>
-#include <vector>
+#include <utility>
+#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/type_traits/conversion_traits.hpp>
namespace boost {
- template <class VertexListGraph, class MutableGraph>
- void difference(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+ template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
+ void difference(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
{
- typename graph_traits < MutableGraph >::edge_iterator ei, ei_end;
- // Don't forget: it is probably better to add only edges that are not in G2 instead of add all and remove them later
+// detail::make_vertex_copier(g_in, g_out);
+// detail::make_edge_copier(g_in, g_out);
- copy_graph(G1, G);
- for (tie(ei, ei_end) = edges(G2); ei != ei_end; ++ei) {
- if (edge(source(*ei, G2), target(*ei, G2), G).second == true)
- remove_edge(source(*ei, G), target(*ei, G), G);
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ // copy vertices from g1
+ typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+ for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+ OutVertex new_v = add_vertex(g_out);
+ // copy_vertex(*vi, new_v); // -> should copy vertex properties here
+ std::pair < typename globalVertexMapping::global_id_type, bool > id = m.get_id(g1, *vi);
+ assert (id.second == true);
+ m.associate(g_out, new_v, id.first);
+ }
+
+
+ // copy edges from g1 that are not in g2
+ typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+ std::pair < InVertex, bool > g2_s, g2_t;
+ std::pair < OutVertex, bool > out_s, out_t;
+ g2_s = m.find_vertex( g1, source(*ei, g1), g2 );
+ g2_t = m.find_vertex( g1, target(*ei, g1), g2 );
+ out_s = m.find_vertex( g1, source(*ei, g1), g_out );
+ out_t = m.find_vertex( g1, target(*ei, g1), g_out );
+
+ assert(out_s.second == true && out_t.second == true);
+
+ if ( ! (g2_s.second && g2_t.second && edge(g2_s.first, g2_t.first, g2).second) ) {
+ typename graph_traits<MutableGraph>::edge_descriptor new_e;
+ bool inserted;
+ boost::tie(new_e, inserted) = add_edge(out_s.first, out_t.first, g_out);
+ // copy_edge(*ei, new_e); // -> should copy vertex properties here
+ }
}
}
Added: sandbox/SOC/2010/graph/boost/graph/global_vertex_mapping.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/boost/graph/global_vertex_mapping.hpp 2010-07-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -0,0 +1,98 @@
+#ifndef BOOST_GRAPH_GLOBAL_VERTEX_MAPPING_HPP
+#define BOOST_GRAPH_GLOBAL_VERTEX_MAPPING_HPP
+
+#include <utility>
+#include <map>
+#include <boost/bimap.hpp>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost {
+ template <class Graph, typename id_type = int, typename graph_name_type = std::string>
+ class GlobalVertexMapping
+ {
+ private:
+ typedef typename graph_traits<const Graph>::vertex_descriptor Vertex;
+ typedef typename boost::bimap < Vertex, id_type > bm_type;
+ typedef typename bm_type::value_type association;
+
+ struct labelling {
+ graph_name_type name;
+ bm_type mapping;
+ };
+
+ std::map < const Graph *, labelling > graph_labelling;
+ id_type dummy_id;
+ Vertex dummy_vertex;
+
+ public:
+ typedef id_type global_id_type;
+
+ GlobalVertexMapping (Vertex dummy_vertex_arg, id_type dummy_id_arg)
+ : dummy_vertex(dummy_vertex_arg), dummy_id(dummy_id_arg) { }
+
+ void add_graph(const Graph &G, graph_name_type name)
+ {
+ graph_labelling[&G].name = name;
+ }
+
+ void associate(const Graph &G, Vertex v, id_type id)
+ {
+ graph_labelling[&G].mapping.insert( association( v, id ));
+ }
+
+ std::pair < Vertex, bool > find_vertex(const Graph &G, Vertex v, const Graph &g_out)
+ {
+ std::pair < id_type, bool > id = get_id(G, v);
+ if (id.second == false)
+ return std::pair<Vertex, bool> (dummy_vertex, false);
+ return get_vertex(g_out, id.first);
+ }
+
+ std::pair < Vertex, bool > get_vertex(const Graph &G, id_type id)
+ {
+ try {
+ return std::pair<Vertex, bool> (graph_labelling[&G].mapping.right.at(id), true);
+ }
+ catch ( std::out_of_range & e ) {
+ return std::pair<Vertex, bool> (dummy_vertex, false);
+ }
+ }
+
+ std::pair < id_type, bool > get_id(const Graph &G, Vertex v)
+ {
+ try {
+ return std::pair<id_type, bool> (graph_labelling[&G].mapping.left.at(v), true);
+ }
+ catch ( std::out_of_range & e ) {
+ return std::pair<id_type, bool> (dummy_id, false);
+ }
+ }
+
+ bool equal(const Graph &G1, Vertex v1, const Graph &G2, Vertex v2)
+ {
+ typename std::map < const Graph *, labelling >::const_iterator
+ i1 = graph_labelling.find(&G1), i2 = graph_labelling.find(&G2);
+ if (i1 == graph_labelling.end() || i2 == graph_labelling.end())
+ return false;
+ bm_type m1 = i1->second.mapping, m2 = i2->second.mapping;
+ typename bm_type::left_const_iterator b1 = m1.left.find(v1), b2 = m2.left.find(v2);
+ if (b1 == m1.left.end() || b2 == m2.left.end())
+ return false;
+ return b1->second == b2->second;
+ }
+
+ void show_associations()
+ {
+ typename std::map < const Graph *, labelling >::const_iterator iter;
+ for ( iter = graph_labelling.begin(); iter != graph_labelling.end(); iter++) {
+ labelling l = iter->second;
+ std::cout << "Graph " << l.name << ": (" << l.mapping.size() << " associations)" << std::endl;
+ typename bm_type::const_iterator liter, lend = l.mapping.end();
+ for ( liter = l.mapping.begin(); liter != lend; liter++ )
+ std::cout << " " << liter->left << " <--> " << liter->right << std::endl;
+ }
+ }
+ };
+}
+
+#endif
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-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -12,26 +12,49 @@
#ifndef BOOST_GRAPH_INTERSECTION_HPP
#define BOOST_GRAPH_INTERSECTION_HPP
-#include <boost/config.hpp>
-#include <vector>
+#include <utility>
+#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/type_traits/conversion_traits.hpp>
namespace boost {
- template <class VertexListGraph, class MutableGraph>
- void intersection(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+ template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
+ void intersection(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
{
- typename graph_traits < MutableGraph >::edge_iterator ei, ei_end;
- typename property_map < MutableGraph, vertex_name_t >::type name_map_G = get(vertex_name, G);
- // typename property_map < VertexListGraph, vertex_name_t >::type name_map_G1 = get(vertex_name, G1);
-
-
- for (tie(ei, ei_end) = edges(G1); ei != ei_end; ++ei)
- if (edge(source(*ei, G1), target(*ei, G1), G2).second == true)
- add_edge(source(*ei, G1), target(*ei, G1), G);
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+ // 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) {
+ std::pair < InVertex, bool > v = m.find_vertex( g1, *vi, g2 ); // search for vi in g2
+ if (v.second == true) { // vi is also in g2
+ OutVertex new_v = add_vertex(g_out);
+ // copy_vertex(*vi, new_v); // -> should copy vertex properties here
+ std::pair < typename globalVertexMapping::global_id_type, bool > id = m.get_id(g1, *vi);
+ assert (id.second == true);
+ m.associate(g_out, new_v, id.first);
+ }
+ }
+
+ // copy edges from (g1 intersection g2)
+ typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+ std::pair < InVertex, bool > g2_s, g2_t;
+ std::pair < OutVertex, bool > out_s, out_t;
+ g2_s = m.find_vertex( g1, source(*ei, g1), g2 );
+ g2_t = m.find_vertex( g1, target(*ei, g1), g2 );
+ out_s = m.find_vertex( g1, source(*ei, g1), g_out );
+ out_t = m.find_vertex( g1, target(*ei, g1), g_out );
+
+ if ( (g2_s.second && g2_t.second && edge(g2_s.first, g2_t.first, g2).second) ) {
+ assert(out_s.second == true && out_t.second == true);
+ typename graph_traits<MutableGraph>::edge_descriptor new_e;
+ bool inserted;
+ boost::tie(new_e, inserted) = add_edge(out_s.first, out_t.first, g_out);
+ // copy_edge(*ei, new_e); // -> should copy vertex properties here
+ }
+ }
}
} // namespace boost
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-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -12,11 +12,8 @@
#ifndef BOOST_GRAPH_JOIN_HPP
#define BOOST_GRAPH_JOIN_HPP
-#include <boost/config.hpp>
-#include <vector>
#include <boost/graph/graph_traits.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/type_traits/conversion_traits.hpp>
+#include <boost/graph/copy.hpp>
namespace boost {
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-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -12,27 +12,65 @@
#ifndef BOOST_GRAPH_SUM_HPP
#define BOOST_GRAPH_SUM_HPP
-#include <boost/config.hpp>
-#include <vector>
+#include <utility>
+#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/type_traits/conversion_traits.hpp>
namespace boost {
-
- template <class VertexListGraph, class MutableGraph>
- void graph_sum(const VertexListGraph& G1, const VertexListGraph& G2, MutableGraph& G)
+ template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
+ void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
{
- typename graph_traits < MutableGraph >::edge_iterator ei, ei_end;
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+ typedef typename globalVertexMapping::global_id_type id_type;
+
+
+ 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_vertex(*vi, new_v); // -> should copy vertex properties here
+ std::pair < typename globalVertexMapping::global_id_type, bool > id = m.get_id(g1, *vi);
+ assert (id.second == true);
+ m.associate(g_out, new_v, id.first);
+ }
+ // copy vertices from (g2 - g1)
+ for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+ std::pair < InVertex, bool > v = m.find_vertex( g2, *vi, g1 ); // search for vi in g1
+ if (v.second == false) { // vi is not in g1
+ OutVertex new_v = add_vertex(g_out);
+ // copy_vertex(*vi, new_v); // -> should copy vertex properties here
+ std::pair < id_type, bool > id = m.get_id(g2, *vi);
+ assert (id.second == true);
+ m.associate(g_out, new_v, id.first);
+ }
+ }
- copy_graph(G1, G);
- // std::cout << "Graph sum - edges: ";
- for (tie(ei, ei_end) = edges(G2); ei != ei_end; ++ei) {
- // typename property_map<MutableGraph, vertex_index_t>::type index = get(vertex_index, G);
- // std::cout << "(" << index[source(*ei, G)] << "," << index[target(*ei, G)] << ") ";
- add_edge(source(*ei, G), target(*ei, G), G);
+ typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ // copy edges from g1
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+ std::pair < OutVertex, bool > out_s, out_t;
+ out_s = m.find_vertex( g1, source(*ei, g1), g_out );
+ out_t = m.find_vertex( g1, target(*ei, g1), g_out );
+ assert(out_s.second == true && out_t.second == true);
+
+ typename graph_traits<MutableGraph>::edge_descriptor new_e;
+ bool inserted;
+ boost::tie(new_e, inserted) = add_edge(out_s.first, out_t.first, g_out);
+ // copy_edge(*ei, new_e); // -> should copy vertex properties here
+ }
+ // copy edges from g2
+ for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
+ std::pair < OutVertex, bool > out_s, out_t;
+ out_s = m.find_vertex( g2, source(*ei, g2), g_out );
+ out_t = m.find_vertex( g2, target(*ei, g2), g_out );
+ assert(out_s.second == true && out_t.second == true);
+
+ typename graph_traits<MutableGraph>::edge_descriptor new_e;
+ bool inserted;
+ boost::tie(new_e, inserted) = add_edge(out_s.first, out_t.first, g_out);
+ // copy_edge(*ei, new_e); // -> should copy vertex properties here
}
- // std::cout << std::endl;
}
} // namespace boost
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-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -12,11 +12,8 @@
#ifndef BOOST_GRAPH_UNION_HPP
#define BOOST_GRAPH_UNION_HPP
-#include <boost/config.hpp>
-#include <vector>
#include <boost/graph/graph_traits.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/type_traits/conversion_traits.hpp>
+#include <boost/graph/copy.hpp>
namespace boost {
Modified: sandbox/SOC/2010/graph/libs/test/Jamfile
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/Jamfile (original)
+++ sandbox/SOC/2010/graph/libs/test/Jamfile 2010-07-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -3,8 +3,8 @@
import testing ;
# If you really want to see the values of the path constants...
-# ECHO $(BOOST_ROOT) ;
-# ECHO $(SOC_ROOT) ;
+ECHO $(BOOST_ROOT) ;
+ECHO $(SOC_ROOT) ;
# Declaring a project causes targets within this module to inherit the
# properties of the target. Here, we're adding to the include paths. Note that
@@ -21,4 +21,5 @@
test-suite graph_test
:
[ run test.cpp ]
+ [ run globalid.cpp ]
;
Added: sandbox/SOC/2010/graph/libs/test/globalid.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/globalid.cpp 2010-07-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -0,0 +1,138 @@
+#include <iostream>
+#include <utility>
+#include <algorithm>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+#include <boost/graph/global_vertex_mapping.hpp>
+
+#include <boost/graph/difference.hpp>
+#include <boost/graph/intersection.hpp>
+#include <boost/graph/sum.hpp>
+
+using namespace boost;
+using namespace std;
+
+// create a typedef for the Graph type
+typedef adjacency_list < vecS, vecS, bidirectionalS, property < vertex_name_t, char > > Graph;
+typedef pair < int, int > Edge;
+
+// if d == 1 creates a cycle
+Graph create_graph(int n, int d)
+{
+ // declare a graph object
+ Graph g(n);
+ char name = 'a';
+ property_map < Graph, vertex_name_t >::type name_map = get(vertex_name, g);
+ graph_traits < Graph >::vertex_iterator vi, vi_end;
+
+ // add the edges to the graph object
+ for (int i = 0; i < n; ++i) {
+ add_edge(i, (i-d+n)%n, g);
+ add_edge(i, (i+d)%n, g);
+ }
+
+ for (tie(vi, vi_end) = vertices(g); vi != vi_end; vi++, name++)
+ name_map[*vi] = name;
+
+ return g;
+}
+
+
+int main(int,char*[])
+{
+ // Make convenient labels for the vertices
+ enum { E, D, C, B, A, N };
+ const int num_vertices = N;
+ const char name[] = "ABCDE";
+ Edge edge_array[] =
+ { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
+ Edge(C,E), Edge(B,D), Edge(D,E), };
+ const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
+ typedef graph_traits<Graph>::vertex_iterator vertex_iter;
+
+ // declare a graph object, adding the edges and edge properties
+ Graph g1(edge_array, edge_array + num_edges, num_vertices);
+ property_map < Graph, vertex_index_t>::type vertex_id = get(vertex_index, g1);
+ property_map < Graph, vertex_name_t >::type name_map1 = get(vertex_name, g1);
+
+ for (std::pair<vertex_iter, vertex_iter> vp = vertices(g1); vp.first != vp.second; ++vp.first) {
+ int id = get(vertex_id, *vp.first);
+ name_map1[id] = name[id];
+ }
+
+ graph_traits<Graph>::edge_iterator ei, ei_end;
+ cout << "edges = ";
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei)
+ cout << "(" << vertex_id[source(*ei, g1)]
+ << "," << vertex_id[target(*ei, g1)] << ") ";
+ cout << endl;
+
+
+ print_graph(g1, name_map1);
+
+ Graph g2 = create_graph(5,1);
+ property_map < Graph, vertex_name_t >::type name_map2 = get(vertex_name, g2);
+ print_graph(g2, name_map2);
+
+
+
+
+ GlobalVertexMapping < Graph, int, string > globalId(*vertices(g1).second, -2);
+ globalId.add_graph(g1,"g1");
+ globalId.add_graph(g2,"g2");
+ globalId.associate(g1,0,0);
+ globalId.associate(g1,1,1);
+ globalId.associate(g1,1,0); // does nothing because (g1,1) is already associated to 1
+ globalId.associate(g1,0,1); // does nothing because (g1,0) is already associated to 0
+ globalId.associate(g1,2,2);
+ globalId.associate(g1,3,3);
+ globalId.associate(g1,4,4);
+
+ globalId.associate(g2,0,4);
+ globalId.associate(g2,1,3);
+ globalId.associate(g2,2,2);
+ globalId.associate(g2,3,1);
+ globalId.associate(g2,4,0);
+
+ globalId.show_associations();
+
+ assert( globalId.equal(g1,0, g2,4));
+ assert( globalId.equal(g1,1, g2,3));
+ assert( globalId.equal(g1,2, g2,2));
+ assert( globalId.equal(g1,3, g2,1));
+ assert( globalId.equal(g1,4, g2,0));
+
+ assert(!globalId.equal(g1,0, g2,0));
+ assert(!globalId.equal(g1,0, g2,1));
+ assert(!globalId.equal(g1,0, g2,2));
+ assert(!globalId.equal(g1,0, g2,3));
+ assert(!globalId.equal(g1,1, g2,0));
+ assert(!globalId.equal(g1,1, g2,1));
+ assert(!globalId.equal(g1,1, g2,2));
+ assert(!globalId.equal(g1,1, g2,4));
+
+ assert( globalId.get_id(g1,0).first == 0 );
+ assert( globalId.get_id(g1,1).first == 1 );
+ assert( globalId.get_id(g2,0).first == 4 );
+ assert( globalId.get_id(g2,3).first == 1 );
+ assert( globalId.get_id(g2,4).first == 0 );
+
+ cout << "g1 + g2:" << endl;
+ Graph gs;
+ graph_sum(g1, g2, globalId, gs);
+ print_graph(gs);
+
+ cout << "g1 - g2:" << endl;
+ Graph gd;
+ difference(g1, g2, globalId, gd);
+ print_graph(gd);
+
+ cout << "g1 intersection g2:" << endl;
+ Graph gi;
+ intersection(g1, g2, globalId, gi);
+ print_graph(gi);
+
+ return 0;
+}
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-17 01:43:28 EDT (Sat, 17 Jul 2010)
@@ -2,11 +2,11 @@
#include <utility> // for std::pair
#include <algorithm> // for std::for_each
-#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/transpose_graph.hpp>
#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/global_vertex_mapping.hpp>
+
#include <boost/graph/union.hpp>
#include <boost/graph/sum.hpp>
#include <boost/graph/intersection.hpp>
@@ -174,19 +174,23 @@
{
Graph h1 = create_graph(5,1);
Graph h2 = create_graph(5,2);
+ graph_traits < Graph >::vertex_descriptor w, z;
+
to_source(h1, 5, 'x');
to_sink(h1, 5, 'x');
to_sink(h2, 5, 'y');
// x and y are the "same"
- add_edge(0, 6, h1); // vertex 6 (w) is only in h1
- add_edge(6, 0, h1);
- get(vertex_name, h1)[6] = 'w';
-
- add_edge(7, 0, h2); // vertex 7 (z) is only in h2
- add_edge(0, 7, h2);
- get(vertex_name, h2)[7] = 'z';
+ w = add_vertex(h1); // vertex 6 (w) is only in h1
+ add_edge(*vertices(h1).first, w, h1);
+ add_edge(w, *vertices(h1).first, h1);
+ get(vertex_name, h1)[w] = 'w';
+
+ z = add_vertex(h2); // vertex 6 (w) is only in h1
+ add_edge(*vertices(h2).first, w, h2);
+ add_edge(w, *vertices(h2).first, h2);
+ get(vertex_name, h2)[z] = 'z';
prt(h1);
prt(h2);
@@ -197,32 +201,40 @@
prt(h_du);
// is there any way to clear h_du and use the same variable for all?
+ GlobalVertexMapping < Graph, graph_traits<Graph>::vertex_descriptor, string > globalId(*vertices(h1).second, -2);
+
+ globalId.add_graph(h1,"h1");
+ globalId.add_graph(h2,"h2");
+
+ globalId.associate(h1, w, 20);
+ globalId.associate(h2, z, 40);
+
+ graph_traits < Graph >::vertex_iterator vi, vi_end;
+ for (tie(vi, vi_end) = vertices(h1); vi != vi_end; vi++)
+ globalId.associate(h1, *vi, *vi);
+ for (tie(vi, vi_end) = vertices(h2); vi != vi_end; vi++)
+ globalId.associate(h2, *vi, *vi);
+
+ globalId.show_associations();
// in this example (graph sum), it creates some parallel edges (e.g., a --> x appears twice)
// because x and y are the considered as the same
Graph h_s;
cout << "Graph sum:" << endl;
- graph_sum(h1, h2, h_s);
+ graph_sum(h1, h2, globalId, h_s);
prt(h_s);
Graph h_i;
cout << "Graph intersection:" << endl;
- intersection(h1, h2, h_i);
+ intersection(h1, h2, globalId, h_i);
prt(h_i);
Graph h_diff;
cout << "Graph difference:" << endl;
- difference(h1, h2, h_diff);
+ difference(h1, h2, globalId, h_diff);
prt(h_diff);
- // Not working
-// Graph h_j;
-// cout << "Graph join:" << endl;
-// graph_join(h1, h2, h_j);
-// prt(h_j);
-
-
return 0;
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk