diff options
| -rw-r--r-- | src/linkgraph/mcf.cpp | 17 |
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); } } |