OpenTTD Source 20261112-master-gbcbec5e63f
linkgraphjob.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 LINKGRAPHJOB_H
11#define LINKGRAPHJOB_H
12
13#include "linkgraph.h"
14#include <atomic>
15#include <thread>
16
17class LinkGraphJob;
18class Path;
19typedef std::list<Path *> PathList;
20
24extern LinkGraphJobPool _link_graph_job_pool;
25
29class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool> {
30public:
35 uint demand = 0;
37 };
38
42 struct EdgeAnnotation {
44 uint flow = 0;
45
46 EdgeAnnotation(const LinkGraph::BaseEdge &base) : base(base) {}
47
52 uint Flow() const { return this->flow; }
53
58 void AddFlow(uint flow) { this->flow += flow; }
59
64 void RemoveFlow(uint flow)
65 {
66 assert(flow <= this->flow);
67 this->flow -= flow;
68 }
69
76 friend inline auto operator<=>(NodeID dest, const EdgeAnnotation &rhs) noexcept
77 {
78 return dest <=> rhs.base.dest_node;
79 }
80 };
81
85 struct NodeAnnotation {
87
89 PathList paths{};
91
92 std::vector<EdgeAnnotation> edges{};
93 std::vector<DemandAnnotation> demands{};
94
95 NodeAnnotation(const LinkGraph::BaseNode &node, size_t size) : base(node), undelivered_supply(node.supply)
96 {
97 this->edges.reserve(node.edges.size());
98 for (auto &e : node.edges) this->edges.emplace_back(e);
99 this->demands.resize(size);
100 }
101
108 {
109 auto it = std::ranges::find_if(this->edges, [=] (const EdgeAnnotation &e) { return e.base.dest_node == to; });
110 assert(it != this->edges.end());
111 return *it;
112 }
113
119 const EdgeAnnotation &operator[](NodeID to) const
120 {
121 auto it = std::ranges::find_if(this->edges, [=] (const EdgeAnnotation &e) { return e.base.dest_node == to; });
122 assert(it != this->edges.end());
123 return *it;
124 }
125
131 uint DemandTo(NodeID to) const { return this->demands[to].demand; }
132
138 uint UnsatisfiedDemandTo(NodeID to) const { return this->demands[to].unsatisfied_demand; }
139
145 void SatisfyDemandTo(NodeID to, uint demand)
146 {
147 assert(demand <= this->demands[to].unsatisfied_demand);
148 this->demands[to].unsatisfied_demand -= demand;
149 }
150
156 void DeliverSupply(NodeID to, uint amount)
157 {
158 this->undelivered_supply -= amount;
159 this->demands[to].demand += amount;
160 this->demands[to].unsatisfied_demand += amount;
161 }
162 };
163
164private:
165 typedef std::vector<NodeAnnotation> NodeAnnotationVector;
166
168 friend class LinkGraphSchedule;
169
170protected:
173 std::thread thread{};
175 NodeAnnotationVector nodes{};
176 std::atomic<bool> job_completed = false;
177 std::atomic<bool> job_aborted = false;
178
179 void EraseFlows(StationID from);
180 void JoinThread();
181 void SpawnThread();
182
183public:
190
191 LinkGraphJob(LinkGraphJobID index, const LinkGraph &orig);
193
194 void Init();
195
201 inline bool IsJobCompleted() const { return this->job_completed.load(std::memory_order_acquire); }
202
208 inline bool IsJobAborted() const { return this->job_aborted.load(std::memory_order_acquire); }
209
216 inline void AbortJob() { this->job_aborted.store(true, std::memory_order_release); }
217
222 inline bool IsScheduledToBeJoined() const { return this->join_date <= TimerGameEconomy::date; }
223
228 inline TimerGameEconomy::Date JoinDate() const { return join_date; }
229
234 inline void ShiftJoinDate(TimerGameEconomy::Date interval) { this->join_date += interval; }
235
240 inline const LinkGraphSettings &Settings() const { return this->settings; }
241
247 inline NodeAnnotation &operator[](NodeID num) { return this->nodes[num]; }
248
253 inline NodeID Size() const { return this->link_graph.Size(); }
254
259 inline CargoType Cargo() const { return this->link_graph.Cargo(); }
260
265 inline TimerGameEconomy::Date LastCompression() const { return this->link_graph.LastCompression(); }
266
271 inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }
272
277 inline const LinkGraph &Graph() const { return this->link_graph; }
278};
279
283class Path {
284public:
286
287 Path(NodeID n, bool source = false);
289 virtual ~Path() = default;
290
295 inline NodeID GetNode() const { return this->node; }
296
301 inline NodeID GetOrigin() const { return this->origin; }
302
307 inline Path *GetParent() { return this->parent; }
308
313 inline uint GetCapacity() const { return this->capacity; }
314
319 inline int GetFreeCapacity() const { return this->free_capacity; }
320
328 static inline int GetCapacityRatio(int free, uint total)
329 {
330 return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
331 }
332
337 inline int GetCapacityRatio() const
338 {
339 return Path::GetCapacityRatio(this->free_capacity, this->capacity);
340 }
341
346 inline uint GetDistance() const { return this->distance; }
347
352 inline void ReduceFlow(uint f) { this->flow -= f; }
353
358 inline void AddFlow(uint f) { this->flow += f; }
359
364 inline uint GetFlow() const { return this->flow; }
365
370 inline uint GetNumChildren() const { return this->num_children; }
371
375 inline void Detach()
376 {
377 if (this->parent != nullptr) {
378 this->parent->num_children--;
379 this->parent = nullptr;
380 }
381 }
382
383 uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
384 void Fork(Path *base, uint cap, int free_cap, uint dist);
385
386protected:
387
391 static constexpr int PATH_CAP_MULTIPLIER = 16;
392 static constexpr int PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER;
393 static constexpr int PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER;
395
396 uint distance = 0;
397 uint capacity = 0;
399 uint flow = 0;
400 NodeID node = INVALID_NODE;
401 NodeID origin = INVALID_NODE;
402 uint num_children = 0;
403 Path *parent = nullptr;
404};
405
406#endif /* LINKGRAPHJOB_H */
CargoType
Cargo slots to indicate a cargo type within a game.
Definition cargo_type.h:22
Flow descriptions by origin stations.
Class for calculation jobs to be run on link graphs.
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
std::atomic< bool > job_completed
Is the job still running. This is accessed by multiple threads and reads may be stale.
TimerGameEconomy::Date JoinDate() const
Get the date when the job should be finished.
void AbortJob()
Abort job.
~LinkGraphJob()
Join the link graph job and destroy it.
NodeAnnotation & operator[](NodeID num)
Get a node abstraction with the specified id.
TimerGameEconomy::Date join_date
Date when the job is to be joined.
std::atomic< bool > job_aborted
Has the job been aborted. This is accessed by multiple threads and reads may be stale.
TimerGameEconomy::Date LastCompression() const
Get the date when the underlying link graph was last compressed.
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
bool IsJobAborted() const
Check if job has been aborted.
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
LinkGraphJob(LinkGraphJobID index)
Bare constructor, only for save/load.
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
CargoType Cargo() const
Get the cargo of the underlying link graph.
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
bool IsJobCompleted() const
Check if job has actually finished.
void EraseFlows(StationID from)
Erase all flows originating at a specific station.
NodeID Size() const
Get the size of the underlying link graph.
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
friend SaveLoadTable GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
void ShiftJoinDate(TimerGameEconomy::Date interval)
Change the join date on date cheating.
void JoinThread()
Join the calling thread with this job's thread if threading is enabled.
std::thread thread
Thread the job is running in or a default-constructed thread if it's running in the main thread.
A connected component of a link graph.
Definition linkgraph.h:35
TimerGameEconomy::Date LastCompression() const
Get date of last compression.
Definition linkgraph.h:249
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
A leg of a path in the link graph.
NodeID GetOrigin() const
Get the overall origin of the path.
virtual ~Path()=default
Ensure the destructor of the sub classes are called as well.
Path(NodeID n, bool source=false)
Create a leg of a path in the link graph.
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
static Path * invalid_path
Static instance of an invalid path.
NodeID origin
Link graph node this path originates from.
uint num_children
Number of child legs that have been forked from this path.
void Detach()
Detach this path from its parent.
static constexpr int PATH_CAP_MULTIPLIER
int GetFreeCapacity() const
Get the free capacity of the path.
static constexpr int PATH_CAP_MAX_FREE
static constexpr int PATH_CAP_MIN_FREE
uint GetFlow() const
Get the flow on this leg.
static int GetCapacityRatio(int free, uint total)
Get ratio of free * 16 (so that we get fewer 0) / max(total capacity, 1) (so that we don't divide by ...
uint flow
Flow the current run of the mcf solver assigns.
uint distance
Sum(distance of all legs up to this one).
NodeID GetNode() const
Get the node this leg passes.
int GetCapacityRatio() const
Get capacity ratio of this path.
void Fork(Path *base, uint cap, int free_cap, uint dist)
Add this path as a new child to the given base path, thus making this path a "fork" of the base path.
NodeID node
Link graph node this leg passes.
uint GetCapacity() const
Get the overall capacity of the path.
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Path * GetParent()
Get the parent leg of this one.
uint GetDistance() const
Get the overall distance of the path.
uint capacity
This capacity is min(capacity) of all edges.
Path * parent
Parent leg of this one.
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
static constexpr TimerGame< struct Economy >::Date INVALID_DATE
static Date date
Current date in days (day counter).
StrongType::Typedef< int32_t, DateTag< struct Economy >, StrongType::Compare, StrongType::Integer > Date
Declaration of link graph classes used for cargo distribution.
Pool< LinkGraphJob, LinkGraphJobID, 32 > LinkGraphJobPool
Type of the pool for link graph jobs.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Definition math_func.hpp:79
@ Invalid
broken savegame (used internally)
Definition saveload.h:438
std::span< const struct SaveLoad > SaveLoadTable
A table of SaveLoad entries.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition settings.cpp:61
Demand between two nodes.
uint unsatisfied_demand
Demand over this edge that hasn't been satisfied yet.
uint demand
Transport demand between the nodes.
Annotation for a link graph edge.
const LinkGraph::BaseEdge & base
Reference to the edge that is annotated.
uint Flow() const
Get the total flow on the edge.
void AddFlow(uint flow)
Add some flow.
friend auto operator<=>(NodeID dest, const EdgeAnnotation &rhs) noexcept
Compare a NodeID with an EdgeAnnotation.
void RemoveFlow(uint flow)
Remove some flow.
uint flow
Planned flow over this edge.
Annotation for a link graph node.
uint undelivered_supply
Amount of supply that hasn't been distributed yet.
const LinkGraph::BaseNode & base
Reference to the node that is annotated.
std::vector< EdgeAnnotation > edges
Annotations for all edges originating at this node.
PathList paths
Paths through this node, sorted so that those with flow == 0 are in the back.
void DeliverSupply(NodeID to, uint amount)
Deliver some supply, adding demand to the respective edge.
FlowStatMap flows
Planned flows to other nodes.
EdgeAnnotation & operator[](NodeID to)
Retrieve an edge starting at this node.
const EdgeAnnotation & operator[](NodeID to) const
Retrieve an edge starting at this node.
uint DemandTo(NodeID to) const
Get the transport demand between end the points of the edge.
void SatisfyDemandTo(NodeID to, uint demand)
Satisfy some demand.
uint UnsatisfiedDemandTo(NodeID to) const
Get the transport demand that hasn't been satisfied by flows, yet.
std::vector< DemandAnnotation > demands
Annotations for the demand to all other nodes.
An edge in the link graph.
Definition linkgraph.h:40
NodeID dest_node
Destination of the edge.
Definition linkgraph.h:46
Node of the link graph.
Definition linkgraph.h:103
std::vector< BaseEdge > edges
Sorted list of outgoing edges from this node.
Definition linkgraph.h:110
Base class for all pools.