OpenTTD Source  20241108-master-g80f628063a
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 <http://www.gnu.org/licenses/>.
6  */
7 
10 #ifndef LINKGRAPHJOB_H
11 #define LINKGRAPHJOB_H
12 
13 #include "../thread.h"
14 #include "linkgraph.h"
15 #include <atomic>
16 
17 class LinkGraphJob;
18 class Path;
19 typedef std::list<Path *> PathList;
20 
25 
29 class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool>{
30 public:
35  uint demand;
37  };
38 
42  struct EdgeAnnotation {
44 
45  uint flow;
46 
48 
53  uint Flow() const { return this->flow; }
54 
59  void AddFlow(uint flow) { this->flow += flow; }
60 
65  void RemoveFlow(uint flow)
66  {
67  assert(flow <= this->flow);
68  this->flow -= flow;
69  }
70 
71  friend inline bool operator <(NodeID dest, const EdgeAnnotation &rhs)
72  {
73  return dest < rhs.base.dest_node;
74  }
75  };
76 
80  struct NodeAnnotation {
82 
84  PathList paths;
86 
87  std::vector<EdgeAnnotation> edges;
88  std::vector<DemandAnnotation> demands;
89 
90  NodeAnnotation(const LinkGraph::BaseNode &node, size_t size) : base(node), undelivered_supply(node.supply), paths(), flows()
91  {
92  this->edges.reserve(node.edges.size());
93  for (auto &e : node.edges) this->edges.emplace_back(e);
94  this->demands.resize(size);
95  }
96 
103  {
104  auto it = std::find_if(this->edges.begin(), this->edges.end(), [=] (const EdgeAnnotation &e) { return e.base.dest_node == to; });
105  assert(it != this->edges.end());
106  return *it;
107  }
108 
114  const EdgeAnnotation &operator[](NodeID to) const
115  {
116  auto it = std::find_if(this->edges.begin(), this->edges.end(), [=] (const EdgeAnnotation &e) { return e.base.dest_node == to; });
117  assert(it != this->edges.end());
118  return *it;
119  }
120 
125  uint DemandTo(NodeID to) const { return this->demands[to].demand; }
126 
131  uint UnsatisfiedDemandTo(NodeID to) const { return this->demands[to].unsatisfied_demand; }
132 
137  void SatisfyDemandTo(NodeID to, uint demand)
138  {
139  assert(demand <= this->demands[to].unsatisfied_demand);
140  this->demands[to].unsatisfied_demand -= demand;
141  }
142 
148  void DeliverSupply(NodeID to, uint amount)
149  {
150  this->undelivered_supply -= amount;
151  this->demands[to].demand += amount;
152  this->demands[to].unsatisfied_demand += amount;
153  }
154  };
155 
156 private:
157  typedef std::vector<NodeAnnotation> NodeAnnotationVector;
158 
160  friend class LinkGraphSchedule;
161 
162 protected:
165  std::thread thread;
167  NodeAnnotationVector nodes;
168  std::atomic<bool> job_completed;
169  std::atomic<bool> job_aborted;
170 
171  void EraseFlows(NodeID from);
172  void JoinThread();
173  void SpawnThread();
174 
175 public:
181  join_date(EconomyTime::INVALID_DATE), job_completed(false), job_aborted(false) {}
182 
183  LinkGraphJob(const LinkGraph &orig);
184  ~LinkGraphJob();
185 
186  void Init();
187 
193  inline bool IsJobCompleted() const { return this->job_completed.load(std::memory_order_acquire); }
194 
200  inline bool IsJobAborted() const { return this->job_aborted.load(std::memory_order_acquire); }
201 
208  inline void AbortJob() { this->job_aborted.store(true, std::memory_order_release); }
209 
214  inline bool IsScheduledToBeJoined() const { return this->join_date <= TimerGameEconomy::date; }
215 
220  inline TimerGameEconomy::Date JoinDate() const { return join_date; }
221 
226  inline void ShiftJoinDate(TimerGameEconomy::Date interval) { this->join_date += interval; }
227 
232  inline const LinkGraphSettings &Settings() const { return this->settings; }
233 
239  inline NodeAnnotation &operator[](NodeID num) { return this->nodes[num]; }
240 
245  inline NodeID Size() const { return this->link_graph.Size(); }
246 
251  inline CargoID Cargo() const { return this->link_graph.Cargo(); }
252 
257  inline TimerGameEconomy::Date LastCompression() const { return this->link_graph.LastCompression(); }
258 
263  inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }
264 
269  inline const LinkGraph &Graph() const { return this->link_graph; }
270 };
271 
275 class Path {
276 public:
278 
279  Path(NodeID n, bool source = false);
280  virtual ~Path() = default;
281 
283  inline NodeID GetNode() const { return this->node; }
284 
286  inline NodeID GetOrigin() const { return this->origin; }
287 
289  inline Path *GetParent() { return this->parent; }
290 
292  inline uint GetCapacity() const { return this->capacity; }
293 
295  inline int GetFreeCapacity() const { return this->free_capacity; }
296 
304  inline static int GetCapacityRatio(int free, uint total)
305  {
306  return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
307  }
308 
313  inline int GetCapacityRatio() const
314  {
315  return Path::GetCapacityRatio(this->free_capacity, this->capacity);
316  }
317 
319  inline uint GetDistance() const { return this->distance; }
320 
322  inline void ReduceFlow(uint f) { this->flow -= f; }
323 
325  inline void AddFlow(uint f) { this->flow += f; }
326 
328  inline uint GetFlow() const { return this->flow; }
329 
331  inline uint GetNumChildren() const { return this->num_children; }
332 
336  inline void Detach()
337  {
338  if (this->parent != nullptr) {
339  this->parent->num_children--;
340  this->parent = nullptr;
341  }
342  }
343 
344  uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
345  void Fork(Path *base, uint cap, int free_cap, uint dist);
346 
347 protected:
348 
349  /*
350  * Some boundaries to clamp against in order to avoid integer overflows.
351  */
352  static constexpr int PATH_CAP_MULTIPLIER = 16;
353  static constexpr int PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER;
354  static constexpr int PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER;
355 
356  uint distance;
357  uint capacity;
359  uint flow;
360  NodeID node;
361  NodeID origin;
364 };
365 
366 #endif /* LINKGRAPHJOB_H */
uint8_t CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:22
Storage class for Economy time constants.
Flow descriptions by origin stations.
Definition: station_base.h:148
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:29
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:232
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
Definition: linkgraphjob.h:167
std::atomic< bool > job_completed
Is the job still running. This is accessed by multiple threads and reads may be stale.
Definition: linkgraphjob.h:168
TimerGameEconomy::Date JoinDate() const
Get the date when the job should be finished.
Definition: linkgraphjob.h:220
void AbortJob()
Abort job.
Definition: linkgraphjob.h:208
~LinkGraphJob()
Join the link graph job and destroy it.
TimerGameEconomy::Date join_date
Date when the job is to be joined.
Definition: linkgraphjob.h:166
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
Definition: linkgraphjob.h:269
std::atomic< bool > job_aborted
Has the job been aborted. This is accessed by multiple threads and reads may be stale.
Definition: linkgraphjob.h:169
TimerGameEconomy::Date LastCompression() const
Get the date when the underlying link graph was last compressed.
Definition: linkgraphjob.h:257
LinkGraphJob()
Bare constructor, only for save/load.
Definition: linkgraphjob.h:180
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
Definition: linkgraphjob.h:263
bool IsJobAborted() const
Check if job has been aborted.
Definition: linkgraphjob.h:200
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
Definition: linkgraphjob.h:164
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
Definition: linkgraphjob.h:214
bool IsJobCompleted() const
Check if job has actually finished.
Definition: linkgraphjob.h:193
NodeAnnotation & operator[](NodeID num)
Get a node abstraction with the specified id.
Definition: linkgraphjob.h:239
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:245
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
Definition: linkgraphjob.h:163
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:251
friend SaveLoadTable GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
void ShiftJoinDate(TimerGameEconomy::Date interval)
Change the join date on date cheating.
Definition: linkgraphjob.h:226
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.
Definition: linkgraphjob.h:165
A connected component of a link graph.
Definition: linkgraph.h:37
TimerGameEconomy::Date LastCompression() const
Get date of last compression.
Definition: linkgraph.h:236
NodeID Size() const
Get the current size of the component.
Definition: linkgraph.h:230
CargoID Cargo() const
Get the cargo ID this component's link graph refers to.
Definition: linkgraph.h:242
A leg of a path in the link graph.
Definition: linkgraphjob.h:275
NodeID GetOrigin() const
Get the overall origin of the path.
Definition: linkgraphjob.h:286
Path(NodeID n, bool source=false)
Create a leg of a path in the link graph.
Path * GetParent()
Get the parent leg of this one.
Definition: linkgraphjob.h:289
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:325
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:277
NodeID origin
Link graph node this path originates from.
Definition: linkgraphjob.h:361
uint num_children
Number of child legs that have been forked from this path.
Definition: linkgraphjob.h:362
void Detach()
Detach this path from its parent.
Definition: linkgraphjob.h:336
int GetFreeCapacity() const
Get the free capacity of the path.
Definition: linkgraphjob.h:295
uint GetFlow() const
Get the flow on this leg.
Definition: linkgraphjob.h:328
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 ...
Definition: linkgraphjob.h:304
uint flow
Flow the current run of the mcf solver assigns.
Definition: linkgraphjob.h:359
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:356
NodeID GetNode() const
Get the node this leg passes.
Definition: linkgraphjob.h:283
int GetCapacityRatio() const
Get capacity ratio of this path.
Definition: linkgraphjob.h:313
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.
Definition: linkgraphjob.h:360
uint GetCapacity() const
Get the overall capacity of the path.
Definition: linkgraphjob.h:292
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
Definition: linkgraphjob.h:331
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:322
uint GetDistance() const
Get the overall distance of the path.
Definition: linkgraphjob.h:319
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:357
Path * parent
Parent leg of this one.
Definition: linkgraphjob.h:363
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:358
static Date date
Current date in days (day counter).
Declaration of link graph classes used for cargo distribution.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
Pool< LinkGraphJob, LinkGraphJobID, 32, 0xFFFF > LinkGraphJobPool
Type of the pool for link graph jobs.
Definition: linkgraphjob.h:22
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Definition: math_func.hpp:79
std::span< const struct SaveLoad > SaveLoadTable
A table of SaveLoad entries.
Definition: saveload.h:511
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:57
void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:334
Demand between two nodes.
Definition: linkgraphjob.h:34
uint unsatisfied_demand
Demand over this edge that hasn't been satisfied yet.
Definition: linkgraphjob.h:36
uint demand
Transport demand between the nodes.
Definition: linkgraphjob.h:35
Annotation for a link graph edge.
Definition: linkgraphjob.h:42
const LinkGraph::BaseEdge & base
Reference to the edge that is annotated.
Definition: linkgraphjob.h:43
uint Flow() const
Get the total flow on the edge.
Definition: linkgraphjob.h:53
void AddFlow(uint flow)
Add some flow.
Definition: linkgraphjob.h:59
void RemoveFlow(uint flow)
Remove some flow.
Definition: linkgraphjob.h:65
uint flow
Planned flow over this edge.
Definition: linkgraphjob.h:45
Annotation for a link graph node.
Definition: linkgraphjob.h:80
uint undelivered_supply
Amount of supply that hasn't been distributed yet.
Definition: linkgraphjob.h:83
const LinkGraph::BaseNode & base
Reference to the node that is annotated.
Definition: linkgraphjob.h:81
std::vector< EdgeAnnotation > edges
Annotations for all edges originating at this node.
Definition: linkgraphjob.h:87
PathList paths
Paths through this node, sorted so that those with flow == 0 are in the back.
Definition: linkgraphjob.h:84
void DeliverSupply(NodeID to, uint amount)
Deliver some supply, adding demand to the respective edge.
Definition: linkgraphjob.h:148
FlowStatMap flows
Planned flows to other nodes.
Definition: linkgraphjob.h:85
EdgeAnnotation & operator[](NodeID to)
Retrieve an edge starting at this node.
Definition: linkgraphjob.h:102
uint DemandTo(NodeID to) const
Get the transport demand between end the points of the edge.
Definition: linkgraphjob.h:125
void SatisfyDemandTo(NodeID to, uint demand)
Satisfy some demand.
Definition: linkgraphjob.h:137
uint UnsatisfiedDemandTo(NodeID to) const
Get the transport demand that hasn't been satisfied by flows, yet.
Definition: linkgraphjob.h:131
std::vector< DemandAnnotation > demands
Annotations for the demand to all other nodes.
Definition: linkgraphjob.h:88
const EdgeAnnotation & operator[](NodeID to) const
Retrieve an edge starting at this node.
Definition: linkgraphjob.h:114
An edge in the link graph.
Definition: linkgraph.h:42
NodeID dest_node
Destination of the edge.
Definition: linkgraph.h:48
Node of the link graph.
Definition: linkgraph.h:90
std::vector< BaseEdge > edges
Sorted list of outgoing edges from this node.
Definition: linkgraph.h:97
Base class for all PoolItems.
Definition: pool_type.hpp:237
Tindex index
Index of this pool item.
Definition: pool_type.hpp:238
Base class for all pools.
Definition: pool_type.hpp:80
Templated helper to make a type-safe 'typedef' representing a single POD value.