|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65143 - in sandbox/SOC/2010/graph: boost/graph libs/doc libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-31 01:30:14
Author: dbarbosa
Date: 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
New Revision: 65143
URL: http://svn.boost.org/trac/boost/changeset/65143
Log:
Tests updated
Simple graph version for concerned algorithms (intersection, sum/union and all kinds of difference)
Added:
sandbox/SOC/2010/graph/libs/test/complement.cpp (contents, props changed)
sandbox/SOC/2010/graph/libs/test/difference.cpp (contents, props changed)
sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp (contents, props changed)
sandbox/SOC/2010/graph/libs/test/intersection.cpp (contents, props changed)
sandbox/SOC/2010/graph/libs/test/join.cpp (contents, props changed)
sandbox/SOC/2010/graph/libs/test/sum.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/graph/boost/graph/difference.hpp | 368 +++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2010/graph/boost/graph/intersection.hpp | 107 +++++++++++
sandbox/SOC/2010/graph/boost/graph/join.hpp | 1
sandbox/SOC/2010/graph/boost/graph/sum.hpp | 165 +++++++++++++++++
sandbox/SOC/2010/graph/libs/doc/graph_difference.html | 12 +
sandbox/SOC/2010/graph/libs/doc/graph_intersection.html | 12 +
sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html | 20 ++
sandbox/SOC/2010/graph/libs/doc/graph_union.html | 20 ++
sandbox/SOC/2010/graph/libs/test/Jamfile | 5
sandbox/SOC/2010/graph/libs/test/disjoint_union.cpp | 134 ++++----------
sandbox/SOC/2010/graph/libs/test/property_test.cpp | 195 +++++---------------
11 files changed, 787 insertions(+), 252 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-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -66,12 +66,58 @@
template <typename VertexListGraph, typename MutableGraph,
typename CopyVertex, typename SetVertexLabel,
+ typename CopyEdge>
+ void simple_graph_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge)
+ {
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ //typename graph_bundle_type<VertexListGraph>::type const& gl1 = get_property(g1);
+ typename graph_bundle_type<VertexListGraph>::type const& gl2 = get_property(g2);
+ typename graph_bundle_type<MutableGraph>::type& gl_out = get_property(g_out);
+
+ 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, 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 < VertexListGraph >::edge_iterator ei, ei_end;
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+ size_t src = g1[source(*ei, g1)].name;
+ size_t 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.vertices.find( src ) != gl2.vertices.end() &&
+ gl2.vertices.find( targ ) != gl2.vertices.end() &&
+ edge(gl2.vertices.find(src)->second, gl2.vertices.find(targ)->second, g2).second) ) { // if ei=(src,targ) 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);
+ }
+ }
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename CopyVertex, typename SetVertexLabel,
typename CopyEdge, typename SetEdgeLabel>
void graph_vertex_symmetric_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
- CopyVertex copy_vertex,
- SetVertexLabel set_vertex_label,
- CopyEdge copy_edge,
- SetEdgeLabel set_edge_label)
+ CopyVertex copy_vertex,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge,
+ SetEdgeLabel set_edge_label)
{
typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
@@ -134,6 +180,69 @@
}
template <typename VertexListGraph, typename MutableGraph,
+ typename CopyVertex, typename SetVertexLabel,
+ typename CopyEdge>
+ void simple_graph_vertex_symmetric_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2,
+ MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge)
+ {
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ typename graph_bundle_type<VertexListGraph>::type const& gl1 = get_property(g1);
+ typename graph_bundle_type<VertexListGraph>::type const& gl2 = get_property(g2);
+ typename graph_bundle_type<MutableGraph>::type& gl_out = get_property(g_out);
+
+ typename graph_traits < VertexListGraph >::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 *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
+ }
+ }
+ for (tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
+ if ( gl1.vertices.find( g2[*vi].name ) == gl1.vertices.end() ) { // if vi is 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
+ }
+ }
+
+ typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ typename graph_traits < MutableGraph >::edge_descriptor new_e;
+ bool inserted;
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+ size_t src = g1[source(*ei, g1)].name;
+ size_t targ = g1[target(*ei, g1)].name;
+
+ if (gl_out.vertices.find( src ) != gl_out.vertices.end() &&
+ gl_out.vertices.find( targ ) != gl_out.vertices.end()) {
+ 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);
+ }
+ }
+ for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
+ size_t src = g2[source(*ei, g2)].name;
+ size_t targ = g2[target(*ei, g2)].name;
+
+ if (gl_out.vertices.find( src ) != gl_out.vertices.end() &&
+ gl_out.vertices.find( targ ) != gl_out.vertices.end()) {
+ 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);
+ }
+ }
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
typename CopyEdge, typename SetEdgeLabel>
void graph_edge_symmetric_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
@@ -215,8 +324,93 @@
}
}
}
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
+ typename CopyEdge>
+ void simple_graph_edge_symmetric_difference_impl(const VertexListGraph& g1, const VertexListGraph& g2,
+ MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ MergeVertices merge_vertices,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge)
+ {
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ typename graph_bundle_type<VertexListGraph>::type const& gl1 = get_property(g1);
+ typename graph_bundle_type<VertexListGraph>::type const& gl2 = get_property(g2);
+ typename graph_bundle_type<MutableGraph>::type& gl_out = get_property(g_out);
+
+ typename graph_traits < VertexListGraph >::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);
+ 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
+ }
+ }
+
+ typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
+ typename graph_traits < MutableGraph >::edge_descriptor new_e;
+ bool inserted;
+
+ // copy edges from g1 - g2
+ for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
+ size_t src = g1[source(*ei, g1)].name;
+ size_t 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.vertices.find( src ) != gl2.vertices.end() &&
+ gl2.vertices.find( targ ) != gl2.vertices.end() &&
+ edge(gl2.vertices.find(src)->second, gl2.vertices.find(targ)->second, g2).second) ) { // if ei=(src,targ) 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);
+ }
+ }
+ // copy edges from g2 - g1
+ for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
+ size_t src = g2[source(*ei, g2)].name;
+ size_t 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 ( ! (gl1.vertices.find( src ) != gl1.vertices.end() &&
+ gl1.vertices.find( targ ) != gl1.vertices.end() &&
+ edge(gl1.vertices.find(src)->second, gl1.vertices.find(targ)->second, g1).second) ) { // if ei=(src,targ) 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, g2, new_e, g_out);
+ }
+ }
+ }
} // namespace detail
+ //
+ // graph_difference
+ //
+
template <typename VertexListGraph, typename MutableGraph>
void graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
{
@@ -264,6 +458,58 @@
return g_out;
}
+ //
+ // simple_graph_difference
+ //
+
+ template <typename VertexListGraph, typename MutableGraph>
+ void simple_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ {
+ detail::simple_graph_difference_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edge_copy<VertexListGraph, MutableGraph>()
+ );
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void simple_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::simple_graph_difference_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<VertexListGraph, 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<VertexListGraph, MutableGraph>())
+ );
+ }
+
+ template <typename VertexListGraph>
+ VertexListGraph simple_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2)
+ {
+ VertexListGraph g_out;
+ simple_graph_difference(g1, g2, g_out);
+ return g_out;
+ }
+
+ template <typename VertexListGraph, typename P, typename T, typename R>
+ VertexListGraph simple_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params)
+ {
+ VertexListGraph g_out;
+ simple_graph_difference(g1, g2, g_out, params);
+ return g_out;
+ }
+
+ //
+ // graph_vertex_symmetric_difference
+ //
+
template <typename VertexListGraph, typename MutableGraph>
void graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
{
@@ -279,7 +525,7 @@
template <typename VertexListGraph, typename MutableGraph,
typename P, typename T, typename R>
void graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params)
{
detail::graph_vertex_symmetric_difference_impl
(g1, g2, g_out,
@@ -304,19 +550,72 @@
template <typename VertexListGraph, typename P, typename T, typename R>
VertexListGraph graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params)
{
VertexListGraph g_out;
graph_vertex_symmetric_difference(g1, g2, g_out, params);
return g_out;
}
+ //
+ // simple_graph_vertex_symmetric_difference
+ //
+
+ template <typename VertexListGraph, typename MutableGraph>
+ void simple_graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ {
+ detail::simple_graph_vertex_symmetric_difference_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edge_copy<VertexListGraph, MutableGraph>()
+ );
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void simple_graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::simple_graph_vertex_symmetric_difference_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<VertexListGraph, 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<VertexListGraph, MutableGraph>())
+ );
+ }
+
+ template <typename VertexListGraph>
+ VertexListGraph simple_graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2)
+ {
+ VertexListGraph g_out;
+ simple_graph_vertex_symmetric_difference(g1, g2, g_out);
+ return g_out;
+ }
+
+ template <typename VertexListGraph, typename P, typename T, typename R>
+ VertexListGraph simple_graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params)
+ {
+ VertexListGraph g_out;
+ simple_graph_vertex_symmetric_difference(g1, g2, g_out, params);
+ return g_out;
+ }
+
+ //
+ // graph_edge_symmetric_difference
+ //
+
template <typename VertexListGraph, typename MutableGraph>
void graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
{
detail::graph_edge_symmetric_difference_impl
(g1, g2, g_out,
detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+ detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
detail::default_set_vertex_label<MutableGraph>(),
detail::default_edge_copy<VertexListGraph, MutableGraph>(),
detail::default_set_edge_label<MutableGraph>()
@@ -326,12 +625,14 @@
template <typename VertexListGraph, typename MutableGraph,
typename P, typename T, typename R>
void graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params)
{
detail::graph_edge_symmetric_difference_impl
(g1, g2, g_out,
choose_param(get_param(params, vertex_copy_t()),
detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
+ choose_param(get_param(params, vertices_merge_t()),
+ detail::default_vertices_merge<VertexListGraph, MutableGraph>()),
choose_param(get_param(params, set_vertex_label_t()),
detail::default_set_vertex_label<MutableGraph>()),
choose_param(get_param(params, edge_copy_t()),
@@ -351,12 +652,63 @@
template <typename VertexListGraph, typename P, typename T, typename R>
VertexListGraph graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params)
{
VertexListGraph g_out;
graph_edge_symmetric_difference(g1, g2, g_out, params);
return g_out;
}
+
+ //
+ // simple_graph_edge_symmetric_difference
+ //
+
+ template <typename VertexListGraph, typename MutableGraph>
+ void simple_graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ {
+ detail::simple_graph_edge_symmetric_difference_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+ detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edge_copy<VertexListGraph, MutableGraph>()
+ );
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void simple_graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::simple_graph_edge_symmetric_difference_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
+ choose_param(get_param(params, vertices_merge_t()),
+ detail::default_vertices_merge<VertexListGraph, 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<VertexListGraph, MutableGraph>())
+ );
+ }
+
+ template <typename VertexListGraph>
+ VertexListGraph simple_graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2)
+ {
+ VertexListGraph g_out;
+ simple_graph_edge_symmetric_difference(g1, g2, g_out);
+ return g_out;
+ }
+
+ template <typename VertexListGraph, typename P, typename T, typename R>
+ VertexListGraph simple_graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params)
+ {
+ VertexListGraph g_out;
+ simple_graph_edge_symmetric_difference(g1, g2, g_out, params);
+ return g_out;
+ }
} // namespace boost
#endif // BOOST_GRAPH_DIFFERENCE_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-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -52,10 +52,11 @@
for (tie(ei, ei_end) = edges(g1); ei != ei_end; ++ei) {
size_t src = g1[source(*ei, g1)].name;
size_t 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
+ assert( gl_out.vertices.find(src) != gl_out.vertices.end() );
+ assert( gl_out.vertices.find(targ) != gl_out.vertices.end() );
+
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.find( g1[*ei].name )->second, g2, new_e, g_out);
@@ -65,7 +66,61 @@
}
}
}
- } // namespace detail
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename MergeVertices, typename SetVertexLabel,
+ typename MergeEdges>
+ void simple_graph_intersection_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ MergeVertices merge_vertices,
+ SetVertexLabel set_vertex_label,
+ MergeEdges merge_edges)
+ {
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ //typename graph_bundle_type<VertexListGraph>::type const& gl1 = get_property(g1);
+ typename graph_bundle_type<VertexListGraph>::type const& gl2 = get_property(g2);
+ typename graph_bundle_type<MutableGraph>::type& gl_out = get_property(g_out);
+
+ // 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.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
+ }
+ }
+
+ typename graph_traits < VertexListGraph >::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) {
+ size_t src = g1[source(*ei, g1)].name;
+ size_t targ = g1[target(*ei, g1)].name;
+ // It was better to do something like:
+ // typename unordered_map<size_t,InVertex>::const_iterator g2_src = gl2.vertices.find( src );
+ // typename unordered_map<size_t,InVertex>::const_iterator g2_targ = gl2.vertices.find( targ );
+ // But with this I fix gl2.vertices to be an unordered_map...
+
+ if ( gl2.vertices.find( src ) != gl2.vertices.end() &&
+ gl2.vertices.find( targ ) != gl2.vertices.end() &&
+ edge(gl2.vertices.find(src)->second, gl2.vertices.find(targ)->second, g2).second ) { // if ei=(src,targ) 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,
+ edge(gl2.vertices.find(src)->second, gl2.vertices.find(targ)->second, g2).first, g2,
+ new_e, g_out);
+ }
+ }
+ }
+ } // namespace
+
+ // graph_intersection
template <typename VertexListGraph, typename MutableGraph>
void graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
@@ -113,6 +168,52 @@
graph_intersection(g1, g2, g_out, params);
return g_out;
}
+
+ // simple_graph_intersection
+
+ template <typename VertexListGraph, typename MutableGraph>
+ void simple_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ {
+ detail::simple_graph_intersection_impl
+ (g1, g2, g_out,
+ detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edges_merge<VertexListGraph, MutableGraph>()
+ );
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void simple_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::simple_graph_intersection_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertices_merge_t()),
+ detail::default_vertices_merge<VertexListGraph, 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<VertexListGraph, MutableGraph>())
+ );
+ }
+
+ template <typename VertexListGraph>
+ VertexListGraph simple_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2)
+ {
+ VertexListGraph g_out;
+ simple_graph_intersection(g1, g2, g_out);
+ return g_out;
+ }
+
+ template <typename VertexListGraph, typename P, typename T, typename R>
+ VertexListGraph simple_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params)
+ {
+ VertexListGraph g_out;
+ simple_graph_intersection(g1, g2, g_out, params);
+ return g_out;
+ }
} // namespace boost
#endif // BOOST_GRAPH_INTERSECTION_HPP
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-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -16,6 +16,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/copy.hpp>
+#include <boost/graph/default.hpp>
namespace boost {
namespace detail {
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-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -107,6 +107,91 @@
}
}
}
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename CopyVertex, typename MergeVertices, typename SetVertexLabel,
+ typename CopyEdge, typename MergeEdges>
+ void simple_graph_sum_impl(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ CopyVertex copy_vertex,
+ MergeVertices merge_vertices,
+ SetVertexLabel set_vertex_label,
+ CopyEdge copy_edge,
+ MergeEdges merge_edges)
+ {
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor InVertex;
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor OutVertex;
+
+ //typename graph_bundle_type<VertexListGraph>::type const& gl1 = get_property(g1);
+ typename graph_bundle_type<VertexListGraph>::type const& gl2 = get_property(g2);
+ typename graph_bundle_type<MutableGraph>::type& gl_out = get_property(g_out);
+
+ typename graph_traits < VertexListGraph >::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);
+ 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
+ }
+ }
+
+ 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) {
+ size_t src = g1[source(*ei, g1)].name;
+ size_t 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.vertices.find( src ) != gl2.vertices.end() &&
+ gl2.vertices.find( targ ) != gl2.vertices.end() &&
+ edge(gl2.vertices.find(src)->second, gl2.vertices.find(targ)->second, g2).second) ) { // if ei=(src,targ) 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);
+ } else {
+ boost::tie(new_e, inserted) = add_edge(gl_out.vertices[src], gl_out.vertices[targ], g_out);
+ assert( inserted );
+ merge_edges(*ei, g1,
+ edge(gl2.vertices.find(src)->second, gl2.vertices.find(targ)->second, g2).first, g2,
+ new_e, g_out);
+ }
+ }
+ // copy edges from g2 if it is *not* already there
+ for (tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
+ size_t src = g2[source(*ei, g2)].name;
+ size_t 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 ( ! (edge(gl_out.vertices[src], gl_out.vertices[targ], g_out).second) ) { // ei=(src,targ) 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);
+ }
+ }
+ }
} // namespace detail
@@ -190,6 +275,86 @@
{
return graph_sum(g1, g2, params);
}
+
+ // For simple graphs
+
+ template <typename VertexListGraph, typename MutableGraph>
+ void simple_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ {
+ detail::simple_graph_sum_impl
+ (g1, g2, g_out,
+ detail::default_vertex_copy<VertexListGraph, MutableGraph>(),
+ detail::default_vertices_merge<VertexListGraph, MutableGraph>(),
+ detail::default_set_vertex_label<MutableGraph>(),
+ detail::default_edge_copy<VertexListGraph, MutableGraph>(),
+ detail::default_edges_merge<VertexListGraph, MutableGraph>()
+ );
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename P, typename T, typename R>
+ void simple_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ detail::simple_graph_sum_impl
+ (g1, g2, g_out,
+ choose_param(get_param(params, vertex_copy_t()),
+ detail::default_vertex_copy<VertexListGraph, MutableGraph>()),
+ choose_param(get_param(params, vertices_merge_t()),
+ detail::default_vertices_merge<VertexListGraph, 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<VertexListGraph, MutableGraph>()),
+ choose_param(get_param(params, edges_merge_t()),
+ detail::default_edges_merge<VertexListGraph, MutableGraph>())
+ );
+ }
+
+ template <typename VertexListGraph>
+ VertexListGraph simple_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2)
+ {
+ VertexListGraph g_out;
+ simple_graph_sum(g1, g2, g_out);
+ return g_out;
+ }
+
+ template <typename VertexListGraph, typename P, typename T, typename R>
+ VertexListGraph simple_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params)
+ {
+ VertexListGraph g_out;
+ simple_graph_sum(g1, g2, g_out, params);
+ return g_out;
+ }
+
+ // simple_graph_union is an alias to simple_graph_sum
+ template <typename VertexListGraph, typename MutableGraph>
+ inline void simple_graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out)
+ {
+ simple_graph_sum(g1, g2, g_out);
+ }
+
+ template <typename VertexListGraph, typename MutableGraph,
+ typename P, typename T, typename R>
+ inline void simple_graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params)
+ {
+ simple_graph_sum(g1, g2, g_out, params);
+ }
+
+ template <typename VertexListGraph>
+ inline VertexListGraph simple_graph_union(const VertexListGraph& g1, const VertexListGraph& g2)
+ {
+ return simple_graph_sum(g1, g2);
+ }
+
+ template <typename VertexListGraph, typename P, typename T, typename R>
+ inline VertexListGraph simple_graph_union(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params)
+ {
+ return simple_graph_sum(g1, g2, params);
+ }
} // namespace boost
#endif // BOOST_GRAPH_SUM_HPP
Modified: sandbox/SOC/2010/graph/libs/doc/graph_difference.html
==============================================================================
--- sandbox/SOC/2010/graph/libs/doc/graph_difference.html (original)
+++ sandbox/SOC/2010/graph/libs/doc/graph_difference.html 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -24,6 +24,14 @@
template <class VertexListGraph>
VertexListGraph graph_difference(const VertexListGraph& g1, const VertexListGraph& g2,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph, class MutableGraph>
+void simple_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph>
+VertexListGraph simple_graph_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
</PRE>
The result graph is <tt>g1</tt> without the edges of graph
@@ -34,6 +42,10 @@
<tt>map<size_t, Vertex> vertices</tt> and <tt>map<size_t,
Edge> edges</tt>, mapping names to descriptors.
+The simple version relies only on vertex naming to identify edges, not
+needing the vertex names and not receiving the <tt>set_edge_label</tt>
+argument.
+
<H3>Where Defined</H3>
<P>
Modified: sandbox/SOC/2010/graph/libs/doc/graph_intersection.html
==============================================================================
--- sandbox/SOC/2010/graph/libs/doc/graph_intersection.html (original)
+++ sandbox/SOC/2010/graph/libs/doc/graph_intersection.html 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -24,6 +24,14 @@
template <class VertexListGraph>
VertexListGraph graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph, class MutableGraph>
+void simple_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph>
+VertexListGraph simple_graph_intersection(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
</PRE>
The result graph contains only vertices and edges present both in
@@ -34,6 +42,10 @@
<tt>map<size_t, Vertex> vertices</tt> and <tt>map<size_t,
Edge> edges</tt>, mapping names to descriptors.
+The simple version relies only on vertex naming to identify edges, not
+needing the vertex names and not receiving the <tt>set_edge_label</tt>
+argument.
+
<H3>Where Defined</H3>
<P>
Modified: sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html
==============================================================================
--- sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html (original)
+++ sandbox/SOC/2010/graph/libs/doc/graph_symmetric_difference.html 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -26,12 +26,28 @@
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
template <class VertexListGraph, class MutableGraph>
+void simple_graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph>
+VertexListGraph simple_graph_edge_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph, class MutableGraph>
void graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
template <class VertexListGraph>
VertexListGraph graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph, class MutableGraph>
+void simple_graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph>
+VertexListGraph simple_graph_vertex_symmetric_difference(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
</PRE>
The edge symmetric difference is the graph containing the union of
@@ -47,6 +63,10 @@
<tt>map<size_t, Vertex> vertices</tt> and <tt>map<size_t,
Edge> edges</tt>, mapping names to descriptors.
+The simple version relies only on vertex naming to identify edges, not
+needing the vertex names and not receiving the <tt>set_edge_label</tt>
+argument.
+
<H3>Where Defined</H3>
<P>
Modified: sandbox/SOC/2010/graph/libs/doc/graph_union.html
==============================================================================
--- sandbox/SOC/2010/graph/libs/doc/graph_union.html (original)
+++ sandbox/SOC/2010/graph/libs/doc/graph_union.html 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -26,12 +26,28 @@
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
template <class VertexListGraph, class MutableGraph>
+void simple_graph_union(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph>
+VertexListGraph simple_graph_union(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph, class MutableGraph>
void graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
template <class VertexListGraph>
VertexListGraph graph_sum(const VertexListGraph& g1, const VertexListGraph& g2,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph, class MutableGraph>
+void simple_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
+
+template <class VertexListGraph>
+VertexListGraph simple_graph_sum(const VertexListGraph& g1, const VertexListGraph& g2,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
</PRE>
Union and sum are synonyms. The result graph contains vertices and
@@ -44,6 +60,10 @@
<tt>map<size_t, Vertex> vertices</tt> and <tt>map<size_t,
Edge> edges</tt>, mapping names to descriptors.
+The simple version relies only on vertex naming to identify edges, not
+needing the vertex names and not receiving the <tt>set_edge_label</tt>
+argument.
+
<H3>Where Defined</H3>
<P>
Modified: sandbox/SOC/2010/graph/libs/test/Jamfile
==============================================================================
--- sandbox/SOC/2010/graph/libs/test/Jamfile (original)
+++ sandbox/SOC/2010/graph/libs/test/Jamfile 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -21,5 +21,10 @@
test-suite graph_test
:
[ run property_test.cpp ]
+ [ run complement.cpp ]
[ run disjoint_union.cpp ]
+ [ run join.cpp ]
+ [ run difference.cpp ]
+ [ run intersection.cpp ]
+ [ run sum.cpp ]
;
Added: sandbox/SOC/2010/graph/libs/test/complement.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/complement.cpp 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -0,0 +1,105 @@
+//
+//=======================================================================
+// 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>
+
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/graph/random.hpp>
+
+#include "graph_op_common.hpp"
+
+#include <boost/graph/complement.hpp>
+
+// Vertex and edge names are NOT used by complement
+// They are here only to test how properties are copied
+// and how it works with a custom copier function
+
+using namespace boost;
+using namespace std;
+
+int main(int,char*[])
+{
+ boost::mt19937 gen;
+ gen.seed(uint32_t(time(0)));
+
+ cout << "Complement test" << endl;
+
+ cout << "Graph g: " << endl;
+ Graph2 g;
+ generate_random_graph(g, 4, 10, gen, false, false);
+ auto_name_vertices(g, "g");
+ check_vertex_naming(g);
+ print(g);
+
+ cout << "Complement of g:" << endl;
+ Graph2 gc = graph_complement(g);
+ // check_vertex_naming(gc); // graph_complement don't set graph_label
+ print(gc);
+
+ cout << "Reflexive Complement of g:" << endl;
+ Graph2 gc2 = graph_reflexive_complement(g, vertex_copy(my_vertex_copier_and_setter<Graph2, Graph2>()));
+ check_vertex_naming(gc2); // vertex_copier_and_setter is doing it
+ print(gc2);
+
+ cout << endl;
+
+ cout << "Graph h: " << endl;
+ Graph1 h;
+ generate_random_graph(h, 4, 12, gen, false, true);
+ auto_name_vertices(h, "h");
+ auto_name_edges(h);
+ check_vertex_and_edge_naming(h);
+ print_named_edges(h);
+
+ cout << "Complement of h:" << endl;
+ Graph1 hc1;
+ graph_complement
+ (h, hc1,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_visitor(my_edge_visitor<Graph1>())
+ );
+ check_vertex_and_edge_naming(hc1);
+ print_named_edges(hc1);
+
+ cout << "Reflexive Complement of h:" << endl;
+ Graph1 hc2;
+ graph_reflexive_complement
+ (h, hc2,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_visitor(my_edge_visitor<Graph1>())
+ .vertex_index_map(get(vertex_index, h))
+ );
+ check_vertex_and_edge_naming(hc2);
+ print_named_edges(hc2);
+
+ cout << endl;
+
+ cout << "Testing with different types and other tests..." << endl;
+
+ Graph1 g_other;
+ graph_complement
+ (g, g_other,
+ vertex_copy(my_vertex_copier_and_setter<Graph2, Graph1>(100,10))
+ .edge_visitor(my_edge_visitor<Graph1>()));
+ check_vertex_and_edge_naming(g_other);
+
+ Graph2 h_other;
+ graph_complement
+ (h, h_other,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph2>(10,100)));
+ check_vertex_naming(h_other);
+
+ Graph1 h_out;
+ graph_complement(h, h_out);
+
+ cout << "Passed." << endl;
+ return EXIT_SUCCESS;
+}
Added: sandbox/SOC/2010/graph/libs/test/difference.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/difference.cpp 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -0,0 +1,178 @@
+//
+//=======================================================================
+// 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>
+
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/graph/random.hpp>
+
+#include "graph_op_common.hpp"
+
+#include <boost/graph/difference.hpp>
+
+using namespace boost;
+using namespace std;
+
+int main(int,char*[])
+{
+ boost::mt19937 gen;
+ gen.seed(uint32_t(time(0)));
+
+ Graph1 g1, g2, gd1, gd2, gd3, gd4, gd5, gd6, gd7, gd8, gd9, gd10, gd;
+ Graph2 h1, h2, hd1, hd2, hd3, hd4, hd5, hd6, hd7, hd8, hd9, hd;
+
+ generate_random_graph(g1, 5, 10, gen, false);
+ generate_random_graph(g2, 3, 6, gen, false);
+
+ auto_name_vertices(g1, "g1_", 10, 100);
+ auto_name_edges(g1);
+ auto_name_vertices(g2, "g2_", 11, 200);
+ auto_name_edges(g2);
+
+ cout << "g1:" << endl;
+ print_named_edges(g1);
+ cout << "g2:" << endl;
+ print_named_edges(g2);
+
+ cout << "Difference of g1 and g2:" << endl;
+ graph_difference(g1, g2, gd1);
+ check_vertex_and_edge_naming(gd1);
+ print_named_edges(gd1);
+
+ cout << "Difference of g2 and g1:" << endl;
+ graph_difference(g2, g1, gd2);
+ check_vertex_and_edge_naming(gd2);
+ print_named_edges(gd2);
+
+ cout << "Vertex Symmetric Difference of g1 and g2:" << endl;
+ graph_vertex_symmetric_difference(g1, g2, gd3);
+ check_vertex_and_edge_naming(gd3);
+ print_named_edges(gd3);
+
+ cout << "Vertex Symmetric Difference of g2 and g1:" << endl;
+ graph_vertex_symmetric_difference(g1, g2, gd4);
+ check_vertex_and_edge_naming(gd4);
+ print_named_edges(gd4);
+
+ cout << "Edge Symmetric Difference of g1 and g2:" << endl;
+ graph_edge_symmetric_difference(g1, g2, gd5);
+ check_vertex_and_edge_naming(gd5);
+ print_named_edges(gd5);
+
+ cout << "Edge Symmetric Difference of g2 and g1:" << endl;
+ graph_edge_symmetric_difference(g1, g2, gd6);
+ check_vertex_and_edge_naming(gd6);
+ print_named_edges(gd6);
+
+ cout << "h1:" << endl;
+ print(h1);
+ cout << "h2:" << endl;
+ print(h2);
+
+ cout << "Simple difference of h1 and h2:" << endl;
+ simple_graph_difference(h1, h2, hd1);
+ check_vertex_naming(hd1);
+ print(hd1);
+
+ cout << "Simple vertex symmetric difference of h1 and h2:" << endl;
+ simple_graph_vertex_symmetric_difference(h1, h2, hd2);
+ check_vertex_naming(hd2);
+ print(hd2);
+
+ cout << "Simple edge symmetric difference of h1 and h2:" << endl;
+ simple_graph_edge_symmetric_difference(h1, h2, hd3);
+ check_vertex_naming(hd3);
+ print(hd3);
+
+ cout << "Other tests..." << endl;
+
+ graph_difference(g1, g2, gd7, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_and_edge_naming(gd7);
+
+ graph_vertex_symmetric_difference(g1, g2, gd8, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_and_edge_naming(gd8);
+
+ graph_edge_symmetric_difference(g1, g2, gd9, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_and_edge_naming(gd9);
+
+ simple_graph_difference(h1, h2, hd4, vertex_copy(my_vertex_copier<Graph2, Graph2>(100, 10)));
+ check_vertex_naming(hd4);
+
+ simple_graph_vertex_symmetric_difference(h1, h2, hd5, vertex_copy(my_vertex_copier<Graph2, Graph2>(100, 10)));
+ check_vertex_naming(hd5);
+
+ simple_graph_edge_symmetric_difference(h1, h2, hd6, vertex_copy(my_vertex_copier<Graph2, Graph2>(100, 10)));
+ check_vertex_naming(hd6);
+
+ // For the following tests, this:
+ // check_vertex_and_edge_naming(gd);
+ // was supposed to work as in the early tests. It does inside the call to graph_difference (and symmetric differences)
+ // But after the graph is copied to gd, the edge name mapping does not work properly anymore.
+ // For vertex it is ok: check_vertex_naming(gd)
+
+ gd = graph_difference(g1, g2);
+ check_vertex_naming(gd);
+
+ gd = graph_difference(g1, g2, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gd);
+
+ gd = graph_vertex_symmetric_difference(g1, g2);
+ check_vertex_naming(gd);
+
+ gd = graph_vertex_symmetric_difference(g1, g2, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gd);
+
+ gd = graph_edge_symmetric_difference(g1, g2);
+ check_vertex_naming(gd);
+
+ gd = graph_edge_symmetric_difference(g1, g2, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gd);
+
+
+ hd = simple_graph_difference(h1, h2);
+ check_vertex_naming(hd);
+
+ hd = simple_graph_difference(h1, h2, vertices_merge(my_vertex_merger<Graph2, Graph2>(100, 10)));
+ check_vertex_naming(hd);
+
+ hd = simple_graph_vertex_symmetric_difference(h1, h2);
+ check_vertex_naming(hd);
+
+ hd = simple_graph_vertex_symmetric_difference(h1, h2, vertices_merge(my_vertex_merger<Graph2, Graph2>(100, 10)));
+ check_vertex_naming(hd);
+
+ hd = simple_graph_edge_symmetric_difference(h1, h2);
+ check_vertex_naming(hd);
+
+ hd = simple_graph_edge_symmetric_difference(h1, h2, vertices_merge(my_vertex_merger<Graph2, Graph2>(100, 10)));
+ check_vertex_naming(hd);
+
+ // with different types
+ simple_graph_difference
+ (g1, g2, hd7,
+ vertex_copy(my_vertex_copier<Graph1, Graph2>(100, 10)));
+ check_vertex_naming(hd7);
+
+ simple_graph_vertex_symmetric_difference
+ (g1, g2, hd8,
+ vertex_copy(my_vertex_copier<Graph1, Graph2>(100, 10)));
+ check_vertex_naming(hd8);
+
+ simple_graph_edge_symmetric_difference
+ (g1, g2, hd9,
+ vertex_copy(my_vertex_copier<Graph1, Graph2>(100, 10))
+ .vertices_merge(my_vertex_merger<Graph1, Graph2>(100, 10)));
+ check_vertex_naming(hd9);
+
+ cout << "Passed." << endl;
+
+ return EXIT_SUCCESS;
+}
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-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -8,136 +8,78 @@
//=======================================================================
//
-#include <iostream> // for std::cout
-#include <utility> // for std::pair
-#include <algorithm> // for std::for_each
+#include <iostream>
#include <ctime>
#include <boost/random/mersenne_twister.hpp>
#include <boost/graph/random.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/graph_utility.hpp>
+#include "graph_op_common.hpp"
-#include <boost/graph/copy.hpp>
#include <boost/graph/disjoint_union.hpp>
+// Vertex and edge names are NOT used by disjoint union
+// They are here only to test how properties are copied
+// and how it works with a custom copier function
+
using namespace boost;
using namespace std;
-struct VertexType1
-{
- string name;
- int id;
- int value;
-};
-
-struct VertexType2
-{
- string name;
- int id;
- float value;
-};
-
-typedef adjacency_list < vecS, vecS, bidirectionalS, VertexType1 > Graph1;
-typedef adjacency_list < vecS, vecS, bidirectionalS, VertexType2 > Graph2;
-
-typedef Graph1::vertex_descriptor Vertex1;
-typedef Graph2::vertex_descriptor Vertex2;
-typedef graph_traits<Graph1>::vertex_iterator VertexIterator1;
-typedef graph_traits<Graph2>::vertex_iterator VertexIterator2;
-
-template <typename G1, typename G2>
-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));
- }
-};
-
-template <typename G1, typename G2>
-struct my_copier2 {
- my_copier2(int _add, float _factor)
- : add(_add), factor(_factor) { }
-
- template <typename Vertex1, typename Vertex2>
- 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;
- }
- int add;
- float factor;
-};
-
-
-
-// print a graph showing vertex and edge names
-template <class Graph>
-void print(Graph &g) {
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
- typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
- for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- cout << "Vertex " << index[*vi] << " [name: " << g[*vi].name << ", id: " << g[*vi].id << ", value: " << g[*vi].value << "] -->";
- for (tie(out_i, out_end) = out_edges(*vi, g); out_i != out_end; ++out_i) {
- cout << " " << index[target(*out_i, g)];
- }
- cout << endl;
- }
-}
-
-template <class Graph>
-void auto_label(Graph &g, string name, int value_offset)
-{
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- int id = 0;
-
- for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- stringstream tmp;
- tmp << id;
- g[*vi].name = name + tmp.str();
- g[*vi].id = id;
- g[*vi].value = id*id + value_offset;
- id++;
- }
-}
-
-
int main(int,char*[])
{
boost::mt19937 gen;
gen.seed(uint32_t(time(0)));
Graph1 g1, g2, g3, g4;
- Graph2 h1, h2, h3;
+ Graph2 h;
generate_random_graph(g1, 3, 3, gen, false);
generate_random_graph(g2, 4, 6, gen, false);
- auto_label(g1, "g1_", 100);
- auto_label(g2, "g2_", 200);
+ auto_name_vertices(g1, "g1_", 10, 100);
+ auto_name_vertices(g2, "g2_", 60, 200);
cout << "g1:" << endl;
print(g1);
cout << "g2:" << endl;
print(g2);
+ cout << "Disjoint union of g1 and g2:" << endl;
graph_disjoint_union(g1, g2, g3);
- cout << "g3:" << endl;
print(g3);
- graph_disjoint_union(g1, g2, g4, vertex_copy(my_copier<Graph1, Graph1>()));
- cout << "g4:" << endl;
+ cout << "Disjoint union of g1 and g2:" << endl;
+ graph_disjoint_union(g1, g2, g4, vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>()));
+ check_vertex_naming(g4);
print(g4);
- graph_disjoint_union(g1, g2, g4, vertex_copy(my_copier<Graph1, Graph1>()));
+ cout << "Other tests..." << endl;
+ g4 = graph_disjoint_union(g1, g2);
- graph_disjoint_union(g1, g2, h1, vertex_copy(my_copier2<Graph1, Graph2>(100, 10)));
- cout << "h1:" << endl;
- print(h1);
+ auto_name_edges(g1);
+ auto_name_edges(g2);
+ Graph1 g5;
+ graph_disjoint_union(g1, g2, g5,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_copy(my_edge_copier_and_setter<Graph1, Graph1>()));
+ check_vertex_and_edge_naming(g5);
+
+ g4 = graph_disjoint_union(g1, g2,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_copy(my_edge_copier_and_setter<Graph1, Graph1>()));
+ // This was supposed to be exactly like the g5 example and work with:
+ // check_vertex_and_edge_naming(g4);
+ // and it works just before, inside and at the end of that call to graph_disjoint_union
+ // After the graph is copied to g4, the edge name mapping does not work properly anymore.
+ // For vertex it is ok:
+ check_vertex_naming(g1);
+
+ cout << "Passed." << endl;
+
+ cout << "Disjoint union of g1 and g2: (output with different type + special copy vertex)" << endl;
+ graph_disjoint_union(g1, g2, h, vertex_copy(my_vertex_copier<Graph1, Graph2>(100, 10)));
+ print(h);
return EXIT_SUCCESS;
}
Added: sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/graph_op_common.hpp 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -0,0 +1,225 @@
+//
+//=======================================================================
+// 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 <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+using namespace boost;
+using namespace std;
+
+struct Vertex_Type1;
+struct Edge_Type1;
+struct Graph_Type1;
+
+struct Vertex_Type2;
+struct Graph_Type2;
+
+typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Type1, Edge_Type1, Graph_Type1, listS > Graph1;
+typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Type2, no_property, Graph_Type2, listS > Graph2;
+
+// Hack: Instead of using Graph definition here to define the
+// descriptors, we define them using the same parameters used to
+// define Graph1 and Graph2:
+typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::vertex_descriptor Vertex;
+typedef adjacency_list_traits< vecS, vecS, bidirectionalS, listS>::edge_descriptor Edge;
+
+struct Vertex_Type1 {
+ size_t name;
+ string str;
+ int id;
+ int value;
+};
+struct Edge_Type1 {
+ size_t name;
+};
+struct Graph_Type1 {
+ unordered_map<size_t, Vertex> vertices;
+ unordered_map<size_t, Edge> edges;
+};
+
+struct Vertex_Type2 {
+ size_t name;
+ string str;
+ int id;
+ float value;
+};
+struct Graph_Type2 {
+ unordered_map<size_t, Vertex> vertices;
+};
+
+
+// Vertex copier
+template <typename G1, typename G2>
+struct my_vertex_copier {
+ my_vertex_copier(int _add = 0, float _factor = 1)
+ : add(_add), factor(_factor) { }
+
+ template <typename Vertex1, typename Vertex2>
+ void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) const {
+ // put(get(vertex_all, g2), v2, get(get(vertex_all, g1), v1)); // Only works if the types are the same
+ g2[v2].name = g1[v1].name;
+ g2[v2].str = g1[v1].str;
+ g2[v2].id = g1[v1].id + add;
+ g2[v2].value = g1[v1].value*factor;
+ }
+ int add;
+ float factor;
+};
+
+// Vertex copier that sets the name mapping
+// It is the same as detail::default_vertex_copy + detail::default_set_vertex_label
+template <typename G1, typename G2>
+struct my_vertex_copier_and_setter {
+ my_vertex_copier_and_setter(int _add = 0, float _factor = 1) {
+ copier = my_vertex_copier<G1,G2>(_add,_factor);
+ }
+
+ template <typename Vertex1, typename Vertex2>
+ void operator()(const Vertex1& v1, const G1& g1, Vertex2& v2, G2& g2) const {
+ copier(v1, g1, v2, g2); // does "g2[v2].name = g1[v1].name;"
+ get_property(g2).vertices[ g1[v1].name ] = v2;
+ }
+
+ my_vertex_copier<G1, G2> copier;
+};
+
+// Edge copier that sets the name mapping
+// It is the same as detail::default_edge_copy + detail::default_set_edge_label
+template <typename G1, typename G2>
+struct my_edge_copier_and_setter {
+ 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 {
+ put(get(edge_all, g2), e2, get(get(edge_all, g1), e1));
+ get_property(g2).edges[ g1[e1].name ] = e2;
+ }
+};
+
+// Vertex merger similar to my_vertex_copier
+template <typename InGraph, typename OutGraph>
+struct my_vertex_merger {
+ my_vertex_merger(int _add = 0, float _factor = 1)
+ : add(_add), factor(_factor) { }
+
+ template <typename InVertex, typename OutVertex>
+ void operator()(const InVertex& v1, const InGraph& g1,
+ const InVertex& v2, const InGraph& g2,
+ OutVertex& v_out, OutGraph& g_out) {
+ g_out[v_out].name = g1[v1].name;
+ g_out[v_out].str = g1[v1].str + "+" + g2[v2].str;
+ g_out[v_out].id = g1[v1].id + add;
+ g_out[v_out].value = g1[v1].value*factor;
+ }
+ int add;
+ float factor;
+};
+
+
+
+// edge visitor for new edges
+// set a name for the new edge
+template <typename Graph>
+struct my_edge_visitor {
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ void operator()(const Edge &e, Graph &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).edges[ g[e].name ] = e;
+ }
+};
+
+
+// name vertices
+template <class Graph>
+void auto_name_vertices(Graph &g, string graph_name, size_t start_vertex_name = 10, int value_offset = 0) {
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+ int id = 0; // id == vertex index
+ size_t name = start_vertex_name; // just to make vertex name != vertex index
+ for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+ stringstream tmp;
+ tmp << id;
+ g[*vi].str = graph_name + tmp.str();
+ g[*vi].id = id;
+ g[*vi].value = id*id + value_offset;
+ g[*vi].name = name;
+ get_property(g).vertices[name] = *vi;
+ name++;
+ id++;
+ }
+}
+
+// name edges
+template <class Graph>
+void auto_name_edges(Graph &g, size_t delta_edge_name = 0) {
+ typename graph_traits<Graph>::edge_iterator ei, ei_end;
+ size_t name;
+ for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
+ size_t src = g[source(*ei, g)].name, targ = g[target(*ei, g)].name;
+ name = delta_edge_name + 100 * src + targ;
+ g[*ei].name = name;
+ get_property(g).edges[name] = *ei;
+ }
+}
+
+// check to see if the naming is consistent
+template <class Graph>
+void check_vertex_naming(Graph &g) {
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+ for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+ assert( get_property(g).vertices[ g[*vi].name ] == *vi);
+}
+
+// check to see if the naming is consistent
+template <class Graph>
+void check_vertex_and_edge_naming(Graph &g) {
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+ typename graph_traits<Graph>::edge_iterator ei, ei_end;
+ for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+ assert( get_property(g).vertices[ g[*vi].name ] == *vi);
+ for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
+ assert( get_property(g).edges[ g[*ei].name ] == *ei);
+}
+
+// print a graph showing vertex and edge names
+template <class Graph>
+void print_named_edges(Graph &g) {
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+ typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
+ typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
+ for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+ cout << "Vertex " << index[*vi]
+ << " [name: " << g[*vi].name << ", id: " << g[*vi].id
+ << ", str: " << g[*vi].str << ", value: " << g[*vi].value << "] -->";
+ for (tie(out_i, out_end) = out_edges(*vi, g); out_i != out_end; ++out_i) {
+ // cout << " " << index[target(*out_i, g)] << " (edge " << *out_i << ": " << g[*out_i].name << ");";
+ cout << " [" << index[target(*out_i, g)] << ", name: " << g[*out_i].name << "];";
+ }
+ cout << endl;
+ }
+}
+
+// print a graph showing only vertex names
+template <class Graph>
+void print(Graph &g) {
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
+ typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
+ typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
+ for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+ cout << "Vertex " << index[*vi]
+ << " [name: " << g[*vi].name << ", id: " << g[*vi].id
+ << ", str: " << g[*vi].str << ", value: " << g[*vi].value << "] -->";
+ for (tie(out_i, out_end) = out_edges(*vi, g); out_i != out_end; ++out_i) {
+ cout << " " << index[target(*out_i, g)];
+ }
+ cout << endl;
+ }
+}
Added: sandbox/SOC/2010/graph/libs/test/intersection.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/intersection.cpp 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -0,0 +1,109 @@
+//
+//=======================================================================
+// 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>
+
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/graph/random.hpp>
+
+#include "graph_op_common.hpp"
+
+#include <boost/graph/intersection.hpp>
+
+using namespace boost;
+using namespace std;
+
+int main(int,char*[])
+{
+ boost::mt19937 gen;
+ gen.seed(uint32_t(time(0)));
+
+ Graph1 g1, g2, gi1, gi2, gi3, gi4, gi5, gi;
+ Graph2 h1, h2, hi1, hi2, hi3;
+
+ generate_random_graph(g1, 5, 10, gen, false);
+ generate_random_graph(g2, 3, 6, gen, false);
+
+ auto_name_vertices(g1, "g1_", 10, 100);
+ auto_name_edges(g1);
+ auto_name_vertices(g2, "g2_", 11, 200);
+ auto_name_edges(g2);
+
+ auto_name_vertices(h1, "h1_", 10, 100);
+ auto_name_vertices(h2, "h2_", 11, 200);
+
+ cout << "g1:" << endl;
+ print_named_edges(g1);
+ cout << "g2:" << endl;
+ print_named_edges(g2);
+
+ cout << "Intersection of g1 and g2:" << endl;
+ graph_intersection(g1, g2, gi1);
+ check_vertex_and_edge_naming(gi1);
+ print_named_edges(gi1);
+
+ cout << "Intersection of g2 and g1:" << endl;
+ graph_intersection(g2, g1, gi2);
+ check_vertex_and_edge_naming(gi2);
+ print_named_edges(gi2);
+
+ cout << "h1:" << endl;
+ print(h1);
+ cout << "h2:" << endl;
+ print(h2);
+
+ cout << "Simple intersection of h1 and h2:" << endl;
+ simple_graph_intersection(h1, h2, hi1);
+ check_vertex_naming(hi1);
+ print(hi1);
+
+ cout << "Other tests..." << endl;
+
+ graph_intersection(g1, g2, gi3, vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10)));
+ check_vertex_and_edge_naming(gi3);
+
+ // For the following tests, this:
+ // check_vertex_and_edge_naming(gi);
+ // was supposed to work as in the early tests. It does inside the call to graph_intersection (and symmetric intersections)
+ // But after the graph is copied to gd, the edge name mapping does not work properly anymore.
+ // For vertex it is ok: check_vertex_naming(gi)
+
+ gi = graph_intersection(g1, g2);
+ check_vertex_naming(gi);
+
+ gi = graph_intersection(g1, g2, vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gi);
+
+ // simple_graph_intersection
+
+ simple_graph_intersection(h2, h1, hi2, vertices_merge(my_vertex_merger<Graph2, Graph2>()));
+ check_vertex_naming(hi2);
+
+ simple_graph_intersection(g1, g2, gi4);
+ check_vertex_naming(gi4);
+
+ simple_graph_intersection(g1, g2, gi5, vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gi5);
+
+ gi = simple_graph_intersection(g1, g2);
+ check_vertex_naming(gi);
+
+ gi = simple_graph_intersection(g1, g2, vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gi);
+
+ // with different types
+ simple_graph_intersection(g1, g2, hi3, vertices_merge(my_vertex_merger<Graph1, Graph2>(100, 10)));
+ check_vertex_naming(hi3);
+
+ cout << "Passed." << endl;
+
+ return EXIT_SUCCESS;
+}
Added: sandbox/SOC/2010/graph/libs/test/join.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/join.cpp 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -0,0 +1,89 @@
+//
+//=======================================================================
+// 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>
+
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/graph/random.hpp>
+
+#include "graph_op_common.hpp"
+
+#include <boost/graph/join.hpp>
+
+// Vertex and edge names are NOT used by join
+// They are here only to test how properties are copied
+// and how it works with a custom copier function
+
+using namespace boost;
+using namespace std;
+
+int main(int,char*[])
+{
+ boost::mt19937 gen;
+ gen.seed(uint32_t(time(0)));
+
+ Graph1 g1, g2, g3, g4;
+ Graph2 h;
+
+ generate_random_graph(g1, 3, 3, gen, false);
+ generate_random_graph(g2, 4, 6, gen, false);
+
+ auto_name_vertices(g1, "g1_", 10, 100);
+ auto_name_vertices(g2, "g2_", 60, 200);
+
+ cout << "g1:" << endl;
+ print(g1);
+ cout << "g2:" << endl;
+ print(g2);
+
+ cout << "Join of g1 and g2:" << endl;
+ graph_join(g1, g2, g3);
+ print(g3);
+
+ cout << "Join of g1 and g2:" << endl;
+ graph_join(g1, g2, g4, vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>()));
+ check_vertex_naming(g4);
+ print(g4);
+
+ cout << "Other tests..." << endl;
+
+ g4 = graph_join(g1, g2);
+
+ auto_name_edges(g1);
+ auto_name_edges(g2);
+ Graph1 g5;
+ graph_join(g1, g2, g5,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_copy(my_edge_copier_and_setter<Graph1, Graph1>())
+ .edge_visitor(my_edge_visitor<Graph1>())
+ );
+ check_vertex_and_edge_naming(g5);
+
+ g4 = graph_join(g1, g2,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_copy(my_edge_copier_and_setter<Graph1, Graph1>())
+ .edge_visitor(my_edge_visitor<Graph1>())
+ );
+ // This was supposed to be exactly like the g5 example and work with:
+ // check_vertex_and_edge_naming(g4);
+ // and it works just before, inside and at the end of that call to graph_join
+ // After the graph is copied to g4, the edge name mapping does not work properly anymore.
+ // For vertex it is ok:
+ check_vertex_naming(g1);
+
+ cout << "Passed." << endl;
+
+ cout << "Join of g1 and g2: (output with different type + special copy vertex)" << endl;
+ graph_join(g1, g2, h, vertex_copy(my_vertex_copier<Graph1, Graph2>(100, 10)));
+ print(h);
+
+ return EXIT_SUCCESS;
+}
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-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -8,9 +8,9 @@
//=======================================================================
//
-#include <iostream> // for std::cout
-#include <utility> // for std::pair
-#include <algorithm> // for std::for_each
+#include <iostream>
+#include <utility>
+#include <algorithm>
#include <ctime>
#include <boost/random/mersenne_twister.hpp>
@@ -26,181 +26,85 @@
#include <boost/graph/complement.hpp>
#include <boost/graph/join.hpp>
+#include "graph_op_common.hpp"
+
using namespace boost;
using namespace std;
-struct Vertex_Label;
-struct Edge_Label;
-struct Graph_Label;
-
-typedef adjacency_list < vecS, vecS, bidirectionalS, Vertex_Label, Edge_Label, Graph_Label, listS > Graph;
-
-// 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;
-};
-struct Edge_Label {
- size_t name;
-};
-struct Graph_Label {
- unordered_map<size_t, Vertex> vertices;
- unordered_map<size_t, Edge> edges;
-};
-
-// First look at main()
-// These are auxiliary functions
-
-// Vertex copier that sets the name mapping
-template <typename G1, typename G2>
-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 {
- put(get(vertex_all, g2), v2, get(get(vertex_all, g1), v1));
- get_property(g2).vertices[ g1[v1].name ] = v2;
- }
-};
-
-// 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 {
- put(get(edge_all, g2), e2, get(get(edge_all, g1), e1));
- get_property(g2).edges[ g1[e1].name ] = e2;
- }
-};
-
-// edge visitor for new edges
-template <typename EdgeDescriptor, typename Graph>
-struct my_edge_visitor {
- void operator()(const EdgeDescriptor &e, Graph &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).edges[ g[e].name ] = e;
- }
-};
-
-// name vertices and edges
-template <class Graph>
-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 = 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).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 = 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).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).vertices[ g[*vi].name ] == *vi);
- if ( check_edges )
- for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
- assert( get_property(g).edges[ g[*ei].name ] == *ei);
-}
-
-// print a graph showing vertex and edge names
-template <class Graph>
-void print(Graph &g) {
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
- typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
- for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- cout << "Vertex " << index[*vi] << " [name: " << g[*vi].name << "] -->";
- for (tie(out_i, out_end) = out_edges(*vi, g); out_i != out_end; ++out_i) {
- cout << " " << index[target(*out_i, g)] << " (edge " << *out_i << ": " << g[*out_i].name << ");";
- }
- cout << endl;
- }
-}
-
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_diff, g_sym_diff, g_union, g_join, g_join2;
+ Graph1 g1, g2, g_simple_compl, g_compl, g_rcompl, g_int, g_sum, g_diff, g_sym_diff, g_sym_diff2, g_union, g_join, g_join2;
- generate_random_graph(g1, 3, 5, gen, false);
- generate_random_graph(g2, 4, 10, gen, false);
+ generate_random_graph(g1, 4, 10, gen, false);
+ generate_random_graph(g2, 3, 5, gen, false);
- auto_label(g1);
- auto_label(g2);
+ auto_name_vertices(g1, "g1_", 10, 100);
+ auto_name_edges(g1);
+ auto_name_vertices(g2, "g2_", 10, 200);
+ auto_name_edges(g2);
cout << "Graph 1 (g1):" << endl;
- check(g1);
- print(g1);
+ check_vertex_and_edge_naming(g1);
+ print_named_edges(g1);
cout << endl;
cout << "Graph 2 (g2):" << endl;
- check(g2);
- print(g2);
+ check_vertex_and_edge_naming(g2);
+ print_named_edges(g2);
cout << endl;
cout << "Complement of g1:" << endl;
graph_complement(g1, g_simple_compl); // ignore name mapping (but copy vertex properties)
- // check(g_compl); // graph_complement don't set graph_label
- print(g_simple_compl);
+ // check_vertex_and_edge_naming(g_compl); // graph_complement don't set graph_label
+ print_named_edges(g_simple_compl);
cout << endl;
cout << "Complement of g1:" << endl;
- my_vertex_copier<Graph, Graph> c;
- g_compl = graph_complement(g1, vertex_copy(c));
- 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);
+ g_compl = graph_complement(g1, vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>()));
+ check_vertex_naming(g_compl); // graph_complement don't set edge names in graph_label, but my_vertex_copier do it for vertices
+ print_named_edges(g_compl);
cout << endl;
cout << "Reflexive complement of g1:" << endl;
- graph_reflexive_complement(g1, g_rcompl, vertex_copy(c).edge_visitor(my_edge_visitor<Edge, Graph>()));
- check(g_rcompl);
- print(g_rcompl);
+ graph_reflexive_complement
+ (g1, g_rcompl,
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_visitor(my_edge_visitor<Graph1>()));
+ check_vertex_and_edge_naming(g_rcompl);
+ print_named_edges(g_rcompl);
cout << endl;
cout << "Intersection of g1 and g2:" << endl;
graph_intersection(g1, g2, g_int);
- check(g_int);
- print(g_int);
+ check_vertex_and_edge_naming(g_int);
+ print_named_edges(g_int);
cout << endl;
cout << "Sum of g1 and g2:" << endl;
graph_sum(g1, g2, g_sum);
- check(g_sum);
- print(g_sum);
+ check_vertex_and_edge_naming(g_sum);
+ print_named_edges(g_sum);
cout << endl;
cout << "Difference of g1 and g2:" << endl;
graph_difference(g1, g2, g_diff);
- check(g_diff);
- print(g_diff);
+ check_vertex_and_edge_naming(g_diff);
+ print_named_edges(g_diff);
cout << endl;
cout << "Vertex Symmetric Difference of g1 and g2:" << endl;
graph_vertex_symmetric_difference(g1, g2, g_sym_diff);
- check(g_sym_diff);
- print(g_sym_diff);
+ check_vertex_and_edge_naming(g_sym_diff);
+ print_named_edges(g_sym_diff);
+ cout << endl;
+
+ cout << "Edge Symmetric Difference of g1 and g2:" << endl;
+ graph_vertex_symmetric_difference(g1, g2, g_sym_diff2);
+ check_vertex_and_edge_naming(g_sym_diff2);
+ print_named_edges(g_sym_diff2);
cout << endl;
// For union and join, the vertex and edge set are considered to be disjoint.
@@ -208,22 +112,23 @@
cout << "Disjoint union of g1 and g2:" << endl;
graph_disjoint_union(g1, g2, g_union);
- print(g_union);
+ print_named_edges(g_union);
cout << endl;
cout << "Join of g1 and g2:" << endl;
graph_join(g1, g2, g_join);
- print(g_join);
+ print_named_edges(g_join);
cout << endl;
cout << "Another join of g1 and g2: (g2 with new labels)" << endl;
- auto_label(g2, 20, 200);
+ auto_name_vertices(g2, "g2_", 20, 200);
+ auto_name_edges(g2);
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);
+ vertex_copy(my_vertex_copier_and_setter<Graph1, Graph1>())
+ .edge_copy(my_edge_copier_and_setter<Graph1, Graph1>())
+ .edge_visitor(my_edge_visitor<Graph1>()));
+ check_vertex_and_edge_naming(g_join2); // passes the test because we are using our own functions
+ print_named_edges(g_join2);
// cout << endl;
return EXIT_SUCCESS;
Added: sandbox/SOC/2010/graph/libs/test/sum.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/libs/test/sum.cpp 2010-08-31 01:30:11 EDT (Tue, 31 Aug 2010)
@@ -0,0 +1,120 @@
+//
+//=======================================================================
+// 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>
+
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/graph/random.hpp>
+
+#include "graph_op_common.hpp"
+
+#include <boost/graph/sum.hpp>
+
+using namespace boost;
+using namespace std;
+
+int main(int,char*[])
+{
+ boost::mt19937 gen;
+ gen.seed(uint32_t(time(0)));
+
+ Graph1 g1, g2, gs1, gs2, gs3, gs4, gs5, gs6, gs;
+ Graph2 h1, h2, hs1, hs2, hs3;
+
+ generate_random_graph(g1, 5, 10, gen, false);
+ generate_random_graph(g2, 3, 6, gen, false);
+
+ auto_name_vertices(g1, "g1_", 10, 100);
+ auto_name_edges(g1);
+ auto_name_vertices(g2, "g2_", 11, 200);
+ auto_name_edges(g2);
+
+ auto_name_vertices(h1, "h1_", 10, 100);
+ auto_name_vertices(h2, "h2_", 11, 200);
+
+ cout << "g1:" << endl;
+ print_named_edges(g1);
+ cout << "g2:" << endl;
+ print_named_edges(g2);
+
+ cout << "Sum of g1 and g2:" << endl;
+ graph_sum(g1, g2, gs1);
+ check_vertex_and_edge_naming(gs1);
+ print_named_edges(gs1);
+
+ cout << "Sum of g2 and g1:" << endl;
+ graph_sum(g2, g1, gs2);
+ check_vertex_and_edge_naming(gs2);
+ print_named_edges(gs2);
+
+ cout << "h1:" << endl;
+ print(h1);
+ cout << "h2:" << endl;
+ print(h2);
+
+ cout << "Simple union of h1 and h2:" << endl;
+ simple_graph_sum(h1, h2, hs1);
+ check_vertex_naming(hs1);
+ print(hs1);
+
+ cout << "Other tests..." << endl;
+
+ graph_sum(g1, g2, gs3, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_and_edge_naming(gs3);
+
+ graph_sum(g1, g2, gs4,
+ vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10))
+ .vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10))
+ );
+ check_vertex_and_edge_naming(gs4);
+ // print_named_edges(gs4);
+
+ // For the following tests, this:
+ // check_vertex_and_edge_naming(gs);
+ // was supposed to work as in the early tests. It does inside the call to graph_sum
+ // But after the graph is copied to gd, the edge name mapping does not work properly anymore.
+ // For vertex it is ok: check_vertex_naming(gs)
+
+ gs = graph_sum(g1, g2);
+ check_vertex_naming(gs);
+
+ gs = graph_sum(g1, g2, vertex_copy(my_vertex_copier<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gs);
+
+ // simple_graph_sum
+
+ simple_graph_sum(h2, h1, hs2, vertices_merge(my_vertex_merger<Graph2, Graph2>()));
+ check_vertex_naming(hs2);
+
+ simple_graph_sum(g1, g2, gs5);
+ check_vertex_naming(gs5);
+
+ simple_graph_sum(g1, g2, gs6, vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gs6);
+
+ gs = simple_graph_sum(g1, g2);
+ check_vertex_naming(gs);
+
+ gs = simple_graph_sum(g1, g2, vertices_merge(my_vertex_merger<Graph1, Graph1>(100, 10)));
+ check_vertex_naming(gs);
+
+ // with different types
+ simple_graph_sum
+ (g1, g2, hs3,
+ vertex_copy(my_vertex_copier<Graph1, Graph2>(100, 10))
+ .vertices_merge(my_vertex_merger<Graph1, Graph2>(100, 10))
+ );
+ check_vertex_naming(hs3);
+
+ cout << "Passed." << endl;
+
+ return EXIT_SUCCESS;
+}
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