Subject: [Boost-commit] svn:boost r64559 - in sandbox/SOC/2010/graph: . boost/graph libs/test
From: dbarbosa_at_[hidden]
Date: 2010-08-03 05:20:45
Author: dbarbosa
Date: 2010-08-03 05:20:44 EDT (Tue, 03 Aug 2010)
New Revision: 64559
URL: http://svn.boost.org/trac/boost/changeset/64559
Log:
added named parameters to graph_complement
added named parameters description
Text files modified:
sandbox/SOC/2010/graph/algorithms.org | 37 ++++++++++++++++++
sandbox/SOC/2010/graph/boost/graph/complement.hpp | 78 ++++++++++++++++++++++++++++++---------
sandbox/SOC/2010/graph/libs/test/property_test.cpp | 42 ++++++++++++++++++--
3 files changed, 133 insertions(+), 24 deletions(-)
Modified: sandbox/SOC/2010/graph/algorithms.org
==============================================================================
--- sandbox/SOC/2010/graph/algorithms.org (original)
+++ sandbox/SOC/2010/graph/algorithms.org 2010-08-03 05:20:44 EDT (Tue, 03 Aug 2010)
@@ -16,6 +16,42 @@
NetworkX (python)
** http://www.jgrapht.org/javadoc/org/jgrapht/graph/GraphUnion.html
JGraphT (Java)
+* Parameters/Named parameters
+ Some of the algorithms needs a "labeled graph" (e.g. intersection)
+ to identify vertices and edges that appears in two (or more) input
+ graphs.
+** Named Parameters
+*** vertex_copy
+*** edge_copy
+*** vertex_merge_copy
+ Let v1 and v2 be vertices in g1 and g2.
+ If we identify that v1 == v2 (using the label) and this vertex
+ should be in the output, we should copy this vertex, but there are
+ two inputs.
+ This function will be like vertex_copy but taking two inputs. The
+ default behaviour will be use vertex_copier for the first input
+ and ignore the second.
+*** edge_merge_copy
+ same as above
+*** orig2out (orig_to_copy)
+ For algorithms with one input. The name orig_to_copy is used in
+ copy, transitive closure, transpose... Should we continue using
+ it?
+ To think: How we do with disjoint union and join? They
+ have two disjoint graphs in the input, so they should had two
+ orig_to_copy, one for each input.
+*** vertex_index_map
+ Already in use by copy, transitive closure, etc. I still need to
+ understand exactly why we need it and where we need it.
+*** create_new_edge (edge visitor ?)
+ My suggestion. When we create a brand new edge, we could call this
+ function. The default behaviour would be do nothing. This can be
+ useful in complement (all edges are new), join (which copy all
+ edges from the inputs but also create new ones), cartesian
+ product, k-th power, closures and reductions, etc.
+*** create_new_vertex (vertex visitor ?)
+ Same as above. Probably none of these algorithms creates brand new
+ vertices.
* Algorithms
** Union (aka Sum)
*** Methods
@@ -279,6 +315,7 @@
(why and where is it needed?)
- http://www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml
** TODO Transitive Reduction
+ Implemented (sort of beta?)
*** Methods
- void graph_transitive_reduction(g_in, g_out)
- graph graph_transitive_reduction(g_in)
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-03 05:20:44 EDT (Tue, 03 Aug 2010)
@@ -15,29 +15,28 @@
#include <utility>
#include <boost/graph/global_vertex_mapping.hpp>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/copy.hpp>
namespace boost {
namespace detail {
- template <class VertexListGraph, class MutableGraph>
- void graph_complement_impl(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
+ template <class Graph, class MutableGraph,
+ typename CopyVertex,
+ typename Orig2OutVertexIndexMap>
+ void graph_complement_impl(const Graph& g_in, MutableGraph& g_out,
+ CopyVertex copy_vertex, Orig2OutVertexIndexMap orig2out,
+ bool reflexive)
{
- 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(g_in, g_out);
-
- auto & gl_in = get_property(g_in, graph_label).hack->vertices;
- auto & gl_out = get_property(g_out, graph_label).hack->vertices;
-
- typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
- typename graph_traits < VertexListGraph >::vertex_iterator ui, ui_end;
+ typename graph_traits < Graph >::vertex_iterator vi, vi_end;
+ typename graph_traits < Graph >::vertex_iterator ui, ui_end;
// copy vertices from g_in
for (tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
OutVertex new_v = add_vertex(g_out);
+ put(orig2out, *vi, new_v);
copy_vertex(*vi, new_v);
- assert( g_out[new_v].name == g_in[*vi].name); // copy_vertex already did it
- gl_out[ g_in[*vi].name ] = new_v;
}
// create edges
@@ -46,7 +45,9 @@
if ( (reflexive || ui != vi) && edge(*ui, *vi, g_in).second == false ) {
typename graph_traits<MutableGraph>::edge_descriptor new_e;
bool inserted;
- boost::tie(new_e, inserted) = add_edge(*ui, *vi, g_out);
+ boost::tie(new_e, inserted) = add_edge(get(orig2out, *ui),
+ get(orig2out, *vi),
+ g_out);
assert(inserted);
}
}
@@ -54,18 +55,57 @@
}
}// namespace detail
- template <class VertexListGraph, class MutableGraph>
- void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+ template <typename VertexListGraph, typename MutableGraph>
+ void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out, bool reflexive)
{
- detail::graph_complement_impl(g_in, g_out, false);
+ typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_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),
+ make_iterator_property_map(orig2out.begin(),
+ get(vertex_index, g_in), orig2out[0]),
+ reflexive
+ );
}
- template <class VertexListGraph, class MutableGraph>
- void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+ template <typename VertexListGraph, typename MutableGraph,
+ class P, class T, class R>
+ void graph_complement(const VertexListGraph& g_in, MutableGraph& g_out,
+ const bgl_named_params<P, T, R>& params, bool reflexive)
{
- detail::graph_complement_impl(g_in, g_out, true);
+ typename std::vector<T>::size_type n;
+ n = is_default_param(get_param(params, orig_to_copy_t()))
+ ? num_vertices(g_in) : 1;
+ std::vector<BOOST_DEDUCED_TYPENAME graph_traits<MutableGraph>::vertex_descriptor>
+ orig2out(n);
+
+ 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]),
+ reflexive
+ );
}
+// template <typename VertexListGraph, typename MutableGraph>
+// void graph_reflexive_complement(const VertexListGraph& g_in, MutableGraph& g_out)
+// {
+// typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_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),
+// make_iterator_property_map(orig2out.begin(),
+// get(vertex_index, g_in), orig2out[0]),
+// true
+// );
+// }
+
} // namespace boost
#endif // BOOST_GRAPH_COMPLEMENT_HPP
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-03 05:20:44 EDT (Tue, 03 Aug 2010)
@@ -42,6 +42,31 @@
unordered_map<size_t, Edge> edges;
};
+
+
+// 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));
+ 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;
+};
+
+
// name vertices and edges
template <class Graph>
void auto_label(Graph &g) {
@@ -119,7 +144,7 @@
boost::mt19937 gen;
gen.seed(uint32_t(time(0)));
- Graph g1, g2, g_compl, g_rcompl, g_int, g_sum, g_union, g_join;
+ 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);
@@ -147,15 +172,22 @@
cout << endl;
cout << "Complement of g1:" << endl;
- graph_complement(g1, g_compl);
- check(g_compl, false); // graph_complement is not setting edge names (yet ?)
+ graph_complement(g1, g_simple_compl, false); // ignore name mapping (but copy vertex properties)
+ print(g_simple_compl);
+ cout << endl;
+
+ cout << "Complement of g1:" << endl;
+ my_copier<Graph, Graph> c(g1, g_compl);
+ graph_complement(g1, g_compl, vertex_copy(c), false);
+ check(g_compl, false); // graph_complement don't set edge names
print(g_compl);
cout << endl;
cout << "Reflexive complement of g1:" << endl;
- graph_reflexive_complement(g1, g_rcompl);
- check(g_rcompl, false); // graph_reflexive_complement is not setting edge names (yet ?)
+ my_copier<Graph, Graph> cc(g1, g_rcompl);
+ graph_complement(g1, g_rcompl, vertex_copy(cc), true);
print(g_rcompl);
+ check(g_rcompl, false); // graph_complement don't set edge names
cout << endl;
cout << "Intersection of g1 and g2:" << endl;