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); }
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);
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;
uint8_t CargoID
Cargo slots to indicate a cargo type within a game.
Storage class for Economy time constants.
Flow descriptions by origin stations.
Class for calculation jobs to be run on link graphs.
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
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.
TimerGameEconomy::Date join_date
Date when the job is to be joined.
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
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.
LinkGraphJob()
Bare constructor, only for save/load.
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.
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.
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
bool IsJobCompleted() const
Check if job has actually finished.
NodeAnnotation & operator[](NodeID num)
Get a node abstraction with the specified id.
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.
CargoID Cargo() const
Get the cargo of the underlying link graph.
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.
TimerGameEconomy::Date LastCompression() const
Get date of last compression.
NodeID Size() const
Get the current size of the component.
CargoID Cargo() const
Get the cargo ID this component's link graph refers to.
A leg of a path in the link graph.
NodeID GetOrigin() const
Get the overall origin of the path.
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.
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.
int GetFreeCapacity() const
Get the free capacity of the path.
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.
uint GetDistance() const
Get the overall distance of the path.
uint capacity
This capacity is min(capacity) fom 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 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.
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
std::span< const struct SaveLoad > SaveLoadTable
A table of SaveLoad entries.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
void free(const void *ptr)
Version of the standard free that accepts const pointers.
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.
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.
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.
const EdgeAnnotation & operator[](NodeID to) const
Retrieve an edge starting at this node.
An edge in the link graph.
NodeID dest_node
Destination of the edge.
std::vector< BaseEdge > edges
Sorted list of outgoing edges from this node.
Base class for all PoolItems.
Tindex index
Index of this pool item.
Base class for all pools.
Templated helper to make a type-safe 'typedef' representing a single POD value.