OpenTTD
linkgraph.cpp
Go to the documentation of this file.
1 /* $Id: linkgraph.cpp 26646 2014-06-14 13:35:39Z fonsinchen $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #include "../stdafx.h"
13 #include "../core/pool_func.hpp"
14 #include "linkgraph.h"
15 
16 #include "../safeguards.h"
17 
18 /* Initialize the link-graph-pool */
19 LinkGraphPool _link_graph_pool("LinkGraph");
21 
22 
28 inline void LinkGraph::BaseNode::Init(TileIndex xy, StationID st, uint demand)
29 {
30  this->xy = xy;
31  this->supply = 0;
32  this->demand = demand;
33  this->station = st;
34  this->last_update = INVALID_DATE;
35 }
36 
41 {
42  this->capacity = 0;
43  this->usage = 0;
46  this->next_edge = INVALID_NODE;
47 }
48 
54 void LinkGraph::ShiftDates(int interval)
55 {
56  this->last_compression += interval;
57  for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
58  BaseNode &source = this->nodes[node1];
59  if (source.last_update != INVALID_DATE) source.last_update += interval;
60  for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
61  BaseEdge &edge = this->edges[node1][node2];
63  if (edge.last_restricted_update != INVALID_DATE) edge.last_restricted_update += interval;
64  }
65  }
66 }
67 
68 void LinkGraph::Compress()
69 {
70  this->last_compression = (_date + this->last_compression) / 2;
71  for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
72  this->nodes[node1].supply /= 2;
73  for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
74  BaseEdge &edge = this->edges[node1][node2];
75  if (edge.capacity > 0) {
76  edge.capacity = max(1U, edge.capacity / 2);
77  edge.usage /= 2;
78  }
79  }
80  }
81 }
82 
88 {
89  Date age = _date - this->last_compression + 1;
90  Date other_age = _date - other->last_compression + 1;
91  NodeID first = this->Size();
92  for (NodeID node1 = 0; node1 < other->Size(); ++node1) {
93  Station *st = Station::Get(other->nodes[node1].station);
94  NodeID new_node = this->AddNode(st);
95  this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);
96  st->goods[this->cargo].link_graph = this->index;
97  st->goods[this->cargo].node = new_node;
98  for (NodeID node2 = 0; node2 < node1; ++node2) {
99  BaseEdge &forward = this->edges[new_node][first + node2];
100  BaseEdge &backward = this->edges[first + node2][new_node];
101  forward = other->edges[node1][node2];
102  backward = other->edges[node2][node1];
103  forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age);
104  forward.usage = LinkGraph::Scale(forward.usage, age, other_age);
105  if (forward.next_edge != INVALID_NODE) forward.next_edge += first;
106  backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age);
107  backward.usage = LinkGraph::Scale(backward.usage, age, other_age);
108  if (backward.next_edge != INVALID_NODE) backward.next_edge += first;
109  }
110  BaseEdge &new_start = this->edges[new_node][new_node];
111  new_start = other->edges[node1][node1];
112  if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;
113  }
114  delete other;
115 }
116 
121 void LinkGraph::RemoveNode(NodeID id)
122 {
123  assert(id < this->Size());
124 
125  NodeID last_node = this->Size() - 1;
126  for (NodeID i = 0; i <= last_node; ++i) {
127  (*this)[i].RemoveEdge(id);
128  BaseEdge *node_edges = this->edges[i];
129  NodeID prev = i;
130  NodeID next = node_edges[i].next_edge;
131  while (next != INVALID_NODE) {
132  if (next == last_node) {
133  node_edges[prev].next_edge = id;
134  break;
135  }
136  prev = next;
137  next = node_edges[prev].next_edge;
138  }
139  node_edges[id] = node_edges[last_node];
140  }
141  Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;
142  this->nodes.Erase(this->nodes.Get(id));
143  this->edges.EraseColumn(id);
144  /* Not doing EraseRow here, as having the extra invalid row doesn't hurt
145  * and removing it would trigger a lot of memmove. The data has already
146  * been copied around in the loop above. */
147 }
148 
157 NodeID LinkGraph::AddNode(const Station *st)
158 {
159  const GoodsEntry &good = st->goods[this->cargo];
160 
161  NodeID new_node = this->Size();
162  this->nodes.Append();
163  /* Avoid reducing the height of the matrix as that is expensive and we
164  * most likely will increase it again later which is again expensive. */
165  this->edges.Resize(new_node + 1U,
166  max(new_node + 1U, this->edges.Height()));
167 
168  this->nodes[new_node].Init(st->xy, st->index,
170 
171  BaseEdge *new_edges = this->edges[new_node];
172 
173  /* Reset the first edge starting at the new node */
174  new_edges[new_node].next_edge = INVALID_NODE;
175 
176  for (NodeID i = 0; i <= new_node; ++i) {
177  new_edges[i].Init();
178  this->edges[i][new_node].Init();
179  }
180  return new_node;
181 }
182 
191 void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode)
192 {
193  assert(this->index != to);
194  BaseEdge &edge = this->edges[to];
195  BaseEdge &first = this->edges[this->index];
196  edge.capacity = capacity;
197  edge.usage = usage;
198  edge.next_edge = first.next_edge;
199  first.next_edge = to;
201  if (mode & EUM_RESTRICTED) edge.last_restricted_update = _date;
202 }
203 
211 void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode)
212 {
213  assert(capacity > 0);
214  assert(usage <= capacity);
215  if (this->edges[to].capacity == 0) {
216  this->AddEdge(to, capacity, usage, mode);
217  } else {
218  (*this)[to].Update(capacity, usage, mode);
219  }
220 }
221 
227 {
228  if (this->index == to) return;
229  BaseEdge &edge = this->edges[to];
230  edge.capacity = 0;
233  edge.usage = 0;
234 
235  NodeID prev = this->index;
236  NodeID next = this->edges[this->index].next_edge;
237  while (next != INVALID_NODE) {
238  if (next == to) {
239  /* Will be removed, skip it. */
240  this->edges[prev].next_edge = edge.next_edge;
241  edge.next_edge = INVALID_NODE;
242  break;
243  } else {
244  prev = next;
245  next = this->edges[next].next_edge;
246  }
247  }
248 }
249 
262 {
263  assert(this->edge.capacity > 0);
264  assert(capacity >= usage);
265 
266  if (mode & EUM_INCREASE) {
267  this->edge.capacity += capacity;
268  this->edge.usage += usage;
269  } else if (mode & EUM_REFRESH) {
270  this->edge.capacity = max(this->edge.capacity, capacity);
271  this->edge.usage = max(this->edge.usage, usage);
272  }
273  if (mode & EUM_UNRESTRICTED) this->edge.last_unrestricted_update = _date;
274  if (mode & EUM_RESTRICTED) this->edge.last_restricted_update = _date;
275 }
276 
282 void LinkGraph::Init(uint size)
283 {
284  assert(this->Size() == 0);
285  this->edges.Resize(size, size);
286  this->nodes.Resize(size);
287 
288  for (uint i = 0; i < size; ++i) {
289  this->nodes[i].Init();
290  BaseEdge *column = this->edges[i];
291  for (uint j = 0; j < size; ++j) column[j].Init();
292  }
293 }
NodeID AddNode(const Station *st)
Add a node to the component and create empty edges associated with it.
Definition: linkgraph.cpp:157
Increase capacity.
An edge in the link graph.
Definition: linkgraph.h:63
LinkGraphPool _link_graph_pool("LinkGraph")
The actual pool with link graphs.
Stores station stats for a single cargo.
Definition: station_base.h:170
Tindex index
Index of this pool item.
Definition: pool_type.hpp:147
void AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode)
Fill an edge with values from a link.
Definition: linkgraph.cpp:191
void ShiftDates(int interval)
Shift all dates by given interval.
Definition: linkgraph.cpp:54
CargoID cargo
Cargo of this component&#39;s link graph.
Definition: linkgraph.h:533
uint usage
Usage of the link.
Definition: linkgraph.h:65
static T max(const T a, const T b)
Returns the maximum of two values.
Definition: math_func.hpp:26
GoodsEntry goods[NUM_CARGO]
Goods at this station.
Definition: station_base.h:472
T * Append(uint to_add=1)
Append an item and return it.
Refresh capacity.
A connected component of a link graph.
Definition: linkgraph.h:40
void Resize(uint num_items)
Set the size of the vector, effectively truncating items from the end or appending uninitialised ones...
NodeID next_edge
Destination of next valid edge starting at the same source node.
Definition: linkgraph.h:68
Date last_update
When the supply was last updated.
Definition: linkgraph.h:53
static uint Scale(uint val, uint target_age, uint orig_age)
Scale a value from a link graph of age orig_age for usage in one of age target_age.
Definition: linkgraph.h:455
uint Size() const
Get the current size of the component.
Definition: linkgraph.h:499
void Resize(uint new_width, uint new_height)
Set the size to a specific width and height, preserving item positions as far as possible in the proc...
LinkGraphID link_graph
Link graph this station belongs to.
Definition: station_base.h:257
byte status
Status of this cargo, see GoodsEntryStatus.
Definition: station_base.h:226
static const Date INVALID_DATE
Representation of an invalid date.
Definition: date_type.h:110
NodeID node
ID of node in link graph referring to this goods entry.
Definition: station_base.h:258
Use restricted link.
EdgeMatrix edges
Edges in the component.
Definition: linkgraph.h:536
Date last_restricted_update
When the restricted part of the link was last updated.
Definition: linkgraph.h:67
void Init()
Create an edge.
Definition: linkgraph.cpp:40
void RemoveNode(NodeID id)
Remove a node from the link graph by overwriting it with the last node.
Definition: linkgraph.cpp:121
Base class for all pools.
Definition: pool_type.hpp:83
EdgeUpdateMode
Special modes for updating links.
uint capacity
Capacity of the link.
Definition: linkgraph.h:64
#define INSTANTIATE_POOL_METHODS(name)
Force instantiation of pool methods so we don&#39;t get linker errors.
Definition: pool_func.hpp:224
void EraseColumn(uint x)
Erase a column, replacing it with the last one.
void Init(uint size)
Resize the component and fill it with empty nodes and edges.
Definition: linkgraph.cpp:282
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:80
Node of the link graph.
Definition: linkgraph.h:48
TileIndex xy
Base tile of the station.
void Erase(T *item)
Removes given item from this vector.
Date last_compression
Last time the capacities and supplies were compressed.
Definition: linkgraph.h:534
Declaration of link graph classes used for cargo distribution.
int32 Date
The type to store our dates in.
Definition: date_type.h:16
void Update(uint capacity, uint usage, EdgeUpdateMode mode)
Update an edge.
Definition: linkgraph.cpp:261
static bool HasBit(const T x, const uint8 y)
Checks if a bit in a value is set.
const T * Get(uint index) const
Get the pointer to item "number" (const)
Use unrestricted link.
NodeVector nodes
Nodes in the component.
Definition: linkgraph.h:535
void RemoveEdge(NodeID to)
Remove an outgoing edge from this node.
Definition: linkgraph.cpp:226
void UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode)
Creates an edge if none exists yet or updates an existing edge.
Definition: linkgraph.cpp:211
static Station * Get(size_t index)
Gets station with given index.
Date _date
Current date in days (day counter)
Definition: date.cpp:28
void Merge(LinkGraph *other)
Merge a link graph with another one.
Definition: linkgraph.cpp:87
Station data structure.
Definition: station_base.h:446
Set when the station accepts the cargo currently for final deliveries.
Definition: station_base.h:177
Date last_unrestricted_update
When the unrestricted part of the link was last updated.
Definition: linkgraph.h:66