OpenTTD Source  1.11.2
mcf.cpp
Go to the documentation of this file.
1 
3 #include "../stdafx.h"
4 #include "../core/math_func.hpp"
5 #include "mcf.h"
6 #include <set>
7 
8 #include "../safeguards.h"
9 
10 typedef std::map<NodeID, Path *> PathViaMap;
11 
17 class DistanceAnnotation : public Path {
18 public:
19 
25  DistanceAnnotation(NodeID n, bool source = false) : Path(n, source) {}
26 
27  bool IsBetter(const DistanceAnnotation *base, uint cap, int free_cap, uint dist) const;
28 
33  inline uint GetAnnotation() const { return this->distance; }
34 
38  inline void UpdateAnnotation() { }
39 
43  struct Comparator {
44  bool operator()(const DistanceAnnotation *x, const DistanceAnnotation *y) const;
45  };
46 };
47 
54 class CapacityAnnotation : public Path {
55  int cached_annotation;
56 
57 public:
58 
64  CapacityAnnotation(NodeID n, bool source = false) : Path(n, source) {}
65 
66  bool IsBetter(const CapacityAnnotation *base, uint cap, int free_cap, uint dist) const;
67 
72  inline int GetAnnotation() const { return this->cached_annotation; }
73 
77  inline void UpdateAnnotation()
78  {
79  this->cached_annotation = this->GetCapacityRatio();
80  }
81 
85  struct Comparator {
86  bool operator()(const CapacityAnnotation *x, const CapacityAnnotation *y) const;
87  };
88 };
89 
95 private:
99 
100 public:
101 
107  i(nullptr, nullptr, INVALID_NODE), end(nullptr, nullptr, INVALID_NODE)
108  {}
109 
115  void SetNode(NodeID source, NodeID node)
116  {
117  this->i = this->job[node].Begin();
118  this->end = this->job[node].End();
119  }
120 
125  NodeID Next()
126  {
127  return this->i != this->end ? (this->i++)->first : INVALID_NODE;
128  }
129 };
130 
135 private:
137 
139  std::vector<NodeID> station_to_node;
140 
142  FlowStat::SharesMap::const_iterator it;
143 
145  FlowStat::SharesMap::const_iterator end;
146 public:
147 
153  {
154  for (NodeID i = 0; i < job.Size(); ++i) {
155  StationID st = job[i].Station();
156  if (st >= this->station_to_node.size()) {
157  this->station_to_node.resize(st + 1);
158  }
159  this->station_to_node[st] = i;
160  }
161  }
162 
168  void SetNode(NodeID source, NodeID node)
169  {
170  const FlowStatMap &flows = this->job[node].Flows();
171  FlowStatMap::const_iterator it = flows.find(this->job[source].Station());
172  if (it != flows.end()) {
173  this->it = it->second.GetShares()->begin();
174  this->end = it->second.GetShares()->end();
175  } else {
176  this->it = FlowStat::empty_sharesmap.begin();
177  this->end = FlowStat::empty_sharesmap.end();
178  }
179  }
180 
185  NodeID Next()
186  {
187  if (this->it == this->end) return INVALID_NODE;
188  return this->station_to_node[(this->it++)->second];
189  }
190 };
191 
202  int free_cap, uint dist) const
203 {
204  /* If any of the paths is disconnected, the other one is better. If both
205  * are disconnected, this path is better.*/
206  if (base->distance == UINT_MAX) {
207  return false;
208  } else if (this->distance == UINT_MAX) {
209  return true;
210  }
211 
212  if (free_cap > 0 && base->free_capacity > 0) {
213  /* If both paths have capacity left, compare their distances.
214  * If the other path has capacity left and this one hasn't, the
215  * other one's better (thus, return true). */
216  return this->free_capacity > 0 ? (base->distance + dist < this->distance) : true;
217  } else {
218  /* If the other path doesn't have capacity left, but this one has,
219  * the other one is worse (thus, return false).
220  * If both paths are out of capacity, do the regular distance
221  * comparison. */
222  return this->free_capacity > 0 ? false : (base->distance + dist < this->distance);
223  }
224 }
225 
236  int free_cap, uint dist) const
237 {
238  int min_cap = Path::GetCapacityRatio(std::min(base->free_capacity, free_cap), std::min(base->capacity, cap));
239  int this_cap = this->GetCapacityRatio();
240  if (min_cap == this_cap) {
241  /* If the capacities are the same and the other path isn't disconnected
242  * choose the shorter path. */
243  return base->distance == UINT_MAX ? false : (base->distance + dist < this->distance);
244  } else {
245  return min_cap > this_cap;
246  }
247 }
248 
258 template<class Tannotation, class Tedge_iterator>
259 void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths)
260 {
261  typedef std::set<Tannotation *, typename Tannotation::Comparator> AnnoSet;
262  Tedge_iterator iter(this->job);
263  uint size = this->job.Size();
264  AnnoSet annos;
265  paths.resize(size, nullptr);
266  for (NodeID node = 0; node < size; ++node) {
267  Tannotation *anno = new Tannotation(node, node == source_node);
268  anno->UpdateAnnotation();
269  annos.insert(anno);
270  paths[node] = anno;
271  }
272  while (!annos.empty()) {
273  typename AnnoSet::iterator i = annos.begin();
274  Tannotation *source = *i;
275  annos.erase(i);
276  NodeID from = source->GetNode();
277  iter.SetNode(source_node, from);
278  for (NodeID to = iter.Next(); to != INVALID_NODE; to = iter.Next()) {
279  if (to == from) continue; // Not a real edge but a consumption sign.
280  Edge edge = this->job[from][to];
281  uint capacity = edge.Capacity();
282  if (this->max_saturation != UINT_MAX) {
283  capacity *= this->max_saturation;
284  capacity /= 100;
285  if (capacity == 0) capacity = 1;
286  }
287  /* punish in-between stops a little */
288  uint distance = DistanceMaxPlusManhattan(this->job[from].XY(), this->job[to].XY()) + 1;
289  Tannotation *dest = static_cast<Tannotation *>(paths[to]);
290  if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance)) {
291  annos.erase(dest);
292  dest->Fork(source, capacity, capacity - edge.Flow(), distance);
293  dest->UpdateAnnotation();
294  annos.insert(dest);
295  }
296  }
297  }
298 }
299 
305 void MultiCommodityFlow::CleanupPaths(NodeID source_id, PathVector &paths)
306 {
307  Path *source = paths[source_id];
308  paths[source_id] = nullptr;
309  for (PathVector::iterator i = paths.begin(); i != paths.end(); ++i) {
310  Path *path = *i;
311  if (path == nullptr) continue;
312  if (path->GetParent() == source) path->Detach();
313  while (path != source && path != nullptr && path->GetFlow() == 0) {
314  Path *parent = path->GetParent();
315  path->Detach();
316  if (path->GetNumChildren() == 0) {
317  paths[path->GetNode()] = nullptr;
318  delete path;
319  }
320  path = parent;
321  }
322  }
323  delete source;
324  paths.clear();
325 }
326 
336 uint MultiCommodityFlow::PushFlow(Edge &edge, Path *path, uint accuracy,
337  uint max_saturation)
338 {
339  assert(edge.UnsatisfiedDemand() > 0);
340  uint flow = Clamp(edge.Demand() / accuracy, 1, edge.UnsatisfiedDemand());
341  flow = path->AddFlow(flow, this->job, max_saturation);
342  edge.SatisfyDemand(flow);
343  return flow;
344 }
345 
352 uint MCF1stPass::FindCycleFlow(const PathVector &path, const Path *cycle_begin)
353 {
354  uint flow = UINT_MAX;
355  const Path *cycle_end = cycle_begin;
356  do {
357  flow = std::min(flow, cycle_begin->GetFlow());
358  cycle_begin = path[cycle_begin->GetNode()];
359  } while (cycle_begin != cycle_end);
360  return flow;
361 }
362 
369 void MCF1stPass::EliminateCycle(PathVector &path, Path *cycle_begin, uint flow)
370 {
371  Path *cycle_end = cycle_begin;
372  do {
373  NodeID prev = cycle_begin->GetNode();
374  cycle_begin->ReduceFlow(flow);
375  if (cycle_begin->GetFlow() == 0) {
376  PathList &node_paths = this->job[cycle_begin->GetParent()->GetNode()].Paths();
377  for (PathList::iterator i = node_paths.begin(); i != node_paths.end(); ++i) {
378  if (*i == cycle_begin) {
379  node_paths.erase(i);
380  node_paths.push_back(cycle_begin);
381  break;
382  }
383  }
384  }
385  cycle_begin = path[prev];
386  Edge edge = this->job[prev][cycle_begin->GetNode()];
387  edge.RemoveFlow(flow);
388  } while (cycle_begin != cycle_end);
389 }
390 
400 bool MCF1stPass::EliminateCycles(PathVector &path, NodeID origin_id, NodeID next_id)
401 {
402  Path *at_next_pos = path[next_id];
403 
404  /* this node has already been searched */
405  if (at_next_pos == Path::invalid_path) return false;
406 
407  if (at_next_pos == nullptr) {
408  /* Summarize paths; add up the paths with the same source and next hop
409  * in one path each. */
410  PathList &paths = this->job[next_id].Paths();
411  PathViaMap next_hops;
412  for (PathList::iterator i = paths.begin(); i != paths.end();) {
413  Path *new_child = *i;
414  uint new_flow = new_child->GetFlow();
415  if (new_flow == 0) break;
416  if (new_child->GetOrigin() == origin_id) {
417  PathViaMap::iterator via_it = next_hops.find(new_child->GetNode());
418  if (via_it == next_hops.end()) {
419  next_hops[new_child->GetNode()] = new_child;
420  ++i;
421  } else {
422  Path *child = via_it->second;
423  child->AddFlow(new_flow);
424  new_child->ReduceFlow(new_flow);
425 
426  /* We might hit end() with with the ++ here and skip the
427  * newly push_back'ed path. That's good as the flow of that
428  * path is 0 anyway. */
429  paths.erase(i++);
430  paths.push_back(new_child);
431  }
432  } else {
433  ++i;
434  }
435  }
436  bool found = false;
437  /* Search the next hops for nodes we have already visited */
438  for (PathViaMap::iterator via_it = next_hops.begin();
439  via_it != next_hops.end(); ++via_it) {
440  Path *child = via_it->second;
441  if (child->GetFlow() > 0) {
442  /* Push one child into the path vector and search this child's
443  * children. */
444  path[next_id] = child;
445  found = this->EliminateCycles(path, origin_id, child->GetNode()) || found;
446  }
447  }
448  /* All paths departing from this node have been searched. Mark as
449  * resolved if no cycles found. If cycles were found further cycles
450  * could be found in this branch, thus it has to be searched again next
451  * time we spot it.
452  */
453  path[next_id] = found ? nullptr : Path::invalid_path;
454  return found;
455  }
456 
457  /* This node has already been visited => we have a cycle.
458  * Backtrack to find the exact flow. */
459  uint flow = this->FindCycleFlow(path, at_next_pos);
460  if (flow > 0) {
461  this->EliminateCycle(path, at_next_pos, flow);
462  return true;
463  }
464 
465  return false;
466 }
467 
474 {
475  bool cycles_found = false;
476  uint size = this->job.Size();
477  PathVector path(size, nullptr);
478  for (NodeID node = 0; node < size; ++node) {
479  /* Starting at each node in the graph find all cycles involving this
480  * node. */
481  std::fill(path.begin(), path.end(), (Path *)nullptr);
482  cycles_found |= this->EliminateCycles(path, node, node);
483  }
484  return cycles_found;
485 }
486 
492 {
493  PathVector paths;
494  uint size = job.Size();
495  uint accuracy = job.Settings().accuracy;
496  bool more_loops;
497  std::vector<bool> finished_sources(size);
498 
499  do {
500  more_loops = false;
501  for (NodeID source = 0; source < size; ++source) {
502  if (finished_sources[source]) continue;
503 
504  /* First saturate the shortest paths. */
505  this->Dijkstra<DistanceAnnotation, GraphEdgeIterator>(source, paths);
506 
507  bool source_demand_left = false;
508  for (NodeID dest = 0; dest < size; ++dest) {
509  Edge edge = job[source][dest];
510  if (edge.UnsatisfiedDemand() > 0) {
511  Path *path = paths[dest];
512  assert(path != nullptr);
513  /* Generally only allow paths that don't exceed the
514  * available capacity. But if no demand has been assigned
515  * yet, make an exception and allow any valid path *once*. */
516  if (path->GetFreeCapacity() > 0 && this->PushFlow(edge, path,
517  accuracy, this->max_saturation) > 0) {
518  /* If a path has been found there is a chance we can
519  * find more. */
520  more_loops = more_loops || (edge.UnsatisfiedDemand() > 0);
521  } else if (edge.UnsatisfiedDemand() == edge.Demand() &&
522  path->GetFreeCapacity() > INT_MIN) {
523  this->PushFlow(edge, path, accuracy, UINT_MAX);
524  }
525  if (edge.UnsatisfiedDemand() > 0) source_demand_left = true;
526  }
527  }
528  finished_sources[source] = !source_demand_left;
529  this->CleanupPaths(source, paths);
530  }
531  } while ((more_loops || this->EliminateCycles()) && !job.IsJobAborted());
532 }
533 
540 {
541  this->max_saturation = UINT_MAX; // disable artificial cap on saturation
542  PathVector paths;
543  uint size = job.Size();
544  uint accuracy = job.Settings().accuracy;
545  bool demand_left = true;
546  std::vector<bool> finished_sources(size);
547  while (demand_left && !job.IsJobAborted()) {
548  demand_left = false;
549  for (NodeID source = 0; source < size; ++source) {
550  if (finished_sources[source]) continue;
551 
552  this->Dijkstra<CapacityAnnotation, FlowEdgeIterator>(source, paths);
553 
554  bool source_demand_left = false;
555  for (NodeID dest = 0; dest < size; ++dest) {
556  Edge edge = this->job[source][dest];
557  Path *path = paths[dest];
558  if (edge.UnsatisfiedDemand() > 0 && path->GetFreeCapacity() > INT_MIN) {
559  this->PushFlow(edge, path, accuracy, UINT_MAX);
560  if (edge.UnsatisfiedDemand() > 0) {
561  demand_left = true;
562  source_demand_left = true;
563  }
564  }
565  }
566  finished_sources[source] = !source_demand_left;
567  this->CleanupPaths(source, paths);
568  }
569  }
570 }
571 
583 template <typename T>
584 bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
585 {
586  if (x_anno > y_anno) return true;
587  if (x_anno < y_anno) return false;
588  return x > y;
589 }
590 
598  const CapacityAnnotation *y) const
599 {
600  return x != y && Greater<int>(x->GetAnnotation(), y->GetAnnotation(),
601  x->GetNode(), y->GetNode());
602 }
603 
611  const DistanceAnnotation *y) const
612 {
613  return x != y && !Greater<uint>(x->GetAnnotation(), y->GetAnnotation(),
614  x->GetNode(), y->GetNode());
615 }
FlowEdgeIterator::Next
NodeID Next()
Get the next node for which a flow exists.
Definition: mcf.cpp:185
mcf.h
GraphEdgeIterator::GraphEdgeIterator
GraphEdgeIterator(LinkGraphJob &job)
Construct a GraphEdgeIterator.
Definition: mcf.cpp:106
Path::capacity
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:449
Path
A leg of a path in the link graph.
Definition: linkgraphjob.h:365
Path::GetCapacityRatio
int GetCapacityRatio() const
Get capacity ratio of this path.
Definition: linkgraphjob.h:403
MultiCommodityFlow::max_saturation
uint max_saturation
Maximum saturation for edges.
Definition: mcf.h:32
FlowEdgeIterator::FlowEdgeIterator
FlowEdgeIterator(LinkGraphJob &job)
Constructor.
Definition: mcf.cpp:152
MCF2ndPass::MCF2ndPass
MCF2ndPass(LinkGraphJob &job)
Run the second pass of the MCF calculation which assigns all remaining demands to existing paths.
Definition: mcf.cpp:539
Path::invalid_path
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:367
Station
Station data structure.
Definition: station_base.h:450
LinkGraphJob::Settings
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:322
LinkGraphJob
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:30
GraphEdgeIterator::job
LinkGraphJob & job
Job being executed.
Definition: mcf.cpp:96
LinkGraph::EdgeIterator
An iterator for non-const edges.
Definition: linkgraph.h:323
Greater
bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
Relation that creates a weak order without duplicates.
Definition: mcf.cpp:584
DistanceAnnotation::DistanceAnnotation
DistanceAnnotation(NodeID n, bool source=false)
Constructor.
Definition: mcf.cpp:25
Path::GetFreeCapacity
int GetFreeCapacity() const
Get the free capacity of the path.
Definition: linkgraphjob.h:385
LinkGraph::Edge
An updatable edge class.
Definition: linkgraph.h:292
FlowEdgeIterator
Iterator class for getting edges from a FlowStatMap.
Definition: mcf.cpp:134
MultiCommodityFlow::PushFlow
uint PushFlow(Edge &edge, Path *path, uint accuracy, uint max_saturation)
Push flow along a path and update the unsatisfied_demand of the associated edge.
Definition: mcf.cpp:336
Path::GetParent
Path * GetParent()
Get the parent leg of this one.
Definition: linkgraphjob.h:379
MultiCommodityFlow::CleanupPaths
void CleanupPaths(NodeID source, PathVector &paths)
Clean up paths that lead nowhere and the root path.
Definition: mcf.cpp:305
CapacityAnnotation::Comparator::operator()
bool operator()(const CapacityAnnotation *x, const CapacityAnnotation *y) const
Compare two capacity annotations.
Definition: mcf.cpp:597
GraphEdgeIterator
Iterator class for getting the edges in the order of their next_edge members.
Definition: mcf.cpp:94
FlowEdgeIterator::SetNode
void SetNode(NodeID source, NodeID node)
Setup the node to retrieve edges from.
Definition: mcf.cpp:168
LinkGraph::EdgeWrapper::Capacity
uint Capacity() const
Get edge's capacity.
Definition: linkgraph.h:92
MCF1stPass::EliminateCycles
bool EliminateCycles()
Eliminate all cycles in the graph.
Definition: mcf.cpp:473
GraphEdgeIterator::i
EdgeIterator i
Iterator pointing to current edge.
Definition: mcf.cpp:97
FlowEdgeIterator::job
LinkGraphJob & job
Link graph job we're working with.
Definition: mcf.cpp:136
FlowEdgeIterator::end
FlowStat::SharesMap::const_iterator end
End of the shares map.
Definition: mcf.cpp:145
CapacityAnnotation
Capacity-based annotation for use in the Dijkstra algorithm.
Definition: mcf.cpp:54
MCF1stPass::MCF1stPass
MCF1stPass(LinkGraphJob &job)
Run the first pass of the MCF calculation.
Definition: mcf.cpp:491
MCF1stPass::EliminateCycle
void EliminateCycle(PathVector &path, Path *cycle_begin, uint flow)
Eliminate a cycle of the given flow in the given set of paths.
Definition: mcf.cpp:369
Path::distance
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:448
FlowStat::empty_sharesmap
static const SharesMap empty_sharesmap
Static instance of FlowStat::SharesMap.
Definition: station_base.h:40
LinkGraphJob::Size
uint Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:335
MultiCommodityFlow::Dijkstra
void Dijkstra(NodeID from, PathVector &paths)
A slightly modified Dijkstra algorithm.
Definition: mcf.cpp:259
DistanceAnnotation::GetAnnotation
uint GetAnnotation() const
Return the actual value of the annotation, in this case the distance.
Definition: mcf.cpp:33
FlowEdgeIterator::station_to_node
std::vector< NodeID > station_to_node
Lookup table for getting NodeIDs from StationIDs.
Definition: mcf.cpp:139
Clamp
static T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Definition: math_func.hpp:77
LinkGraphSettings::accuracy
uint8 accuracy
accuracy when calculating things on the link graph. low accuracy => low running time
Definition: settings_type.h:520
CapacityAnnotation::IsBetter
bool IsBetter(const CapacityAnnotation *base, uint cap, int free_cap, uint dist) const
Determines if an extension to the given Path with the given parameters is better than this path.
Definition: mcf.cpp:235
DistanceAnnotation
Distance-based annotation for use in the Dijkstra algorithm.
Definition: mcf.cpp:17
LinkGraphJob::IsJobAborted
bool IsJobAborted() const
Check if job has been aborted.
Definition: linkgraphjob.h:290
GraphEdgeIterator::SetNode
void SetNode(NodeID source, NodeID node)
Setup the node to start iterating at.
Definition: mcf.cpp:115
Path::AddFlow
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:415
FlowStatMap
Flow descriptions by origin stations.
Definition: station_base.h:152
FlowEdgeIterator::it
FlowStat::SharesMap::const_iterator it
Current iterator in the shares map.
Definition: mcf.cpp:142
MultiCommodityFlow::job
LinkGraphJob & job
Job we're working with.
Definition: mcf.h:31
DistanceAnnotation::Comparator
Comparator for std containers.
Definition: mcf.cpp:43
Path::free_capacity
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:450
GraphEdgeIterator::Next
NodeID Next()
Retrieve the ID of the node the next edge points to.
Definition: mcf.cpp:125
MCF1stPass::FindCycleFlow
uint FindCycleFlow(const PathVector &path, const Path *cycle_begin)
Find the flow along a cycle including cycle_begin in path.
Definition: mcf.cpp:352
DistanceAnnotation::UpdateAnnotation
void UpdateAnnotation()
Update the cached annotation value.
Definition: mcf.cpp:38
CapacityAnnotation::UpdateAnnotation
void UpdateAnnotation()
Update the cached annotation value.
Definition: mcf.cpp:77
DistanceMaxPlusManhattan
uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
Gets the biggest distance component (x or y) between the two given tiles plus the Manhattan distance,...
Definition: map.cpp:205
GraphEdgeIterator::end
EdgeIterator end
Iterator pointing beyond last edge.
Definition: mcf.cpp:98
CapacityAnnotation::Comparator
Comparator for std containers.
Definition: mcf.cpp:85
Path::GetNumChildren
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
Definition: linkgraphjob.h:421
Path::Detach
void Detach()
Detach this path from its parent.
Definition: linkgraphjob.h:426
Path::ReduceFlow
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:412
DistanceAnnotation::IsBetter
bool IsBetter(const DistanceAnnotation *base, uint cap, int free_cap, uint dist) const
Determines if an extension to the given Path with the given parameters is better than this path.
Definition: mcf.cpp:201
CapacityAnnotation::GetAnnotation
int GetAnnotation() const
Return the actual value of the annotation, in this case the capacity.
Definition: mcf.cpp:72
Path::GetOrigin
NodeID GetOrigin() const
Get the overall origin of the path.
Definition: linkgraphjob.h:376
DistanceAnnotation::Comparator::operator()
bool operator()(const DistanceAnnotation *x, const DistanceAnnotation *y) const
Compare two distance annotations.
Definition: mcf.cpp:610
CapacityAnnotation::CapacityAnnotation
CapacityAnnotation(NodeID n, bool source=false)
Constructor.
Definition: mcf.cpp:64
Path::GetFlow
uint GetFlow() const
Get the flow on this leg.
Definition: linkgraphjob.h:418
MultiCommodityFlow
Multi-commodity flow calculating base class.
Definition: mcf.h:14
Path::GetNode
NodeID GetNode() const
Get the node this leg passes.
Definition: linkgraphjob.h:373