fork download

copy

#include <iostream> //std::cin,cout,ios_base
#include <vector> //std::vector
#include <tuple> //std::tie
#include <limits.h> //INT_MAX (no `std::')
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
 
#include <boost/graph/push_relabel_max_flow.hpp>
 
using namespace boost;
 
struct VertexProperties{
 
};
 
struct EdgeProperties{
	int id;
	int capacity;
	int residual_capacity;
};
 
typedef boost::adjacency_list<vecS,vecS,directedS,VertexProperties,EdgeProperties> Graph;
typedef boost::graph_traits<Graph> Traits;
typedef Traits::vertex_descriptor Vertex;
typedef Traits::edge_descriptor Edge;
 
void do_add_edge(int& next_id, const Vertex& a, const Vertex& b, const int c, Graph& g,std::map<Edge,Edge>& reverse_edge_of);
 
int main(int arc, char* argv[]){
	std::ios_base::sync_with_stdio(false);
 
	int n = 3; //nof vertices ( >2)
 
	Graph g(n);
 
	Vertex s = vertex(n-2,g); //source
	Vertex t = vertex(n-1,g); //sink
 
	Vertex u = vertex(0,g);
 
	std::map<Edge,Edge> reverse_edge_map;
	int next_id = 0;
 
	do_add_edge(next_id,s,u,3,g,reverse_edge_map);
	do_add_edge(next_id,u,t,1,g,reverse_edge_map);
 
	std::vector<int> rescap(num_edges(g));
 
	//this doesn't work
	int maxflow = push_relabel_max_flow(
		g,
		s,
		t,
		capacity_map(get(&EdgeProperties::capacity,g))
		.residual_capacity_map(get(&EdgeProperties::residual_capacity,g))
		.reverse_edge_map(make_assoc_property_map(reverse_edge_map))
		.vertex_index_map(get(vertex_index,g))
	);
	/* this would work
	int maxflow = push_relabel_max_flow(
		g,
		s,
		t,
		get(&EdgeProperties::capacity,g),
		get(&EdgeProperties::residual_capacity,g),
		make_assoc_property_map(reverse_edge_map),
		get(vertex_index,g)
	);
	*/
 
	std::cout << "maxflow = " << maxflow << "\n";
 
	return 0;
}
 
void do_add_edge(int& next_id, const Vertex& a, const Vertex& b, const int c, Graph& g,std::map<Edge,Edge>& reverse_edge_of){
	Edge e,re; bool success;
 
	std::tie(e,success) = add_edge(a,b,g);
	g[e].id = next_id;
	g[e].capacity = c;
	g[e].residual_capacity = c;
 
	//reverse edge
	std::tie(re,success) = add_edge(b,a,g);
	g[re].id = next_id + 1;
	g[re].capacity = 0;
	g[re].residual_capacity = 0;
 
	reverse_edge_of[e] = re;
	reverse_edge_of[re] = e;
 
	next_id += 2;
}

In file included from /usr/include/boost/graph/adjacency_list.hpp:246:0,
                 from prog.cpp:6:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of 'struct boost::detail::adj_list_any_edge_pmap::bind_<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, EdgeProperties, boost::edge_capacity_t>':
/usr/include/boost/graph/detail/adjacency_list.hpp:2683:12:   required from 'struct boost::detail::adj_list_choose_edge_pmap<boost::edge_capacity_t, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, EdgeProperties>'
/usr/include/boost/graph/detail/adjacency_list.hpp:2688:14:   required from 'struct boost::detail::adj_list_edge_property_selector::bind_<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, EdgeProperties, boost::edge_capacity_t>'
/usr/include/boost/graph/properties.hpp:208:12:   required from 'struct boost::detail::edge_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::edge_capacity_t>'
/usr/include/boost/graph/properties.hpp:228:10:   required from 'struct boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::edge_capacity_t, void>'
/usr/include/boost/mpl/eval_if.hpp:38:31:   recursively required from 'struct boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::edge_capacity_t, void> >, boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::edge_capacity_t, void> >'
/usr/include/boost/mpl/eval_if.hpp:38:31:   required from 'struct boost::mpl::eval_if<boost::is_same<boost::param_not_found, boost::param_not_found>, boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::edge_capacity_t, void> >, boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::edge_capacity_t, void> >, boost::mpl::identity<boost::param_not_found> >'
/usr/include/boost/graph/named_function_params.hpp:269:12:   required from 'struct boost::detail::choose_impl_result<mpl_::bool_<true>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::param_not_found, boost::edge_capacity_t>'
/usr/include/boost/graph/named_function_params.hpp:326:156:   required from 'struct boost::detail::edge_capacity_value<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>, boost::vec_adj_list_vertex_id_map<VertexProperties, unsigned int>, boost::vertex_index_t, boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int> > >, boost::edge_reverse_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::directed_tag, int, int&, unsigned int, EdgeProperties, int EdgeProperties::*>, boost::edge_residual_capacity_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::directed_tag, int, int&, unsigned int, EdgeProperties, int EdgeProperties::*>, boost::edge_capacity_t, boost::no_property> > > >'
/usr/include/boost/graph/push_relabel_max_flow.hpp:714:3:   required by substitution of 'template<class Graph, class P, class T, class R> typename boost::detail::edge_capacity_value<Graph, P, T, R>::type boost::push_relabel_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [with Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties>; P = boost::vec_adj_list_vertex_id_map<VertexProperties, unsigned int>; T = boost::vertex_index_t; R = boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int> > >, boost::edge_reverse_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::directed_tag, int, int&, unsigned int, EdgeProperties, int EdgeProperties::*>, boost::edge_residual_capacity_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::directed_tag, int, int&, unsigned int, EdgeProperties, int EdgeProperties::*>, boost::edge_capacity_t, boost::no_property> > >]'
prog.cpp:59:2:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2651:29: error: forming reference to void
         typedef value_type& reference;
                             ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2652:35: error: forming reference to void
         typedef const value_type& const_reference;
                                   ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2656:61: error: forming reference to void
             typename Graph::vertex_descriptor,Property,Tag> type;
                                                             ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2659:68: error: forming reference to void
             typename Graph::vertex_descriptor,const Property, Tag> const_type;
                                                                    ^
prog.cpp: In function 'int main(int, char**)':
prog.cpp:59:2: error: no matching function for call to 'push_relabel_max_flow(Graph&, Vertex&, Vertex&, boost::bgl_named_params<boost::vec_adj_list_vertex_id_map<VertexProperties, unsigned int>, boost::vertex_index_t, boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int> > >, boost::edge_reverse_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::directed_tag, int, int&, unsigned int, EdgeProperties, int EdgeProperties::*>, boost::edge_residual_capacity_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::directed_tag, int, int&, unsigned int, EdgeProperties, int EdgeProperties::*>, boost::edge_capacity_t, boost::no_property> > > >)'
  );
  ^
In file included from prog.cpp:9:0:
/usr/include/boost/graph/push_relabel_max_flow.hpp:689:3: note: candidate: template<class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class VertexIndexMap> typename boost::property_traits<IndexMap>::value_type boost::push_relabel_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap)
   push_relabel_max_flow
   ^
/usr/include/boost/graph/push_relabel_max_flow.hpp:689:3: note:   template argument deduction/substitution failed:
prog.cpp:59:2: note:   candidate expects 7 arguments, 4 provided
  );
  ^
In file included from prog.cpp:9:0:
/usr/include/boost/graph/push_relabel_max_flow.hpp:714:3: note: candidate: template<class Graph, class P, class T, class R> typename boost::detail::edge_capacity_value<Graph, P, T, R>::type boost::push_relabel_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&)
   push_relabel_max_flow
   ^
/usr/include/boost/graph/push_relabel_max_flow.hpp:714:3: note:   substitution of deduced template arguments resulted in errors seen above
/usr/include/boost/graph/push_relabel_max_flow.hpp:734:3: note: candidate: template<class Graph> typename boost::property_traits<typename boost::property_map<Graph, boost::edge_capacity_t>::const_type>::value_type boost::push_relabel_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor)
   push_relabel_max_flow
   ^
/usr/include/boost/graph/push_relabel_max_flow.hpp:734:3: note:   template argument deduction/substitution failed:
prog.cpp:59:2: note:   candidate expects 3 arguments, 4 provided
  );
  ^

Standard output is empty