589584b4e4
* trac 11374: find_flow_cost() not working with bundled properties. When using bundled for Weight and Cost properties, find_flow_cost() coudln't work because the properties had been "hard coded" instead of using generic types. Fixes https://svn.boost.org/trac/boost/ticket/11374 * trac 12038: max-flow algorithms not working with named parameters. The named parameter "Capacity" was not working. I just had to reverse the order of get_param_type parameters. Here are the max-flow algorithms that are curretly not working with the named parameter "Capacity": - edmonds_karp_max_flow, - push_relabel_max_flow, - boykov_kolmogorov_max_flow. Fixes https://svn.boost.org/trac/boost/ticket/12038 * trac 11374: find_flow_cost() not working with named parameters and bundled properties at the same time. When using bundled properties as well as named parameters, there was an error. What happened is that the "named parameters" version of find_flow_cost() was not using a generic return value, hence the error. Also, the return value_type was using edge_capacity_value instead of edge_weight_value (which is the type of a flow cost). I fixed it using the trick used for edmonds_karp_max_flow(): add `edge_weight_value` to named_function_params.hpp. * Unit test find_flow_cost() with bundled properties & named params. -> unit tests for trac 11374 I used the existing min_cost_max_flow_utils.hpp, but I had to make the graph of getSampleGraph() more generic. In the first place, I wanted to make a compile-only test but I also made the test runnable so we check that - find_flow_cost works() correctly with bundled properties - successive_shortest_path_nonnegative_weights() also works with bundled properties To run this test, this is a bit painful... I had to run the entire graph-related tests. - I commented the other tests except for graph in ./status/Jamfile.v2 - in this same dir, I ran `../b2` One issue though: csr_graph_test seems to be broken on my boost copy, I may have an issue with updating the submodules or something... * Unit test edmond_karp_max_flow with named params & bundled properties. -> unit tests for trac 12038 As the previous commit, I rely on min_cost_max_flow_utils.hpp. And I also made a runnable test instead of a simple "compile-time" test. * Indented with 2 spaces instead of tabs Thanks for the patch!
53 lines
1.8 KiB
C++
53 lines
1.8 KiB
C++
//=======================================================================
|
|
// Copyright 2013 University of Warsaw.
|
|
// Authors: Piotr Wygocki
|
|
//
|
|
// 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_FIND_FLOW_COST_HPP
|
|
#define BOOST_GRAPH_FIND_FLOW_COST_HPP
|
|
|
|
#include <boost/graph/iteration_macros.hpp>
|
|
|
|
namespace boost {
|
|
|
|
template<class Graph, class Capacity, class ResidualCapacity, class Weight>
|
|
typename property_traits<Weight>::value_type
|
|
find_flow_cost(const Graph & g, Capacity capacity, ResidualCapacity residual_capacity, Weight weight) {
|
|
typedef typename property_traits<Weight>::value_type Cost;
|
|
|
|
Cost cost = 0;
|
|
BGL_FORALL_EDGES_T(e, g, Graph) {
|
|
if(get(capacity, e) > Cost(0)) {
|
|
cost += (get(capacity, e) - get(residual_capacity, e)) * get(weight, e);
|
|
}
|
|
}
|
|
return cost;
|
|
}
|
|
|
|
template <class Graph, class P, class T, class R>
|
|
typename detail::edge_weight_value<Graph, P, T, R>::type
|
|
find_flow_cost(const Graph & g,
|
|
const bgl_named_params<P, T, R>& params) {
|
|
return find_flow_cost(g,
|
|
choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
|
|
choose_const_pmap(get_param(params, edge_residual_capacity),
|
|
g, edge_residual_capacity),
|
|
choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
|
|
}
|
|
|
|
template <class Graph>
|
|
typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
|
|
find_flow_cost(const Graph &g) {
|
|
bgl_named_params<int, buffer_param_t> params(0);
|
|
return find_flow_cost(g, params);
|
|
}
|
|
|
|
|
|
} //boost
|
|
|
|
#endif /* BOOST_GRAPH_FIND_FLOW_COST_HPP */
|
|
|