diff options
| -rw-r--r-- | src/linkgraph/flowmapper.cpp | 2 | ||||
| -rw-r--r-- | src/linkgraph/linkgraphjob.cpp | 2 | ||||
| -rw-r--r-- | src/linkgraph/linkgraphjob.h | 5 | ||||
| -rw-r--r-- | src/linkgraph/mcf.cpp | 26 |
4 files changed, 28 insertions, 7 deletions
diff --git a/src/linkgraph/flowmapper.cpp b/src/linkgraph/flowmapper.cpp index 70779e8ec..b9aa9cd59 100644 --- a/src/linkgraph/flowmapper.cpp +++ b/src/linkgraph/flowmapper.cpp @@ -28,7 +28,7 @@ void FlowMapper::Run(LinkGraphJob &job) const for (PathList::iterator i = paths.begin(); i != paths.end(); ++i) { Path *path = *i; uint flow = path->GetFlow(); - if (flow == 0) continue; + if (flow == 0) break; /* compress to monthly value */ flow = max(1U, flow * 30 / runtime); Node node = job[path->GetNode()]; diff --git a/src/linkgraph/linkgraphjob.cpp b/src/linkgraph/linkgraphjob.cpp index dcdc7ba36..242689e8d 100644 --- a/src/linkgraph/linkgraphjob.cpp +++ b/src/linkgraph/linkgraphjob.cpp @@ -181,7 +181,7 @@ uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation) } new_flow = this->parent->AddFlow(new_flow, job, max_saturation); if (this->flow == 0 && new_flow > 0) { - job[this->parent->node].Paths().push_back(this); + job[this->parent->node].Paths().push_front(this); } edge.AddFlow(new_flow); } diff --git a/src/linkgraph/linkgraphjob.h b/src/linkgraph/linkgraphjob.h index 79231c754..66aff3672 100644 --- a/src/linkgraph/linkgraphjob.h +++ b/src/linkgraph/linkgraphjob.h @@ -45,7 +45,7 @@ private: */ struct NodeAnnotation { uint undelivered_supply; ///< Amount of supply that hasn't been distributed yet. - PathList paths; ///< Paths through this node. + PathList paths; ///< Paths through this node, sorted so that those with flow == 0 are in the back. FlowStatMap flows; ///< Planned flows to other nodes. void Init(uint supply); }; @@ -234,7 +234,8 @@ public: const FlowStatMap &Flows() const { return this->node_anno.flows; } /** - * Get the paths this node is part of. + * Get the paths this node is part of. Paths are always expected to be + * sorted so that those with flow == 0 are in the back of the list. * @return Paths. */ PathList &Paths() { return this->node_anno.paths; } diff --git a/src/linkgraph/mcf.cpp b/src/linkgraph/mcf.cpp index d07f147b2..af9f6ce5f 100644 --- a/src/linkgraph/mcf.cpp +++ b/src/linkgraph/mcf.cpp @@ -351,7 +351,17 @@ void MCF1stPass::EliminateCycle(PathVector &path, Path *cycle_begin, uint flow) do { NodeID prev = cycle_begin->GetNode(); cycle_begin->ReduceFlow(flow); - cycle_begin = path[cycle_begin->GetNode()]; + if (cycle_begin->GetFlow() == 0) { + PathList &node_paths = this->job[cycle_begin->GetParent()->GetNode()].Paths(); + for (PathList::iterator i = node_paths.begin(); i != node_paths.end(); ++i) { + if (*i == cycle_begin) { + node_paths.erase(i); + node_paths.push_back(cycle_begin); + break; + } + } + } + cycle_begin = path[prev]; Edge edge = this->job[prev][cycle_begin->GetNode()]; edge.RemoveFlow(flow); } while (cycle_begin != cycle_end); @@ -379,18 +389,28 @@ bool MCF1stPass::EliminateCycles(PathVector &path, NodeID origin_id, NodeID next * in one path each. */ PathList &paths = this->job[next_id].Paths(); PathViaMap next_hops; - for (PathList::iterator i = paths.begin(); i != paths.end(); ++i) { + for (PathList::iterator i = paths.begin(); i != paths.end();) { Path *new_child = *i; + uint new_flow = new_child->GetFlow(); + if (new_flow == 0) break; if (new_child->GetOrigin() == origin_id) { PathViaMap::iterator via_it = next_hops.find(new_child->GetNode()); if (via_it == next_hops.end()) { next_hops[new_child->GetNode()] = new_child; + ++i; } else { Path *child = via_it->second; - uint new_flow = new_child->GetFlow(); child->AddFlow(new_flow); new_child->ReduceFlow(new_flow); + + /* We might hit end() with with the ++ here and skip the + * newly push_back'ed path. That's good as the flow of that + * path is 0 anyway. */ + paths.erase(i++); + paths.push_back(new_child); } + } else { + ++i; } } bool found = false; |