PGROUTING  2.5
 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 
32 #include "pgr_flowgraph.hpp"
33 #include <boost/graph/push_relabel_max_flow.hpp>
34 #include <boost/graph/edmonds_karp_max_flow.hpp>
35 #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
36 
37 
38 #include <map>
39 #include <string>
40 #include <utility>
41 #include <vector>
42 #include <set>
43 #include <limits>
44 
45 #include "c_types/pgr_flow_t.h"
46 #include "c_types/pgr_edge_t.h"
48 
49 
50 
51 namespace pgrouting {
52 namespace graph {
53 
54 
55 class PgrFlowGraph {
56  typedef boost::graph_traits<FlowGraph>::vertex_descriptor V;
57  typedef boost::graph_traits<FlowGraph>::edge_descriptor E;
58  typedef boost::graph_traits<FlowGraph>::vertex_iterator V_it;
59  typedef boost::graph_traits<FlowGraph>::edge_iterator E_it;
60  typedef boost::graph_traits<FlowGraph>::out_edge_iterator Eout_it;
61 
62 
63  boost::property_map
64  <FlowGraph, boost::edge_capacity_t>::type capacity;
65  boost::property_map
66  <FlowGraph, boost::edge_reverse_t>::type rev;
67  boost::property_map
68  <FlowGraph, boost::edge_residual_capacity_t>::type residual_capacity;
69 
70 
71  public:
72  int64_t push_relabel() {
73  return boost::push_relabel_max_flow(
74  graph,
76  supersink);
77  }
78 
79  int64_t edmonds_karp() {
80  return boost::edmonds_karp_max_flow(
81  graph,
83  supersink);
84  }
85 
86  int64_t boykov_kolmogorov() {
87  size_t num_v = boost::num_vertices(graph);
88  std::vector<boost::default_color_type> color(num_v);
89  std::vector<int64_t> distance(num_v);
90  return boost::boykov_kolmogorov_max_flow(
91  graph,
93  supersink);
94  }
95  std::vector<General_path_element_t> edge_disjoint_paths() {
96  size_t num_v = boost::num_vertices(graph);
97  std::vector<boost::default_color_type> color(num_v);
98  std::vector<int64_t> distance(num_v);
99  auto flow = boost::boykov_kolmogorov_max_flow(
100  graph,
101  supersource,
102  supersink);
103  return get_edge_disjoint_paths(flow);
104  }
105 
106  PgrFlowGraph(
107  const std::vector<pgr_edge_t> &edges,
108  const std::set<int64_t> &source_vertices,
109  const std::set<int64_t> &sink_vertices,
110  int algorithm);
111 
112  PgrFlowGraph(
113  const std::vector<pgr_edge_t> &edges,
114  const std::set<int64_t> &source_vertices,
115  const std::set<int64_t> &sink_vertices,
116  bool directed);
117 
118 
119  std::vector<pgr_flow_t> get_flow_edges() const;
120 
121  std::vector<General_path_element_t> get_edge_disjoint_paths(
122  int64_t flow);
123 
124  private:
125  V get_boost_vertex(int64_t id) const {
126  return id_to_V.at(id);
127  }
128 
129  int64_t get_vertex_id(V v) const {
130  return V_to_id.at(v);
131  }
132 
133  int64_t get_edge_id(E e) const {
134  return E_to_id.at(e);
135  }
136 
137  void set_supersource(
138  const std::set<int64_t> &source_vertices);
139  void set_supersink(
140  const std::set<int64_t> &sink_vertices);
141 
143  const std::vector<pgr_edge_t> &edges);
144  void insert_edges(
145  const std::vector<pgr_edge_t> &edges);
147  const std::vector<pgr_edge_t> &edges,
148  bool directed);
149 
150  void flow_dfs(
151  V vertex,
152  int64_t path_id,
153  std::vector<std::vector<int64_t> > &paths);
154 
155  /*
156  * vertices = {sources} U {sink} U {edges.source} U {edge.target}
157  */
158  template <typename T>
160  const T &edges,
161  const std::set<int64_t> &source_vertices,
162  const std::set<int64_t> &sink_vertices) {
163  std::set<int64_t> vertices(source_vertices);
164  vertices.insert(sink_vertices.begin(), sink_vertices.end());
165 
166  for (const auto e : edges) {
167  vertices.insert(e.source);
168  vertices.insert(e.target);
169  }
170 
171  for (const auto id : vertices) {
172  V v = add_vertex(graph);
173  id_to_V.insert(std::pair<int64_t, V>(id, v));
174  V_to_id.insert(std::pair<V, int64_t>(v, id));
175  }
176 
177  set_supersource(source_vertices);
178  set_supersink(sink_vertices);
179  }
180 
181  private:
183  std::map<int64_t, V> id_to_V;
184  std::map<V, int64_t> V_to_id;
185  std::map<E, int64_t> E_to_id;
186 
187 
188  /* In multi source flow graphs, a super source is created connected to all sources with "infinite" capacity
189  * The same applies for sinks.
190  * To avoid code repetition, a supersource/sink is used even in the one to one signature.
191  */
194 };
195 
196 } // namespace graph
197 } // namespace pgrouting
198 
199 #endif // SRC_MAX_FLOW_SRC_PGR_MAXFLOW_HPP_
static edge_t edges[22573]
std::vector< General_path_element_t > edge_disjoint_paths()
Definition: pgr_maxflow.hpp:95
void insert_edges_push_relabel(const std::vector< pgr_edge_t > &edges)
Definition: pgr_maxflow.cpp:74
std::map< int64_t, V > id_to_V
void add_vertices(const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
boost::graph_traits< FlowGraph >::vertex_iterator V_it
Definition: pgr_maxflow.hpp:58
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
std::map< E, int64_t > E_to_id
boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, 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
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 get_vertex_id(V v) const
std::vector< pgr_flow_t > get_flow_edges() const
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
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)
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
std::map< V, int64_t > V_to_id
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)
int64_t get_edge_id(E e) const