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;