summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorfonsinchen <fonsinchen@openttd.org>2013-10-19 17:15:19 +0000
committerfonsinchen <fonsinchen@openttd.org>2013-10-19 17:15:19 +0000
commitb3b460cae294ccf31b013fbd8d198939afb6abef (patch)
tree4ef819c1038ed58629f48c88dc0f920947fd1b3a
parentc08259fe9266e41aa5ce0bc89ad49f113c436b53 (diff)
downloadopenttd-b3b460cae294ccf31b013fbd8d198939afb6abef.tar.xz
(svn r25885) -Codechange: Keep paths sorted so that the ones with flow == 0 are in the back and don't have to be iterated over so often.
-rw-r--r--src/linkgraph/flowmapper.cpp2
-rw-r--r--src/linkgraph/linkgraphjob.cpp2
-rw-r--r--src/linkgraph/linkgraphjob.h5
-rw-r--r--src/linkgraph/mcf.cpp26
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;