cpp/openttd-patchpack/source Changeset - r24041:9b1ea5c01558

Changeset - r24041:9b1ea5c01558

Parent rev.

Child rev.

[Not reviewed]

master

0 1 0

Jonathan G Rennison - 5 years ago 2019-10-06 16:02:38
j.g.rennison@gmail.com

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.

1 file changed with 16 insertions and 1 deletions:

src/linkgraph/mcf.cpp

0 comments (0 inline, 0 general)

src/linkgraph/mcf.cpp

➞

Show inline comments

@@ @@ -491,19 +491,23 @@ bool MCF1stPass::EliminateCycles() @@
 MCF1stPass::MCF1stPass(LinkGraphJob &job) : MultiCommodityFlow(job)
+{
 	PathVector paths;
 	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) {
 					Path *path = paths[dest];
 					assert(path != nullptr);
 					/* Generally only allow paths that don't exceed the
@@ @@ -515,14 +519,16 @@ MCF1stPass::MCF1stPass(LinkGraphJob &job @@
 						 * find more. */
 						more_loops = more_loops || (edge.UnsatisfiedDemand() > 0);
 					} else if (edge.UnsatisfiedDemand() == edge.Demand() &&
 							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());
+}
 /**
@@ @@ -534,24 +540,33 @@ MCF2ndPass::MCF2ndPass(LinkGraphJob &job @@
+{
 	this->max_saturation = UINT_MAX; // disable artificial cap on saturation
 	PathVector paths;
 	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);
+		}
+	}
+}
 /**

0 comments (0 inline, 0 general)