pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 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 #pragma once
28 
29 #if defined(__MINGW32__) || defined(_MSC_VER)
30 #include <winsock2.h>
31 #include <windows.h>
32 #ifdef unlink
33 #undef unlink
34 #endif
35 #endif
36 
37 #include <boost/config.hpp>
38 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/push_relabel_max_flow.hpp>
40 #include <boost/graph/edmonds_karp_max_flow.hpp>
41 #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
42 
43 #if 0
44 #include "./../../common/src/signalhandler.h"
45 #endif
46 #include "./../../common/src/pgr_types.h"
47 
48 #include <map>
49 #include <string>
50 #include <utility>
51 #include <vector>
52 #include <set>
53 
54 
55 // user's functions
56 // for development
57 
58 typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>
60 typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
61  // Vertex properties
62  boost::property<boost::vertex_name_t, std::string,
63  boost::property<boost::vertex_index_t, int64_t,
64  boost::property<boost::vertex_color_t, boost::default_color_type,
65  boost::property<boost::vertex_distance_t, int64_t,
66  boost::property<boost::vertex_predecessor_t, Traits::edge_descriptor> > > > >,
67  // Edge properties
68  boost::property<boost::edge_capacity_t, int64_t,
69  boost::property<boost::edge_residual_capacity_t, int64_t,
70  boost::property<boost::edge_reverse_t, Traits::edge_descriptor> > > >
72 
73 template<class G>
74 class PgrFlowGraph {
75  public:
77 
78  typedef typename boost::graph_traits<G>::vertex_descriptor V;
79  typedef typename boost::graph_traits<G>::edge_descriptor E;
80  typedef typename boost::graph_traits<G>::vertex_iterator V_it;
81  typedef typename boost::graph_traits<G>::edge_iterator E_it;
82 
83  typename boost::property_map<G, boost::edge_capacity_t>::type capacity;
84  typename boost::property_map<G, boost::edge_reverse_t>::type rev;
85  typename boost::property_map<G, boost::edge_residual_capacity_t>::type
87 
88 
89  std::map<int64_t, V> id_to_V;
90  std::map<V, int64_t> V_to_id;
91  std::map<E, int64_t> E_to_id;
92 
95 
96  V get_boost_vertex(int64_t id) {
97  return id_to_V[id];
98  }
99 
100  int64_t get_vertex_id(V v) {
101  return V_to_id[v];
102  }
103 
104  int64_t get_edge_id(E e) {
105  return E_to_id[e];
106  }
107 
108  int64_t push_relabel() {
109  return boost::push_relabel_max_flow(boost_graph,
111  sink_vertex);
112  }
113 
114  int64_t edmonds_karp() {
115  return boost::edmonds_karp_max_flow(boost_graph,
117  sink_vertex);
118  }
119 
120  int64_t boykov_kolmogorov() {
121  size_t num_v = boost::num_vertices(boost_graph);
122  std::vector<boost::default_color_type> color(num_v);
123  std::vector<int64_t> distance(num_v);
124  return boost::boykov_kolmogorov_max_flow(boost_graph,
126  sink_vertex);
127  }
128 
129  void create_flow_graph(pgr_edge_t *data_edges,
130  size_t total_tuples,
131  const std::set<int64_t> &source_vertices,
132  const std::set<int64_t> &sink_vertices,
133  char *algorithm) {
134  /* In multi source flow graphs, a super source is created connected to all sources with "infinite" capacity
135  * The same applies for sinks.
136  * To avoid code repetition, a supersource/sink is used even in the one to one signature.
137  */
138  std::set<int64_t> vertices;
139  for (int64_t source : source_vertices) {
140  vertices.insert(source);
141  }
142  for (int64_t sink : sink_vertices) {
143  vertices.insert(sink);
144  }
145  for (size_t i = 0; i < total_tuples; ++i) {
146  vertices.insert(data_edges[i].source);
147  vertices.insert(data_edges[i].target);
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  for (int64_t source_id : source_vertices) {
158  V source = get_boost_vertex(source_id);
159  E e, e_rev;
160  boost::tie(e, added) =
161  boost::add_edge(supersource, source, boost_graph);
162  boost::tie(e_rev, added) =
163  boost::add_edge(source, supersource, boost_graph);
164  capacity[e] = 999999999;
165  capacity[e_rev] = 0;
166  rev[e] = e_rev;
167  rev[e_rev] = e;
168  }
169 
170  V supersink = add_vertex(boost_graph);
171  for (int64_t sink_id : sink_vertices) {
172  V sink = get_boost_vertex(sink_id);
173  E e, e_rev;
174  boost::tie(e, added) = boost::add_edge(sink, supersink, boost_graph);
175  boost::tie(e_rev, added) =
176  boost::add_edge(supersink, sink, boost_graph);
177  capacity[e] = 999999999;
178  capacity[e_rev] = 0;
179  rev[e] = e_rev;
180  rev[e_rev] = e;
181  }
182 
183  source_vertex = supersource;
184  sink_vertex = supersink;
185 
186  capacity = get(boost::edge_capacity, boost_graph);
187  rev = get(boost::edge_reverse, boost_graph);
188  residual_capacity = get(boost::edge_residual_capacity, boost_graph);
189 
190  /*
191  * Push-relabel requires each edge to be mapped to its reverse with capacity 0.
192  * The other algorithms have no such requirement. (I can have half as many edges)
193  */
194  if (strcmp(algorithm, "push_relabel") == 0) {
195  for (size_t i = 0; i < total_tuples; ++i) {
196  V v1 = get_boost_vertex(data_edges[i].source);
197  V v2 = get_boost_vertex(data_edges[i].target);
198  E e1, e1_rev, e2, e2_rev;
199  if (data_edges[i].cost > 0) {
200  boost::tie(e1, added) = boost::add_edge(v1, v2, boost_graph);
201  boost::tie(e1_rev, added) =
202  boost::add_edge(v2, v1, boost_graph);
203  E_to_id.insert(std::pair<E, int64_t>(e1, data_edges[i].id));
204  E_to_id.insert(std::pair<E, int64_t>(e1_rev,
205  data_edges[i].id));
206  capacity[e1] = (int64_t) data_edges[i].cost;
207  capacity[e1_rev] = 0;
208  rev[e1] = e1_rev;
209  rev[e1_rev] = e1;
210  }
211  if (data_edges[i].reverse_cost > 0) {
212  boost::tie(e2, added) = boost::add_edge(v2, v1, boost_graph);
213  boost::tie(e2_rev, added) =
214  boost::add_edge(v1, v2, boost_graph);
215  E_to_id.insert(std::pair<E, int64_t>(e2, data_edges[i].id));
216  E_to_id.insert(std::pair<E, int64_t>(e2_rev,
217  data_edges[i].id));
218  capacity[e2] = (int64_t) data_edges[i].reverse_cost;
219  capacity[e2_rev] = 0;
220  rev[e2] = e2_rev;
221  rev[e2_rev] = e2;
222  }
223  }
224  } else {
225  for (size_t i = 0; i < total_tuples; ++i) {
226  V v1 = get_boost_vertex(data_edges[i].source);
227  V v2 = get_boost_vertex(data_edges[i].target);
228  E e, e_rev;
229  boost::tie(e, added) = boost::add_edge(v1, v2, boost_graph);
230  boost::tie(e_rev, added) =
231  boost::add_edge(v2, v1, boost_graph);
232  E_to_id.insert(std::pair<E, int64_t>(e, data_edges[i].id));
233  E_to_id.insert(std::pair<E, int64_t>(e_rev, data_edges[i].id));
234  capacity[e] =
235  data_edges[i].cost > 0 ? (int64_t) data_edges[i].cost : 0;
236  capacity[e_rev] = data_edges[i].reverse_cost > 0
237  ? (int64_t) data_edges[i].reverse_cost : 0;
238  rev[e] = e_rev;
239  rev[e_rev] = e;
240  }
241  }
242  }
243 
244  void get_flow_edges(std::vector<pgr_flow_t> &flow_edges) {
245  E_it e, e_end;
246  for (boost::tie(e, e_end) = boost::edges(boost_graph); e != e_end;
247  ++e) {
248  // A supersource/supersink is used internally
249  if (((capacity[*e] - residual_capacity[*e]) > 0) &&
250  ((*e).m_source != source_vertex) &&
251  ((*e).m_target != sink_vertex)) {
253  edge.edge = get_edge_id(*e);
254  edge.source = get_vertex_id((*e).m_source);
255  edge.target = get_vertex_id((*e).m_target);
256  edge.flow = capacity[*e] - residual_capacity[*e];
257  edge.residual_capacity = residual_capacity[*e];
258  flow_edges.push_back(edge);
259  }
260  }
261  }
262 };
boost::graph_traits< G >::vertex_descriptor V
Definition: pgr_maxflow.hpp:78
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)
boost::graph_traits< G >::edge_iterator E_it
Definition: pgr_maxflow.hpp:81
double reverse_cost
Definition: pgr_types.h:132
int64_t push_relabel()
boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS > Traits
Definition: pgr_maxflow.hpp:59
int64_t source
Definition: pgr_types.h:137
V get_boost_vertex(int64_t id)
Definition: pgr_maxflow.hpp:96
int64_t edmonds_karp()
boost::property_map< G, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:84
std::map< V, int64_t > V_to_id
Definition: pgr_maxflow.hpp:90
int64_t edge
Definition: pgr_types.h:136
double cost
Definition: pgr_types.h:131
boost::graph_traits< G >::vertex_iterator V_it
Definition: pgr_maxflow.hpp:80
boost::graph_traits< G >::edge_descriptor E
Definition: pgr_maxflow.hpp:79
edge_astar_t * edges
Definition: BDATester.cpp:46
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:71
int64_t flow
Definition: pgr_types.h:139
std::map< E, int64_t > E_to_id
Definition: pgr_maxflow.hpp:91
int64_t get_edge_id(E e)
std::map< int64_t, V > id_to_V
Definition: pgr_maxflow.hpp:89
int64_t target
Definition: pgr_types.h:138
boost::property_map< G, boost::edge_residual_capacity_t >::type residual_capacity
Definition: pgr_maxflow.hpp:86
int64_t residual_capacity
Definition: pgr_types.h:140
boost::property_map< G, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:83
int64_t get_vertex_id(V v)
void get_flow_edges(std::vector< pgr_flow_t > &flow_edges)
int64_t boykov_kolmogorov()