fork download
copy 
  1. #include <iostream> //std::cin,cout,ios_base
  2. #include <vector> //std::vector
  3. #include <tuple> //std::tie
  4. #include <limits.h> //INT_MAX (no `std::')
  5.  
  6. #include <boost/graph/adjacency_list.hpp>
  7. #include <boost/graph/graph_traits.hpp>
  8.  
  9. #include <boost/graph/push_relabel_max_flow.hpp>
  10.  
  11. using namespace boost;
  12.  
  13. struct VertexProperties{
  14.  
  15. };
  16.  
  17. struct EdgeProperties{
  18. 	int id;
  19. 	int capacity;
  20. 	int residual_capacity;
  21. };
  22.  
  23. typedef boost::adjacency_list<vecS,vecS,directedS,VertexProperties,EdgeProperties> Graph;
  24. typedef boost::graph_traits<Graph> Traits;
  25. typedef Traits::vertex_descriptor Vertex;
  26. typedef Traits::edge_descriptor Edge;
  27.  
  28. 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);
  29.  
  30. int main(int arc, char* argv[]){
  31. 	std::ios_base::sync_with_stdio(false);
  32.  
  33. 	int n = 3; //nof vertices ( >2)
  34.  
  35. 	Graph g(n);
  36.  
  37. 	Vertex s = vertex(n-2,g); //source
  38. 	Vertex t = vertex(n-1,g); //sink
  39.  
  40. 	Vertex u = vertex(0,g);
  41.  
  42. 	std::map<Edge,Edge> reverse_edge_map;
  43. 	int next_id = 0;
  44.  
  45. 	do_add_edge(next_id,s,u,3,g,reverse_edge_map);
  46. 	do_add_edge(next_id,u,t,1,g,reverse_edge_map);
  47.  
  48. 	std::vector<int> rescap(num_edges(g));
  49.  
  50. 	//why doesn't this work?
  51. 	/*int maxflow = push_relabel_max_flow(
  52. 		g,
  53. 		s,
  54. 		t,
  55. 		capacity_map(get(&EdgeProperties::capacity,g))
  56. 		.residual_capacity_map(get(&EdgeProperties::residual_capacity,g))
  57. 		.reverse_edge_map(make_assoc_property_map(reverse_edge_map))
  58. 		.vertex_index_map(get(vertex_index,g))
  59. 	);*/
  60.  
  61. 	//this does work
  62. 	int maxflow = push_relabel_max_flow(
  63. 		g,
  64. 		s,
  65. 		t,
  66. 		get(&EdgeProperties::capacity,g),
  67. 		get(&EdgeProperties::residual_capacity,g),
  68. 		make_assoc_property_map(reverse_edge_map),
  69. 		get(vertex_index,g)
  70. 	);
  71.  
  72. 	std::cout << "maxflow = " << maxflow << "\n";
  73.  
  74. 	return 0;
  75. }
  76.  
  77. 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){
  78. 	Edge e,re; bool success;
  79.  
  80. 	std::tie(e,success) = add_edge(a,b,g);
  81. 	g[e].id = next_id;
  82. 	g[e].capacity = c;
  83. 	g[e].residual_capacity = c;
  84.  
  85. 	//reverse edge
  86. 	std::tie(re,success) = add_edge(b,a,g);
  87. 	g[re].id = next_id + 1;
  88. 	g[re].capacity = 0;
  89. 	g[re].residual_capacity = 0;
  90.  
  91. 	reverse_edge_of[e] = re;
  92. 	reverse_edge_of[re] = e;
  93.  
  94. 	next_id += 2;
  95. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
maxflow = 1
https://ideone.com/U3O0p8
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!