From 22f56ffdd7b106b0fd080e1dc4adc957e1b356ea Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Sun, 9 Jun 2013 12:57:41 +0000 Subject: (svn r25353) -Add: link graph job implementation --- src/linkgraph/linkgraphjob.cpp | 185 ++++++++++++++++++ src/linkgraph/linkgraphjob.h | 413 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 598 insertions(+) create mode 100644 src/linkgraph/linkgraphjob.cpp create mode 100644 src/linkgraph/linkgraphjob.h (limited to 'src') diff --git a/src/linkgraph/linkgraphjob.cpp b/src/linkgraph/linkgraphjob.cpp new file mode 100644 index 000000000..fc94d49cc --- /dev/null +++ b/src/linkgraph/linkgraphjob.cpp @@ -0,0 +1,185 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * 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. + * 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. + * 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 . + */ + +/** @file linkgraphjob.cpp Definition of link graph job classes used for cargo distribution. */ + +#include "../stdafx.h" +#include "../core/pool_func.hpp" +#include "../window_func.h" +#include "linkgraphjob.h" + +/* Initialize the link-graph-job-pool */ +LinkGraphJobPool _link_graph_job_pool("LinkGraphJob"); +INSTANTIATE_POOL_METHODS(LinkGraphJob) + +/** + * Create a link graph job from a link graph. The link graph will be copied so + * that the calculations don't interfer with the normal operations on the + * original. The job is immediately started. + * @param orig Original LinkGraph to be copied. + */ +LinkGraphJob::LinkGraphJob(const LinkGraph &orig) : + /* Copying the link graph here also copies its index member. + * This is on purpose. */ + link_graph(orig), + settings(_settings_game.linkgraph), + thread(NULL), + join_date(_date + _settings_game.linkgraph.recalc_time) +{ +} + +/** + * Join the link graph job and destroy it. + */ +LinkGraphJob::~LinkGraphJob() +{ + assert(this->thread == NULL); + + /* Link graph has been merged into another one. */ + if (!LinkGraph::IsValidID(this->link_graph.index)) return; + + uint size = this->Size(); + for (NodeID node_id = 0; node_id < size; ++node_id) { + Node from = (*this)[node_id]; + + /* The station can have been deleted. */ + Station *st = Station::GetIfValid(from.Station()); + if (st == NULL) continue; + + /* Link graph merging and station deletion may change around IDs. Make + * sure that everything is still consistent or ignore it otherwise. */ + GoodsEntry &ge = st->goods[this->Cargo()]; + if (ge.link_graph != this->link_graph.index || ge.node != node_id) continue; + + LinkGraph *lg = LinkGraph::Get(ge.link_graph); + FlowStatMap &flows = from.Flows(); + + for (EdgeIterator it(from.Begin()); it != from.End(); ++it) { + if (from[it->first].Flow() == 0) continue; + StationID to = (*this)[it->first].Station(); + Station *st2 = Station::GetIfValid(to); + if (st2 == NULL || st2->goods[this->Cargo()].link_graph != this->link_graph.index || + st2->goods[this->Cargo()].node != it->first || + (*lg)[node_id][it->first].LastUpdate() == INVALID_DATE) { + /* Edge has been removed. Delete flows. */ + flows.DeleteFlows(to); + } + } + + ge.flows.swap(flows); + InvalidateWindowData(WC_STATION_VIEW, st->index, this->Cargo()); + } +} + +/** + * Initialize the link graph job: Resize nodes and edges and populate them. + * This is done after the constructor so that we can do it in the calculation + * thread without delaying the main game. + */ +void LinkGraphJob::Init() +{ + uint size = this->Size(); + this->nodes.Resize(size); + this->edges.Resize(size, size); + for (uint i = 0; i < size; ++i) { + this->nodes[i].Init(this->link_graph[i].Supply()); + EdgeAnnotation *node_edges = this->edges[i]; + for (uint j = 0; j < size; ++j) { + node_edges[j].Init(); + } + } +} + +/** + * Initialize a linkgraph job edge. + */ +void LinkGraphJob::EdgeAnnotation::Init() +{ + this->demand = 0; + this->flow = 0; + this->unsatisfied_demand = 0; +} + +/** + * Initialize a Linkgraph job node. The underlying memory is expected to be + * freshly allocated, without any constructors having been called. + * @param supply Initial undelivered supply. + */ +void LinkGraphJob::NodeAnnotation::Init(uint supply) +{ + this->undelivered_supply = supply; + new (&this->flows) FlowStatMap; + new (&this->paths) PathList; +} + +/** + * Add this path as a new child to the given base path, thus making this path + * a "fork" of the base path. + * @param base Path to fork from. + * @param cap Maximum capacity of the new leg. + * @param free_cap Remaining free capacity of the new leg. + * @param dist Distance of the new leg. + */ +void Path::Fork(Path *base, uint cap, int free_cap, uint dist) +{ + this->capacity = min(base->capacity, cap); + this->free_capacity = min(base->free_capacity, free_cap); + this->distance = base->distance + dist; + assert(this->distance > 0); + if (this->parent != base) { + this->Detach(); + this->parent = base; + this->parent->num_children++; + } + this->origin = base->origin; +} + +/** + * Push some flow along a path and register the path in the nodes it passes if + * successful. + * @param new_flow Amount of flow to push. + * @param job Link graph job this node belongs to. + * @param max_saturation Maximum saturation of edges. + * @return Amount of flow actually pushed. + */ +uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation) +{ + if (this->parent != NULL) { + LinkGraphJob::Edge edge = job[this->parent->node][this->node]; + if (max_saturation != UINT_MAX) { + uint usable_cap = edge.Capacity() * max_saturation / 100; + if (usable_cap > edge.Flow()) { + new_flow = min(new_flow, usable_cap - edge.Flow()); + } else { + return 0; + } + } + new_flow = this->parent->AddFlow(new_flow, job, max_saturation); + if (this->flow == 0 && new_flow > 0) { + job[this->parent->node].Paths().push_back(this); + } + edge.AddFlow(new_flow); + } + this->flow += new_flow; + return new_flow; +} + +/** + * Create a leg of a path in the link graph. + * @param n Id of the link graph node this path passes. + * @param source If true, this is the first leg of the path. + */ +Path::Path(NodeID n, bool source) : + distance(source ? 0 : UINT_MAX), + capacity(0), + free_capacity(source ? INT_MAX : INT_MIN), + flow(0), node(n), origin(source ? n : INVALID_NODE), + num_children(0), parent(NULL) +{} + diff --git a/src/linkgraph/linkgraphjob.h b/src/linkgraph/linkgraphjob.h new file mode 100644 index 000000000..f54270e6d --- /dev/null +++ b/src/linkgraph/linkgraphjob.h @@ -0,0 +1,413 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * 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. + * 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. + * 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 . + */ + +/** @file linkgraph.h Declaration of link graph job classes used for cargo distribution. */ + +#ifndef LINKGRAPHJOB_H +#define LINKGRAPHJOB_H + +#include "../thread/thread.h" +#include "linkgraph.h" +#include + +class LinkGraphJob; +class Path; +typedef std::list PathList; + +/** Type of the pool for link graph jobs. */ +typedef Pool LinkGraphJobPool; +/** The actual pool with link graph jobs. */ +extern LinkGraphJobPool _link_graph_job_pool; + +/** + * Class for calculation jobs to be run on link graphs. + */ +class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool>{ +private: + /** + * Annotation for a link graph edge. + */ + struct EdgeAnnotation { + uint demand; ///< Transport demand between the nodes. + uint unsatisfied_demand; ///< Demand over this edge that hasn't been satisfied yet. + uint flow; ///< Planned flow over this edge. + void Init(); + }; + + /** + * Annotation for a link graph node. + */ + struct NodeAnnotation { + uint undelivered_supply; ///< Amount of supply that hasn't been distributed yet. + PathList paths; ///< Paths through this node. + FlowStatMap flows; ///< Planned flows to other nodes. + void Init(uint supply); + }; + + typedef SmallVector NodeAnnotationVector; + typedef SmallMatrix EdgeAnnotationMatrix; + + friend const SaveLoad *GetLinkGraphJobDesc(); + friend class LinkGraphSchedule; + +protected: + const LinkGraph link_graph; ///< Link graph to by analyzed. Is copied when job is started and mustn't be modified later. + const LinkGraphSettings settings; ///< Copy of _settings_game.linkgraph at spawn time. + ThreadObject *thread; ///< Thread the job is running in or NULL if it's running in the main thread. + const Date join_date; ///< Date when the job is to be joined. + NodeAnnotationVector nodes; ///< Extra node data necessary for link graph calculation. + EdgeAnnotationMatrix edges; ///< Extra edge data necessary for link graph calculation. + +public: + + /** + * A job edge. Wraps a link graph edge and an edge annotation. The + * annotation can be modified, the edge is constant. + */ + class Edge : public LinkGraph::ConstEdge { + private: + EdgeAnnotation &anno; ///< Annotation being wrapped. + public: + /** + * Constructor. + * @param edge Link graph edge to be wrapped. + * @param anno Annotation to be wrapped. + */ + Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno) : + LinkGraph::ConstEdge(edge), anno(anno) {} + + /** + * Get the transport demand between end the points of the edge. + * @return Demand. + */ + uint Demand() const { return this->anno.demand; } + + /** + * Get the transport demand that hasn't been satisfied by flows, yet. + * @return Unsatisfied demand. + */ + uint UnsatisfiedDemand() const { return this->anno.unsatisfied_demand; } + + /** + * Get the total flow on the edge. + * @return Flow. + */ + uint Flow() const { return this->anno.flow; } + + /** + * Add some flow. + * @param flow Flow to be added. + */ + void AddFlow(uint flow) { this->anno.flow += flow; } + + /** + * Remove some flow. + * @param flow Flow to be removed. + */ + void RemoveFlow(uint flow) + { + assert(flow <= this->anno.flow); + this->anno.flow -= flow; + } + + /** + * Add some (not yet satisfied) demand. + * @param demand Demand to be added. + */ + void AddDemand(uint demand) + { + this->anno.demand += demand; + this->anno.unsatisfied_demand += demand; + } + + /** + * Satisfy some demand. + * @param demand Demand to be satisfied. + */ + void SatisfyDemand(uint demand) + { + assert(demand <= this->anno.unsatisfied_demand); + this->anno.unsatisfied_demand -= demand; + } + }; + + /** + * Iterator for job edges. + */ + class EdgeIterator : public LinkGraph::BaseEdgeIterator { + EdgeAnnotation *base_anno; ///< Array of annotations to be (indirectly) iterated. + public: + /** + * Constructor. + * @param base Array of edges to be iterated. + * @param base_anno Array of annotations to be iterated. + * @param current Start offset of iteration. + */ + EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current) : + LinkGraph::BaseEdgeIterator(base, current), + base_anno(base_anno) {} + + /** + * Dereference. + * @return Pair of the edge currently pointed to and the ID of its + * other end. + */ + SmallPair operator*() const + { + return SmallPair(this->current, Edge(this->base[this->current], this->base_anno[this->current])); + } + + /** + * Dereference. Has to be repeated here as operator* is different than + * in LinkGraph::EdgeWrapper. + * @return Fake pointer to pair of NodeID/Edge. + */ + FakePointer operator->() const { + return FakePointer(this->operator*()); + } + }; + + /** + * Link graph job node. Wraps a constant link graph node and a modifiable + * node annotation. + */ + class Node : public LinkGraph::ConstNode { + private: + NodeAnnotation &node_anno; ///< Annotation being wrapped. + EdgeAnnotation *edge_annos; ///< Edge annotations belonging to this node. + public: + + /** + * Constructor. + * @param lgj Job to take the node from. + * @param node ID of the node. + */ + Node (LinkGraphJob *lgj, NodeID node) : + LinkGraph::ConstNode(&lgj->link_graph, node), + node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node]) + {} + + /** + * Retrieve an edge starting at this node. Mind that this returns an + * object, not a reference. + * @param to Remote end of the edge. + * @return Edge between this node and "to". + */ + Edge operator[](NodeID to) const { return Edge(this->edges[to], this->edge_annos[to]); } + + /** + * Iterator for the "begin" of the edge array. Only edges with capacity + * are iterated. The others are skipped. + * @return Iterator pointing to the first edge. + */ + EdgeIterator Begin() const { return EdgeIterator(this->edges, this->edge_annos, index); } + + /** + * Iterator for the "end" of the edge array. Only edges with capacity + * are iterated. The others are skipped. + * @return Iterator pointing beyond the last edge. + */ + EdgeIterator End() const { return EdgeIterator(this->edges, this->edge_annos, INVALID_NODE); } + + /** + * Get amount of supply that hasn't been delivered, yet. + * @return Undelivered supply. + */ + uint UndeliveredSupply() const { return this->node_anno.undelivered_supply; } + + /** + * Get the flows running through this node. + * @return Flows. + */ + FlowStatMap &Flows() { return this->node_anno.flows; } + + /** + * Get a constant version of the flows running through this node. + * @return Flows. + */ + const FlowStatMap &Flows() const { return this->node_anno.flows; } + + /** + * Get the paths this node is part of. + * @return Paths. + */ + PathList &Paths() { return this->node_anno.paths; } + + /** + * Get a constant version of the paths this node is part of. + * @return Paths. + */ + const PathList &Paths() const { return this->node_anno.paths; } + + /** + * Deliver some supply, adding demand to the respective edge. + * @param to Destination for supply. + * @param amount Amount of supply to be delivered. + */ + void DeliverSupply(NodeID to, uint amount) + { + this->node_anno.undelivered_supply -= amount; + (*this)[to].AddDemand(amount); + } + }; + + /** + * Bare constructor, only for save/load. link_graph, join_date and actually + * settings have to be brutally const-casted in order to populate them. + */ + LinkGraphJob() : settings(_settings_game.linkgraph), thread(NULL), + join_date(INVALID_DATE) {} + + LinkGraphJob(const LinkGraph &orig); + ~LinkGraphJob(); + + void Init(); + + /** + * Check if job is supposed to be finished. + * @return True if job should be finished by now, false if not. + */ + inline bool IsFinished() const { return this->join_date <= _date; } + + /** + * Get the date when the job should be finished. + * @return Join date. + */ + inline Date JoinDate() const { return join_date; } + + /** + * Get the link graph settings for this component. + * @return Settings. + */ + inline const LinkGraphSettings &Settings() const { return this->settings; } + + /** + * Get a node abstraction with the specified id. + * @param num ID of the node. + * @return the Requested node. + */ + inline Node operator[](NodeID num) { return Node(this, num); } + + /** + * Get the size of the underlying link graph. + * @return Size. + */ + inline uint Size() const { return this->link_graph.Size(); } + + /** + * Get the cargo of the underlying link graph. + * @return Cargo. + */ + inline CargoID Cargo() const { return this->link_graph.Cargo(); } + + /** + * Get the date when the underlying link graph was last compressed. + * @return Compression date. + */ + inline Date LastCompression() const { return this->link_graph.LastCompression(); } + + /** + * Get the ID of the underlying link graph. + * @return Link graph ID. + */ + inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; } + + /** + * Get a reference to the underlying link graph. Only use this for save/load. + * @return Link graph. + */ + inline const LinkGraph &Graph() const { return this->link_graph; } +}; + +#define FOR_ALL_LINK_GRAPH_JOBS(var) FOR_ALL_ITEMS_FROM(LinkGraphJob, link_graph_job_index, var, 0) + +/** + * A leg of a path in the link graph. Paths can form trees by being "forked". + */ +class Path { +public: + Path(NodeID n, bool source = false); + + /** Get the node this leg passes. */ + inline NodeID GetNode() const { return this->node; } + + /** Get the overall origin of the path. */ + inline NodeID GetOrigin() const { return this->origin; } + + /** Get the parent leg of this one. */ + inline Path *GetParent() { return this->parent; } + + /** Get the overall capacity of the path. */ + inline uint GetCapacity() const { return this->capacity; } + + /** Get the free capacity of the path. */ + inline int GetFreeCapacity() const { return this->free_capacity; } + + /** + * Get ratio of free * 16 (so that we get fewer 0) / + * total capacity + 1 (so that we don't divide by 0). + * @param free Free capacity. + * @param total Total capacity. + * @return free * 16 / (total + 1). + */ + inline static int GetCapacityRatio(int free, int total) + { + return (free << 4) / (total + 1); + } + + /** + * Get capacity ratio of this path. + * @return free capacity * 16 / (total capacity + 1). + */ + inline int GetCapacityRatio() const + { + return Path::GetCapacityRatio(this->free_capacity, this->capacity); + } + + /** Get the overall distance of the path. */ + inline uint GetDistance() const { return this->distance; } + + /** Reduce the flow on this leg only by the specified amount. */ + inline void ReduceFlow(uint f) { this->flow -= f; } + + /** Increase the flow on this leg only by the specified amount. */ + inline void AddFlow(uint f) { this->flow += f; } + + /** Get the flow on this leg. */ + inline uint GetFlow() const { return this->flow; } + + /** Get the number of "forked off" child legs of this one. */ + inline uint GetNumChildren() const { return this->num_children; } + + /** + * Detach this path from its parent. + */ + inline void Detach() + { + if (this->parent != NULL) { + this->parent->num_children--; + this->parent = NULL; + } + } + + uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation); + void Fork(Path *base, uint cap, int free_cap, uint dist); + +protected: + uint distance; ///< Sum(distance of all legs up to this one). + uint capacity; ///< This capacity is min(capacity) fom all edges. + int free_capacity; ///< This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra. + uint flow; ///< Flow the current run of the mcf solver assigns. + NodeID node; ///< Link graph node this leg passes. + NodeID origin; ///< Link graph node this path originates from. + uint num_children; ///< Number of child legs that have been forked from this path. + Path *parent; ///< Parent leg of this one. +}; + +#endif /* LINKGRAPHJOB_H */ -- cgit v1.2.3-54-g00ecf