OpenTTD Source  20241121-master-g67a0fccfad
mcf.cpp
Go to the documentation of this file.
1 
3 #include "../stdafx.h"
4 #include "../core/math_func.hpp"
5 #include "../timer/timer_game_tick.h"
6 #include "mcf.h"
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:
97 
98  std::vector<LinkGraphJob::EdgeAnnotation>::const_iterator i;
99  std::vector<LinkGraphJob::EdgeAnnotation>::const_iterator end;
100 
101 public:
102 
108 
113  void SetNode(NodeID, NodeID node)
114  {
115  this->i = this->job[node].edges.cbegin();
116  this->end = this->job[node].edges.cend();
117  }
118 
123  NodeID Next()
124  {
125  return this->i != this->end ? (this->i++)->base.dest_node : INVALID_NODE;
126  }
127 };
128 
133 private:
135 
137  std::vector<NodeID> station_to_node;
138 
140  FlowStat::SharesMap::const_iterator it;
141 
143  FlowStat::SharesMap::const_iterator end;
144 public:
145 
151  {
152  for (NodeID i = 0; i < job.Size(); ++i) {
153  StationID st = job[i].base.station;
154  if (st >= this->station_to_node.size()) {
155  this->station_to_node.resize(st + 1);
156  }
157  this->station_to_node[st] = i;
158  }
159  }
160 
166  void SetNode(NodeID source, NodeID node)
167  {
168  const FlowStatMap &flows = this->job[node].flows;
169  FlowStatMap::const_iterator it = flows.find(this->job[source].base.station);
170  if (it != flows.end()) {
171  this->it = it->second.GetShares()->begin();
172  this->end = it->second.GetShares()->end();
173  } else {
174  this->it = FlowStat::empty_sharesmap.begin();
175  this->end = FlowStat::empty_sharesmap.end();
176  }
177  }
178 
183  NodeID Next()
184  {
185  if (this->it == this->end) return INVALID_NODE;
186  return this->station_to_node[(this->it++)->second];
187  }
188 };
189 
200  int free_cap, uint dist) const
201 {
202  /* If any of the paths is disconnected, the other one is better. If both
203  * are disconnected, this path is better.*/
204  if (base->distance == UINT_MAX) {
205  return false;
206  } else if (this->distance == UINT_MAX) {
207  return true;
208  }
209 
210  if (free_cap > 0 && base->free_capacity > 0) {
211  /* If both paths have capacity left, compare their distances.
212  * If the other path has capacity left and this one hasn't, the
213  * other one's better (thus, return true). */
214  return this->free_capacity > 0 ? (base->distance + dist < this->distance) : true;
215  } else {
216  /* If the other path doesn't have capacity left, but this one has,
217  * the other one is worse (thus, return false).
218  * If both paths are out of capacity, do the regular distance
219  * comparison. */
220  return this->free_capacity > 0 ? false : (base->distance + dist < this->distance);
221  }
222 }
223 
234  int free_cap, uint dist) const
235 {
236  int min_cap = Path::GetCapacityRatio(std::min(base->free_capacity, free_cap), std::min(base->capacity, cap));
237  int this_cap = this->GetCapacityRatio();
238  if (min_cap == this_cap) {
239  /* If the capacities are the same and the other path isn't disconnected
240  * choose the shorter path. */
241  return base->distance == UINT_MAX ? false : (base->distance + dist < this->distance);
242  } else {
243  return min_cap > this_cap;
244  }
245 }
246 
256 template<class Tannotation, class Tedge_iterator>
257 void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths)
258 {
259  typedef std::set<Tannotation *, typename Tannotation::Comparator> AnnoSet;
260  Tedge_iterator iter(this->job);
261  uint16_t size = this->job.Size();
262  AnnoSet annos;
263  paths.resize(size, nullptr);
264  for (NodeID node = 0; node < size; ++node) {
265  Tannotation *anno = new Tannotation(node, node == source_node);
266  anno->UpdateAnnotation();
267  annos.insert(anno);
268  paths[node] = anno;
269  }
270  while (!annos.empty()) {
271  typename AnnoSet::iterator i = annos.begin();
272  Tannotation *source = *i;
273  annos.erase(i);
274  NodeID from = source->GetNode();
275  iter.SetNode(source_node, from);
276  for (NodeID to = iter.Next(); to != INVALID_NODE; to = iter.Next()) {
277  if (to == from) continue; // Not a real edge but a consumption sign.
278  const Edge &edge = this->job[from][to];
279  uint capacity = edge.base.capacity;
280  if (this->max_saturation != UINT_MAX) {
281  capacity *= this->max_saturation;
282  capacity /= 100;
283  if (capacity == 0) capacity = 1;
284  }
285  /* Prioritize the fastest route for passengers, mail and express cargo,
286  * and the shortest route for other classes of cargo.
287  * In-between stops are punished with a 1 tile or 1 day penalty. */
288  bool express = IsCargoInClass(this->job.Cargo(), CC_PASSENGERS) ||
289  IsCargoInClass(this->job.Cargo(), CC_MAIL) ||
291  uint distance = DistanceMaxPlusManhattan(this->job[from].base.xy, this->job[to].base.xy) + 1;
292  /* Compute a default travel time from the distance and an average speed of 1 tile/day. */
293  uint time = (edge.base.TravelTime() != 0) ? edge.base.TravelTime() + Ticks::DAY_TICKS : distance * Ticks::DAY_TICKS;
294  uint distance_anno = express ? time : distance;
295 
296  Tannotation *dest = static_cast<Tannotation *>(paths[to]);
297  if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance_anno)) {
298  annos.erase(dest);
299  dest->Fork(source, capacity, capacity - edge.Flow(), distance_anno);
300  dest->UpdateAnnotation();
301  annos.insert(dest);
302  }
303  }
304  }
305 }
306 
312 void MultiCommodityFlow::CleanupPaths(NodeID source_id, PathVector &paths)
313 {
314  Path *source = paths[source_id];
315  paths[source_id] = nullptr;
316  for (PathVector::iterator i = paths.begin(); i != paths.end(); ++i) {
317  Path *path = *i;
318  if (path == nullptr) continue;
319  if (path->GetParent() == source) path->Detach();
320  while (path != source && path != nullptr && path->GetFlow() == 0) {
321  Path *parent = path->GetParent();
322  path->Detach();
323  if (path->GetNumChildren() == 0) {
324  paths[path->GetNode()] = nullptr;
325  delete path;
326  }
327  path = parent;
328  }
329  }
330  delete source;
331  paths.clear();
332 }
333 
344 uint MultiCommodityFlow::PushFlow(Node &node, NodeID to, Path *path, uint accuracy,
345  uint max_saturation)
346 {
347  assert(node.UnsatisfiedDemandTo(to) > 0);
348  uint flow = Clamp(node.DemandTo(to) / accuracy, 1, node.UnsatisfiedDemandTo(to));
349  flow = path->AddFlow(flow, this->job, max_saturation);
350  node.SatisfyDemandTo(to, flow);
351  return flow;
352 }
353 
360 uint MCF1stPass::FindCycleFlow(const PathVector &path, const Path *cycle_begin)
361 {
362  uint flow = UINT_MAX;
363  const Path *cycle_end = cycle_begin;
364  do {
365  flow = std::min(flow, cycle_begin->GetFlow());
366  cycle_begin = path[cycle_begin->GetNode()];
367  } while (cycle_begin != cycle_end);
368  return flow;
369 }
370 
377 void MCF1stPass::EliminateCycle(PathVector &path, Path *cycle_begin, uint flow)
378 {
379  Path *cycle_end = cycle_begin;
380  do {
381  NodeID prev = cycle_begin->GetNode();
382  cycle_begin->ReduceFlow(flow);
383  if (cycle_begin->GetFlow() == 0) {
384  PathList &node_paths = this->job[cycle_begin->GetParent()->GetNode()].paths;
385  for (PathList::iterator i = node_paths.begin(); i != node_paths.end(); ++i) {
386  if (*i == cycle_begin) {
387  node_paths.erase(i);
388  node_paths.push_back(cycle_begin);
389  break;
390  }
391  }
392  }
393  cycle_begin = path[prev];
394  Edge &edge = this->job[prev][cycle_begin->GetNode()];
395  edge.RemoveFlow(flow);
396  } while (cycle_begin != cycle_end);
397 }
398 
408 bool MCF1stPass::EliminateCycles(PathVector &path, NodeID origin_id, NodeID next_id)
409 {
410  Path *at_next_pos = path[next_id];
411 
412  /* this node has already been searched */
413  if (at_next_pos == Path::invalid_path) return false;
414 
415  if (at_next_pos == nullptr) {
416  /* Summarize paths; add up the paths with the same source and next hop
417  * in one path each. */
418  PathList &paths = this->job[next_id].paths;
419  PathViaMap next_hops;
420  for (PathList::iterator i = paths.begin(); i != paths.end();) {
421  Path *new_child = *i;
422  uint new_flow = new_child->GetFlow();
423  if (new_flow == 0) break;
424  if (new_child->GetOrigin() == origin_id) {
425  PathViaMap::iterator via_it = next_hops.find(new_child->GetNode());
426  if (via_it == next_hops.end()) {
427  next_hops[new_child->GetNode()] = new_child;
428  ++i;
429  } else {
430  Path *child = via_it->second;
431  child->AddFlow(new_flow);
432  new_child->ReduceFlow(new_flow);
433 
434  /* We might hit end() with with the ++ here and skip the
435  * newly push_back'ed path. That's good as the flow of that
436  * path is 0 anyway. */
437  paths.erase(i++);
438  paths.push_back(new_child);
439  }
440  } else {
441  ++i;
442  }
443  }
444  bool found = false;
445  /* Search the next hops for nodes we have already visited */
446  for (PathViaMap::iterator via_it = next_hops.begin();
447  via_it != next_hops.end(); ++via_it) {
448  Path *child = via_it->second;
449  if (child->GetFlow() > 0) {
450  /* Push one child into the path vector and search this child's
451  * children. */
452  path[next_id] = child;
453  found = this->EliminateCycles(path, origin_id, child->GetNode()) || found;
454  }
455  }
456  /* All paths departing from this node have been searched. Mark as
457  * resolved if no cycles found. If cycles were found further cycles
458  * could be found in this branch, thus it has to be searched again next
459  * time we spot it.
460  */
461  path[next_id] = found ? nullptr : Path::invalid_path;
462  return found;
463  }
464 
465  /* This node has already been visited => we have a cycle.
466  * Backtrack to find the exact flow. */
467  uint flow = this->FindCycleFlow(path, at_next_pos);
468  if (flow > 0) {
469  this->EliminateCycle(path, at_next_pos, flow);
470  return true;
471  }
472 
473  return false;
474 }
475 
482 {
483  bool cycles_found = false;
484  uint16_t size = this->job.Size();
485  PathVector path(size, nullptr);
486  for (NodeID node = 0; node < size; ++node) {
487  /* Starting at each node in the graph find all cycles involving this
488  * node. */
489  std::fill(path.begin(), path.end(), (Path *)nullptr);
490  cycles_found |= this->EliminateCycles(path, node, node);
491  }
492  return cycles_found;
493 }
494 
500 {
501  PathVector paths;
502  uint16_t size = job.Size();
503  uint accuracy = job.Settings().accuracy;
504  bool more_loops;
505  std::vector<bool> finished_sources(size);
506 
507  do {
508  more_loops = false;
509  for (NodeID source = 0; source < size; ++source) {
510  if (finished_sources[source]) continue;
511 
512  /* First saturate the shortest paths. */
513  this->Dijkstra<DistanceAnnotation, GraphEdgeIterator>(source, paths);
514 
515  Node &src_node = job[source];
516  bool source_demand_left = false;
517  for (NodeID dest = 0; dest < size; ++dest) {
518  if (src_node.UnsatisfiedDemandTo(dest) > 0) {
519  Path *path = paths[dest];
520  assert(path != nullptr);
521  /* Generally only allow paths that don't exceed the
522  * available capacity. But if no demand has been assigned
523  * yet, make an exception and allow any valid path *once*. */
524  if (path->GetFreeCapacity() > 0 && this->PushFlow(src_node, dest, path,
525  accuracy, this->max_saturation) > 0) {
526  /* If a path has been found there is a chance we can
527  * find more. */
528  more_loops = more_loops || (src_node.UnsatisfiedDemandTo(dest) > 0);
529  } else if (src_node.UnsatisfiedDemandTo(dest) == src_node.DemandTo(dest) &&
530  path->GetFreeCapacity() > INT_MIN) {
531  this->PushFlow(src_node, dest, path, accuracy, UINT_MAX);
532  }
533  if (src_node.UnsatisfiedDemandTo(dest) > 0) source_demand_left = true;
534  }
535  }
536  finished_sources[source] = !source_demand_left;
537  this->CleanupPaths(source, paths);
538  }
539  } while ((more_loops || this->EliminateCycles()) && !job.IsJobAborted());
540 }
541 
548 {
549  this->max_saturation = UINT_MAX; // disable artificial cap on saturation
550  PathVector paths;
551  uint16_t size = job.Size();
552  uint accuracy = job.Settings().accuracy;
553  bool demand_left = true;
554  std::vector<bool> finished_sources(size);
555  while (demand_left && !job.IsJobAborted()) {
556  demand_left = false;
557  for (NodeID source = 0; source < size; ++source) {
558  if (finished_sources[source]) continue;
559 
560  this->Dijkstra<CapacityAnnotation, FlowEdgeIterator>(source, paths);
561 
562  Node &src_node = job[source];
563  bool source_demand_left = false;
564  for (NodeID dest = 0; dest < size; ++dest) {
565  Path *path = paths[dest];
566  if (src_node.UnsatisfiedDemandTo(dest) > 0 && path->GetFreeCapacity() > INT_MIN) {
567  this->PushFlow(src_node, dest, path, accuracy, UINT_MAX);
568  if (src_node.UnsatisfiedDemandTo(dest) > 0) {
569  demand_left = true;
570  source_demand_left = true;
571  }
572  }
573  }
574  finished_sources[source] = !source_demand_left;
575  this->CleanupPaths(source, paths);
576  }
577  }
578 }
579 
591 template <typename T>
592 bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
593 {
594  if (x_anno > y_anno) return true;
595  if (x_anno < y_anno) return false;
596  return x > y;
597 }
598 
606  const CapacityAnnotation *y) const
607 {
608  return x != y && Greater<int>(x->GetAnnotation(), y->GetAnnotation(),
609  x->GetNode(), y->GetNode());
610 }
611 
619  const DistanceAnnotation *y) const
620 {
621  return x != y && !Greater<uint>(x->GetAnnotation(), y->GetAnnotation(),
622  x->GetNode(), y->GetNode());
623 }
bool IsCargoInClass(CargoID c, CargoClass cc)
Does cargo c have cargo class cc?
Definition: cargotype.h:232
@ CC_MAIL
Mail.
Definition: cargotype.h:51
@ CC_EXPRESS
Express cargo (Goods, Food, Candy, but also possible for passengers)
Definition: cargotype.h:52
@ CC_PASSENGERS
Passengers.
Definition: cargotype.h:50
Capacity-based annotation for use in the Dijkstra algorithm.
Definition: mcf.cpp:54
void UpdateAnnotation()
Update the cached annotation value.
Definition: mcf.cpp:77
int GetAnnotation() const
Return the actual value of the annotation, in this case the capacity.
Definition: mcf.cpp:72
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:233
CapacityAnnotation(NodeID n, bool source=false)
Constructor.
Definition: mcf.cpp:64
Distance-based annotation for use in the Dijkstra algorithm.
Definition: mcf.cpp:17
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:199
DistanceAnnotation(NodeID n, bool source=false)
Constructor.
Definition: mcf.cpp:25
uint GetAnnotation() const
Return the actual value of the annotation, in this case the distance.
Definition: mcf.cpp:33
void UpdateAnnotation()
Update the cached annotation value.
Definition: mcf.cpp:38
Iterator class for getting edges from a FlowStatMap.
Definition: mcf.cpp:132
FlowStat::SharesMap::const_iterator end
End of the shares map.
Definition: mcf.cpp:143
FlowStat::SharesMap::const_iterator it
Current iterator in the shares map.
Definition: mcf.cpp:140
std::vector< NodeID > station_to_node
Lookup table for getting NodeIDs from StationIDs.
Definition: mcf.cpp:137
void SetNode(NodeID source, NodeID node)
Setup the node to retrieve edges from.
Definition: mcf.cpp:166
FlowEdgeIterator(LinkGraphJob &job)
Constructor.
Definition: mcf.cpp:150
LinkGraphJob & job
Link graph job we're working with.
Definition: mcf.cpp:134
NodeID Next()
Get the next node for which a flow exists.
Definition: mcf.cpp:183
Flow descriptions by origin stations.
Definition: station_base.h:148
static const SharesMap empty_sharesmap
Static instance of FlowStat::SharesMap.
Definition: station_base.h:36
Iterator class for getting the edges in the order of their next_edge members.
Definition: mcf.cpp:94
LinkGraphJob & job
Job being executed.
Definition: mcf.cpp:96
std::vector< LinkGraphJob::EdgeAnnotation >::const_iterator end
Iterator pointing beyond last edge.
Definition: mcf.cpp:99
std::vector< LinkGraphJob::EdgeAnnotation >::const_iterator i
Iterator pointing to current edge.
Definition: mcf.cpp:98
GraphEdgeIterator(LinkGraphJob &job)
Construct a GraphEdgeIterator.
Definition: mcf.cpp:107
NodeID Next()
Retrieve the ID of the node the next edge points to.
Definition: mcf.cpp:123
void SetNode(NodeID, NodeID node)
Setup the node to start iterating at.
Definition: mcf.cpp:113
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:29
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:232
bool IsJobAborted() const
Check if job has been aborted.
Definition: linkgraphjob.h:200
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:245
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:251
MCF1stPass(LinkGraphJob &job)
Run the first pass of the MCF calculation.
Definition: mcf.cpp:499
bool EliminateCycles()
Eliminate all cycles in the graph.
Definition: mcf.cpp:481
uint FindCycleFlow(const PathVector &path, const Path *cycle_begin)
Find the flow along a cycle including cycle_begin in path.
Definition: mcf.cpp:360
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:377
MCF2ndPass(LinkGraphJob &job)
Run the second pass of the MCF calculation which assigns all remaining demands to existing paths.
Definition: mcf.cpp:547
Multi-commodity flow calculating base class.
Definition: mcf.h:13
void Dijkstra(NodeID from, PathVector &paths)
A slightly modified Dijkstra algorithm.
Definition: mcf.cpp:257
LinkGraphJob & job
Job we're working with.
Definition: mcf.h:30
uint max_saturation
Maximum saturation for edges.
Definition: mcf.h:31
uint PushFlow(Node &node, NodeID to, Path *path, uint accuracy, uint max_saturation)
Push flow along a path and update the unsatisfied_demand of the associated edge.
Definition: mcf.cpp:344
void CleanupPaths(NodeID source, PathVector &paths)
Clean up paths that lead nowhere and the root path.
Definition: mcf.cpp:312
A leg of a path in the link graph.
Definition: linkgraphjob.h:275
NodeID GetOrigin() const
Get the overall origin of the path.
Definition: linkgraphjob.h:286
Path * GetParent()
Get the parent leg of this one.
Definition: linkgraphjob.h:289
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:325
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:277
void Detach()
Detach this path from its parent.
Definition: linkgraphjob.h:336
int GetFreeCapacity() const
Get the free capacity of the path.
Definition: linkgraphjob.h:295
uint GetFlow() const
Get the flow on this leg.
Definition: linkgraphjob.h:328
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:356
NodeID GetNode() const
Get the node this leg passes.
Definition: linkgraphjob.h:283
int GetCapacityRatio() const
Get capacity ratio of this path.
Definition: linkgraphjob.h:313
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
Definition: linkgraphjob.h:331
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:322
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:357
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:358
static constexpr TimerGameTick::Ticks DAY_TICKS
1 day is 74 ticks; TimerGameCalendar::date_fract used to be uint16_t and incremented by 885.
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:194
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Definition: math_func.hpp:79
bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
Relation that creates a weak order without duplicates.
Definition: mcf.cpp:592
Declaration of Multi-Commodity-Flow solver.
Comparator for std containers.
Definition: mcf.cpp:85
bool operator()(const CapacityAnnotation *x, const CapacityAnnotation *y) const
Compare two capacity annotations.
Definition: mcf.cpp:605
Comparator for std containers.
Definition: mcf.cpp:43
bool operator()(const DistanceAnnotation *x, const DistanceAnnotation *y) const
Compare two distance annotations.
Definition: mcf.cpp:618
uint8_t accuracy
accuracy when calculating things on the link graph. low accuracy => low running time
An edge in the link graph.
Definition: linkgraph.h:42
uint32_t TravelTime() const
Get edge's average travel time.
Definition: linkgraph.h:56
uint capacity
Capacity of the link.
Definition: linkgraph.h:43
Node of the link graph.
Definition: linkgraph.h:90