diff options
Diffstat (limited to 'boost/graph')
55 files changed, 2312 insertions, 1210 deletions
diff --git a/boost/graph/adjacency_matrix.hpp b/boost/graph/adjacency_matrix.hpp index ade7351fb8..571bc3d3d1 100644 --- a/boost/graph/adjacency_matrix.hpp +++ b/boost/graph/adjacency_matrix.hpp @@ -14,9 +14,9 @@ #include <boost/config.hpp> #include <vector> #include <memory> +#include <iterator> #include <boost/assert.hpp> #include <boost/limits.hpp> -#include <boost/iterator.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_mutability_traits.hpp> #include <boost/graph/graph_selectors.hpp> @@ -499,7 +499,11 @@ namespace boost { #if defined(BOOST_NO_STD_ALLOCATOR) typedef std::vector<StoredEdge> Matrix; #else +#if defined(BOOST_NO_CXX11_ALLOCATOR) typedef typename Allocator::template rebind<StoredEdge>::other Alloc; +#else + typedef typename std::allocator_traits<Allocator>::template rebind_alloc<StoredEdge> Alloc; +#endif typedef std::vector<StoredEdge, Alloc> Matrix; #endif typedef typename Matrix::iterator MatrixIter; diff --git a/boost/graph/astar_search.hpp b/boost/graph/astar_search.hpp index f9f86c14c6..8201b50f17 100644 --- a/boost/graph/astar_search.hpp +++ b/boost/graph/astar_search.hpp @@ -430,33 +430,89 @@ namespace boost { // Distance type is the value type of the distance map if there is one, // otherwise the value type of the weight map. - typedef - typename detail::override_const_property_result< - arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type - weight_map_type; - typedef typename boost::property_traits<weight_map_type>::value_type W; - typedef - 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; + typedef typename boost::detail::override_const_property_result< + arg_pack_type, + boost::graph::keywords::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 || detail::get_max<D>()]; - + const D zero_actual = D(); + const D zero_d = arg_pack[_distance_zero | zero_actual]; + null_visitor null_vis; + astar_visitor<null_visitor> default_visitor(null_vis); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::visitor, + dummy_property_map& + >::type vis = arg_pack[_visitor | default_visitor]; + dummy_property_map dummy_prop; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::predecessor_map, + dummy_property_map& + >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::rank_map, + D + > rank_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::rank_map, + D + >::map_type r_map = rank_map_gen(g, arg_pack); + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::distance_map, + D + > dist_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::distance_map, + D + >::map_type dist_map = dist_map_gen(g, arg_pack); + weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); + typename boost::detail::override_const_property_result< + arg_pack_type, + boost::graph::keywords::tag::vertex_index_map, + vertex_index_t, + VertexListGraph + >::type v_i_map = detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::color_map, + boost::default_color_type + >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); + std::less<D> default_compare; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_compare, + std::less<D>& + >::type dist_comp = arg_pack[_distance_compare | default_compare]; + closed_plus<D> default_combine(inf); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_combine, + closed_plus<D>& + >::type dist_comb = arg_pack[_distance_combine | default_combine]; astar_search (g, s, h, - arg_pack[_visitor | make_astar_visitor(null_visitor())], - arg_pack[_predecessor_map | dummy_property_map()], - detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), - detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack), - detail::override_const_property(arg_pack, _weight_map, g, edge_weight), - detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index), - detail::make_color_map_from_arg_pack(g, arg_pack), - arg_pack[_distance_compare | std::less<D>()], - arg_pack[_distance_combine | closed_plus<D>(inf)], + vis, + pred_map, + r_map, + dist_map, + w_map, + v_i_map, + c_map, + dist_comp, + dist_comb, inf, - arg_pack[_distance_zero | D()]); + zero_d); } - // Named parameter interfaces template <typename VertexListGraph, typename AStarHeuristic, typename P, typename T, typename R> @@ -472,28 +528,73 @@ namespace boost { // Distance type is the value type of the distance map if there is one, // otherwise the value type of the weight map. - typedef - typename detail::override_const_property_result< - arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type - weight_map_type; - typedef typename boost::property_traits<weight_map_type>::value_type W; - typedef - 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; + typedef typename boost::detail::override_const_property_result< + arg_pack_type, + boost::graph::keywords::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 || detail::get_max<D>()]; - + const D zero_actual = D(); + const D zero_d = arg_pack[_distance_zero | zero_actual]; + null_visitor null_vis; + astar_visitor<null_visitor> default_visitor(null_vis); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::visitor, + dummy_property_map& + >::type vis = arg_pack[_visitor | default_visitor]; + dummy_property_map dummy_prop; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::predecessor_map, + dummy_property_map& + >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::rank_map, + D + > rank_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::rank_map, + D + >::map_type r_map = rank_map_gen(g, arg_pack); + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::distance_map, + D + > dist_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::distance_map, + D + >::map_type dist_map = dist_map_gen(g, arg_pack); + weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); + std::less<D> default_compare; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_compare, + std::less<D>& + >::type dist_comp = arg_pack[_distance_compare | default_compare]; + closed_plus<D> default_combine(inf); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_combine, + closed_plus<D>& + >::type dist_comb = arg_pack[_distance_combine | default_combine]; astar_search_tree (g, s, h, - arg_pack[_visitor | make_astar_visitor(null_visitor())], - arg_pack[_predecessor_map | dummy_property_map()], - detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), - detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack), - detail::override_const_property(arg_pack, _weight_map, g, edge_weight), - arg_pack[_distance_compare | std::less<D>()], - arg_pack[_distance_combine | closed_plus<D>(inf)], + vis, + pred_map, + r_map, + dist_map, + w_map, + dist_comp, + dist_comb, inf, - arg_pack[_distance_zero | D()]); + zero_d); } template <typename VertexListGraph, @@ -508,25 +609,87 @@ namespace boost { using namespace boost::graph::keywords; typedef bgl_named_params<P, T, R> params_type; BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) - typedef - typename detail::override_const_property_result< - arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type - weight_map_type; + typedef typename boost::detail::override_const_property_result< + arg_pack_type, + boost::graph::keywords::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 || detail::get_max<D>()]; + const D zero_actual = D(); + const D zero_d = arg_pack[_distance_zero | zero_actual]; + null_visitor null_vis; + astar_visitor<null_visitor> default_visitor(null_vis); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::visitor, + dummy_property_map& + >::type vis = arg_pack[_visitor | default_visitor]; + dummy_property_map dummy_prop; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::predecessor_map, + dummy_property_map& + >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::rank_map, + D + > rank_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::rank_map, + D + >::map_type r_map = rank_map_gen(g, arg_pack); + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::distance_map, + D + > dist_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::distance_map, + D + >::map_type dist_map = dist_map_gen(g, arg_pack); + weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::color_map, + boost::default_color_type + >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); + typename boost::detail::override_const_property_result< + arg_pack_type, + boost::graph::keywords::tag::vertex_index_map, + vertex_index_t, + VertexListGraph + >::type v_i_map = detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index); + std::less<D> default_compare; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_compare, + std::less<D>& + >::type dist_comp = arg_pack[_distance_compare | default_compare]; + closed_plus<D> default_combine(inf); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_combine, + closed_plus<D>& + >::type dist_comb = arg_pack[_distance_combine | default_combine]; astar_search_no_init (g, s, h, - arg_pack[_visitor | make_astar_visitor(null_visitor())], - arg_pack[_predecessor_map | dummy_property_map()], - detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), - detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack), - detail::override_const_property(arg_pack, _weight_map, g, edge_weight), - detail::make_color_map_from_arg_pack(g, arg_pack), - detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index), - arg_pack[_distance_compare | std::less<D>()], - arg_pack[_distance_combine | closed_plus<D>(inf)], + vis, + pred_map, + r_map, + dist_map, + w_map, + c_map, + v_i_map, + dist_comp, + dist_comb, inf, - arg_pack[_distance_zero | D()]); + zero_d); } template <typename VertexListGraph, @@ -541,23 +704,73 @@ namespace boost { using namespace boost::graph::keywords; typedef bgl_named_params<P, T, R> params_type; BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) - typedef - typename detail::override_const_property_result< - arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type - weight_map_type; + typedef typename boost::detail::override_const_property_result< + arg_pack_type, + boost::graph::keywords::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 || detail::get_max<D>()]; + const D zero_actual = D(); + const D zero_d = arg_pack[_distance_zero | zero_actual]; + null_visitor null_vis; + astar_visitor<null_visitor> default_visitor(null_vis); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::visitor, + dummy_property_map& + >::type vis = arg_pack[_visitor | default_visitor]; + dummy_property_map dummy_prop; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::predecessor_map, + dummy_property_map& + >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::rank_map, + D + > rank_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::rank_map, + D + >::map_type r_map = rank_map_gen(g, arg_pack); + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::distance_map, + D + > dist_map_gen(zero_actual); + typename boost::detail::map_maker< + VertexListGraph, + arg_pack_type, + boost::graph::keywords::tag::distance_map, + D + >::map_type dist_map = dist_map_gen(g, arg_pack); + weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); + std::less<D> default_compare; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_compare, + std::less<D>& + >::type dist_comp = arg_pack[_distance_compare | default_compare]; + closed_plus<D> default_combine(inf); + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::distance_combine, + closed_plus<D>& + >::type dist_comb = arg_pack[_distance_combine | default_combine]; astar_search_no_init_tree (g, s, h, - arg_pack[_visitor | make_astar_visitor(null_visitor())], - arg_pack[_predecessor_map | dummy_property_map()], - detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), - detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack), - detail::override_const_property(arg_pack, _weight_map, g, edge_weight), - arg_pack[_distance_compare | std::less<D>()], - arg_pack[_distance_combine | closed_plus<D>(inf)], + vis, + pred_map, + r_map, + dist_map, + w_map, + dist_comp, + dist_comb, inf, - arg_pack[_distance_zero | D()]); + zero_d); } } // namespace boost diff --git a/boost/graph/bipartite.hpp b/boost/graph/bipartite.hpp index 74316fd537..6e2e707396 100644 --- a/boost/graph/bipartite.hpp +++ b/boost/graph/bipartite.hpp @@ -32,7 +32,7 @@ namespace boost { */ template <typename Vertex> - struct bipartite_visitor_error: std::exception + struct BOOST_SYMBOL_VISIBLE bipartite_visitor_error: std::exception { std::pair <Vertex, Vertex> witnesses; @@ -212,7 +212,7 @@ namespace boost { detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map), put_property (partition_map, color_traits <partition_color_t>::white (), on_start_vertex ())))))); } - catch (detail::bipartite_visitor_error <vertex_descriptor_t> error) + catch (const detail::bipartite_visitor_error <vertex_descriptor_t>&) { return false; } @@ -299,7 +299,7 @@ namespace boost { std::make_pair (put_property (partition_map, color_traits <partition_color_t>::white (), on_start_vertex ()), record_predecessors (predecessor_map, on_tree_edge ()))))))); } - catch (detail::bipartite_visitor_error <vertex_descriptor_t> error) + catch (const detail::bipartite_visitor_error <vertex_descriptor_t>& error) { typedef std::vector <vertex_descriptor_t> path_t; diff --git a/boost/graph/boyer_myrvold_planar_test.hpp b/boost/graph/boyer_myrvold_planar_test.hpp index dc0158687f..111c5ac4a3 100644 --- a/boost/graph/boyer_myrvold_planar_test.hpp +++ b/boost/graph/boyer_myrvold_planar_test.hpp @@ -48,33 +48,31 @@ namespace boost { //Dispatch for no planar embedding, no kuratowski subgraph isolation - typedef typename remove_const - < - typename remove_reference - < typename parameter::binding - < ArgumentPack, tag::graph>::type - >::type - >::type graph_t; - - typedef typename parameter::binding - < ArgumentPack, + typedef typename remove_const< + typename parameter::value_type<ArgumentPack, tag::graph>::type + >::type graph_t; + + typedef typename property_map< + graph_t, + vertex_index_t + >::const_type vertex_default_index_map_t; + + typedef typename parameter::value_type< + ArgumentPack, tag::vertex_index_map, - typename property_map - < typename remove_reference<graph_t>::type, - vertex_index_t>::const_type - >::type vertex_index_map_t; + vertex_default_index_map_t + >::type vertex_index_map_t; + graph_t const& g = args[graph]; + vertex_default_index_map_t v_d_map = get(vertex_index, g); + vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; boyer_myrvold_impl <graph_t, vertex_index_map_t, graph::detail::no_old_handles, graph::detail::no_embedding > - planarity_tester(args[graph], - args[vertex_index_map | - get(vertex_index, args[graph]) - ] - ); + planarity_tester(g, v_i_map); return planarity_tester.is_planar() ? true : false; } @@ -88,40 +86,51 @@ namespace boost ) { //Dispatch for no planar embedding, kuratowski subgraph isolation - typedef typename remove_const - < - typename remove_reference - < typename parameter::binding - < ArgumentPack, tag::graph>::type - >::type - >::type graph_t; - - typedef typename parameter::binding - < ArgumentPack, + typedef typename remove_const< + typename parameter::value_type<ArgumentPack, tag::graph>::type + >::type graph_t; + + typedef typename property_map< + graph_t, + vertex_index_t + >::const_type vertex_default_index_map_t; + + typedef typename parameter::value_type< + ArgumentPack, tag::vertex_index_map, - typename property_map<graph_t, vertex_index_t>::type - >::type vertex_index_map_t; - + vertex_default_index_map_t + >::type vertex_index_map_t; + + typedef typename property_map< + graph_t, + edge_index_t + >::const_type edge_default_index_map_t; + + typedef typename parameter::value_type< + ArgumentPack, + tag::edge_index_map, + edge_default_index_map_t + >::type edge_index_map_t; + + graph_t const& g = args[graph]; + vertex_default_index_map_t v_d_map = get(vertex_index, g); + vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; + edge_default_index_map_t e_d_map = get(edge_index, g); + edge_index_map_t e_i_map = args[edge_index_map | e_d_map]; boyer_myrvold_impl <graph_t, vertex_index_map_t, graph::detail::store_old_handles, graph::detail::no_embedding > - planarity_tester(args[graph], - args[vertex_index_map | - get(vertex_index, args[graph]) - ] - ); + planarity_tester(g, v_i_map); if (planarity_tester.is_planar()) return true; else { planarity_tester.extract_kuratowski_subgraph - (args[kuratowski_subgraph], - args[edge_index_map|get(edge_index, args[graph])] - ); + (args[kuratowski_subgraph], e_i_map); return false; } } @@ -136,20 +145,24 @@ namespace boost ) { //Dispatch for planar embedding, no kuratowski subgraph isolation - typedef typename remove_const - < - typename remove_reference - < typename parameter::binding - < ArgumentPack, tag::graph>::type - >::type - >::type graph_t; - - typedef typename parameter::binding - < ArgumentPack, - tag::vertex_index_map, - typename property_map<graph_t, vertex_index_t>::type - >::type vertex_index_map_t; + typedef typename remove_const< + typename parameter::value_type<ArgumentPack, tag::graph>::type + >::type graph_t; + typedef typename property_map< + graph_t, + vertex_index_t + >::const_type vertex_default_index_map_t; + + typedef typename parameter::value_type< + ArgumentPack, + tag::vertex_index_map, + vertex_default_index_map_t + >::type vertex_index_map_t; + + graph_t const& g = args[graph]; + vertex_default_index_map_t v_d_map = get(vertex_index, g); + vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; boyer_myrvold_impl <graph_t, vertex_index_map_t, @@ -160,11 +173,7 @@ namespace boost graph::detail::recursive_lazy_list #endif > - planarity_tester(args[graph], - args[vertex_index_map | - get(vertex_index, args[graph]) - ] - ); + planarity_tester(g, v_i_map); if (planarity_tester.is_planar()) { @@ -184,20 +193,37 @@ namespace boost ) { //Dispatch for planar embedding, kuratowski subgraph isolation - typedef typename remove_const - < - typename remove_reference - < typename parameter::binding - < ArgumentPack, tag::graph>::type - >::type - >::type graph_t; - - typedef typename parameter::binding - < ArgumentPack, - tag::vertex_index_map, - typename property_map<graph_t, vertex_index_t>::type - >::type vertex_index_map_t; - + typedef typename remove_const< + typename parameter::value_type<ArgumentPack, tag::graph>::type + >::type graph_t; + + typedef typename property_map< + graph_t, + vertex_index_t + >::const_type vertex_default_index_map_t; + + typedef typename parameter::value_type< + ArgumentPack, + tag::vertex_index_map, + vertex_default_index_map_t + >::type vertex_index_map_t; + + typedef typename property_map< + graph_t, + edge_index_t + >::const_type edge_default_index_map_t; + + typedef typename parameter::value_type< + ArgumentPack, + tag::edge_index_map, + edge_default_index_map_t + >::type edge_index_map_t; + + graph_t const& g = args[graph]; + vertex_default_index_map_t v_d_map = get(vertex_index, g); + vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; + edge_default_index_map_t e_d_map = get(edge_index, g); + edge_index_map_t e_i_map = args[edge_index_map | e_d_map]; boyer_myrvold_impl <graph_t, vertex_index_map_t, @@ -208,11 +234,7 @@ namespace boost graph::detail::recursive_lazy_list #endif > - planarity_tester(args[graph], - args[vertex_index_map | - get(vertex_index, args[graph]) - ] - ); + planarity_tester(g, v_i_map); if (planarity_tester.is_planar()) { @@ -222,9 +244,7 @@ namespace boost else { planarity_tester.extract_kuratowski_subgraph - (args[kuratowski_subgraph], - args[edge_index_map | get(edge_index, args[graph])] - ); + (args[kuratowski_subgraph], e_i_map); return false; } } diff --git a/boost/graph/breadth_first_search.hpp b/boost/graph/breadth_first_search.hpp index b0d10ad5f3..6201076746 100644 --- a/boost/graph/breadth_first_search.hpp +++ b/boost/graph/breadth_first_search.hpp @@ -24,11 +24,10 @@ #include <boost/graph/overloading.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/two_bit_color_map.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/concept/assert.hpp> -#ifdef BOOST_GRAPH_USE_MPI -#include <boost/graph/distributed/concepts.hpp> -#endif // BOOST_GRAPH_USE_MPI +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/concepts.hpp>) namespace boost { @@ -405,9 +404,7 @@ namespace boost { } // namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/breadth_first_search.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/breadth_first_search.hpp>) #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP diff --git a/boost/graph/bron_kerbosch_all_cliques.hpp b/boost/graph/bron_kerbosch_all_cliques.hpp index b663cf95f0..1dcc04975c 100644 --- a/boost/graph/bron_kerbosch_all_cliques.hpp +++ b/boost/graph/bron_kerbosch_all_cliques.hpp @@ -84,7 +84,7 @@ namespace boost // number = {1}, // year = {2006}, // pages = {28-42} -// ee = {http://dx.doi.org/10.1016/j.tcs.2006.06.015} +// ee = {https://doi.org/10.1016/j.tcs.2006.06.015} // } /** diff --git a/boost/graph/connected_components.hpp b/boost/graph/connected_components.hpp index 9279110f19..117e6a82cd 100644 --- a/boost/graph/connected_components.hpp +++ b/boost/graph/connected_components.hpp @@ -16,6 +16,7 @@ #include <boost/graph/properties.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/overloading.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/static_assert.hpp> #include <boost/concept/assert.hpp> @@ -100,8 +101,6 @@ namespace boost { } // namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/connected_components.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/connected_components.hpp>) #endif // BOOST_GRAPH_CONNECTED_COMPONENTS_HPP diff --git a/boost/graph/copy.hpp b/boost/graph/copy.hpp index 6246ebceb1..77aebcde1b 100644 --- a/boost/graph/copy.hpp +++ b/boost/graph/copy.hpp @@ -395,7 +395,7 @@ namespace boost { CopyVertex cv, CopyEdge ce) : g_out(graph), orig2copy(c), copy_vertex(cv), copy_edge(ce) { } - template <class Vertex, class Graph> + template <class Vertex> typename graph_traits<NewGraph>::vertex_descriptor copy_one_vertex(Vertex u) const { typename graph_traits<NewGraph>::vertex_descriptor new_u = add_vertex(g_out); diff --git a/boost/graph/cycle_canceling.hpp b/boost/graph/cycle_canceling.hpp index 46a4b864c8..bc7e69099f 100644 --- a/boost/graph/cycle_canceling.hpp +++ b/boost/graph/cycle_canceling.hpp @@ -1,6 +1,6 @@ //======================================================================= // Copyright 2013 University of Warsaw. -// Authors: Piotr Wygocki +// Authors: Piotr Wygocki // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at @@ -12,7 +12,7 @@ // by Ahuja, Magnanti, Orlin. #ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP -#define BOOST_GRAPH_CYCLE_CANCELING_HPP +#define BOOST_GRAPH_CYCLE_CANCELING_HPP #include <numeric> @@ -20,7 +20,6 @@ #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/pending/indirect_cmp.hpp> -#include <boost/pending/relaxed_heap.hpp> #include <boost/graph/bellman_ford_shortest_paths.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/detail/augment.hpp> @@ -32,11 +31,11 @@ namespace boost { namespace detail { template <typename PredEdgeMap, typename Vertex> -class RecordEdgeMapAndCycleVertex +class RecordEdgeMapAndCycleVertex : public bellman_visitor<edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> > { typedef edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> PredRec; public: - RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex & v) : + RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex & v) : bellman_visitor<PredRec>(PredRec(pred)), m_v(v), m_pred(pred) {} template <typename Graph, typename Edge> @@ -63,27 +62,27 @@ template <class Graph, class Pred, class Distance, class Reversed, class Residua void cycle_canceling(const Graph &g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, Distance distance) { typedef filtered_graph<const Graph, is_residual_edge<ResidualCapacity> > ResGraph; ResGraph gres = detail::residual_graph(g, residual_capacity); - + typedef graph_traits<ResGraph> ResGTraits; typedef graph_traits<Graph> GTraits; typedef typename ResGTraits::edge_descriptor edge_descriptor; typedef typename ResGTraits::vertex_descriptor vertex_descriptor; - + typename GTraits::vertices_size_type N = num_vertices(g); - + BGL_FORALL_VERTICES_T(v, g, Graph) { put(pred, v, edge_descriptor()); put(distance, v, 0); } vertex_descriptor cycleStart; - while(!bellman_ford_shortest_paths(gres, N, + while(!bellman_ford_shortest_paths(gres, N, weight_map(weight). distance_map(distance). visitor(detail::RecordEdgeMapAndCycleVertex<Pred, vertex_descriptor>(pred, cycleStart)))) { detail::augment(g, cycleStart, cycleStart, pred, residual_capacity, rev); - + BGL_FORALL_VERTICES_T(v, g, Graph) { put(pred, v, edge_descriptor()); put(distance, v, 0); @@ -97,7 +96,7 @@ namespace detail { template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance> void cycle_canceling_dispatch2( - const Graph &g, + const Graph &g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, @@ -110,7 +109,7 @@ void cycle_canceling_dispatch2( //setting default distance map template <class Graph, class P, class T, class R, class Pred, class ResidualCapacity, class Weight, class Reversed> void cycle_canceling_dispatch2( - Graph &g, + Graph &g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, @@ -121,27 +120,27 @@ void cycle_canceling_dispatch2( std::vector<D> d_map(num_vertices(g)); - cycle_canceling(g, weight, rev, residual_capacity, pred, + cycle_canceling(g, weight, rev, residual_capacity, pred, make_iterator_property_map(d_map.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index))); } template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred> void cycle_canceling_dispatch1( - Graph &g, - Weight weight, + Graph &g, + Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, const bgl_named_params<P, T, R>& params) { - cycle_canceling_dispatch2(g, weight, rev,residual_capacity, pred, + cycle_canceling_dispatch2(g, weight, rev,residual_capacity, pred, get_param(params, vertex_distance), params); } //setting default predecessors map template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed> void cycle_canceling_dispatch1( - Graph &g, - Weight weight, + Graph &g, + Weight weight, Reversed rev, ResidualCapacity residual_capacity, param_not_found, @@ -151,7 +150,7 @@ void cycle_canceling_dispatch1( cycle_canceling_dispatch2(g, weight, rev, residual_capacity, make_iterator_property_map(p_map.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)), - get_param(params, vertex_distance), params); + get_param(params, vertex_distance), params); } }//detail @@ -159,12 +158,12 @@ void cycle_canceling_dispatch1( template <class Graph, class P, class T, class R> void cycle_canceling(Graph &g, const bgl_named_params<P, T, R>& params) { - cycle_canceling_dispatch1(g, + cycle_canceling_dispatch1(g, choose_const_pmap(get_param(params, edge_weight), g, edge_weight), choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), - choose_pmap(get_param(params, edge_residual_capacity), + choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity), - get_param(params, vertex_predecessor), + get_param(params, vertex_predecessor), params); } @@ -178,4 +177,3 @@ void cycle_canceling(Graph &g) { } #endif /* BOOST_GRAPH_CYCLE_CANCELING_HPP */ - diff --git a/boost/graph/depth_first_search.hpp b/boost/graph/depth_first_search.hpp index cf60e1ac84..0a29de1da5 100644 --- a/boost/graph/depth_first_search.hpp +++ b/boost/graph/depth_first_search.hpp @@ -19,6 +19,7 @@ #include <boost/graph/properties.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/named_function_params.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/ref.hpp> #include <boost/implicit_cast.hpp> #include <boost/optional.hpp> @@ -102,7 +103,7 @@ namespace boost { // The corresponding context shift back from the adjacent vertex occurs // after all of its out-edges have been examined. // - // See http://lists.boost.org/MailArchives/boost/msg48752.php for FAQ. + // See https://lists.boost.org/Archives/boost/2003/06/49265.php for FAQ. template <class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc> @@ -366,8 +367,6 @@ namespace boost { } } // namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/depth_first_search.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/depth_first_search.hpp>) #endif diff --git a/boost/graph/detail/adjacency_list.hpp b/boost/graph/detail/adjacency_list.hpp index 6fb497d7ea..01d400ffdc 100644 --- a/boost/graph/detail/adjacency_list.hpp +++ b/boost/graph/detail/adjacency_list.hpp @@ -267,7 +267,7 @@ namespace boost { : Base(static_cast< Base const& >(x)), m_property(const_cast<self&>(x).m_property) { } self& operator=(const self& x) { // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla). - static_cast<Base&>(*this) = static_cast< Base const& >(x); + static_cast<Base&>(*this) = static_cast< Base const& >(x); m_property = const_cast<self&>(x).m_property; return *this; } @@ -277,7 +277,7 @@ namespace boost { : Base(static_cast< Base&& >(x)), m_property(std::move(x.m_property)) { } self& operator=(self&& x) { // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla). - static_cast<Base&>(*this) = static_cast< Base&& >(x); + static_cast<Base&>(*this) = static_cast< Base&& >(x); m_property = std::move(x.m_property); return *this; } @@ -2051,16 +2051,15 @@ namespace boost { if ((*ei).get_target() > u) --(*ei).get_target(); } + template <class EdgeList, class vertex_descriptor> inline void reindex_edge_list(EdgeList& el, vertex_descriptor u, boost::disallow_parallel_edge_tag) { - typename EdgeList::iterator ei = el.begin(), e_end = el.end(); - while (ei != e_end) { - typename EdgeList::value_type ce = *ei; - ++ei; - if (ce.get_target() > u) { + for(typename EdgeList::iterator ei = el.begin(); ei != el.end(); ++ei) { + if (ei->get_target() > u) { + typename EdgeList::value_type ce = *ei; el.erase(ce); --ce.get_target(); el.insert(ce); diff --git a/boost/graph/detail/array_binary_tree.hpp b/boost/graph/detail/array_binary_tree.hpp index fd403d1f30..a594ba6bf8 100644 --- a/boost/graph/detail/array_binary_tree.hpp +++ b/boost/graph/detail/array_binary_tree.hpp @@ -14,7 +14,6 @@ #include <iterator> #include <functional> #include <boost/config.hpp> -#include <boost/iterator.hpp> namespace boost { @@ -43,9 +42,12 @@ public: struct children_type { struct iterator - : boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode, - difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&> { // replace with iterator_adaptor implementation -JGS + typedef std::bidirectional_iterator_tag iterator_category; + typedef ArrayBinaryTreeNode value_type; + typedef size_type difference_type; + typedef array_binary_tree_node* pointer; + typedef ArrayBinaryTreeNode& reference; inline iterator() : i(0), n(0) { } inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } diff --git a/boost/graph/detail/empty_header.hpp b/boost/graph/detail/empty_header.hpp new file mode 100644 index 0000000000..fde3672551 --- /dev/null +++ b/boost/graph/detail/empty_header.hpp @@ -0,0 +1,10 @@ +#ifndef BOOST_GRAPH_DETAIL_EMPTY_HEADER_HPP_INCLUDED +#define BOOST_GRAPH_DETAIL_EMPTY_HEADER_HPP_INCLUDED + +// Copyright 2018 Peter Dimov +// +// Use, modification and distribution are subject to the +// Boost Software License, Version 1.0 (See accompanying file +// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) + +#endif // #ifndef BOOST_GRAPH_DETAIL_EMPTY_HEADER_HPP_INCLUDED diff --git a/boost/graph/detail/geodesic.hpp b/boost/graph/detail/geodesic.hpp index 57352b1adc..b94482ccdb 100644 --- a/boost/graph/detail/geodesic.hpp +++ b/boost/graph/detail/geodesic.hpp @@ -33,7 +33,7 @@ namespace boost // pages = {466--484}, // priority = {0}, // title = {A Graph-theoretic perspective on centrality}, -// url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005}, +// url = {https://doi.org/10.1016/j.socnet.2005.11.005}, // volume = {28}, // year = {2006} // } diff --git a/boost/graph/detail/mpi_include.hpp b/boost/graph/detail/mpi_include.hpp new file mode 100644 index 0000000000..9e1c8858aa --- /dev/null +++ b/boost/graph/detail/mpi_include.hpp @@ -0,0 +1,16 @@ +#ifndef BOOST_GRAPH_DETAIL_MPI_INCLUDE_HPP_INCLUDED +#define BOOST_GRAPH_DETAIL_MPI_INCLUDE_HPP_INCLUDED + +// Copyright 2018 Peter Dimov +// +// Use, modification and distribution are subject to the +// Boost Software License, Version 1.0 (See accompanying file +// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) + +#if defined BOOST_GRAPH_USE_MPI +# define BOOST_GRAPH_MPI_INCLUDE(x) x +#else +# define BOOST_GRAPH_MPI_INCLUDE(x) <boost/graph/detail/empty_header.hpp> +#endif + +#endif // #ifndef BOOST_GRAPH_DETAIL_MPI_INCLUDE_HPP_INCLUDED diff --git a/boost/graph/detail/read_graphviz_new.hpp b/boost/graph/detail/read_graphviz_new.hpp index 81221c0b25..8d3eea5229 100644 --- a/boost/graph/detail/read_graphviz_new.hpp +++ b/boost/graph/detail/read_graphviz_new.hpp @@ -5,13 +5,13 @@ // http://www.boost.org/LICENSE_1_0.txt) // -// read_graphviz_new.hpp - +// read_graphviz_new.hpp - // Initialize a model of the BGL's MutableGraph concept and an associated // collection of property maps using a graph expressed in the GraphViz -// DOT Language. +// DOT Language. // // Based on the grammar found at: -// http://www.graphviz.org/cvs/doc/info/lang.html +// https://web.archive.org/web/20041213234742/http://www.graphviz.org/cvs/doc/info/lang.html // // Jeremiah rewrite used grammar found at: // http://www.graphviz.org/doc/info/lang.html diff --git a/boost/graph/detail/read_graphviz_spirit.hpp b/boost/graph/detail/read_graphviz_spirit.hpp index 2ba09cc0a4..d10bbc720c 100644 --- a/boost/graph/detail/read_graphviz_spirit.hpp +++ b/boost/graph/detail/read_graphviz_spirit.hpp @@ -5,13 +5,13 @@ // http://www.boost.org/LICENSE_1_0.txt) // -// read_graphviz_spirit.hpp - +// read_graphviz_spirit.hpp - // Initialize a model of the BGL's MutableGraph concept and an associated // collection of property maps using a graph expressed in the GraphViz -// DOT Language. +// DOT Language. // // Based on the grammar found at: -// http://www.graphviz.org/cvs/doc/info/lang.html +// https://web.archive.org/web/20041213234742/http://www.graphviz.org/cvs/doc/info/lang.html // // See documentation for this code at: // http://www.boost.org/libs/graph/doc/read_graphviz.html diff --git a/boost/graph/dijkstra_shortest_paths.hpp b/boost/graph/dijkstra_shortest_paths.hpp index 10e40f828a..f4a2a2474f 100644 --- a/boost/graph/dijkstra_shortest_paths.hpp +++ b/boost/graph/dijkstra_shortest_paths.hpp @@ -22,11 +22,11 @@ #include <boost/graph/relax.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/graph/exception.hpp> -#include <boost/pending/relaxed_heap.hpp> #include <boost/graph/overloading.hpp> #include <boost/smart_ptr.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/graph/two_bit_color_map.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/property_map/property_map.hpp> #include <boost/property_map/vector_property_map.hpp> #include <boost/type_traits.hpp> @@ -53,18 +53,13 @@ namespace boost { * @param old_distance the previous distance to @p vertex */ template<typename Buffer, typename Vertex, typename DistanceType> - inline void + inline void dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance) { (void)old_distance; Q.update(vertex); } -#ifdef BOOST_GRAPH_DIJKSTRA_TESTING - // This is a misnomer now: it now just refers to the "default heap", which is - // currently d-ary (d=4) but can be changed by a #define. - static bool dijkstra_relaxed_heap = true; -#endif template <class Visitor, class Graph> struct DijkstraVisitorConcept { @@ -129,7 +124,7 @@ namespace boost { template <class Edge, class Graph> void tree_edge(Edge e, Graph& g) { - bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, + bool decreased = relax_target(e, g, m_weight, m_predecessor, m_distance, m_combine, m_compare); if (decreased) m_vis.edge_relaxed(e, g); @@ -140,7 +135,7 @@ namespace boost { void gray_target(Edge e, Graph& g) { D old_distance = get(m_distance, target(e, g)); - bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, + bool decreased = relax_target(e, g, m_weight, m_predecessor, m_distance, m_combine, m_compare); if (decreased) { dijkstra_queue_update(m_Q, target(e, g), old_distance); @@ -187,7 +182,7 @@ namespace boost { // The test here is equivalent to e_weight < 0 if m_combine has a // cancellation law, but always returns false when m_combine is a // projection operator. - if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero)) + if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero)) boost::throw_exception(negative_edge()); // End of test for negative-weight edges. @@ -345,25 +340,7 @@ namespace boost { typedef typename graph_traits<Graph>::vertex_descriptor Vertex; -#ifdef BOOST_GRAPH_DIJKSTRA_TESTING - if (!dijkstra_relaxed_heap) { - typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap> - MutableQueue; - - MutableQueue Q(num_vertices(g), icmp, index_map); - detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, - PredecessorMap, DistanceMap, Combine, Compare> - bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); - - breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color); - return; - } -#endif // BOOST_GRAPH_DIJKSTRA_TESTING - -#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP - typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue; - MutableQueue Q(num_vertices(g), icmp, index_map); -#else // Now the default: use a d-ary heap + // Now the default: use a d-ary heap boost::scoped_array<std::size_t> index_in_heap_map_holder; typedef detail::vertex_property_map_generator<Graph, IndexMap, std::size_t> @@ -374,7 +351,6 @@ namespace boost { typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare> MutableQueue; MutableQueue Q(distance, index_in_heap, compare); -#endif // Relaxed heap detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, PredecessorMap, DistanceMap, Combine, Compare> @@ -406,7 +382,7 @@ namespace boost { template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, - class DistInf, class DistZero, typename T, typename Tag, + class DistInf, class DistZero, typename T, typename Tag, typename Base> inline void dijkstra_shortest_paths @@ -429,7 +405,7 @@ namespace boost { template <class VertexListGraph, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, - class DistInf, class DistZero, typename T, typename Tag, + class DistInf, class DistZero, typename T, typename Tag, typename Base> inline void dijkstra_shortest_paths @@ -564,7 +540,7 @@ namespace boost { choose_param(get_param(params, distance_compare_t()), std::less<D>()), choose_param(get_param(params, distance_combine_t()), - closed_plus<D>(inf)), + std::plus<D>()), inf, choose_param(get_param(params, distance_zero_t()), D()), @@ -616,8 +592,6 @@ namespace boost { } // namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/dijkstra_shortest_paths.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/dijkstra_shortest_paths.hpp>) #endif // BOOST_GRAPH_DIJKSTRA_HPP diff --git a/boost/graph/dijkstra_shortest_paths_no_color_map.hpp b/boost/graph/dijkstra_shortest_paths_no_color_map.hpp index b1a9ef5890..ae8769fc6f 100644 --- a/boost/graph/dijkstra_shortest_paths_no_color_map.hpp +++ b/boost/graph/dijkstra_shortest_paths_no_color_map.hpp @@ -13,7 +13,6 @@ #include <boost/pending/indirect_cmp.hpp> #include <boost/graph/relax.hpp> -#include <boost/pending/relaxed_heap.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/iteration_macros.hpp> @@ -41,19 +40,12 @@ namespace boost { { typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typedef typename property_traits<DistanceMap>::value_type Distance; - + typedef indirect_cmp<DistanceMap, DistanceCompare> DistanceIndirectCompare; DistanceIndirectCompare distance_indirect_compare(distance_map, distance_compare); - - // Choose vertex queue type -#if BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP - typedef relaxed_heap<Vertex, DistanceIndirectCompare, VertexIndexMap> - VertexQueue; - VertexQueue vertex_queue(num_vertices(graph), - distance_indirect_compare, - index_map); -#else + + // Default - use d-ary heap (d = 4) typedef detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t> @@ -62,54 +54,53 @@ namespace boost { typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, DistanceCompare> VertexQueue; - + boost::scoped_array<std::size_t> index_in_heap_map_holder; IndexInHeapMap index_in_heap = IndexInHeapMapHelper::build(graph, index_map, - index_in_heap_map_holder); + index_in_heap_map_holder); VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare); -#endif - + // Add vertex to the queue vertex_queue.push(start_vertex); - + // Starting vertex will always be the first discovered vertex visitor.discover_vertex(start_vertex, graph); - + while (!vertex_queue.empty()) { Vertex min_vertex = vertex_queue.top(); vertex_queue.pop(); - + visitor.examine_vertex(min_vertex, graph); - + // Check if any other vertices can be reached Distance min_vertex_distance = get(distance_map, min_vertex); - + if (!distance_compare(min_vertex_distance, distance_infinity)) { // This is the minimum vertex, so all other vertices are unreachable return; } - + // Examine neighbors of min_vertex BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) { visitor.examine_edge(current_edge, graph); - + // Check if the edge has a negative weight if (distance_compare(get(weight_map, current_edge), distance_zero)) { boost::throw_exception(negative_edge()); } - + // Extract the neighboring vertex and get its distance Vertex neighbor_vertex = target(current_edge, graph); Distance neighbor_vertex_distance = get(distance_map, neighbor_vertex); - bool is_neighbor_undiscovered = + bool is_neighbor_undiscovered = !distance_compare(neighbor_vertex_distance, distance_infinity); // Attempt to relax the edge - bool was_edge_relaxed = relax(current_edge, graph, weight_map, + bool was_edge_relaxed = relax_target(current_edge, graph, weight_map, predecessor_map, distance_map, distance_weight_combine, distance_compare); - + if (was_edge_relaxed) { visitor.edge_relaxed(current_edge, graph); if (is_neighbor_undiscovered) { @@ -121,9 +112,9 @@ namespace boost { } else { visitor.edge_not_relaxed(current_edge, graph); } - + } // end out edge iteration - + visitor.finish_vertex(min_vertex, graph); } // end while queue not empty } @@ -150,17 +141,17 @@ namespace boost { // Initialize vertices BGL_FORALL_VERTICES_T(current_vertex, graph, Graph) { visitor.initialize_vertex(current_vertex, graph); - + // Default all distances to infinity put(distance_map, current_vertex, distance_infinity); - + // Default all vertex predecessors to the vertex itself put(predecessor_map, current_vertex, current_vertex); } - + // Set distance for start_vertex to zero put(distance_map, start_vertex, distance_zero); - + // Pass everything on to the no_init version dijkstra_shortest_paths_no_color_map_no_init(graph, start_vertex, predecessor_map, distance_map, weight_map, @@ -195,7 +186,7 @@ namespace boost { choose_param(get_param(params, distance_compare_t()), std::less<DistanceType>()), choose_param(get_param(params, distance_combine_t()), - closed_plus<DistanceType>(inf)), + std::plus<DistanceType>()), inf, choose_param(get_param(params, distance_zero_t()), DistanceType()), @@ -216,7 +207,7 @@ namespace boost { typedef typename property_traits<WeightMap>::value_type DistanceType; typename std::vector<DistanceType>::size_type vertex_count = is_default_param(distance_map) ? num_vertices(graph) : 1; - + std::vector<DistanceType> default_distance_map(vertex_count); detail::dijkstra_no_color_map_dispatch2 diff --git a/boost/graph/dimacs.hpp b/boost/graph/dimacs.hpp index 3e8407dfab..12adba81e6 100644 --- a/boost/graph/dimacs.hpp +++ b/boost/graph/dimacs.hpp @@ -21,7 +21,7 @@ namespace boost { namespace graph { -class dimacs_exception : public std::exception {}; +class BOOST_SYMBOL_VISIBLE dimacs_exception : public std::exception {}; class dimacs_basic_reader { public: diff --git a/boost/graph/distributed/detail/mpi_process_group.ipp b/boost/graph/distributed/detail/mpi_process_group.ipp index c157387be9..94050da9c2 100644 --- a/boost/graph/distributed/detail/mpi_process_group.ipp +++ b/boost/graph/distributed/detail/mpi_process_group.ipp @@ -839,10 +839,19 @@ all_gather(const mpi_process_group& pg, InputIterator first, &sizes[0], 1, MPI_INT, communicator(pg)); BOOST_ASSERT(result == MPI_SUCCESS); + (void)result; // Adjust sizes based on the number of bytes - std::transform(sizes.begin(), sizes.end(), sizes.begin(), - std::bind2nd(std::multiplies<int>(), sizeof(T))); + // + // std::transform(sizes.begin(), sizes.end(), sizes.begin(), + // std::bind2nd(std::multiplies<int>(), sizeof(T))); + // + // std::bind2nd has been removed from C++17 + + for( std::size_t i = 0, n = sizes.size(); i < n; ++i ) + { + sizes[ i ] *= sizeof( T ); + } // Compute displacements std::vector<int> displacements; @@ -880,6 +889,7 @@ process_subgroup(const mpi_process_group& pg, MPI_Group current_group; int result = MPI_Comm_group(communicator(pg), ¤t_group); BOOST_ASSERT(result == MPI_SUCCESS); + (void)result; MPI_Group new_group; result = MPI_Group_incl(current_group, ranks.size(), &ranks[0], &new_group); diff --git a/boost/graph/exception.hpp b/boost/graph/exception.hpp index 382d671928..f1f13dcf89 100644 --- a/boost/graph/exception.hpp +++ b/boost/graph/exception.hpp @@ -15,36 +15,36 @@ namespace boost { - struct bad_graph : public std::invalid_argument { + struct BOOST_SYMBOL_VISIBLE bad_graph : public std::invalid_argument { bad_graph(const std::string& what_arg) : std::invalid_argument(what_arg) { } }; - struct not_a_dag : public bad_graph { + struct BOOST_SYMBOL_VISIBLE not_a_dag : public bad_graph { not_a_dag() : bad_graph("The graph must be a DAG.") { } }; - struct negative_edge : public bad_graph { + struct BOOST_SYMBOL_VISIBLE negative_edge : public bad_graph { negative_edge() : bad_graph("The graph may not contain an edge with negative weight.") { } }; - struct negative_cycle : public bad_graph { + struct BOOST_SYMBOL_VISIBLE negative_cycle : public bad_graph { negative_cycle() : bad_graph("The graph may not contain negative cycles.") { } }; - struct not_connected : public bad_graph { + struct BOOST_SYMBOL_VISIBLE not_connected : public bad_graph { not_connected() : bad_graph("The graph must be connected.") { } }; - struct not_complete : public bad_graph { + struct BOOST_SYMBOL_VISIBLE not_complete : public bad_graph { not_complete() : bad_graph("The graph must be complete.") { } diff --git a/boost/graph/exterior_property.hpp b/boost/graph/exterior_property.hpp index af6df8180b..f920939f3a 100644 --- a/boost/graph/exterior_property.hpp +++ b/boost/graph/exterior_property.hpp @@ -14,8 +14,7 @@ namespace boost { namespace detail { // The vector matrix provides a little abstraction over vector - // types that makes matrices easier to work with. Note that it's - // non-copyable, meaning you should be passing it by value. + // types that makes matrices easier to work with. template <typename Value> struct vector_matrix { @@ -28,7 +27,7 @@ namespace detail { typedef container_type* pointer; typedef typename matrix_type::size_type size_type; - // Instantiate the matrix over n elements (creates an nxn matrix). + // Instantiate the matrix over n elements (creates an n by n matrix). // The graph has to be passed in order to ensure the index maps // are constructed correctly when returning indexible elements. inline vector_matrix(size_type n) diff --git a/boost/graph/fruchterman_reingold.hpp b/boost/graph/fruchterman_reingold.hpp index 01d080a418..24e1ae8cfa 100644 --- a/boost/graph/fruchterman_reingold.hpp +++ b/boost/graph/fruchterman_reingold.hpp @@ -14,6 +14,7 @@ #include <boost/graph/named_function_params.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/topology.hpp> // For topology concepts +#include <boost/graph/detail/mpi_include.hpp> #include <vector> #include <list> #include <algorithm> // for std::min and std::max @@ -433,8 +434,6 @@ fruchterman_reingold_force_directed_layout } // end namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/fruchterman_reingold.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/fruchterman_reingold.hpp>) #endif // BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP diff --git a/boost/graph/graph_test.hpp b/boost/graph/graph_test.hpp deleted file mode 100644 index 69d89f34f2..0000000000 --- a/boost/graph/graph_test.hpp +++ /dev/null @@ -1,384 +0,0 @@ -//======================================================================= -// Copyright 2002 Indiana University. -// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek -// -// Distributed under the Boost Software License, Version 1.0. (See -// accompanying file LICENSE_1_0.txt or copy at -// http://www.boost.org/LICENSE_1_0.txt) -//======================================================================= - -#ifndef BOOST_GRAPH_TEST_HPP -#define BOOST_GRAPH_TEST_HPP - -#include <vector> -#include <boost/test/minimal.hpp> -#include <boost/graph/filtered_graph.hpp> -#include <boost/graph/iteration_macros.hpp> -#include <boost/graph/isomorphism.hpp> -#include <boost/graph/copy.hpp> -#include <boost/graph/graph_utility.hpp> // for connects -#include <boost/range.hpp> -#include <boost/range/algorithm/find_if.hpp> - - -// UNDER CONSTRUCTION - -namespace boost { - - template <typename Graph> - struct graph_test - { - - typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; - typedef typename graph_traits<Graph>::edge_descriptor edge_t; - typedef typename graph_traits<Graph>::vertices_size_type v_size_t; - typedef typename graph_traits<Graph>::degree_size_type deg_size_t; - typedef typename graph_traits<Graph>::edges_size_type e_size_t; - typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter; - typedef typename property_map<Graph, vertex_index_t>::type index_map_t; - typedef iterator_property_map<typename std::vector<vertex_t>::iterator, - index_map_t,vertex_t,vertex_t&> IsoMap; - - struct ignore_vertex { - ignore_vertex() { } - ignore_vertex(vertex_t v) : v(v) { } - bool operator()(vertex_t x) const { return x != v; } - vertex_t v; - }; - struct ignore_edge { - ignore_edge() { } - ignore_edge(edge_t e) : e(e) { } - bool operator()(edge_t x) const { return x != e; } - edge_t e; - }; - struct ignore_edges { - ignore_edges(vertex_t s, vertex_t t, const Graph& g) - : s(s), t(t), g(g) { } - bool operator()(edge_t x) const { - return !(source(x, g) == s && target(x, g) == t); - } - vertex_t s; vertex_t t; const Graph& g; - }; - - //========================================================================= - // Traversal Operations - - void test_incidence_graph - (const std::vector<vertex_t>& vertex_set, - const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, - const Graph& g) - { - typedef typename std::vector<vertex_t>::const_iterator vertex_iter; - typedef typename std::vector< std::pair<vertex_t, vertex_t> > - ::const_iterator edge_iter; - typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter; - - for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) { - vertex_t u = *ui; - std::vector<vertex_t> adj; - for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) - if (e->first == u) - adj.push_back(e->second); - - std::pair<out_edge_iter, out_edge_iter> p = out_edges(u, g); - BOOST_CHECK(out_degree(u, g) == adj.size()); - BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) - == out_degree(u, g)); - for (; p.first != p.second; ++p.first) { - edge_t e = *p.first; - BOOST_CHECK(source(e, g) == u); - BOOST_CHECK(container_contains(adj, target(e, g)) == true); - } - } - } - - void test_bidirectional_graph - (const std::vector<vertex_t>& vertex_set, - const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, - const Graph& g) - { - typedef typename std::vector<vertex_t>::const_iterator vertex_iter; - typedef typename std::vector< std::pair<vertex_t, vertex_t> > - ::const_iterator edge_iter; - typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iter; - - for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) { - vertex_t v = *vi; - std::vector<vertex_t> inv_adj; - for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) - if (e->second == v) - inv_adj.push_back(e->first); - - std::pair<in_edge_iter, in_edge_iter> p = in_edges(v, g); - BOOST_CHECK(in_degree(v, g) == inv_adj.size()); - BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) - == in_degree(v, g)); - for (; p.first != p.second; ++p.first) { - edge_t e = *p.first; - BOOST_CHECK(target(e, g) == v); - BOOST_CHECK(container_contains(inv_adj, source(e, g)) == true); - } - } - } - - void test_adjacency_graph - (const std::vector<vertex_t>& vertex_set, - const std::vector< std::pair<vertex_t,vertex_t> >& edge_set, - const Graph& g) - { - typedef typename std::vector<vertex_t>::const_iterator vertex_iter; - typedef typename std::vector<std::pair<vertex_t,vertex_t> > - ::const_iterator edge_iter; - typedef typename graph_traits<Graph>::adjacency_iterator adj_iter; - - for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) { - vertex_t u = *ui; - std::vector<vertex_t> adj; - for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e) - if (e->first == u) - adj.push_back(e->second); - - std::pair<adj_iter, adj_iter> p = adjacent_vertices(u, g); - BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) == adj.size()); - for (; p.first != p.second; ++p.first) { - vertex_t v = *p.first; - BOOST_CHECK(container_contains(adj, v) == true); - } - } - } - - void test_vertex_list_graph - (const std::vector<vertex_t>& vertex_set, const Graph& g) - { - typedef typename graph_traits<Graph>::vertex_iterator v_iter; - std::pair<v_iter, v_iter> p = vertices(g); - BOOST_CHECK(num_vertices(g) == vertex_set.size()); - v_size_t n = (size_t)std::distance(p.first, p.second); - BOOST_CHECK(n == num_vertices(g)); - for (; p.first != p.second; ++p.first) { - vertex_t v = *p.first; - BOOST_CHECK(container_contains(vertex_set, v) == true); - } - } - - void test_edge_list_graph - (const std::vector<vertex_t>& vertex_set, - const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, - const Graph& g) - { - typedef typename graph_traits<Graph>::edge_iterator e_iter; - std::pair<e_iter, e_iter> p = edges(g); - BOOST_CHECK(num_edges(g) == edge_set.size()); - e_size_t m = std::distance(p.first, p.second); - BOOST_CHECK(m == num_edges(g)); - for (; p.first != p.second; ++p.first) { - edge_t e = *p.first; - BOOST_CHECK(find_if(edge_set, connects(source(e, g), target(e, g), g)) != boost::end(edge_set)); - BOOST_CHECK(container_contains(vertex_set, source(e, g)) == true); - BOOST_CHECK(container_contains(vertex_set, target(e, g)) == true); - } - } - - void test_adjacency_matrix - (const std::vector<vertex_t>& vertex_set, - const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, - const Graph& g) - { - std::pair<edge_t, bool> p; - for (typename std::vector<std::pair<vertex_t, vertex_t> > - ::const_iterator i = edge_set.begin(); - i != edge_set.end(); ++i) { - p = edge(i->first, i->second, g); - BOOST_CHECK(p.second == true); - BOOST_CHECK(source(p.first, g) == i->first); - BOOST_CHECK(target(p.first, g) == i->second); - } - typename std::vector<vertex_t>::const_iterator j, k; - for (j = vertex_set.begin(); j != vertex_set.end(); ++j) - for (k = vertex_set.begin(); k != vertex_set.end(); ++k) { - p = edge(*j, *k, g); - if (p.second == true) - BOOST_CHECK(find_if(edge_set, - connects(source(p.first, g), target(p.first, g), g)) != boost::end(edge_set)); - } - } - - //========================================================================= - // Mutating Operations - - void test_add_vertex(Graph& g) - { - Graph cpy; - std::vector<vertex_t> iso_vec(num_vertices(g)); - IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); - copy_graph(g, cpy, orig_to_copy(iso_map)); - - BOOST_CHECK((verify_isomorphism(g, cpy, iso_map))); - - vertex_t v = add_vertex(g); - - BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1); - - BOOST_CHECK(out_degree(v, g) == 0); - - // Make sure the rest of the graph stayed the same - BOOST_CHECK((verify_isomorphism - (make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy, - iso_map))); - } - - void test_add_edge(vertex_t u, vertex_t v, Graph& g) - { - Graph cpy; - std::vector<vertex_t> iso_vec(num_vertices(g)); - IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); - copy_graph(g, cpy, orig_to_copy(iso_map)); - - bool parallel_edge_exists = container_contains(adjacent_vertices(u, g), v); - - std::pair<edge_t, bool> p = add_edge(u, v, g); - edge_t e = p.first; - bool added = p.second; - - if (is_undirected(g) && u == v) // self edge - BOOST_CHECK(added == false); - else if (parallel_edge_exists) - BOOST_CHECK(allows_parallel_edges(g) && added == true - || !allows_parallel_edges(g) && added == false); - else - BOOST_CHECK(added == true); - - if (p.second == true) { // edge added - BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1); - - BOOST_CHECK(container_contains(out_edges(u, g), e) == true); - - BOOST_CHECK((verify_isomorphism - (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map))); - } - else { // edge not added - if (! (is_undirected(g) && u == v)) { - // e should be a parallel edge - BOOST_CHECK(source(e, g) == u); - BOOST_CHECK(target(e, g) == v); - } - // The graph should not be changed. - BOOST_CHECK((verify_isomorphism(g, cpy, iso_map))); - } - } // test_add_edge() - - - void test_remove_edge(vertex_t u, vertex_t v, Graph& g) - { - Graph cpy; - std::vector<vertex_t> iso_vec(num_vertices(g)); - IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); - copy_graph(g, cpy, orig_to_copy(iso_map)); - - deg_size_t occurances = count(adjacent_vertices(u, g), v); - - remove_edge(u, v, g); - - BOOST_CHECK(num_edges(g) + occurances == num_edges(cpy)); - BOOST_CHECK((verify_isomorphism - (g, make_filtered_graph(cpy, ignore_edges(u,v,cpy)), - iso_map))); - } - - void test_remove_edge(edge_t e, Graph& g) - { - Graph cpy; - std::vector<vertex_t> iso_vec(num_vertices(g)); - IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); - copy_graph(g, cpy, orig_to_copy(iso_map)); - - vertex_t u = source(e, g), v = target(e, g); - deg_size_t occurances = count(adjacent_vertices(u, g), v); - - remove_edge(e, g); - - BOOST_CHECK(num_edges(g) + 1 == num_edges(cpy)); - BOOST_CHECK(count(adjacent_vertices(u, g), v) + 1 == occurances); - BOOST_CHECK((verify_isomorphism - (g, make_filtered_graph(cpy, ignore_edge(e)), - iso_map))); - } - - void test_clear_vertex(vertex_t v, Graph& g) - { - Graph cpy; - std::vector<vertex_t> iso_vec(num_vertices(g)); - IsoMap iso_map(iso_vec.begin(), get(vertex_index, g)); - copy_graph(g, cpy, orig_to_copy(iso_map)); - - clear_vertex(v, g); - - BOOST_CHECK(out_degree(v, g) == 0); - BOOST_CHECK(num_vertices(g) == num_vertices(cpy)); - BOOST_CHECK((verify_isomorphism - (g, make_filtered_graph(cpy, keep_all(), ignore_vertex(v)), - iso_map))); - } - - //========================================================================= - // Property Map - - template <typename PropVal, typename PropertyTag> - void test_readable_vertex_property_graph - (const std::vector<PropVal>& vertex_prop, PropertyTag tag, const Graph& g) - { - typedef typename property_map<Graph, PropertyTag>::const_type const_Map; - const_Map pmap = get(tag, g); - typename std::vector<PropVal>::const_iterator i = vertex_prop.begin(); - - for (typename boost::graph_traits<Graph>::vertex_iterator - bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; - bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9) - for (typename boost::graph_traits<Graph>::vertex_descriptor v; - bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false; - ++bgl_first_9) { - //BGL_FORALL_VERTICES_T(v, g, Graph) { - typename property_traits<const_Map>::value_type - pval1 = get(pmap, v), pval2 = get(tag, g, v); - BOOST_CHECK(pval1 == pval2); - BOOST_CHECK(pval1 == *i++); - } - } - - template <typename PropVal, typename PropertyTag> - void test_vertex_property_graph - (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g) - { - typedef typename property_map<Graph, PropertyTag>::type PMap; - PMap pmap = get(tag, g); - typename std::vector<PropVal>::const_iterator i = vertex_prop.begin(); - for (typename boost::graph_traits<Graph>::vertex_iterator - bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; - bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9) - for (typename boost::graph_traits<Graph>::vertex_descriptor v; - bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false; - ++bgl_first_9) - // BGL_FORALL_VERTICES_T(v, g, Graph) - put(pmap, v, *i++); - - test_readable_vertex_property_graph(vertex_prop, tag, g); - - BGL_FORALL_VERTICES_T(v, g, Graph) - put(pmap, v, vertex_prop[0]); - - typename std::vector<PropVal>::const_iterator j = vertex_prop.begin(); - BGL_FORALL_VERTICES_T(v, g, Graph) - put(tag, g, v, *j++); - - test_readable_vertex_property_graph(vertex_prop, tag, g); - } - - - }; - - -} // namespace boost - -#include <boost/graph/iteration_macros_undef.hpp> - -#endif // BOOST_GRAPH_TEST_HPP diff --git a/boost/graph/graphml.hpp b/boost/graph/graphml.hpp index a7faa647bb..9d798520ce 100644 --- a/boost/graph/graphml.hpp +++ b/boost/graph/graphml.hpp @@ -34,7 +34,7 @@ namespace boost ///////////////////////////////////////////////////////////////////////////// // Graph reader exceptions ///////////////////////////////////////////////////////////////////////////// -struct parse_error: public graph_exception +struct BOOST_SYMBOL_VISIBLE parse_error: public graph_exception { parse_error(const std::string& err) {error = err; statement = "parse error: " + error;} virtual ~parse_error() throw() {} @@ -100,7 +100,7 @@ class mutate_graph_impl : public mutate_graph mpl::for_each<value_types>(put_property<MutableGraph *,value_types> (name, m_dp, &m_g, value, value_type, m_type_names, type_found)); } - catch (bad_lexical_cast) + catch (const bad_lexical_cast&) { BOOST_THROW_EXCEPTION( parse_error("invalid value \"" + value + "\" for key " + @@ -125,7 +125,7 @@ class mutate_graph_impl : public mutate_graph (name, m_dp, any_cast<vertex_descriptor>(vertex), value, value_type, m_type_names, type_found)); } - catch (bad_lexical_cast) + catch (const bad_lexical_cast&) { BOOST_THROW_EXCEPTION( parse_error("invalid value \"" + value + "\" for key " + @@ -150,7 +150,7 @@ class mutate_graph_impl : public mutate_graph (name, m_dp, any_cast<edge_descriptor>(edge), value, value_type, m_type_names, type_found)); } - catch (bad_lexical_cast) + catch (const bad_lexical_cast&) { BOOST_THROW_EXCEPTION( parse_error("invalid value \"" + value + "\" for key " + diff --git a/boost/graph/graphviz.hpp b/boost/graph/graphviz.hpp index 1c8cb194ac..b82e11a926 100644 --- a/boost/graph/graphviz.hpp +++ b/boost/graph/graphviz.hpp @@ -27,6 +27,7 @@ #include <boost/graph/dll_import_export.hpp> #include <boost/graph/compressed_sparse_row_graph.hpp> #include <boost/graph/iteration_macros.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/spirit/include/classic_multi_pass.hpp> #include <boost/lexical_cast.hpp> #include <boost/static_assert.hpp> @@ -616,12 +617,12 @@ namespace boost { ///////////////////////////////////////////////////////////////////////////// // Graph reader exceptions ///////////////////////////////////////////////////////////////////////////// -struct graph_exception : public std::exception { +struct BOOST_SYMBOL_VISIBLE graph_exception : public std::exception { virtual ~graph_exception() throw() {} virtual const char* what() const throw() = 0; }; -struct bad_parallel_edge : public graph_exception { +struct BOOST_SYMBOL_VISIBLE bad_parallel_edge : public graph_exception { std::string from; std::string to; mutable std::string statement; @@ -639,7 +640,7 @@ struct bad_parallel_edge : public graph_exception { } }; -struct directed_graph_error : public graph_exception { +struct BOOST_SYMBOL_VISIBLE directed_graph_error : public graph_exception { virtual ~directed_graph_error() throw() {} virtual const char* what() const throw() { return @@ -648,7 +649,7 @@ struct directed_graph_error : public graph_exception { } }; -struct undirected_graph_error : public graph_exception { +struct BOOST_SYMBOL_VISIBLE undirected_graph_error : public graph_exception { virtual ~undirected_graph_error() throw() {} virtual const char* what() const throw() { return @@ -657,7 +658,7 @@ struct undirected_graph_error : public graph_exception { } }; -struct bad_graphviz_syntax: public graph_exception { +struct BOOST_SYMBOL_VISIBLE bad_graphviz_syntax: public graph_exception { std::string errmsg; bad_graphviz_syntax(const std::string& errmsg) : errmsg(errmsg) {} @@ -951,8 +952,6 @@ bool read_graphviz(std::istream& in, MutableGraph& graph, } // namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/graphviz.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/graphviz.hpp>) #endif // BOOST_GRAPHVIZ_HPP diff --git a/boost/graph/gursoy_atun_layout.hpp b/boost/graph/gursoy_atun_layout.hpp index d843db7ac3..5ac52f30e1 100644 --- a/boost/graph/gursoy_atun_layout.hpp +++ b/boost/graph/gursoy_atun_layout.hpp @@ -14,7 +14,7 @@ // "Neighbourhood Preserving Load Balancing: A Self-Organizing Approach" // in 6th International Euro-Par Conference Munich, Germany, August 29 – September 1, 2000 Proceedings, // pp 234-241 -// http://dx.doi.org/10.1007/3-540-44520-X_32 +// https://doi.org/10.1007/3-540-44520-X_32 #include <boost/config/no_tr1/cmath.hpp> #include <boost/throw_exception.hpp> @@ -183,7 +183,7 @@ gursoy_atun_step typedef detail::gursoy_shortest<EdgeWeightMap> shortest; shortest::run(graph, min_distance_loc, node_distance, update_position, weight); - } catch (detail::over_distance_limit) { + } catch (const detail::over_distance_limit&) { /* Thrown to break out of BFS or Dijkstra early */ } } diff --git a/boost/graph/isomorphism.hpp b/boost/graph/isomorphism.hpp index 225cd20513..cf70834aa6 100644 --- a/boost/graph/isomorphism.hpp +++ b/boost/graph/isomorphism.hpp @@ -501,6 +501,7 @@ fi_adj_loop_k:++fi_adj.first; template <typename Graph1, typename Graph2> struct isomorphism_impl { typedef bool result_type; + typedef result_type type; template <typename ArgPack> bool operator()(const Graph1& g1, const Graph2& g2, const ArgPack& arg_pack) const { using namespace boost::graph::keywords; diff --git a/boost/graph/loop_erased_random_walk.hpp b/boost/graph/loop_erased_random_walk.hpp index 712c45d7ca..5805c2e5bc 100644 --- a/boost/graph/loop_erased_random_walk.hpp +++ b/boost/graph/loop_erased_random_walk.hpp @@ -19,7 +19,7 @@ namespace boost { - struct loop_erased_random_walk_stuck : public std::exception { + struct BOOST_SYMBOL_VISIBLE loop_erased_random_walk_stuck : public std::exception { virtual ~loop_erased_random_walk_stuck() throw() {} inline virtual const char* what() const throw() { return "Loop-erased random walk found a vertex with no out-edges"; diff --git a/boost/graph/matrix_as_graph.hpp b/boost/graph/matrix_as_graph.hpp index fb727940d7..4e8d56b921 100644 --- a/boost/graph/matrix_as_graph.hpp +++ b/boost/graph/matrix_as_graph.hpp @@ -12,6 +12,8 @@ #define BOOST_GRAPH_MATRIX2GRAPH_HPP #include <utility> +#include <cstddef> +#include <iterator> #include <boost/config.hpp> #include <boost/operators.hpp> #include <boost/pending/detail/int_iterator.hpp> @@ -86,10 +88,14 @@ namespace boost { template <class Iter, class Vertex> class matrix_adj_iterator - : public std::iterator<std::input_iterator_tag, Vertex > { typedef matrix_adj_iterator self; public: + typedef std::input_iterator_tag iterator_category; + typedef Vertex value_type; + typedef std::ptrdiff_t difference_type; + typedef Vertex* pointer; + typedef Vertex& reference; matrix_adj_iterator() { } matrix_adj_iterator(Iter i) : _iter(i) { } matrix_adj_iterator(const self& x) : _iter(x._iter) { } @@ -105,10 +111,14 @@ namespace boost { template <class Iter, class Vertex> class matrix_incidence_iterator - : public std::iterator<std::input_iterator_tag, Iter > { typedef matrix_incidence_iterator self; public: + typedef std::input_iterator_tag iterator_category; + typedef Iter value_type; + typedef std::ptrdiff_t difference_type; + typedef Iter* pointer; + typedef Iter& reference; matrix_incidence_iterator() { } matrix_incidence_iterator(Iter i) : _iter(i) { } matrix_incidence_iterator(const self& x) : _iter(x._iter) { } diff --git a/boost/graph/max_cardinality_matching.hpp b/boost/graph/max_cardinality_matching.hpp index 1549345a2f..5b4a8b70d6 100644 --- a/boost/graph/max_cardinality_matching.hpp +++ b/boost/graph/max_cardinality_matching.hpp @@ -27,7 +27,7 @@ namespace boost { namespace graph { namespace detail { - enum { V_EVEN, V_ODD, V_UNREACHED }; + enum VERTEX_STATE { V_EVEN, V_ODD, V_UNREACHED }; } } // end namespace graph::detail template <typename Graph, typename MateMap, typename VertexIndexMap> diff --git a/boost/graph/maximum_adjacency_search.hpp b/boost/graph/maximum_adjacency_search.hpp index e27a7a048e..211bf7ee84 100644 --- a/boost/graph/maximum_adjacency_search.hpp +++ b/boost/graph/maximum_adjacency_search.hpp @@ -146,10 +146,10 @@ namespace boost { // start traversing the graph //vertex_descriptor s, t; - weight_type w; + //weight_type w; while (!pq.empty()) { // while PQ \neq {} do const vertex_descriptor u = pq.top(); // u = extractmax(PQ) - w = get(keys, u); vis.start_vertex(u, g); + /* weight_type w = */ get(keys, u); vis.start_vertex(u, g); pq.pop(); // vis.start_vertex(u, g); BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do @@ -218,9 +218,9 @@ maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, cons struct mas_dispatch { typedef void result_type; template <typename Graph, typename ArgPack> - static result_type apply(const Graph& g, - //const bgl_named_params<P,T,R>& params, - const ArgPack& params, + static result_type apply(const Graph& g, + //const bgl_named_params<P,T,R>& params, + const ArgPack& params, WeightMap w) { using namespace boost::graph::keywords; @@ -233,12 +233,25 @@ maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, cons typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params); + boost::null_visitor null_vis; + boost::mas_visitor<boost::null_visitor> default_visitor(null_vis); + vertex_descriptor v = vertex_descriptor(); + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::vertex_assignment_map, + vertex_descriptor + > map_gen(v); + typename boost::detail::map_maker< + Graph, + ArgPack, + boost::graph::keywords::tag::vertex_assignment_map, + vertex_descriptor + >::map_type default_map = map_gen(g, params); boost::maximum_adjacency_search (g, w, - params [ _visitor | make_mas_visitor(null_visitor())], + params [ _visitor | default_visitor], params [ _root_vertex | *vertices(g).first], - params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)], + params [ _vertex_assignment_map | default_map], pq ); } @@ -249,8 +262,8 @@ maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, cons typedef void result_type; template <typename Graph, typename ArgPack> - static result_type apply(const Graph& g, - const ArgPack& params, + static result_type apply(const Graph& g, + const ArgPack& params, param_not_found) { using namespace boost::graph::keywords; @@ -266,12 +279,25 @@ maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, cons typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params); + boost::null_visitor null_vis; + boost::mas_visitor<boost::null_visitor> default_visitor(null_vis); + vertex_descriptor v = vertex_descriptor(); + boost::detail::make_property_map_from_arg_pack_gen< + boost::graph::keywords::tag::vertex_assignment_map, + vertex_descriptor + > map_gen(v); + typename boost::detail::map_maker< + Graph, + ArgPack, + boost::graph::keywords::tag::vertex_assignment_map, + vertex_descriptor + >::map_type default_map = map_gen(g, params); boost::maximum_adjacency_search (g, get(edge_weight, g), - params [ _visitor | make_mas_visitor(null_visitor())], + params [ _visitor | default_visitor], params [ _root_vertex | *vertices(g).first], - params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)], + params [ _vertex_assignment_map | default_map], pq ); } diff --git a/boost/graph/maximum_weighted_matching.hpp b/boost/graph/maximum_weighted_matching.hpp new file mode 100644 index 0000000000..6fbc4dd422 --- /dev/null +++ b/boost/graph/maximum_weighted_matching.hpp @@ -0,0 +1,1167 @@ +//======================================================================= +// Copyright (c) 2018 Yi Ji +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +//======================================================================= + +#ifndef BOOST_GRAPH_MAXIMUM_WEIGHTED_MATCHING_HPP +#define BOOST_GRAPH_MAXIMUM_WEIGHTED_MATCHING_HPP + +#include <algorithm> // for std::iter_swap +#include <boost/shared_ptr.hpp> +#include <boost/make_shared.hpp> +#include <boost/graph/max_cardinality_matching.hpp> + +namespace boost +{ + template <typename Graph, typename MateMap, typename VertexIndexMap> + typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type + matching_weight_sum(const Graph& g, MateMap mate, VertexIndexMap vm) + { + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t; + typedef typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type edge_property_t; + + edge_property_t weight_sum = 0; + vertex_iterator_t vi, vi_end; + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + vertex_descriptor_t v = *vi; + if (get(mate, v) != graph_traits<Graph>::null_vertex() && get(vm, v) < get(vm, get(mate,v))) + weight_sum += get(edge_weight, g, edge(v,mate[v],g).first); + } + return weight_sum; + } + + template <typename Graph, typename MateMap> + inline typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type + matching_weight_sum(const Graph& g, MateMap mate) + { + return matching_weight_sum(g, mate, get(vertex_index,g)); + } + + template <typename Graph, typename MateMap, typename VertexIndexMap> + class weighted_augmenting_path_finder + { + public: + + template <typename T> + struct map_vertex_to_ + { + typedef boost::iterator_property_map<typename std::vector<T>::iterator, VertexIndexMap> type; + }; + typedef typename graph::detail::VERTEX_STATE vertex_state_t; + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t; + typedef typename std::vector<vertex_descriptor_t>::const_iterator vertex_vec_iter_t; + typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator_t; + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor_t; + typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t; + typedef typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type edge_property_t; + typedef std::deque<vertex_descriptor_t> vertex_list_t; + typedef std::vector<edge_descriptor_t> edge_list_t; + typedef typename map_vertex_to_<vertex_descriptor_t>::type vertex_to_vertex_map_t; + typedef typename map_vertex_to_<edge_property_t>::type vertex_to_weight_map_t; + typedef typename map_vertex_to_<bool>::type vertex_to_bool_map_t; + typedef typename map_vertex_to_<std::pair<vertex_descriptor_t, vertex_descriptor_t> >::type vertex_to_pair_map_t; + typedef typename map_vertex_to_<std::pair<edge_descriptor_t, bool> >::type vertex_to_edge_map_t; + typedef typename map_vertex_to_<vertex_to_edge_map_t>::type vertex_pair_to_edge_map_t; + + class blossom + { + public: + + typedef boost::shared_ptr<blossom> blossom_ptr_t; + std::vector<blossom_ptr_t> sub_blossoms; + edge_property_t dual_var; + blossom_ptr_t father; + + blossom() : dual_var(0), father(blossom_ptr_t()) {} + + // get the base vertex of a blossom by recursively getting + // its base sub-blossom, which is always the first one in + // sub_blossoms because of how we create and maintain blossoms + virtual vertex_descriptor_t get_base() const + { + const blossom* b = this; + while (!b->sub_blossoms.empty()) + b = b->sub_blossoms[0].get(); + return b->get_base(); + } + + // set a sub-blossom as a blossom's base by exchanging it + // with its first sub-blossom + void set_base(const blossom_ptr_t& sub) + { + for (blossom_iterator_t bi = sub_blossoms.begin(); bi != sub_blossoms.end(); ++bi) + { + if (sub.get() == bi->get()) + { + std::iter_swap(sub_blossoms.begin(), bi); + break; + } + } + } + + // get all vertices inside recursively + virtual std::vector<vertex_descriptor_t> vertices() const + { + std::vector<vertex_descriptor_t> all_vertices; + for (typename std::vector<blossom_ptr_t>::const_iterator bi = sub_blossoms.begin(); bi != sub_blossoms.end(); ++bi) + { + std::vector<vertex_descriptor_t> some_vertices = (*bi)->vertices(); + all_vertices.insert(all_vertices.end(), some_vertices.begin(), some_vertices.end()); + } + return all_vertices; + } + }; + + // a trivial_blossom only has one vertex and no sub-blossom; + // for each vertex v, in_blossom[v] is the trivial_blossom that contains it directly + class trivial_blossom : public blossom + { + public: + trivial_blossom(vertex_descriptor_t v) : trivial_vertex(v) {} + virtual vertex_descriptor_t get_base() const + { + return trivial_vertex; + } + + virtual std::vector<vertex_descriptor_t> vertices() const + { + std::vector<vertex_descriptor_t> all_vertices; + all_vertices.push_back(trivial_vertex); + return all_vertices; + } + + private: + + vertex_descriptor_t trivial_vertex; + }; + + typedef boost::shared_ptr<blossom> blossom_ptr_t; + typedef typename std::vector<blossom_ptr_t>::iterator blossom_iterator_t; + typedef typename map_vertex_to_<blossom_ptr_t>::type vertex_to_blossom_map_t; + + weighted_augmenting_path_finder(const Graph& arg_g, MateMap arg_mate, VertexIndexMap arg_vm) : + g(arg_g), + vm(arg_vm), + null_edge(std::pair<edge_descriptor_t, bool>(num_edges(g) == 0 ? edge_descriptor_t() : *edges(g).first, false)), + mate_vector(num_vertices(g)), + label_S_vector(num_vertices(g), graph_traits<Graph>::null_vertex()), + label_T_vector(num_vertices(g), graph_traits<Graph>::null_vertex()), + outlet_vector(num_vertices(g), graph_traits<Graph>::null_vertex()), + tau_idx_vector(num_vertices(g), graph_traits<Graph>::null_vertex()), + dual_var_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::min())), + pi_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::max())), + gamma_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::max())), + tau_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::max())), + in_blossom_vector(num_vertices(g)), + old_label_vector(num_vertices(g)), + critical_edge_vectors(num_vertices(g), std::vector<std::pair<edge_descriptor_t, bool> >(num_vertices(g), null_edge)), + + mate(mate_vector.begin(), vm), + label_S(label_S_vector.begin(), vm), + label_T(label_T_vector.begin(), vm), + outlet(outlet_vector.begin(), vm), + tau_idx(tau_idx_vector.begin(), vm), + dual_var(dual_var_vector.begin(), vm), + pi(pi_vector.begin(), vm), + gamma(gamma_vector.begin(), vm), + tau(tau_vector.begin(), vm), + in_blossom(in_blossom_vector.begin(), vm), + old_label(old_label_vector.begin(), vm) + { + vertex_iterator_t vi, vi_end; + edge_iterator_t ei, ei_end; + + edge_property_t max_weight = std::numeric_limits<edge_property_t>::min(); + for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) + max_weight = std::max(max_weight, get(edge_weight, g, *ei)); + + typename std::vector<std::vector<std::pair<edge_descriptor_t, bool> > >::iterator vei; + + for (boost::tie(vi,vi_end) = vertices(g), vei = critical_edge_vectors.begin(); vi != vi_end; ++vi, ++vei) + { + vertex_descriptor_t u = *vi; + mate[u] = get(arg_mate, u); + dual_var[u] = 2*max_weight; + in_blossom[u] = boost::make_shared<trivial_blossom>(u); + outlet[u] = u; + critical_edge_vector.push_back(vertex_to_edge_map_t(vei->begin(), vm)); + } + + critical_edge = vertex_pair_to_edge_map_t(critical_edge_vector.begin(), vm); + + init(); + } + + // return the top blossom where v is contained inside + blossom_ptr_t in_top_blossom(vertex_descriptor_t v) const + { + blossom_ptr_t b = in_blossom[v]; + while (b->father != blossom_ptr_t()) + b = b->father; + return b; + } + + // check if vertex v is in blossom b + bool is_in_blossom(blossom_ptr_t b, vertex_descriptor_t v) const + { + if (v == graph_traits<Graph>::null_vertex()) + return false; + blossom_ptr_t vb = in_blossom[v]->father; + while (vb != blossom_ptr_t()) + { + if (vb.get() == b.get()) + return true; + vb = vb->father; + } + return false; + } + + // return the base vertex of the top blossom that contains v + inline vertex_descriptor_t base_vertex(vertex_descriptor_t v) const + { + return in_top_blossom(v)->get_base(); + } + + // add an existed top blossom of base vertex v into new top + // blossom b as its sub-blossom + void add_sub_blossom(blossom_ptr_t b, vertex_descriptor_t v) + { + blossom_ptr_t sub = in_top_blossom(v); + sub->father = b; + b->sub_blossoms.push_back(sub); + if (sub->sub_blossoms.empty()) + return; + for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end(); ++bi) + { + if (bi->get() == sub.get()) + { + top_blossoms.erase(bi); + break; + } + } + } + + // when a top blossom is created or its base vertex getting an S-label, + // add all edges incident to this blossom into even_edges + void bloom(blossom_ptr_t b) + { + std::vector<vertex_descriptor_t> vertices_of_b = b->vertices(); + vertex_vec_iter_t vi; + for (vi = vertices_of_b.begin(); vi != vertices_of_b.end(); ++vi) + { + out_edge_iterator_t oei, oei_end; + for (boost::tie(oei,oei_end) = out_edges(*vi, g); oei != oei_end; ++oei) + { + if (target(*oei,g) != *vi && mate[*vi] != target(*oei,g)) + even_edges.push_back(*oei); + } + } + } + + // assigning a T-label to a non S-vertex, along with outlet and updating pi value + // if updated pi[v] equals zero, augment the matching from its mate vertex + void put_T_label(vertex_descriptor_t v, vertex_descriptor_t T_label, + vertex_descriptor_t outlet_v, edge_property_t pi_v) + { + if (label_S[v] != graph_traits<Graph>::null_vertex()) + return; + + label_T[v] = T_label; + outlet[v] = outlet_v; + pi[v] = pi_v; + + vertex_descriptor_t v_mate = mate[v]; + if (pi[v] == 0) + { + label_T[v_mate] = graph_traits<Graph>::null_vertex(); + label_S[v_mate] = v; + bloom(in_top_blossom(v_mate)); + } + } + + // get the missing T-label for a to-be-expanded base vertex + // the missing T-label is the last vertex of the path from outlet[v] to v + std::pair<vertex_descriptor_t, vertex_descriptor_t> missing_label(vertex_descriptor_t b_base) + { + vertex_descriptor_t missing_outlet = outlet[b_base]; + + if (outlet[b_base] == b_base) + return std::make_pair(graph_traits<Graph>::null_vertex(), missing_outlet); + + vertex_iterator_t vi, vi_end; + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + old_label[*vi] = std::make_pair(label_T[*vi], outlet[*vi]); + + std::pair<vertex_descriptor_t, vertex_state_t> child(outlet[b_base], graph::detail::V_EVEN); + blossom_ptr_t b = in_blossom[child.first]; + for (; b->father->father != blossom_ptr_t(); b = b->father); + child.first = b->get_base(); + + if (child.first == b_base) + return std::make_pair(graph_traits<Graph>::null_vertex(), missing_outlet); + + while (true) + { + std::pair<vertex_descriptor_t, vertex_state_t> child_parent = parent(child, true); + + for (b = in_blossom[child_parent.first]; b->father->father != blossom_ptr_t(); b = b->father); + missing_outlet = child_parent.first; + child_parent.first = b->get_base(); + + if (child_parent.first == b_base) + break; + else + child = child_parent; + } + return std::make_pair(child.first, missing_outlet); + } + + // expand a top blossom, put all its non-trivial sub-blossoms into top_blossoms + blossom_iterator_t expand_blossom(blossom_iterator_t bi, std::vector<blossom_ptr_t>& new_ones) + { + blossom_ptr_t b = *bi; + for (blossom_iterator_t i = b->sub_blossoms.begin(); i != b->sub_blossoms.end(); ++i) + { + blossom_ptr_t sub_blossom = *i; + vertex_descriptor_t sub_base = sub_blossom->get_base(); + label_S[sub_base] = label_T[sub_base] = graph_traits<Graph>::null_vertex(); + outlet[sub_base] = sub_base; + sub_blossom->father = blossom_ptr_t(); + // new top blossoms cannot be pushed back into top_blossoms immediately, + // because push_back() may cause reallocation and then invalid iterators + if (!sub_blossom->sub_blossoms.empty()) + new_ones.push_back(sub_blossom); + } + return top_blossoms.erase(bi); + } + + // when expanding a T-blossom with base v, it requires more operations: + // supply the missing T-labels for new base vertices by picking the minimum tau from vertices of + // each corresponding new top-blossoms; when label_T[v] is null or we have a smaller tau from + // missing_label(v), replace T-label and outlet of v (but don't bloom v) + blossom_iterator_t expand_T_blossom(blossom_iterator_t bi, std::vector<blossom_ptr_t>& new_ones) + { + blossom_ptr_t b = *bi; + + vertex_descriptor_t b_base = b->get_base(); + std::pair<vertex_descriptor_t, vertex_descriptor_t> T_and_outlet = missing_label(b_base); + + blossom_iterator_t next_bi = expand_blossom(bi, new_ones); + + for (blossom_iterator_t i = b->sub_blossoms.begin(); i != b->sub_blossoms.end(); ++i) + { + blossom_ptr_t sub_blossom = *i; + vertex_descriptor_t sub_base = sub_blossom->get_base(); + vertex_descriptor_t min_tau_v = graph_traits<Graph>::null_vertex(); + edge_property_t min_tau = std::numeric_limits<edge_property_t>::max(); + + std::vector<vertex_descriptor_t> sub_vertices = sub_blossom->vertices(); + for (vertex_vec_iter_t v = sub_vertices.begin(); v != sub_vertices.end(); ++v) + { + if (tau[*v] < min_tau) + { + min_tau = tau[*v]; + min_tau_v = *v; + } + } + + if (min_tau < std::numeric_limits<edge_property_t>::max()) + put_T_label(sub_base, tau_idx[min_tau_v], min_tau_v, tau[min_tau_v]); + } + + if (label_T[b_base] == graph_traits<Graph>::null_vertex() || tau[old_label[b_base].second] < pi[b_base]) + boost::tie(label_T[b_base], outlet[b_base]) = T_and_outlet; + + return next_bi; + } + + // when vertices v and w are matched to each other by augmenting, + // we must set v/w as base vertex of any blossom who contains v/w and + // is a sub-blossom of their lowest (smallest) common blossom + void adjust_blossom(vertex_descriptor_t v, vertex_descriptor_t w) + { + blossom_ptr_t vb = in_blossom[v], wb = in_blossom[w], lowest_common_blossom; + std::vector<blossom_ptr_t> v_ancestors, w_ancestors; + + while (vb->father != blossom_ptr_t()) + { + v_ancestors.push_back(vb->father); + vb = vb->father; + } + while (wb->father != blossom_ptr_t()) + { + w_ancestors.push_back(wb->father); + wb = wb->father; + } + + typename std::vector<blossom_ptr_t>::reverse_iterator i, j; + i = v_ancestors.rbegin(); + j = w_ancestors.rbegin(); + while (i != v_ancestors.rend() && j != w_ancestors.rend() && i->get() == j->get()) + { + lowest_common_blossom = *i; + ++i;++j; + } + + vb = in_blossom[v]; + wb = in_blossom[w]; + while (vb->father != lowest_common_blossom) + { + vb->father->set_base(vb); + vb = vb->father; + } + while (wb->father != lowest_common_blossom) + { + wb->father->set_base(wb); + wb = wb->father; + } + } + + // every edge weight is multiplied by 4 to ensure integer weights + // throughout the algorithm if all input weights are integers + inline edge_property_t slack(const edge_descriptor_t& e) const + { + vertex_descriptor_t v, w; + v = source(e, g); + w = target(e, g); + return dual_var[v] + dual_var[w] - 4*get(edge_weight, g, e); + } + + // backtrace one step on vertex v along the augmenting path + // by its labels and its vertex state; + // boolean parameter "use_old" means whether we are updating labels, + // if we are, then we use old labels to backtrace and also we + // don't jump to its base vertex when we reach an odd vertex + std::pair<vertex_descriptor_t, vertex_state_t> parent(std::pair<vertex_descriptor_t, vertex_state_t> v, + bool use_old = false) const + { + if (v.second == graph::detail::V_EVEN) + { + // a paranoid check: label_S shoule be the same as mate in backtracing + if (label_S[v.first] == graph_traits<Graph>::null_vertex()) + label_S[v.first] = mate[v.first]; + return std::make_pair(label_S[v.first], graph::detail::V_ODD); + } + else if (v.second == graph::detail::V_ODD) + { + vertex_descriptor_t w = use_old ? old_label[v.first].first : base_vertex(label_T[v.first]); + return std::make_pair(w, graph::detail::V_EVEN); + } + return std::make_pair(v.first, graph::detail::V_UNREACHED); + } + + // backtrace from vertices v and w to their free (unmatched) ancesters, + // return the nearest common ancestor (null_vertex if none) of v and w + vertex_descriptor_t nearest_common_ancestor(vertex_descriptor_t v, vertex_descriptor_t w, + vertex_descriptor_t& v_free_ancestor, + vertex_descriptor_t& w_free_ancestor) const + { + std::pair<vertex_descriptor_t, vertex_state_t> v_up(v, graph::detail::V_EVEN); + std::pair<vertex_descriptor_t, vertex_state_t> w_up(w, graph::detail::V_EVEN); + vertex_descriptor_t nca; + nca = w_free_ancestor = v_free_ancestor = graph_traits<Graph>::null_vertex(); + + std::vector<bool> ancestor_of_w_vector(num_vertices(g), false); + std::vector<bool> ancestor_of_v_vector(num_vertices(g), false); + vertex_to_bool_map_t ancestor_of_w(ancestor_of_w_vector.begin(), vm); + vertex_to_bool_map_t ancestor_of_v(ancestor_of_v_vector.begin(), vm); + + while (nca == graph_traits<Graph>::null_vertex() && + (v_free_ancestor == graph_traits<Graph>::null_vertex() || + w_free_ancestor == graph_traits<Graph>::null_vertex())) + { + ancestor_of_w[w_up.first] = true; + ancestor_of_v[v_up.first] = true; + + if (w_free_ancestor == graph_traits<Graph>::null_vertex()) + w_up = parent(w_up); + if (v_free_ancestor == graph_traits<Graph>::null_vertex()) + v_up = parent(v_up); + + if (mate[v_up.first] == graph_traits<Graph>::null_vertex()) + v_free_ancestor = v_up.first; + if (mate[w_up.first] == graph_traits<Graph>::null_vertex()) + w_free_ancestor = w_up.first; + + if (ancestor_of_w[v_up.first] == true || v_up.first == w_up.first) + nca = v_up.first; + else if (ancestor_of_v[w_up.first] == true) + nca = w_up.first; + else if (v_free_ancestor == w_free_ancestor && + v_free_ancestor != graph_traits<Graph>::null_vertex()) + nca = v_up.first; + } + + return nca; + } + + // when a new top blossom b is created by connecting (v, w), we add sub-blossoms into + // b along backtracing from v_prime and w_prime to stop_vertex (the base vertex); + // also, we set labels and outlet for each base vertex we pass by + void make_blossom(blossom_ptr_t b, vertex_descriptor_t w_prime, + vertex_descriptor_t v_prime, vertex_descriptor_t stop_vertex) + { + std::pair<vertex_descriptor_t, vertex_state_t> u(v_prime, graph::detail::V_ODD); + std::pair<vertex_descriptor_t, vertex_state_t> u_up(w_prime, graph::detail::V_EVEN); + + for (; u_up.first != stop_vertex; u = u_up, u_up = parent(u)) + { + if (u_up.second == graph::detail::V_EVEN) + { + if (!in_top_blossom(u_up.first)->sub_blossoms.empty()) + outlet[u_up.first] = label_T[u.first]; + label_T[u_up.first] = outlet[u.first]; + } + else if (u_up.second == graph::detail::V_ODD) + label_S[u_up.first] = u.first; + + add_sub_blossom(b, u_up.first); + } + } + + // the design of recursively expanding augmenting path in (reversed_)retrieve_augmenting_path + // functions is inspired by same functions in max_cardinality_matching.hpp; + // except that in weighted matching, we use "outlet" vertices instead of "bridge" vertex pairs: + // if blossom b is the smallest non-trivial blossom that contains its base vertex v, then + // v and outlet[v] are where augmenting path enters and leaves b + void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w, vertex_state_t v_state) + { + if (v == w) + aug_path.push_back(v); + else if (v_state == graph::detail::V_EVEN) + { + aug_path.push_back(v); + retrieve_augmenting_path(label_S[v], w, graph::detail::V_ODD); + } + else if (v_state == graph::detail::V_ODD) + { + if (outlet[v] == v) + aug_path.push_back(v); + else + reversed_retrieve_augmenting_path(outlet[v], v, graph::detail::V_EVEN); + retrieve_augmenting_path(label_T[v], w, graph::detail::V_EVEN); + } + } + + void reversed_retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w, vertex_state_t v_state) + { + if (v == w) + aug_path.push_back(v); + else if (v_state == graph::detail::V_EVEN) + { + reversed_retrieve_augmenting_path(label_S[v], w, graph::detail::V_ODD); + aug_path.push_back(v); + } + else if (v_state == graph::detail::V_ODD) + { + reversed_retrieve_augmenting_path(label_T[v], w, graph::detail::V_EVEN); + if (outlet[v] != v) + retrieve_augmenting_path(outlet[v], v, graph::detail::V_EVEN); + else + aug_path.push_back(v); + } + } + + // correct labels for vertices in the augmenting path + void relabel(vertex_descriptor_t v) + { + blossom_ptr_t b = in_blossom[v]->father; + + if (!is_in_blossom(b, mate[v])) + { // if v is a new base vertex + std::pair<vertex_descriptor_t, vertex_state_t> u(v, graph::detail::V_EVEN); + while (label_S[u.first] != u.first && is_in_blossom(b, label_S[u.first])) + u = parent(u, true); + + vertex_descriptor_t old_base = u.first; + if (label_S[old_base] != old_base) + { // if old base is not exposed + label_T[v] = label_S[old_base]; + outlet[v] = old_base; + } + else + { // if old base is exposed then new label_T[v] is not in b, + // we must (i) make b2 the smallest blossom containing v but not as base vertex + // (ii) backtrace from b2's new base vertex to b + label_T[v] = graph_traits<Graph>::null_vertex(); + for (b = b->father; b != blossom_ptr_t() && b->get_base() == v; b = b->father); + if (b != blossom_ptr_t()) + { + u = std::make_pair(b->get_base(), graph::detail::V_ODD); + while (!is_in_blossom(in_blossom[v]->father, old_label[u.first].first)) + u = parent(u, true); + label_T[v] = u.first; + outlet[v] = old_label[u.first].first; + } + } + } + else if (label_S[v] == v || !is_in_blossom(b, label_S[v])) + { // if v is an old base vertex + // let u be the new base vertex; backtrace from u's old T-label + std::pair<vertex_descriptor_t, vertex_state_t> u(b->get_base(), graph::detail::V_ODD); + while (old_label[u.first].first != graph_traits<Graph>::null_vertex() && old_label[u.first].first != v) + u = parent(u, true); + label_T[v] = old_label[u.first].second; + outlet[v] = v; + } + else // if v is neither a new nor an old base vertex + label_T[v] = label_S[v]; + } + + void augmenting(vertex_descriptor_t v, vertex_descriptor_t v_free_ancestor, + vertex_descriptor_t w, vertex_descriptor_t w_free_ancestor) + { + vertex_iterator_t vi, vi_end; + + // retrieve the augmenting path and put it in aug_path + reversed_retrieve_augmenting_path(v, v_free_ancestor, graph::detail::V_EVEN); + retrieve_augmenting_path(w, w_free_ancestor, graph::detail::V_EVEN); + + // augment the matching along aug_path + vertex_descriptor_t a, b; + vertex_list_t reversed_aug_path; + while (!aug_path.empty()) + { + a = aug_path.front(); + aug_path.pop_front(); + reversed_aug_path.push_back(a); + b = aug_path.front(); + aug_path.pop_front(); + reversed_aug_path.push_back(b); + + mate[a] = b; + mate[b] = a; + + // reset base vertex for every blossom in augment path + adjust_blossom(a, b); + } + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + old_label[*vi] = std::make_pair(label_T[*vi], outlet[*vi]); + + // correct labels for in-blossom vertices along aug_path + while (!reversed_aug_path.empty()) + { + a = reversed_aug_path.front(); + reversed_aug_path.pop_front(); + + if (in_blossom[a]->father != blossom_ptr_t()) + relabel(a); + } + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + vertex_descriptor_t u = *vi; + if (mate[u] != graph_traits<Graph>::null_vertex()) + label_S[u] = mate[u]; + } + + // expand blossoms with zero dual variables + std::vector<blossom_ptr_t> new_top_blossoms; + for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end();) + { + if ((*bi)->dual_var <= 0) + bi = expand_blossom(bi, new_top_blossoms); + else + ++bi; + } + top_blossoms.insert(top_blossoms.end(), new_top_blossoms.begin(), new_top_blossoms.end()); + init(); + } + + // create a new blossom and set labels for vertices inside + void blossoming(vertex_descriptor_t v, vertex_descriptor_t v_prime, + vertex_descriptor_t w, vertex_descriptor_t w_prime, + vertex_descriptor_t nca) + { + vertex_iterator_t vi, vi_end; + + std::vector<bool> is_old_base_vector(num_vertices(g)); + vertex_to_bool_map_t is_old_base(is_old_base_vector.begin(), vm); + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + if (*vi == base_vertex(*vi)) + is_old_base[*vi] = true; + } + + blossom_ptr_t b = boost::make_shared<blossom>(); + add_sub_blossom(b, nca); + + label_T[w_prime] = v; + label_T[v_prime] = w; + outlet[w_prime] = w; + outlet[v_prime] = v; + + make_blossom(b, w_prime, v_prime, nca); + make_blossom(b, v_prime, w_prime, nca); + + label_T[nca] = graph_traits<Graph>::null_vertex(); + outlet[nca] = nca; + + top_blossoms.push_back(b); + bloom(b); + + // set gamma[b_base] = min_slack{critical_edge(b_base, other_base)} where each critical edge + // is updated before, by argmin{slack(old_bases_in_b, other_base)}; + vertex_vec_iter_t i, j; + std::vector<vertex_descriptor_t> b_vertices = b->vertices(), old_base_in_b, other_base; + vertex_descriptor_t b_base = b->get_base(); + for (i = b_vertices.begin(); i != b_vertices.end(); ++i) + { + if (is_old_base[*i]) + old_base_in_b.push_back(*i); + } + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + if (*vi != b_base && *vi == base_vertex(*vi)) + other_base.push_back(*vi); + } + for (i = other_base.begin(); i != other_base.end(); ++i) + { + edge_property_t min_slack = std::numeric_limits<edge_property_t>::max(); + std::pair<edge_descriptor_t, bool> b_vi = null_edge; + for (j = old_base_in_b.begin(); j != old_base_in_b.end(); ++j) + { + if (critical_edge[*j][*i] != null_edge && min_slack > slack(critical_edge[*j][*i].first)) + { + min_slack = slack(critical_edge[*j][*i].first); + b_vi = critical_edge[*j][*i]; + } + } + critical_edge[b_base][*i] = critical_edge[*i][b_base] = b_vi; + } + gamma[b_base] = std::numeric_limits<edge_property_t>::max(); + for (i = other_base.begin(); i != other_base.end(); ++i) + { + if (critical_edge[b_base][*i] != null_edge) + gamma[b_base] = std::min(gamma[b_base], slack(critical_edge[b_base][*i].first)); + } + } + + void init() + { + even_edges.clear(); + + vertex_iterator_t vi, vi_end; + typename std::vector<std::vector<std::pair<edge_descriptor_t, bool> > >::iterator vei; + + for (boost::tie(vi,vi_end) = vertices(g), vei = critical_edge_vectors.begin(); vi != vi_end; ++vi, ++vei) + { + vertex_descriptor_t u = *vi; + out_edge_iterator_t ei, ei_end; + + gamma[u] = tau[u] = pi[u] = std::numeric_limits<edge_property_t>::max(); + std::fill(vei->begin(), vei->end(), null_edge); + + if (base_vertex(u) != u) + continue; + + label_S[u] = label_T[u] = graph_traits<Graph>::null_vertex(); + outlet[u] = u; + + if (mate[u] == graph_traits<Graph>::null_vertex()) + { + label_S[u] = u; + bloom(in_top_blossom(u)); + } + } + } + + bool augment_matching() + { + vertex_descriptor_t v, w, w_free_ancestor, v_free_ancestor; + v = w = w_free_ancestor = v_free_ancestor = graph_traits<Graph>::null_vertex(); + bool found_alternating_path = false; + + // note that we only use edges of zero slack value for augmenting + while (!even_edges.empty() && !found_alternating_path) + { + // search for augmenting paths depth-first + edge_descriptor_t current_edge = even_edges.back(); + even_edges.pop_back(); + + v = source(current_edge, g); + w = target(current_edge, g); + + vertex_descriptor_t v_prime = base_vertex(v); + vertex_descriptor_t w_prime = base_vertex(w); + + // w_prime == v_prime implies that we get an edge that has been shrunk into a blossom + if (v_prime == w_prime) + continue; + + // a paranoid check + if (label_S[v_prime] == graph_traits<Graph>::null_vertex()) + { + std::swap(v_prime, w_prime); + std::swap(v, w); + } + + // w_prime may be unlabeled or have a T-label; replace the existed T-label if the edge slack + // is smaller than current pi[w_prime] and update it. Note that a T-label is "deserved" only when pi equals zero. + // also update tau and tau_idx so that tau_idx becomes T-label when a T-blossom is expanded + if (label_S[w_prime] == graph_traits<Graph>::null_vertex()) + { + if (slack(current_edge) < pi[w_prime]) + put_T_label(w_prime, v, w, slack(current_edge)); + if (slack(current_edge) < tau[w]) + { + if (in_blossom[w]->father == blossom_ptr_t() || label_T[w_prime] == v || + label_T[w_prime] == graph_traits<Graph>::null_vertex() || + nearest_common_ancestor(v_prime, label_T[w_prime], + v_free_ancestor, w_free_ancestor) == graph_traits<Graph>::null_vertex()) + { + tau[w] = slack(current_edge); + tau_idx[w] = v; + } + } + } + + else + { + if (slack(current_edge) > 0) + { + // update gamma and critical_edges when we have a smaller edge slack + gamma[v_prime] = std::min(gamma[v_prime], slack(current_edge)); + gamma[w_prime] = std::min(gamma[w_prime], slack(current_edge)); + if (critical_edge[v_prime][w_prime] == null_edge || + slack(critical_edge[v_prime][w_prime].first) > slack(current_edge)) + { + critical_edge[v_prime][w_prime] = std::pair<edge_descriptor_t, bool>(current_edge, true); + critical_edge[w_prime][v_prime] = std::pair<edge_descriptor_t, bool>(current_edge, true); + } + continue; + } + else if (slack(current_edge) == 0) + { + // if nca is null_vertex then we have an augmenting path; otherwise we have + // a new top blossom with nca as its base vertex + vertex_descriptor_t nca = nearest_common_ancestor(v_prime, w_prime, v_free_ancestor, w_free_ancestor); + + if (nca == graph_traits<Graph>::null_vertex()) + found_alternating_path = true; //to break out of the loop + else + blossoming(v, v_prime, w, w_prime, nca); + } + } + } + + if (!found_alternating_path) + return false; + + augmenting(v, v_free_ancestor, w, w_free_ancestor); + return true; + } + + // slack the vertex and blossom dual variables when there is no augmenting path found + // according to the primal-dual method + bool adjust_dual() + { + edge_property_t delta1, delta2, delta3, delta4, delta; + delta1 = delta2 = delta3 = delta4 = std::numeric_limits<edge_property_t>::max(); + + vertex_iterator_t vi, vi_end; + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + delta1 = std::min(delta1, dual_var[*vi]); + delta4 = pi[*vi] > 0 ? std::min(delta4, pi[*vi]) : delta4; + if (*vi == base_vertex(*vi)) + delta3 = std::min(delta3, gamma[*vi]/2); + } + + for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end(); ++bi) + { + vertex_descriptor_t b_base = (*bi)->get_base(); + if (label_T[b_base] != graph_traits<Graph>::null_vertex() && pi[b_base] == 0) + delta2 = std::min(delta2, (*bi)->dual_var/2); + } + + delta = std::min(std::min(delta1, delta2), std::min(delta3, delta4)); + + // start updating dual variables, note that the order is important + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + vertex_descriptor_t v = *vi, v_prime = base_vertex(v); + + if (label_S[v_prime] != graph_traits<Graph>::null_vertex()) + dual_var[v] -= delta; + else if (label_T[v_prime] != graph_traits<Graph>::null_vertex() && pi[v_prime] == 0) + dual_var[v] += delta; + + if (v == v_prime) + gamma[v] -= 2*delta; + } + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + vertex_descriptor_t v_prime = base_vertex(*vi); + if (pi[v_prime] > 0) + tau[*vi] -= delta; + } + + for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end(); ++bi) + { + vertex_descriptor_t b_base = (*bi)->get_base(); + if (label_T[b_base] != graph_traits<Graph>::null_vertex() && pi[b_base] == 0) + (*bi)->dual_var -= 2*delta; + if (label_S[b_base] != graph_traits<Graph>::null_vertex()) + (*bi)->dual_var += 2*delta; + } + + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + vertex_descriptor_t v = *vi; + if (pi[v] > 0) + pi[v] -= delta; + + // when some T-vertices have zero pi value, bloom their mates so that matching can be further augmented + if (label_T[v] != graph_traits<Graph>::null_vertex() && pi[v] == 0) + put_T_label(v, label_T[v], outlet[v], pi[v]); + } + + + // optimal solution reached, halt + if (delta == delta1) + return false; + + // expand odd blossoms with zero dual variables and zero pi value of their base vertices + if (delta == delta2 && delta != delta3) + { + std::vector<blossom_ptr_t> new_top_blossoms; + for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end();) + { + const blossom_ptr_t b = *bi; + vertex_descriptor_t b_base = b->get_base(); + if (b->dual_var == 0 && label_T[b_base] != graph_traits<Graph>::null_vertex() && pi[b_base] == 0) + bi = expand_T_blossom(bi, new_top_blossoms); + else + ++bi; + } + top_blossoms.insert(top_blossoms.end(), new_top_blossoms.begin(), new_top_blossoms.end()); + } + + while (true) + { + // find a zero-slack critical edge (v, w) of zero gamma values + std::pair<edge_descriptor_t, bool> best_edge = null_edge; + std::vector<vertex_descriptor_t> base_nodes; + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + { + if (*vi == base_vertex(*vi)) + base_nodes.push_back(*vi); + } + for (vertex_vec_iter_t i = base_nodes.begin(); i != base_nodes.end(); ++i) + { + if (gamma[*i] == 0) + { + for (vertex_vec_iter_t j = base_nodes.begin(); j != base_nodes.end(); ++j) + { + if (critical_edge[*i][*j] != null_edge && slack(critical_edge[*i][*j].first) == 0) + best_edge = critical_edge[*i][*j]; + } + } + } + + // if not found, continue finding other augment matching + if (best_edge == null_edge) + { + bool augmented = augment_matching(); + return augmented || delta != delta1; + } + // if found, determine either augmenting or blossoming + vertex_descriptor_t v = source(best_edge.first, g), w = target(best_edge.first, g); + vertex_descriptor_t v_prime = base_vertex(v), w_prime = base_vertex(w), v_free_ancestor, w_free_ancestor; + vertex_descriptor_t nca = nearest_common_ancestor(v_prime, w_prime, v_free_ancestor, w_free_ancestor); + if (nca == graph_traits<Graph>::null_vertex()) + { + augmenting(v, v_free_ancestor, w, w_free_ancestor); + return true; + } + else + blossoming(v, v_prime, w, w_prime, nca); + } + + return false; + } + + template <typename PropertyMap> + void get_current_matching(PropertyMap pm) + { + vertex_iterator_t vi, vi_end; + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + put(pm, *vi, mate[*vi]); + } + + private: + + const Graph& g; + VertexIndexMap vm; + const std::pair<edge_descriptor_t, bool> null_edge; + + // storage for the property maps below + std::vector<vertex_descriptor_t> mate_vector; + std::vector<vertex_descriptor_t> label_S_vector, label_T_vector; + std::vector<vertex_descriptor_t> outlet_vector; + std::vector<vertex_descriptor_t> tau_idx_vector; + std::vector<edge_property_t> dual_var_vector; + std::vector<edge_property_t> pi_vector, gamma_vector, tau_vector; + std::vector<blossom_ptr_t> in_blossom_vector; + std::vector<std::pair<vertex_descriptor_t, vertex_descriptor_t> > old_label_vector; + std::vector<vertex_to_edge_map_t> critical_edge_vector; + std::vector<std::vector<std::pair<edge_descriptor_t, bool> > > critical_edge_vectors; + + // iterator property maps + vertex_to_vertex_map_t mate; + vertex_to_vertex_map_t label_S; // v has an S-label -> v can be an even vertex, label_S[v] is its mate + vertex_to_vertex_map_t label_T; // v has a T-label -> v can be an odd vertex, label_T[v] is its predecessor in aug_path + vertex_to_vertex_map_t outlet; + vertex_to_vertex_map_t tau_idx; + vertex_to_weight_map_t dual_var; + vertex_to_weight_map_t pi, gamma, tau; + vertex_to_blossom_map_t in_blossom; // map any vertex v to the trivial blossom containing v + vertex_to_pair_map_t old_label; // <old T-label, old outlet> before relabeling or expanding T-blossoms + vertex_pair_to_edge_map_t critical_edge; // an not matched edge (v, w) is critical if v and w belongs to different S-blossoms + + vertex_list_t aug_path; + edge_list_t even_edges; + std::vector<blossom_ptr_t> top_blossoms; + + }; + + template <typename Graph, typename MateMap, typename VertexIndexMap> + void maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm) + { + empty_matching<Graph, MateMap>::find_matching(g, mate); + weighted_augmenting_path_finder<Graph, MateMap, VertexIndexMap> augmentor(g, mate, vm); + + // can have |V| times augmenting at most + for (std::size_t t = 0; t < num_vertices(g); ++t) + { + bool augmented = false; + while (!augmented) + { + augmented = augmentor.augment_matching(); + if (!augmented) + { + // halt if adjusting dual variables can't bring potential augment + if (!augmentor.adjust_dual()) + break; + } + } + if (!augmented) + break; + } + + augmentor.get_current_matching(mate); + } + + template <typename Graph, typename MateMap> + inline void maximum_weighted_matching(const Graph& g, MateMap mate) + { + maximum_weighted_matching(g, mate, get(vertex_index,g)); + } + + // brute-force matcher searches all possible combinations of matched edges to get the maximum weighted matching + // which can be used for testing on small graphs (within dozens vertices) + template <typename Graph, typename MateMap, typename VertexIndexMap> + class brute_force_matching + { + public: + + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t; + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; + typedef typename std::vector<vertex_descriptor_t>::iterator vertex_vec_iter_t; + typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t; + typedef boost::iterator_property_map<vertex_vec_iter_t, VertexIndexMap> vertex_to_vertex_map_t; + + brute_force_matching(const Graph& arg_g, MateMap arg_mate, VertexIndexMap arg_vm) : + g(arg_g), + vm(arg_vm), + mate_vector(num_vertices(g)), + best_mate_vector(num_vertices(g)), + mate(mate_vector.begin(), vm), + best_mate(best_mate_vector.begin(), vm) + { + vertex_iterator_t vi,vi_end; + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + best_mate[*vi] = mate[*vi] = get(arg_mate, *vi); + } + + template <typename PropertyMap> + void find_matching(PropertyMap pm) + { + edge_iterator_t ei; + boost::tie(ei, ei_end) = edges(g); + select_edge(ei); + + vertex_iterator_t vi,vi_end; + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + put(pm, *vi, best_mate[*vi]); + } + + private: + + const Graph& g; + VertexIndexMap vm; + std::vector<vertex_descriptor_t> mate_vector, best_mate_vector; + vertex_to_vertex_map_t mate, best_mate; + edge_iterator_t ei_end; + + void select_edge(edge_iterator_t ei) + { + if (ei == ei_end) + { + if (matching_weight_sum(g, mate) > matching_weight_sum(g, best_mate)) + { + vertex_iterator_t vi, vi_end; + for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) + best_mate[*vi] = mate[*vi]; + } + return; + } + + vertex_descriptor_t v, w; + v = source(*ei, g); + w = target(*ei, g); + + select_edge(++ei); + + if (mate[v] == graph_traits<Graph>::null_vertex() && + mate[w] == graph_traits<Graph>::null_vertex()) + { + mate[v] = w; + mate[w] = v; + select_edge(ei); + mate[v] = mate[w] = graph_traits<Graph>::null_vertex(); + } + } + + }; + + template <typename Graph, typename MateMap, typename VertexIndexMap> + void brute_force_maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm) + { + empty_matching<Graph, MateMap>::find_matching(g, mate); + brute_force_matching<Graph, MateMap, VertexIndexMap> brute_force_matcher(g, mate, vm); + brute_force_matcher.find_matching(mate); + } + + template <typename Graph, typename MateMap> + inline void brute_force_maximum_weighted_matching(const Graph& g, MateMap mate) + { + brute_force_maximum_weighted_matching(g, mate, get(vertex_index, g)); + } + +} + +#endif diff --git a/boost/graph/metis.hpp b/boost/graph/metis.hpp index 2ec2fc3e76..f6a1425f3e 100644 --- a/boost/graph/metis.hpp +++ b/boost/graph/metis.hpp @@ -26,8 +26,8 @@ namespace boost { namespace graph { -class metis_exception : public std::exception {}; -class metis_input_exception : public metis_exception {}; +class BOOST_SYMBOL_VISIBLE metis_exception : public std::exception {}; +class BOOST_SYMBOL_VISIBLE metis_input_exception : public metis_exception {}; class metis_reader { diff --git a/boost/graph/minimum_degree_ordering.hpp b/boost/graph/minimum_degree_ordering.hpp index 1e171da6cb..74ec912702 100644 --- a/boost/graph/minimum_degree_ordering.hpp +++ b/boost/graph/minimum_degree_ordering.hpp @@ -270,6 +270,7 @@ namespace boost { typedef Marker<diff_t, vertex_t, VertexIndexMap> MarkerP; // Data Members + bool has_no_edges; // input parameters Graph& G; @@ -295,7 +296,7 @@ namespace boost { PermutationMap perm, SuperNodeMap supernode_size, VertexIndexMap id) - : G(g), delta(delta), degree(degree), + : has_no_edges(true), G(g), delta(delta), degree(degree), inverse_perm(inverse_perm), perm(perm), supernode_size(supernode_size), @@ -317,7 +318,9 @@ namespace boost { // Initialize degreelists. Degreelists organizes the nodes // according to their degree. for (boost::tie(v, vend) = vertices(G); v != vend; ++v) { - put(degree, *v, out_degree(*v, G)); + typename Traits::degree_size_type d = out_degree(*v, G); + put(degree, *v, d); + if (0 < d) has_no_edges = false; degreelists.push(*v); } } @@ -336,6 +339,12 @@ namespace boost { numbering.increment(); list_isolated.pop(); } + + if (has_no_edges) + { + return; + } + size_type min_degree = 1; typename DegreeLists::stack list_min_degree = degreelists[min_degree]; diff --git a/boost/graph/named_function_params.hpp b/boost/graph/named_function_params.hpp index 4842dc9548..ec8dfb7c67 100644 --- a/boost/graph/named_function_params.hpp +++ b/boost/graph/named_function_params.hpp @@ -13,13 +13,16 @@ #include <functional> #include <vector> #include <boost/limits.hpp> -#include <boost/ref.hpp> +#include <boost/core/enable_if.hpp> +#include <boost/core/ref.hpp> #include <boost/utility/result_of.hpp> #include <boost/preprocessor.hpp> +#include <boost/parameter/is_argument_pack.hpp> #include <boost/parameter/name.hpp> #include <boost/parameter/binding.hpp> #include <boost/type_traits.hpp> -#include <boost/mpl/not.hpp> +#include <boost/mpl/bool.hpp> +#include <boost/mpl/has_key.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_map/property_map.hpp> @@ -394,9 +397,6 @@ BOOST_BGL_DECLARE_NAMED_PARAMS }; struct bgl_parameter_not_found_type {}; - - template <typename ArgPack, typename KeywordType> - struct parameter_exists : boost::mpl::not_<boost::is_same<typename boost::parameter::binding<ArgPack, KeywordType, bgl_parameter_not_found_type>::type, bgl_parameter_not_found_type> > {}; } #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var) \ @@ -419,12 +419,13 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <typename ArgPack, typename Tag, typename Prop, typename Graph> struct override_const_property_result { + typedef typename boost::mpl::has_key<ArgPack, Tag>::type _parameter_exists; typedef typename override_const_property_t< typename boost::parameter::value_type<ArgPack, Tag, int>::type, Prop, Graph, - boost::detail::parameter_exists<ArgPack, Tag>::value + _parameter_exists::value >::result_type type; }; @@ -432,18 +433,19 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <typename ArgPack, typename Tag, typename Prop, typename Graph> typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { + typedef typename boost::mpl::has_key<ArgPack, Tag>::type _parameter_exists; return override_const_property_t< typename boost::parameter::value_type<ArgPack, Tag, int>::type, Prop, Graph, - boost::detail::parameter_exists<ArgPack, Tag>::value + _parameter_exists::value >()(g, ap[t | 0]); } template <typename ArgType, typename Prop, typename Graph, bool Exists> struct override_property_t { typedef ArgType result_type; - result_type operator()(const Graph&, const typename boost::add_reference<ArgType>::type a) const {return a;} + result_type operator()(const Graph&, typename boost::add_lvalue_reference<ArgType>::type a) const {return a;} }; template <typename ArgType, typename Prop, typename Graph> @@ -454,12 +456,13 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <typename ArgPack, typename Tag, typename Prop, typename Graph> struct override_property_result { + typedef typename boost::mpl::has_key<ArgPack, Tag>::type _parameter_exists; typedef typename override_property_t< typename boost::parameter::value_type<ArgPack, Tag, int>::type, Prop, Graph, - boost::detail::parameter_exists<ArgPack, Tag>::value + _parameter_exists::value >::result_type type; }; @@ -467,11 +470,12 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <typename ArgPack, typename Tag, typename Prop, typename Graph> typename override_property_result<ArgPack, Tag, Prop, Graph>::type override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { + typedef typename boost::mpl::has_key<ArgPack, Tag>::type _parameter_exists; return override_property_t< typename boost::parameter::value_type<ArgPack, Tag, int>::type, Prop, Graph, - boost::detail::parameter_exists<ArgPack, Tag>::value + _parameter_exists::value >()(g, ap[t | 0]); } @@ -482,7 +486,7 @@ BOOST_BGL_DECLARE_NAMED_PARAMS typedef boost::parameter::aux::tagged_argument<K, A> type; }; -#define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n) boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, BOOST_PP_SUB(n, i)), BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i))>, +#define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n) boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, BOOST_PP_SUB(n, i)), BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i))>, #define BOOST_GRAPH_MAKE_PAIR_PARAM(z, i, _) const boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, i), BOOST_PP_CAT(Arg, i)>& BOOST_PP_CAT(kw, i) #define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \ @@ -511,17 +515,26 @@ BOOST_BGL_DECLARE_NAMED_PARAMS BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq)) #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed) \ - template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)> \ - typename boost::result_of< \ - detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)> \ - (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ - const typename boost::detail::make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(nnamed, Keyword) BOOST_PP_COMMA_IF(nnamed) BOOST_PP_ENUM_PARAMS(nnamed, Arg))>::type&) \ - >::type \ - name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) \ - BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)) { \ - return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>() \ - (BOOST_PP_ENUM_PARAMS(nfixed, param), \ - (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw))); \ + template < \ + BOOST_PP_ENUM_PARAMS_Z(z, nfixed, typename Param) \ + BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, nnamed, typename ArgumentPack) \ + > \ + typename \ + BOOST_PP_EXPR_IF(nnamed, boost::lazy_enable_if<boost::parameter::is_argument_pack<ArgumentPack0>) \ + BOOST_PP_COMMA_IF(nnamed) \ + ::boost::graph::detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS_Z(z, nfixed, Param)> \ + BOOST_PP_EXPR_IF(nnamed, >)::type \ + name( \ + BOOST_PP_ENUM_BINARY_PARAMS_Z(z, nfixed, Param, const& param) \ + BOOST_PP_ENUM_TRAILING_BINARY_PARAMS_Z(z, nnamed, ArgumentPack, const& tagged_arg) \ + ) \ + { \ + return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)( \ + BOOST_PP_ENUM_PARAMS_Z(z, nfixed, param) \ + BOOST_PP_COMMA_IF(nnamed) BOOST_PP_LPAREN_IF(nnamed) \ + BOOST_PP_ENUM_PARAMS_Z(z, nnamed, tagged_arg) \ + BOOST_PP_RPAREN_IF(nnamed) \ + ); \ } #define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed) \ @@ -536,7 +549,6 @@ BOOST_BGL_DECLARE_NAMED_PARAMS BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params) \ return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ } \ - \ BOOST_PP_EXPR_IF(nfixed, template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_EXPR_IF(nfixed, >) \ BOOST_PP_EXPR_IF(nfixed, typename) boost::result_of< \ ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ @@ -561,14 +573,17 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <typename Graph, typename ArgPack, typename Value, typename PM> struct map_maker_helper<false, Graph, ArgPack, Value, PM> { + typedef typename boost::mpl::has_key< + ArgPack + , boost::graph::keywords::tag::vertex_index_map + >::type _parameter_exists; typedef typename boost::remove_const< typename override_const_property_t< typename boost::parameter::value_type< ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, boost::vertex_index_t, Graph, - boost::detail::parameter_exists< - ArgPack, boost::graph::keywords::tag::vertex_index_map>::value + _parameter_exists::value >::result_type>::type vi_map_type; typedef boost::shared_array_property_map<Value, vi_map_type> @@ -589,11 +604,8 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <typename Graph, typename ArgPack, typename MapTag, typename ValueType> struct map_maker { - BOOST_STATIC_CONSTANT( - bool, - has_map = - (parameter_exists<ArgPack, MapTag> - ::value)); + typedef typename boost::mpl::has_key<ArgPack, MapTag>::type _parameter_exists; + BOOST_STATIC_CONSTANT(bool, has_map = (_parameter_exists::value)); typedef map_maker_helper<has_map, Graph, ArgPack, ValueType, typename boost::remove_const< typename boost::parameter::value_type< @@ -666,11 +678,8 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare> struct priority_queue_maker { - BOOST_STATIC_CONSTANT( - bool, - g_hasQ = - (parameter_exists<ArgPack, PriorityQueueTag> - ::value)); + typedef typename boost::mpl::has_key<ArgPack, PriorityQueueTag>::type _parameter_exists; + BOOST_STATIC_CONSTANT(bool, g_hasQ = (_parameter_exists::value)); typedef boost::reference_wrapper<int> int_refw; typedef typename boost::parameter::value_type< ArgPack, diff --git a/boost/graph/one_bit_color_map.hpp b/boost/graph/one_bit_color_map.hpp index b153b732f7..aaf8943b00 100644 --- a/boost/graph/one_bit_color_map.hpp +++ b/boost/graph/one_bit_color_map.hpp @@ -16,6 +16,7 @@ #include <boost/property_map/property_map.hpp> #include <boost/graph/properties.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/shared_array.hpp> #include <boost/config.hpp> #include <boost/assert.hpp> @@ -97,8 +98,6 @@ make_one_bit_color_map(std::size_t n, const IndexMap& index_map) } // end namespace boost -#endif // BOOST_ONE_BIT_COLOR_MAP_HPP +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/one_bit_color_map.hpp>) -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/one_bit_color_map.hpp> -#endif +#endif // BOOST_ONE_BIT_COLOR_MAP_HPP diff --git a/boost/graph/page_rank.hpp b/boost/graph/page_rank.hpp index a8987046d3..1285444936 100644 --- a/boost/graph/page_rank.hpp +++ b/boost/graph/page_rank.hpp @@ -16,6 +16,7 @@ #include <boost/graph/properties.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/overloading.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <vector> namespace boost { namespace graph { @@ -154,8 +155,6 @@ remove_dangling_links(MutableGraph& g } } // end namespace boost::graph -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/page_rank.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/page_rank.hpp>) #endif // BOOST_GRAPH_PAGE_RANK_HPP diff --git a/boost/graph/parallel/distribution.hpp b/boost/graph/parallel/distribution.hpp index 8256b197e7..6dc974c1ae 100644 --- a/boost/graph/parallel/distribution.hpp +++ b/boost/graph/parallel/distribution.hpp @@ -22,6 +22,7 @@ #include <boost/iterator/counting_iterator.hpp> #include <boost/random/uniform_int.hpp> #include <boost/shared_ptr.hpp> +#include <boost/config.hpp> #include <typeinfo> namespace boost { namespace parallel { @@ -461,8 +462,12 @@ class twod_random make_counting_iterator(global_to_local.size()), global_to_local.begin()); +#if defined(BOOST_NO_CXX98_RANDOM_SHUFFLE) + std::shuffle(global_to_local.begin(), global_to_local.end(), gen); +#else random_int<RandomNumberGen> rand(gen); std::random_shuffle(global_to_local.begin(), global_to_local.end(), rand); +#endif } template<typename SizeType> @@ -563,9 +568,12 @@ class random_distribution make_counting_iterator(n), local_to_global.begin()); +#if defined(BOOST_NO_CXX98_RANDOM_SHUFFLE) + std::shuffle(local_to_global.begin(), local_to_global.end(), gen); +#else random_int<RandomNumberGen> rand(gen); std::random_shuffle(local_to_global.begin(), local_to_global.end(), rand); - +#endif for (std::vector<std::size_t>::size_type i = 0; i < n; ++i) global_to_local[local_to_global[i]] = i; diff --git a/boost/graph/planar_detail/boyer_myrvold_impl.hpp b/boost/graph/planar_detail/boyer_myrvold_impl.hpp index 45a552aa5d..f1b3cec822 100644 --- a/boost/graph/planar_detail/boyer_myrvold_impl.hpp +++ b/boost/graph/planar_detail/boyer_myrvold_impl.hpp @@ -591,7 +591,8 @@ namespace boost first_face_itr, second_face_itr, face_end; vertex_t first_side_vertex = graph_traits<Graph>::null_vertex(); - vertex_t second_side_vertex; + vertex_t second_side_vertex + = graph_traits<Graph>::null_vertex(); vertex_t first_tail, second_tail; first_tail = second_tail = curr_face_handle.get_anchor(); diff --git a/boost/graph/profile.hpp b/boost/graph/profile.hpp index 1ff99de5c4..54163c5af2 100644 --- a/boost/graph/profile.hpp +++ b/boost/graph/profile.hpp @@ -1,7 +1,8 @@ // //======================================================================= // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch) -// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st) +// ETH Zurich, Center of Structure Technologies +// (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/) // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at diff --git a/boost/graph/r_c_shortest_paths.hpp b/boost/graph/r_c_shortest_paths.hpp index 7e490fc7d2..ccd778c92e 100644 --- a/boost/graph/r_c_shortest_paths.hpp +++ b/boost/graph/r_c_shortest_paths.hpp @@ -2,7 +2,7 @@ // Copyright Michael Drexl 2005, 2006. // Distributed under the Boost Software License, Version 1.0. -// (See accompanying file LICENSE_1_0.txt or copy at +// (See accompanying file LICENSE_1_0.txt or copy at // http://boost.org/LICENSE_1_0.txt) #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP @@ -13,6 +13,8 @@ #include <vector> #include <list> +#include <boost/make_shared.hpp> +#include <boost/enable_shared_from_this.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/property_map/property_map.hpp> @@ -21,25 +23,23 @@ namespace boost { // r_c_shortest_paths_label struct template<class Graph, class Resource_Container> -struct r_c_shortest_paths_label +struct r_c_shortest_paths_label : public boost::enable_shared_from_this<r_c_shortest_paths_label<Graph, Resource_Container> > { r_c_shortest_paths_label - ( const unsigned long n, - const Resource_Container& rc = Resource_Container(), - const r_c_shortest_paths_label* const pl = 0, - const typename graph_traits<Graph>::edge_descriptor& ed = - graph_traits<Graph>::edge_descriptor(), - const typename graph_traits<Graph>::vertex_descriptor& vd = - graph_traits<Graph>::vertex_descriptor() ) - : num( n ), - cumulated_resource_consumption( rc ), - p_pred_label( pl ), - pred_edge( ed ), - resident_vertex( vd ), - b_is_dominated( false ), - b_is_processed( false ), - b_is_valid( true ) + ( const unsigned long n, + const Resource_Container& rc = Resource_Container(), + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > pl = boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> >(), + const typename graph_traits<Graph>::edge_descriptor& ed = graph_traits<Graph>::edge_descriptor(), + const typename graph_traits<Graph>::vertex_descriptor& vd = graph_traits<Graph>::vertex_descriptor() ) + : num( n ), + cumulated_resource_consumption( rc ), + p_pred_label( pl ), + pred_edge( ed ), + resident_vertex( vd ), + b_is_dominated( false ), + b_is_processed( false ) {} + r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other ) { if( this == &other ) @@ -50,179 +50,162 @@ struct r_c_shortest_paths_label } const unsigned long num; Resource_Container cumulated_resource_consumption; - const r_c_shortest_paths_label* const p_pred_label; + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > p_pred_label; const typename graph_traits<Graph>::edge_descriptor pred_edge; const typename graph_traits<Graph>::vertex_descriptor resident_vertex; bool b_is_dominated; bool b_is_processed; - bool b_is_valid; }; // r_c_shortest_paths_label template<class Graph, class Resource_Container> inline bool operator== -( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, +( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { - assert (l1.b_is_valid && l2.b_is_valid); - return + return l1.cumulated_resource_consumption == l2.cumulated_resource_consumption; } template<class Graph, class Resource_Container> inline bool operator!= -( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, +( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { - assert (l1.b_is_valid && l2.b_is_valid); - return + return !( l1 == l2 ); } template<class Graph, class Resource_Container> inline bool operator< -( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, +( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { - assert (l1.b_is_valid && l2.b_is_valid); - return + return l1.cumulated_resource_consumption < l2.cumulated_resource_consumption; } template<class Graph, class Resource_Container> inline bool operator> -( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, +( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { - assert (l1.b_is_valid && l2.b_is_valid); - return + return l2.cumulated_resource_consumption < l1.cumulated_resource_consumption; } template<class Graph, class Resource_Container> inline bool operator<= -( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, +( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { - assert (l1.b_is_valid && l2.b_is_valid); - return + return l1 < l2 || l1 == l2; } template<class Graph, class Resource_Container> inline bool operator>= -( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, +( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { - assert (l1.b_is_valid && l2.b_is_valid); return l2 < l1 || l1 == l2; } -namespace detail { +template<typename Graph, typename Resource_Container> +inline bool operator< + ( const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t, + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u) { + return *t < *u; +} -// ks_smart_pointer class -// from: -// Kuhlins, S.; Schader, M. (1999): -// Die C++-Standardbibliothek -// Springer, Berlin -// p. 333 f. -template<class T> -class ks_smart_pointer -{ -public: - ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {} - ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {} - ks_smart_pointer& operator=( const ks_smart_pointer& other ) - { pt = other.pt; return *this; } - ~ks_smart_pointer() {} - T& operator*() const { return *pt; } - T* operator->() const { return pt; } - T* get() const { return pt; } - operator T*() const { return pt; } - friend bool operator==( const ks_smart_pointer& t, - const ks_smart_pointer& u ) - { return *t.pt == *u.pt; } - friend bool operator!=( const ks_smart_pointer& t, - const ks_smart_pointer& u ) - { return *t.pt != *u.pt; } - friend bool operator<( const ks_smart_pointer& t, - const ks_smart_pointer& u ) - { return *t.pt < *u.pt; } - friend bool operator>( const ks_smart_pointer& t, - const ks_smart_pointer& u ) - { return *t.pt > *u.pt; } - friend bool operator<=( const ks_smart_pointer& t, - const ks_smart_pointer& u ) - { return *t.pt <= *u.pt; } - friend bool operator>=( const ks_smart_pointer& t, - const ks_smart_pointer& u ) - { return *t.pt >= *u.pt; } -private: - T* pt; -}; // ks_smart_pointer +template<typename Graph, typename Resource_Container> +inline bool operator<=( const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t, + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u ) { + return *t <= *u; +} + +template<typename Graph, typename Resource_Container> +inline bool operator> + ( + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t, + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u ) { + return *t > *u; +} +template<typename Graph, typename Resource_Container> +inline bool operator>= + ( + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t, + const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u) { + return *t >= *u; +} + +namespace detail { // r_c_shortest_paths_dispatch function (body/implementation) -template<class Graph, - class VertexIndexMap, - class EdgeIndexMap, - class Resource_Container, - class Resource_Extension_Function, - class Dominance_Function, - class Label_Allocator, +template<class Graph, + class VertexIndexMap, + class EdgeIndexMap, + class Resource_Container, + class Resource_Extension_Function, + class Dominance_Function, + class Label_Allocator, class Visitor> void r_c_shortest_paths_dispatch -( const Graph& g, - const VertexIndexMap& vertex_index_map, - const EdgeIndexMap& /*edge_index_map*/, - typename graph_traits<Graph>::vertex_descriptor s, - typename graph_traits<Graph>::vertex_descriptor t, +( const Graph& g, + const VertexIndexMap& vertex_index_map, + const EdgeIndexMap& /*edge_index_map*/, + typename graph_traits<Graph>::vertex_descriptor s, + typename graph_traits<Graph>::vertex_descriptor t, // each inner vector corresponds to a pareto-optimal path std::vector <std::vector <typename graph_traits - <Graph>::edge_descriptor> >& pareto_optimal_solutions, + <Graph>::edge_descriptor> >& pareto_optimal_solutions, std::vector - <Resource_Container>& pareto_optimal_resource_containers, - bool b_all_pareto_optimal_solutions, - // to initialize the first label/resource container + <Resource_Container>& pareto_optimal_resource_containers, + bool b_all_pareto_optimal_solutions, + // to initialize the first label/resource container // and to carry the type information - const Resource_Container& rc, - Resource_Extension_Function& ref, - Dominance_Function& dominance, + const Resource_Container& rc, + Resource_Extension_Function& ref, + Dominance_Function& dominance, // to specify the memory management strategy for the labels - Label_Allocator /*la*/, + Label_Allocator /*la*/, Visitor vis ) { pareto_optimal_resource_containers.clear(); pareto_optimal_solutions.clear(); size_t i_label_num = 0; - typedef - typename +#if defined(BOOST_NO_CXX11_ALLOCATOR) + typedef + typename Label_Allocator::template rebind <r_c_shortest_paths_label <Graph, Resource_Container> >::other LAlloc; +#else + typedef + typename + std::allocator_traits<Label_Allocator>::template rebind_alloc + <r_c_shortest_paths_label + <Graph, Resource_Container> > LAlloc; + typedef std::allocator_traits<LAlloc> LTraits; +#endif LAlloc l_alloc; - typedef - ks_smart_pointer - <r_c_shortest_paths_label<Graph, Resource_Container> > Splabel; - std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> > + typedef + boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > Splabel; + std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> > unprocessed_labels; bool b_feasible = true; - r_c_shortest_paths_label<Graph, Resource_Container>* first_label = - l_alloc.allocate( 1 ); - l_alloc.construct - ( first_label, - r_c_shortest_paths_label - <Graph, Resource_Container>( i_label_num++, - rc, - 0, - typename graph_traits<Graph>:: - edge_descriptor(), - s ) ); - - Splabel splabel_first_label = Splabel( first_label ); + Splabel splabel_first_label = boost::allocate_shared<r_c_shortest_paths_label<Graph, Resource_Container> >( + l_alloc, + i_label_num++, + rc, + boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> >(), + typename graph_traits<Graph>::edge_descriptor(), + s ); + unprocessed_labels.push( splabel_first_label ); std::vector<std::list<Splabel> > vec_vertex_labels_data( num_vertices( g ) ); iterator_property_map<typename std::vector<std::list<Splabel> >::iterator, @@ -230,7 +213,7 @@ void r_c_shortest_paths_dispatch vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map); vec_vertex_labels[s].push_back( splabel_first_label ); typedef - std::vector<typename std::list<Splabel>::iterator> + std::vector<typename std::list<Splabel>::iterator> vec_last_valid_positions_for_dominance_data_type; vec_last_valid_positions_for_dominance_data_type vec_last_valid_positions_for_dominance_data( num_vertices( g ) ); @@ -247,7 +230,7 @@ void r_c_shortest_paths_dispatch iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap> vec_last_valid_index_for_dominance (vec_last_valid_index_for_dominance_data.begin(), vertex_index_map); - std::vector<bool> + std::vector<bool> b_vec_vertex_already_checked_for_dominance_data( num_vertices( g ), false ); iterator_property_map<std::vector<bool>::iterator, VertexIndexMap> b_vec_vertex_already_checked_for_dominance @@ -257,42 +240,39 @@ void r_c_shortest_paths_dispatch while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) ) { Splabel cur_label = unprocessed_labels.top(); - assert (cur_label->b_is_valid); unprocessed_labels.pop(); vis.on_label_popped( *cur_label, g ); - // an Splabel object in unprocessed_labels and the respective Splabel - // object in the respective list<Splabel> of vec_vertex_labels share their + // an Splabel object in unprocessed_labels and the respective Splabel + // object in the respective list<Splabel> of vec_vertex_labels share their // embedded r_c_shortest_paths_label object - // to avoid memory leaks, dominated - // r_c_shortest_paths_label objects are marked and deleted when popped - // from unprocessed_labels, as they can no longer be deleted at the end of - // the function; only the Splabel object in unprocessed_labels still + // to avoid memory leaks, dominated + // r_c_shortest_paths_label objects are marked and deleted when popped + // from unprocessed_labels, as they can no longer be deleted at the end of + // the function; only the Splabel object in unprocessed_labels still // references the r_c_shortest_paths_label object - // this is also for efficiency, because the else branch is executed only - // if there is a chance that extending the - // label leads to new undominated labels, which in turn is possible only + // this is also for efficiency, because the else branch is executed only + // if there is a chance that extending the + // label leads to new undominated labels, which in turn is possible only // if the label to be extended is undominated - assert (cur_label->b_is_valid); if( !cur_label->b_is_dominated ) { typename boost::graph_traits<Graph>::vertex_descriptor i_cur_resident_vertex = cur_label->resident_vertex; - std::list<Splabel>& list_labels_cur_vertex = + std::list<Splabel>& list_labels_cur_vertex = get(vec_vertex_labels, i_cur_resident_vertex); - if( list_labels_cur_vertex.size() >= 2 - && vec_last_valid_index_for_dominance[i_cur_resident_vertex] + if( list_labels_cur_vertex.size() >= 2 + && vec_last_valid_index_for_dominance[i_cur_resident_vertex] < list_labels_cur_vertex.size() ) { - typename std::list<Splabel>::iterator outer_iter = + typename std::list<Splabel>::iterator outer_iter = list_labels_cur_vertex.begin(); bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = false; while( outer_iter != list_labels_cur_vertex.end() ) { Splabel cur_outer_splabel = *outer_iter; - assert (cur_outer_splabel->b_is_valid); typename std::list<Splabel>::iterator inner_iter = outer_iter; - if( !b_outer_iter_at_or_beyond_last_valid_pos_for_dominance - && outer_iter == + if( !b_outer_iter_at_or_beyond_last_valid_pos_for_dominance + && outer_iter == get(vec_last_valid_positions_for_dominance, i_cur_resident_vertex) ) b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true; @@ -303,7 +283,7 @@ void r_c_shortest_paths_dispatch } else { - inner_iter = + inner_iter = get(vec_last_valid_positions_for_dominance, i_cur_resident_vertex); ++inner_iter; @@ -312,9 +292,8 @@ void r_c_shortest_paths_dispatch while( inner_iter != list_labels_cur_vertex.end() ) { Splabel cur_inner_splabel = *inner_iter; - assert (cur_inner_splabel->b_is_valid); if( dominance( cur_outer_splabel-> - cumulated_resource_consumption, + cumulated_resource_consumption, cur_inner_splabel-> cumulated_resource_consumption ) ) { @@ -323,9 +302,7 @@ void r_c_shortest_paths_dispatch list_labels_cur_vertex.erase( buf ); if( cur_inner_splabel->b_is_processed ) { - cur_inner_splabel->b_is_valid = false; - l_alloc.destroy( cur_inner_splabel.get() ); - l_alloc.deallocate( cur_inner_splabel.get(), 1 ); + cur_inner_splabel.reset(); } else cur_inner_splabel->b_is_dominated = true; @@ -334,7 +311,7 @@ void r_c_shortest_paths_dispatch else ++inner_iter; if( dominance( cur_inner_splabel-> - cumulated_resource_consumption, + cumulated_resource_consumption, cur_outer_splabel-> cumulated_resource_consumption ) ) { @@ -342,12 +319,9 @@ void r_c_shortest_paths_dispatch ++outer_iter; list_labels_cur_vertex.erase( buf ); b_outer_iter_erased = true; - assert (cur_outer_splabel->b_is_valid); if( cur_outer_splabel->b_is_processed ) { - cur_outer_splabel->b_is_valid = false; - l_alloc.destroy( cur_outer_splabel.get() ); - l_alloc.deallocate( cur_outer_splabel.get(), 1 ); + cur_outer_splabel.reset(); } else cur_outer_splabel->b_is_dominated = true; @@ -369,28 +343,22 @@ void r_c_shortest_paths_dispatch list_labels_cur_vertex.size() - 1); } } - assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid); if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t ) { // the devil don't sleep if( cur_label->b_is_dominated ) { - cur_label->b_is_valid = false; - l_alloc.destroy( cur_label.get() ); - l_alloc.deallocate( cur_label.get(), 1 ); + cur_label.reset(); } while( unprocessed_labels.size() ) { Splabel l = unprocessed_labels.top(); - assert (l->b_is_valid); unprocessed_labels.pop(); - // delete only dominated labels, because nondominated labels are + // delete only dominated labels, because nondominated labels are // deleted at the end of the function if( l->b_is_dominated ) { - l->b_is_valid = false; - l_alloc.destroy( l.get() ); - l_alloc.deallocate( l.get(), 1 ); + l.reset(); } } break; @@ -399,56 +367,45 @@ void r_c_shortest_paths_dispatch { cur_label->b_is_processed = true; vis.on_label_not_dominated( *cur_label, g ); - typename graph_traits<Graph>::vertex_descriptor cur_vertex = + typename graph_traits<Graph>::vertex_descriptor cur_vertex = cur_label->resident_vertex; typename graph_traits<Graph>::out_edge_iterator oei, oei_end; - for( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g ); - oei != oei_end; + for( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g ); + oei != oei_end; ++oei ) { b_feasible = true; - r_c_shortest_paths_label<Graph, Resource_Container>* new_label = - l_alloc.allocate( 1 ); - l_alloc.construct( new_label, - r_c_shortest_paths_label - <Graph, Resource_Container> - ( i_label_num++, - cur_label->cumulated_resource_consumption, - cur_label.get(), - *oei, - target( *oei, g ) ) ); - b_feasible = - ref( g, - new_label->cumulated_resource_consumption, - new_label->p_pred_label->cumulated_resource_consumption, + Splabel new_label = boost::allocate_shared<r_c_shortest_paths_label<Graph, Resource_Container> >( + l_alloc, + i_label_num++, + cur_label->cumulated_resource_consumption, + cur_label, + *oei, + target( *oei, g ) ); + b_feasible = + ref( g, + new_label->cumulated_resource_consumption, + new_label->p_pred_label->cumulated_resource_consumption, new_label->pred_edge ); if( !b_feasible ) { vis.on_label_not_feasible( *new_label, g ); - new_label->b_is_valid = false; - l_alloc.destroy( new_label ); - l_alloc.deallocate( new_label, 1 ); + new_label.reset(); } else { - const r_c_shortest_paths_label<Graph, Resource_Container>& - ref_new_label = *new_label; - vis.on_label_feasible( ref_new_label, g ); - Splabel new_sp_label( new_label ); - vec_vertex_labels[new_sp_label->resident_vertex]. - push_back( new_sp_label ); - unprocessed_labels.push( new_sp_label ); + vis.on_label_feasible( *new_label, g ); + vec_vertex_labels[new_label->resident_vertex]. + push_back( new_label ); + unprocessed_labels.push( new_label ); } } } else { - assert (cur_label->b_is_valid); vis.on_label_dominated( *cur_label, g ); - cur_label->b_is_valid = false; - l_alloc.destroy( cur_label.get() ); - l_alloc.deallocate( cur_label.get(), 1 ); + cur_label.reset(); } } std::list<Splabel> dsplabels = get(vec_vertex_labels, t); @@ -459,18 +416,31 @@ void r_c_shortest_paths_dispatch { for( ; csi != csi_end; ++csi ) { - std::vector<typename graph_traits<Graph>::edge_descriptor> + std::vector<typename graph_traits<Graph>::edge_descriptor> cur_pareto_optimal_path; - const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label = - (*csi).get(); - assert (p_cur_label->b_is_valid); + boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > p_cur_label = *csi; pareto_optimal_resource_containers. push_back( p_cur_label->cumulated_resource_consumption ); while( p_cur_label->num != 0 ) { cur_pareto_optimal_path.push_back( p_cur_label->pred_edge ); p_cur_label = p_cur_label->p_pred_label; - assert (p_cur_label->b_is_valid); + + // assertion b_is_valid beyond this point is not correct if the domination function + // requires resource levels to be strictly greater than existing values + // + // Example + // Customers + // id min_arrival max_departure + // 2 0 974 + // 3 0 972 + // 4 0 964 + // 5 678 801 + // + // Path A: 2-3-4-5 (times: 0-16-49-84-678) + // Path B: 3-2-4-5 (times: 0-18-51-62-678) + // The partial path 3-2-4 dominates the other partial path 2-3-4, + // though the path 3-2-4-5 does not strictly dominate the path 2-3-4-5 } pareto_optimal_solutions.push_back( cur_pareto_optimal_path ); if( !b_all_pareto_optimal_solutions ) @@ -479,14 +449,12 @@ void r_c_shortest_paths_dispatch } BGL_FORALL_VERTICES_T(i, g, Graph) { - const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i]; - csi_end = list_labels_cur_vertex.end(); - for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi ) + std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i]; + typename std::list<Splabel>::iterator si = list_labels_cur_vertex.begin(); + const typename std::list<Splabel>::iterator si_end = list_labels_cur_vertex.end(); + for(; si != si_end; ++si ) { - assert ((*csi)->b_is_valid); - (*csi)->b_is_valid = false; - l_alloc.destroy( (*csi).get() ); - l_alloc.deallocate( (*csi).get(), 1 ); + (*si).reset(); } } } // r_c_shortest_paths_dispatch @@ -506,13 +474,13 @@ struct default_r_c_shortest_paths_visitor 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> + template<class Queue, class Graph> bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;} }; // default_r_c_shortest_paths_visitor // default_r_c_shortest_paths_allocator -typedef +typedef std::allocator<int> default_r_c_shortest_paths_allocator; // default_r_c_shortest_paths_allocator @@ -521,93 +489,93 @@ typedef // first overload: // - return all pareto-optimal solutions // - specify Label_Allocator and Visitor arguments -template<class Graph, - class VertexIndexMap, - class EdgeIndexMap, - class Resource_Container, - class Resource_Extension_Function, - class Dominance_Function, - class Label_Allocator, +template<class Graph, + class VertexIndexMap, + class EdgeIndexMap, + class Resource_Container, + class Resource_Extension_Function, + class Dominance_Function, + class Label_Allocator, class Visitor> void r_c_shortest_paths -( const Graph& g, - const VertexIndexMap& vertex_index_map, - const EdgeIndexMap& edge_index_map, - typename graph_traits<Graph>::vertex_descriptor s, - typename graph_traits<Graph>::vertex_descriptor t, +( const Graph& g, + const VertexIndexMap& vertex_index_map, + const EdgeIndexMap& edge_index_map, + typename graph_traits<Graph>::vertex_descriptor s, + typename graph_traits<Graph>::vertex_descriptor t, // each inner vector corresponds to a pareto-optimal path - std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& - pareto_optimal_solutions, - std::vector<Resource_Container>& pareto_optimal_resource_containers, - // to initialize the first label/resource container + std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& + pareto_optimal_solutions, + std::vector<Resource_Container>& pareto_optimal_resource_containers, + // to initialize the first label/resource container // and to carry the type information - const Resource_Container& rc, - const Resource_Extension_Function& ref, - const Dominance_Function& dominance, + const Resource_Container& rc, + const Resource_Extension_Function& ref, + const Dominance_Function& dominance, // to specify the memory management strategy for the labels - Label_Allocator la, + Label_Allocator la, Visitor vis ) { - r_c_shortest_paths_dispatch( g, - vertex_index_map, - edge_index_map, - s, - t, - pareto_optimal_solutions, - pareto_optimal_resource_containers, - true, - rc, - ref, - dominance, - la, + r_c_shortest_paths_dispatch( g, + vertex_index_map, + edge_index_map, + s, + t, + pareto_optimal_solutions, + pareto_optimal_resource_containers, + true, + rc, + ref, + dominance, + la, vis ); } // second overload: // - return only one pareto-optimal solution // - specify Label_Allocator and Visitor arguments -template<class Graph, - class VertexIndexMap, - class EdgeIndexMap, - class Resource_Container, - class Resource_Extension_Function, - class Dominance_Function, - class Label_Allocator, +template<class Graph, + class VertexIndexMap, + class EdgeIndexMap, + class Resource_Container, + class Resource_Extension_Function, + class Dominance_Function, + class Label_Allocator, class Visitor> void r_c_shortest_paths -( const Graph& g, - const VertexIndexMap& vertex_index_map, - const EdgeIndexMap& edge_index_map, - typename graph_traits<Graph>::vertex_descriptor s, - typename graph_traits<Graph>::vertex_descriptor t, - std::vector<typename graph_traits<Graph>::edge_descriptor>& - pareto_optimal_solution, - Resource_Container& pareto_optimal_resource_container, - // to initialize the first label/resource container +( const Graph& g, + const VertexIndexMap& vertex_index_map, + const EdgeIndexMap& edge_index_map, + typename graph_traits<Graph>::vertex_descriptor s, + typename graph_traits<Graph>::vertex_descriptor t, + std::vector<typename graph_traits<Graph>::edge_descriptor>& + pareto_optimal_solution, + Resource_Container& pareto_optimal_resource_container, + // to initialize the first label/resource container // and to carry the type information - const Resource_Container& rc, - const Resource_Extension_Function& ref, - const Dominance_Function& dominance, + const Resource_Container& rc, + const Resource_Extension_Function& ref, + const Dominance_Function& dominance, // to specify the memory management strategy for the labels - Label_Allocator la, + Label_Allocator la, Visitor vis ) { // each inner vector corresponds to a pareto-optimal path - std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > + std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > pareto_optimal_solutions; std::vector<Resource_Container> pareto_optimal_resource_containers; - r_c_shortest_paths_dispatch( g, - vertex_index_map, - edge_index_map, - s, - t, - pareto_optimal_solutions, - pareto_optimal_resource_containers, - false, - rc, - ref, - dominance, - la, + r_c_shortest_paths_dispatch( g, + vertex_index_map, + edge_index_map, + s, + t, + pareto_optimal_solutions, + pareto_optimal_resource_containers, + false, + rc, + ref, + dominance, + la, vis ); if (!pareto_optimal_solutions.empty()) { pareto_optimal_solution = pareto_optimal_solutions[0]; @@ -618,83 +586,83 @@ void r_c_shortest_paths // third overload: // - return all pareto-optimal solutions // - use default Label_Allocator and Visitor -template<class Graph, - class VertexIndexMap, - class EdgeIndexMap, - class Resource_Container, - class Resource_Extension_Function, +template<class Graph, + class VertexIndexMap, + class EdgeIndexMap, + class Resource_Container, + class Resource_Extension_Function, class Dominance_Function> void r_c_shortest_paths -( const Graph& g, - const VertexIndexMap& vertex_index_map, - const EdgeIndexMap& edge_index_map, - typename graph_traits<Graph>::vertex_descriptor s, - typename graph_traits<Graph>::vertex_descriptor t, +( const Graph& g, + const VertexIndexMap& vertex_index_map, + const EdgeIndexMap& edge_index_map, + typename graph_traits<Graph>::vertex_descriptor s, + typename graph_traits<Graph>::vertex_descriptor t, // each inner vector corresponds to a pareto-optimal path - std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& - pareto_optimal_solutions, - std::vector<Resource_Container>& pareto_optimal_resource_containers, - // to initialize the first label/resource container + std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& + pareto_optimal_solutions, + std::vector<Resource_Container>& pareto_optimal_resource_containers, + // to initialize the first label/resource container // and to carry the type information - const Resource_Container& rc, - const Resource_Extension_Function& ref, + const Resource_Container& rc, + const Resource_Extension_Function& ref, const Dominance_Function& dominance ) { - r_c_shortest_paths_dispatch( g, - vertex_index_map, - edge_index_map, - s, - t, - pareto_optimal_solutions, - pareto_optimal_resource_containers, - true, - rc, - ref, - dominance, - default_r_c_shortest_paths_allocator(), + r_c_shortest_paths_dispatch( g, + vertex_index_map, + edge_index_map, + s, + t, + pareto_optimal_solutions, + pareto_optimal_resource_containers, + true, + rc, + ref, + dominance, + default_r_c_shortest_paths_allocator(), default_r_c_shortest_paths_visitor() ); } // fourth overload: // - return only one pareto-optimal solution // - use default Label_Allocator and Visitor -template<class Graph, - class VertexIndexMap, - class EdgeIndexMap, - class Resource_Container, - class Resource_Extension_Function, +template<class Graph, + class VertexIndexMap, + class EdgeIndexMap, + class Resource_Container, + class Resource_Extension_Function, class Dominance_Function> void r_c_shortest_paths -( const Graph& g, - const VertexIndexMap& vertex_index_map, - const EdgeIndexMap& edge_index_map, - typename graph_traits<Graph>::vertex_descriptor s, - typename graph_traits<Graph>::vertex_descriptor t, - std::vector<typename graph_traits<Graph>::edge_descriptor>& - pareto_optimal_solution, - Resource_Container& pareto_optimal_resource_container, - // to initialize the first label/resource container +( const Graph& g, + const VertexIndexMap& vertex_index_map, + const EdgeIndexMap& edge_index_map, + typename graph_traits<Graph>::vertex_descriptor s, + typename graph_traits<Graph>::vertex_descriptor t, + std::vector<typename graph_traits<Graph>::edge_descriptor>& + pareto_optimal_solution, + Resource_Container& pareto_optimal_resource_container, + // to initialize the first label/resource container // and to carry the type information - const Resource_Container& rc, - const Resource_Extension_Function& ref, + const Resource_Container& rc, + const Resource_Extension_Function& ref, const Dominance_Function& dominance ) { // each inner vector corresponds to a pareto-optimal path - std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > + std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > pareto_optimal_solutions; std::vector<Resource_Container> pareto_optimal_resource_containers; - r_c_shortest_paths_dispatch( g, - vertex_index_map, - edge_index_map, - s, - t, - pareto_optimal_solutions, - pareto_optimal_resource_containers, - false, - rc, - ref, - dominance, - default_r_c_shortest_paths_allocator(), + r_c_shortest_paths_dispatch( g, + vertex_index_map, + edge_index_map, + s, + t, + pareto_optimal_solutions, + pareto_optimal_resource_containers, + false, + rc, + ref, + dominance, + default_r_c_shortest_paths_allocator(), default_r_c_shortest_paths_visitor() ); if (!pareto_optimal_solutions.empty()) { pareto_optimal_solution = pareto_optimal_solutions[0]; @@ -705,26 +673,26 @@ void r_c_shortest_paths // check_r_c_path function -template<class Graph, - class Resource_Container, +template<class Graph, + class Resource_Container, class Resource_Extension_Function> -void check_r_c_path( const Graph& g, +void check_r_c_path( const Graph& g, const std::vector <typename graph_traits - <Graph>::edge_descriptor>& ed_vec_path, - const Resource_Container& initial_resource_levels, - // if true, computed accumulated final resource levels must + <Graph>::edge_descriptor>& ed_vec_path, + const Resource_Container& initial_resource_levels, + // if true, computed accumulated final resource levels must // be equal to desired_final_resource_levels - // if false, computed accumulated final resource levels must + // if false, computed accumulated final resource levels must // be less than or equal to desired_final_resource_levels - bool b_result_must_be_equal_to_desired_final_resource_levels, - const Resource_Container& desired_final_resource_levels, - Resource_Container& actual_final_resource_levels, - const Resource_Extension_Function& ref, - bool& b_is_a_path_at_all, - bool& b_feasible, - bool& b_correctly_extended, - typename graph_traits<Graph>::edge_descriptor& + bool b_result_must_be_equal_to_desired_final_resource_levels, + const Resource_Container& desired_final_resource_levels, + Resource_Container& actual_final_resource_levels, + const Resource_Extension_Function& ref, + bool& b_is_a_path_at_all, + bool& b_feasible, + bool& b_correctly_extended, + typename graph_traits<Graph>::edge_descriptor& ed_last_extended_arc ) { size_t i_size_ed_vec_path = ed_vec_path.size(); @@ -733,7 +701,7 @@ void check_r_c_path( const Graph& g, b_feasible = true; else { - if( i_size_ed_vec_path == 1 + if( i_size_ed_vec_path == 1 || target( ed_vec_path[0], g ) == source( ed_vec_path[1], g ) ) buf_path = ed_vec_path; else @@ -758,21 +726,21 @@ void check_r_c_path( const Graph& g, for( size_t i = 0; i < i_size_ed_vec_path; ++i ) { ed_last_extended_arc = buf_path[i]; - b_feasible = ref( g, - actual_final_resource_levels, - current_resource_levels, + b_feasible = ref( g, + actual_final_resource_levels, + current_resource_levels, buf_path[i] ); current_resource_levels = actual_final_resource_levels; if( !b_feasible ) return; } if( b_result_must_be_equal_to_desired_final_resource_levels ) - b_correctly_extended = - actual_final_resource_levels == desired_final_resource_levels ? + b_correctly_extended = + actual_final_resource_levels == desired_final_resource_levels ? true : false; else { - if( actual_final_resource_levels < desired_final_resource_levels + if( actual_final_resource_levels < desired_final_resource_levels || actual_final_resource_levels == desired_final_resource_levels ) b_correctly_extended = true; } diff --git a/boost/graph/random_spanning_tree.hpp b/boost/graph/random_spanning_tree.hpp index 76dc7f2b9a..ee23c5e1ee 100644 --- a/boost/graph/random_spanning_tree.hpp +++ b/boost/graph/random_spanning_tree.hpp @@ -95,12 +95,26 @@ namespace boost { using namespace boost::graph::keywords; typedef bgl_named_params<P, T, R> params_type; BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) - random_spanning_tree(g, - gen, - arg_pack[_root_vertex | *vertices(g).first], - arg_pack[_predecessor_map], - arg_pack[_weight_map | static_property_map<double>(1.)], - boost::detail::make_color_map_from_arg_pack(g, arg_pack)); + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + vertex_descriptor default_vertex = *vertices(g).first; + vertex_descriptor start_vertex = arg_pack[_root_vertex | default_vertex]; + typename boost::parameter::binding< + arg_pack_type, + boost::graph::keywords::tag::predecessor_map + >::type pred_map = arg_pack[_predecessor_map]; + static_property_map<double> default_weight_map(1.); + typename boost::parameter::value_type< + arg_pack_type, + boost::graph::keywords::tag::weight_map, + static_property_map<double> + >::type e_w_map = arg_pack[_weight_map | default_weight_map]; + typename boost::detail::map_maker< + Graph, + arg_pack_type, + boost::graph::keywords::tag::color_map, + boost::default_color_type + >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); + random_spanning_tree(g, gen, start_vertex, pred_map, e_w_map, c_map); } } diff --git a/boost/graph/relax.hpp b/boost/graph/relax.hpp index e3866df484..ea9521b237 100644 --- a/boost/graph/relax.hpp +++ b/boost/graph/relax.hpp @@ -76,6 +76,37 @@ namespace boost { } else return false; } + + template <class Graph, class WeightMap, + class PredecessorMap, class DistanceMap, + class BinaryFunction, class BinaryPredicate> + bool relax_target(typename graph_traits<Graph>::edge_descriptor e, + const Graph& g, const WeightMap& w, + PredecessorMap& p, DistanceMap& d, + const BinaryFunction& combine, const BinaryPredicate& compare) + { + typedef typename graph_traits<Graph>::vertex_descriptor Vertex; + typedef typename property_traits<DistanceMap>::value_type D; + typedef typename property_traits<WeightMap>::value_type W; + const Vertex u = source(e, g); + const Vertex v = target(e, g); + const D d_u = get(d, u); + const D d_v = get(d, v); + const W& w_e = get(w, e); + + // The seemingly redundant comparisons after the distance puts are to + // ensure that extra floating-point precision in x87 registers does not + // lead to relax() returning true when the distance did not actually + // change. + if (compare(combine(d_u, w_e), d_v)) { + put(d, v, combine(d_u, w_e)); + if (compare(get(d, v), d_v)) { + put(p, v, u); + return true; + } + } + return false; + } template <class Graph, class WeightMap, class PredecessorMap, class DistanceMap> diff --git a/boost/graph/rmat_graph_generator.hpp b/boost/graph/rmat_graph_generator.hpp index f083fc5558..a96887fbd6 100644 --- a/boost/graph/rmat_graph_generator.hpp +++ b/boost/graph/rmat_graph_generator.hpp @@ -20,6 +20,7 @@ #include <boost/random/uniform_int.hpp> #include <boost/random/uniform_01.hpp> #include <boost/graph/graph_traits.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/type_traits/is_base_and_derived.hpp> #include <boost/type_traits/is_same.hpp> // #include <boost/test/floating_point_comparison.hpp> @@ -588,8 +589,6 @@ namespace boost { } // end namespace boost -#ifdef BOOST_GRAPH_USE_MPI -#include <boost/graph/distributed/rmat_graph_generator.hpp> -#endif // BOOST_GRAPH_USE_MPI +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/rmat_graph_generator.hpp>) #endif // BOOST_GRAPH_RMAT_GENERATOR_HPP diff --git a/boost/graph/sloan_ordering.hpp b/boost/graph/sloan_ordering.hpp index 88ad1b297f..afc634a921 100644 --- a/boost/graph/sloan_ordering.hpp +++ b/boost/graph/sloan_ordering.hpp @@ -1,7 +1,8 @@ // //======================================================================= // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch) -// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st) +// ETH Zurich, Center of Structure Technologies +// (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/) // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at diff --git a/boost/graph/stanford_graph.hpp b/boost/graph/stanford_graph.hpp index 01431737bf..d9b451a8f3 100644 --- a/boost/graph/stanford_graph.hpp +++ b/boost/graph/stanford_graph.hpp @@ -10,7 +10,6 @@ #define BOOST_GRAPH_SGB_GRAPH_HPP #include <boost/config.hpp> -#include <boost/iterator.hpp> #include <boost/operators.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/graph_traits.hpp> diff --git a/boost/graph/stoer_wagner_min_cut.hpp b/boost/graph/stoer_wagner_min_cut.hpp index eb5998c710..357f170840 100644 --- a/boost/graph/stoer_wagner_min_cut.hpp +++ b/boost/graph/stoer_wagner_min_cut.hpp @@ -215,9 +215,10 @@ namespace graph { typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack); + boost::dummy_property_map dummy_prop; return boost::stoer_wagner_min_cut(g, weights, - arg_pack [_parity_map | boost::dummy_property_map()], + arg_pack [_parity_map | dummy_prop], 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) diff --git a/boost/graph/strong_components.hpp b/boost/graph/strong_components.hpp index f1bd56d6f7..67dbfdd806 100644 --- a/boost/graph/strong_components.hpp +++ b/boost/graph/strong_components.hpp @@ -18,6 +18,7 @@ #include <boost/type_traits/conversion_traits.hpp> #include <boost/static_assert.hpp> #include <boost/graph/overloading.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/concept/assert.hpp> namespace boost { @@ -336,8 +337,6 @@ namespace boost { } // namespace boost -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/strong_components.hpp> -#endif +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/strong_components.hpp>) #endif // BOOST_GRAPH_STRONG_COMPONENTS_HPP diff --git a/boost/graph/subgraph.hpp b/boost/graph/subgraph.hpp index 22706bc617..3d068a5c36 100644 --- a/boost/graph/subgraph.hpp +++ b/boost/graph/subgraph.hpp @@ -131,12 +131,24 @@ public: // copy constructor subgraph(const subgraph& x) - : m_parent(x.m_parent), m_edge_counter(x.m_edge_counter) - , m_global_vertex(x.m_global_vertex), m_global_edge(x.m_global_edge) + : m_parent(x.m_parent), m_edge_counter(0) { if(x.is_root()) { - m_graph = x.m_graph; + m_graph = x.m_graph; + m_edge_counter = x.m_edge_counter; + m_global_vertex = x.m_global_vertex; + m_global_edge = x.m_global_edge; + } + else + { + get_property(*this) = get_property(x); + typename subgraph<Graph>::vertex_iterator vi,vi_end; + boost::tie(vi, vi_end) = vertices(x); + for(; vi != vi_end; ++vi) + { + add_vertex(x.local_to_global(*vi), *this); + } } // Do a deep copy (recursive). // Only the root graph is copied, the subgraphs contain @@ -144,16 +156,10 @@ public: typename subgraph<Graph>::children_iterator i,i_end; boost::tie(i,i_end) = x.children(); for(; i != i_end; ++i) - { - subgraph<Graph> child = this->create_subgraph(); - child = *i; - vertex_iterator vi,vi_end; - boost::tie(vi,vi_end) = vertices(*i); - for (;vi!=vi_end;++vi) - { - add_vertex(*vi,child); - } - } + { + m_children.push_back(new subgraph<Graph>(*i)); + m_children.back()->m_parent = this; + } } @@ -371,46 +377,54 @@ typename subgraph<G>::vertex_descriptor add_vertex(typename subgraph<G>::vertex_descriptor u_global, subgraph<G>& g) { - BOOST_ASSERT(!g.is_root()); - typename subgraph<G>::vertex_descriptor u_local, v_global; - typename subgraph<G>::edge_descriptor e_global; - - u_local = add_vertex(g.m_graph); - g.m_global_vertex.push_back(u_global); - g.m_local_vertex[u_global] = u_local; - - subgraph<G>& r = g.root(); - - // remember edge global and local maps - { - typename subgraph<G>::out_edge_iterator ei, ei_end; - for (boost::tie(ei, ei_end) = out_edges(u_global, r); - ei != ei_end; ++ei) { - e_global = *ei; - v_global = target(e_global, r); - if (g.find_vertex(v_global).second == true) - g.local_add_edge(u_local, g.global_to_local(v_global), e_global); - } - } - if (is_directed(g)) { // not necessary for undirected graph - typename subgraph<G>::vertex_iterator vi, vi_end; - typename subgraph<G>::out_edge_iterator ei, ei_end; - for(boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) { - v_global = *vi; - if (v_global == u_global) - continue; // don't insert self loops twice! - if (!g.find_vertex(v_global).second) - continue; // not a subgraph vertex => try next one - for(boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) { - e_global = *ei; - if(target(e_global, r) == u_global) { - g.local_add_edge(g.global_to_local(v_global), u_local, e_global); - } + BOOST_ASSERT(!g.is_root()); + typename subgraph<G>::vertex_descriptor u_local; + bool exists_local; + boost::tie(u_local, exists_local) = g.find_vertex(u_global); + + if (!exists_local) { + typename subgraph<G>::vertex_descriptor v_global; + typename subgraph<G>::edge_descriptor e_global; + // call recursion for parent subgraph + if (!g.parent().is_root()) + add_vertex(u_global, g.parent()); + + u_local = add_vertex(g.m_graph); + g.m_global_vertex.push_back(u_global); + g.m_local_vertex[u_global] = u_local; + + subgraph<G>& r = g.root(); + + // remember edge global and local maps + { + typename subgraph<G>::out_edge_iterator ei, ei_end; + for (boost::tie(ei, ei_end) = out_edges(u_global, r); + ei != ei_end; ++ei) { + e_global = *ei; + v_global = target(e_global, r); + if (g.find_vertex(v_global).second == true) + g.local_add_edge(u_local, g.global_to_local(v_global), e_global); } - } - } - - return u_local; + } + if (is_directed(g)) { // not necessary for undirected graph + typename subgraph<G>::vertex_iterator vi, vi_end; + typename subgraph<G>::out_edge_iterator ei, ei_end; + for(boost::tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) { + v_global = *vi; + if (v_global == u_global) + continue; // don't insert self loops twice! + if (!g.find_vertex(v_global).second) + continue; // not a subgraph vertex => try next one + for(boost::tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) { + e_global = *ei; + if(target(e_global, r) == u_global) { + g.local_add_edge(g.global_to_local(v_global), u_local, e_global); + } + } + } + } + } + return u_local; } // NOTE: Descriptors are local unless otherwise noted. diff --git a/boost/graph/successive_shortest_path_nonnegative_weights.hpp b/boost/graph/successive_shortest_path_nonnegative_weights.hpp index 72b1512c16..6a3aeb168e 100644 --- a/boost/graph/successive_shortest_path_nonnegative_weights.hpp +++ b/boost/graph/successive_shortest_path_nonnegative_weights.hpp @@ -1,6 +1,6 @@ //======================================================================= // Copyright 2013 University of Warsaw. -// Authors: Piotr Wygocki +// Authors: Piotr Wygocki // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at @@ -11,7 +11,7 @@ // by Ahuja, Magnanti, Orlin. #ifndef BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP -#define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP +#define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP #include <numeric> @@ -19,7 +19,6 @@ #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/pending/indirect_cmp.hpp> -#include <boost/pending/relaxed_heap.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/iteration_macros.hpp> @@ -29,9 +28,9 @@ namespace boost { namespace detail { - + template <class Graph, class Weight, class Distance, class Reversed> -class MapReducedWeight : +class MapReducedWeight : public put_get_helper<typename property_traits<Weight>::value_type, MapReducedWeight<Graph, Weight, Distance, Reversed> > { typedef graph_traits<Graph> gtraits; public: @@ -39,11 +38,11 @@ public: typedef typename property_traits<Weight>::value_type value_type; typedef value_type reference; typedef typename gtraits::edge_descriptor key_type; - MapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) : + MapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) : g_(g), weight_(w), distance_(d), rev_(r) {} reference operator[](key_type v) const { - return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v); + return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v); } private: const Graph & g_; @@ -53,7 +52,7 @@ private: }; template <class Graph, class Weight, class Distance, class Reversed> -MapReducedWeight<Graph, Weight, Distance, Reversed> +MapReducedWeight<Graph, Weight, Distance, Reversed> make_mapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) { return MapReducedWeight<Graph, Weight, Distance, Reversed>(g, w, d, r); } @@ -63,21 +62,21 @@ make_mapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) { template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex> void successive_shortest_path_nonnegative_weights( - const Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + const Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, - Weight weight, + Weight weight, Reversed rev, VertexIndex index, - Pred pred, + Pred pred, Distance distance, Distance2 distance_prev) { filtered_graph<const Graph, is_residual_edge<ResidualCapacity> > gres = detail::residual_graph(g, residual_capacity); typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; - + BGL_FORALL_EDGES_T(e, g, Graph) { put(residual_capacity, e, get(capacity, e)); } @@ -90,7 +89,7 @@ void successive_shortest_path_nonnegative_weights( BGL_FORALL_VERTICES_T(v, g, Graph) { put(pred, v, edge_descriptor()); } - dijkstra_shortest_paths(gres, s, + dijkstra_shortest_paths(gres, s, weight_map(detail::make_mapReducedWeight(gres, weight, distance_prev, rev)). distance_map(distance). vertex_index_map(index). @@ -113,8 +112,8 @@ namespace detail { template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class Distance2, class VertexIndex> void successive_shortest_path_nonnegative_weights_dispatch3( - const Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + const Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, @@ -130,8 +129,8 @@ void successive_shortest_path_nonnegative_weights_dispatch3( //setting default distance map template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex> void successive_shortest_path_nonnegative_weights_dispatch3( - Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, @@ -151,8 +150,8 @@ void successive_shortest_path_nonnegative_weights_dispatch3( template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex> void successive_shortest_path_nonnegative_weights_dispatch2( - Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, @@ -168,8 +167,8 @@ void successive_shortest_path_nonnegative_weights_dispatch2( //setting default distance map template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex> void successive_shortest_path_nonnegative_weights_dispatch2( - Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, @@ -177,7 +176,7 @@ void successive_shortest_path_nonnegative_weights_dispatch2( Reversed rev, VertexIndex index, Pred pred, - param_not_found, + param_not_found, const bgl_named_params<P, T, R>& params) { typedef typename property_traits<Weight>::value_type D; @@ -190,12 +189,12 @@ void successive_shortest_path_nonnegative_weights_dispatch2( template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex> void successive_shortest_path_nonnegative_weights_dispatch1( - Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, - Weight weight, + Weight weight, Reversed rev, VertexIndex index, Pred pred, @@ -207,12 +206,12 @@ void successive_shortest_path_nonnegative_weights_dispatch1( //setting default predecessors map template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class VertexIndex> void successive_shortest_path_nonnegative_weights_dispatch1( - Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, Capacity capacity, ResidualCapacity residual_capacity, - Weight weight, + Weight weight, Reversed rev, VertexIndex index, param_not_found, @@ -220,9 +219,9 @@ void successive_shortest_path_nonnegative_weights_dispatch1( typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; std::vector<edge_descriptor> pred_vec(num_vertices(g)); - successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, + successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, make_iterator_property_map(pred_vec.begin(), index), - get_param(params, vertex_distance), params); + get_param(params, vertex_distance), params); } }//detail @@ -230,26 +229,26 @@ void successive_shortest_path_nonnegative_weights_dispatch1( template <class Graph, class P, class T, class R> void successive_shortest_path_nonnegative_weights( - Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + Graph &g, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t, const bgl_named_params<P, T, R>& params) { - - return detail::successive_shortest_path_nonnegative_weights_dispatch1(g, s, t, + + return detail::successive_shortest_path_nonnegative_weights_dispatch1(g, s, t, choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity), - choose_pmap(get_param(params, edge_residual_capacity), + choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity), choose_const_pmap(get_param(params, edge_weight), g, edge_weight), choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), choose_const_pmap(get_param(params, vertex_index), g, vertex_index), - get_param(params, vertex_predecessor), + get_param(params, vertex_predecessor), params); } template <class Graph> void successive_shortest_path_nonnegative_weights( Graph &g, - typename graph_traits<Graph>::vertex_descriptor s, + typename graph_traits<Graph>::vertex_descriptor s, typename graph_traits<Graph>::vertex_descriptor t) { bgl_named_params<int, buffer_param_t> params(0); successive_shortest_path_nonnegative_weights(g, s, t, params); @@ -258,4 +257,3 @@ void successive_shortest_path_nonnegative_weights( }//boost #endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */ - diff --git a/boost/graph/two_bit_color_map.hpp b/boost/graph/two_bit_color_map.hpp index 3d55eabc70..077b7cb342 100644 --- a/boost/graph/two_bit_color_map.hpp +++ b/boost/graph/two_bit_color_map.hpp @@ -15,6 +15,7 @@ #include <boost/property_map/property_map.hpp> #include <boost/graph/properties.hpp> +#include <boost/graph/detail/mpi_include.hpp> #include <boost/shared_array.hpp> #include <boost/config.hpp> #include <boost/assert.hpp> @@ -102,8 +103,6 @@ make_two_bit_color_map(std::size_t n, const IndexMap& index_map) } // end namespace boost -#endif // BOOST_TWO_BIT_COLOR_MAP_HPP +#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/two_bit_color_map.hpp>) -#ifdef BOOST_GRAPH_USE_MPI -# include <boost/graph/distributed/two_bit_color_map.hpp> -#endif +#endif // BOOST_TWO_BIT_COLOR_MAP_HPP diff --git a/boost/graph/vector_as_graph.hpp b/boost/graph/vector_as_graph.hpp index b771eaf7fd..1c3890224f 100644 --- a/boost/graph/vector_as_graph.hpp +++ b/boost/graph/vector_as_graph.hpp @@ -18,7 +18,7 @@ #include <utility> #include <vector> #include <cstddef> -#include <boost/iterator.hpp> +#include <iterator> #include <boost/iterator/counting_iterator.hpp> #include <boost/range/irange.hpp> #include <boost/graph/graph_traits.hpp> @@ -110,12 +110,15 @@ namespace boost { // need rewrite this using boost::iterator_adaptor template <class V, class Iter> class val_out_edge_iterator - : public boost::iterator<std::input_iterator_tag, std::pair<V,V>, - std::ptrdiff_t, std::pair<V,V>*, const std::pair<V,V> > { typedef val_out_edge_iterator self; typedef std::pair<V,V> Edge; public: + typedef std::input_iterator_tag iterator_category; + typedef std::pair<V,V> value_type; + typedef std::ptrdiff_t difference_type; + typedef std::pair<V,V>* pointer; + typedef const std::pair<V,V> reference; val_out_edge_iterator() { } val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) { } Edge operator*() const { return Edge(_source, *_iter); } diff --git a/boost/graph/wavefront.hpp b/boost/graph/wavefront.hpp index 4d9c909c70..3873ac718c 100644 --- a/boost/graph/wavefront.hpp +++ b/boost/graph/wavefront.hpp @@ -1,7 +1,8 @@ // //======================================================================= // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch) -// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st) +// ETH Zurich, Center of Structure Technologies +// (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/) // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at |