PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_maxflow.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 Copyright (c) 2016 Andrea Nardelli
7 Mail: nrd.nardelli@gmail.com
8 
9 ------
10 
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15 
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20 
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 
25 ********************************************************************PGR-GNU*/
26 
27 #ifndef SRC_MAX_FLOW_SRC_PGR_MAXFLOW_HPP_
28 #define SRC_MAX_FLOW_SRC_PGR_MAXFLOW_HPP_
29 #pragma once
30 
31 #ifdef unlink
32 #undef unlink
33 #endif
34 
35 #include <boost/config.hpp>
36 #include <boost/graph/adjacency_list.hpp>
37 #include <boost/graph/push_relabel_max_flow.hpp>
38 #include <boost/graph/edmonds_karp_max_flow.hpp>
39 #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
40 
41 
42 #include <map>
43 #include <string>
44 #include <utility>
45 #include <vector>
46 #include <set>
47 #include <limits>
48 
49 #include "./../../common/src/pgr_types.h"
50 
51 
52 namespace pgrouting {
53 
54 typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>
56 typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
57  // Vertex properties
58  boost::property<boost::vertex_name_t, std::string,
59  boost::property<boost::vertex_index_t, int64_t,
60  boost::property<boost::vertex_color_t, boost::default_color_type,
61  boost::property<boost::vertex_distance_t, int64_t,
62  boost::property<boost::vertex_predecessor_t, Traits::edge_descriptor>
63  > > > >,
64  // Edge properties
65  boost::property<boost::edge_capacity_t, int64_t,
66  boost::property<boost::edge_residual_capacity_t, int64_t,
67  boost::property<boost::edge_reverse_t, Traits::edge_descriptor> > > >
69 
70 namespace graph {
71 
72 template<class G>
73 class PgrFlowGraph {
74  public:
76 
77  typedef typename boost::graph_traits<G>::vertex_descriptor V;
78  typedef typename boost::graph_traits<G>::edge_descriptor E;
79  typedef typename boost::graph_traits<G>::vertex_iterator V_it;
80  typedef typename boost::graph_traits<G>::edge_iterator E_it;
81 
82  typename boost::property_map<G, boost::edge_capacity_t>::type capacity;
83  typename boost::property_map<G, boost::edge_reverse_t>::type rev;
84  typename boost::property_map<G, boost::edge_residual_capacity_t>::type
86 
87 
88  std::map<int64_t, V> id_to_V;
89  std::map<V, int64_t> V_to_id;
90  std::map<E, int64_t> E_to_id;
91 
94 
95  V get_boost_vertex(int64_t id) {
96  return id_to_V[id];
97  }
98 
99  int64_t get_vertex_id(V v) {
100  return V_to_id[v];
101  }
102 
103  int64_t get_edge_id(E e) {
104  return E_to_id[e];
105  }
106 
107  int64_t push_relabel() {
108  return boost::push_relabel_max_flow(boost_graph,
110  sink_vertex);
111  }
112 
113  int64_t edmonds_karp() {
114  return boost::edmonds_karp_max_flow(boost_graph,
116  sink_vertex);
117  }
118 
119  int64_t boykov_kolmogorov() {
120  size_t num_v = boost::num_vertices(boost_graph);
121  std::vector<boost::default_color_type> color(num_v);
122  std::vector<int64_t> distance(num_v);
123  return boost::boykov_kolmogorov_max_flow(boost_graph,
125  sink_vertex);
126  }
127 
128  void create_flow_graph(pgr_edge_t *data_edges,
129  size_t total_tuples,
130  const std::set<int64_t> &source_vertices,
131  const std::set<int64_t> &sink_vertices,
132  char *algorithm) {
133  /* In multi source flow graphs, a super source is created connected to all sources with "infinite" capacity
134  * The same applies for sinks.
135  * To avoid code repetition, a supersource/sink is used even in the one to one signature.
136  */
137 
138  /*
139  * vertices = {sources} U {sink} U {edges.source} U {edge.target}
140  */
141  std::set<int64_t> vertices(source_vertices);
142  vertices.insert(sink_vertices.begin(), sink_vertices.end());
143 
144  for (size_t i = 0; i < total_tuples; ++i) {
145  vertices.insert(data_edges[i].source);
146  vertices.insert(data_edges[i].target);
147  }
148 
149  for (int64_t id : vertices) {
150  V v = add_vertex(boost_graph);
151  id_to_V.insert(std::pair<int64_t, V>(id, v));
152  V_to_id.insert(std::pair<V, int64_t>(v, id));
153  }
154  bool added;
155 
156  V supersource = add_vertex(boost_graph);
157  V supersink = add_vertex(boost_graph);
158 
159  source_vertex = supersource;
160  sink_vertex = supersink;
161 
162  capacity = get(boost::edge_capacity, boost_graph);
163  rev = get(boost::edge_reverse, boost_graph);
164  residual_capacity = get(boost::edge_residual_capacity, boost_graph);
165 
166  /* Inserting edges
167  * Push-relabel requires each edge to be mapped to its reverse with capacity 0.
168  * The other algorithms have no such requirement. (can have have as many edges)
169  */
170  if (strcmp(algorithm, "push_relabel") == 0) {
171  for (size_t i = 0; i < total_tuples; ++i) {
172  V v1 = get_boost_vertex(data_edges[i].source);
173  V v2 = get_boost_vertex(data_edges[i].target);
174  E e1, e1_rev, e2, e2_rev;
175  if (data_edges[i].cost > 0) {
176  boost::tie(e1, added) = boost::add_edge(v1, v2, boost_graph);
177  boost::tie(e1_rev, added) =
178  boost::add_edge(v2, v1, boost_graph);
179  E_to_id.insert(std::pair<E, int64_t>(e1, data_edges[i].id));
180  E_to_id.insert(std::pair<E, int64_t>(e1_rev,
181  data_edges[i].id));
182  capacity[e1] = (int64_t) data_edges[i].cost;
183  capacity[e1_rev] = 0;
184  rev[e1] = e1_rev;
185  rev[e1_rev] = e1;
186  }
187  if (data_edges[i].reverse_cost > 0) {
188  boost::tie(e2, added) = boost::add_edge(v2, v1, boost_graph);
189  boost::tie(e2_rev, added) =
190  boost::add_edge(v1, v2, boost_graph);
191  E_to_id.insert(std::pair<E, int64_t>(e2, data_edges[i].id));
192  E_to_id.insert(std::pair<E, int64_t>(e2_rev,
193  data_edges[i].id));
194  capacity[e2] = (int64_t) data_edges[i].reverse_cost;
195  capacity[e2_rev] = 0;
196  rev[e2] = e2_rev;
197  rev[e2_rev] = e2;
198  }
199  }
200  } else {
201  for (size_t i = 0; i < total_tuples; ++i) {
202  V v1 = get_boost_vertex(data_edges[i].source);
203  V v2 = get_boost_vertex(data_edges[i].target);
204  E e, e_rev;
205  boost::tie(e, added) = boost::add_edge(v1, v2, boost_graph);
206  boost::tie(e_rev, added) =
207  boost::add_edge(v2, v1, boost_graph);
208  E_to_id.insert(std::pair<E, int64_t>(e, data_edges[i].id));
209  E_to_id.insert(std::pair<E, int64_t>(e_rev, data_edges[i].id));
210  capacity[e] =
211  data_edges[i].cost > 0 ? (int64_t) data_edges[i].cost : 0;
212  capacity[e_rev] = data_edges[i].reverse_cost > 0
213  ? (int64_t) data_edges[i].reverse_cost : 0;
214  rev[e] = e_rev;
215  rev[e_rev] = e;
216  }
217  }
218  for (int64_t source_id : source_vertices) {
219  V source = get_boost_vertex(source_id);
220  int64_t total = 0;
221  for (auto edge = out_edges(source, boost_graph).first;
222  edge != out_edges(source, boost_graph).second;
223  ++edge) {
224  total += capacity[*edge];
225  }
226  E e, e_rev;
227  boost::tie(e, added) =
228  boost::add_edge(supersource, source, boost_graph);
229  boost::tie(e_rev, added) =
230  boost::add_edge(source, supersource, boost_graph);
231 
232  capacity[e] = total;
233  /* From sources to supersource has 0 capacity*/
234  capacity[e_rev] = 0;
235  rev[e] = e_rev;
236  rev[e_rev] = e;
237  }
238  for (int64_t sink_id : sink_vertices) {
239  V sink = get_boost_vertex(sink_id);
240  E e, e_rev;
241  boost::tie(e, added) = boost::add_edge(sink, supersink, boost_graph);
242  boost::tie(e_rev, added) =
243  boost::add_edge(supersink, sink, boost_graph);
244  /*
245  * NOTE: int64_t crashes the server
246  */
247  /* From sinks to supersink has maximum capacity*/
248  capacity[e] = (std::numeric_limits<int32_t>::max)();
249  /* From supersink to sinks has 0 capacity*/
250  capacity[e_rev] = 0;
251  rev[e] = e_rev;
252  rev[e_rev] = e;
253  }
254 
255  }
256 
257  void get_flow_edges(std::vector<pgr_flow_t> &flow_edges) {
258  E_it e, e_end;
259  for (boost::tie(e, e_end) = boost::edges(boost_graph); e != e_end;
260  ++e) {
261  // A supersource/supersink is used internally
262  if (((capacity[*e] - residual_capacity[*e]) > 0) &&
263  ((*e).m_source != source_vertex) &&
264  ((*e).m_target != sink_vertex)) {
266  edge.edge = get_edge_id(*e);
267  edge.source = get_vertex_id((*e).m_source);
268  edge.target = get_vertex_id((*e).m_target);
269  edge.flow = capacity[*e] - residual_capacity[*e];
270  edge.residual_capacity = residual_capacity[*e];
271  flow_edges.push_back(edge);
272  }
273  }
274  }
275 };
276 
277 } // namespace graph
278 } // namespace pgrouting
279 
280 #endif // SRC_MAX_FLOW_SRC_PGR_MAXFLOW_HPP_
boost::property_map< G, boost::edge_residual_capacity_t >::type residual_capacity
Definition: pgr_maxflow.hpp:85
double reverse_cost
Definition: pgr_types.h:146
void create_flow_graph(pgr_edge_t *data_edges, size_t total_tuples, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, char *algorithm)
std::map< int64_t, V > id_to_V
Definition: pgr_maxflow.hpp:88
std::map< E, int64_t > E_to_id
Definition: pgr_maxflow.hpp:90
std::map< V, int64_t > V_to_id
Definition: pgr_maxflow.hpp:89
int64_t source
Definition: pgr_types.h:151
boost::graph_traits< G >::vertex_descriptor V
Definition: pgr_maxflow.hpp:77
boost::graph_traits< G >::edge_iterator E_it
Definition: pgr_maxflow.hpp:80
boost::graph_traits< G >::vertex_iterator V_it
Definition: pgr_maxflow.hpp:79
void get_flow_edges(std::vector< pgr_flow_t > &flow_edges)
int64_t edge
Definition: pgr_types.h:150
double cost
Definition: pgr_types.h:145
edge_astar_t * edges
Definition: BDATester.cpp:46
boost::property_map< G, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:83
boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS > Traits
Definition: pgr_maxflow.hpp:55
int64_t flow
Definition: pgr_types.h:153
boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, boost::property< boost::vertex_name_t, std::string, boost::property< boost::vertex_index_t, int64_t, boost::property< boost::vertex_color_t, boost::default_color_type, boost::property< boost::vertex_distance_t, int64_t, boost::property< boost::vertex_predecessor_t, Traits::edge_descriptor > > > > >, boost::property< boost::edge_capacity_t, int64_t, boost::property< boost::edge_residual_capacity_t, int64_t, boost::property< boost::edge_reverse_t, Traits::edge_descriptor > > > > FlowGraph
Definition: pgr_maxflow.hpp:68
int64_t target
Definition: pgr_types.h:152
int64_t residual_capacity
Definition: pgr_types.h:154
boost::property_map< G, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:82
boost::graph_traits< G >::edge_descriptor E
Definition: pgr_maxflow.hpp:78