OpenTTD Source
1.11.0-beta2
|
Go to the documentation of this file.
10 #ifndef LINKGRAPHJOB_H
11 #define LINKGRAPHJOB_H
13 #include "../thread.h"
20 typedef std::list<Path *> PathList;
49 void Init(uint supply);
52 typedef std::vector<NodeAnnotation> NodeAnnotationVector;
121 this->anno.
flow -= flow;
130 this->anno.
demand += demand;
168 return std::pair<NodeID, Edge>(this->
current,
Edge(this->
base[this->
current], this->base_anno[this->current]));
177 return FakePointer(this->
operator*());
252 const PathList &
Paths()
const {
return this->node_anno.
paths; }
262 (*this)[to].AddDemand(amount);
283 inline bool IsJobCompleted()
const {
return this->job_completed.load(std::memory_order_acquire); }
290 inline bool IsJobAborted()
const {
return this->job_aborted.load(std::memory_order_acquire); }
298 inline void AbortJob() { this->job_aborted.store(
true, std::memory_order_release); }
335 inline uint
Size()
const {
return this->link_graph.
Size(); }
369 Path(NodeID n,
bool source =
false);
395 return Clamp(
free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
427 if (this->
parent !=
nullptr) {
434 void Fork(
Path *base, uint cap,
int free_cap, uint dist);
442 PATH_CAP_MULTIPLIER = 16,
443 PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
444 PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
const BaseEdge * edges
Outgoing edges for wrapped node.
uint GetCapacity() const
Get the overall capacity of the path.
uint Demand() const
Get the transport demand between end the points of the edge.
FlowStatMap flows
Planned flows to other nodes.
uint capacity
This capacity is min(capacity) fom all edges.
uint demand
Transport demand between the nodes.
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.
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
static Path * invalid_path
Static instance of an invalid path.
uint Flow() const
Get the total flow on the edge.
uint UndeliveredSupply() const
Get amount of supply that hasn't been delivered, yet.
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.
void Init()
Initialize a linkgraph job edge.
std::atomic< bool > job_completed
Is the job still running. This is accessed by multiple threads and reads may be stale.
void SatisfyDemand(uint demand)
Satisfy some demand.
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.
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.
EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current)
Constructor.
PathList paths
Paths through this node, sorted so that those with flow == 0 are in the back.
int GetFreeCapacity() const
Get the free capacity of the path.
EdgeAnnotationMatrix edges
Extra edge data necessary for link graph calculation.
Date join_date
Date when the job is to be joined.
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
Node operator[](NodeID num)
Get a node abstraction with the specified id.
Path * parent
Parent leg of this one.
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
Node(LinkGraphJob *lgj, NodeID node)
Constructor.
Wrapper for an edge (const or not) allowing retrieval, but no modification.
Path * GetParent()
Get the parent leg of this one.
BaseEdgeIterator(const LinkGraph::BaseEdge *base, NodeID current)
Constructor.
void AbortJob()
Abort job.
Date _date
Current date in days (day counter)
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.
Tedge & edge
Actual edge to be used.
void ShiftJoinDate(int interval)
Change the join date on date cheating.
uint unsatisfied_demand
Demand over this edge that hasn't been satisfied yet.
Annotation for a link graph edge.
const PathList & Paths() const
Get a constant version of the paths this node is part of.
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
int32 Date
The type to store our dates in.
An edge in the link graph.
uint Size() const
Get the current size of the component.
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.
EdgeAnnotation * edge_annos
Edge annotations belonging to this node.
Base class for iterating across outgoing edges of a node.
FakePointer operator->() const
Dereference.
PathList & Paths()
Get the paths this node is part of.
uint UnsatisfiedDemand() const
Get the transport demand that hasn't been satisfied by flows, yet.
PathCapacityBoundaries
Some boundaries to clamp against in order to avoid integer overflows.
EdgeAnnotation * base_anno
Array of annotations to be (indirectly) iterated.
uint flow
Flow the current run of the mcf solver assigns.
Date LastCompression() const
Get date of last compression.
uint distance
Sum(distance of all legs up to this one).
uint Size() const
Get the size of the underlying link graph.
void DeliverSupply(NodeID to, uint amount)
Deliver some supply, adding demand to the respective edge.
static T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Base class for all pools.
std::pair< NodeID, Edge > operator*() const
Dereference.
Annotation for a link graph node.
FlowStatMap & Flows()
Get the flows running through this node.
Edge operator[](NodeID to) const
Retrieve an edge starting at this node.
NodeID current
Current offset in edges array.
static const Date INVALID_DATE
Representation of an invalid date.
EdgeIterator End() const
Iterator for the "end" of the edge array.
bool IsJobAborted() const
Check if job has been aborted.
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
void RemoveFlow(uint flow)
Remove some flow.
NodeAnnotation & node_anno
Annotation being wrapped.
Flow descriptions by origin stations.
const LinkGraph::BaseEdge * base
Array of edges being iterated.
Date LastCompression() const
Get the date when the underlying link graph was last compressed.
EdgeAnnotation & anno
Annotation being wrapped.
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.
Date JoinDate() const
Get the date when the job should be finished.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
byte CargoID
Cargo slots to indicate a cargo type within a game.
CargoID Cargo() const
Get the cargo of the underlying link graph.
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.
EdgeIterator Begin() const
Iterator for the "begin" of the edge array.
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
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.
Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno)
Constructor.
NodeID index
ID of wrapped node.
void AddDemand(uint demand)
Add some (not yet satisfied) demand.
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.
const friend SaveLoad * GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
uint GetFlow() const
Get the flow on this leg.
const BaseNode & node
Node being wrapped.
const FlowStatMap & Flows() const
Get a constant version of the flows running through this node.
void Init(uint supply)
Initialize a Linkgraph job node.
Pool< LinkGraphJob, LinkGraphJobID, 32, 0xFFFF > LinkGraphJobPool
Type of the pool for link graph jobs.
void AddFlow(uint flow)
Add some flow.
NodeID GetNode() const
Get the node this leg passes.