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