find_flow_cost() not working with bundled or user-defined properties

[Maël Valais <mael.valais@…>]

I tripped over that bug when trying to use find_flow_cost(). Using the source below, it won't compile. The error log is here : ​http://pastebin.com/Gd3JdbuK

I think this is a problem in boost/graph/find_flow_cost.hpp:18. For example, line 19:

typedef typename property_traits<typename property_map<Graph, edge_weight_t>::const_type>::value_type Cost;

should rather be

typedef typename property_traits<Weight>::value_type Cost;

The same problem occurs line on 17 and 19.

The minimum working example:

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/find_flow_cost.hpp>

using namespace boost;

typedef adjacency_list_traits<vecS,vecS,directedS> traits;
struct edge_t {
	double capacity;
	float cost;
	float residual_capacity;
	traits::edge_descriptor reversed_edge;
};
struct node_t {
	std::string name;
	boost::default_color_type color;
	traits::edge_descriptor predecessor;
};

typedef adjacency_list < listS, vecS, directedS, node_t, edge_t > Graph;


int main()
{

	Graph g;
	property_map < Graph, double edge_t::* >::type capacity = get(&edge_t::capacity, g);
	property_map < Graph, float edge_t::* >::type cost = get(&edge_t::cost, g);
	property_map < Graph, float edge_t::* >::type residual_capacity = get(&edge_t::residual_capacity, g);
	property_map < Graph, traits::edge_descriptor edge_t::* >::type rev = get(&edge_t::reversed_edge, g);

	property_map < Graph, std::string node_t::* >::type name = get(&node_t::name, g);
	property_map < Graph, boost::default_color_type node_t::* >::type col = get(&node_t::color, g);
	property_map < Graph, traits::edge_descriptor node_t::* >::type pred = get(&node_t::predecessor, g);



	traits::vertex_descriptor s, t;

	read_dimacs_max_flow(g, capacity, rev, s, t);

	long flow, flow_cost;
	// XXX The "non-named parameter version" (works fine)
	flow = edmonds_karp_max_flow(g, s, t,capacity,residual_capacity,rev,col,pred);
	// XXX The "named parameter version" (producing errors)
//	flow = edmonds_karp_max_flow(g, s, t,
//			capacity_map(capacity)
//			.residual_capacity_map(residual_capacity)
//			.reverse_edge_map(rev)
//			.color_map(col)
//			.predecessor_map(pred));


	find_flow_cost(g,capacity,residual_capacity,cost);
	//flow_cost = find_flow_cost(g,capacity,residual_capacity,cost);


	std::cout << "c  The total flow:" << std::endl;
	std::cout << "s " << flow << std::endl << std::endl;

	std::cout << "c flow values:" << std::endl;
	graph_traits < Graph >::vertex_iterator u_iter, u_end;
	graph_traits < Graph >::out_edge_iterator ei, e_end;
	for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
		for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
			if (capacity[*ei] > 0)
				std::cout << "a " << *u_iter << " " << target(*ei, g) << " "
				<< (capacity[*ei] - residual_capacity[*ei]) << std::endl;

	return EXIT_SUCCESS;
}

[Maël Valais <mael.valais@…>]

PR added: ​https://github.com/boostorg/graph/pull/59

[Maël Valais <mael.valais@…>]

Also a closely related bug:

I wanted to use find_flow_cost() with the named parameter feature (as well as my bundled properties). Here is a small example that should work but doesn't:

#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/find_flow_cost.hpp>

using namespace boost;
typedef adjacency_list_traits<vecS,vecS,directedS> traits;
struct edge_t {
        double capacity;
        float cost;
        float residual_capacity;
        traits::edge_descriptor reversed_edge;
};
struct node_t {
        std::string name;
        boost::default_color_type color;
        traits::edge_descriptor predecessor;
};
typedef adjacency_list < listS, vecS, directedS, node_t, edge_t > Graph;

int main()
{
        Graph g;
        property_map < Graph, double edge_t::* >::type capacity = get(&edge_t::capacity, g);
        property_map < Graph, float edge_t::* >::type cost = get(&edge_t::cost, g);
        property_map < Graph, float edge_t::* >::type residual_capacity = get(&edge_t::residual_capacity, g);
        property_map < Graph, traits::edge_descriptor edge_t::* >::type rev = get(&edge_t::reversed_edge, g);
        property_map < Graph, std::string node_t::* >::type name = get(&node_t::name, g);
        property_map < Graph, boost::default_color_type node_t::* >::type col = get(&node_t::color, g);
        property_map < Graph, traits::edge_descriptor node_t::* >::type pred = get(&node_t::predecessor, g);
        traits::vertex_descriptor s, t;
        read_dimacs_max_flow(g, capacity, rev, s, t);

        // XXX The "bundled properties" & "named parameters" version (producing errors)
        find_flow_cost(g,
                        capacity_map(capacity)
                        .residual_capacity_map(residual_capacity)
                        .weight_map(cost));
        
        return EXIT_SUCCESS;
}

[Maël Valais <mael.valais@…>]

I re-submitted the patch in ​https://github.com/boostorg/graph/pull/61. It has been accepted yesterday, we may close that issue!