Subject: [Boost-commit] svn:boost r64736 - in sandbox/SOC/2010/graph: boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-11 05:09:55
Author: dbarbosa
Date: 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
New Revision: 64736
URL: http://svn.boost.org/trac/boost/changeset/64736
Log:
- Updating properties.hpp and making the code work with the new graph bundled property
- Default copy, merge and visitor parameter functions in default.hpp
- New parameter functions: set_vertex_label and set_edge_label; default functions in default.hpp
- Encapsulating my version of copy vertex and edge (with 4 parameters) to 2 paramters to be passed to copy_graph
- All algorithms working with Named Parameters, but there is still some work to be done (they reiceve at most one copy_vertex and one copy_edge, and disjoint union and join are not yet receiving orig_to_copy_t and vertex_index)
- Fixing copyright info
- Etc
Added:
sandbox/SOC/2010/graph/boost/graph/default.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/graph/boost/graph/complement.hpp | 55 ++++------
sandbox/SOC/2010/graph/boost/graph/difference.hpp | 85 ++++++++++++++++
sandbox/SOC/2010/graph/boost/graph/intersection.hpp | 164 ++++++++++++++++----------------
sandbox/SOC/2010/graph/boost/graph/join.hpp | 126 +++++++++++++++++++-----
sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp | 8 +
sandbox/SOC/2010/graph/boost/graph/properties.hpp | 93 ++++++++++++------
sandbox/SOC/2010/graph/boost/graph/sum.hpp | 202 ++++++++++++++++++++++++++-------------
sandbox/SOC/2010/graph/boost/graph/union.hpp | 76 +++++---------
sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp | 49 +++++----
sandbox/SOC/2010/graph/libs/test/property_test.cpp | 169 ++++++++++++++------------------
sandbox/SOC/2010/graph/libs/test/test.cpp | 10 +
11 files changed, 629 insertions(+), 408 deletions(-)
Modified: sandbox/SOC/2010/graph/boost/graph/complement.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/complement.hpp (original)
+++ sandbox/SOC/2010/graph/boost/graph/complement.hpp 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
//
//=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -13,28 +12,21 @@
#define BOOST_GRAPH_COMPLEMENT_HPP
#include <utility>
-#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/copy.hpp>
+#include <boost/graph/default.hpp>
namespace boost {
namespace detail {
- template <typename EdgeDescriptor, typename Graph>
- struct default_edge_visitor {
- void operator()(const EdgeDescriptor &, Graph &) { }
- };
-
template <typename Graph, typename MutableGraph,
typename CopyVertex,
- typename Orig2OutVertexIndexMap,
- typename NewEdgeVisitor>
+ typename NewEdgeVisitor,
+ typename Orig2OutVertexIndexMap>
void graph_complement_impl(const Graph& g_in, MutableGraph& g_out,
- CopyVertex copy_vertex, Orig2OutVertexIndexMap orig2out,
- NewEdgeVisitor edge_visitor,
+ CopyVertex copy_vertex, NewEdgeVisitor edge_visitor,
+ Orig2OutVertexIndexMap orig2out,
bool reflexive)
{
- typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
typename graph_traits < Graph >::vertex_iterator vi, vi_end;
@@ -44,7 +36,7 @@
for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
OutVertex new_v = add_vertex(g_out);
put(orig2out, *vi, new_v);
- copy_vertex(*vi, new_v);
+ copy_vertex(*vi, g_in, new_v, g_out);
}
// create edges
@@ -62,31 +54,29 @@
}
}
}
- }// namespace detail
+ } // namespace detail
- template <typename VertexListGraph, typename MutableGraph>
- void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
+ template <typename Graph, typename MutableGraph>
+ void graph_complement(const Graph& g_in, MutableGraph& g_out, bool reflexive)
{
typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
- typedef typename graph_traits<MutableGraph>::edge_descriptor edge_t;
std::vector<vertex_t> orig2out(num_vertices(g_in));
detail::graph_complement_impl
(g_in, g_out,
- detail::make_vertex_copier(g_in, g_out),
+ detail::default_vertex_copy<Graph, MutableGraph>(),
+ detail::default_edge_visitor<MutableGraph>(),
make_iterator_property_map(orig2out.begin(),
get(vertex_index, g_in), orig2out[0]),
- detail::default_edge_visitor<edge_t, MutableGraph>(),
reflexive
);
}
- template <typename VertexListGraph, typename MutableGraph,
+ template <typename Graph, typename MutableGraph,
typename P, typename T, typename R>
- void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out,
+ void graph_complement(const Graph& g_in, MutableGraph& g_out,
const bgl_named_params<P, T, R>& params, bool reflexive)
{
- typedef typename graph_traits<MutableGraph>::edge_descriptor edge_t;
typename std::vector<T>::size_type n;
n = is_default_param(get_param(params, orig_to_copy_t()))
? num_vertices(g_in) : 1;
@@ -95,18 +85,21 @@
detail::graph_complement_impl
(g_in, g_out,
- detail::choose_vertex_copier(get_param(params, vertex_copy_t()),
- g_in, g_out),
- make_iterator_property_map(orig2out.begin(),
- get(vertex_index, g_in), orig2out[0]),
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<Graph, MutableGraph>()),
choose_param(get_param(params, edge_visitor_t()),
- detail::default_edge_visitor<edge_t, MutableGraph>()),
+ detail::default_edge_visitor<MutableGraph>()),
+ choose_param(get_param(params, orig_to_copy_t()),
+ make_iterator_property_map
+ (orig2out.begin(),
+ choose_const_pmap(get_param(params, vertex_index),
+ g_in, vertex_index), orig2out[0])),
reflexive
);
}
-// template <typename VertexListGraph, typename MutableGraph>
-// void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+// template <typename Graph, typename MutableGraph>
+// void graph_reflexive_complement(const Graph& g_in, MutableGraph& g_out)
// {
// typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
// std::vector<vertex_t> orig2out(num_vertices(g_in));
Added: sandbox/SOC/2010/graph/boost/graph/default.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/boost/graph/default.hpp 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,162 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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_DEFAULT_HPP
+#define BOOST_GRAPH_DEFAULT_HPP
+
+#include <utility>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost {
+ namespace detail {
+ // To visit brand new edges. Default behavior: it does nothing
+ template <typename Graph>
+ struct default_edge_visitor {
+ typedef typename graph_traits<Graph>::edge_descriptor EdgeDescriptor;
+ void operator()(const EdgeDescriptor &, Graph &) const { }
+ };
+
+ // To set labels
+ template <typename Graph>
+ struct default_set_vertex_label {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ void operator()(size_t label, Vertex& v, Graph& g) const {
+ g[v].name = label;
+ get_property(g).vertices[ label ] = v;
+ }
+ };
+
+ template <typename Graph>
+ struct default_set_edge_label {
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ void operator()(size_t label, Edge& e, Graph& g) const {
+ g[e].name = label;
+ get_property(g).edges[ label ] = e;
+ }
+ };
+
+ // Merge two vertices or two edges that are identified as the same (using the label)
+ // Default behavior is to copy the properties from the first input, ignoring the second
+ template <typename InGraph, typename OutGraph>
+ struct default_vertices_merge {
+ typedef typename graph_traits<InGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+ void operator()(const InVertex& v1, const InGraph&g1,
+ const InVertex& v2, const InGraph&g2,
+ OutVertex& v_out, OutGraph& g_out) const
+ {
+ put(get(vertex_all, g_out), v_out, get(get(vertex_all, g1), v1));
+ }
+ };
+
+ template <typename InGraph, typename OutGraph>
+ struct default_edges_merge {
+ typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
+ typedef typename graph_traits<OutGraph>::edge_descriptor OutEdge;
+ void operator()(const InEdge& e1, const InGraph&g1,
+ const InEdge& e2, const InGraph&g2,
+ OutEdge& e_out, OutGraph& g_out) const
+ {
+ put(get(edge_all, g_out), e_out, get(get(edge_all, g1), e1));
+ }
+ };
+
+ // To copy vertex and edge properties. Similar to code in copy.hpp,
+ // but here operator() receives both graphs as parameters
+ template <typename InGraph, typename OutGraph>
+ struct default_vertex_copy {
+ typedef typename graph_traits<InGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<OutGraph>::vertex_descriptor OutVertex;
+ void operator()(const InVertex& v_in, const InGraph&g_in,
+ OutVertex& v_out, OutGraph& g_out) const
+ {
+ put(get(vertex_all, g_out), v_out, get(get(vertex_all, g_in), v_in));
+ }
+ };
+
+ template <typename InGraph, typename OutGraph>
+ struct default_edge_copy {
+ typedef typename graph_traits<InGraph>::edge_descriptor InEdge;
+ typedef typename graph_traits<OutGraph>::edge_descriptor OutEdge;
+ void operator()(const InEdge& e_in, const InGraph&g_in,
+ OutEdge& e_out, OutGraph& g_out) const
+ {
+ put(get(edge_all, g_out), e_out, get(get(edge_all, g_in), e_in));
+ }
+ };
+
+ // Encapsulation of copier interface taking four arguments
+ // (including both graphs - as defined above) to an interface used
+ // by copy.hpp (taking only two arguments).
+
+ template <typename GraphIn, typename GraphOut, typename Copier>
+ struct encapsulate_vertex_copier {
+ encapsulate_vertex_copier(const GraphIn& g_in, GraphOut& g_out, Copier copier)
+ : g_in(g_in), g_out(g_out), copier(copier) { }
+
+ template <typename VertexIn, typename VertexOut>
+ inline void operator()(const VertexIn& v_in, VertexOut& v_out) {
+ copier(v_in, g_in, v_out, g_out);
+ }
+ private:
+ const GraphIn& g_in;
+ GraphOut& g_out;
+ Copier copier;
+ };
+
+ template <typename Copier, typename GraphIn, typename GraphOut>
+ inline typename detail::encapsulate_vertex_copier<GraphIn, GraphOut, Copier>
+ to_two_parameters_vertex_copier(const GraphIn& g1, GraphOut& g2, Copier c)
+ {
+ return detail::encapsulate_vertex_copier<GraphIn, GraphOut, Copier> (g1, g2, c);
+ }
+
+ template <typename GraphIn, typename GraphOut, typename Copier>
+ struct encapsulate_edge_copier {
+ encapsulate_edge_copier(const GraphIn& g_in, GraphOut& g_out, Copier copier)
+ : g_in(g_in), g_out(g_out), copier(copier) { }
+
+ template <typename EdgeIn, typename EdgeOut>
+ inline void operator()(const EdgeIn& e_in, EdgeOut& e_out) {
+ copier(e_in, g_in, e_out, g_out);
+ }
+ private:
+ const GraphIn& g_in;
+ GraphOut& g_out;
+ Copier copier;
+ };
+
+ template <typename Copier, typename GraphIn, typename GraphOut>
+ inline typename detail::encapsulate_edge_copier<GraphIn, GraphOut, Copier>
+ to_two_parameters_edge_copier(const GraphIn& g1, GraphOut& g2, Copier c)
+ {
+ return detail::encapsulate_edge_copier<GraphIn, GraphOut, Copier> (g1, g2, c);
+ }
+
+// template <typename Param, typename GraphIn, typename GraphOut>
+// inline typename detail::encapsulate_edge_copier<GraphIn, GraphOut, Param>
+// disjoint_union_choose_edge_copier(const GraphIn& g1, GraphOut& g2, Param param)
+// {
+// return detail::encapsulate_edge_copier<GraphIn, GraphOut, Param> (g1, g2, param);
+// }
+//
+// template <typename GraphIn, typename GraphOut>
+// inline typename detail::encapsulate_edge_copier<GraphIn, GraphOut, typename detail::default_edge_copy<GraphIn, GraphOut> >
+// disjoint_union_choose_edge_copier(const GraphIn& g1, GraphOut& g2, detail::error_property_not_found)
+// {
+// return detail::encapsulate_edge_copier<GraphIn, GraphOut, typename detail::default_edge_copy<GraphIn, GraphOut> >
+// (g1, g2, detail::default_edge_copy<GraphIn, GraphOut>());
+// }
+
+
+ } // namespace detail
+} // namespace boost
+
+#endif // BOOST_GRAPH_DEFAULT_HPP
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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
//
//=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -15,12 +14,90 @@
#include <utility>
#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/copy.hpp>
+#include <boost/graph/default.hpp>
namespace boost {
+ namespace detail {
+ template <typename Graph, typename MutableGraph,
+ typename CopyVertex, typename SetVertexLabel,
+ typename CopyEdge, typename SetEdgeLabel>
+ void graph_difference_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge,
+ SetEdgeLabel set_edge_label)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ auto & gl1 = get_property(g1);
+ auto & gl2 = get_property(g2);
+ auto & gl_out = get_property(g_out);
+
+ typename graph_traits < Graph >::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, g1, new_v, g_out);
+ set_vertex_label(g1[*vi].name, new_v, g_out);
+ assert( g_out[new_v].name == g1[*vi].name ); // set_vertex_label did it
+ assert( gl_out.vertices[ g1[*vi].name ] == new_v ); // set_vertex_label did it
+ }
+
+ // copy edges from g1 that are not in g2
+ typename graph_traits < Graph >::edge_iterator ei, ei_end;
+ 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.vertices.find(src) != gl_out.vertices.end() );
+ assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
+
+ if ( gl2.edges.find( g1[*ei].name ) == gl2.edges.end() ) { // if ei is not in g2
+ typename graph_traits<MutableGraph>::edge_descriptor new_e;
+ bool inserted;
+ boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
+ assert( inserted );
+ copy_edge(*ei, g1, new_e, g_out);
+ set_edge_label(g1[*ei].name, new_e, g_out);
+ assert( g_out[new_e].name == g1[*ei].name ); // set_edge_label did it
+ assert( gl_out.edges[ g1[*ei].name ] == new_e ); // set_edge_label did it
+ }
+ }
+ }
+ } // namespace detail
+
+ template <typename Graph, typename MutableGraph>
+ void graph_difference(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+ {
+ detail::graph_difference_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<Graph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edge_copy<Graph, MutableGraph>(),
+ detail::default_set_edge_label<MutableGraph>()
+ );
+ }
+
+ template <typename Graph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void graph_difference(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::graph_difference_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<Graph, MutableGraph>()),
+ choose_param(get_param(params, set_vertex_label_t()),
+ detail::default_set_vertex_label<MutableGraph>()),
+ choose_param(get_param(params, edge_copy_t()),
+ detail::default_edge_copy<Graph, MutableGraph>()),
+ choose_param(get_param(params, set_edge_label_t()),
+ detail::default_set_edge_label<MutableGraph>())
+ );
+ }
// Version with globalVertexMapping
- template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
+ template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
void gvm_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
{
typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
//
//=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -15,100 +14,103 @@
#include <utility>
#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/default.hpp>
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 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;
-
- // 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 vi is in g2
- OutVertex new_v = add_vertex(g_out);
- copy_vertex(*vi, new_v);
- assert( g_out[new_v].name == g1[*vi].name ); // copy_vertex already did it
- gl_out[ g1[*vi].name ] = new_v;
+ namespace detail {
+ template <typename Graph, typename MutableGraph,
+ typename MergeVertices, typename SetVertexLabel,
+ typename MergeEdges, typename SetEdgeLabel>
+ void graph_intersection_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ MergeVertices merge_vertices,
+ SetVertexLabel set_vertex_label,
+ MergeEdges merge_edges,
+ SetEdgeLabel set_edge_label)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ auto & gl1 = get_property(g1);
+ auto & gl2 = get_property(g2);
+ auto & gl_out = get_property(g_out);
+
+ // copy vertices from (g1 intersection g2)
+ typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+ for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+ if ( gl2.vertices.find( g1[*vi].name ) != gl2.vertices.end() ) { // if vi is in g2
+ OutVertex new_v = add_vertex(g_out);
+ merge_vertices(*vi, g1, gl2.vertices.find ( g1[*vi].name )->second, g2, new_v, g_out);
+ set_vertex_label(g1[*vi].name, new_v, g_out);
+ assert( g_out[new_v].name == g1[*vi].name ); // set_vertex_label did it
+ assert( gl_out.vertices[ g1[*vi].name ] == new_v ); // set_vertex_label did it
+ }
}
- }
- // copy edges from (g1 intersection g2)
- // *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 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) ) {
- 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(gl_out[src], gl_out[targ], g_out);
- copy_edge(*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;
+ typename graph_traits < Graph >::edge_iterator ei, ei_end;
+ typename graph_traits < MutableGraph >::edge_descriptor new_e;
+ bool inserted;
+ // copy edges from (g1 intersection g2)
+ 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.vertices.find(src) != gl_out.vertices.end() );
+ assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
+
+ if ( gl2.edges.find( g1[*ei].name ) != gl2.edges.end() ) { // if ei is in g2
+ boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
+ assert( inserted );
+ // merge_edges(*ei, g1, gl2.edges[ g1[*ei].name ], g2, new_e, g_out); // Does not compile! Why?
+ merge_edges(*ei, g1, gl2.edges.find( g1[*ei].name )->second, g2, new_e, g_out);
+ set_edge_label(g1[*ei].name, new_e, g_out);
+ assert( g_out[new_e].name == g1[*ei].name ); // set_edge_label did it
+ assert( gl_out.edges[ g1[*ei].name ] == new_e ); // set_edge_label did it
+ }
}
}
+ } // namespace detail
-#if 0
- // if we use the edge name, the code is the following:
- // 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) {
- auto gl2e = get_property(g2, graph_label).hack->edges;
-
- if ( gl2e.find( g1[*ei].name ) != gl2e.end() ) {
- 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( g2[ source(gl2e[g1[*ei].name], g2) ].name == g1[ source(*ei, g1) ].name);
- assert( g2[ target(gl2e[g1[*ei].name], g2) ].name == g1[ target(*ei, g1) ].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);
- copy_edge(*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;
- }
- }
-#endif // if 0
+ template <typename Graph, typename MutableGraph>
+ void graph_intersection(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+ {
+ detail::graph_intersection_impl
+ (g1, g2, g_out,
+ detail::default_vertices_merge<Graph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edges_merge<Graph, MutableGraph>(),
+ detail::default_set_edge_label<MutableGraph>()
+ );
}
+ template <typename Graph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void graph_intersection(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::graph_intersection_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertices_merge_t()),
+ detail::default_vertices_merge<Graph, MutableGraph>()),
+ choose_param(get_param(params, set_vertex_label_t()),
+ detail::default_set_vertex_label<MutableGraph>()),
+ choose_param(get_param(params, edges_merge_t()),
+ detail::default_edges_merge<Graph, MutableGraph>()),
+ choose_param(get_param(params, set_edge_label_t()),
+ detail::default_set_edge_label<MutableGraph>())
+ );
+ }
// Version with globalVertexMapping
- template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
- void gvm_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+ template <class Graph, class MutableGraph, class globalVertexMapping>
+ void gvm_graph_intersection(const Graph& g1, const Graph& g2, globalVertexMapping m, MutableGraph& g_out)
{
- typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
- 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);
+ detail::vertex_copier<Graph, MutableGraph> copy_vertex = detail::make_vertex_copier(g1, g_out);
+ detail::edge_copier<Graph, MutableGraph> copy_edge = detail::make_edge_copier(g1, g_out);
// copy vertices from (g1 intersection g2)
- typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+ typename graph_traits < Graph >::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
@@ -121,7 +123,7 @@
}
// copy edges from (g1 intersection g2)
- typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ typename graph_traits < Graph >::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;
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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
//
//=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -9,6 +8,9 @@
//=======================================================================
//
+// Todo:
+// - Make it use orig_to_copy_t and vertex_index Named Parameters
+
#ifndef BOOST_GRAPH_JOIN_HPP
#define BOOST_GRAPH_JOIN_HPP
@@ -17,35 +19,105 @@
#include <boost/graph/union.hpp>
namespace boost {
+ namespace detail {
+ template <typename Graph, typename MutableGraph,
+ typename CopyVertex, typename CopyEdge,
+ typename NewEdgeVisitor,
+ typename In2OutVertexIndexMap>
+ void graph_join_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ CopyEdge copy_edge,
+ NewEdgeVisitor edge_visitor,
+ In2OutVertexIndexMap g1_to_out, In2OutVertexIndexMap g2_to_out)
+ {
+ bool directed = is_convertible<typename MutableGraph::directed_category, directed_tag>::value;
+ // if disjoint union was receiving two In2OutVertexIndexMap, then we could just call disjoint union here
+
+ copy_graph
+ (g1, g_out,
+ orig_to_copy(g1_to_out)
+ .vertex_copy(detail::to_two_parameters_vertex_copier(g1, g_out, copy_vertex))
+ .edge_copy(detail::to_two_parameters_edge_copier(g1, g_out, copy_edge))
+ );
+
+ copy_graph
+ (g2, g_out,
+ orig_to_copy(g2_to_out)
+ .vertex_copy(detail::to_two_parameters_vertex_copier(g2, g_out, copy_vertex))
+ .edge_copy(detail::to_two_parameters_edge_copier(g2, g_out, copy_edge))
+ );
+
+ typename graph_traits < Graph >::vertex_iterator vi, vi_end, ui, ui_end;
+ for (tie(ui, ui_end) = vertices(g1); ui != ui_end; ++ui) {
+ for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+ typename graph_traits<MutableGraph>::edge_descriptor new_e;
+ bool inserted;
+ boost::tie(new_e, inserted) = add_edge(get(g1_to_out, *ui),
+ get(g2_to_out, *vi),
+ g_out);
+ assert(inserted);
+ edge_visitor(new_e, g_out);
+
+ if (directed) {
+ boost::tie(new_e, inserted) = add_edge(get(g2_to_out, *vi),
+ get(g1_to_out, *ui),
+ g_out);
+ assert(inserted);
+ edge_visitor(new_e, g_out);
+ }
+ }
+ }
+ }
+ } // namespace detail
+
- template <class VertexListGraph, class MutableGraph>
- void graph_join(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ template <class Graph, class MutableGraph>
+ void graph_join(const Graph& g1, const Graph& g2, MutableGraph& g_out)
{
- typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
+ std::vector<vertex_t> g1_to_out(num_vertices(g1));
+ std::vector<vertex_t> g2_to_out(num_vertices(g2));
+ detail::graph_join_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<Graph, MutableGraph>(),
+ detail::default_edge_copy<Graph, MutableGraph>(),
+ detail::default_edge_visitor<MutableGraph>(),
+ make_iterator_property_map(g1_to_out.begin(),
+ get(vertex_index, g1), g1_to_out[0]),
+ make_iterator_property_map(g2_to_out.begin(),
+ get(vertex_index, g2), g2_to_out[0])
+ );
+ }
- 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;
-
- 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);
- }
+ template <typename Graph, typename MutableGraph, typename P, typename T, typename R>
+ void graph_join(const Graph& g1, const Graph& g2, MutableGraph &g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_t;
+ typename std::vector<T>::size_type n1, n2;
+ if (is_default_param(get_param(params, orig_to_copy_t()))) {
+ n1 = num_vertices(g1);
+ n2 = num_vertices(g2);
+ } else {
+ n1 = n2 = 1;
}
+ std::vector<vertex_t> g1_to_out(n1);
+ std::vector<vertex_t> g2_to_out(n2);
+
+ detail::graph_join_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<Graph, MutableGraph>()),
+ // detail::default_edge_copy<Graph, MutableGraph>(),
+ choose_param(get_param(params, edge_copy_t()),
+ detail::default_edge_copy<Graph, MutableGraph>()),
+ choose_param(get_param(params, edge_visitor_t()),
+ detail::default_edge_visitor<MutableGraph>()),
+ make_iterator_property_map(g1_to_out.begin(),
+ get(vertex_index, g1), g1_to_out[0]),
+ make_iterator_property_map(g2_to_out.begin(),
+ get(vertex_index, g2), g2_to_out[0])
+ );
}
} // namespace boost
Modified: sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp (original)
+++ sandbox/SOC/2010/graph/boost/graph/named_function_params.hpp 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -31,6 +31,10 @@
struct edge_copy_t { };
struct vertex_copy_t { };
struct edge_visitor_t { };
+ struct vertices_merge_t { };
+ struct edges_merge_t { };
+ struct set_vertex_label_t { };
+ struct set_edge_label_t { };
struct vertex_isomorphism_t { };
struct vertex_invariant_t { };
struct vertex_invariant1_t { };
@@ -81,6 +85,10 @@
BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \
BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \
BOOST_BGL_ONE_PARAM_CREF(edge_visitor, edge_visitor) \
+ BOOST_BGL_ONE_PARAM_CREF(vertices_merge, vertices_merge) \
+ BOOST_BGL_ONE_PARAM_CREF(edges_merge, edges_merge) \
+ BOOST_BGL_ONE_PARAM_CREF(set_vertex_label, set_vertex_label) \
+ BOOST_BGL_ONE_PARAM_CREF(set_edge_label, set_edge_label) \
BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \
BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \
BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \
Modified: sandbox/SOC/2010/graph/boost/graph/properties.hpp
==============================================================================
--- sandbox/SOC/2010/graph/boost/graph/properties.hpp (original)
+++ sandbox/SOC/2010/graph/boost/graph/properties.hpp 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -88,7 +88,6 @@
BOOST_DEF_PROPERTY(vertex, all);
BOOST_DEF_PROPERTY(edge, all);
BOOST_DEF_PROPERTY(graph, all);
- BOOST_DEF_PROPERTY(graph, label);
BOOST_DEF_PROPERTY(vertex, index);
BOOST_DEF_PROPERTY(vertex, index1);
BOOST_DEF_PROPERTY(vertex, index2);
@@ -127,6 +126,7 @@
BOOST_DEF_PROPERTY(graph, visitor);
// These tags are used for property bundles
+ BOOST_DEF_PROPERTY(graph, bundle);
BOOST_DEF_PROPERTY(vertex, bundle);
BOOST_DEF_PROPERTY(edge, bundle);
@@ -200,6 +200,7 @@
};
template <class Graph, class PropertyTag>
class vertex_property_map {
+ public:
typedef typename vertex_property_type<Graph>::type Property;
typedef typename graph_tag_or_void<Graph>::type graph_tag;
typedef typename vertex_property_selector<graph_tag>::type Selector;
@@ -243,7 +244,7 @@
template <class Graph, class Property>
struct property_map {
- private:
+ // private:
typedef typename property_kind<Property>::type Kind;
typedef typename detail::property_map_kind_selector<Kind>::type Selector;
typedef typename Selector::template bind_<Graph, Property> Bind;
@@ -264,8 +265,9 @@
template <class Graph, class Property>
class graph_property {
public:
- typedef typename property_value<typename Graph::graph_property_type,
- Property>::type type;
+ typedef typename property_value<
+ typename Graph::graph_property_type, Property
+ >::type type;
};
template <class Graph>
@@ -433,44 +435,71 @@
// These metafunctions help implement the process of determining the vertex
// and edge properties of a graph.
namespace graph_detail {
- template <typename Retag>
+ template<typename Retag>
struct retagged_property {
typedef typename Retag::type type;
};
- template <typename Retag, typename With, typename Without>
+ // Search the normalized PropList (as returned by retagged<>::type) for
+ // the given bundle. Return the type error if no such bundle can be found.
+ template <typename PropList, typename Bundle>
struct retagged_bundle {
- typedef typename mpl::if_<
- is_same<typename Retag::retagged, no_property>,
- Without,
- With
- >::type type;
- };
-
- template <typename Prop>
- struct vertex_prop {
- private:
- typedef detail::retag_property_list<vertex_bundle_t, Prop> Retag;
- public:
- typedef typename retagged_property<Retag>::type type;
- typedef typename retagged_bundle<
- Retag, Prop, no_vertex_bundle
- >::type bundle;
+ typedef typename property_value<PropList, Bundle>::type Value;
+ typedef typename mpl::if_<
+ is_same<Value, detail::error_property_not_found>, no_bundle, Value
+ >::type type;
};
- template <typename Prop>
- struct edge_prop {
-// private:
- typedef detail::retag_property_list<edge_bundle_t, Prop> Retag;
+ template<typename Prop, typename Bundle>
+ class normal_property {
+ // Normalize the property into a property list.
+ typedef detail::retag_property_list<Bundle, Prop> List;
public:
- typedef typename Retag::retagged retagged;
- typedef typename retagged_property<Retag>::type type;
- typedef typename retagged_bundle<
- Retag, Prop, no_edge_bundle
- >::type bundle;
- };
+ // Extract the normalized property and bundle types.
+ typedef typename retagged_property<List>::type property;
+ typedef typename retagged_bundle<property, Bundle>::type bundle;
+ };
+
+ template<typename Prop>
+ struct graph_prop : normal_property<Prop, graph_bundle_t>
+ { };
+
+ template<typename Prop>
+ struct vertex_prop : normal_property<Prop, vertex_bundle_t>
+ { };
+
+ template<typename Prop>
+ struct edge_prop : normal_property<Prop, edge_bundle_t>
+ { };
} // namespace graph_detail
+// NOTE: These functions are declared, but never defined since they need to
+// be overloaded by graph implementations. However, we need them to be
+// declared for the functions below.
+template<typename Graph, typename Tag>
+typename graph_property<Graph, graph_bundle_t>::type&
+get_property(Graph& g, Tag);
+
+template<typename Graph, typename Tag>
+typename graph_property<Graph, graph_bundle_t>::type const&
+get_property(Graph const& g, Tag);
+
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+// NOTE: This operation is a simple adaptor over the overloaded get_property
+// operations.
+template<typename Graph>
+inline typename graph_property<Graph, graph_bundle_t>::type&
+get_property(Graph& g) {
+ return get_property(g, graph_bundle);
+}
+
+template<typename Graph>
+inline typename graph_property<Graph, graph_bundle_t>::type const&
+get_property(Graph const& g) {
+ return get_property(g, graph_bundle);
+}
+#endif
+
} // namespace boost
#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
//
//=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -14,93 +13,158 @@
#include <utility>
#include <boost/graph/global_vertex_mapping.hpp>
+#include <boost/graph/default.hpp>
#include <boost/graph/graph_traits.hpp>
namespace boost {
+ namespace detail {
+ template <typename Graph, typename MutableGraph,
+ typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
+ typename CopyEdge, typename MergeEdges, typename SetEdgeLabel>
+ void graph_sum_impl(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ MergeVertices merge_vertices,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge,
+ MergeEdges merge_edges,
+ SetEdgeLabel set_edge_label)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ auto & gl1 = get_property(g1);
+ auto & gl2 = get_property(g2);
+ auto & gl_out = get_property(g_out);
+
+ typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+ // copy vertices from g1
+ for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi) {
+ if ( gl2.vertices.find ( g1[*vi].name ) == gl2.vertices.end() ) { // if vi is not in g2
+ OutVertex new_v = add_vertex(g_out);
+ copy_vertex(*vi, g1, new_v, g_out);
+ set_vertex_label(g1[*vi].name, new_v, g_out);
+ assert( g_out[new_v].name == g1[*vi].name ); // set_vertex_label did it
+ assert( gl_out.vertices[ g1[*vi].name ] == new_v ); // set_vertex_label did it
+ } else { // vi is also in g2, we should merge them
+ OutVertex new_v = add_vertex(g_out);
+ InVertex v1 = *vi;
+ // merge_vertices(v1, g1, gl2.vertices[ g1[*vi].name ], g2, new_v, g_out); // Does not compile! Why?
+ merge_vertices(*vi, g1, gl2.vertices.find ( g1[*vi].name )->second, g2, new_v, g_out);
+ set_vertex_label(g1[*vi].name, new_v, g_out);
+ assert( g_out[new_v].name == g1[*vi].name ); // set_vertex_label did it
+ assert( gl_out.vertices[ g1[*vi].name ] == new_v ); // set_vertex_label did it
+ }
+ }
+ // copy vertices from (g2 - g1)
+ for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+ if ( gl_out.vertices.find ( g2[*vi].name ) == gl_out.vertices.end() ) { // if vi is not in g1
+ OutVertex new_v = add_vertex(g_out);
+ copy_vertex(*vi, g2, new_v, g_out);
+ set_vertex_label(g2[*vi].name, new_v, g_out);
+ assert( g_out[new_v].name == g2[*vi].name ); // set_vertex_label did it
+ assert( gl_out.vertices[ g2[*vi].name ] == new_v ); // set_vertex_label did it
+ }
+ }
- 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 < Graph >::edge_iterator ei, ei_end;
+ typename graph_traits < MutableGraph >::edge_descriptor new_e;
+ bool inserted;
- 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;
+ // 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.vertices.find(src) != gl_out.vertices.end() );
+ assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
+
+ if ( gl2.edges.find( g1[*ei].name ) == gl2.edges.end() ) { // if ei is not in g2
+ boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
+ assert( inserted );
+ copy_edge(*ei, g1, new_e, g_out);
+ set_edge_label(g1[*ei].name, new_e, g_out);
+ assert( g_out[new_e].name == g1[*ei].name ); // set_edge_label did it
+ assert( gl_out.edges[ g1[*ei].name ] == new_e ); // set_edge_label did it
+ } else {
+ boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
+ assert( inserted );
+ // merge_edges(*ei, g1, gl2.edges[ g1[*ei].name ], g2, new_e, g_out); // Does not compile! Why?
+ merge_edges(*ei, g1, gl2.edges.find( g1[*ei].name )->second, g2, new_e, g_out);
+ set_edge_label(g1[*ei].name, new_e, g_out);
+ assert( g_out[new_e].name == g1[*ei].name ); // set_edge_label did it
+ assert( gl_out.edges[ g1[*ei].name ] == new_e ); // set_edge_label did it
+ }
+ }
+ // 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.vertices.find(src) != gl_out.vertices.end() );
+ assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
+
+ if ( gl_out.edges.find( g2[*ei].name ) == gl_out.edges.end() ) { // ei is not yet in g_out
+ boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
+ assert( inserted );
+ copy_edge(*ei, g2, new_e, g_out);
+ set_edge_label(g2[*ei].name, new_e, g_out);
+ assert( g_out[new_e].name == g2[*ei].name ); // set_edge_label did it
+ assert( gl_out.edges[ g2[*ei].name ] == new_e ); // set_edge_label did it
+ }
}
}
+ } // namespace detail
- 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() );
+ template <typename Graph, typename MutableGraph>
+ void graph_sum(const Graph& g1, const Graph& g2, MutableGraph& g_out)
+ {
+ detail::graph_sum_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<Graph, MutableGraph>(),
+ detail::default_vertices_merge<Graph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edge_copy<Graph, MutableGraph>(),
+ detail::default_edges_merge<Graph, MutableGraph>(),
+ detail::default_set_edge_label<MutableGraph>()
+ );
+ }
- 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;
- }
- }
+ template <typename Graph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void graph_sum(const Graph& g1, const Graph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::graph_sum_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<Graph, MutableGraph>()),
+ choose_param(get_param(params, vertices_merge_t()),
+ detail::default_vertices_merge<Graph, MutableGraph>()),
+ choose_param(get_param(params, set_vertex_label_t()),
+ detail::default_set_vertex_label<MutableGraph>()),
+ choose_param(get_param(params, edge_copy_t()),
+ detail::default_edge_copy<Graph, MutableGraph>()),
+ choose_param(get_param(params, edges_merge_t()),
+ detail::default_edges_merge<Graph, MutableGraph>()),
+ choose_param(get_param(params, set_edge_label_t()),
+ detail::default_set_edge_label<MutableGraph>())
+ );
}
// Version with globalVertexMapping
- template <class VertexListGraph, class MutableGraph, class globalVertexMapping>
- void gvm_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, globalVertexMapping m, MutableGraph& g_out)
+ template <typename Graph, typename MutableGraph, typename globalVertexMapping>
+ void gvm_graph_sum(const Graph& g1, const Graph& g2, globalVertexMapping m, MutableGraph& g_out)
{
- typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<Graph>::vertex_descriptor InVertex;
typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
typedef typename globalVertexMapping::global_id_type id_type;
- detail::vertex_copier<VertexListGraph, MutableGraph>
+ detail::vertex_copier<Graph, MutableGraph>
copy_vertex1 = detail::make_vertex_copier(g1, g_out), copy_vertex2 = detail::make_vertex_copier(g2, g_out);
- detail::edge_copier<VertexListGraph, MutableGraph>
+ detail::edge_copier<Graph, MutableGraph>
copy_edge1 = detail::make_edge_copier(g1, g_out), copy_edge2 = detail::make_edge_copier(g2, g_out);
- typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
+ typename graph_traits < Graph >::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);
@@ -121,7 +185,7 @@
}
}
- typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ typename graph_traits < Graph >::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;
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-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,6 @@
//
//=======================================================================
-// Copyright 1997-2001 University of Notre Dame.
-// Authors: Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
+// Copyright (C) 2010 Davi M. J. Barbosa
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -9,74 +8,57 @@
//=======================================================================
//
+// Todo:
+// - Make it use orig_to_copy_t and vertex_index Named Parametersparameters
+
#ifndef BOOST_GRAPH_UNION_HPP
#define BOOST_GRAPH_UNION_HPP
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/copy.hpp>
-#include <boost/graph/sum.hpp>
+#include <boost/graph/default.hpp>
namespace boost {
-
- // This is also disjoint! But it uses graph_sum and vertice/edge names
- template <class VertexListGraph, class MutableGraph>
- 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>
+ template <typename VertexListGraph, typename MutableGraph>
void graph_disjoint_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph &g_out)
{
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,
+ template <typename Graph, typename MutableGraph, typename P, typename T, typename R>
+ void graph_disjoint_union(const Graph& g1, const Graph& 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)
+ vertex_copy(detail::to_two_parameters_vertex_copier
+ (g1, g_out,
+ choose_param
+ (get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<Graph, MutableGraph>())))
+ .edge_copy(
+ detail::to_two_parameters_edge_copier
+ (g1, g_out,
+ choose_param
+ (get_param(params, edge_copy_t()),
+ detail::default_edge_copy<Graph, MutableGraph>())))
);
copy_graph
(g2, g_out,
- p.vertex_copy(get_param(p, vertex_copy_t()).second).edge_copy(get_param(p,edge_copy_t()).second)
+ vertex_copy(detail::to_two_parameters_vertex_copier
+ (g2, g_out,
+ choose_param
+ (get_param (params, vertex_copy_t()),
+ detail::default_vertex_copy<Graph, MutableGraph>())))
+ .edge_copy(detail::to_two_parameters_edge_copier
+ (g2, g_out,
+ choose_param
+ (get_param (params, edge_copy_t()),
+ detail::default_edge_copy<Graph, MutableGraph>())))
);
}
-
-
} // namespace boost
#endif // BOOST_GRAPH_UNION_HPP
Modified: sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp (original)
+++ sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp 2010-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,3 +1,13 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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)
+//=======================================================================
+//
+
#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // for std::for_each
@@ -9,6 +19,7 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/copy.hpp>
#include <boost/graph/union.hpp>
using namespace boost;
@@ -37,34 +48,25 @@
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));
+struct my_copier {
+ typedef typename graph_traits<G1>::vertex_descriptor Vertex1;
+ typedef typename graph_traits<G2>::vertex_descriptor Vertex2;
+ void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) {
+ put(get(vertex_all, g2), v2, get(get(vertex_all, g1), 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) { }
-
+struct my_copier2 {
+ my_copier2(int _add, float _factor)
+ : add(_add), factor(_factor) { }
+
template <typename Vertex1, typename Vertex2>
- void operator()(const Vertex1& v1, Vertex2& v2) const {
+ void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) {
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;
};
@@ -126,13 +128,14 @@
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)));
+ graph_disjoint_union(g1, g2, g4, vertex_copy(my_copier<Graph1, Graph1>()));
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)));
+ graph_disjoint_union(g1, g2, g4, vertex_copy(my_copier<Graph1, Graph1>()));
+
+
+ graph_disjoint_union(g1, g2, h1, vertex_copy(my_copier2<Graph1, Graph2>(100, 10)));
cout << "h1:" << endl;
print(h1);
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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,3 +1,13 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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)
+//=======================================================================
+//
+
#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // for std::for_each
@@ -9,10 +19,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/difference.hpp>
+#include <boost/graph/intersection.hpp>
#include <boost/graph/union.hpp>
+#include <boost/graph/complement.hpp>
#include <boost/graph/join.hpp>
using namespace boost;
@@ -22,14 +33,13 @@
struct Edge_Label;
struct Graph_Label;
-struct Graph_Label_Hack {
- struct Graph_Label * hack;
-};
-
-typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Label, Edge_Label, property<graph_label_t, Graph_Label_Hack> > Graph;
+typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Label, Edge_Label, Graph_Label, listS > Graph;
-typedef Graph::vertex_descriptor Vertex;
-typedef Graph::edge_descriptor Edge;
+// Hack: Instead of using Graph definition here to define the
+// descriptors, we define them using the same parameters used to
+// define Graph:
+typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::vertex_descriptor Vertex;
+typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::edge_descriptor Edge;
struct Vertex_Label {
size_t name;
@@ -42,30 +52,31 @@
unordered_map<size_t, Edge> edges;
};
-
// First look at main()
// These are auxiliary functions
-// copier that sets the name mapping
+// Vertex copier that sets the name mapping
template <typename G1, typename G2>
-struct my_copier {
- my_copier(const G1& _g1, G2& _g2)
- : 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 {
- auto & gl2 = get_property(g2, graph_label).hack->vertices;
- put(vertex_all_map2, v2, get(vertex_all_map1, v1));
+struct my_vertex_copier {
+ typedef typename graph_traits<G1>::vertex_descriptor Vertex1;
+ typedef typename graph_traits<G2>::vertex_descriptor Vertex2;
+ void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) const {
+ auto & gl2 = get_property(g2).vertices;
+ put(get(vertex_all, g2), v2, get(get(vertex_all, g1), v1));
gl2[ g1[v1].name ] = v2;
}
- const G1& g1;
- G2& g2;
- typename property_map<G1, vertex_all_t>::const_type vertex_all_map1;
- mutable typename property_map<G2, vertex_all_t>::type vertex_all_map2;
+};
+
+// Edge copier that sets the name mapping
+template <typename G1, typename G2>
+struct my_edge_copier {
+ typedef typename graph_traits<G1>::edge_descriptor Edge1;
+ typedef typename graph_traits<G2>::edge_descriptor Edge2;
+ void operator()(const Edge1& e1, const G1& g1, Edge2& e2, G2& g2) const {
+ auto & gl2 = get_property(g2).edges;
+ put(get(edge_all, g2), e2, get(get(edge_all, g1), e1));
+ gl2[ g1[e1].name ] = e2;
+ }
};
// edge visitor for new edges
@@ -73,68 +84,44 @@
struct my_edge_visitor {
void operator()(const EdgeDescriptor &e, Graph &g)
{
- typename graph_traits<Graph>::vertex_descriptor u, v;
- u = source(e, g);
- v = target(e, g);
+ typename graph_traits<Graph>::vertex_descriptor
+ u = source(e, g), v = target(e, g);
g[e].name = g[u].name * 100 + g[v].name;
- get_property(g, graph_label).hack->edges[ g[e].name ] = e;
+ get_property(g).edges[ g[e].name ] = e;
}
};
// name vertices and edges
template <class Graph>
-void auto_label(Graph &g) {
+void auto_label(Graph &g, size_t start_vertex_label = 10, size_t delta_edge_label = 0) {
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
+ size_t label = start_vertex_label; // just to make vertex name != vertex index
// vertices
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
g[*vi].name = label;
- get_property(g, graph_label).hack->vertices[label] = *vi;
+ get_property(g).vertices[label] = *vi;
label++;
}
// edges (does not work for parallel edges - they will have the same name)
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- size_t src, targ;
- src = g[source(*ei, g)].name - 10;
- targ = g[target(*ei, g)].name - 10;
- label = 100 + 10 * src + targ;
+ size_t src = g[source(*ei, g)].name, targ = g[target(*ei, g)].name;
+ label = delta_edge_label + 100 * src + targ;
g[*ei].name = label;
- get_property(g, graph_label).hack->edges[label] = *ei;
- }
-}
-
-
-// rename vertices and edges (only because of union! To make the sets disjoint)
-template <class Graph>
-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;
+ get_property(g).edges[label] = *ei;
}
}
-
// check to see if the naming is ok
template <class Graph>
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);
+ assert( get_property(g).vertices[ g[*vi].name ] == *vi);
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);
+ assert( get_property(g).edges[ g[*ei].name ] == *ei);
}
// print a graph showing vertex and edge names
@@ -152,22 +139,12 @@
}
}
-
int main(int,char*[])
{
boost::mt19937 gen;
gen.seed(uint32_t(time(0)));
- Graph g1, g2, g_simple_compl, 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_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);
+ Graph g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_diff, g_union, g_join, g_join2;
generate_random_graph(g1, 3, 5, gen, false);
generate_random_graph(g2, 4, 10, gen, false);
@@ -192,17 +169,16 @@
cout << endl;
cout << "Complement of g1:" << endl;
- my_copier<Graph, Graph> c(g1, g_compl);
+ my_vertex_copier<Graph, Graph> c;
graph_complement(g1, g_compl, vertex_copy(c), false);
- check(g_compl, false); // graph_complement don't set edge names in graph_label, but my_copier do it for vertices
+ check(g_compl, false); // graph_complement don't set edge names in graph_label, but my_vertex_copier do it for vertices
print(g_compl);
cout << endl;
cout << "Reflexive complement of g1:" << endl;
- my_copier<Graph, Graph> cc(g1, g_rcompl);
- graph_complement(g1, g_rcompl, vertex_copy(cc).edge_visitor(my_edge_visitor<Edge, Graph>()), true);
- print(g_rcompl);
+ graph_complement(g1, g_rcompl, vertex_copy(c).edge_visitor(my_edge_visitor<Edge, Graph>()), true);
check(g_rcompl);
+ print(g_rcompl);
cout << endl;
cout << "Intersection of g1 and g2:" << endl;
@@ -217,29 +193,34 @@
print(g_sum);
cout << endl;
- // 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 << "Difference of g1 and g2:" << endl;
+ graph_difference(g1, g2, g_diff);
+ check(g_diff);
+ print(g_diff);
cout << endl;
- cout << "Disjoint union of g1 and g2':" << endl;
- graph_union(g1, g2, g_union);
- check(g_union);
+ // For union and join, the vertex and edge set are considered to be disjoint.
+ // They ignore the vertex and edge names
+
+ cout << "Disjoint union of g1 and g2:" << endl;
+ graph_disjoint_union(g1, g2, g_union);
print(g_union);
cout << endl;
- cout << "Join of g1 and g2':" << 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;
+ cout << endl;
+
+ cout << "Another join of g1 and g2: (g2 with new labels)" << endl;
+ auto_label(g2, 20, 200);
+ graph_join(g1, g2, g_join2,
+ vertex_copy(my_vertex_copier<Graph, Graph>())
+ .edge_copy(my_edge_copier<Graph, Graph>())
+ .edge_visitor(my_edge_visitor<Edge, Graph>()));
+ check(g_join2); // passes the test because we are using our own functions
+ print(g_join2);
+ // 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-08-11 05:09:52 EDT (Wed, 11 Aug 2010)
@@ -1,3 +1,13 @@
+//
+//=======================================================================
+// Copyright (C) 2010 Davi M. J. Barbosa
+//
+// 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)
+//=======================================================================
+//
+
#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // for std::for_each