4 #include "../core/math_func.hpp"
8 #include "../safeguards.h"
10 typedef std::map<NodeID, Path *> PathViaMap;
55 int cached_annotation;
107 i(nullptr, nullptr, INVALID_NODE),
end(nullptr, nullptr, INVALID_NODE)
117 this->i = this->job[node].Begin();
118 this->end = this->job[node].End();
127 return this->i != this->end ? (this->i++)->first : INVALID_NODE;
142 FlowStat::SharesMap::const_iterator
it;
145 FlowStat::SharesMap::const_iterator
end;
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);
159 this->station_to_node[st] = i;
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();
187 if (this->it == this->end)
return INVALID_NODE;
188 return this->station_to_node[(this->it++)->second];
202 int free_cap, uint dist)
const
208 }
else if (this->
distance == UINT_MAX) {
236 int free_cap, uint dist)
const
240 if (min_cap == this_cap) {
245 return min_cap > this_cap;
258 template<
class Tannotation,
class Tedge_iterator>
261 typedef std::set<Tannotation *, typename Tannotation::Comparator> AnnoSet;
262 Tedge_iterator iter(this->
job);
263 uint16 size = this->
job.
Size();
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();
272 while (!annos.empty()) {
273 typename AnnoSet::iterator i = annos.begin();
274 Tannotation *source = *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;
280 Edge edge = this->
job[from][to];
285 if (capacity == 0) capacity = 1;
296 uint distance_anno = express ? time : distance;
298 Tannotation *dest =
static_cast<Tannotation *
>(paths[to]);
299 if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance_anno)) {
301 dest->Fork(source, capacity, capacity - edge.Flow(), distance_anno);
302 dest->UpdateAnnotation();
316 Path *source = paths[source_id];
317 paths[source_id] =
nullptr;
318 for (PathVector::iterator i = paths.begin(); i != paths.end(); ++i) {
320 if (path ==
nullptr)
continue;
322 while (path != source && path !=
nullptr && path->
GetFlow() == 0) {
326 paths[path->
GetNode()] =
nullptr;
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);
363 uint flow = UINT_MAX;
364 const Path *cycle_end = cycle_begin;
366 flow = std::min(flow, cycle_begin->
GetFlow());
367 cycle_begin = path[cycle_begin->
GetNode()];
368 }
while (cycle_begin != cycle_end);
380 Path *cycle_end = cycle_begin;
382 NodeID prev = cycle_begin->
GetNode();
384 if (cycle_begin->
GetFlow() == 0) {
386 for (PathList::iterator i = node_paths.begin(); i != node_paths.end(); ++i) {
387 if (*i == cycle_begin) {
389 node_paths.push_back(cycle_begin);
394 cycle_begin = path[prev];
396 edge.RemoveFlow(flow);
397 }
while (cycle_begin != cycle_end);
411 Path *at_next_pos = path[next_id];
416 if (at_next_pos ==
nullptr) {
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;
431 Path *child = via_it->second;
439 paths.push_back(new_child);
447 for (PathViaMap::iterator via_it = next_hops.begin();
448 via_it != next_hops.end(); ++via_it) {
449 Path *child = via_it->second;
453 path[next_id] = child;
484 bool cycles_found =
false;
485 uint16 size = this->
job.
Size();
486 PathVector path(size,
nullptr);
487 for (NodeID node = 0; node < size; ++node) {
490 std::fill(path.begin(), path.end(), (
Path *)
nullptr);
506 std::vector<bool> finished_sources(size);
510 for (NodeID source = 0; source < size; ++source) {
511 if (finished_sources[source])
continue;
514 this->Dijkstra<DistanceAnnotation, GraphEdgeIterator>(source, paths);
516 bool source_demand_left =
false;
517 for (NodeID dest = 0; dest < size; ++dest) {
519 if (edge.UnsatisfiedDemand() > 0) {
520 Path *path = paths[dest];
521 assert(path !=
nullptr);
526 accuracy, this->max_saturation) > 0) {
529 more_loops = more_loops || (edge.UnsatisfiedDemand() > 0);
530 }
else if (edge.UnsatisfiedDemand() == edge.Demand() &&
532 this->
PushFlow(edge, path, accuracy, UINT_MAX);
534 if (edge.UnsatisfiedDemand() > 0) source_demand_left =
true;
537 finished_sources[source] = !source_demand_left;
554 bool demand_left =
true;
555 std::vector<bool> finished_sources(size);
558 for (NodeID source = 0; source < size; ++source) {
559 if (finished_sources[source])
continue;
561 this->Dijkstra<CapacityAnnotation, FlowEdgeIterator>(source, paths);
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) {
571 source_demand_left =
true;
575 finished_sources[source] = !source_demand_left;
592 template <
typename T>
593 bool Greater(T x_anno, T y_anno, NodeID x, NodeID y)
595 if (x_anno > y_anno)
return true;
596 if (x_anno < y_anno)
return false;
609 return x != y && Greater<int>(x->GetAnnotation(), y->GetAnnotation(),
610 x->GetNode(), y->GetNode());
622 return x != y && !Greater<uint>(x->GetAnnotation(), y->GetAnnotation(),
623 x->GetNode(), y->GetNode());