OpenTTD
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 <list>
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 private:
34  struct EdgeAnnotation {
35  uint demand;
37  uint flow;
38  void Init();
39  };
40 
44  struct NodeAnnotation {
46  PathList paths;
48  void Init(uint supply);
49  };
50 
51  typedef std::vector<NodeAnnotation> NodeAnnotationVector;
53 
54  friend const SaveLoad *GetLinkGraphJobDesc();
55  friend class LinkGraphSchedule;
56 
57 protected:
60  std::thread thread;
62  NodeAnnotationVector nodes;
63  EdgeAnnotationMatrix edges;
64 
65  void EraseFlows(NodeID from);
66  void JoinThread();
67  void SpawnThread();
68 
69 public:
70 
75  class Edge : public LinkGraph::ConstEdge {
76  private:
78  public:
84  Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno) :
85  LinkGraph::ConstEdge(edge), anno(anno) {}
86 
91  uint Demand() const { return this->anno.demand; }
92 
97  uint UnsatisfiedDemand() const { return this->anno.unsatisfied_demand; }
98 
103  uint Flow() const { return this->anno.flow; }
104 
109  void AddFlow(uint flow) { this->anno.flow += flow; }
110 
115  void RemoveFlow(uint flow)
116  {
117  assert(flow <= this->anno.flow);
118  this->anno.flow -= flow;
119  }
120 
125  void AddDemand(uint demand)
126  {
127  this->anno.demand += demand;
128  this->anno.unsatisfied_demand += demand;
129  }
130 
136  {
137  assert(demand <= this->anno.unsatisfied_demand);
138  this->anno.unsatisfied_demand -= demand;
139  }
140  };
141 
145  class EdgeIterator : public LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator> {
147  public:
154  EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current) :
155  LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, current),
156  base_anno(base_anno) {}
157 
164  {
165  return SmallPair<NodeID, Edge>(this->current, Edge(this->base[this->current], this->base_anno[this->current]));
166  }
167 
173  FakePointer operator->() const {
174  return FakePointer(this->operator*());
175  }
176  };
177 
182  class Node : public LinkGraph::ConstNode {
183  private:
186  public:
187 
193  Node (LinkGraphJob *lgj, NodeID node) :
194  LinkGraph::ConstNode(&lgj->link_graph, node),
195  node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node])
196  {}
197 
204  Edge operator[](NodeID to) const { return Edge(this->edges[to], this->edge_annos[to]); }
205 
211  EdgeIterator Begin() const { return EdgeIterator(this->edges, this->edge_annos, index); }
212 
218  EdgeIterator End() const { return EdgeIterator(this->edges, this->edge_annos, INVALID_NODE); }
219 
224  uint UndeliveredSupply() const { return this->node_anno.undelivered_supply; }
225 
230  FlowStatMap &Flows() { return this->node_anno.flows; }
231 
236  const FlowStatMap &Flows() const { return this->node_anno.flows; }
237 
243  PathList &Paths() { return this->node_anno.paths; }
244 
249  const PathList &Paths() const { return this->node_anno.paths; }
250 
256  void DeliverSupply(NodeID to, uint amount)
257  {
258  this->node_anno.undelivered_supply -= amount;
259  (*this)[to].AddDemand(amount);
260  }
261  };
262 
267  LinkGraphJob() : settings(_settings_game.linkgraph),
268  join_date(INVALID_DATE) {}
269 
270  LinkGraphJob(const LinkGraph &orig);
271  ~LinkGraphJob();
272 
273  void Init();
274 
279  inline bool IsFinished() const { return this->join_date <= _date; }
280 
285  inline Date JoinDate() const { return join_date; }
286 
291  inline void ShiftJoinDate(int interval) { this->join_date += interval; }
292 
297  inline const LinkGraphSettings &Settings() const { return this->settings; }
298 
304  inline Node operator[](NodeID num) { return Node(this, num); }
305 
310  inline uint Size() const { return this->link_graph.Size(); }
311 
316  inline CargoID Cargo() const { return this->link_graph.Cargo(); }
317 
322  inline Date LastCompression() const { return this->link_graph.LastCompression(); }
323 
328  inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }
329 
334  inline const LinkGraph &Graph() const { return this->link_graph; }
335 };
336 
340 class Path {
341 public:
343 
344  Path(NodeID n, bool source = false);
345 
347  inline NodeID GetNode() const { return this->node; }
348 
350  inline NodeID GetOrigin() const { return this->origin; }
351 
353  inline Path *GetParent() { return this->parent; }
354 
356  inline uint GetCapacity() const { return this->capacity; }
357 
359  inline int GetFreeCapacity() const { return this->free_capacity; }
360 
368  inline static int GetCapacityRatio(int free, uint total)
369  {
370  return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / max(total, 1U);
371  }
372 
377  inline int GetCapacityRatio() const
378  {
379  return Path::GetCapacityRatio(this->free_capacity, this->capacity);
380  }
381 
383  inline uint GetDistance() const { return this->distance; }
384 
386  inline void ReduceFlow(uint f) { this->flow -= f; }
387 
389  inline void AddFlow(uint f) { this->flow += f; }
390 
392  inline uint GetFlow() const { return this->flow; }
393 
395  inline uint GetNumChildren() const { return this->num_children; }
396 
400  inline void Detach()
401  {
402  if (this->parent != nullptr) {
403  this->parent->num_children--;
404  this->parent = nullptr;
405  }
406  }
407 
408  uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
409  void Fork(Path *base, uint cap, int free_cap, uint dist);
410 
411 protected:
412 
417  PATH_CAP_MULTIPLIER = 16,
418  PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
419  PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
420  };
421 
422  uint distance;
423  uint capacity;
425  uint flow;
426  NodeID node;
427  NodeID origin;
430 };
431 
432 #endif /* LINKGRAPHJOB_H */
Constant node class.
Definition: linkgraph.h:337
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:79
void Init()
Initialize a linkgraph job edge.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:424
std::thread thread
Thread the job is running in or a default-constructed thread if it&#39;s running in the main thread...
Definition: linkgraphjob.h:60
A job edge.
Definition: linkgraphjob.h:75
An edge in the link graph.
Definition: linkgraph.h:61
Annotation for a link graph edge.
Definition: linkgraphjob.h:34
FakePointer operator->() const
Dereference.
Definition: linkgraphjob.h:173
uint undelivered_supply
Amount of supply that hasn&#39;t been distributed yet.
Definition: linkgraphjob.h:45
uint Flow() const
Get the total flow on the edge.
Definition: linkgraphjob.h:103
CargoID Cargo() const
Get the cargo ID this component&#39;s link graph refers to.
Definition: linkgraph.h:509
Node operator[](NodeID num)
Get a node abstraction with the specified id.
Definition: linkgraphjob.h:304
Pool< LinkGraphJob, LinkGraphJobID, 32, 0xFFFF > LinkGraphJobPool
Type of the pool for link graph jobs.
Definition: linkgraphjob.h:22
EdgeAnnotation * edge_annos
Edge annotations belonging to this node.
Definition: linkgraphjob.h:185
uint GetCapacity() const
Get the overall capacity of the path.
Definition: linkgraphjob.h:356
uint demand
Transport demand between the nodes.
Definition: linkgraphjob.h:35
FlowStatMap flows
Planned flows to other nodes.
Definition: linkgraphjob.h:47
uint flow
Planned flow over this edge.
Definition: linkgraphjob.h:37
Tindex index
Index of this pool item.
Definition: pool_type.hpp:189
const PathList & Paths() const
Get a constant version of the paths this node is part of.
Definition: linkgraphjob.h:249
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:389
void ShiftJoinDate(int interval)
Change the join date on date cheating.
Definition: linkgraphjob.h:291
Date LastCompression() const
Get the date when the underlying link graph was last compressed.
Definition: linkgraphjob.h:322
static T max(const T a, const T b)
Returns the maximum of two values.
Definition: math_func.hpp:24
NodeID GetOrigin() const
Get the overall origin of the path.
Definition: linkgraphjob.h:350
A connected component of a link graph.
Definition: linkgraph.h:38
Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno)
Constructor.
Definition: linkgraphjob.h:84
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:297
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
Definition: linkgraphjob.h:395
uint Size() const
Get the current size of the component.
Definition: linkgraph.h:497
uint unsatisfied_demand
Demand over this edge that hasn&#39;t been satisfied yet.
Definition: linkgraphjob.h:36
Simple pair of data.
uint GetFlow() const
Get the flow on this leg.
Definition: linkgraphjob.h:392
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
Definition: linkgraphjob.h:59
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:422
NodeID GetNode() const
Get the node this leg passes.
Definition: linkgraphjob.h:347
static const Date INVALID_DATE
Representation of an invalid date.
Definition: date_type.h:108
A leg of a path in the link graph.
Definition: linkgraphjob.h:340
uint num_children
Number of child legs that have been forked from this path.
Definition: linkgraphjob.h:428
void SatisfyDemand(uint demand)
Satisfy some demand.
Definition: linkgraphjob.h:135
int GetCapacityRatio() const
Get capacity ratio of this path.
Definition: linkgraphjob.h:377
Link graph job node.
Definition: linkgraphjob.h:182
PathList & Paths()
Get the paths this node is part of.
Definition: linkgraphjob.h:243
Node(LinkGraphJob *lgj, NodeID node)
Constructor.
Definition: linkgraphjob.h:193
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:342
void DeliverSupply(NodeID to, uint amount)
Deliver some supply, adding demand to the respective edge.
Definition: linkgraphjob.h:256
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:386
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:423
Date JoinDate() const
Get the date when the job should be finished.
Definition: linkgraphjob.h:285
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
Wrapper for an edge (const or not) allowing retrieval, but no modification.
Definition: linkgraph.h:75
Date LastCompression() const
Get date of last compression.
Definition: linkgraph.h:503
NodeID origin
Link graph node this path originates from.
Definition: linkgraphjob.h:427
Edge operator[](NodeID to) const
Retrieve an edge starting at this node.
Definition: linkgraphjob.h:204
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&#39;t divide by ...
Definition: linkgraphjob.h:368
void AddFlow(uint flow)
Add some flow.
Definition: linkgraphjob.h:109
Base class for all PoolItems.
Definition: pool_type.hpp:188
uint UnsatisfiedDemand() const
Get the transport demand that hasn&#39;t been satisfied by flows, yet.
Definition: linkgraphjob.h:97
Base class for iterating across outgoing edges of a node.
Definition: linkgraph.h:180
int GetFreeCapacity() const
Get the free capacity of the path.
Definition: linkgraphjob.h:359
Base class for all pools.
Definition: pool_type.hpp:82
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:316
static T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Definition: math_func.hpp:137
void RemoveFlow(uint flow)
Remove some flow.
Definition: linkgraphjob.h:115
NodeID node
Link graph node this leg passes.
Definition: linkgraphjob.h:426
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn&#39;t be modified later.
Definition: linkgraphjob.h:58
FlowStatMap & Flows()
Get the flows running through this node.
Definition: linkgraphjob.h:230
uint GetDistance() const
Get the overall distance of the path.
Definition: linkgraphjob.h:383
bool IsFinished() const
Check if job is supposed to be finished.
Definition: linkgraphjob.h:279
EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current)
Constructor.
Definition: linkgraphjob.h:154
PathList paths
Paths through this node, sorted so that those with flow == 0 are in the back.
Definition: linkgraphjob.h:46
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
void JoinThread()
Join the calling thread with this job&#39;s thread if threading is enabled.
NodeAnnotation & node_anno
Annotation being wrapped.
Definition: linkgraphjob.h:184
void Detach()
Detach this path from its parent.
Definition: linkgraphjob.h:400
uint flow
Flow the current run of the mcf solver assigns.
Definition: linkgraphjob.h:425
PathCapacityBoundaries
Some boundaries to clamp against in order to avoid integer overflows.
Definition: linkgraphjob.h:416
EdgeIterator End() const
Iterator for the "end" of the edge array.
Definition: linkgraphjob.h:218
Date join_date
Date when the job is to be joined.
Definition: linkgraphjob.h:61
Iterator for job edges.
Definition: linkgraphjob.h:145
const FlowStatMap & Flows() const
Get a constant version of the flows running through this node.
Definition: linkgraphjob.h:236
uint Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:310
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
Definition: linkgraphjob.h:334
LinkGraphJob()
Bare constructor, only for save/load.
Definition: linkgraphjob.h:267
friend const SaveLoad * GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
Definition: linkgraphjob.h:328
Flow descriptions by origin stations.
Definition: station_base.h:152
Declaration of link graph classes used for cargo distribution.
int32 Date
The type to store our dates in.
Definition: date_type.h:14
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: depend.cpp:129
EdgeAnnotationMatrix edges
Extra edge data necessary for link graph calculation.
Definition: linkgraphjob.h:63
EdgeAnnotation & anno
Annotation being wrapped.
Definition: linkgraphjob.h:77
SaveLoad type struct.
Definition: saveload.h:496
uint UndeliveredSupply() const
Get amount of supply that hasn&#39;t been delivered, yet.
Definition: linkgraphjob.h:224
byte CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:20
Path * GetParent()
Get the parent leg of this one.
Definition: linkgraphjob.h:353
SmallPair< NodeID, Edge > operator*() const
Dereference.
Definition: linkgraphjob.h:163
Date _date
Current date in days (day counter)
Definition: date.cpp:26
EdgeAnnotation * base_anno
Array of annotations to be (indirectly) iterated.
Definition: linkgraphjob.h:146
void AddDemand(uint demand)
Add some (not yet satisfied) demand.
Definition: linkgraphjob.h:125
Path * parent
Parent leg of this one.
Definition: linkgraphjob.h:429
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
Definition: linkgraphjob.h:62
EdgeIterator Begin() const
Iterator for the "begin" of the edge array.
Definition: linkgraphjob.h:211
~LinkGraphJob()
Join the link graph job and destroy it.
uint Demand() const
Get the transport demand between end the points of the edge.
Definition: linkgraphjob.h:91
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:29
Annotation for a link graph node.
Definition: linkgraphjob.h:44