OpenTTD Source  12.0-beta2
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  uint16 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  /* Prioritize the fastest route for passengers, mail and express cargo,
288  * and the shortest route for other classes of cargo.
289  * In-between stops are punished with a 1 tile or 1 day penalty. */
290  bool express = IsCargoInClass(this->job.Cargo(), CC_PASSENGERS) ||
291  IsCargoInClass(this->job.Cargo(), CC_MAIL) ||
293  uint distance = DistanceMaxPlusManhattan(this->job[from].XY(), this->job[to].XY()) + 1;
294  /* Compute a default travel time from the distance and an average speed of 1 tile/day. */
295  uint time = (edge.TravelTime() != 0) ? edge.TravelTime() + DAY_TICKS : distance * DAY_TICKS;
296  uint distance_anno = express ? time : distance;
297 
298  Tannotation *dest = static_cast<Tannotation *>(paths[to]);
299  if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance_anno)) {
300  annos.erase(dest);
301  dest->Fork(source, capacity, capacity - edge.Flow(), distance_anno);
302  dest->UpdateAnnotation();
303  annos.insert(dest);
304  }
305  }
306  }
307 }
308 
314 void MultiCommodityFlow::CleanupPaths(NodeID source_id, PathVector &paths)
315 {
316  Path *source = paths[source_id];
317  paths[source_id] = nullptr;
318  for (PathVector::iterator i = paths.begin(); i != paths.end(); ++i) {
319  Path *path = *i;
320  if (path == nullptr) continue;
321  if (path->GetParent() == source) path->Detach();
322  while (path != source && path != nullptr && path->GetFlow() == 0) {
323  Path *parent = path->GetParent();
324  path->Detach();
325  if (path->GetNumChildren() == 0) {
326  paths[path->GetNode()] = nullptr;
327  delete path;
328  }
329  path = parent;
330  }
331  }
332  delete source;
333  paths.clear();
334 }
335 
345 uint MultiCommodityFlow::PushFlow(Edge &edge, Path *path, uint accuracy,
346  uint max_saturation)
347 {
348  assert(edge.UnsatisfiedDemand() > 0);
349  uint flow = Clamp(edge.Demand() / accuracy, 1, edge.UnsatisfiedDemand());
350  flow = path->AddFlow(flow, this->job, max_saturation);
351  edge.SatisfyDemand(flow);
352  return flow;
353 }
354 
361 uint MCF1stPass::FindCycleFlow(const PathVector &path, const Path *cycle_begin)
362 {
363  uint flow = UINT_MAX;
364  const Path *cycle_end = cycle_begin;
365  do {
366  flow = std::min(flow, cycle_begin->GetFlow());
367  cycle_begin = path[cycle_begin->GetNode()];
368  } while (cycle_begin != cycle_end);
369  return flow;
370 }
371 
378 void MCF1stPass::EliminateCycle(PathVector &path, Path *cycle_begin, uint flow)
379 {
380  Path *cycle_end = cycle_begin;
381  do {
382  NodeID prev = cycle_begin->GetNode();
383  cycle_begin->ReduceFlow(flow);
384  if (cycle_begin->GetFlow() == 0) {
385  PathList &node_paths = this->job[cycle_begin->GetParent()->GetNode()].Paths();
386  for (PathList::iterator i = node_paths.begin(); i != node_paths.end(); ++i) {
387  if (*i == cycle_begin) {
388  node_paths.erase(i);
389  node_paths.push_back(cycle_begin);
390  break;
391  }
392  }
393  }
394  cycle_begin = path[prev];
395  Edge edge = this->job[prev][cycle_begin->GetNode()];
396  edge.RemoveFlow(flow);
397  } while (cycle_begin != cycle_end);
398 }
399 
409 bool MCF1stPass::EliminateCycles(PathVector &path, NodeID origin_id, NodeID next_id)
410 {
411  Path *at_next_pos = path[next_id];
412 
413  /* this node has already been searched */
414  if (at_next_pos == Path::invalid_path) return false;
415 
416  if (at_next_pos == nullptr) {
417  /* Summarize paths; add up the paths with the same source and next hop
418  * in one path each. */
419  PathList &paths = this->job[next_id].Paths();
420  PathViaMap next_hops;
421  for (PathList::iterator i = paths.begin(); i != paths.end();) {
422  Path *new_child = *i;
423  uint new_flow = new_child->GetFlow();
424  if (new_flow == 0) break;
425  if (new_child->GetOrigin() == origin_id) {
426  PathViaMap::iterator via_it = next_hops.find(new_child->GetNode());
427  if (via_it == next_hops.end()) {
428  next_hops[new_child->GetNode()] = new_child;
429  ++i;
430  } else {
431  Path *child = via_it->second;
432  child->AddFlow(new_flow);
433  new_child->ReduceFlow(new_flow);
434 
435  /* We might hit end() with with the ++ here and skip the
436  * newly push_back'ed path. That's good as the flow of that
437  * path is 0 anyway. */
438  paths.erase(i++);
439  paths.push_back(new_child);
440  }
441  } else {
442  ++i;
443  }
444  }
445  bool found = false;
446  /* Search the next hops for nodes we have already visited */
447  for (PathViaMap::iterator via_it = next_hops.begin();
448  via_it != next_hops.end(); ++via_it) {
449  Path *child = via_it->second;
450  if (child->GetFlow() > 0) {
451  /* Push one child into the path vector and search this child's
452  * children. */
453  path[next_id] = child;
454  found = this->EliminateCycles(path, origin_id, child->GetNode()) || found;
455  }
456  }
457  /* All paths departing from this node have been searched. Mark as
458  * resolved if no cycles found. If cycles were found further cycles
459  * could be found in this branch, thus it has to be searched again next
460  * time we spot it.
461  */
462  path[next_id] = found ? nullptr : Path::invalid_path;
463  return found;
464  }
465 
466  /* This node has already been visited => we have a cycle.
467  * Backtrack to find the exact flow. */
468  uint flow = this->FindCycleFlow(path, at_next_pos);
469  if (flow > 0) {
470  this->EliminateCycle(path, at_next_pos, flow);
471  return true;
472  }
473 
474  return false;
475 }
476 
483 {
484  bool cycles_found = false;
485  uint16 size = this->job.Size();
486  PathVector path(size, nullptr);
487  for (NodeID node = 0; node < size; ++node) {
488  /* Starting at each node in the graph find all cycles involving this
489  * node. */
490  std::fill(path.begin(), path.end(), (Path *)nullptr);
491  cycles_found |= this->EliminateCycles(path, node, node);
492  }
493  return cycles_found;
494 }
495 
501 {
502  PathVector paths;
503  uint16 size = job.Size();
504  uint accuracy = job.Settings().accuracy;
505  bool more_loops;
506  std::vector<bool> finished_sources(size);
507 
508  do {
509  more_loops = false;
510  for (NodeID source = 0; source < size; ++source) {
511  if (finished_sources[source]) continue;
512 
513  /* First saturate the shortest paths. */
514  this->Dijkstra<DistanceAnnotation, GraphEdgeIterator>(source, paths);
515 
516  bool source_demand_left = false;
517  for (NodeID dest = 0; dest < size; ++dest) {
518  Edge edge = job[source][dest];
519  if (edge.UnsatisfiedDemand() > 0) {
520  Path *path = paths[dest];
521  assert(path != nullptr);
522  /* Generally only allow paths that don't exceed the
523  * available capacity. But if no demand has been assigned
524  * yet, make an exception and allow any valid path *once*. */
525  if (path->GetFreeCapacity() > 0 && this->PushFlow(edge, path,
526  accuracy, this->max_saturation) > 0) {
527  /* If a path has been found there is a chance we can
528  * find more. */
529  more_loops = more_loops || (edge.UnsatisfiedDemand() > 0);
530  } else if (edge.UnsatisfiedDemand() == edge.Demand() &&
531  path->GetFreeCapacity() > INT_MIN) {
532  this->PushFlow(edge, path, accuracy, UINT_MAX);
533  }
534  if (edge.UnsatisfiedDemand() > 0) source_demand_left = true;
535  }
536  }
537  finished_sources[source] = !source_demand_left;
538  this->CleanupPaths(source, paths);
539  }
540  } while ((more_loops || this->EliminateCycles()) && !job.IsJobAborted());
541 }
542 
549 {
550  this->max_saturation = UINT_MAX; // disable artificial cap on saturation
551  PathVector paths;
552  uint16 size = job.Size();
553  uint accuracy = job.Settings().accuracy;
554  bool demand_left = true;
555  std::vector<bool> finished_sources(size);
556  while (demand_left && !job.IsJobAborted()) {
557  demand_left = false;
558  for (NodeID source = 0; source < size; ++source) {
559  if (finished_sources[source]) continue;
560 
561  this->Dijkstra<CapacityAnnotation, FlowEdgeIterator>(source, paths);
562 
563  bool source_demand_left = false;
564  for (NodeID dest = 0; dest < size; ++dest) {
565  Edge edge = this->job[source][dest];
566  Path *path = paths[dest];
567  if (edge.UnsatisfiedDemand() > 0 && path->GetFreeCapacity() > INT_MIN) {
568  this->PushFlow(edge, path, accuracy, UINT_MAX);
569  if (edge.UnsatisfiedDemand() > 0) {
570  demand_left = true;
571  source_demand_left = true;
572  }
573  }
574  }
575  finished_sources[source] = !source_demand_left;
576  this->CleanupPaths(source, paths);
577  }
578  }
579 }
580 
592 template <typename T>
593 bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
594 {
595  if (x_anno > y_anno) return true;
596  if (x_anno < y_anno) return false;
597  return x > y;
598 }
599 
607  const CapacityAnnotation *y) const
608 {
609  return x != y && Greater<int>(x->GetAnnotation(), y->GetAnnotation(),
610  x->GetNode(), y->GetNode());
611 }
612 
620  const DistanceAnnotation *y) const
621 {
622  return x != y && !Greater<uint>(x->GetAnnotation(), y->GetAnnotation(),
623  x->GetNode(), y->GetNode());
624 }
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:548
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:447
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
LinkGraph::EdgeWrapper::TravelTime
uint32 TravelTime() const
Get edge's average travel time.
Definition: linkgraph.h:105
CC_EXPRESS
@ CC_EXPRESS
Express cargo (Goods, Food, Candy, but also possible for passengers)
Definition: cargotype.h:43
GraphEdgeIterator::job
LinkGraphJob & job
Job being executed.
Definition: mcf.cpp:96
LinkGraph::EdgeIterator
An iterator for non-const edges.
Definition: linkgraph.h:330
Greater
bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
Relation that creates a weak order without duplicates.
Definition: mcf.cpp:593
CC_PASSENGERS
@ CC_PASSENGERS
Passengers.
Definition: cargotype.h:41
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:299
FlowEdgeIterator
Iterator class for getting edges from a FlowStatMap.
Definition: mcf.cpp:134
LinkGraphJob::Size
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:335
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:345
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:314
CapacityAnnotation::Comparator::operator()
bool operator()(const CapacityAnnotation *x, const CapacityAnnotation *y) const
Compare two capacity annotations.
Definition: mcf.cpp:606
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:93
MCF1stPass::EliminateCycles
bool EliminateCycles()
Eliminate all cycles in the graph.
Definition: mcf.cpp:482
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:500
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:378
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:37
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:532
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:149
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:361
LinkGraphJob::Cargo
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:341
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
IsCargoInClass
static bool IsCargoInClass(CargoID c, CargoClass cc)
Does cargo c have cargo class cc?
Definition: cargotype.h:194
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
CC_MAIL
@ CC_MAIL
Mail.
Definition: cargotype.h:42
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
DAY_TICKS
static const int DAY_TICKS
1 day is 74 ticks; _date_fract used to be uint16 and incremented by 885.
Definition: date_type.h:28
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:619
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