|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r84299 - in branches/release: boost/graph boost/graph/detail boost/graph/distributed boost/graph/property_maps boost/property_map libs/graph libs/graph/doc libs/graph/example libs/graph/src libs/graph/test libs/property_map libs/property_map/doc libs/property_map/example libs/property_map/test
From: jewillco_at_[hidden]
Date: 2013-05-16 11:38:08
Author: jewillco
Date: 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
New Revision: 84299
URL: http://svn.boost.org/trac/boost/changeset/84299
Log:
Merged Boost.Graph, Boost.Graph.Parallel, and Boost.PropertyMap changes from trunk
Added:
branches/release/boost/graph/maximum_adjacency_search.hpp
- copied unchanged from r83410, /trunk/boost/graph/maximum_adjacency_search.hpp
branches/release/boost/property_map/compose_property_map.hpp
- copied unchanged from r83037, /trunk/boost/property_map/compose_property_map.hpp
branches/release/libs/graph/doc/maximum_adjacency_search.html
- copied unchanged from r83410, /trunk/libs/graph/doc/maximum_adjacency_search.html
branches/release/libs/graph/test/mas_test.cpp
- copied, changed from r83410, /trunk/libs/graph/test/mas_test.cpp
branches/release/libs/property_map/doc/compose_property_map.html
- copied, changed from r83037, /trunk/libs/property_map/doc/compose_property_map.html
branches/release/libs/property_map/example/compose_property_map_example.cpp
- copied unchanged from r83037, /trunk/libs/property_map/example/compose_property_map_example.cpp
branches/release/libs/property_map/test/compose_property_map_test.cpp
- copied unchanged from r83037, /trunk/libs/property_map/test/compose_property_map_test.cpp
Properties modified:
branches/release/boost/graph/ (props changed)
branches/release/boost/graph/adjacency_list.hpp (props changed)
branches/release/boost/graph/astar_search.hpp (contents, props changed)
branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp (props changed)
branches/release/boost/graph/compressed_sparse_row_graph.hpp (props changed)
branches/release/boost/graph/detail/ (props changed)
branches/release/boost/graph/detail/adjacency_list.hpp (contents, props changed)
branches/release/boost/graph/detail/d_ary_heap.hpp (props changed)
branches/release/boost/graph/detail/labeled_graph_traits.hpp (props changed)
branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp (props changed)
branches/release/boost/graph/directed_graph.hpp (props changed)
branches/release/boost/graph/distributed/selector.hpp (props changed)
branches/release/boost/graph/graph_concepts.hpp (props changed)
branches/release/boost/graph/graph_traits.hpp (props changed)
branches/release/boost/graph/graphml.hpp (props changed)
branches/release/boost/graph/kamada_kawai_spring_layout.hpp (props changed)
branches/release/boost/graph/labeled_graph.hpp (props changed)
branches/release/boost/graph/metric_tsp_approx.hpp (props changed)
branches/release/boost/graph/named_graph.hpp (contents, props changed)
branches/release/boost/graph/properties.hpp (props changed)
branches/release/boost/graph/property_maps/constant_property_map.hpp (props changed)
branches/release/boost/graph/reverse_graph.hpp (contents, props changed)
branches/release/boost/graph/tiernan_all_cycles.hpp (props changed)
branches/release/boost/graph/undirected_graph.hpp (props changed)
branches/release/boost/graph/vf2_sub_graph_iso.hpp (contents, props changed)
branches/release/boost/property_map/ (props changed)
branches/release/libs/graph/ (props changed)
branches/release/libs/graph/doc/ (props changed)
branches/release/libs/graph/doc/astar_search.html (props changed)
branches/release/libs/graph/doc/graph_concepts.html (props changed)
branches/release/libs/graph/doc/push_relabel_max_flow.html (props changed)
branches/release/libs/graph/doc/read_graphml.html (props changed)
branches/release/libs/graph/doc/read_graphml.rst (props changed)
branches/release/libs/graph/doc/small_world_generator.html (props changed)
branches/release/libs/graph/doc/table_of_contents.html (contents, props changed)
branches/release/libs/graph/doc/vf2_sub_graph_iso.html (contents, props changed)
branches/release/libs/graph/example/ (props changed)
branches/release/libs/graph/example/Jamfile.v2 (contents, props changed)
branches/release/libs/graph/example/astar-cities.cpp (contents, props changed)
branches/release/libs/graph/example/undirected_adjacency_list.cpp (props changed)
branches/release/libs/graph/example/undirected_adjacency_list.expected (props changed)
branches/release/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (props changed)
branches/release/libs/graph/src/graphml.cpp (contents, props changed)
branches/release/libs/graph/test/ (props changed)
branches/release/libs/property_map/ (props changed)
Text files modified:
branches/release/boost/graph/astar_search.hpp | 8
branches/release/boost/graph/detail/adjacency_list.hpp | 5
branches/release/boost/graph/detail/histogram_sort.hpp | 2
branches/release/boost/graph/dijkstra_shortest_paths.hpp | 6
branches/release/boost/graph/distributed/adjacency_list.hpp | 3
branches/release/boost/graph/distributed/mpi_process_group.hpp | 2
branches/release/boost/graph/distributed/named_graph.hpp | 6
branches/release/boost/graph/isomorphism.hpp | 22 +
branches/release/boost/graph/johnson_all_pairs_shortest.hpp | 4
branches/release/boost/graph/named_function_params.hpp | 10 +
branches/release/boost/graph/named_graph.hpp | 16 +
branches/release/boost/graph/r_c_shortest_paths.hpp | 6
branches/release/boost/graph/reverse_graph.hpp | 9
branches/release/boost/graph/rmat_graph_generator.hpp | 18 +-
branches/release/boost/graph/sloan_ordering.hpp | 24 +-
branches/release/boost/graph/stoer_wagner_min_cut.hpp | 339 ++++++++++++++++++++-------------------
branches/release/boost/graph/vf2_sub_graph_iso.hpp | 298 ++++++++++++++++++++++++----------
branches/release/libs/graph/doc/johnson_all_pairs_shortest.html | 31 +-
branches/release/libs/graph/doc/r_c_shortest_paths.html | 2
branches/release/libs/graph/doc/table_of_contents.html | 1
branches/release/libs/graph/doc/vf2_sub_graph_iso.html | 36 ++-
branches/release/libs/graph/example/Jamfile.v2 | 4
branches/release/libs/graph/example/astar-cities.cpp | 2
branches/release/libs/graph/example/dijkstra-example-listS.cpp | 26 ---
branches/release/libs/graph/example/dijkstra-example.cpp | 24 --
branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp | 25 --
branches/release/libs/graph/example/matching_example.cpp | 1
branches/release/libs/graph/src/graphml.cpp | 4
branches/release/libs/graph/test/Jamfile.v2 | 1
branches/release/libs/graph/test/astar_search_test.cpp | 19 +
branches/release/libs/graph/test/mas_test.cpp | 2
branches/release/libs/graph/test/vf2_sub_graph_iso_test.cpp | 5
branches/release/libs/property_map/doc/compose_property_map.html | 20 +
branches/release/libs/property_map/doc/property_map.html | 1
branches/release/libs/property_map/test/Jamfile.v2 | 1
35 files changed, 567 insertions(+), 416 deletions(-)
Modified: branches/release/boost/graph/astar_search.hpp
==============================================================================
--- branches/release/boost/graph/astar_search.hpp (original)
+++ branches/release/boost/graph/astar_search.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -438,7 +438,7 @@
typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
distance_map_type;
typedef typename boost::property_traits<distance_map_type>::value_type D;
- const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+ const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
astar_search
(g, s, h,
@@ -480,7 +480,7 @@
typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
distance_map_type;
typedef typename boost::property_traits<distance_map_type>::value_type D;
- const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+ const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
astar_search_tree
(g, s, h,
@@ -512,7 +512,7 @@
arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
weight_map_type;
typedef typename boost::property_traits<weight_map_type>::value_type D;
- const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+ const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
astar_search_no_init
(g, s, h,
arg_pack[_visitor | make_astar_visitor(null_visitor())],
@@ -545,7 +545,7 @@
arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
weight_map_type;
typedef typename boost::property_traits<weight_map_type>::value_type D;
- const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+ const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
astar_search_no_init_tree
(g, s, h,
arg_pack[_visitor | make_astar_visitor(null_visitor())],
Modified: branches/release/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/detail/adjacency_list.hpp (original)
+++ branches/release/boost/graph/detail/adjacency_list.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -17,6 +17,7 @@
#include <boost/detail/workaround.hpp>
#include <boost/operators.hpp>
#include <boost/property_map/property_map.hpp>
+#include <boost/pending/container_traits.hpp>
#include <boost/range/irange.hpp>
#include <boost/graph/graph_traits.hpp>
#include <memory>
@@ -1903,7 +1904,7 @@
{
typedef typename Config::stored_vertex stored_vertex;
Derived& g = static_cast<Derived&>(g_);
- g.removing_vertex(u);
+ g.removing_vertex(u, boost::graph_detail::iterator_stability(g_.m_vertices));
stored_vertex* su = (stored_vertex*)u;
g.m_vertices.erase(su->m_position);
delete su;
@@ -2203,7 +2204,7 @@
{
typedef typename Config::directed_category Cat;
Graph& g = static_cast<Graph&>(g_);
- g.removing_vertex(v);
+ g.removing_vertex(v, boost::graph_detail::iterator_stability(g_.m_vertices));
detail::remove_vertex_dispatch(g, v, Cat());
}
// O(1)
Modified: branches/release/boost/graph/detail/histogram_sort.hpp
==============================================================================
--- branches/release/boost/graph/detail/histogram_sort.hpp (original)
+++ branches/release/boost/graph/detail/histogram_sort.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -69,7 +69,7 @@
// m_rowstart
EdgeIndex start_of_this_row = 0;
starts[0] = start_of_this_row;
- for (vertices_size_type i = 1; i <= numkeys; ++i) {
+ for (vertices_size_type i = 1; i < numkeys + 1; ++i) {
start_of_this_row += starts[i];
starts[i] = start_of_this_row;
}
Modified: branches/release/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/dijkstra_shortest_paths.hpp (original)
+++ branches/release/boost/graph/dijkstra_shortest_paths.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -159,7 +159,11 @@
void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
template <class Edge, class Graph>
void examine_edge(Edge e, Graph& g) {
- if (m_compare(get(m_weight, e), m_zero))
+ // Comparison needs to be more complicated because distance and weight
+ // types may not be the same; see bug 8398
+ // (https://svn.boost.org/trac/boost/ticket/8398)
+ D source_dist = get(m_distance, source(e, g));
+ if (m_compare(m_combine(source_dist, get(m_weight, e)), source_dist))
boost::throw_exception(negative_edge());
m_vis.examine_edge(e, g);
}
Modified: branches/release/boost/graph/distributed/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjacency_list.hpp (original)
+++ branches/release/boost/graph/distributed/adjacency_list.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -37,6 +37,7 @@
#include <boost/graph/parallel/algorithm.hpp>
#include <boost/graph/distributed/selector.hpp>
#include <boost/graph/parallel/process_group.hpp>
+#include <boost/pending/container_traits.hpp>
// Callbacks
#include <boost/function/function2.hpp>
@@ -3427,7 +3428,7 @@
typedef typename graph_type::named_graph_mixin named_graph_mixin;
BOOST_ASSERT(u.owner == g.processor());
static_cast<named_graph_mixin&>(static_cast<graph_type&>(g))
- .removing_vertex(u);
+ .removing_vertex(u, boost::graph_detail::iterator_stability(g.base().m_vertices));
g.distribution().clear();
remove_vertex(u.local, g.base());
}
Modified: branches/release/boost/graph/distributed/mpi_process_group.hpp
==============================================================================
--- branches/release/boost/graph/distributed/mpi_process_group.hpp (original)
+++ branches/release/boost/graph/distributed/mpi_process_group.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -416,7 +416,7 @@
void synchronize() const;
- operator bool() { return impl_; }
+ operator bool() { return bool(impl_); }
mpi_process_group base() const;
Modified: branches/release/boost/graph/distributed/named_graph.hpp
==============================================================================
--- branches/release/boost/graph/distributed/named_graph.hpp (original)
+++ branches/release/boost/graph/distributed/named_graph.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -267,7 +267,8 @@
/// Notify the named_graph that we are removing the given
/// vertex. This is a no-op.
- void removing_vertex(Vertex) { }
+ template <typename VertexIterStability>
+ void removing_vertex(Vertex, VertexIterStability) { }
/// Notify the named_graph that we are clearing the graph
void clearing_graph() { }
@@ -1211,7 +1212,8 @@
/// Notify the named_graph that we are removing the given
/// vertex. This is a no-op.
- void removing_vertex(Vertex) { }
+ template <typename VertexIterStability>
+ void removing_vertex(Vertex, VertexIterStability) { }
/// Notify the named_graph that we are clearing the graph
void clearing_graph() { }
Modified: branches/release/boost/graph/isomorphism.hpp
==============================================================================
--- branches/release/boost/graph/isomorphism.hpp (original)
+++ branches/release/boost/graph/isomorphism.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -222,7 +222,7 @@
recur:
if (iter != ordered_edges.end()) {
i = source(*iter, G1);
- j = target(*iter, G2);
+ j = target(*iter, G1);
if (dfs_num[i] > dfs_num_k) {
G2_verts = vertices(G2);
while (G2_verts.first != G2_verts.second) {
@@ -310,8 +310,8 @@
if (k.empty()) return false;
const match_continuation& this_k = k.back();
switch (this_k.position) {
- case match_continuation::pos_G2_vertex_loop: {G2_verts = this_k.G2_verts; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*G2_verts.first] = false; i = source(*iter, G1); j = target(*iter, G2); goto G2_loop_k;}
- case match_continuation::pos_fi_adj_loop: {fi_adj = this_k.fi_adj; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*fi_adj.first] = false; i = source(*iter, G1); j = target(*iter, G2); goto fi_adj_loop_k;}
+ case match_continuation::pos_G2_vertex_loop: {G2_verts = this_k.G2_verts; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*G2_verts.first] = false; i = source(*iter, G1); j = target(*iter, G1); goto G2_loop_k;}
+ case match_continuation::pos_fi_adj_loop: {fi_adj = this_k.fi_adj; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*fi_adj.first] = false; i = source(*iter, G1); j = target(*iter, G1); goto fi_adj_loop_k;}
case match_continuation::pos_dfs_num: {k.pop_back(); goto return_point_false;}
default: {
BOOST_ASSERT(!"Bad position");
@@ -378,6 +378,14 @@
const Graph& m_g;
};
+ // Count actual number of vertices, even in filtered graphs.
+ template <typename Graph>
+ size_t count_vertices(const Graph& g)
+ {
+ size_t n = 0;
+ BGL_FORALL_VERTICES_T(v, g, Graph) {(void)v; ++n;}
+ return n;
+ }
template <typename Graph1, typename Graph2, typename IsoMapping,
typename Invariant1, typename Invariant2,
@@ -392,7 +400,7 @@
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> ));
BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> ));
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> ));
+ //BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> ));
typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
@@ -407,7 +415,7 @@
// Property map requirements
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<IsoMapping, vertex1_t> ));
typedef typename property_traits<IsoMapping>::value_type IsoMappingValue;
- BOOST_STATIC_ASSERT((is_same<IsoMappingValue, vertex2_t>::value));
+ BOOST_STATIC_ASSERT((is_convertible<IsoMappingValue, vertex2_t>::value));
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_t> ));
typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
@@ -417,9 +425,9 @@
typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value));
- if (num_vertices(G1) != num_vertices(G2))
+ if (count_vertices(G1) != count_vertices(G2))
return false;
- if (num_vertices(G1) == 0 && num_vertices(G2) == 0)
+ if (count_vertices(G1) == 0 && count_vertices(G2) == 0)
return true;
detail::isomorphism_algo<Graph1, Graph2, IsoMapping, Invariant1,
Modified: branches/release/boost/graph/johnson_all_pairs_shortest.hpp
==============================================================================
--- branches/release/boost/graph/johnson_all_pairs_shortest.hpp (original)
+++ branches/release/boost/graph/johnson_all_pairs_shortest.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -113,7 +113,7 @@
for (boost::tie(e, e_end) = edges(g2); e != e_end; ++e) {
typename Traits2::vertex_descriptor a = source(*e, g2),
b = target(*e, g2);
- put(w_hat, *e, combine(get(w, *e), (get(h, a) - get(h, b))));
+ put(w_hat, *e, combine((get(h, a) - get(h, b)), get(w, *e)));
}
for (boost::tie(u, u_end) = vertices(g2); u != u_end; ++u) {
dijkstra_visitor<> dvis;
@@ -121,7 +121,7 @@
(g2, *u, pred, d, w_hat, id2, compare, combine, inf, zero,dvis);
for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) {
if (*u != s && *v != s) {
- D[get(id2, *u)-1][get(id2, *v)-1] = combine(get(d, *v), (get(h, *v) - get(h, *u)));
+ D[get(id2, *u)-1][get(id2, *v)-1] = combine((get(h, *v) - get(h, *u)), get(d, *v));
}
}
}
Modified: branches/release/boost/graph/named_function_params.hpp
==============================================================================
--- branches/release/boost/graph/named_function_params.hpp (original)
+++ branches/release/boost/graph/named_function_params.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -12,6 +12,7 @@
#include <functional>
#include <vector>
+#include <boost/limits.hpp>
#include <boost/ref.hpp>
#include <boost/utility/result_of.hpp>
#include <boost/preprocessor.hpp>
@@ -718,6 +719,15 @@
result_type operator()() const {return get_default_starting_vertex(g);}
};
+ // Wrapper to avoid instantiating numeric_limits when users provide distance_inf value manually
+ template <typename T>
+ struct get_max {
+ T operator()() const {
+ return (std::numeric_limits<T>::max)();
+ }
+ typedef T result_type;
+ };
+
} // namespace detail
} // namespace boost
Modified: branches/release/boost/graph/named_graph.hpp
==============================================================================
--- branches/release/boost/graph/named_graph.hpp (original)
+++ branches/release/boost/graph/named_graph.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -11,6 +11,7 @@
#define BOOST_GRAPH_NAMED_GRAPH_HPP
#include <boost/config.hpp>
+#include <boost/static_assert.hpp>
#include <boost/functional/hash.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
@@ -19,9 +20,11 @@
#include <boost/multi_index_container.hpp>
#include <boost/optional.hpp>
#include <boost/pending/property.hpp> // for boost::lookup_one_property
+#include <boost/pending/container_traits.hpp>
#include <boost/throw_exception.hpp>
#include <boost/tuple/tuple.hpp> // for boost::make_tuple
#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/remove_cv.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/utility/enable_if.hpp>
@@ -253,7 +256,8 @@
/// Notify the named_graph that we are removing the given
/// vertex. The name of the vertex will be removed from the mapping.
- void removing_vertex(Vertex vertex);
+ template <typename VertexIterStability>
+ void removing_vertex(Vertex vertex, VertexIterStability);
/// Notify the named_graph that we are clearing the graph.
/// This will clear out all of the name->vertex mappings
@@ -308,8 +312,10 @@
}
template<BGL_NAMED_GRAPH_PARAMS>
-inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex)
+template<typename VertexIterStability>
+inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex, VertexIterStability)
{
+ BOOST_STATIC_ASSERT_MSG ((boost::is_base_of<boost::graph_detail::stable_tag, VertexIterStability>::value), "Named graphs cannot use vecS as vertex container and remove vertices; the lack of vertex descriptor stability (which iterator stability is a proxy for) means that the name -> vertex mapping would need to be completely rebuilt after each deletion. See https://svn.boost.org/trac/boost/ticket/7863 for more information and a test case.");
typedef typename BGL_NAMED_GRAPH::vertex_name_type vertex_name_type;
const vertex_name_type& vertex_name = extract_name(derived()[vertex]);
named_vertices.erase(vertex_name);
@@ -486,7 +492,8 @@
/// Notify the named_graph that we are removing the given
/// vertex. This is a no-op.
- void removing_vertex(Vertex) { }
+ template <typename VertexIterStability>
+ void removing_vertex(Vertex, VertexIterStability) { }
/// Notify the named_graph that we are clearing the graph. This is a
/// no-op.
@@ -517,7 +524,8 @@
/// Notify the named_graph that we are removing the given
/// vertex. This is a no-op.
- void removing_vertex(Vertex) { }
+ template <typename VertexIterStability>
+ void removing_vertex(Vertex, VertexIterStability) { }
/// Notify the named_graph that we are clearing the graph. This is a
/// no-op.
Modified: branches/release/boost/graph/r_c_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/r_c_shortest_paths.hpp (original)
+++ branches/release/boost/graph/r_c_shortest_paths.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -222,7 +222,7 @@
std::vector<int> vec_last_valid_index_for_dominance( num_vertices( g ), 0 );
std::vector<bool>
b_vec_vertex_already_checked_for_dominance( num_vertices( g ), false );
- while( unprocessed_labels.size() )
+ while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) )
{
Splabel cur_label = unprocessed_labels.top();
unprocessed_labels.pop();
@@ -409,7 +409,7 @@
typename std::list<Splabel>::const_iterator csi = dsplabels.begin();
typename std::list<Splabel>::const_iterator csi_end = dsplabels.end();
// if d could be reached from o
- if( dsplabels.size() )
+ if( !dsplabels.empty() )
{
for( ; csi != csi_end; ++csi )
{
@@ -458,6 +458,8 @@
void on_label_dominated( const Label&, const Graph& ) {}
template<class Label, class Graph>
void on_label_not_dominated( const Label&, const Graph& ) {}
+ template<class Queue, class Graph>
+ bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;}
}; // default_r_c_shortest_paths_visitor
Modified: branches/release/boost/graph/reverse_graph.hpp
==============================================================================
--- branches/release/boost/graph/reverse_graph.hpp (original)
+++ branches/release/boost/graph/reverse_graph.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -109,6 +109,8 @@
// Constructor
reverse_graph(GraphRef g) : m_g(g) {}
+ // Conversion from reverse_graph on non-const reference to one on const reference
+ reverse_graph(const reverse_graph<BidirectionalGraph, BidirectionalGraph&>& o): m_g(o.m_g) {}
// Graph requirements
typedef typename Traits::vertex_descriptor vertex_descriptor;
@@ -364,7 +366,12 @@
template <class BidirGraph, class GRef, class Property>
struct property_map<reverse_graph<BidirGraph, GRef>, Property> {
typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop;
- typedef typename property_map<BidirGraph, Property>::type orig_type;
+ typedef boost::is_const<typename boost::remove_reference<GRef>::type> is_ref_const;
+ typedef typename boost::mpl::if_<
+ is_ref_const,
+ typename property_map<BidirGraph, Property>::const_type,
+ typename property_map<BidirGraph, Property>::type>::type
+ orig_type;
typedef typename property_map<BidirGraph, Property>::const_type orig_const_type;
typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_type>, orig_type>::type type;
typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type;
Modified: branches/release/boost/graph/rmat_graph_generator.hpp
==============================================================================
--- branches/release/boost/graph/rmat_graph_generator.hpp (original)
+++ branches/release/boost/graph/rmat_graph_generator.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -22,7 +22,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/type_traits/is_same.hpp>
-#include <boost/test/floating_point_comparison.hpp>
+// #include <boost/test/floating_point_comparison.hpp>
using boost::shared_ptr;
using boost::uniform_01;
@@ -139,7 +139,7 @@
typedef std::pair<vertices_size_type, vertices_size_type> value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
- typedef void difference_type;
+ typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
rmat_iterator()
@@ -156,7 +156,7 @@
{
this->gen.reset(new uniform_01<RandomGenerator>(gen));
- BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
@@ -250,7 +250,7 @@
typedef std::pair<vertices_size_type, vertices_size_type> value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
- typedef void difference_type;
+ typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
sorted_rmat_iterator()
@@ -266,7 +266,7 @@
values(sort_pair<vertices_size_type>()), done(false)
{
- BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
@@ -352,7 +352,7 @@
typedef std::pair<vertices_size_type, vertices_size_type> value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
- typedef void difference_type;
+ typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
unique_rmat_iterator()
@@ -367,7 +367,7 @@
: gen(), done(false)
{
- BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
@@ -464,7 +464,7 @@
typedef std::pair<vertices_size_type, vertices_size_type> value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
- typedef void difference_type;
+ typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
sorted_unique_rmat_iterator()
@@ -480,7 +480,7 @@
values(sort_pair<vertices_size_type>()), done(false)
{
- BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
Modified: branches/release/boost/graph/sloan_ordering.hpp
==============================================================================
--- branches/release/boost/graph/sloan_ordering.hpp (original)
+++ branches/release/boost/graph/sloan_ordering.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -46,9 +46,9 @@
//
/////////////////////////////////////////////////////////////////////////
template<class Distance>
- unsigned RLS_depth(Distance& d)
+ typename Distance::value_type RLS_depth(Distance& d)
{
- unsigned h_s = 0;
+ typename Distance::value_type h_s = 0;
typename Distance::iterator iter;
for (iter = d.begin(); iter != d.end(); ++iter)
@@ -70,14 +70,16 @@
//
/////////////////////////////////////////////////////////////////////////
template<class Distance, class my_int>
- unsigned RLS_max_width(Distance& d, my_int depth)
+ typename Distance::value_type RLS_max_width(Distance& d, my_int depth)
{
+
+ typedef typename Distance::value_type Degree;
//Searching for the maximum width of a level
- std::vector<unsigned> dummy_width(depth+1, 0);
- std::vector<unsigned>::iterator my_it;
+ std::vector<Degree> dummy_width(depth+1, 0);
+ typename std::vector<Degree>::iterator my_it;
typename Distance::iterator iter;
- unsigned w_max = 0;
+ Degree w_max = 0;
for (iter = d.begin(); iter != d.end(); ++iter)
{
@@ -117,10 +119,10 @@
s = *(vertices(G).first);
Vertex e = s;
Vertex i;
- unsigned my_degree = get(degree, s );
- unsigned dummy, h_i, h_s, w_i, w_e;
+ Degree my_degree = get(degree, s );
+ Degree dummy, h_i, h_s, w_i, w_e;
bool new_start = true;
- unsigned maximum_degree = 0;
+ Degree maximum_degree = 0;
//Creating a std-vector for storing the distance from the start vertex in dist
std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);
@@ -196,7 +198,7 @@
// step 5
// Initializing w
- w_e = (std::numeric_limits<unsigned>::max)();
+ w_e = (std::numeric_limits<Degree>::max)();
//end 5
@@ -290,7 +292,7 @@
typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
//Sets the color and priority to their initial status
- unsigned cdeg;
+ Degree cdeg;
typename graph_traits<Graph>::vertex_iterator ui, ui_end;
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
{
Modified: branches/release/boost/graph/stoer_wagner_min_cut.hpp
==============================================================================
--- branches/release/boost/graph/stoer_wagner_min_cut.hpp (original)
+++ branches/release/boost/graph/stoer_wagner_min_cut.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -15,104 +15,96 @@
#include <boost/graph/buffer_concepts.hpp>
#include <boost/graph/exception.hpp>
#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/maximum_adjacency_search.hpp>
#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/one_bit_color_map.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/utility/result_of.hpp>
+#include <boost/graph/iteration_macros.hpp>
namespace boost {
-
+
namespace detail {
-
- /**
- * \brief Performs a phase of the Stoer-Wagner min-cut algorithm
- *
- * Performs a phase of the Stoer-Wagner min-cut algorithm.
- *
- * As described by Stoer & Wagner (1997), a phase is simply a maximum adjacency search
- * (also called a maximum cardinality search), which results in the selection of two vertices
- * \em s and \em t, and, as a side product, a minimum <em>s</em>-<em>t</em> cut of
- * the input graph. Here, the input graph is basically \p g, but some vertices are virtually
- * assigned to others as a way of viewing \p g as a graph with some sets of
- * vertices merged together.
- *
- * This implementation is a translation of pseudocode by Professor Uri Zwick,
- * School of Computer Science, Tel Aviv University.
- *
- * \pre \p g is a connected, undirected graph
- * \param[in] g the input graph
- * \param[in] assignments a read/write property map from each vertex to the vertex that it is assigned to
- * \param[in] assignedVertices a list of vertices that are assigned to others
- * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
- * \param[out] pq a keyed, updatable max-priority queue
- * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and "<em>t</em>"
- * of the minimum <em>s</em>-<em>t</em> cut and the cut weight \em w
- * of the minimum <em>s</em>-<em>t</em> cut.
- * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf
- *
- * \author Daniel Trebbien
- * \date 2010-09-11
- */
- template <class UndirectedGraph, class VertexAssignmentMap, class WeightMap, class KeyedUpdatablePriorityQueue>
- boost::tuple<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::property_traits<WeightMap>::value_type>
- stoer_wagner_phase(const UndirectedGraph& g, VertexAssignmentMap assignments, const std::set<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor>& assignedVertices, WeightMap weights, KeyedUpdatablePriorityQueue& pq) {
- typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+ template < typename ParityMap, typename WeightMap, typename IndexMap >
+ class mas_min_cut_visitor : public boost::default_mas_visitor {
+ typedef one_bit_color_map <IndexMap> InternalParityMap;
typedef typename boost::property_traits<WeightMap>::value_type weight_type;
-
- BOOST_ASSERT(pq.empty());
- typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
-
- BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
- if (v == get(assignments, v)) { // foreach u \in V do
- put(keys, v, weight_type(0));
-
- pq.push(v);
- }
+ public:
+ template < typename Graph >
+ mas_min_cut_visitor(const Graph& g,
+ ParityMap parity,
+ weight_type& cutweight,
+ WeightMap weight_map,
+ IndexMap index_map)
+ : m_bestParity(parity),
+ m_parity(make_one_bit_color_map(num_vertices(g), index_map)),
+ m_bestWeight(cutweight),
+ m_cutweight(0),
+ m_visited(0),
+ m_weightMap(weight_map)
+ {
+ // set here since the init list sets the reference
+ m_bestWeight = (std::numeric_limits<weight_type>::max)();
}
-
- BOOST_ASSERT(pq.size() >= 2);
-
- vertex_descriptor s = boost::graph_traits<UndirectedGraph>::null_vertex();
- vertex_descriptor t = boost::graph_traits<UndirectedGraph>::null_vertex();
- weight_type w;
- while (!pq.empty()) { // while PQ \neq {} do
- const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
- w = get(keys, u);
- pq.pop();
-
- s = t; t = u;
-
- BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph) { // foreach (u, v) \in E do
- const vertex_descriptor v = get(assignments, target(e, g));
-
- if (pq.contains(v)) { // if v \in PQ then
- put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
- pq.update(v);
- }
+
+ template < typename Vertex, typename Graph >
+ void initialize_vertex(Vertex u, const Graph & g)
+ {
+ typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+ typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
+
+ put(m_parity, u, internal_parity_type(0));
+ put(m_bestParity, u, parity_type(0));
+ }
+
+ template < typename Edge, typename Graph >
+ void examine_edge(Edge e, const Graph & g)
+ {
+ weight_type w = get(m_weightMap, e);
+
+ // if the target of e is already marked then decrease cutweight
+ // otherwise, increase it
+ if (get(m_parity, boost::target(e, g))) {
+ m_cutweight -= w;
+ } else {
+ m_cutweight += w;
}
-
- typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
- for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
- const vertex_descriptor uPrime = *assignedVertexIt;
-
- if (get(assignments, uPrime) == u) {
- BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph) { // foreach (u, v) \in E do
- const vertex_descriptor v = get(assignments, target(e, g));
-
- if (pq.contains(v)) { // if v \in PQ then
- put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
- pq.update(v);
- }
- }
+ }
+
+ template < typename Vertex, typename Graph >
+ void finish_vertex(Vertex u, const Graph & g)
+ {
+ typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+ typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
+
+ ++m_visited;
+ put(m_parity, u, internal_parity_type(1));
+
+ if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) {
+ m_bestWeight = m_cutweight;
+ BGL_FORALL_VERTICES_T(i, g, Graph) {
+ put(m_bestParity,i, get(m_parity,i));
}
}
}
-
- return boost::make_tuple(s, t, w);
- }
-
+
+ inline void clear() {
+ m_bestWeight = (std::numeric_limits<weight_type>::max)();
+ m_visited = 0;
+ m_cutweight = 0;
+ }
+
+ private:
+ ParityMap m_bestParity;
+ InternalParityMap m_parity;
+ weight_type& m_bestWeight;
+ weight_type m_cutweight;
+ unsigned m_visited;
+ const WeightMap& m_weightMap;
+ };
+
/**
* \brief Computes a min-cut of the input graph
*
@@ -135,9 +127,57 @@
* \author Daniel Trebbien
* \date 2010-09-11
*/
- template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
+ template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
typename boost::property_traits<WeightMap>::value_type
- stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
+ stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
+ typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+ typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
+ typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
+ typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+ typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+
+ typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end;
+
+ weight_type bestW = (std::numeric_limits<weight_type>::max)();
+ weight_type bestThisTime = (std::numeric_limits<weight_type>::max)();
+ vertex_descriptor bestStart;
+
+ detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap>
+ vis(g, parities, bestThisTime, weights, index_map);
+
+ // for each node in the graph,
+ for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
+ // run the MAS and find the min cut
+ vis.clear();
+ boost::maximum_adjacency_search(g,
+ boost::weight_map(weights).
+ visitor(vis).
+ root_vertex(*u_iter).
+ vertex_assignment_map(assignments).
+ max_priority_queue(pq));
+ if (bestThisTime < bestW) {
+ bestW = bestThisTime;
+ bestStart = *u_iter;
+ }
+ }
+
+ // Run one more time, starting from the best start location, to
+ // ensure the visitor has the best values.
+ vis.clear();
+ boost::maximum_adjacency_search(g,
+ boost::vertex_assignment_map(assignments).
+ weight_map(weights).
+ visitor(vis).
+ root_vertex(bestStart).
+ max_priority_queue(pq));
+
+ return bestW;
+ }
+ } // end `namespace detail` within `namespace boost`
+
+ template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
+ typename boost::property_traits<WeightMap>::value_type
+ stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>));
BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>));
typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
@@ -151,91 +191,62 @@
BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
-
+
vertices_size_type n = num_vertices(g);
if (n < 2)
throw boost::bad_graph("the input graph must have at least two vertices.");
else if (!pq.empty())
throw std::invalid_argument("the max-priority queue must be empty initially.");
-
- std::set<vertex_descriptor> assignedVertices;
-
- // initialize `assignments` (all vertices are initially assigned to themselves)
- BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
- put(assignments, v, v);
- }
-
- vertex_descriptor s, t;
- weight_type bestW;
-
- boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
- BOOST_ASSERT(s != t);
- BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
- put(parities, v, parity_type(v == t ? 1 : 0));
- }
- put(assignments, t, s);
- assignedVertices.insert(t);
- --n;
-
- for (; n >= 2; --n) {
- weight_type w;
- boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
- BOOST_ASSERT(s != t);
-
- if (w < bestW) {
- BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
- put(parities, v, parity_type(get(assignments, v) == t ? 1 : 0));
-
- if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
- put(assignments, v, s);
- }
-
- bestW = w;
- } else {
- BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
- if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
- put(assignments, v, s);
- }
- }
- put(assignments, t, s);
- assignedVertices.insert(t);
- }
-
- BOOST_ASSERT(pq.empty());
-
- return bestW;
+
+ return detail::stoer_wagner_min_cut(g, weights,
+ parities, assignments, pq, index_map);
}
-
- } // end `namespace detail` within `namespace boost`
-
- template <class UndirectedGraph, class WeightMap, class P, class T, class R>
- inline typename boost::property_traits<WeightMap>::value_type
- stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, const boost::bgl_named_params<P, T, R>& params) {
- typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
- typedef typename std::vector<vertex_descriptor>::size_type heap_container_size_type;
- typedef typename boost::property_traits<WeightMap>::value_type weight_type;
-
- typedef boost::bgl_named_params<P, T, R> params_type;
- BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
-
- typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type;
- gen_type gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
- typename boost::result_of<gen_type(const UndirectedGraph&, const arg_pack_type&)>::type pq = gen(g, arg_pack);
-
- return boost::detail::stoer_wagner_min_cut(g,
- weights,
- choose_param(get_param(params, boost::parity_map_t()), boost::dummy_property_map()),
- boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
- pq
- );
- }
-
- template <class UndirectedGraph, class WeightMap>
- inline typename boost::property_traits<WeightMap>::value_type
- stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights) {
- return boost::stoer_wagner_min_cut(g, weights, boost::vertex_index_map(get(boost::vertex_index, g)));
+
+namespace graph {
+ namespace detail {
+ template <class UndirectedGraph, class WeightMap>
+ struct stoer_wagner_min_cut_impl {
+ typedef typename boost::property_traits<WeightMap>::value_type result_type;
+ template <typename ArgPack>
+ result_type operator() (const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const {
+ using namespace boost::graph::keywords;
+ typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+ typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+
+ typedef typename boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type;
+
+ gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0)));
+
+ typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack);
+
+ return boost::stoer_wagner_min_cut(g,
+ weights,
+ arg_pack [_parity_map | boost::dummy_property_map()],
+ boost::detail::make_property_map_from_arg_pack_gen<tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
+ pq,
+ boost::detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index)
+ );
+ }
+ };
}
-
+ BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut,2,4)
+}
+
+ // Named parameter interface
+ BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2)
+namespace graph {
+ // version without IndexMap kept for backwards compatibility
+ // (but requires vertex_index_t to be defined in the graph)
+ // Place after the macro to avoid compilation errors
+ template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
+ typename boost::property_traits<WeightMap>::value_type
+ stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
+
+ return stoer_wagner_min_cut(g, weights,
+ parities, assignments, pq,
+ get(vertex_index, g));
+ }
+} // end `namespace graph`
} // end `namespace boost`
#include <boost/graph/iteration_macros_undef.hpp>
Modified: branches/release/boost/graph/vf2_sub_graph_iso.hpp
==============================================================================
--- branches/release/boost/graph/vf2_sub_graph_iso.hpp (original)
+++ branches/release/boost/graph/vf2_sub_graph_iso.hpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -1,5 +1,6 @@
//=======================================================================
// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+// Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark (jlandersen_at_[hidden])
//
// The algorithm implemented here is derived from original ideas by
// Pasquale Foggia and colaborators. For further information see
@@ -10,6 +11,9 @@
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
+// Revision History:
+// 8 April 2013: Fixed a typo in vf2_print_callback. (Flavio De Lorenzi)
+
#ifndef BOOST_VF2_SUB_GRAPH_ISO_HPP
#define BOOST_VF2_SUB_GRAPH_ISO_HPP
@@ -54,7 +58,7 @@
// Print (sub)graph isomorphism map
BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", "
- << get(vertex_index_t(), graph1_, get(f, v)) << ") ";
+ << get(vertex_index_t(), graph2_, get(f, v)) << ") ";
std::cout << std::endl;
@@ -372,7 +376,7 @@
};
- enum problem_selector { subgraph_iso, isomorphism };
+ enum problem_selector {subgraph_mono, subgraph_iso, isomorphism };
// The actual state associated with both graphs
template<typename Graph1,
@@ -405,8 +409,15 @@
base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_;
base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_;
- // Two helper functions used in Feasibility and Valid functions to test
+ // Three helper functions used in Feasibility and Valid functions to test
// terminal set counts when testing for:
+ // - graph sub-graph monomorphism, or
+ inline bool comp_term_sets(graph1_size_type a,
+ graph2_size_type b,
+ boost::mpl::int_<subgraph_mono>) const {
+ return a <= b;
+ }
+
// - graph sub-graph isomorphism, or
inline bool comp_term_sets(graph1_size_type a,
graph2_size_type b,
@@ -519,15 +530,16 @@
BGL_FORALL_INEDGES_T(w_new, e2, graph2_, Graph2) {
vertex2_type w = source(e2, graph2_);
if (state2_.in_core(w) || (w == w_new)) {
- vertex1_type v = v_new;
- if (w != w_new)
- v = state2_.core(w);
-
- if (!edge1_exists(v, v_new,
- edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
- graph1_))
- return false;
+ if (problem_selection != subgraph_mono) {
+ vertex1_type v = v_new;
+ if (w != w_new)
+ v = state2_.core(w);
+ if (!edge1_exists(v, v_new,
+ edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
+ graph1_))
+ return false;
+ }
} else {
if (0 < state2_.in_depth(w))
++term_in2_count;
@@ -545,15 +557,16 @@
BGL_FORALL_OUTEDGES_T(w_new, e2, graph2_, Graph2) {
vertex2_type w = target(e2, graph2_);
if (state2_.in_core(w) || (w == w_new)) {
- vertex1_type v = v_new;
- if (w != w_new)
- v = state2_.core(w);
-
- if (!edge1_exists(v_new, v,
- edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
- graph1_))
- return false;
+ if (problem_selection != subgraph_mono) {
+ vertex1_type v = v_new;
+ if (w != w_new)
+ v = state2_.core(w);
+ if (!edge1_exists(v_new, v,
+ edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
+ graph1_))
+ return false;
+ }
} else {
if (0 < state2_.in_depth(w))
++term_in2_count;
@@ -564,13 +577,23 @@
}
}
}
-
- return comp_term_sets(term_in1_count, term_in2_count,
- boost::mpl::int_<problem_selection>()) &&
- comp_term_sets(term_out1_count, term_out2_count,
- boost::mpl::int_<problem_selection>()) &&
- comp_term_sets(rest1_count, rest2_count,
- boost::mpl::int_<problem_selection>());
+
+ if (problem_selection != subgraph_mono) { // subgraph_iso and isomorphism
+ return comp_term_sets(term_in1_count, term_in2_count,
+ boost::mpl::int_<problem_selection>()) &&
+ comp_term_sets(term_out1_count, term_out2_count,
+ boost::mpl::int_<problem_selection>()) &&
+ comp_term_sets(rest1_count, rest2_count,
+ boost::mpl::int_<problem_selection>());
+ } else { // subgraph_mono
+ return comp_term_sets(term_in1_count, term_in2_count,
+ boost::mpl::int_<problem_selection>()) &&
+ comp_term_sets(term_out1_count, term_out2_count,
+ boost::mpl::int_<problem_selection>()) &&
+ comp_term_sets(term_in1_count + term_out1_count + rest1_count,
+ term_in2_count + term_out2_count + rest2_count,
+ boost::mpl::int_<problem_selection>());
+ }
}
// Returns true if vertex v in graph1 is a possible candidate to
@@ -790,6 +813,91 @@
}
+ // Enumerates all graph sub-graph mono-/iso-morphism mappings between graphs
+ // graph_small and graph_large. Continues until user_callback returns true or the
+ // search space has been fully explored.
+ template <problem_selector problem_selection,
+ typename GraphSmall,
+ typename GraphLarge,
+ typename IndexMapSmall,
+ typename IndexMapLarge,
+ typename VertexOrderSmall,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_morphism(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ IndexMapSmall index_map_small, IndexMapLarge index_map_large,
+ const VertexOrderSmall& vertex_order_small,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
+
+ // Graph requirements
+ BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphSmall> ));
+ BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphSmall> ));
+ BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphSmall> ));
+ BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphSmall> ));
+
+ BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphLarge> ));
+ BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphLarge> ));
+ BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphLarge> ));
+ BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphLarge> ));
+
+ typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type;
+ typedef typename graph_traits<GraphLarge>::vertex_descriptor vertex_large_type;
+
+ typedef typename graph_traits<GraphSmall>::vertices_size_type size_type_small;
+ typedef typename graph_traits<GraphLarge>::vertices_size_type size_type_large;
+
+ // Property map requirements
+ BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapSmall, vertex_small_type> ));
+ typedef typename property_traits<IndexMapSmall>::value_type IndexMapSmallValue;
+ BOOST_STATIC_ASSERT(( is_convertible<IndexMapSmallValue, size_type_small>::value ));
+
+ BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapLarge, vertex_large_type> ));
+ typedef typename property_traits<IndexMapLarge>::value_type IndexMapLargeValue;
+ BOOST_STATIC_ASSERT(( is_convertible<IndexMapLargeValue, size_type_large>::value ));
+
+ // Edge & vertex requirements
+ typedef typename graph_traits<GraphSmall>::edge_descriptor edge_small_type;
+ typedef typename graph_traits<GraphLarge>::edge_descriptor edge_large_type;
+
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate,
+ edge_small_type, edge_large_type> ));
+
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate,
+ vertex_small_type, vertex_large_type> ));
+
+ // Vertex order requirements
+ BOOST_CONCEPT_ASSERT(( ContainerConcept<VertexOrderSmall> ));
+ typedef typename VertexOrderSmall::value_type order_value_type;
+ BOOST_STATIC_ASSERT(( is_same<vertex_small_type, order_value_type>::value ));
+ BOOST_ASSERT( num_vertices(graph_small) == vertex_order_small.size() );
+
+ if (num_vertices(graph_small) > num_vertices(graph_large))
+ return false;
+
+ typename graph_traits<GraphSmall>::edges_size_type num_edges_small = num_edges(graph_small);
+ typename graph_traits<GraphLarge>::edges_size_type num_edges_large = num_edges(graph_large);
+
+ // Double the number of edges for undirected graphs: each edge counts as
+ // in-edge and out-edge
+ if (is_undirected(graph_small)) num_edges_small *= 2;
+ if (is_undirected(graph_large)) num_edges_large *= 2;
+ if (num_edges_small > num_edges_large)
+ return false;
+
+ if ((num_vertices(graph_small) == 0) && (num_vertices(graph_large) == 0))
+ return true;
+
+ detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ SubGraphIsoMapCallback, problem_selection>
+ s(graph_small, graph_large, index_map_small, index_map_large, edge_comp, vertex_comp);
+
+ return detail::match(graph_small, graph_large, user_callback, vertex_order_small, s);
+ }
+
} // namespace detail
@@ -805,6 +913,72 @@
return vertex_order;
}
+
+ // Enumerates all graph sub-graph monomorphism mappings between graphs
+ // graph_small and graph_large. Continues until user_callback returns true or the
+ // search space has been fully explored.
+ template <typename GraphSmall,
+ typename GraphLarge,
+ typename IndexMapSmall,
+ typename IndexMapLarge,
+ typename VertexOrderSmall,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ IndexMapSmall index_map_small, IndexMapLarge index_map_large,
+ const VertexOrderSmall& vertex_order_small,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
+ return detail::vf2_subgraph_morphism<detail::subgraph_mono>
+ (graph_small, graph_large,
+ user_callback,
+ index_map_small, index_map_large,
+ vertex_order_small,
+ edge_comp,
+ vertex_comp);
+ }
+
+
+ // All default interface for vf2_subgraph_iso
+ template <typename GraphSmall,
+ typename GraphLarge,
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback) {
+ return vf2_subgraph_mono(graph_small, graph_large, user_callback,
+ get(vertex_index, graph_small), get(vertex_index, graph_large),
+ vertex_order_by_mult(graph_small),
+ always_equivalent(), always_equivalent());
+ }
+
+
+ // Named parameter interface of vf2_subgraph_iso
+ template <typename GraphSmall,
+ typename GraphLarge,
+ typename VertexOrderSmall,
+ typename SubGraphIsoMapCallback,
+ typename Param,
+ typename Tag,
+ typename Rest>
+ bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ const VertexOrderSmall& vertex_order_small,
+ const bgl_named_params<Param, Tag, Rest>& params) {
+ return vf2_subgraph_mono(graph_small, graph_large, user_callback,
+ choose_const_pmap(get_param(params, vertex_index1),
+ graph_small, vertex_index),
+ choose_const_pmap(get_param(params, vertex_index2),
+ graph_large, vertex_index),
+ vertex_order_small,
+ choose_param(get_param(params, edges_equivalent_t()),
+ always_equivalent()),
+ choose_param(get_param(params, vertices_equivalent_t()),
+ always_equivalent())
+ );
+ }
+
// Enumerates all graph sub-graph isomorphism mappings between graphs
// graph_small and graph_large. Continues until user_callback returns true or the
@@ -823,71 +997,13 @@
const VertexOrderSmall& vertex_order_small,
EdgeEquivalencePredicate edge_comp,
VertexEquivalencePredicate vertex_comp) {
-
- // Graph requirements
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphSmall> ));
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphSmall> ));
- BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphSmall> ));
- BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphSmall> ));
-
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphLarge> ));
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphLarge> ));
- BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphLarge> ));
- BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphLarge> ));
-
- typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type;
- typedef typename graph_traits<GraphLarge>::vertex_descriptor vertex_large_type;
-
- typedef typename graph_traits<GraphSmall>::vertices_size_type size_type_small;
- typedef typename graph_traits<GraphLarge>::vertices_size_type size_type_large;
-
- // Property map requirements
- BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapSmall, vertex_small_type> ));
- typedef typename property_traits<IndexMapSmall>::value_type IndexMapSmallValue;
- BOOST_STATIC_ASSERT(( is_convertible<IndexMapSmallValue, size_type_small>::value ));
-
- BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapLarge, vertex_large_type> ));
- typedef typename property_traits<IndexMapLarge>::value_type IndexMapLargeValue;
- BOOST_STATIC_ASSERT(( is_convertible<IndexMapLargeValue, size_type_large>::value ));
-
- // Edge & vertex requirements
- typedef typename graph_traits<GraphSmall>::edge_descriptor edge_small_type;
- typedef typename graph_traits<GraphLarge>::edge_descriptor edge_large_type;
-
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate,
- edge_small_type, edge_large_type> ));
-
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate,
- vertex_small_type, vertex_large_type> ));
-
- // Vertex order requirements
- BOOST_CONCEPT_ASSERT(( ContainerConcept<VertexOrderSmall> ));
- typedef typename VertexOrderSmall::value_type order_value_type;
- BOOST_STATIC_ASSERT(( is_same<vertex_small_type, order_value_type>::value ));
- BOOST_ASSERT( num_vertices(graph_small) == vertex_order_small.size() );
-
- if (num_vertices(graph_small) > num_vertices(graph_large))
- return false;
-
- typename graph_traits<GraphSmall>::edges_size_type num_edges_small = num_edges(graph_small);
- typename graph_traits<GraphLarge>::edges_size_type num_edges_large = num_edges(graph_large);
-
- // Double the number of edges for undirected graphs: each edge counts as
- // in-edge and out-edge
- if (is_undirected(graph_small)) num_edges_small *= 2;
- if (is_undirected(graph_large)) num_edges_large *= 2;
- if (num_edges_small > num_edges_large)
- return false;
-
- if ((num_vertices(graph_small) == 0) && (num_vertices(graph_large) == 0))
- return true;
-
- detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
- EdgeEquivalencePredicate, VertexEquivalencePredicate,
- SubGraphIsoMapCallback, detail::subgraph_iso>
- s(graph_small, graph_large, index_map_small, index_map_large, edge_comp, vertex_comp);
-
- return detail::match(graph_small, graph_large, user_callback, vertex_order_small, s);
+ return detail::vf2_subgraph_morphism<detail::subgraph_iso>
+ (graph_small, graph_large,
+ user_callback,
+ index_map_small, index_map_large,
+ vertex_order_small,
+ edge_comp,
+ vertex_comp);
}
Modified: branches/release/libs/graph/doc/johnson_all_pairs_shortest.html
==============================================================================
--- branches/release/libs/graph/doc/johnson_all_pairs_shortest.html (original)
+++ branches/release/libs/graph/doc/johnson_all_pairs_shortest.html 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -15,7 +15,7 @@
<BR Clear>
-<H1><A NAME="sec:johnson">
+<H1><A NAME="sec:johnson"></A>
<TT>johnson_all_pairs_shortest_paths</TT>
</H1>
@@ -75,10 +75,12 @@
OUT: <tt>DistanceMatrix& D</tt>
<blockquote>
The length of the shortest path between each pair of vertices
-<i>u,v</i> in the graph is stored in <tt>D[u][v]</tt>. The set of
-types {<tt>DistanceMatrix, vertices_size_type, D</tt>} must be a model
+<i>u,v</i> in the graph is stored in <tt>D[u][v]</tt>. The tuple of
+types (<tt>DistanceMatrix, vertices_size_type, D</tt>) must be a model
of BasicMatrix where <tt>D</tt> is the
-value type of the <tt>DistanceMap</tt>.
+value type of the <tt>DistanceMap</tt>. There must be implicit conversions
+between the value type of the distance matrix and the value type of the weight
+map.
</blockquote>
@@ -86,12 +88,11 @@
IN: <tt>weight_map(WeightMap w_map)</tt>
<blockquote>
- The weight or ``length'' of each edge in the graph.
+ The weight or "length" of each edge in the graph.
The type <tt>WeightMap</tt> must be a model of
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
the graph needs to be usable as the key type for the weight
- map. The value type for the map must be
- <i>Addable</i> with the value type of the distance map.<br>
+ map. The value type of the weight map must support a subtraction operation.<br>
<b>Default:</b> <tt>get(edge_weight, g)</tt>
</blockquote>
@@ -112,7 +113,7 @@
<b>Default:</b> <tt>get(vertex_index, g)</tt>
Note: if you use this default, make sure your graph has
an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
not have an internal <tt>vertex_index</tt> property.
<br>
</blockquote>
@@ -128,7 +129,8 @@
This function is use to compare distances to determine
which vertex is closer to the source vertex.
The <tt>CompareFunction</tt> type must be a model of
- \stlconcept{BinaryPredicate} and have argument types that
+ Binary Predicate
+ and have argument types that
match the value type of the <tt>WeightMap</tt> property map.<br>
<b>Default:</b> <tt>std::less<DT></tt> with
<tt>DT=typename property_traits<WeightMap>::value_type</tt>
@@ -139,11 +141,8 @@
This function is used to combine distances to compute the distance
of a path. The <tt>CombineFunction</tt> type must be a model of <a
href="http://www.sgi.com/tech/stl/BinaryFunction.html">Binary
- Function</a>. The first argument type of the binary function must
- match the value type of the <tt>DistanceMap</tt> property map and
- the second argument type must match the value type of the
- <tt>WeightMap</tt> property map. The result type must be the same
- type as the distance value type.<br>
+ Function</a>. Both argument types and the return type of the binary function
+ must match the value type of the <tt>WeightMap</tt> property map. This operation is required to act as the sum operation for the weight type; in particular, it must be the inverse of the binary <tt>-</tt> operator on that type.<br>
<b>Default:</b> <tt>std::plus<DT></tt> with
<tt>DT=typename property_traits<WeightMap>::value_type</tt>
</blockquote>
@@ -152,7 +151,7 @@
<blockquote>
This value is used to initialize the distance for each
vertex before the start of the algorithm.
- The type <tt>DT</tt> must be the value type of the <tt>WeigthMap</tt>.<br>
+ The type <tt>DT</tt> must be the value type of the <tt>WeightMap</tt>.<br>
<b>Default:</b> <tt>std::numeric_limits::max()</tt>
</blockquote>
@@ -160,7 +159,7 @@
<blockquote>
This value is used to initialize the distance for the source
vertex before the start of the algorithm. The type <tt>DT</tt>
- must be the value type of the <tt>WeigthMap</tt>.<br>
+ must be the value type of the <tt>WeightMap</tt>.<br>
<b>Default:</b> <tt>0</tt>
</blockquote>
Modified: branches/release/libs/graph/doc/r_c_shortest_paths.html
==============================================================================
--- branches/release/libs/graph/doc/r_c_shortest_paths.html (original)
+++ branches/release/libs/graph/doc/r_c_shortest_paths.html 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -466,7 +466,7 @@
</blockquote>
IN: <tt>Label_Allocator la</tt>
<blockquote>
-An object of type <tt>Label_Allocator</tt> specifying a strategy for the memory management of the labels. It must offer the same interface as <tt>std::allocator<lt;r_c_shortest_paths_label<Graph, Resource_Container> ></tt>. There is a default type <tt>default_r_c_shortest_paths_allocator</tt> for this parameter using the STL standard allocator. If the third or the fourth overload of the function is used, an object of this type is used as <tt>Label_Allocator</tt> parameter. If the first or the second overload is used, one must specify both a <tt>Label_Allocator</tt> and a <tt>Visitor</tt> parameter. If one wants to develop a user-defined type only for <tt>Visitor</tt>, one can use <tt>default_r_c_shortest_paths_allocator</tt> as <tt>Label_Allocator</tt> parameter. If one wants to use a specialized allocator, one can specify an arbitrary type as template parameter for the value type to the allocator; it is rebound to the correct type.
+An object of type <tt>Label_Allocator</tt> specifying a strategy for the memory management of the labels. It must offer the same interface as <tt>std::allocator<r_c_shortest_paths_label<Graph, Resource_Container> ></tt>. There is a default type <tt>default_r_c_shortest_paths_allocator</tt> for this parameter using the STL standard allocator. If the third or the fourth overload of the function is used, an object of this type is used as <tt>Label_Allocator</tt> parameter. If the first or the second overload is used, one must specify both a <tt>Label_Allocator</tt> and a <tt>Visitor</tt> parameter. If one wants to develop a user-defined type only for <tt>Visitor</tt>, one can use <tt>default_r_c_shortest_paths_allocator</tt> as <tt>Label_Allocator</tt> parameter. If one wants to use a specialized allocator, one can specify an arbitrary type as template parameter for the value type to the allocator; it is rebound to the correct type.
</blockquote>
IN: <tt>Visitor vis</tt>
<blockquote>
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -287,6 +287,7 @@
<LI>sequential_vertex_coloring
<LI>is_bipartite (including two-coloring of bipartite graphs)
<LI>find_odd_cycle
+ <LI>maximum_adjacency_search
</ol>
</li>
Modified: branches/release/libs/graph/doc/vf2_sub_graph_iso.html
==============================================================================
--- branches/release/libs/graph/doc/vf2_sub_graph_iso.html (original)
+++ branches/release/libs/graph/doc/vf2_sub_graph_iso.html 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -87,13 +87,16 @@
graph that preserves the edge structure of the graphs. <em>M</em> is said to be a
graph-subgraph isomorphism if and only if <em>M</em> is an isomorphism between
<em>G<sub>1</sub></em> and a subgraph of <em>G<sub>2</sub></em>.
+ An induced subgraph of a graph <em>G = (V, E)</em> is a normal subgraph
+ <em>G' = (V', E')</em> with the extra condition that all edges of <em>G</em>
+ which have both endpoints in <em>V'</em> are in <em>E'</em>.
</p>
<p>
- This function finds all graph-subgraph isomorphism mappings between
+ This function finds all induced subgraph isomorphisms between
graphs <tt>graph_small</tt> and <tt>graph_large</tt> and outputs them to
<tt>user_callback</tt>. It continues until <tt>user_callback</tt>
- returns true or the search space has been fully explored. <tt>vf2_subgraph_iso</tt>
+ returns false or the search space has been fully explored. <tt>vf2_subgraph_iso</tt>
returns true if a graph-subgraph isomorphism exists and false otherwise.
<tt>EdgeEquivalencePredicate</tt> and
<tt>VertexEquivalencePredicate</tt> predicates are used to test whether
@@ -182,8 +185,8 @@
and <tt>CorresondenceMap2To1</tt> types are models
of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
Property Map</a> and map equivalent vertices across the two
- graphs given to <tt>vf2_subgraph_iso</tt> (or <tt>vf2_graph_iso</tt>). For
- instance, if <tt>v</tt> is
+ graphs given to <tt>vf2_subgraph_iso</tt> (or <tt>vf2_graph_iso</tt> or
+ <tt>vf2_subgraph_mono</tt>). For instance, if <tt>v</tt> is
from <tt>graph_small</tt>, <tt>w</tt> is from <tt>graph_large</tt>,
and the vertices can be considered equivalent,
then <tt>get(f, v)</tt> will be <tt>w</tt> and <tt>get(g, w)</tt>
@@ -279,13 +282,22 @@
function
</p>
<p><tt>vf2_graph_iso(...)</tt></p>
+ <p><tt>vf2_subgraph_mono(...)</tt></p>
<p>
- for isomorphism testing take the same parameters as the corresponding
- functions <tt>vf2_subgraph_iso</tt> for subgraph isomorphism testing.
- The algorithm finds all isomorphism mappings between graphs
- <tt>graph1</tt> and <tt>graph2</tt> and outputs them to
- <tt>user_callback</tt>. It continues until <tt>user_callback</tt>
- returns true or the search space has been fully explored. As before,
+ for isomorphism and (not necessarily induced) subgraph isomorphism testing,
+ taking the same parameters as the corresponding functions <tt>vf2_subgraph_iso</tt>
+ for induced subgraph isomorphism testing.
+ For <tt>vf2_graph_iso</tt> the algorithm finds all isomorphism mappings between
+ graphs <tt>graph1</tt> and <tt>graph2</tt> and outputs them to
+ <tt>user_callback</tt>.
+ For <tt>vf2_graph_mono</tt> the algorithm finds all mappings of <tt>graph_small</tt>
+ to subgraphs of <tt>graph_large</tt>.
+ Note that, as opposed to <tt>vf2_subgraph_iso</tt>,
+ these subgraphs need not to be induced subgraphs.
+ </p>
+ <p>
+ Both algorithms continues until <tt>user_callback</tt>
+ returns false or the search space has been fully explored. As before,
<tt>EdgeEquivalencePredicate</tt> and
<tt>VertexEquivalencePredicate</tt> predicates are used to test
whether edges and vertices are equivalent. By default
@@ -511,7 +523,9 @@
<hr>
<p>
Copyright © 2012, Flavio De Lorenzi
- (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>)
+ (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>) <br />
+ Copyright © 2013, Jakob Lykke Andersen, University of Southern Denmark
+ (<a href="mailto:jlandersen_at_[hidden]">jlandersen_at_[hidden]</a>)
</p>
</body>
</html>
Modified: branches/release/libs/graph/example/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2 (original)
+++ branches/release/libs/graph/example/Jamfile.v2 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -35,6 +35,9 @@
exe bfs-example : bfs-example.cpp ;
exe bfs-example2 : bfs-example2.cpp ;
exe dfs-example : dfs-example.cpp ;
+exe dijkstra-example : dijkstra-example.cpp ;
+exe dijkstra-example-listS : dijkstra-example-listS.cpp ;
+exe dijkstra-no-color-map-example : dijkstra-no-color-map-example.cpp ;
exe adjacency_list_io : adjacency_list_io.cpp ;
exe undirected_adjacency_list : undirected_adjacency_list.cpp ;
exe directed_graph : directed_graph.cpp ;
@@ -46,4 +49,5 @@
exe subgraph_properties : subgraph_properties.cpp ;
exe vf2_sub_graph_iso_example : vf2_sub_graph_iso_example.cpp ;
exe vf2_sub_graph_iso_multi_example : vf2_sub_graph_iso_multi_example.cpp ;
+exe sloan_ordering : sloan_ordering.cpp ;
Modified: branches/release/libs/graph/example/astar-cities.cpp
==============================================================================
--- branches/release/libs/graph/example/astar-cities.cpp (original)
+++ branches/release/libs/graph/example/astar-cities.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -171,7 +171,7 @@
// pick random start/goal
- mt19937 gen(time(0));
+ boost::mt19937 gen(time(0));
vertex start = random_vertex(g, gen);
vertex goal = random_vertex(g, gen);
Modified: branches/release/libs/graph/example/dijkstra-example-listS.cpp
==============================================================================
--- branches/release/libs/graph/example/dijkstra-example-listS.cpp (original)
+++ branches/release/libs/graph/example/dijkstra-example-listS.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -38,25 +38,8 @@
int num_arcs = sizeof(edge_array) / sizeof(Edge);
graph_traits<graph_t>::vertex_iterator i, iend;
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- graph_t g(num_nodes);
- property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
-
- std::vector<vertex_descriptor> msvc_vertices;
- for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
- msvc_vertices.push_back(*i);
-
- for (std::size_t j = 0; j < num_arcs; ++j) {
- edge_descriptor e; bool inserted;
- boost::tie(e, inserted) = add_edge(msvc_vertices[edge_array[j].first],
- msvc_vertices[edge_array[j].second], g);
- weightmap[e] = weights[j];
- }
-
-#else
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
-#endif
// Manually intialize the vertex index and name maps
property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);
@@ -73,16 +56,7 @@
d = get(vertex_distance, g);
property_map<graph_t, vertex_predecessor_t>::type
p = get(vertex_predecessor, g);
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ has trouble with the named parameters mechanism
- property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);
- dijkstra_shortest_paths(g, s, p, d, weightmap, indexmap,
- std::less<int>(), closed_plus<int>(),
- (std::numeric_limits<int>::max)(), 0,
- default_dijkstra_visitor());
-#else
dijkstra_shortest_paths(g, s, predecessor_map(p).distance_map(d));
-#endif
std::cout << "distances and parents:" << std::endl;
graph_traits < graph_t >::vertex_iterator vi, vend;
Modified: branches/release/libs/graph/example/dijkstra-example.cpp
==============================================================================
--- branches/release/libs/graph/example/dijkstra-example.cpp (original)
+++ branches/release/libs/graph/example/dijkstra-example.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -12,6 +12,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/property_map/property_map.hpp>
using namespace boost;
@@ -32,32 +33,15 @@
};
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
int num_arcs = sizeof(edge_array) / sizeof(Edge);
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- graph_t g(num_nodes);
- property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
- for (std::size_t j = 0; j < num_arcs; ++j) {
- edge_descriptor e; bool inserted;
- boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
- weightmap[e] = weights[j];
- }
-#else
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
-#endif
std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
vertex_descriptor s = vertex(A, g);
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ has trouble with the named parameters mechanism
- property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);
- dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap,
- std::less<int>(), closed_plus<int>(),
- (std::numeric_limits<int>::max)(), 0,
- default_dijkstra_visitor());
-#else
- dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));
-#endif
+ dijkstra_shortest_paths(g, s,
+ predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, g))).
+ distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, g))));
std::cout << "distances and parents:" << std::endl;
graph_traits < graph_t >::vertex_iterator vi, vend;
Modified: branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp
==============================================================================
--- branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp (original)
+++ branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -16,6 +16,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
+#include <boost/property_map/property_map.hpp>
using namespace boost;
@@ -36,33 +37,15 @@
};
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
int num_arcs = sizeof(edge_array) / sizeof(Edge);
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- graph_t g(num_nodes);
- property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
- for (std::size_t j = 0; j < num_arcs; ++j) {
- edge_descriptor e; bool inserted;
- boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
- weightmap[e] = weights[j];
- }
-#else
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
-#endif
std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
vertex_descriptor s = vertex(A, g);
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ has trouble with the named parameters mechanism
- property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);
- dijkstra_shortest_paths_no_color_map(g, s, &p[0], &d[0], weightmap,
- indexmap, std::less<int>(),
- closed_plus<int>(),
- (std::numeric_limits<int>::max)(), 0,
- default_dijkstra_visitor());
-#else
- dijkstra_shortest_paths_no_color_map(g, s, predecessor_map(&p[0]).distance_map(&d[0]));
-#endif
+ dijkstra_shortest_paths_no_color_map(g, s,
+ predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, g))).
+ distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, g))));
std::cout << "distances and parents:" << std::endl;
graph_traits < graph_t >::vertex_iterator vi, vend;
Modified: branches/release/libs/graph/example/matching_example.cpp
==============================================================================
--- branches/release/libs/graph/example/matching_example.cpp (original)
+++ branches/release/libs/graph/example/matching_example.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -44,6 +44,7 @@
// our vertices are stored in a vector, so we can refer to vertices
// by integers in the range 0..15
+ add_edge(1,2,g);
add_edge(0,4,g);
add_edge(1,5,g);
add_edge(2,6,g);
Modified: branches/release/libs/graph/src/graphml.cpp
==============================================================================
--- branches/release/libs/graph/src/graphml.cpp (original)
+++ branches/release/libs/graph/src/graphml.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -71,6 +71,7 @@
else if (for_ == "port") kind = port_key;
else if (for_ == "endpoint") kind = endpoint_key;
else if (for_ == "all") kind = all_key;
+ else if (for_ == "graphml") kind = graphml_key;
else {BOOST_THROW_EXCEPTION(parse_error("Attribute for is not valid: " + for_));}
m_keys[id] = kind;
m_key_name[id] = name;
@@ -132,7 +133,8 @@
hyperedge_key,
port_key,
endpoint_key,
- all_key
+ all_key,
+ graphml_key
};
void
Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -122,6 +122,7 @@
[ run two_graphs_common_spanning_trees_test.cpp ]
[ run random_spanning_tree_test.cpp ../build//boost_graph ]
[ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
+ [ run mas_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
[ compile filtered_graph_properties_dijkstra.cpp ]
[ run vf2_sub_graph_iso_test.cpp ]
Modified: branches/release/libs/graph/test/astar_search_test.cpp
==============================================================================
--- branches/release/libs/graph/test/astar_search_test.cpp (original)
+++ branches/release/libs/graph/test/astar_search_test.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -31,7 +31,12 @@
{
float y, x; // lat, long
};
-typedef float cost;
+struct my_float {float v; explicit my_float(float v = float()): v(v) {}};
+typedef my_float cost;
+ostream& operator<<(ostream& o, my_float f) {return o << f.v;}
+my_float operator+(my_float a, my_float b) {return my_float(a.v + b.v);}
+bool operator==(my_float a, my_float b) {return a.v == b.v;}
+bool operator<(my_float a, my_float b) {return a.v < b.v;}
template <class Name, class LocMap>
class city_writer {
@@ -80,9 +85,9 @@
: m_location(l), m_goal(goal) {}
CostType operator()(Vertex u)
{
- CostType dx = m_location[m_goal].x - m_location[u].x;
- CostType dy = m_location[m_goal].y - m_location[u].y;
- return ::sqrt(dx * dx + dy * dy);
+ float dx = m_location[m_goal].x - m_location[u].x;
+ float dy = m_location[m_goal].y - m_location[u].y;
+ return CostType(::sqrt(dx * dx + dy * dy));
}
private:
LocMap m_location;
@@ -153,8 +158,8 @@
};
unsigned int num_edges = sizeof(edge_array) / sizeof(edge);
cost weights[] = { // estimated travel time (mins)
- 96, 134, 143, 65, 115, 133, 117, 116, 74, 56,
- 84, 73, 69, 70, 116, 147, 173, 183, 74, 71, 124
+ my_float(96), my_float(134), my_float(143), my_float(65), my_float(115), my_float(133), my_float(117), my_float(116), my_float(74), my_float(56),
+ my_float(84), my_float(73), my_float(69), my_float(70), my_float(116), my_float(147), my_float(173), my_float(183), my_float(74), my_float(71), my_float(124)
};
@@ -187,7 +192,7 @@
distance_heuristic<mygraph_t, cost, location*>
(locations, goal),
predecessor_map(&p[0]).distance_map(&d[0]).
- visitor(astar_goal_visitor<vertex>(goal)));
+ visitor(astar_goal_visitor<vertex>(goal)).distance_inf(my_float((std::numeric_limits<float>::max)())));
} catch(found_goal fg) { // found a path to the goal
Copied: branches/release/libs/graph/test/mas_test.cpp (from r83410, /trunk/libs/graph/test/mas_test.cpp)
==============================================================================
--- /trunk/libs/graph/test/mas_test.cpp (original)
+++ branches/release/libs/graph/test/mas_test.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -210,7 +210,7 @@
std::map<edge_descriptor, weight_type> wm;
weight_type i = 0;
- BGL_FORALL_EDGES_T(e, g, undirected_unweighted_graph) {
+ BGL_FORALL_EDGES(e, g, undirected_unweighted_graph) {
wm[e] = ws[i];
++i;
}
Modified: branches/release/libs/graph/test/vf2_sub_graph_iso_test.cpp
==============================================================================
--- branches/release/libs/graph/test/vf2_sub_graph_iso_test.cpp (original)
+++ branches/release/libs/graph/test/vf2_sub_graph_iso_test.cpp 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -9,6 +9,9 @@
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
+// Revision History:
+// 8 April 2013: Fixed a typo in random_functor. (Flavio De Lorenzi)
+
#include <iostream>
#include <fstream>
#include <map>
@@ -36,7 +39,7 @@
random_functor(Generator& g) : g(g) { }
std::size_t operator()(std::size_t n) {
boost::uniform_int<std::size_t> distrib(0, n-1);
- boost::variate_generator<boost::mt19937&, boost::uniform_int<std::size_t> >
+ boost::variate_generator<Generator&, boost::uniform_int<std::size_t> >
x(g, distrib);
return x();
}
Copied: branches/release/libs/property_map/doc/compose_property_map.html (from r83037, /trunk/libs/property_map/doc/compose_property_map.html)
==============================================================================
--- /trunk/libs/property_map/doc/compose_property_map.html (original)
+++ branches/release/libs/property_map/doc/compose_property_map.html 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -1,24 +1,30 @@
<html>
<!--
- Copyright (c) 2012 Guillaume Pinot
+ Copyright (c) 2013 Eurodecision
+ Authors: Guillaume Pinot
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)
-->
+
<head>
<title>Compose Property Map Adaptor</title>
</head>
+
<body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"
- alink="#ff0000">
+ alink="#ff0000">
<img src="../../../boost.png"
alt="C++ Boost" width="277" height="86">
<br Clear>
-<h2><a name="sec:compose-property-map"></a>
+<h2>
+<a name="sec:compose-property-map"></a>Compose Property Map
+Adaptor
</h2>
+
<pre>
compose_property_map<FPMap, GPMap>
</pre>
@@ -129,13 +135,13 @@
<hr>
-<br>
-
-<hr>
-
<table>
<tr valign="top">
<td nowrap>Copyright © 2013</td>
+<td>Eurodecision</td>
+</tr>
+<tr valign="top">
+<td nowrap>Author:</td>
<td>Guillaume Pinot</td>
</tr>
</table>
Modified: branches/release/libs/property_map/doc/property_map.html
==============================================================================
--- branches/release/libs/property_map/doc/property_map.html (original)
+++ branches/release/libs/property_map/doc/property_map.html 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -292,6 +292,7 @@
<li>vector_property_map</li>
<li>ref_property_map </li>
<li>transform_value_property_map </li>
+ <li>compose_property_map </li>
</ul>
<h3>History</h3>
Modified: branches/release/libs/property_map/test/Jamfile.v2
==============================================================================
--- branches/release/libs/property_map/test/Jamfile.v2 (original)
+++ branches/release/libs/property_map/test/Jamfile.v2 2013-05-16 11:38:05 EDT (Thu, 16 May 2013)
@@ -12,6 +12,7 @@
test-suite property_map
: [ compile property_map_cc.cpp ]
+ [ run compose_property_map_test.cpp ]
[ run dynamic_properties_test.cpp ]
[ run function_property_map_test.cpp ]
[ run transform_value_property_map_test.cpp ]
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