OpenTTD Source
20240917-master-g9ab0a47812
|
Go to the documentation of this file.
10 #ifndef LINKGRAPHJOB_H
11 #define LINKGRAPHJOB_H
13 #include "../thread.h"
19 typedef std::list<Path *> PathList;
67 assert(flow <= this->
flow);
71 friend inline bool operator <(NodeID dest,
const EdgeAnnotation &rhs)
87 std::vector<EdgeAnnotation>
edges;
92 this->edges.reserve(node.
edges.size());
93 for (
auto &e : node.
edges) this->edges.emplace_back(e);
94 this->demands.resize(size);
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());
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());
125 uint
DemandTo(NodeID to)
const {
return this->demands[to].demand; }
139 assert(demand <= this->
demands[to].unsatisfied_demand);
140 this->demands[to].unsatisfied_demand -= demand;
150 this->undelivered_supply -= amount;
151 this->demands[to].demand += amount;
152 this->demands[to].unsatisfied_demand += amount;
157 typedef std::vector<NodeAnnotation> NodeAnnotationVector;
193 inline bool IsJobCompleted()
const {
return this->job_completed.load(std::memory_order_acquire); }
200 inline bool IsJobAborted()
const {
return this->job_aborted.load(std::memory_order_acquire); }
208 inline void AbortJob() { this->job_aborted.store(
true, std::memory_order_release); }
226 inline void ShiftJoinDate(TimerGameEconomy::Date interval) { this->join_date += interval; }
245 inline NodeID
Size()
const {
return this->link_graph.
Size(); }
279 Path(NodeID n,
bool source =
false);
280 virtual ~
Path() =
default;
306 return Clamp(
free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
338 if (this->
parent !=
nullptr) {
345 void Fork(
Path *base, uint cap,
int free_cap, uint dist);
353 PATH_CAP_MULTIPLIER = 16,
354 PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
355 PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
uint GetCapacity() const
Get the overall capacity of the path.
FlowStatMap flows
Planned flows to other nodes.
uint capacity
This capacity is min(capacity) fom all edges.
A leg of a path in the link graph.
int GetCapacityRatio() const
Get capacity ratio of this path.
A connected component of a link graph.
std::span< const struct SaveLoad > SaveLoadTable
A table of SaveLoad entries.
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
static Path * invalid_path
Static instance of an invalid path.
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Class for calculation jobs to be run on link graphs.
bool IsJobCompleted() const
Check if job has actually finished.
Tindex index
Index of this pool item.
~LinkGraphJob()
Join the link graph job and destroy it.
NodeID dest_node
Destination of the edge.
void AddFlow(uint flow)
Add some flow.
const EdgeAnnotation & operator[](NodeID to) const
Retrieve an edge starting at this node.
std::atomic< bool > job_completed
Is the job still running. This is accessed by multiple threads and reads may be stale.
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.
uint UnsatisfiedDemandTo(NodeID to) const
Get the transport demand that hasn't been satisfied by flows, yet.
TimerGameEconomy::Date LastCompression() const
Get the date when the underlying link graph was last compressed.
Storage class for Economy time constants.
void JoinThread()
Join the calling thread with this job's thread if threading is enabled.
uint flow
Planned flow over this edge.
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 ...
NodeID origin
Link graph node this path originates from.
NodeID Size() const
Get the current size of the component.
PathList paths
Paths through this node, sorted so that those with flow == 0 are in the back.
void ShiftJoinDate(TimerGameEconomy::Date interval)
Change the join date on date cheating.
int GetFreeCapacity() const
Get the free capacity of the path.
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
Path * parent
Parent leg of this one.
std::vector< DemandAnnotation > demands
Annotations for the demand to all other nodes.
friend SaveLoadTable GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
uint demand
Transport demand between the nodes.
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
uint unsatisfied_demand
Demand over this edge that hasn't been satisfied yet.
uint Flow() const
Get the total flow on the edge.
NodeID Size() const
Get the size of the underlying link graph.
Path * GetParent()
Get the parent leg of this one.
const LinkGraph::BaseNode & base
Reference to the node that is annotated.
void AbortJob()
Abort job.
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
uint undelivered_supply
Amount of supply that hasn't been distributed yet.
void free(const void *ptr)
Version of the standard free that accepts const pointers.
Annotation for a link graph edge.
void RemoveFlow(uint flow)
Remove some flow.
TimerGameEconomy::Date JoinDate() const
Get the date when the job should be finished.
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
An edge in the link graph.
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
CargoID Cargo() const
Get the cargo ID this component's link graph refers to.
std::thread thread
Thread the job is running in or a default-constructed thread if it's running in the main thread.
TimerGameEconomy::Date LastCompression() const
Get date of last compression.
std::vector< BaseEdge > edges
Sorted list of outgoing edges from this node.
PathCapacityBoundaries
Some boundaries to clamp against in order to avoid integer overflows.
uint flow
Flow the current run of the mcf solver assigns.
uint distance
Sum(distance of all legs up to this one).
uint DemandTo(NodeID to) const
Get the transport demand between end the points of the edge.
TimerGameEconomy::Date join_date
Date when the job is to be joined.
Base class for all pools.
Annotation for a link graph node.
EdgeAnnotation & operator[](NodeID to)
Retrieve an edge starting at this node.
bool IsJobAborted() const
Check if job has been aborted.
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Flow descriptions by origin stations.
void DeliverSupply(NodeID to, uint amount)
Deliver some supply, adding demand to the respective edge.
uint8_t CargoID
Cargo slots to indicate a cargo type within a game.
Path(NodeID n, bool source=false)
Create a leg of a path in the link graph.
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
NodeAnnotation & operator[](NodeID num)
Get a node abstraction with the specified id.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
std::vector< EdgeAnnotation > edges
Annotations for all edges originating at this node.
CargoID Cargo() const
Get the cargo of the underlying link graph.
const LinkGraph::BaseEdge & base
Reference to the edge that is annotated.
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
std::atomic< bool > job_aborted
Has the job been aborted. This is accessed by multiple threads and reads may be stale.
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
void Detach()
Detach this path from its parent.
NodeID node
Link graph node this leg passes.
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Base class for all PoolItems.
uint num_children
Number of child legs that have been forked from this path.
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
LinkGraphJob()
Bare constructor, only for save/load.
uint GetDistance() const
Get the overall distance of the path.
NodeID GetOrigin() const
Get the overall origin of the path.
uint GetFlow() const
Get the flow on this leg.
void SatisfyDemandTo(NodeID to, uint demand)
Satisfy some demand.
Demand between two nodes.
Pool< LinkGraphJob, LinkGraphJobID, 32, 0xFFFF > LinkGraphJobPool
Type of the pool for link graph jobs.
NodeID GetNode() const
Get the node this leg passes.
static Date date
Current date in days (day counter).