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());