(svn r25353) -Add: link graph job implementation

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 */