PGROUTING  2.6
pgrouting::graph::PgrFlowGraph Class Reference

#include "pgr_maxflow.hpp"

Collaboration diagram for pgrouting::graph::PgrFlowGraph:

Public Member Functions

 PgrFlowGraph (const std::vector< pgr_edge_t > &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, int algorithm)
 
 PgrFlowGraph (const std::vector< pgr_edge_t > &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices, bool directed)
 
int64_t boykov_kolmogorov ()
 
std::vector< General_path_element_tedge_disjoint_paths ()
 
int64_t edmonds_karp ()
 
std::vector< General_path_element_tget_edge_disjoint_paths (int64_t flow)
 
std::vector< pgr_flow_tget_flow_edges () const
 
int64_t push_relabel ()
 

Private Types

typedef boost::graph_traits< FlowGraph >::edge_descriptor E
 
typedef boost::graph_traits< FlowGraph >::edge_iterator E_it
 
typedef boost::graph_traits< FlowGraph >::out_edge_iterator Eout_it
 
typedef boost::graph_traits< FlowGraph >::vertex_descriptor V
 
typedef boost::graph_traits< FlowGraph >::vertex_iterator V_it
 

Private Member Functions

template<typename T >
void add_vertices (const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
 
void flow_dfs (V vertex, int64_t path_id, std::vector< std::vector< int64_t > > &paths)
 
V get_boost_vertex (int64_t id) const
 
int64_t get_edge_id (E e) const
 
int64_t get_vertex_id (V v) const
 
void insert_edges (const std::vector< pgr_edge_t > &edges)
 
void insert_edges_edge_disjoint (const std::vector< pgr_edge_t > &edges, bool directed)
 
void insert_edges_push_relabel (const std::vector< pgr_edge_t > &edges)
 
void set_supersink (const std::set< int64_t > &sink_vertices)
 
void set_supersource (const std::set< int64_t > &source_vertices)
 

Private Attributes

boost::property_map< FlowGraph, boost::edge_capacity_t >::type capacity
 
std::map< E, int64_t > E_to_id
 
FlowGraph graph
 
std::map< int64_t, Vid_to_V
 
boost::property_map< FlowGraph, boost::edge_residual_capacity_t >::type residual_capacity
 
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
 
V supersink
 
V supersource
 
std::map< V, int64_t > V_to_id
 

Detailed Description

Definition at line 55 of file pgr_maxflow.hpp.

Member Typedef Documentation

typedef boost::graph_traits<FlowGraph>::edge_descriptor pgrouting::graph::PgrFlowGraph::E
private

Definition at line 57 of file pgr_maxflow.hpp.

typedef boost::graph_traits<FlowGraph>::edge_iterator pgrouting::graph::PgrFlowGraph::E_it
private

Definition at line 59 of file pgr_maxflow.hpp.

typedef boost::graph_traits<FlowGraph>::out_edge_iterator pgrouting::graph::PgrFlowGraph::Eout_it
private

Definition at line 60 of file pgr_maxflow.hpp.

typedef boost::graph_traits<FlowGraph>::vertex_descriptor pgrouting::graph::PgrFlowGraph::V
private

Definition at line 56 of file pgr_maxflow.hpp.

typedef boost::graph_traits<FlowGraph>::vertex_iterator pgrouting::graph::PgrFlowGraph::V_it
private

Definition at line 58 of file pgr_maxflow.hpp.

Constructor & Destructor Documentation

pgrouting::graph::PgrFlowGraph::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 at line 38 of file pgr_maxflow.cpp.

References add_vertices(), capacity, graph, insert_edges(), insert_edges_push_relabel(), residual_capacity, and rev.

Referenced by edge_disjoint_paths().

42  {
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 }
void insert_edges_push_relabel(const std::vector< pgr_edge_t > &edges)
Definition: pgr_maxflow.cpp:74
void add_vertices(const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
boost::property_map< FlowGraph, boost::edge_residual_capacity_t >::type residual_capacity
Definition: pgr_maxflow.hpp:68
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
void insert_edges(const std::vector< pgr_edge_t > &edges)
boost::property_map< FlowGraph, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:64

Here is the call graph for this function:

Here is the caller graph for this function:

pgrouting::graph::PgrFlowGraph::PgrFlowGraph ( const std::vector< pgr_edge_t > &  edges,
const std::set< int64_t > &  source_vertices,
const std::set< int64_t > &  sink_vertices,
bool  directed 
)

Definition at line 56 of file pgr_maxflow.cpp.

References add_vertices(), capacity, graph, insert_edges_edge_disjoint(), residual_capacity, and rev.

60  {
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 }
void add_vertices(const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
boost::property_map< FlowGraph, boost::edge_residual_capacity_t >::type residual_capacity
Definition: pgr_maxflow.hpp:68
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
boost::property_map< FlowGraph, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:64
void insert_edges_edge_disjoint(const std::vector< pgr_edge_t > &edges, bool directed)

Here is the call graph for this function:

Member Function Documentation

template<typename T >
void pgrouting::graph::PgrFlowGraph::add_vertices ( const T &  edges,
const std::set< int64_t > &  source_vertices,
const std::set< int64_t > &  sink_vertices 
)
inlineprivate

Definition at line 159 of file pgr_maxflow.hpp.

References graph, id_to_V, set_supersink(), set_supersource(), and V_to_id.

Referenced by PgrFlowGraph().

162  {
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  }
std::map< int64_t, V > id_to_V
void set_supersource(const std::set< int64_t > &source_vertices)
void set_supersink(const std::set< int64_t > &sink_vertices)
std::map< V, int64_t > V_to_id
boost::graph_traits< FlowGraph >::vertex_descriptor V
Definition: pgr_maxflow.hpp:56

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::graph::PgrFlowGraph::boykov_kolmogorov ( )
inline

Definition at line 86 of file pgr_maxflow.hpp.

References graph, supersink, and supersource.

Referenced by do_pgr_max_flow().

86  {
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  }

Here is the caller graph for this function:

std::vector<General_path_element_t> pgrouting::graph::PgrFlowGraph::edge_disjoint_paths ( )
inline

Definition at line 95 of file pgr_maxflow.hpp.

References get_edge_disjoint_paths(), get_flow_edges(), graph, PgrFlowGraph(), supersink, and supersource.

Referenced by single_execution().

95  {
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  }
std::vector< General_path_element_t > get_edge_disjoint_paths(int64_t flow)

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::graph::PgrFlowGraph::edmonds_karp ( )
inline

Definition at line 79 of file pgr_maxflow.hpp.

References graph, supersink, and supersource.

Referenced by do_pgr_max_flow().

79  {
80  return boost::edmonds_karp_max_flow(
81  graph,
83  supersink);
84  }

Here is the caller graph for this function:

void pgrouting::graph::PgrFlowGraph::flow_dfs ( V  vertex,
int64_t  path_id,
std::vector< std::vector< int64_t > > &  paths 
)
private

Definition at line 228 of file pgr_maxflow.cpp.

References capacity, get_vertex_id(), graph, residual_capacity, and supersink.

Referenced by get_edge_disjoint_paths(), and get_edge_id().

230  {
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 }
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
boost::graph_traits< FlowGraph >::out_edge_iterator Eout_it
Definition: pgr_maxflow.hpp:60
int64_t get_vertex_id(V v) const
boost::property_map< FlowGraph, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:64

Here is the call graph for this function:

Here is the caller graph for this function:

V pgrouting::graph::PgrFlowGraph::get_boost_vertex ( int64_t  id) const
inlineprivate

Definition at line 125 of file pgr_maxflow.hpp.

References id_to_V.

Referenced by get_edge_disjoint_paths(), insert_edges(), insert_edges_edge_disjoint(), insert_edges_push_relabel(), set_supersink(), and set_supersource().

125  {
126  return id_to_V.at(id);
127  }
std::map< int64_t, V > id_to_V

Here is the caller graph for this function:

std::vector< General_path_element_t > pgrouting::graph::PgrFlowGraph::get_edge_disjoint_paths ( int64_t  flow)

Definition at line 254 of file pgr_maxflow.cpp.

References capacity, General_path_element_t::edge, General_path_element_t::end_id, flow_dfs(), get_boost_vertex(), get_edge_id(), get_vertex_id(), graph, General_path_element_t::node, residual_capacity, General_path_element_t::seq, General_path_element_t::start_id, and supersource.

Referenced by edge_disjoint_paths().

255  {
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 }
Definition: trsp.h:31
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
boost::graph_traits< FlowGraph >::out_edge_iterator Eout_it
Definition: pgr_maxflow.hpp:60
int64_t get_vertex_id(V v) const
V get_boost_vertex(int64_t id) const
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
int64_t get_edge_id(E e) const

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::graph::PgrFlowGraph::get_edge_id ( E  e) const
inlineprivate

Definition at line 133 of file pgr_maxflow.hpp.

References E_to_id, flow_dfs(), insert_edges(), insert_edges_edge_disjoint(), insert_edges_push_relabel(), set_supersink(), and set_supersource().

Referenced by get_edge_disjoint_paths(), and get_flow_edges().

133  {
134  return E_to_id.at(e);
135  }
std::map< E, int64_t > E_to_id

Here is the call graph for this function:

Here is the caller graph for this function:

std::vector< pgr_flow_t > pgrouting::graph::PgrFlowGraph::get_flow_edges ( ) const

Definition at line 204 of file pgr_maxflow.cpp.

References capacity, pgr_flow_t::edge, pgr_flow_t::flow, get_edge_id(), get_vertex_id(), graph, pgr_flow_t::residual_capacity, residual_capacity, pgr_flow_t::source, supersink, supersource, and pgr_flow_t::target.

Referenced by do_pgr_max_flow(), and edge_disjoint_paths().

204  {
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 }
Definition: trsp.h:31
int64_t source
Definition: pgr_flow_t.h:60
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:59
boost::graph_traits< FlowGraph >::edge_iterator E_it
Definition: pgr_maxflow.hpp:59
int64_t flow
Definition: pgr_flow_t.h:62
int64_t get_vertex_id(V v) const
int64_t target
Definition: pgr_flow_t.h:61
int64_t residual_capacity
Definition: pgr_flow_t.h:63
boost::property_map< FlowGraph, boost::edge_capacity_t >::type capacity
Definition: pgr_maxflow.hpp:64
int64_t get_edge_id(E e) const

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::graph::PgrFlowGraph::get_vertex_id ( V  v) const
inlineprivate

Definition at line 129 of file pgr_maxflow.hpp.

References V_to_id.

Referenced by flow_dfs(), get_edge_disjoint_paths(), and get_flow_edges().

129  {
130  return V_to_id.at(v);
131  }
std::map< V, int64_t > V_to_id

Here is the caller graph for this function:

void pgrouting::graph::PgrFlowGraph::insert_edges ( const std::vector< pgr_edge_t > &  edges)
private

Definition at line 109 of file pgr_maxflow.cpp.

References capacity, edge::cost, E_to_id, get_boost_vertex(), graph, edge::id, rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by get_edge_id(), and PgrFlowGraph().

110  {
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 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
long id
Definition: trsp.h:32
std::map< E, int64_t > E_to_id
V get_boost_vertex(int64_t id) const
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
long target
Definition: trsp.h:34
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
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::graph::PgrFlowGraph::insert_edges_edge_disjoint ( const std::vector< pgr_edge_t > &  edges,
bool  directed 
)
private

Definition at line 132 of file pgr_maxflow.cpp.

References capacity, edge::cost, E_to_id, get_boost_vertex(), graph, edge::id, rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by get_edge_id(), and PgrFlowGraph().

134  {
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 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
long id
Definition: trsp.h:32
std::map< E, int64_t > E_to_id
V get_boost_vertex(int64_t id) const
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
long target
Definition: trsp.h:34
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
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::graph::PgrFlowGraph::insert_edges_push_relabel ( const std::vector< pgr_edge_t > &  edges)
private

Definition at line 74 of file pgr_maxflow.cpp.

References capacity, edge::cost, E_to_id, get_boost_vertex(), graph, edge::id, rev, edge::reverse_cost, edge::source, and edge::target.

Referenced by get_edge_id(), and PgrFlowGraph().

75  {
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 }
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
long id
Definition: trsp.h:32
std::map< E, int64_t > E_to_id
V get_boost_vertex(int64_t id) const
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
long target
Definition: trsp.h:34
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
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::graph::PgrFlowGraph::push_relabel ( )
inline

Definition at line 72 of file pgr_maxflow.hpp.

References graph, supersink, and supersource.

Referenced by do_pgr_max_flow().

72  {
73  return boost::push_relabel_max_flow(
74  graph,
76  supersink);
77  }

Here is the caller graph for this function:

void pgrouting::graph::PgrFlowGraph::set_supersink ( const std::set< int64_t > &  sink_vertices)
private

Definition at line 181 of file pgr_maxflow.cpp.

References capacity, get_boost_vertex(), graph, rev, and supersink.

Referenced by add_vertices(), and get_edge_id().

182  {
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 }
V get_boost_vertex(int64_t id) const
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
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

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::graph::PgrFlowGraph::set_supersource ( const std::set< int64_t > &  source_vertices)
private

Definition at line 161 of file pgr_maxflow.cpp.

References capacity, get_boost_vertex(), graph, rev, and supersource.

Referenced by add_vertices(), and get_edge_id().

162  {
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 }
V get_boost_vertex(int64_t id) const
boost::property_map< FlowGraph, boost::edge_reverse_t >::type rev
Definition: pgr_maxflow.hpp:66
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

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

boost::property_map<FlowGraph, boost::edge_capacity_t>::type pgrouting::graph::PgrFlowGraph::capacity
private
std::map<E, int64_t> pgrouting::graph::PgrFlowGraph::E_to_id
private
std::map<int64_t, V> pgrouting::graph::PgrFlowGraph::id_to_V
private

Definition at line 183 of file pgr_maxflow.hpp.

Referenced by add_vertices(), and get_boost_vertex().

boost::property_map<FlowGraph, boost::edge_residual_capacity_t>::type pgrouting::graph::PgrFlowGraph::residual_capacity
private

Definition at line 68 of file pgr_maxflow.hpp.

Referenced by flow_dfs(), get_edge_disjoint_paths(), get_flow_edges(), and PgrFlowGraph().

boost::property_map<FlowGraph, boost::edge_reverse_t>::type pgrouting::graph::PgrFlowGraph::rev
private
V pgrouting::graph::PgrFlowGraph::supersink
private
V pgrouting::graph::PgrFlowGraph::supersource
private
std::map<V, int64_t> pgrouting::graph::PgrFlowGraph::V_to_id
private

Definition at line 184 of file pgr_maxflow.hpp.

Referenced by add_vertices(), and get_vertex_id().


The documentation for this class was generated from the following files: