(svn r25257) -Add: basic link graph (fonsinchen)

5 files changed, 827 insertions, 1 deletions

diff --git a/src/linkgraph/linkgraph.cpp b/src/linkgraph/linkgraph.cpp
new file mode 100644
index 000000000..dbaa02b41
--- /dev/null
+++ b/src/linkgraph/linkgraph.cpp
@@ -0,0 +1,254 @@
+/* $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.cpp Definition of link graph classes used for cargo distribution. */
+
+#include "../stdafx.h"
+#include "../core/pool_func.hpp"
+#include "linkgraph.h"
+
+/* Initialize the link-graph-pool */
+LinkGraphPool _link_graph_pool("LinkGraph");
+INSTANTIATE_POOL_METHODS(LinkGraph)
+
+/**
+ * Create a node or clear it.
+ * @param st ID of the associated station.
+ * @param demand Demand for cargo at the station.
+ */
+inline void LinkGraph::BaseNode::Init(StationID st, uint demand)
+{
+	this->supply = 0;
+	this->demand = demand;
+	this->station = st;
+	this->last_update = INVALID_DATE;
+}
+
+/**
+ * Create an edge.
+ * @param distance Length of the link as manhattan distance.
+ */
+inline void LinkGraph::BaseEdge::Init(uint distance)
+{
+	this->distance = distance;
+	this->capacity = 0;
+	this->usage = 0;
+	this->last_update = INVALID_DATE;
+	this->next_edge = INVALID_NODE;
+}
+
+void LinkGraph::Compress()
+{
+	this->last_compression = (_date + this->last_compression) / 2;
+	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
+		this->nodes[node1].supply /= 2;
+		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
+			BaseEdge &edge = this->edges[node1][node2];
+			if (edge.capacity > 0) {
+				edge.capacity = max(1U, edge.capacity / 2);
+				edge.usage /= 2;
+			}
+		}
+	}
+}
+
+/**
+ * Merge a link graph with another one.
+ * @param other LinkGraph to be merged into this one.
+ */
+void LinkGraph::Merge(LinkGraph *other)
+{
+	Date age = _date - this->last_compression + 1;
+	Date other_age = _date - other->last_compression + 1;
+	NodeID first = this->Size();
+	for (NodeID node1 = 0; node1 < other->Size(); ++node1) {
+		Station *st = Station::Get(other->nodes[node1].station);
+		NodeID new_node = this->AddNode(st);
+		this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);
+		st->goods[this->cargo].link_graph = this->index;
+		st->goods[this->cargo].node = new_node;
+		for (NodeID node2 = 0; node2 < node1; ++node2) {
+			BaseEdge &forward = this->edges[new_node][first + node2];
+			BaseEdge &backward = this->edges[first + node2][new_node];
+			forward = other->edges[node1][node2];
+			backward = other->edges[node2][node1];
+			forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age);
+			forward.usage = LinkGraph::Scale(forward.usage, age, other_age);
+			if (forward.next_edge != INVALID_NODE) forward.next_edge += first;
+			backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age);
+			backward.usage = LinkGraph::Scale(backward.usage, age, other_age);
+			if (backward.next_edge != INVALID_NODE) backward.next_edge += first;
+		}
+		BaseEdge &new_start = this->edges[new_node][new_node];
+		new_start = other->edges[node1][node1];
+		if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;
+	}
+	delete other;
+}
+
+/**
+ * Remove a node from the link graph by overwriting it with the last node.
+ * @param id ID of the node to be removed.
+ */
+void LinkGraph::RemoveNode(NodeID id)
+{
+	assert(id < this->Size());
+
+	NodeID last_node = this->Size() - 1;
+	for (NodeID i = 0; i <= last_node; ++i) {
+		(*this)[i].RemoveEdge(id);
+		BaseEdge *node_edges = this->edges[i];
+		NodeID prev = i;
+		NodeID next = node_edges[i].next_edge;
+		while (next != INVALID_NODE) {
+			if (next == last_node) {
+				node_edges[prev].next_edge = id;
+				break;
+			}
+			prev = next;
+			next = node_edges[prev].next_edge;
+		}
+		node_edges[id] = node_edges[last_node];
+	}
+	Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;
+	this->nodes.Erase(this->nodes.Get(id));
+	this->edges.EraseColumn(id);
+	/* Not doing EraseRow here, as having the extra invalid row doesn't hurt
+	 * and removing it would trigger a lot of memmove. The data has already
+	 * been copied around in the loop above. */
+}
+
+/**
+ * Add a node to the component and create empty edges associated with it. Set
+ * the station's last_component to this component. Calculate the distances to all
+ * other nodes. The distances to _all_ nodes are important as the demand
+ * calculator relies on their availability.
+ * @param st New node's station.
+ * @return New node's ID.
+ */
+NodeID LinkGraph::AddNode(const Station *st)
+{
+	const GoodsEntry &good = st->goods[this->cargo];
+
+	NodeID new_node = this->Size();
+	this->nodes.Append();
+	/* Avoid reducing the height of the matrix as that is expensive and we
+	 * most likely will increase it again later which is again expensive. */
+	this->edges.Resize(new_node + 1U,
+			max(new_node + 1U, this->edges.Height()));
+
+	this->nodes[new_node].Init(st->index,
+			HasBit(good.acceptance_pickup, GoodsEntry::GES_ACCEPTANCE));
+
+	BaseEdge *new_edges = this->edges[new_node];
+
+	/* Reset the first edge starting at the new node */
+	new_edges[new_node].next_edge = INVALID_NODE;
+
+	for (NodeID i = 0; i <= new_node; ++i) {
+		uint distance = DistanceManhattan(st->xy, Station::Get(this->nodes[i].station)->xy);
+		new_edges[i].Init(distance);
+		this->edges[i][new_node].Init(distance);
+	}
+	return new_node;
+}
+
+/**
+ * Fill an edge with values from a link.
+ * @param to Destination node of the link.
+ * @param capacity Capacity of the link.
+ */
+void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage)
+{
+	assert(this->index != to);
+	BaseEdge &edge = this->edges[to];
+	BaseEdge &first = this->edges[this->index];
+	edge.capacity = capacity;
+	edge.usage = usage == UINT_MAX ? 0 : usage;
+	edge.next_edge = first.next_edge;
+	first.next_edge = to;
+	edge.last_update = _date;
+}
+
+void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage)
+{
+	assert(capacity > 0);
+	assert(usage <= capacity || usage == UINT_MAX);
+	if (this->edges[to].last_update == INVALID_DATE) {
+		this->AddEdge(to, capacity, usage);
+	} else {
+		(*this)[to].Update(capacity, usage);
+	}
+}
+
+/**
+ * Remove an outgoing edge from this node.
+ * @param to ID of destination node.
+ */
+void LinkGraph::Node::RemoveEdge(NodeID to)
+{
+	if (this->index == to) return;
+	BaseEdge &edge = this->edges[to];
+	edge.capacity = 0;
+	edge.last_update = INVALID_DATE;
+	edge.usage = 0;
+
+	NodeID prev = this->index;
+	NodeID next = this->edges[this->index].next_edge;
+	while (next != INVALID_NODE) {
+		if (next == to) {
+			/* Will be removed, skip it. */
+			this->edges[prev].next_edge = edge.next_edge;
+			edge.next_edge = INVALID_NODE;
+			break;
+		} else {
+			prev = next;
+			next = this->edges[next].next_edge;
+		}
+	}
+}
+
+/**
+ * Create a new edge or update an existing one. If usage is UINT_MAX refresh
+ * the edge to have at least the given capacity, otherwise add the capacity.
+ * @param from Start node of the edge.
+ * @param to End node of the edge.
+ * @param capacity Capacity to be added/updated.
+ * @param usage Usage to be added or UINT_MAX.
+ */
+void LinkGraph::Edge::Update(uint capacity, uint usage)
+{
+	assert(this->edge.capacity > 0);
+	if (usage == UINT_MAX) {
+		this->edge.capacity = max(this->edge.capacity, capacity);
+	} else {
+		assert(capacity >= usage);
+		this->edge.capacity += capacity;
+		this->edge.usage += usage;
+	}
+	this->edge.last_update = _date;
+}
+
+/**
+ * Resize the component and fill it with empty nodes and edges. Used when
+ * loading from save games. The component is expected to be empty before.
+ * @param size New size of the component.
+ */
+void LinkGraph::Init(uint size)
+{
+	assert(this->Size() == 0);
+	this->edges.Resize(size, size);
+	this->nodes.Resize(size);
+
+	for (uint i = 0; i < size; ++i) {
+		this->nodes[i].Init();
+		BaseEdge *column = this->edges[i];
+		for (uint j = 0; j < size; ++j) column[j].Init();
+	}
+}
diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h
new file mode 100644
index 000000000..8dfe3f8ea
--- /dev/null
+++ b/src/linkgraph/linkgraph.h
@@ -0,0 +1,516 @@
+/* $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 classes used for cargo distribution. */
+
+#ifndef LINKGRAPH_H
+#define LINKGRAPH_H
+
+#include "../core/pool_type.hpp"
+#include "../core/smallmap_type.hpp"
+#include "../core/smallmatrix_type.hpp"
+#include "../station_base.h"
+#include "../cargotype.h"
+#include "../date_func.h"
+#include "linkgraph_type.h"
+
+struct SaveLoad;
+class LinkGraph;
+
+/**
+ * Type of the pool for link graph components. Each station can be in at up to
+ * 32 link graphs. So we allow for plenty of them to be created.
+ */
+typedef Pool<LinkGraph, LinkGraphID, 32, 0xFFFFFF> LinkGraphPool;
+/** The actual pool with link graphs. */
+extern LinkGraphPool _link_graph_pool;
+
+/**
+ * A connected component of a link graph. Contains a complete set of stations
+ * connected by links as nodes and edges. Each component also holds a copy of
+ * the link graph settings at the time of its creation. The global settings
+ * might change between the creation and join time so we can't rely on them.
+ */
+class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
+public:
+
+	/**
+	 * Node of the link graph. contains all relevant information from the associated
+	 * station. It's copied so that the link graph job can work on its own data set
+	 * in a separate thread.
+	 */
+	struct BaseNode {
+		uint supply;             ///< Supply at the station.
+		uint demand;             ///< Acceptance at the station.
+		StationID station;       ///< Station ID.
+		Date last_update;        ///< When the supply was last updated.
+		void Init(StationID st = INVALID_STATION, uint demand = 0);
+	};
+
+	/**
+	 * An edge in the link graph. Corresponds to a link between two stations or at
+	 * least the distance between them. Edges from one node to itself contain the
+	 * ID of the opposite Node of the first active edge (i.e. not just distance) in
+	 * the column as next_edge.
+	 */
+	struct BaseEdge {
+		uint distance;    ///< Length of the link.
+		uint capacity;    ///< Capacity of the link.
+		uint usage;       ///< Usage of the link.
+		Date last_update; ///< When the link was last updated.
+		NodeID next_edge; ///< Destination of next valid edge starting at the same source node.
+		void Init(uint distance = 0);
+	};
+
+	/**
+	 * Wrapper for an edge (const or not) allowing retrieval, but no modification.
+	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".
+	 */
+	template<typename Tedge>
+	class EdgeWrapper {
+	protected:
+		Tedge &edge; ///< Actual edge to be used.
+
+	public:
+
+		/**
+		 * Wrap a an edge.
+		 * @param edge Edge to be wrapped.
+		 */
+		EdgeWrapper (Tedge &edge) : edge(edge) {}
+
+		/**
+		 * Get edge's capacity.
+		 * @return Capacity.
+		 */
+		uint Capacity() const { return this->edge.capacity; }
+
+		/**
+		 * Get edge's usage.
+		 * @return Usage.
+		 */
+		uint Usage() const { return this->edge.usage; }
+
+		/**
+		 * Get edge's distance.
+		 * @return Distance.
+		 */
+		uint Distance() const { return this->edge.distance; }
+
+		/**
+		 * Get edge's last update.
+		 * @return Last update.
+		 */
+		Date LastUpdate() const { return this->edge.last_update; }
+	};
+
+	/**
+	 * Wrapper for a node (const or not) allowing retrieval, but no modification.
+	 * @tparam Tedge Actual node class, may be "const BaseNode" or just "BaseNode".
+	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".
+	 */
+	template<typename Tnode, typename Tedge>
+	class NodeWrapper {
+	protected:
+		Tnode &node;  ///< Node being wrapped.
+		Tedge *edges; ///< Outgoing edges for wrapped node.
+		NodeID index; ///< ID of wrapped node.
+
+	public:
+
+		/**
+		 * Wrap a node.
+		 * @param node Node to be wrapped.
+		 * @param edges Outgoing edges for node to be wrapped.
+		 * @param index ID of node to be wrapped.
+		 */
+		NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),
+			edges(edges), index(index) {}
+
+		/**
+		 * Get supply of wrapped node.
+		 * @return Supply.
+		 */
+		uint Supply() const { return this->node.supply; }
+
+		/**
+		 * Get demand of wrapped node.
+		 * @return Demand.
+		 */
+		uint Demand() const { return this->node.demand; }
+
+		/**
+		 * Get ID of station belonging to wrapped node.
+		 * @return ID of node's station.
+		 */
+		StationID Station() const { return this->node.station; }
+
+		/**
+		 * Get node's last update.
+		 * @return Last update.
+		 */
+		Date LastUpdate() const { return this->node.last_update; }
+	};
+
+	/**
+	 * Base class for iterating across outgoing edges of a node. Only the real
+	 * edges (those with capacity) are iterated. The ones with only distance
+	 * information are skipped.
+	 * @tparam Tedge Actual edge class. May be "BaseEdge" or "const BaseEdge".
+	 * @tparam Titer Actual iterator class.
+	 */
+	template <class Tedge, class Tedge_wrapper, class Titer>
+	class BaseEdgeIterator {
+	protected:
+		Tedge *base;    ///< Array of edges being iterated.
+		NodeID current; ///< Current offset in edges array.
+
+		/**
+		 * A "fake" pointer to enable operator-> on temporaries. As the objects
+		 * returned from operator* aren't references but real objects, we have
+		 * to return something that implements operator->, but isn't a pointer
+		 * from operator->. A fake pointer.
+		 */
+		class FakePointer : public SmallPair<NodeID, Tedge_wrapper> {
+		public:
+
+			/**
+			 * Construct a fake pointer from a pair of NodeID and edge.
+			 * @param pair Pair to be "pointed" to (in fact shallow-copied).
+			 */
+			FakePointer(const SmallPair<NodeID, Tedge_wrapper> &pair) : SmallPair<NodeID, Tedge_wrapper>(pair) {}
+
+			/**
+			 * Retrieve the pair by operator->.
+			 * @return Pair being "pointed" to.
+			 */
+			SmallPair<NodeID, Tedge_wrapper> *operator->() { return this; }
+		};
+
+	public:
+		/**
+		 * Constructor.
+		 * @param base Array of edges to be iterated.
+		 * @param current ID of current node (to locate the first edge).
+		 */
+		BaseEdgeIterator (Tedge *base, NodeID current) :
+			base(base),
+			current(current == INVALID_NODE ? current : base[current].next_edge)
+		{}
+
+		/**
+		 * Prefix-increment.
+		 * @return This.
+		 */
+		Titer &operator++()
+		{
+			this->current = this->base[this->current].next_edge;
+			return static_cast<Titer &>(*this);
+		}
+
+		/**
+		 * Postfix-increment.
+		 * @return Version of this before increment.
+		 */
+		Titer operator++(int)
+		{
+			Titer ret(static_cast<Titer &>(*this));
+			this->current = this->base[this->current].next_edge;
+			return ret;
+		}
+
+		/**
+		 * Compare with some other edge iterator. The other one may be of a
+		 * child class.
+		 * @tparam Tother Class of other iterator.
+		 * @param other Instance of other iterator.
+		 * @return If the iterators have the same edge array and current node.
+		 */
+		template<class Tother>
+		bool operator==(const Tother &other)
+		{
+			return this->base == other.base && this->current == other.current;
+		}
+
+		/**
+		 * Compare for inequality with some other edge iterator. The other one
+		 * may be of a child class.
+		 * @tparam Tother Class of other iterator.
+		 * @param other Instance of other iterator.
+		 * @return If either the edge arrays or the current nodes differ.
+		 */
+		template<class Tother>
+		bool operator!=(const Tother &other)
+		{
+			return this->base != other.base || this->current != other.current;
+		}
+
+		/**
+		 * Dereference with operator*.
+		 * @return Pair of current target NodeID and edge object.
+		 */
+		SmallPair<NodeID, Tedge_wrapper> operator*() const
+		{
+			return SmallPair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));
+		}
+
+		/**
+		 * Dereference with operator->.
+		 * @return Fake pointer to Pair of current target NodeID and edge object.
+		 */
+		FakePointer operator->() const {
+			return FakePointer(this->operator*());
+		}
+	};
+
+	/**
+	 * A constant edge class.
+	 */
+	typedef EdgeWrapper<const BaseEdge> ConstEdge;
+
+	/**
+	 * An updatable edge class.
+	 */
+	class Edge : public EdgeWrapper<BaseEdge> {
+	public:
+		/**
+		 * Constructor
+		 * @param edge Edge to be wrapped.
+		 */
+		Edge(BaseEdge &edge) : EdgeWrapper<BaseEdge>(edge) {}
+		void Update(uint capacity, uint usage);
+	};
+
+	/**
+	 * An iterator for const edges. Cannot be typedef'ed because of
+	 * template-reference to ConstEdgeIterator itself.
+	 */
+	class ConstEdgeIterator : public BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator> {
+	public:
+		/**
+		 * Constructor.
+		 * @param edges Array of edges to be iterated over.
+		 * @param current ID of current edge's end node.
+		 */
+		ConstEdgeIterator(const BaseEdge *edges, NodeID current) :
+			BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}
+	};
+
+	/**
+	 * An iterator for non-const edges. Cannot be typedef'ed because of
+	 * template-reference to EdgeIterator itself.
+	 */
+	class EdgeIterator : public BaseEdgeIterator<BaseEdge, Edge, EdgeIterator> {
+	public:
+		/**
+		 * Constructor.
+		 * @param edges Array of edges to be iterated over.
+		 * @param current ID of current edge's end node.
+		 */
+		EdgeIterator(BaseEdge *edges, NodeID current) :
+			BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}
+	};
+
+	/**
+	 * Constant node class. Only retrieval operations are allowed on both the
+	 * node itself and its edges.
+	 */
+	class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {
+	public:
+		/**
+		 * Constructor.
+		 * @param lg LinkGraph to get the node from.
+		 * @param node ID of the node.
+		 */
+		ConstNode(const LinkGraph *lg, NodeID node) :
+			NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)
+		{}
+
+		/**
+		 * Get a ConstEdge. This is not a reference as the wrapper objects are
+		 * not actually persistent.
+		 * @param to ID of end node of edge.
+		 * @return Constant edge wrapper.
+		 */
+		ConstEdge operator[](NodeID to) const { return ConstEdge(this->edges[to]); }
+
+		/**
+		 * Get an iterator pointing to the start of the edges array.
+		 * @return Constant edge iterator.
+		 */
+		ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->edges, this->index); }
+
+		/**
+		 * Get an iterator pointing beyond the end of the edges array.
+		 * @return Constant edge iterator.
+		 */
+		ConstEdgeIterator End() const { return ConstEdgeIterator(this->edges, INVALID_NODE); }
+	};
+
+	/**
+	 * Updatable node class. The node itself as well as its edges can be modified.
+	 */
+	class Node : public NodeWrapper<BaseNode, BaseEdge> {
+	public:
+		/**
+		 * Constructor.
+		 * @param lg LinkGraph to get the node from.
+		 * @param node ID of the node.
+		 */
+		Node(LinkGraph *lg, NodeID node) :
+			NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)
+		{}
+
+		/**
+		 * Get an Edge. This is not a reference as the wrapper objects are not
+		 * actually persistent.
+		 * @param to ID of end node of edge.
+		 * @return Edge wrapper.
+		 */
+		Edge operator[](NodeID to) { return Edge(this->edges[to]); }
+
+		/**
+		 * Get an iterator pointing to the start of the edges array.
+		 * @return Edge iterator.
+		 */
+		EdgeIterator Begin() { return EdgeIterator(this->edges, this->index); }
+
+		/**
+		 * Get an iterator pointing beyond the end of the edges array.
+		 * @return Constant edge iterator.
+		 */
+		EdgeIterator End() { return EdgeIterator(this->edges, INVALID_NODE); }
+
+		/**
+		 * Update the node's supply and set last_update to the current date.
+		 * @param supply Supply to be added.
+		 */
+		void UpdateSupply(uint supply)
+		{
+			this->node.supply += supply;
+			this->node.last_update = _date;
+		}
+
+		/**
+		 * Set the node's demand.
+		 * @param demand New demand for the node.
+		 */
+		void SetDemand(uint demand)
+		{
+			this->node.demand = demand;
+		}
+
+		void AddEdge(NodeID to, uint capacity, uint usage = 0);
+		void UpdateEdge(NodeID to, uint capacity, uint usage = 0);
+		void RemoveEdge(NodeID to);
+	};
+
+	typedef SmallVector<BaseNode, 16> NodeVector;
+	typedef SmallMatrix<BaseEdge> EdgeMatrix;
+
+	/** Minimum effective distance for timeout calculation. */
+	static const uint MIN_TIMEOUT_DISTANCE = 48;
+
+	/** Minimum number of days between subsequent compressions of a LG. */
+	static const uint COMPRESSION_INTERVAL = 256;
+
+	/**
+	 * Scale a value from a link graph of age orig_age for usage in one of age
+	 * target_age. Make sure that the value stays > 0 if it was > 0 before.
+	 * @param val Value to be scaled.
+	 * @param target_age Age of the target link graph.
+	 * @param orig_age Age of the original link graph.
+	 * @return scaled value.
+	 */
+	inline static uint Scale(uint val, uint target_age, uint orig_age)
+	{
+		return val > 0 ? max(1U, val * target_age / orig_age) : 0;
+	}
+
+	/** Bare constructor, only for save/load. */
+	LinkGraph() : cargo(INVALID_CARGO), last_compression(0) {}
+	/**
+	 * Real constructor.
+	 * @param cargo Cargo the link graph is about.
+	 */
+	LinkGraph(CargoID cargo) : cargo(cargo), last_compression(_date) {}
+
+	void Init(uint size);
+	void Compress();
+	void Merge(LinkGraph *other);
+
+	/* Splitting link graphs is intentionally not implemented.
+	 * The overhead in determining connectedness would probably outweigh the
+	 * benefit of having to deal with smaller graphs. In real world examples
+	 * networks generally grow. Only rarely a network is permanently split.
+	 * Reacting to temporary splits here would obviously create performance
+	 * problems and detecting the temporary or permanent nature of splits isn't
+	 * trivial. */
+
+	/**
+	 * Get a node with the specified id.
+	 * @param num ID of the node.
+	 * @return the Requested node.
+	 */
+	inline Node operator[](NodeID num) { return Node(this, num); }
+
+	/**
+	 * Get a const reference to a node with the specified id.
+	 * @param num ID of the node.
+	 * @return the Requested node.
+	 */
+	inline ConstNode operator[](NodeID num) const { return ConstNode(this, num); }
+
+	/**
+	 * Get the current size of the component.
+	 * @return Size.
+	 */
+	inline uint Size() const { return this->nodes.Length(); }
+
+	/**
+	 * Get date of last compression.
+	 * @return Date of last compression.
+	 */
+	inline Date LastCompression() const { return this->last_compression; }
+
+	/**
+	 * Get the cargo ID this component's link graph refers to.
+	 * @return Cargo ID.
+	 */
+	inline CargoID Cargo() const { return this->cargo; }
+
+	/**
+	 * Scale a value to its monthly equivalent, based on last compression.
+	 * @param base Value to be scaled.
+	 * @return Scaled value.
+	 */
+	inline uint Monthly(uint base) const
+	{
+		return base * 30 / (_date - this->last_compression + 1);
+	}
+
+	NodeID AddNode(const Station *st);
+	void RemoveNode(NodeID id);
+
+protected:
+	friend class LinkGraph::ConstNode;
+	friend class LinkGraph::Node;
+	friend const SaveLoad *GetLinkGraphDesc();
+	friend const SaveLoad *GetLinkGraphJobDesc();
+	friend void SaveLoad_LinkGraph(LinkGraph &lg);
+
+	CargoID cargo;         ///< Cargo of this component's link graph.
+	Date last_compression; ///< Last time the capacities and supplies were compressed.
+	NodeVector nodes;      ///< Nodes in the component.
+	EdgeMatrix edges;      ///< Edges in the component.
+};
+
+#define FOR_ALL_LINK_GRAPHS(var) FOR_ALL_ITEMS_FROM(LinkGraph, link_graph_index, var, 0)
+
+#endif /* LINKGRAPH_H */
diff --git a/src/linkgraph/linkgraph_base.h b/src/linkgraph/linkgraph_base.h
new file mode 100644
index 000000000..1878b1368
--- /dev/null
+++ b/src/linkgraph/linkgraph_base.h
@@ -0,0 +1,26 @@
+/* $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_base.h Some typedefs for the main game. */
+
+#ifndef LINKGRAPH_BASE_H
+#define LINKGRAPH_BASE_H
+
+#include "linkgraph.h"
+
+typedef LinkGraph::Node Node;
+typedef LinkGraph::Edge Edge;
+typedef LinkGraph::EdgeIterator EdgeIterator;
+
+typedef LinkGraph::ConstNode ConstNode;
+typedef LinkGraph::ConstEdge ConstEdge;
+typedef LinkGraph::ConstEdgeIterator ConstEdgeIterator;
+
+
+#endif /* LINKGRAPH_BASE_H */
diff --git a/src/linkgraph/linkgraph_type.h b/src/linkgraph/linkgraph_type.h
new file mode 100644
index 000000000..13411a707
--- /dev/null
+++ b/src/linkgraph/linkgraph_type.h
@@ -0,0 +1,24 @@
+/* $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_type.h Declaration of link graph types used for cargo distribution. */
+
+#ifndef LINKGRAPH_TYPE_H
+#define LINKGRAPH_TYPE_H
+
+typedef uint16 LinkGraphID;
+static const LinkGraphID INVALID_LINK_GRAPH = UINT16_MAX;
+
+typedef uint16 LinkGraphJobID;
+static const LinkGraphID INVALID_LIN_KGRAPH_JOB = UINT16_MAX;
+
+typedef uint16 NodeID;
+static const NodeID INVALID_NODE = UINT16_MAX;
+
+#endif /* LINKGRAPH_TYPE_H */
diff --git a/src/station_base.h b/src/station_base.h
index 322a7dc8e..7a3d3a885 100644
--- a/src/station_base.h
+++ b/src/station_base.h
@@ -16,6 +16,7 @@
 #include "newgrf_airport.h"
 #include "cargopacket.h"
 #include "industry_type.h"
+#include "linkgraph/linkgraph_type.h"
 #include "newgrf_storage.h"
 
 typedef Pool<BaseStation, StationID, 32, 64000> StationPool;
@@ -74,7 +75,9 @@ struct GoodsEntry {
 		time_since_pickup(255),
 		rating(INITIAL_STATION_RATING),
 		last_speed(0),
-		last_age(255)
+		last_age(255),
+		link_graph(INVALID_LINK_GRAPH),
+		node(INVALID_NODE)
 	{}
 
 	byte acceptance_pickup; ///< Status of this cargo, see #GoodsEntryStatus.
@@ -108,6 +111,9 @@ struct GoodsEntry {
 	byte amount_fract;      ///< Fractional part of the amount in the cargo list
 	StationCargoList cargo; ///< The cargo packets of cargo waiting in this station
 
+	LinkGraphID link_graph; ///< Link graph this station belongs to.
+	NodeID node;            ///< ID of node in link graph referring to this goods entry.
+
 	/**
 	 * Reports whether a vehicle has ever tried to load the cargo at this station.
 	 * This does not imply that there was cargo available for loading. Refer to GES_PICKUP for that.