summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorJonathan G Rennison <j.g.rennison@gmail.com>2019-10-06 17:02:38 +0100
committerNiels Martin Hansen <nielsm@indvikleren.dk>2020-01-08 22:49:53 +0100
commit6e7117e04c740be951a3dcc81aeda716569fa013 (patch)
tree8beca11c11790ecadf36c282bb6024c8d26c8b6e /src
parent190e074287c76a9332ab1e3632aff037a6d09675 (diff)
downloadopenttd-6e7117e04c740be951a3dcc81aeda716569fa013.tar.xz
Codechange: [Linkgraph] Skip MCF source node Dijkstra when all demand satisfied
MCF Dijkstra iterations are executed for all source nodes in a round-robin order. Source nodes typically require different numbers of MCF Dijkstra iterations to satisfy all of their demand. This change is to avoid performing MCF Dijkstra iterations on source nodes which have already been fully satisfied.
Diffstat (limited to 'src')
-rw-r--r--src/linkgraph/mcf.cpp17
1 files changed, 16 insertions, 1 deletions
diff --git a/src/linkgraph/mcf.cpp b/src/linkgraph/mcf.cpp
index c64674237..c8c031ea3 100644
--- a/src/linkgraph/mcf.cpp
+++ b/src/linkgraph/mcf.cpp
@@ -494,13 +494,17 @@ MCF1stPass::MCF1stPass(LinkGraphJob &job) : MultiCommodityFlow(job)
uint size = job.Size();
uint accuracy = job.Settings().accuracy;
bool more_loops;
+ std::vector<bool> finished_sources(size);
do {
more_loops = false;
for (NodeID source = 0; source < size; ++source) {
+ if (finished_sources[source]) continue;
+
/* First saturate the shortest paths. */
this->Dijkstra<DistanceAnnotation, GraphEdgeIterator>(source, paths);
+ bool source_demand_left = false;
for (NodeID dest = 0; dest < size; ++dest) {
Edge edge = job[source][dest];
if (edge.UnsatisfiedDemand() > 0) {
@@ -518,8 +522,10 @@ MCF1stPass::MCF1stPass(LinkGraphJob &job) : MultiCommodityFlow(job)
path->GetFreeCapacity() > INT_MIN) {
this->PushFlow(edge, path, accuracy, UINT_MAX);
}
+ if (edge.UnsatisfiedDemand() > 0) source_demand_left = true;
}
}
+ finished_sources[source] = !source_demand_left;
this->CleanupPaths(source, paths);
}
} while (more_loops || this->EliminateCycles());
@@ -537,18 +543,27 @@ MCF2ndPass::MCF2ndPass(LinkGraphJob &job) : MultiCommodityFlow(job)
uint size = job.Size();
uint accuracy = job.Settings().accuracy;
bool demand_left = true;
+ std::vector<bool> finished_sources(size);
while (demand_left) {
demand_left = false;
for (NodeID source = 0; source < size; ++source) {
+ if (finished_sources[source]) continue;
+
this->Dijkstra<CapacityAnnotation, FlowEdgeIterator>(source, paths);
+
+ bool source_demand_left = false;
for (NodeID dest = 0; dest < size; ++dest) {
Edge edge = this->job[source][dest];
Path *path = paths[dest];
if (edge.UnsatisfiedDemand() > 0 && path->GetFreeCapacity() > INT_MIN) {
this->PushFlow(edge, path, accuracy, UINT_MAX);
- if (edge.UnsatisfiedDemand() > 0) demand_left = true;
+ if (edge.UnsatisfiedDemand() > 0) {
+ demand_left = true;
+ source_demand_left = true;
+ }
}
}
+ finished_sources[source] = !source_demand_left;
this->CleanupPaths(source, paths);
}
}