From 957f5ca11758d556763881d04ced39cd34c470c1 Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Sat, 14 Jun 2014 13:35:39 +0000 Subject: (svn r26646) -Fix [FS#6041]: Save locations instead of distances in link graphs to reduce size. --- src/linkgraph/demands.cpp | 3 ++- src/linkgraph/linkgraph.cpp | 30 +++++++----------------------- src/linkgraph/linkgraph.h | 28 ++++++++++++++++++---------- src/linkgraph/mcf.cpp | 3 +-- 4 files changed, 28 insertions(+), 36 deletions(-) (limited to 'src/linkgraph') diff --git a/src/linkgraph/demands.cpp b/src/linkgraph/demands.cpp index c16288123..2c88778ab 100644 --- a/src/linkgraph/demands.cpp +++ b/src/linkgraph/demands.cpp @@ -210,7 +210,8 @@ void DemandCalculator::CalcDemand(LinkGraphJob &job, Tscaler scaler) /* Scale the distance by mod_dist around max_distance */ int32 distance = this->max_distance - (this->max_distance - - (int32)job[from_id][to_id].Distance()) * this->mod_dist / 100; + (int32)DistanceMaxPlusManhattan(job[from_id].XY(), job[to_id].XY())) * + this->mod_dist / 100; /* Scale the accuracy by distance around accuracy / 2 */ int32 divisor = this->accuracy * (this->mod_dist - 50) / 100 + diff --git a/src/linkgraph/linkgraph.cpp b/src/linkgraph/linkgraph.cpp index 01b3d1ee2..50945d361 100644 --- a/src/linkgraph/linkgraph.cpp +++ b/src/linkgraph/linkgraph.cpp @@ -21,11 +21,13 @@ INSTANTIATE_POOL_METHODS(LinkGraph) /** * Create a node or clear it. + * @param xy Location of the associated station. * @param st ID of the associated station. * @param demand Demand for cargo at the station. */ -inline void LinkGraph::BaseNode::Init(StationID st, uint demand) +inline void LinkGraph::BaseNode::Init(TileIndex xy, StationID st, uint demand) { + this->xy = xy; this->supply = 0; this->demand = demand; this->station = st; @@ -34,11 +36,9 @@ inline void LinkGraph::BaseNode::Init(StationID st, uint demand) /** * Create an edge. - * @param distance Length of the link as manhattan distance. */ -inline void LinkGraph::BaseEdge::Init(uint distance) +inline void LinkGraph::BaseEdge::Init() { - this->distance = distance; this->capacity = 0; this->usage = 0; this->last_unrestricted_update = INVALID_DATE; @@ -146,21 +146,6 @@ void LinkGraph::RemoveNode(NodeID id) * been copied around in the loop above. */ } -/** - * Update distances between the given node and all others. - * @param id Node that changed position. - * @param xy New position of the node. - */ -void LinkGraph::UpdateDistances(NodeID id, TileIndex xy) -{ - assert(id < this->Size()); - for (NodeID other = 0; other < this->Size(); ++other) { - if (other == id) continue; - this->edges[id][other].distance = this->edges[other][id].distance = - DistanceMaxPlusManhattan(xy, Station::Get(this->nodes[other].station)->xy); - } -} - /** * Add a node to the component and create empty edges associated with it. Set * the station's last_component to this component. Calculate the distances to all @@ -180,7 +165,7 @@ NodeID LinkGraph::AddNode(const Station *st) this->edges.Resize(new_node + 1U, max(new_node + 1U, this->edges.Height())); - this->nodes[new_node].Init(st->index, + this->nodes[new_node].Init(st->xy, st->index, HasBit(good.status, GoodsEntry::GES_ACCEPTANCE)); BaseEdge *new_edges = this->edges[new_node]; @@ -189,9 +174,8 @@ NodeID LinkGraph::AddNode(const Station *st) new_edges[new_node].next_edge = INVALID_NODE; for (NodeID i = 0; i <= new_node; ++i) { - uint distance = DistanceMaxPlusManhattan(st->xy, Station::Get(this->nodes[i].station)->xy); - new_edges[i].Init(distance); - this->edges[i][new_node].Init(distance); + new_edges[i].Init(); + this->edges[i][new_node].Init(); } return new_node; } diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h index 7aaa1901d..799f22c78 100644 --- a/src/linkgraph/linkgraph.h +++ b/src/linkgraph/linkgraph.h @@ -49,8 +49,9 @@ public: uint supply; ///< Supply at the station. uint demand; ///< Acceptance at the station. StationID station; ///< Station ID. + TileIndex xy; ///< Location of the station referred to by the node. Date last_update; ///< When the supply was last updated. - void Init(StationID st = INVALID_STATION, uint demand = 0); + void Init(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0); }; /** @@ -60,13 +61,12 @@ public: * the column as next_edge. */ struct BaseEdge { - uint distance; ///< Length of the link. uint capacity; ///< Capacity of the link. uint usage; ///< Usage of the link. Date last_unrestricted_update; ///< When the unrestricted part of the link was last updated. Date last_restricted_update; ///< When the restricted part of the link was last updated. NodeID next_edge; ///< Destination of next valid edge starting at the same source node. - void Init(uint distance = 0); + void Init(); }; /** @@ -98,12 +98,6 @@ public: */ uint Usage() const { return this->edge.usage; } - /** - * Get edge's distance. - * @return Distance. - */ - uint Distance() const { return this->edge.distance; } - /** * Get the date of the last update to the edge's unrestricted capacity. * @return Last update. @@ -169,6 +163,12 @@ public: * @return Last update. */ Date LastUpdate() const { return this->node.last_update; } + + /** + * Get the location of the station associated with the node. + * @return Location of the station. + */ + TileIndex XY() const { return this->node.xy; } }; /** @@ -412,6 +412,15 @@ public: this->node.last_update = _date; } + /** + * Update the node's location on the map. + * @param xy New location. + */ + void UpdateLocation(TileIndex xy) + { + this->node.xy = xy; + } + /** * Set the node's demand. * @param demand New demand for the node. @@ -513,7 +522,6 @@ public: NodeID AddNode(const Station *st); void RemoveNode(NodeID id); - void UpdateDistances(NodeID id, TileIndex xy); protected: friend class LinkGraph::ConstNode; diff --git a/src/linkgraph/mcf.cpp b/src/linkgraph/mcf.cpp index 3163ec9e3..81d4d6d38 100644 --- a/src/linkgraph/mcf.cpp +++ b/src/linkgraph/mcf.cpp @@ -259,7 +259,6 @@ void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths) for (NodeID to = iter.Next(); to != INVALID_NODE; to = iter.Next()) { if (to == from) continue; // Not a real edge but a consumption sign. Edge edge = this->job[from][to]; - assert(edge.Distance() < UINT_MAX); uint capacity = edge.Capacity(); if (this->max_saturation != UINT_MAX) { capacity *= this->max_saturation; @@ -267,7 +266,7 @@ void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths) if (capacity == 0) capacity = 1; } /* punish in-between stops a little */ - uint distance = edge.Distance() + 1; + uint distance = DistanceMaxPlusManhattan(this->job[from].XY(), this->job[to].XY()) + 1; Tannotation *dest = static_cast(paths[to]); if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance)) { annos.erase(dest); -- cgit v1.2.3-54-g00ecf