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_edgedisjointpaths.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/assert.hpp>
40 
41 #if 0
42 #include "./../../common/src/signalhandler.h"
43 #endif
44 #include "./../../common/src/pgr_types.h"
45 
46 #include <map>
47 #include <utility>
48 #include <vector>
49 #include <set>
50 
51 #include "pgr_maxflow.hpp"
52 
53 // user's functions
54 // for development
55 
56 template<class G>
58  public:
60 
61  typedef typename boost::graph_traits<G>::vertex_descriptor V;
62  typedef typename boost::graph_traits<G>::edge_descriptor E;
63  typedef typename boost::graph_traits<G>::vertex_iterator V_it;
64  typedef typename boost::graph_traits<G>::edge_iterator E_it;
65  typedef typename boost::graph_traits<G>::out_edge_iterator Eout_it;
66 
67  typename boost::property_map<G, boost::edge_capacity_t>::type capacity;
68  typename boost::property_map<G, boost::edge_reverse_t>::type rev;
69  typename boost::property_map<G, boost::edge_residual_capacity_t>::type
71 
72  std::map<int64_t, V> id_to_V;
73  std::map<V, int64_t> V_to_id;
74  std::map<E, int64_t> E_to_id;
75 
78 
79  V get_boost_vertex(int64_t id) {
80  return id_to_V[id];
81  }
82 
83  int64_t get_vertex_id(V v) {
84  return V_to_id[v];
85  }
86 
87  int64_t get_edge_id(E e) {
88  return E_to_id[e];
89  }
90 
91  int64_t boykov_kolmogorov() {
92  size_t num_v = boost::num_vertices(boost_graph);
93  std::vector<boost::default_color_type> color(num_v);
94  std::vector<int64_t> distance(num_v);
95  return boost::boykov_kolmogorov_max_flow(boost_graph,
97  sink_vertex);
98  }
99 
101  size_t total_tuples,
102  const std::set<int64_t> &source_vertices,
103  const std::set<int64_t> &sink_vertices,
104  bool directed) {
105  std::set<int64_t> vertices;
106  for (int64_t source : source_vertices) {
107  vertices.insert(source);
108  }
109  for (int64_t sink : sink_vertices) {
110  vertices.insert(sink);
111  }
112  for (size_t i = 0; i < total_tuples; ++i) {
113  vertices.insert(data_edges[i].source);
114  vertices.insert(data_edges[i].target);
115  }
116  for (int64_t id : vertices) {
117  V v = add_vertex(boost_graph);
118  id_to_V.insert(std::pair<int64_t, V>(id, v));
119  V_to_id.insert(std::pair<V, int64_t>(v, id));
120  }
121  bool added;
122 
123  V supersource = add_vertex(boost_graph);
124  for (int64_t source_id : source_vertices) {
125  V source = get_boost_vertex(source_id);
126  E e, e_rev;
127  boost::tie(e, added) =
128  boost::add_edge(supersource, source, boost_graph);
129  boost::tie(e_rev, added) =
130  boost::add_edge(source, supersource, boost_graph);
131  capacity[e] = 999999999;
132  capacity[e_rev] = 0;
133  rev[e] = e_rev;
134  rev[e_rev] = e;
135  }
136 
137  V supersink = add_vertex(boost_graph);
138  for (int64_t sink_id : sink_vertices) {
139  V sink = get_boost_vertex(sink_id);
140  E e1, e1_rev;
141  boost::tie(e1, added) =
142  boost::add_edge(sink, supersink, boost_graph);
143  boost::tie(e1_rev, added) =
144  boost::add_edge(supersink, sink, boost_graph);
145  capacity[e1] = 999999999;
146  capacity[e1_rev] = 0;
147  rev[e1] = e1_rev;
148  rev[e1_rev] = e1;
149  }
150 
151  source_vertex = supersource;
152  sink_vertex = supersink;
153 
154  capacity = get(boost::edge_capacity, boost_graph);
155  rev = get(boost::edge_reverse, boost_graph);
157  get(boost::edge_residual_capacity, boost_graph);
158 
159  for (size_t i = 0; i < total_tuples; ++i) {
160  V v1 = get_boost_vertex(data_edges[i].source);
161  V v2 = get_boost_vertex(data_edges[i].target);
162  if (directed) {
163  E e, e_rev;
164  boost::tie(e, added) =
165  boost::add_edge(v1, v2, boost_graph);
166  boost::tie(e_rev, added) =
167  boost::add_edge(v2, v1, boost_graph);
168  E_to_id.insert(std::pair<E, int64_t>(e, data_edges[i].id));
169  E_to_id.insert(std::pair<E, int64_t>(e_rev,
170  data_edges[i].id));
171  capacity[e] = data_edges[i].going ? 1 : 0;
172  capacity[e_rev] = data_edges[i].coming ? 1 : 0;
173  rev[e] = e_rev;
174  rev[e_rev] = e;
175  } else {
176  if (data_edges[i].going || data_edges[i].coming) {
177  E e, e_rev;
178  boost::tie(e, added) =
179  boost::add_edge(v1, v2, boost_graph);
180  boost::tie(e_rev, added) =
181  boost::add_edge(v2, v1, boost_graph);
182  E_to_id.insert(std::pair<E, int64_t>(e, data_edges[i].id));
183  E_to_id.insert(std::pair<E, int64_t>(e_rev,
184  data_edges[i].id));
185  capacity[e] = 1;
186  capacity[e_rev] = 1;
187  rev[e] = e_rev;
188  rev[e_rev] = e;
189  }
190  }
191  }
192  }
193 
194  void
196  int64_t path_id,
197  std::vector<std::vector<int64_t> > &paths) {
198  Eout_it ei, e_end;
199  if (boost::edge(vertex, sink_vertex, boost_graph).second) {
200  int64_t v_id = get_vertex_id(vertex);
201  paths[path_id].push_back(v_id);
202  } else {
203  for (boost::tie(ei, e_end) =
204  boost::out_edges(vertex, boost_graph);
205  ei != e_end; ++ei) {
206  if (residual_capacity[*ei] < capacity[*ei]) {
207  // exclude this edge from subsequent visits
208  capacity[*ei] = -1;
209  int64_t v_id = get_vertex_id(vertex);
210  paths[path_id].push_back(v_id);
211  flow_dfs((*ei).m_target,
212  path_id,
213  paths);
214  break;
215  }
216  }
217  }
218  }
219 
220  void
221  get_edge_disjoint_paths(std::vector<General_path_element_t> &path_elements,
222  int64_t flow) {
223  std::vector<std::vector<int64_t> > paths(flow, std::vector<int64_t>());
224  int64_t path_id = 0;
225  Eout_it ei, e_end, ei2, e2_end;
226  for (boost::tie(ei, e_end) =
227  boost::out_edges(source_vertex, boost_graph);
228  ei != e_end; ++ei) {
229  if (capacity[*ei] - residual_capacity[*ei] > 0) {
230  for (boost::tie(ei2, e2_end) =
231  boost::out_edges((*ei).m_target, boost_graph);
232  ei2 != e2_end; ++ei2) {
233  if (capacity[*ei2] - residual_capacity[*ei2]
234  > 0) {
235  paths[path_id].push_back(get_vertex_id((*ei2).m_source));
236  flow_dfs((*ei2).m_target, path_id, paths);
237  path_id++;
238  }
239  }
240  }
241  }
242  for (int i = 0; i < flow; i++) {
243  size_t size = paths[i].size();
244  E e;
245  bool exists;
246  size_t j;
247  for (j = 0; j < size - 1; j++) {
249  edge.seq = (int) (j + 1);
250  edge.start_id = paths[i][0];
251  edge.end_id = paths[i][size - 1];
252  edge.node = paths[i][j];
253  boost::tie(e, exists) = boost::edge(get_boost_vertex(paths[i][j]),
254  get_boost_vertex(paths[i][j
255  + 1]),
256  boost_graph);
257  edge.edge = get_edge_id(e);
258  path_elements.push_back(edge);
259  }
261  edge.seq = (int) (j + 1);
262  edge.start_id = paths[i][0];
263  edge.end_id = paths[i][size - 1];
264  edge.node = paths[i][j];
265  edge.edge = -1;
266  path_elements.push_back(edge);
267  }
268  }
269 };
boost::property_map< G, boost::edge_reverse_t >::type rev
boost::graph_traits< G >::edge_descriptor E
boost::graph_traits< G >::vertex_descriptor V
std::map< int64_t, V > id_to_V
void create_edge_disjoint_paths_graph(pgr_basic_edge_t *data_edges, size_t total_tuples, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, bool directed)
std::map< V, int64_t > V_to_id
boost::graph_traits< G >::out_edge_iterator Eout_it
boost::property_map< G, boost::edge_capacity_t >::type capacity
boost::graph_traits< G >::vertex_iterator V_it
void get_edge_disjoint_paths(std::vector< General_path_element_t > &path_elements, int64_t flow)
void flow_dfs(V vertex, int64_t path_id, std::vector< std::vector< int64_t > > &paths)
std::map< E, int64_t > E_to_id
boost::property_map< G, boost::edge_residual_capacity_t >::type residual_capacity
boost::graph_traits< G >::edge_iterator E_it