PGROUTING  3.2
pgr_minCostMaxFlow.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
5 
6 Copyright (c) 2018 Maoguang Wang
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 
28 
29 #include <set>
30 #include <vector>
31 #include <utility>
32 #include <limits>
33 
34 namespace pgrouting {
35 namespace graph {
36 
38  const std::vector<pgr_costFlow_t> &edges,
39  const std::set<int64_t> &sourceVertices,
40  const std::set<int64_t> &sinkVertices) {
41  AddVertices(edges, sourceVertices, sinkVertices);
42 
43  capacity = get(boost::edge_capacity, graph);
44  weight = get(boost::edge_weight, graph);
45  rev = get(boost::edge_reverse, graph);
46  residual_capacity = get(boost::edge_residual_capacity, graph);
47 
48  InsertEdges(edges);
49 }
50 
53  PgrCostFlowGraph::V w, double wei, double cap) {
54  bool b;
56  boost::tie(e, b) = boost::add_edge(vertex(v, graph),
57  vertex(w, graph), graph);
58  capacity[e] = cap;
59  weight[e] = wei;
60  return e;
61 }
62 
64  const std::vector<pgr_costFlow_t> &edges) {
65  for (const auto edge : edges) {
66  PgrCostFlowGraph::E e1, e1Rev, e2, e2Rev;
69 
70  if (edge.capacity > 0) {
71  e1 = AddEdge(v1, v2, edge.cost,
72  static_cast<double>(edge.capacity));
73  e1Rev = AddEdge(v2, v1, -edge.cost, 0);
74 
75  eToId.insert(std::pair<PgrCostFlowGraph::E,
76  int64_t>(e1, edge.edge_id));
77  eToId.insert(std::pair<PgrCostFlowGraph::E,
78  int64_t>(e1Rev, edge.edge_id));
79 
80  rev[e1] = e1Rev;
81  rev[e1Rev] = e1;
82  }
83 
84  if (edge.reverse_capacity > 0) {
85  e2 = AddEdge(v2, v1, edge.reverse_cost,
86  static_cast<double>(edge.reverse_capacity));
87  e2Rev = AddEdge(v1, v2, -edge.reverse_cost, 0);
88 
89  eToId.insert(std::pair<PgrCostFlowGraph::E,
90  int64_t>(e2, edge.edge_id));
91  eToId.insert(std::pair<PgrCostFlowGraph::E,
92  int64_t>(e2Rev, edge.edge_id));
93 
94  rev[e2] = e2Rev;
95  rev[e2Rev] = e2;
96  }
97  }
98 }
99 
101  const std::set<int64_t> &sourceVertices) {
102  supersource = add_vertex(graph);
103  for (int64_t source_id : sourceVertices) {
104  PgrCostFlowGraph::V source = GetBoostVertex(source_id);
105  PgrCostFlowGraph::E e, eRev;
106  e = AddEdge(supersource, source,
107  0, (std::numeric_limits<int32_t>::max)());
108  eRev = AddEdge(source, supersource, 0, 0);
109  rev[e] = eRev;
110  rev[eRev] = e;
111  }
112 }
113 
115  const std::set<int64_t> &sinkVertices) {
116  supersink = add_vertex(graph);
117  for (int64_t sink_id : sinkVertices) {
118  PgrCostFlowGraph::V sink = GetBoostVertex(sink_id);
119  PgrCostFlowGraph::E e, eRev;
120  e = AddEdge(sink, supersink, 0, (std::numeric_limits<int32_t>::max)());
121  eRev = AddEdge(supersink, sink, 0, 0);
122  rev[e] = eRev;
123  rev[eRev] = e;
124  }
125 }
126 
127 int64_t
129  int64_t maxFlow = 0;
130  E_it e, eEnd;
131  for (boost::tie(e, eEnd) = boost::edges(graph); e != eEnd; ++e) {
132  if (((capacity[*e] - residual_capacity[*e]) > 0) &&
133  ((*e).m_source == supersource))
134  maxFlow +=
135  static_cast<int64_t>(capacity[*e] - residual_capacity[*e]);
136  }
137  return maxFlow;
138 }
139 
140 std::vector<pgr_flow_t>
142  std::vector<pgr_flow_t> flowEdges;
143  E_it e, eEnd;
144  for (boost::tie(e, eEnd) = boost::edges(graph); e != eEnd; ++e) {
145  if (((capacity[*e] - residual_capacity[*e]) > 0) &&
146  ((*e).m_source != supersource) &&
147  ((*e).m_target != supersink)) {
149  edge.edge = GetEdgeId(*e);
150  edge.source = GetVertexId((*e).m_source);
151  edge.target = GetVertexId((*e).m_target);
152  edge.flow =
153  static_cast<int64_t>(capacity[*e] - residual_capacity[*e]);
154  edge.residual_capacity =
155  static_cast<int64_t>(residual_capacity[*e]);
156  edge.cost = weight[*e] * static_cast<double>(edge.flow);
157  if (flowEdges.size() == 0)
158  edge.agg_cost = edge.cost;
159  else
160  edge.agg_cost = (flowEdges.back()).agg_cost + edge.cost;
161  flowEdges.push_back(edge);
162  }
163  }
164  return flowEdges;
165 }
166 
167 } // namespace graph
168 } // namespace pgrouting
edge::reverse_cost
float8 reverse_cost
Definition: trsp.h:46
edge::cost
float8 cost
Definition: trsp.h:45
edge::target
int64 target
Definition: trsp.h:44
pgrouting::graph::PgrCostFlowGraph::PgrCostFlowGraph
PgrCostFlowGraph()=delete
pgr_flow_t
Definition: pgr_flow_t.h:37
pgrouting::graph::PgrCostFlowGraph::residual_capacity
ResidualCapacity residual_capacity
Definition: pgr_minCostMaxFlow.hpp:58
pgrouting::graph::PgrCostFlowGraph::rev
Reversed rev
Definition: pgr_minCostMaxFlow.hpp:59
pgrouting::graph::PgrCostFlowGraph::weight
Weight weight
Definition: pgr_minCostMaxFlow.hpp:60
edge
Definition: trsp.h:41
pgrouting::graph::PgrCostFlowGraph::SetSupersource
void SetSupersource(const std::set< int64_t > &source_vertices)
Definition: pgr_minCostMaxFlow.cpp:100
pgrouting::graph::PgrCostFlowGraph::E_it
boost::graph_traits< CostFlowGraph >::edge_iterator E_it
Definition: pgr_minCostMaxFlow.hpp:55
pgrouting::graph::PgrCostFlowGraph::GetBoostVertex
V GetBoostVertex(int64_t id) const
Definition: pgr_minCostMaxFlow.hpp:83
pgrouting::graph::PgrCostFlowGraph::GetVertexId
int64_t GetVertexId(V v) const
Definition: pgr_minCostMaxFlow.hpp:87
pgr_minCostMaxFlow.hpp
pgrouting::graph::PgrCostFlowGraph::V
Traits::vertex_descriptor V
Definition: pgr_minCostMaxFlow.hpp:52
pgrouting::graph::PgrCostFlowGraph::GetMaxFlow
int64_t GetMaxFlow() const
Definition: pgr_minCostMaxFlow.cpp:128
edge::source
int64 source
Definition: trsp.h:43
pgrouting::graph::PgrCostFlowGraph::SetSupersink
void SetSupersink(const std::set< int64_t > &sink_vertices)
Definition: pgr_minCostMaxFlow.cpp:114
pgrouting::graph::PgrCostFlowGraph::capacity
Capacity capacity
Definition: pgr_minCostMaxFlow.hpp:57
pgrouting::graph::PgrCostFlowGraph::AddEdge
E AddEdge(V v, V w, double wei, double cap)
Definition: pgr_minCostMaxFlow.cpp:51
pgrouting::graph::PgrCostFlowGraph::AddVertices
void AddVertices(const T &edges, const std::set< int64_t > &source_vertices, const std::set< int64_t > &sink_vertices)
Definition: pgr_minCostMaxFlow.hpp:111
pgrouting::graph::PgrCostFlowGraph::eToId
std::map< E, int64_t > eToId
Definition: pgr_minCostMaxFlow.hpp:137
pgrouting::graph::PgrCostFlowGraph::GetFlowEdges
std::vector< pgr_flow_t > GetFlowEdges() const
Definition: pgr_minCostMaxFlow.cpp:141
pgrouting::graph::PgrCostFlowGraph::E
Traits::edge_descriptor E
Definition: pgr_minCostMaxFlow.hpp:53
pgrouting::graph::PgrCostFlowGraph::GetEdgeId
int64_t GetEdgeId(E e) const
Definition: pgr_minCostMaxFlow.hpp:91
pgrouting::graph::PgrCostFlowGraph::supersource
V supersource
Definition: pgr_minCostMaxFlow.hpp:144
pgrouting::graph::PgrCostFlowGraph::supersink
V supersink
Definition: pgr_minCostMaxFlow.hpp:145
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::graph::PgrCostFlowGraph::graph
CostFlowGraph graph
Definition: pgr_minCostMaxFlow.hpp:134
pgrouting::graph::PgrCostFlowGraph::InsertEdges
void InsertEdges(const std::vector< pgr_costFlow_t > &edges)
Definition: pgr_minCostMaxFlow.cpp:63