PGROUTING  2.5
pgr_maxflow.cpp
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 #include "pgr_maxflow.hpp"
28 
29 #include <limits>
30 #include <utility>
31 #include <vector>
32 #include <set>
33 
34 namespace pgrouting {
35 namespace graph {
36 
37 
39  const std::vector<pgr_edge_t> &edges,
40  const std::set<int64_t> &source_vertices,
41  const std::set<int64_t> &sink_vertices,
42  int algorithm) {
43  add_vertices(edges, source_vertices, sink_vertices);
44 
45  capacity = get(boost::edge_capacity, graph);
46  rev = get(boost::edge_reverse, graph);
47  residual_capacity = get(boost::edge_residual_capacity, graph);
48 
49  if (algorithm == 1) {
51  } else {
52  insert_edges(edges);
53  }
54 }
55 
57  const std::vector<pgr_edge_t> &edges,
58  const std::set<int64_t> &source_vertices,
59  const std::set<int64_t> &sink_vertices,
60  bool directed) {
61  add_vertices(edges, source_vertices, sink_vertices);
62 
63  capacity = get(boost::edge_capacity, graph);
64  rev = get(boost::edge_reverse, graph);
66  get(boost::edge_residual_capacity, graph);
67 
68  insert_edges_edge_disjoint(edges, directed);
69 }
70 
71 /* Inserting edges
72  * Push-relabel requires each edge to be mapped to its reverse with capacity 0.
73  */
75  const std::vector<pgr_edge_t> &edges) {
76  bool added;
77  for (const auto edge : edges) {
80  E e1, e1_rev, e2, e2_rev;
81  if (edge.cost > 0) {
82  boost::tie(e1, added) = boost::add_edge(v1, v2, graph);
83  boost::tie(e1_rev, added) =
84  boost::add_edge(v2, v1, graph);
85  E_to_id.insert(std::pair<E, int64_t>(e1, edge.id));
86  E_to_id.insert(std::pair<E, int64_t>(e1_rev, edge.id));
87  capacity[e1] = (int64_t) edge.cost;
88  capacity[e1_rev] = 0;
89  rev[e1] = e1_rev;
90  rev[e1_rev] = e1;
91  }
92  if (edge.reverse_cost > 0) {
93  boost::tie(e2, added) = boost::add_edge(v2, v1, graph);
94  boost::tie(e2_rev, added) =
95  boost::add_edge(v1, v2, graph);
96  E_to_id.insert(std::pair<E, int64_t>(e2, edge.id));
97  E_to_id.insert(std::pair<E, int64_t>(e2_rev, edge.id));
98  capacity[e2] = (int64_t) edge.reverse_cost;
99  capacity[e2_rev] = 0;
100  rev[e2] = e2_rev;
101  rev[e2_rev] = e2;
102  }
103  }
104 }
105 
106 /* Inserting edges
107  * The other pgr_maxflow algorithms have no such requirement. (can have have as many edges)
108  */
110  const std::vector<pgr_edge_t> &edges) {
111  bool added;
112  for (const auto edge : edges) {
115  E e, e_rev;
116  boost::tie(e, added) = boost::add_edge(v1, v2, graph);
117  boost::tie(e_rev, added) =
118  boost::add_edge(v2, v1, graph);
119  E_to_id.insert(std::pair<E, int64_t>(e, edge.id));
120  E_to_id.insert(std::pair<E, int64_t>(e_rev, edge.id));
121  capacity[e] = edge.cost > 0 ? (int64_t) edge.cost : 0;
122  capacity[e_rev] = edge.reverse_cost > 0
123  ? (int64_t) edge.reverse_cost : 0;
124  rev[e] = e_rev;
125  rev[e_rev] = e;
126  }
127 }
128 
129 /* Inserting edges
130  * for the edge_disjoint_paths algorithms
131  */
133  const std::vector<pgr_edge_t> &edges,
134  bool directed) {
135  bool added;
136  for (const auto edge : edges) {
139  E e, e_rev;
140  boost::tie(e, added) =
141  boost::add_edge(v1, v2, graph);
142  boost::tie(e_rev, added) =
143  boost::add_edge(v2, v1, graph);
144  E_to_id.insert(std::pair<E, int64_t>(e, edge.id));
145  E_to_id.insert(std::pair<E, int64_t>(e_rev,
146  edge.id));
147  if (directed) {
148  capacity[e] = edge.cost >= 0 ? 1 : 0;
149  capacity[e_rev] = edge.reverse_cost >= 0 ? 1 : 0;
150  } else {
151  if (edge.cost >= 0 || edge.reverse_cost >= 0) {
152  capacity[e] = 1;
153  capacity[e_rev] = 1;
154  }
155  }
156  rev[e] = e_rev;
157  rev[e_rev] = e;
158  }
159 }
160 
162  const std::set<int64_t> &source_vertices) {
163  bool added;
164  supersource = add_vertex(graph);
165  for (int64_t source_id : source_vertices) {
166  V source = get_boost_vertex(source_id);
167  E e, e_rev;
168  boost::tie(e, added) =
169  boost::add_edge(supersource, source, graph);
170  boost::tie(e_rev, added) =
171  boost::add_edge(source, supersource, graph);
172 
173  capacity[e] = (std::numeric_limits<int32_t>::max)();
174  /* From sources to supersource has 0 capacity*/
175  capacity[e_rev] = 0;
176  rev[e] = e_rev;
177  rev[e_rev] = e;
178  }
179 }
180 
182  const std::set<int64_t> &sink_vertices) {
183  bool added;
184  supersink = add_vertex(graph);
185  for (int64_t sink_id : sink_vertices) {
186  V sink = get_boost_vertex(sink_id);
187  E e, e_rev;
188  boost::tie(e, added) = boost::add_edge(sink, supersink, graph);
189  boost::tie(e_rev, added) =
190  boost::add_edge(supersink, sink, graph);
191  /*
192  * NOTE: int64_t crashes the server
193  */
194  /* From sinks to supersink has maximum capacity*/
195  capacity[e] = (std::numeric_limits<int32_t>::max)();
196  /* From supersink to sinks has 0 capacity*/
197  capacity[e_rev] = 0;
198  rev[e] = e_rev;
199  rev[e_rev] = e;
200  }
201 }
202 
203 std::vector<pgr_flow_t>
205  std::vector<pgr_flow_t> flow_edges;
206  E_it e, e_end;
207  for (boost::tie(e, e_end) = boost::edges(graph); e != e_end;
208  ++e) {
209  // A supersource/supersink is used internally
210  if (((capacity[*e] - residual_capacity[*e]) > 0) &&
211  ((*e).m_source != supersource) &&
212  ((*e).m_target != supersink)) {
214  edge.edge = get_edge_id(*e);
215  edge.source = get_vertex_id((*e).m_source);
216  edge.target = get_vertex_id((*e).m_target);
217  edge.flow = capacity[*e] - residual_capacity[*e];
218  edge.residual_capacity = residual_capacity[*e];
219  flow_edges.push_back(edge);
220  }
221  }
222  return flow_edges;
223 }
224 
225 
226 
227 void
229  int64_t path_id,
230  std::vector<std::vector<int64_t> > &paths) {
231  Eout_it ei, e_end;
232  if (boost::edge(vertex, supersink, graph).second) {
233  int64_t v_id = get_vertex_id(vertex);
234  paths[path_id].push_back(v_id);
235  } else {
236  for (boost::tie(ei, e_end) =
237  boost::out_edges(vertex, graph);
238  ei != e_end; ++ei) {
239  if (residual_capacity[*ei] < capacity[*ei]) {
240  // exclude this edge from subsequent visits
241  capacity[*ei] = -1;
242  int64_t v_id = get_vertex_id(vertex);
243  paths[path_id].push_back(v_id);
244  flow_dfs((*ei).m_target,
245  path_id,
246  paths);
247  break;
248  }
249  }
250  }
251 }
252 
253 std::vector<General_path_element_t>
255  int64_t flow) {
256  std::vector<General_path_element_t> path_elements;
257 
258  std::vector<std::vector<int64_t> > paths(flow, std::vector<int64_t>());
259  int64_t path_id = 0;
260  Eout_it ei, e_end, ei2, e2_end;
261  for (boost::tie(ei, e_end) =
262  boost::out_edges(supersource, graph);
263  ei != e_end; ++ei) {
264  if (capacity[*ei] - residual_capacity[*ei] > 0) {
265  for (boost::tie(ei2, e2_end) =
266  boost::out_edges((*ei).m_target, graph);
267  ei2 != e2_end; ++ei2) {
268  if (capacity[*ei2] - residual_capacity[*ei2]
269  > 0) {
270  paths[path_id].push_back(get_vertex_id((*ei2).m_source));
271  flow_dfs((*ei2).m_target, path_id, paths);
272  path_id++;
273  }
274  }
275  }
276  }
277  for (int i = 0; i < flow; i++) {
278  size_t size = paths[i].size();
279  E e;
280  bool exists;
281  size_t j;
282  for (j = 0; j < size - 1; j++) {
284  edge.seq = static_cast<int>(j + 1);
285  edge.start_id = paths[i][0];
286  edge.end_id = paths[i][size - 1];
287  edge.node = paths[i][j];
288  boost::tie(e, exists) = boost::edge(get_boost_vertex(paths[i][j]),
289  get_boost_vertex(paths[i][j
290  + 1]),
291  graph);
292  edge.edge = get_edge_id(e);
293  path_elements.push_back(edge);
294  }
296  edge.seq = static_cast<int>(j + 1);
297  edge.start_id = paths[i][0];
298  edge.end_id = paths[i][size - 1];
299  edge.node = paths[i][j];
300  edge.edge = -1;
301  path_elements.push_back(edge);
302  }
303  return path_elements;
304 }
305 
306 
307 
308 } // namespace graph
309 } // namespace pgrouting
310 
static edge_t edges[22573]
float8 cost
Definition: trsp.h:35
void insert_edges_push_relabel(const std::vector< pgr_edge_t > &edges)
Definition: pgr_maxflow.cpp:74
Definition: trsp.h:31
int64_t source
Definition: pgr_flow_t.h:64
void add_vertices(const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
long id
Definition: trsp.h:32
void flow_dfs(V vertex, int64_t path_id, std::vector< std::vector< int64_t > > &paths)
boost::property_map< FlowGraph, boost::edge_residual_capacity_t >::type residual_capacity
Definition: pgr_maxflow.hpp:68
int64_t edge
Definition: pgr_flow_t.h:63
std::map< E, int64_t > E_to_id
boost::graph_traits< FlowGraph >::out_edge_iterator Eout_it
Definition: pgr_maxflow.hpp:60
boost::graph_traits< FlowGraph >::edge_iterator E_it
Definition: pgr_maxflow.hpp:59
void set_supersource(const std::set< int64_t > &source_vertices)
int64_t flow
Definition: pgr_flow_t.h:66
int64_t get_vertex_id(V v) const
int64_t target
Definition: pgr_flow_t.h:65
std::vector< pgr_flow_t > get_flow_edges() const
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
std::vector< General_path_element_t > get_edge_disjoint_paths(int64_t flow)
V get_boost_vertex(int64_t id) const
PgrFlowGraph(const std::vector< pgr_edge_t > &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, int algorithm)
Definition: pgr_maxflow.cpp:38
int64_t residual_capacity
Definition: pgr_flow_t.h:67
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
void set_supersink(const std::set< int64_t > &sink_vertices)
long target
Definition: trsp.h:34
void insert_edges(const std::vector< pgr_edge_t > &edges)
boost::graph_traits< FlowGraph >::edge_descriptor E
Definition: pgr_maxflow.hpp:57
boost::property_map< FlowGraph, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:64
boost::graph_traits< FlowGraph >::vertex_descriptor V
Definition: pgr_maxflow.hpp:56
void insert_edges_edge_disjoint(const std::vector< pgr_edge_t > &edges, bool directed)
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33
int64_t get_edge_id(E e) const