From 06313e49812b534d1c16ce5376f39081519b0aef Mon Sep 17 00:00:00 2001 From: rubidium Date: Sun, 19 May 2013 14:11:20 +0000 Subject: (svn r25257) -Add: basic link graph (fonsinchen) --- src/linkgraph/linkgraph.cpp | 254 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 254 insertions(+) create mode 100644 src/linkgraph/linkgraph.cpp (limited to 'src/linkgraph/linkgraph.cpp') 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 . + */ + +/** @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(); + } +} -- cgit v1.2.3-54-g00ecf