4 #include "../core/math_func.hpp"
5 #include "../timer/timer_game_tick.h"
8 #include "../safeguards.h"
10 typedef std::map<NodeID, Path *> PathViaMap;
55 int cached_annotation;
98 std::vector<LinkGraphJob::EdgeAnnotation>::const_iterator
i;
99 std::vector<LinkGraphJob::EdgeAnnotation>::const_iterator
end;
115 this->i = this->job[node].edges.cbegin();
116 this->end = this->job[node].edges.cend();
125 return this->i != this->end ? (this->i++)->base.dest_node : INVALID_NODE;
140 FlowStat::SharesMap::const_iterator
it;
143 FlowStat::SharesMap::const_iterator
end;
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);
157 this->station_to_node[st] = i;
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();
185 if (this->it == this->end)
return INVALID_NODE;
186 return this->station_to_node[(this->it++)->second];
200 int free_cap, uint dist)
const
206 }
else if (this->
distance == UINT_MAX) {
234 int free_cap, uint dist)
const
238 if (min_cap == this_cap) {
243 return min_cap > this_cap;
256 template<
class Tannotation,
class Tedge_iterator>
259 typedef std::set<Tannotation *, typename Tannotation::Comparator> AnnoSet;
260 Tedge_iterator iter(this->
job);
261 uint16_t size = this->
job.
Size();
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();
270 while (!annos.empty()) {
271 typename AnnoSet::iterator i = annos.begin();
272 Tannotation *source = *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;
278 const Edge &edge = this->
job[from][to];
283 if (capacity == 0) capacity = 1;
294 uint distance_anno = express ? time : distance;
296 Tannotation *dest =
static_cast<Tannotation *
>(paths[to]);
297 if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance_anno)) {
299 dest->Fork(source, capacity, capacity - edge.Flow(), distance_anno);
300 dest->UpdateAnnotation();
314 Path *source = paths[source_id];
315 paths[source_id] =
nullptr;
316 for (PathVector::iterator i = paths.begin(); i != paths.end(); ++i) {
318 if (path ==
nullptr)
continue;
320 while (path != source && path !=
nullptr && path->
GetFlow() == 0) {
324 paths[path->
GetNode()] =
nullptr;
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);
362 uint flow = UINT_MAX;
363 const Path *cycle_end = cycle_begin;
365 flow = std::min(flow, cycle_begin->
GetFlow());
366 cycle_begin = path[cycle_begin->
GetNode()];
367 }
while (cycle_begin != cycle_end);
379 Path *cycle_end = cycle_begin;
381 NodeID prev = cycle_begin->
GetNode();
383 if (cycle_begin->
GetFlow() == 0) {
385 for (PathList::iterator i = node_paths.begin(); i != node_paths.end(); ++i) {
386 if (*i == cycle_begin) {
388 node_paths.push_back(cycle_begin);
393 cycle_begin = path[prev];
395 edge.RemoveFlow(flow);
396 }
while (cycle_begin != cycle_end);
410 Path *at_next_pos = path[next_id];
415 if (at_next_pos ==
nullptr) {
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;
430 Path *child = via_it->second;
438 paths.push_back(new_child);
446 for (PathViaMap::iterator via_it = next_hops.begin();
447 via_it != next_hops.end(); ++via_it) {
448 Path *child = via_it->second;
452 path[next_id] = child;
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) {
489 std::fill(path.begin(), path.end(), (
Path *)
nullptr);
505 std::vector<bool> finished_sources(size);
509 for (NodeID source = 0; source < size; ++source) {
510 if (finished_sources[source])
continue;
513 this->Dijkstra<DistanceAnnotation, GraphEdgeIterator>(source, paths);
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);
524 if (path->
GetFreeCapacity() > 0 && this->PushFlow(src_node, dest, path,
525 accuracy, this->max_saturation) > 0) {
528 more_loops = more_loops || (src_node.UnsatisfiedDemandTo(dest) > 0);
529 }
else if (src_node.UnsatisfiedDemandTo(dest) == src_node.DemandTo(dest) &&
531 this->
PushFlow(src_node, dest, path, accuracy, UINT_MAX);
533 if (src_node.UnsatisfiedDemandTo(dest) > 0) source_demand_left =
true;
536 finished_sources[source] = !source_demand_left;
553 bool demand_left =
true;
554 std::vector<bool> finished_sources(size);
557 for (NodeID source = 0; source < size; ++source) {
558 if (finished_sources[source])
continue;
560 this->Dijkstra<CapacityAnnotation, FlowEdgeIterator>(source, paths);
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) {
570 source_demand_left =
true;
574 finished_sources[source] = !source_demand_left;
591 template <
typename T>
592 bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
594 if (x_anno > y_anno)
return true;
595 if (x_anno < y_anno)
return false;
608 return x != y && Greater<int>(x->GetAnnotation(), y->GetAnnotation(),
609 x->GetNode(), y->GetNode());
621 return x != y && !Greater<uint>(x->GetAnnotation(), y->GetAnnotation(),
622 x->GetNode(), y->GetNode());
bool IsCargoInClass(CargoID c, CargoClass cc)
Does cargo c have cargo class cc?
@ CC_EXPRESS
Express cargo (Goods, Food, Candy, but also possible for passengers)
@ CC_PASSENGERS
Passengers.
Capacity-based annotation for use in the Dijkstra algorithm.
void UpdateAnnotation()
Update the cached annotation value.
int GetAnnotation() const
Return the actual value of the annotation, in this case the capacity.
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.
CapacityAnnotation(NodeID n, bool source=false)
Constructor.
Distance-based annotation for use in the Dijkstra algorithm.
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.
DistanceAnnotation(NodeID n, bool source=false)
Constructor.
uint GetAnnotation() const
Return the actual value of the annotation, in this case the distance.
void UpdateAnnotation()
Update the cached annotation value.
Iterator class for getting edges from a FlowStatMap.
FlowStat::SharesMap::const_iterator end
End of the shares map.
FlowStat::SharesMap::const_iterator it
Current iterator in the shares map.
std::vector< NodeID > station_to_node
Lookup table for getting NodeIDs from StationIDs.
void SetNode(NodeID source, NodeID node)
Setup the node to retrieve edges from.
FlowEdgeIterator(LinkGraphJob &job)
Constructor.
LinkGraphJob & job
Link graph job we're working with.
NodeID Next()
Get the next node for which a flow exists.
Flow descriptions by origin stations.
static const SharesMap empty_sharesmap
Static instance of FlowStat::SharesMap.
Iterator class for getting the edges in the order of their next_edge members.
LinkGraphJob & job
Job being executed.
std::vector< LinkGraphJob::EdgeAnnotation >::const_iterator end
Iterator pointing beyond last edge.
std::vector< LinkGraphJob::EdgeAnnotation >::const_iterator i
Iterator pointing to current edge.
GraphEdgeIterator(LinkGraphJob &job)
Construct a GraphEdgeIterator.
NodeID Next()
Retrieve the ID of the node the next edge points to.
void SetNode(NodeID, NodeID node)
Setup the node to start iterating at.
Class for calculation jobs to be run on link graphs.
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
bool IsJobAborted() const
Check if job has been aborted.
NodeID Size() const
Get the size of the underlying link graph.
CargoID Cargo() const
Get the cargo of the underlying link graph.
MCF1stPass(LinkGraphJob &job)
Run the first pass of the MCF calculation.
bool EliminateCycles()
Eliminate all cycles in the graph.
uint FindCycleFlow(const PathVector &path, const Path *cycle_begin)
Find the flow along a cycle including cycle_begin in path.
void EliminateCycle(PathVector &path, Path *cycle_begin, uint flow)
Eliminate a cycle of the given flow in the given set of paths.
MCF2ndPass(LinkGraphJob &job)
Run the second pass of the MCF calculation which assigns all remaining demands to existing paths.
Multi-commodity flow calculating base class.
void Dijkstra(NodeID from, PathVector &paths)
A slightly modified Dijkstra algorithm.
LinkGraphJob & job
Job we're working with.
uint max_saturation
Maximum saturation for edges.
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.
void CleanupPaths(NodeID source, PathVector &paths)
Clean up paths that lead nowhere and the root path.
A leg of a path in the link graph.
NodeID GetOrigin() const
Get the overall origin of the path.
Path * GetParent()
Get the parent leg of this one.
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
static Path * invalid_path
Static instance of an invalid path.
void Detach()
Detach this path from its parent.
int GetFreeCapacity() const
Get the free capacity of the path.
uint GetFlow() const
Get the flow on this leg.
uint distance
Sum(distance of all legs up to this one).
NodeID GetNode() const
Get the node this leg passes.
int GetCapacityRatio() const
Get capacity ratio of this path.
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
uint capacity
This capacity is min(capacity) fom all edges.
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
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,...
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
Relation that creates a weak order without duplicates.
Declaration of Multi-Commodity-Flow solver.
Comparator for std containers.
bool operator()(const CapacityAnnotation *x, const CapacityAnnotation *y) const
Compare two capacity annotations.
Comparator for std containers.
bool operator()(const DistanceAnnotation *x, const DistanceAnnotation *y) const
Compare two distance annotations.
uint8_t accuracy
accuracy when calculating things on the link graph. low accuracy => low running time
An edge in the link graph.
uint32_t TravelTime() const
Get edge's average travel time.
uint capacity
Capacity of the link.