OpenTTD Source 20261112-master-gbcbec5e63f
linkgraph.h
Go to the documentation of this file.
1/*
2 * This file is part of OpenTTD.
3 * 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.
4 * 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.
5 * 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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
6 */
7
9
10#ifndef LINKGRAPH_H
11#define LINKGRAPH_H
12
13#include "../core/pool_type.hpp"
14#include "../station_base.h"
17#include "linkgraph_type.h"
18
19class LinkGraph;
20
27extern LinkGraphPool _link_graph_pool;
28
35class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
36public:
40 struct BaseEdge {
41 uint capacity = 0;
42 uint usage = 0;
43 uint64_t travel_time_sum = 0;
46 NodeID dest_node = INVALID_NODE;
47
48 BaseEdge(NodeID dest_node = INVALID_NODE);
49
54 uint32_t TravelTime() const { return this->travel_time_sum / this->capacity; }
55
60 TimerGameEconomy::Date LastUpdate() const { return std::max(this->last_unrestricted_update, this->last_restricted_update); }
61
62 void Update(uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes);
63 void Restrict() { this->last_unrestricted_update = EconomyTime::INVALID_DATE; }
64 void Release() { this->last_restricted_update = EconomyTime::INVALID_DATE; }
65
71 auto operator<=>(const BaseEdge &rhs) const noexcept
72 {
73 return this->dest_node <=> rhs.dest_node;
74 }
75
81 auto operator<=>(NodeID rhs) const noexcept
82 {
83 return this->dest_node <=> rhs;
84 }
85
92 friend inline auto operator<=>(NodeID lhs, const LinkGraph::BaseEdge &rhs) noexcept
93 {
94 return lhs <=> rhs.dest_node;
95 }
96 };
97
103 struct BaseNode {
104 uint supply = 0;
105 uint demand = 0;
106 StationID station = StationID::Invalid();
109
110 std::vector<BaseEdge> edges;
111
112 BaseNode(TileIndex xy = INVALID_TILE, StationID st = StationID::Invalid(), uint demand = 0);
113
119 {
120 this->supply += supply;
121 this->last_update = TimerGameEconomy::date;
122 }
123
129 {
130 this->xy = xy;
131 }
132
137 void SetDemand(uint demand)
138 {
139 this->demand = demand;
140 }
141
142 void AddEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes);
143 void UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes);
144 void RemoveEdge(NodeID to);
145
151 bool HasEdgeTo(NodeID dest) const
152 {
153 return std::binary_search(this->edges.begin(), this->edges.end(), dest);
154 }
155
156 BaseEdge &operator[](NodeID to)
157 {
158 assert(this->HasEdgeTo(to));
159 return *GetEdge(to);
160 }
161
162 const BaseEdge &operator[](NodeID to) const
163 {
164 assert(this->HasEdgeTo(to));
165 return *GetEdge(to);
166 }
167
168 private:
169 std::vector<BaseEdge>::iterator GetEdge(NodeID dest)
170 {
171 return std::lower_bound(this->edges.begin(), this->edges.end(), dest);
172 }
173
174 std::vector<BaseEdge>::const_iterator GetEdge(NodeID dest) const
175 {
176 return std::lower_bound(this->edges.begin(), this->edges.end(), dest);
177 }
178 };
179
180 typedef std::vector<BaseNode> NodeVector;
181
183 static const uint MIN_TIMEOUT_DISTANCE = 32;
184
187
190
199 static inline uint Scale(uint val, TimerGameEconomy::Date target_age, TimerGameEconomy::Date orig_age)
200 {
201 return val > 0 ? std::max(1U, val * target_age.base() / orig_age.base()) : 0;
202 }
203
211
212 void Init(uint size);
213 void ShiftDates(TimerGameEconomy::Date interval);
214 void Compress();
215 void Merge(LinkGraph *other);
216
217 /* Splitting link graphs is intentionally not implemented.
218 * The overhead in determining connectedness would probably outweigh the
219 * benefit of having to deal with smaller graphs. In real world examples
220 * networks generally grow. Only rarely a network is permanently split.
221 * Reacting to temporary splits here would obviously create performance
222 * problems and detecting the temporary or permanent nature of splits isn't
223 * trivial. */
224
230 inline BaseNode &operator[](NodeID num) { return this->nodes[num]; }
231
237 inline const BaseNode &operator[](NodeID num) const { return this->nodes[num]; }
238
243 inline NodeID Size() const { return (NodeID)this->nodes.size(); }
244
250
255 inline CargoType Cargo() const { return this->cargo; }
256
262 inline uint Monthly(uint base) const
263 {
264 return base * 30 / (TimerGameEconomy::date - this->last_compression + 1).base();
265 }
266
267 NodeID AddNode(const Station *st);
268 void RemoveNode(NodeID id);
269
270protected:
273 friend class SlLinkgraphNode;
274 friend class SlLinkgraphEdge;
275 friend class LinkGraphJob;
276
279 NodeVector nodes{};
280};
281
282#endif /* LINKGRAPH_H */
static constexpr CargoType INVALID_CARGO
Invalid marker for cargoes.
Definition cargo_type.h:83
CargoType
Cargo slots to indicate a cargo type within a game.
Definition cargo_type.h:22
Class for calculation jobs to be run on link graphs.
A connected component of a link graph.
Definition linkgraph.h:35
const BaseNode & operator[](NodeID num) const
Get a const reference to a node with the specified id.
Definition linkgraph.h:237
void Merge(LinkGraph *other)
Merge a link graph with another one.
Definition linkgraph.cpp:91
void Init(uint size)
Resize the component and fill it with empty nodes and edges.
CargoType cargo
Cargo of this component's link graph.
Definition linkgraph.h:277
uint Monthly(uint base) const
Scale a value to its monthly equivalent, based on last compression.
Definition linkgraph.h:262
NodeVector nodes
Nodes in the component.
Definition linkgraph.h:279
friend SaveLoadTable GetLinkGraphDesc()
Get a SaveLoad array for a link graph.
void ShiftDates(TimerGameEconomy::Date interval)
Shift all dates by given interval.
Definition linkgraph.cpp:54
TimerGameEconomy::Date LastCompression() const
Get date of last compression.
Definition linkgraph.h:249
NodeID AddNode(const Station *st)
Add a node to the component and create empty edges associated with it.
BaseNode & operator[](NodeID num)
Get a node with the specified id.
Definition linkgraph.h:230
NodeID Size() const
Get the current size of the component.
Definition linkgraph.h:243
CargoType Cargo() const
Get the cargo type this component's link graph refers to.
Definition linkgraph.h:255
static const uint MIN_TIMEOUT_DISTANCE
Minimum effective distance for timeout calculation.
Definition linkgraph.h:183
void RemoveNode(NodeID id)
Remove a node from the link graph by overwriting it with the last node.
static constexpr TimerGameEconomy::Date STALE_LINK_DEPOT_TIMEOUT
Number of days before deleting links served only by vehicles stopped in depot.
Definition linkgraph.h:186
static constexpr TimerGameEconomy::Date COMPRESSION_INTERVAL
Minimum number of days between subsequent compressions of a LG.
Definition linkgraph.h:189
static uint Scale(uint val, TimerGameEconomy::Date target_age, TimerGameEconomy::Date orig_age)
Scale a value from a link graph of age orig_age for usage in one of age target_age.
Definition linkgraph.h:199
LinkGraph(LinkGraphID index, CargoType cargo=INVALID_CARGO)
Real constructor.
Definition linkgraph.h:209
friend SaveLoadTable GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
TimerGameEconomy::Date last_compression
Last time the capacities and supplies were compressed.
Definition linkgraph.h:278
static constexpr TimerGame< struct Economy >::Date INVALID_DATE
Timer that is increased every 27ms, and counts towards economy time units, expressed in days / months...
static Date date
Current date in days (day counter).
StrongType::Typedef< int32_t, DateTag< struct Economy >, StrongType::Compare, StrongType::Integer > Date
LinkGraphPool _link_graph_pool
The actual pool with link graphs.
Pool< LinkGraph, LinkGraphID, 32 > LinkGraphPool
Type of the pool for link graph components.
Definition linkgraph.h:25
Declaration of link graph types used for cargo distribution.
EnumBitSet< EdgeUpdateMode, uint8_t > EdgeUpdateModes
Bitset of EdgeUpdateMode elements.
Label< struct NodeIDTag > NodeID
Label type of the nodes in the AllowedSubtags.
Definition of Pool, structure used to access PoolItems, and PoolItem, base structure for Vehicle,...
Types often used outside the saveload code related to saving and loading games.
std::span< const struct SaveLoad > SaveLoadTable
A table of SaveLoad entries.
Base classes/functions for stations.
An edge in the link graph.
Definition linkgraph.h:40
TimerGameEconomy::Date last_restricted_update
When the restricted part of the link was last updated.
Definition linkgraph.h:45
TimerGameEconomy::Date LastUpdate() const
Get the date of the last update to any part of the edge's capacity.
Definition linkgraph.h:60
auto operator<=>(const BaseEdge &rhs) const noexcept
Comparison operator based on dest_node.
Definition linkgraph.h:71
uint32_t TravelTime() const
Get edge's average travel time.
Definition linkgraph.h:54
uint64_t travel_time_sum
Sum of the travel times of the link, in ticks.
Definition linkgraph.h:43
NodeID dest_node
Destination of the edge.
Definition linkgraph.h:46
friend auto operator<=>(NodeID lhs, const LinkGraph::BaseEdge &rhs) noexcept
Compare a NodeID with a BaseEdge.
Definition linkgraph.h:92
uint usage
Usage of the link.
Definition linkgraph.h:42
auto operator<=>(NodeID rhs) const noexcept
Compare with a NodeID.
Definition linkgraph.h:81
void Update(uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes)
Update an edge.
BaseEdge(NodeID dest_node=INVALID_NODE)
Create an edge.
Definition linkgraph.cpp:39
TimerGameEconomy::Date last_unrestricted_update
When the unrestricted part of the link was last updated.
Definition linkgraph.h:44
uint capacity
Capacity of the link.
Definition linkgraph.h:41
Node of the link graph.
Definition linkgraph.h:103
StationID station
Station ID.
Definition linkgraph.h:106
void SetDemand(uint demand)
Set the node's demand.
Definition linkgraph.h:137
TimerGameEconomy::Date last_update
When the supply was last updated.
Definition linkgraph.h:108
BaseNode(TileIndex xy=INVALID_TILE, StationID st=StationID::Invalid(), uint demand=0)
Create a node or clear it.
Definition linkgraph.cpp:26
void UpdateLocation(TileIndex xy)
Update the node's location on the map.
Definition linkgraph.h:128
std::vector< BaseEdge > edges
Sorted list of outgoing edges from this node.
Definition linkgraph.h:110
uint supply
Supply at the station.
Definition linkgraph.h:104
void RemoveEdge(NodeID to)
Remove an outgoing edge from this node.
void AddEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes)
Fill an edge with values from a link.
TileIndex xy
Location of the station referred to by the node.
Definition linkgraph.h:107
uint demand
Acceptance at the station.
Definition linkgraph.h:105
void UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateModes modes)
Creates an edge if none exists yet or updates an existing edge.
bool HasEdgeTo(NodeID dest) const
Check if an edge to a destination is present.
Definition linkgraph.h:151
void UpdateSupply(uint supply)
Update the node's supply and set last_update to the current date.
Definition linkgraph.h:118
Base class for all pools.
Station data structure.
StrongType::Typedef< uint32_t, struct TileIndexTag, StrongType::Compare, StrongType::Integer, StrongType::Compatible< int32_t >, StrongType::Compatible< int64_t > > TileIndex
The index/ID of a Tile.
Definition tile_type.h:92
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition tile_type.h:100
Definition of the game-economy-timer.