summaryrefslogtreecommitdiff
path: root/src/linkgraph
diff options
context:
space:
mode:
authorfonsinchen <fonsinchen@openttd.org>2013-06-09 12:57:41 +0000
committerfonsinchen <fonsinchen@openttd.org>2013-06-09 12:57:41 +0000
commit22f56ffdd7b106b0fd080e1dc4adc957e1b356ea (patch)
tree477872c3fddd35ea741b211596fa7a91594bbf7b /src/linkgraph
parent33ad9774fb7c51f1ec706851c7a96a7ced5ff622 (diff)
downloadopenttd-22f56ffdd7b106b0fd080e1dc4adc957e1b356ea.tar.xz
(svn r25353) -Add: link graph job implementation
Diffstat (limited to 'src/linkgraph')
-rw-r--r--src/linkgraph/linkgraphjob.cpp185
-rw-r--r--src/linkgraph/linkgraphjob.h413
2 files changed, 598 insertions, 0 deletions
diff --git a/src/linkgraph/linkgraphjob.cpp b/src/linkgraph/linkgraphjob.cpp
new file mode 100644
index 000000000..fc94d49cc
--- /dev/null
+++ b/src/linkgraph/linkgraphjob.cpp
@@ -0,0 +1,185 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file linkgraphjob.cpp Definition of link graph job classes used for cargo distribution. */
+
+#include "../stdafx.h"
+#include "../core/pool_func.hpp"
+#include "../window_func.h"
+#include "linkgraphjob.h"
+
+/* Initialize the link-graph-job-pool */
+LinkGraphJobPool _link_graph_job_pool("LinkGraphJob");
+INSTANTIATE_POOL_METHODS(LinkGraphJob)
+
+/**
+ * Create a link graph job from a link graph. The link graph will be copied so
+ * that the calculations don't interfer with the normal operations on the
+ * original. The job is immediately started.
+ * @param orig Original LinkGraph to be copied.
+ */
+LinkGraphJob::LinkGraphJob(const LinkGraph &orig) :
+ /* Copying the link graph here also copies its index member.
+ * This is on purpose. */
+ link_graph(orig),
+ settings(_settings_game.linkgraph),
+ thread(NULL),
+ join_date(_date + _settings_game.linkgraph.recalc_time)
+{
+}
+
+/**
+ * Join the link graph job and destroy it.
+ */
+LinkGraphJob::~LinkGraphJob()
+{
+ assert(this->thread == NULL);
+
+ /* Link graph has been merged into another one. */
+ if (!LinkGraph::IsValidID(this->link_graph.index)) return;
+
+ uint size = this->Size();
+ for (NodeID node_id = 0; node_id < size; ++node_id) {
+ Node from = (*this)[node_id];
+
+ /* The station can have been deleted. */
+ Station *st = Station::GetIfValid(from.Station());
+ if (st == NULL) continue;
+
+ /* Link graph merging and station deletion may change around IDs. Make
+ * sure that everything is still consistent or ignore it otherwise. */
+ GoodsEntry &ge = st->goods[this->Cargo()];
+ if (ge.link_graph != this->link_graph.index || ge.node != node_id) continue;
+
+ LinkGraph *lg = LinkGraph::Get(ge.link_graph);
+ FlowStatMap &flows = from.Flows();
+
+ for (EdgeIterator it(from.Begin()); it != from.End(); ++it) {
+ if (from[it->first].Flow() == 0) continue;
+ StationID to = (*this)[it->first].Station();
+ Station *st2 = Station::GetIfValid(to);
+ if (st2 == NULL || st2->goods[this->Cargo()].link_graph != this->link_graph.index ||
+ st2->goods[this->Cargo()].node != it->first ||
+ (*lg)[node_id][it->first].LastUpdate() == INVALID_DATE) {
+ /* Edge has been removed. Delete flows. */
+ flows.DeleteFlows(to);
+ }
+ }
+
+ ge.flows.swap(flows);
+ InvalidateWindowData(WC_STATION_VIEW, st->index, this->Cargo());
+ }
+}
+
+/**
+ * Initialize the link graph job: Resize nodes and edges and populate them.
+ * This is done after the constructor so that we can do it in the calculation
+ * thread without delaying the main game.
+ */
+void LinkGraphJob::Init()
+{
+ uint size = this->Size();
+ this->nodes.Resize(size);
+ this->edges.Resize(size, size);
+ for (uint i = 0; i < size; ++i) {
+ this->nodes[i].Init(this->link_graph[i].Supply());
+ EdgeAnnotation *node_edges = this->edges[i];
+ for (uint j = 0; j < size; ++j) {
+ node_edges[j].Init();
+ }
+ }
+}
+
+/**
+ * Initialize a linkgraph job edge.
+ */
+void LinkGraphJob::EdgeAnnotation::Init()
+{
+ this->demand = 0;
+ this->flow = 0;
+ this->unsatisfied_demand = 0;
+}
+
+/**
+ * Initialize a Linkgraph job node. The underlying memory is expected to be
+ * freshly allocated, without any constructors having been called.
+ * @param supply Initial undelivered supply.
+ */
+void LinkGraphJob::NodeAnnotation::Init(uint supply)
+{
+ this->undelivered_supply = supply;
+ new (&this->flows) FlowStatMap;
+ new (&this->paths) PathList;
+}
+
+/**
+ * Add this path as a new child to the given base path, thus making this path
+ * a "fork" of the base path.
+ * @param base Path to fork from.
+ * @param cap Maximum capacity of the new leg.
+ * @param free_cap Remaining free capacity of the new leg.
+ * @param dist Distance of the new leg.
+ */
+void Path::Fork(Path *base, uint cap, int free_cap, uint dist)
+{
+ this->capacity = min(base->capacity, cap);
+ this->free_capacity = min(base->free_capacity, free_cap);
+ this->distance = base->distance + dist;
+ assert(this->distance > 0);
+ if (this->parent != base) {
+ this->Detach();
+ this->parent = base;
+ this->parent->num_children++;
+ }
+ this->origin = base->origin;
+}
+
+/**
+ * Push some flow along a path and register the path in the nodes it passes if
+ * successful.
+ * @param new_flow Amount of flow to push.
+ * @param job Link graph job this node belongs to.
+ * @param max_saturation Maximum saturation of edges.
+ * @return Amount of flow actually pushed.
+ */
+uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation)
+{
+ if (this->parent != NULL) {
+ LinkGraphJob::Edge edge = job[this->parent->node][this->node];
+ if (max_saturation != UINT_MAX) {
+ uint usable_cap = edge.Capacity() * max_saturation / 100;
+ if (usable_cap > edge.Flow()) {
+ new_flow = min(new_flow, usable_cap - edge.Flow());
+ } else {
+ return 0;
+ }
+ }
+ 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);
+ }
+ edge.AddFlow(new_flow);
+ }
+ this->flow += new_flow;
+ return new_flow;
+}
+
+/**
+ * Create a leg of a path in the link graph.
+ * @param n Id of the link graph node this path passes.
+ * @param source If true, this is the first leg of the path.
+ */
+Path::Path(NodeID n, bool source) :
+ distance(source ? 0 : UINT_MAX),
+ capacity(0),
+ free_capacity(source ? INT_MAX : INT_MIN),
+ flow(0), node(n), origin(source ? n : INVALID_NODE),
+ num_children(0), parent(NULL)
+{}
+
diff --git a/src/linkgraph/linkgraphjob.h b/src/linkgraph/linkgraphjob.h
new file mode 100644
index 000000000..f54270e6d
--- /dev/null
+++ b/src/linkgraph/linkgraphjob.h
@@ -0,0 +1,413 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file linkgraph.h Declaration of link graph job classes used for cargo distribution. */
+
+#ifndef LINKGRAPHJOB_H
+#define LINKGRAPHJOB_H
+
+#include "../thread/thread.h"
+#include "linkgraph.h"
+#include <list>
+
+class LinkGraphJob;
+class Path;
+typedef std::list<Path *> PathList;
+
+/** Type of the pool for link graph jobs. */
+typedef Pool<LinkGraphJob, LinkGraphJobID, 32, 0xFFFFFF> LinkGraphJobPool;
+/** The actual pool with link graph jobs. */
+extern LinkGraphJobPool _link_graph_job_pool;
+
+/**
+ * Class for calculation jobs to be run on link graphs.
+ */
+class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool>{
+private:
+ /**
+ * Annotation for a link graph edge.
+ */
+ struct EdgeAnnotation {
+ uint demand; ///< Transport demand between the nodes.
+ uint unsatisfied_demand; ///< Demand over this edge that hasn't been satisfied yet.
+ uint flow; ///< Planned flow over this edge.
+ void Init();
+ };
+
+ /**
+ * Annotation for a link graph node.
+ */
+ struct NodeAnnotation {
+ uint undelivered_supply; ///< Amount of supply that hasn't been distributed yet.
+ PathList paths; ///< Paths through this node.
+ FlowStatMap flows; ///< Planned flows to other nodes.
+ void Init(uint supply);
+ };
+
+ typedef SmallVector<NodeAnnotation, 16> NodeAnnotationVector;
+ typedef SmallMatrix<EdgeAnnotation> EdgeAnnotationMatrix;
+
+ friend const SaveLoad *GetLinkGraphJobDesc();
+ friend class LinkGraphSchedule;
+
+protected:
+ const LinkGraph link_graph; ///< Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
+ const LinkGraphSettings settings; ///< Copy of _settings_game.linkgraph at spawn time.
+ ThreadObject *thread; ///< Thread the job is running in or NULL if it's running in the main thread.
+ const Date join_date; ///< Date when the job is to be joined.
+ NodeAnnotationVector nodes; ///< Extra node data necessary for link graph calculation.
+ EdgeAnnotationMatrix edges; ///< Extra edge data necessary for link graph calculation.
+
+public:
+
+ /**
+ * A job edge. Wraps a link graph edge and an edge annotation. The
+ * annotation can be modified, the edge is constant.
+ */
+ class Edge : public LinkGraph::ConstEdge {
+ private:
+ EdgeAnnotation &anno; ///< Annotation being wrapped.
+ public:
+ /**
+ * Constructor.
+ * @param edge Link graph edge to be wrapped.
+ * @param anno Annotation to be wrapped.
+ */
+ Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno) :
+ LinkGraph::ConstEdge(edge), anno(anno) {}
+
+ /**
+ * Get the transport demand between end the points of the edge.
+ * @return Demand.
+ */
+ uint Demand() const { return this->anno.demand; }
+
+ /**
+ * Get the transport demand that hasn't been satisfied by flows, yet.
+ * @return Unsatisfied demand.
+ */
+ uint UnsatisfiedDemand() const { return this->anno.unsatisfied_demand; }
+
+ /**
+ * Get the total flow on the edge.
+ * @return Flow.
+ */
+ uint Flow() const { return this->anno.flow; }
+
+ /**
+ * Add some flow.
+ * @param flow Flow to be added.
+ */
+ void AddFlow(uint flow) { this->anno.flow += flow; }
+
+ /**
+ * Remove some flow.
+ * @param flow Flow to be removed.
+ */
+ void RemoveFlow(uint flow)
+ {
+ assert(flow <= this->anno.flow);
+ this->anno.flow -= flow;
+ }
+
+ /**
+ * Add some (not yet satisfied) demand.
+ * @param demand Demand to be added.
+ */
+ void AddDemand(uint demand)
+ {
+ this->anno.demand += demand;
+ this->anno.unsatisfied_demand += demand;
+ }
+
+ /**
+ * Satisfy some demand.
+ * @param demand Demand to be satisfied.
+ */
+ void SatisfyDemand(uint demand)
+ {
+ assert(demand <= this->anno.unsatisfied_demand);
+ this->anno.unsatisfied_demand -= demand;
+ }
+ };
+
+ /**
+ * Iterator for job edges.
+ */
+ class EdgeIterator : public LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator> {
+ EdgeAnnotation *base_anno; ///< Array of annotations to be (indirectly) iterated.
+ public:
+ /**
+ * Constructor.
+ * @param base Array of edges to be iterated.
+ * @param base_anno Array of annotations to be iterated.
+ * @param current Start offset of iteration.
+ */
+ EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current) :
+ LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, current),
+ base_anno(base_anno) {}
+
+ /**
+ * Dereference.
+ * @return Pair of the edge currently pointed to and the ID of its
+ * other end.
+ */
+ SmallPair<NodeID, Edge> operator*() const
+ {
+ return SmallPair<NodeID, Edge>(this->current, Edge(this->base[this->current], this->base_anno[this->current]));
+ }
+
+ /**
+ * Dereference. Has to be repeated here as operator* is different than
+ * in LinkGraph::EdgeWrapper.
+ * @return Fake pointer to pair of NodeID/Edge.
+ */
+ FakePointer operator->() const {
+ return FakePointer(this->operator*());
+ }
+ };
+
+ /**
+ * Link graph job node. Wraps a constant link graph node and a modifiable
+ * node annotation.
+ */
+ class Node : public LinkGraph::ConstNode {
+ private:
+ NodeAnnotation &node_anno; ///< Annotation being wrapped.
+ EdgeAnnotation *edge_annos; ///< Edge annotations belonging to this node.
+ public:
+
+ /**
+ * Constructor.
+ * @param lgj Job to take the node from.
+ * @param node ID of the node.
+ */
+ Node (LinkGraphJob *lgj, NodeID node) :
+ LinkGraph::ConstNode(&lgj->link_graph, node),
+ node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node])
+ {}
+
+ /**
+ * Retrieve an edge starting at this node. Mind that this returns an
+ * object, not a reference.
+ * @param to Remote end of the edge.
+ * @return Edge between this node and "to".
+ */
+ Edge operator[](NodeID to) const { return Edge(this->edges[to], this->edge_annos[to]); }
+
+ /**
+ * Iterator for the "begin" of the edge array. Only edges with capacity
+ * are iterated. The others are skipped.
+ * @return Iterator pointing to the first edge.
+ */
+ EdgeIterator Begin() const { return EdgeIterator(this->edges, this->edge_annos, index); }
+
+ /**
+ * Iterator for the "end" of the edge array. Only edges with capacity
+ * are iterated. The others are skipped.
+ * @return Iterator pointing beyond the last edge.
+ */
+ EdgeIterator End() const { return EdgeIterator(this->edges, this->edge_annos, INVALID_NODE); }
+
+ /**
+ * Get amount of supply that hasn't been delivered, yet.
+ * @return Undelivered supply.
+ */
+ uint UndeliveredSupply() const { return this->node_anno.undelivered_supply; }
+
+ /**
+ * Get the flows running through this node.
+ * @return Flows.
+ */
+ FlowStatMap &Flows() { return this->node_anno.flows; }
+
+ /**
+ * Get a constant version of the flows running through this node.
+ * @return Flows.
+ */
+ const FlowStatMap &Flows() const { return this->node_anno.flows; }
+
+ /**
+ * Get the paths this node is part of.
+ * @return Paths.
+ */
+ PathList &Paths() { return this->node_anno.paths; }
+
+ /**
+ * Get a constant version of the paths this node is part of.
+ * @return Paths.
+ */
+ const PathList &Paths() const { return this->node_anno.paths; }
+
+ /**
+ * Deliver some supply, adding demand to the respective edge.
+ * @param to Destination for supply.
+ * @param amount Amount of supply to be delivered.
+ */
+ void DeliverSupply(NodeID to, uint amount)
+ {
+ this->node_anno.undelivered_supply -= amount;
+ (*this)[to].AddDemand(amount);
+ }
+ };
+
+ /**
+ * Bare constructor, only for save/load. link_graph, join_date and actually
+ * settings have to be brutally const-casted in order to populate them.
+ */
+ LinkGraphJob() : settings(_settings_game.linkgraph), thread(NULL),
+ join_date(INVALID_DATE) {}
+
+ LinkGraphJob(const LinkGraph &orig);
+ ~LinkGraphJob();
+
+ void Init();
+
+ /**
+ * Check if job is supposed to be finished.
+ * @return True if job should be finished by now, false if not.
+ */
+ inline bool IsFinished() const { return this->join_date <= _date; }
+
+ /**
+ * Get the date when the job should be finished.
+ * @return Join date.
+ */
+ inline Date JoinDate() const { return join_date; }
+
+ /**
+ * Get the link graph settings for this component.
+ * @return Settings.
+ */
+ inline const LinkGraphSettings &Settings() const { return this->settings; }
+
+ /**
+ * Get a node abstraction with the specified id.
+ * @param num ID of the node.
+ * @return the Requested node.
+ */
+ inline Node operator[](NodeID num) { return Node(this, num); }
+
+ /**
+ * Get the size of the underlying link graph.
+ * @return Size.
+ */
+ inline uint Size() const { return this->link_graph.Size(); }
+
+ /**
+ * Get the cargo of the underlying link graph.
+ * @return Cargo.
+ */
+ inline CargoID Cargo() const { return this->link_graph.Cargo(); }
+
+ /**
+ * Get the date when the underlying link graph was last compressed.
+ * @return Compression date.
+ */
+ inline Date LastCompression() const { return this->link_graph.LastCompression(); }
+
+ /**
+ * Get the ID of the underlying link graph.
+ * @return Link graph ID.
+ */
+ inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }
+
+ /**
+ * Get a reference to the underlying link graph. Only use this for save/load.
+ * @return Link graph.
+ */
+ inline const LinkGraph &Graph() const { return this->link_graph; }
+};
+
+#define FOR_ALL_LINK_GRAPH_JOBS(var) FOR_ALL_ITEMS_FROM(LinkGraphJob, link_graph_job_index, var, 0)
+
+/**
+ * A leg of a path in the link graph. Paths can form trees by being "forked".
+ */
+class Path {
+public:
+ Path(NodeID n, bool source = false);
+
+ /** Get the node this leg passes. */
+ inline NodeID GetNode() const { return this->node; }
+
+ /** Get the overall origin of the path. */
+ inline NodeID GetOrigin() const { return this->origin; }
+
+ /** Get the parent leg of this one. */
+ inline Path *GetParent() { return this->parent; }
+
+ /** Get the overall capacity of the path. */
+ inline uint GetCapacity() const { return this->capacity; }
+
+ /** Get the free capacity of the path. */
+ inline int GetFreeCapacity() const { return this->free_capacity; }
+
+ /**
+ * Get ratio of free * 16 (so that we get fewer 0) /
+ * total capacity + 1 (so that we don't divide by 0).
+ * @param free Free capacity.
+ * @param total Total capacity.
+ * @return free * 16 / (total + 1).
+ */
+ inline static int GetCapacityRatio(int free, int total)
+ {
+ return (free << 4) / (total + 1);
+ }
+
+ /**
+ * Get capacity ratio of this path.
+ * @return free capacity * 16 / (total capacity + 1).
+ */
+ inline int GetCapacityRatio() const
+ {
+ return Path::GetCapacityRatio(this->free_capacity, this->capacity);
+ }
+
+ /** Get the overall distance of the path. */
+ inline uint GetDistance() const { return this->distance; }
+
+ /** Reduce the flow on this leg only by the specified amount. */
+ inline void ReduceFlow(uint f) { this->flow -= f; }
+
+ /** Increase the flow on this leg only by the specified amount. */
+ inline void AddFlow(uint f) { this->flow += f; }
+
+ /** Get the flow on this leg. */
+ inline uint GetFlow() const { return this->flow; }
+
+ /** Get the number of "forked off" child legs of this one. */
+ inline uint GetNumChildren() const { return this->num_children; }
+
+ /**
+ * Detach this path from its parent.
+ */
+ inline void Detach()
+ {
+ if (this->parent != NULL) {
+ this->parent->num_children--;
+ this->parent = NULL;
+ }
+ }
+
+ uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
+ void Fork(Path *base, uint cap, int free_cap, uint dist);
+
+protected:
+ uint distance; ///< Sum(distance of all legs up to this one).
+ uint capacity; ///< This capacity is min(capacity) fom all edges.
+ int free_capacity; ///< This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
+ uint flow; ///< Flow the current run of the mcf solver assigns.
+ NodeID node; ///< Link graph node this leg passes.
+ NodeID origin; ///< Link graph node this path originates from.
+ uint num_children; ///< Number of child legs that have been forked from this path.
+ Path *parent; ///< Parent leg of this one.
+};
+
+#endif /* LINKGRAPHJOB_H */