Changeset - r26920:e212d9198e19
Parent rev.
Child rev.
[Not reviewed]
master
0 9 0
Michael Lutz - 23 months ago 2023-01-02 20:46:49
michi@icosahedron.de
Codechange: [Linkgraph] Only store present link graph edges and not all possible edges.
9 files changed with 152 insertions and 145 deletions:
src/linkgraph/linkgraph.cpp
27
75
src/linkgraph/linkgraph.h
60
28
src/linkgraph/linkgraph_gui.cpp
2
2
src/linkgraph/linkgraphjob.cpp
2
1
src/linkgraph/linkgraphjob.h
12
7
src/saveload/linkgraph_sl.cpp
40
28
src/saveload/saveload.h
2
src/station.cpp
1
1
src/station_cmd.cpp
6
3
0 comments (0 inline, 0 general)
src/linkgraph/linkgraph.cpp
➞
Show inline comments
 
@@ -35,14 +35,14 @@ LinkGraph::BaseNode::BaseNode(TileIndex
 
/**
 
 * Create an edge.
 
 */
 
LinkGraph::BaseEdge::BaseEdge()
 
LinkGraph::BaseEdge::BaseEdge(NodeID dest_node)
 
{
 
	this->capacity = 0;
 
	this->usage = 0;
 
	this->travel_time_sum = 0;
 
	this->last_unrestricted_update = INVALID_DATE;
 
	this->last_restricted_update = INVALID_DATE;
 
	this->next_edge = INVALID_NODE;
 
	this->dest_node = dest_node;
 
}
 

			




	
	
	
		
 
/**

			




	
	
		
 
@@ -56,8 +56,7 @@ void LinkGraph::ShiftDates(int interval)

			




	
	
	
		
 
	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {

			




	
	
	
		
 
		BaseNode &source = this->nodes[node1];

			




	
	
	
		
 
		if (source.last_update != INVALID_DATE) source.last_update += interval;

			




	
	
	
		
 
		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {

			




	
	
	
		
 
			BaseEdge &edge = this->nodes[node1].edges[node2];

			




	
	
	
		
 
		for (BaseEdge &edge : this->nodes[node1].edges) {

			




	
	
	
		
 
			if (edge.last_unrestricted_update != INVALID_DATE) edge.last_unrestricted_update += interval;

			




	
	
	
		
 
			if (edge.last_restricted_update != INVALID_DATE) edge.last_restricted_update += interval;

			




	
	
	
		
 
		}

			




	
	
		
 
@@ -69,8 +68,7 @@ void LinkGraph::Compress()

			




	
	
	
		
 
	this->last_compression = (_date + this->last_compression) / 2;

			




	
	
	
		
 
	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {

			




	
	
	
		
 
		this->nodes[node1].supply /= 2;

			




	
	
	
		
 
		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {

			




	
	
	
		
 
			BaseEdge &edge = this->nodes[node1].edges[node2];

			




	
	
	
		
 
		for (BaseEdge &edge : this->nodes[node1].edges) {

			




	
	
	
		
 
			if (edge.capacity > 0) {

			




	
	
	
		
 
				uint new_capacity = std::max(1U, edge.capacity / 2);

			




	
	
	
		
 
				if (edge.capacity < (1 << 16)) {

			




	
	
		
 
@@ -100,23 +98,13 @@ void LinkGraph::Merge(LinkGraph *other)

			




	
	
	
		
 
		this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);

			




	
	
	
		
 
		st->goods[this->cargo].link_graph = this->index;

			




	
	
	
		
 
		st->goods[this->cargo].node = new_node;

			




	
	
	
		
 
		for (NodeID node2 = 0; node2 < node1; ++node2) {

			




	
	
	
		
 
			BaseEdge &forward = this->nodes[new_node].edges[first + node2];

			




	
	
	
		
 
			BaseEdge &backward = this->nodes[first + node2].edges[new_node];

			




	
	
	
		
 
			forward = other->nodes[node1].edges[node2];

			




	
	
	
		
 
			backward = other->nodes[node2].edges[node1];

			




	
	
	
		
 
			forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age);

			




	
	
	
		
 
			forward.usage = LinkGraph::Scale(forward.usage, age, other_age);

			




	
	
	
		
 
			forward.travel_time_sum = LinkGraph::Scale(forward.travel_time_sum, age, other_age);

			




	
	
	
		
 
			if (forward.next_edge != INVALID_NODE) forward.next_edge += first;

			




	
	
	
		
 
			backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age);

			




	
	
	
		
 
			backward.usage = LinkGraph::Scale(backward.usage, age, other_age);

			




	
	
	
		
 
			backward.travel_time_sum = LinkGraph::Scale(backward.travel_time_sum, age, other_age);

			




	
	
	
		
 
			if (backward.next_edge != INVALID_NODE) backward.next_edge += first;

			




	
	
	
		
 

			




	
	
	
		
 
		for (BaseEdge &e : other->nodes[node1].edges) {

			




	
	
	
		
 
			BaseEdge &new_edge = this->nodes[new_node].edges.emplace_back(first + e.dest_node);

			




	
	
	
		
 
			new_edge.capacity = LinkGraph::Scale(e.capacity, age, other_age);

			




	
	
	
		
 
			new_edge.usage = LinkGraph::Scale(e.usage, age, other_age);

			




	
	
	
		
 
			new_edge.travel_time_sum = LinkGraph::Scale(e.travel_time_sum, age, other_age);

			




	
	
	
		
 
		}

			




	
	
	
		
 
		BaseEdge &new_start = this->nodes[new_node].edges[new_node];

			




	
	
	
		
 
		new_start = other->nodes[node1].edges[node1];

			




	
	
	
		
 
		if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;

			




	
	
	
		
 
	}

			




	
	
	
		
 
	delete other;

			




	
	
	
		
 
}

			




	
	
		
 
@@ -130,28 +118,23 @@ void LinkGraph::RemoveNode(NodeID id)

			




	
	
	
		
 
	assert(id < this->Size());

			




	
	
	
		
 

			




	
	
	
		
 
	NodeID last_node = this->Size() - 1;

			




	
	
	
		
 
	for (NodeID i = 0; i <= last_node; ++i) {

			




	
	
	
		
 
		(*this)[i].RemoveEdge(id);

			




	
	
	
		
 
		auto node_edges = this->nodes[i].edges;

			




	
	
	
		
 
		NodeID prev = i;

			




	
	
	
		
 
		NodeID next = node_edges[i].next_edge;

			




	
	
	
		
 
		while (next != INVALID_NODE) {

			




	
	
	
		
 
			if (next == last_node) {

			




	
	
	
		
 
				node_edges[prev].next_edge = id;

			




	
	
	
		
 
				break;

			




	
	
	
		
 
			}

			




	
	
	
		
 
			prev = next;

			




	
	
	
		
 
			next = node_edges[prev].next_edge;

			




	
	
	
		
 
		}

			




	
	
	
		
 
		node_edges[id] = node_edges[last_node];

			




	
	
	
		
 
	}

			




	
	
	
		
 
	Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;

			




	
	
	
		
 
	/* Erase node by swapping with the last element. Node index is referenced

			




	
	
	
		
 
	 * directly from station goods entries so the order and position must remain. */

			




	
	
	
		
 
	this->nodes[id] = this->nodes.back();

			




	
	
	
		
 
	this->nodes.pop_back();

			




	
	
	
		
 
	for (auto &n : this->nodes) {

			




	
	
	
		
 
		n.edges.pop_back();

			




	
	
	
		
 
		/* Find iterator position where an edge to id would be. */

			




	
	
	
		
 
		auto [first, last] = std::equal_range(n.edges.begin(), n.edges.end(), id);

			




	
	
	
		
 
		/* Remove potential node (erasing an empty range is safe). */

			




	
	
	
		
 
		auto insert = n.edges.erase(first, last);

			




	
	
	
		
 
		/* As the edge list is sorted, a potential edge to last_node will always be the last edge. */

			




	
	
	
		
 
		if (!n.edges.empty() && n.edges.back().dest_node == last_node) {

			




	
	
	
		
 
			/* Change dest ID and move into the spot of the deleted edge. */

			




	
	
	
		
 
			n.edges.back().dest_node = id;

			




	
	
	
		
 
			n.edges.insert(insert, n.edges.back());

			




	
	
	
		
 
			n.edges.pop_back();

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
		
 
@@ -170,13 +153,6 @@ NodeID LinkGraph::AddNode(const Station 

			




	
	
	
		
 
	NodeID new_node = this->Size();

			




	
	
	
		
 
	this->nodes.emplace_back(st->xy, st->index, HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));

			




	
	
	
		
 

			




	
	
	
		
 
	for (auto &n : this->nodes) {

			




	
	
	
		
 
		n.edges.resize(this->Size());

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	/* Reset the first edge starting at the new node */

			




	
	
	
		
 
	this->nodes[new_node].edges[new_node].next_edge = INVALID_NODE;

			




	
	
	
		
 

			




	
	
	
		
 
	return new_node;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
		
 
@@ -191,13 +167,12 @@ NodeID LinkGraph::AddNode(const Station 

			




	
	
	
		
 
void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode)

			




	
	
	
		
 
{

			




	
	
	
		
 
	assert(this->index != to);

			




	
	
	
		
 
	BaseEdge &edge = this->node.edges[to];

			




	
	
	
		
 
	BaseEdge &first = this->node.edges[this->index];

			




	
	
	
		
 
	assert(!this->HasEdgeTo(to));

			




	
	
	
		
 

			




	
	
	
		
 
	BaseEdge &edge = *this->node.edges.emplace(std::upper_bound(this->node.edges.begin(), this->node.edges.end(), to), to);

			




	
	
	
		
 
	edge.capacity = capacity;

			




	
	
	
		
 
	edge.usage = usage;

			




	
	
	
		
 
	edge.travel_time_sum = static_cast<uint64>(travel_time) * capacity;

			




	
	
	
		
 
	edge.next_edge = first.next_edge;

			




	
	
	
		
 
	first.next_edge = to;

			




	
	
	
		
 
	if (mode & EUM_UNRESTRICTED)  edge.last_unrestricted_update = _date;

			




	
	
	
		
 
	if (mode & EUM_RESTRICTED) edge.last_restricted_update = _date;

			




	
	
	
		
 
}

			




	
	
		
 
@@ -213,7 +188,7 @@ void LinkGraph::Node::UpdateEdge(NodeID 

			




	
	
	
		
 
{

			




	
	
	
		
 
	assert(capacity > 0);

			




	
	
	
		
 
	assert(usage <= capacity);

			




	
	
	
		
 
	if (this->node.edges[to].capacity == 0) {

			




	
	
	
		
 
	if (!this->HasEdgeTo(to)) {

			




	
	
	
		
 
		this->AddEdge(to, capacity, usage, travel_time, mode);

			




	
	
	
		
 
	} else {

			




	
	
	
		
 
		(*this)[to].Update(capacity, usage, travel_time, mode);

			




	
	
		
 
@@ -226,27 +201,8 @@ void LinkGraph::Node::UpdateEdge(NodeID 

			




	
	
	
		
 
 */

			




	
	
	
		
 
void LinkGraph::Node::RemoveEdge(NodeID to)

			




	
	
	
		
 
{

			




	
	
	
		
 
	if (this->index == to) return;

			




	
	
	
		
 
	BaseEdge &edge = this->node.edges[to];

			




	
	
	
		
 
	edge.capacity = 0;

			




	
	
	
		
 
	edge.last_unrestricted_update = INVALID_DATE;

			




	
	
	
		
 
	edge.last_restricted_update = INVALID_DATE;

			




	
	
	
		
 
	edge.usage = 0;

			




	
	
	
		
 
	edge.travel_time_sum = 0;

			




	
	
	
		
 

			




	
	
	
		
 
	NodeID prev = this->index;

			




	
	
	
		
 
	NodeID next = this->node.edges[this->index].next_edge;

			




	
	
	
		
 
	while (next != INVALID_NODE) {

			




	
	
	
		
 
		if (next == to) {

			




	
	
	
		
 
			/* Will be removed, skip it. */

			




	
	
	
		
 
			this->node.edges[prev].next_edge = edge.next_edge;

			




	
	
	
		
 
			edge.next_edge = INVALID_NODE;

			




	
	
	
		
 
			break;

			




	
	
	
		
 
		} else {

			




	
	
	
		
 
			prev = next;

			




	
	
	
		
 
			next = this->node.edges[next].next_edge;

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 
	auto [first, last] = std::equal_range(this->node.edges.begin(), this->node.edges.end(), to);

			




	
	
	
		
 
	this->node.edges.erase(first, last);

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/**

			




	
	
		
 
@@ -297,8 +253,4 @@ void LinkGraph::Init(uint size)

			




	
	
	
		
 
{

			




	
	
	
		
 
	assert(this->Size() == 0);

			




	
	
	
		
 
	this->nodes.resize(size);

			




	
	
	
		
 

			




	
	
	
		
 
	for (auto &n : this->nodes) {

			




	
	
	
		
 
		n.edges.resize(size);

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraph.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -38,10 +38,7 @@ extern LinkGraphPool _link_graph_pool;

			




	
	
	
		
 
class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {

			




	
	
	
		
 
public:

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * An edge in the link graph. Corresponds to a link between two stations or at

			




	
	
	
		
 
	 * least the distance between them. Edges from one node to itself contain the

			




	
	
	
		
 
	 * ID of the opposite Node of the first active edge (i.e. not just distance) in

			




	
	
	
		
 
	 * the column as next_edge.

			




	
	
	
		
 
	 * An edge in the link graph. Corresponds to a link between two stations.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	struct BaseEdge {

			




	
	
	
		
 
		uint capacity;                 ///< Capacity of the link.

			




	
	
		
 
@@ -49,9 +46,25 @@ public:

			




	
	
	
		
 
		uint64 travel_time_sum;        ///< Sum of the travel times of the link, in ticks.

			




	
	
	
		
 
		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.

			




	
	
	
		
 
		NodeID dest_node;              ///< Destination of the edge.

			




	
	
	
		
 

			




	
	
	
		
 
		BaseEdge(NodeID dest_node = INVALID_NODE);

			




	
	
	
		
 

			




	
	
	
		
 
		/** Comparison operator based on \c dest_node. */

			




	
	
	
		
 
		bool operator <(const BaseEdge &rhs) const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return this->dest_node < rhs.dest_node;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		BaseEdge();

			




	
	
	
		
 
		bool operator <(NodeID rhs) const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return this->dest_node < rhs;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		friend inline bool operator <(NodeID lhs, const LinkGraph::BaseEdge &rhs)

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return lhs < rhs.dest_node;

			




	
	
	
		
 
		}

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -66,7 +79,7 @@ public:

			




	
	
	
		
 
		TileIndex xy;            ///< Location of the station referred to by the node.

			




	
	
	
		
 
		Date last_update;        ///< When the supply was last updated.

			




	
	
	
		
 

			




	
	
	
		
 
		std::vector<BaseEdge> edges;

			




	
	
	
		
 
		std::vector<BaseEdge> edges; ///< Sorted list of outgoing edges from this node.

			




	
	
	
		
 

			




	
	
	
		
 
		BaseNode(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);

			




	
	
	
		
 
	};

			




	
	
		
 
@@ -135,6 +148,10 @@ public:

			




	
	
	
		
 
		Tnode &node;       ///< Node being wrapped.

			




	
	
	
		
 
		NodeID index;      ///< ID of wrapped node.

			




	
	
	
		
 

			




	
	
	
		
 
		auto GetEdge(NodeID dest) const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return std::lower_bound(this->node.edges.begin(), this->node.edges.end(), dest);

			




	
	
	
		
 
		}

			




	
	
	
		
 
	public:

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -173,6 +190,16 @@ public:

			




	
	
	
		
 
		 * @return Location of the station.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		TileIndex XY() const { return this->node.xy; }

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Check if an edge to a destination is present.

			




	
	
	
		
 
		 * @param dest Wanted edge destination.

			




	
	
	
		
 
		 * @return True if an edge is present.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		bool HasEdgeTo(NodeID dest) const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return std::binary_search(this->node.edges.begin(), this->node.edges.end(), dest);

			




	
	
	
		
 
		}

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -186,7 +213,7 @@ public:

			




	
	
	
		
 
	class BaseEdgeIterator {

			




	
	
	
		
 
	protected:

			




	
	
	
		
 
		span<Tedge> base; ///< Array of edges being iterated.

			




	
	
	
		
 
		NodeID current;   ///< Current offset in edges array.

			




	
	
	
		
 
		size_t current;   ///< Current offset in edges array.

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * A "fake" pointer to enable operator-> on temporaries. As the objects

			




	
	
		
 
@@ -214,12 +241,9 @@ public:

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Constructor.

			




	
	
	
		
 
		 * @param base Array of edges to be iterated.

			




	
	
	
		
 
		 * @param current ID of current node (to locate the first edge).

			




	
	
	
		
 
		 * @param end Make the iterator the end sentinel?

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		BaseEdgeIterator (span<Tedge> base, NodeID current) :

			




	
	
	
		
 
			base(base),

			




	
	
	
		
 
			current(current == INVALID_NODE ? current : base[current].next_edge)

			




	
	
	
		
 
		{}

			




	
	
	
		
 
		BaseEdgeIterator(span<Tedge> base, bool end) : base(base), current(end ? base.size() : 0) {}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Prefix-increment.

			




	
	
		
 
@@ -227,7 +251,7 @@ public:

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		Titer &operator++()

			




	
	
	
		
 
		{

			




	
	
	
		
 
			this->current = this->base[this->current].next_edge;

			




	
	
	
		
 
			if (this->current < this->base.size()) this->current++;

			




	
	
	
		
 
			return static_cast<Titer &>(*this);

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
		
 
@@ -238,7 +262,7 @@ public:

			




	
	
	
		
 
		Titer operator++(int)

			




	
	
	
		
 
		{

			




	
	
	
		
 
			Titer ret(static_cast<Titer &>(*this));

			




	
	
	
		
 
			this->current = this->base[this->current].next_edge;

			




	
	
	
		
 
			++(*this);

			




	
	
	
		
 
			return ret;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
		
 
@@ -274,7 +298,7 @@ public:

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		std::pair<NodeID, Tedge_wrapper> operator*() const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return std::pair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));

			




	
	
	
		
 
			return std::pair<NodeID, Tedge_wrapper>(this->base[this->current].dest_node, Tedge_wrapper(this->base[this->current]));

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -315,10 +339,10 @@ public:

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Constructor.

			




	
	
	
		
 
		 * @param edges Array of edges to be iterated over.

			




	
	
	
		
 
		 * @param current ID of current edge's end node.

			




	
	
	
		
 
		 * @param end Make the iterator the end sentinel?

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		ConstEdgeIterator(span<const BaseEdge> edges, NodeID current) :

			




	
	
	
		
 
			BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}

			




	
	
	
		
 
		ConstEdgeIterator(span<const BaseEdge> edges, bool end) :

			




	
	
	
		
 
			BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, end) {}

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -330,10 +354,10 @@ public:

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Constructor.

			




	
	
	
		
 
		 * @param edges Array of edges to be iterated over.

			




	
	
	
		
 
		 * @param current ID of current edge's end node.

			




	
	
	
		
 
		 * @param end Make the iterator the end sentinel?

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		EdgeIterator(span<BaseEdge> edges, NodeID current) :

			




	
	
	
		
 
			BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}

			




	
	
	
		
 
		EdgeIterator(span<BaseEdge> edges, bool end) :

			




	
	
	
		
 
			BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, end) {}

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -355,19 +379,23 @@ public:

			




	
	
	
		
 
		 * @param to ID of end node of edge.

			




	
	
	
		
 
		 * @return Constant edge wrapper.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		ConstEdge operator[](NodeID to) const { return ConstEdge(this->node.edges[to]); }

			




	
	
	
		
 
		ConstEdge operator[](NodeID to) const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			assert(this->HasEdgeTo(to));

			




	
	
	
		
 
			return ConstEdge(*this->GetEdge(to));

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get an iterator pointing to the start of the edges array.

			




	
	
	
		
 
		 * @return Constant edge iterator.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->node.edges, this->index); }

			




	
	
	
		
 
		ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->node.edges, false); }

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get an iterator pointing beyond the end of the edges array.

			




	
	
	
		
 
		 * @return Constant edge iterator.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		ConstEdgeIterator End() const { return ConstEdgeIterator(this->node.edges, INVALID_NODE); }

			




	
	
	
		
 
		ConstEdgeIterator End() const { return ConstEdgeIterator(this->node.edges, true); }

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -388,19 +416,23 @@ public:

			




	
	
	
		
 
		 * @param to ID of end node of edge.

			




	
	
	
		
 
		 * @return Edge wrapper.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		Edge operator[](NodeID to) { return Edge(this->node.edges[to]); }

			




	
	
	
		
 
		Edge operator[](NodeID to)

			




	
	
	
		
 
		{

			




	
	
	
		
 
			assert(this->HasEdgeTo(to));

			




	
	
	
		
 
			return Edge(*this->GetEdge(to));

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get an iterator pointing to the start of the edges array.

			




	
	
	
		
 
		 * @return Edge iterator.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		EdgeIterator Begin() { return EdgeIterator(this->node.edges, this->index); }

			




	
	
	
		
 
		EdgeIterator Begin() { return EdgeIterator(this->node.edges, false); }

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get an iterator pointing beyond the end of the edges array.

			




	
	
	
		
 
		 * @return Constant edge iterator.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		EdgeIterator End() { return EdgeIterator(this->node.edges, INVALID_NODE); }

			




	
	
	
		
 
		EdgeIterator End() { return EdgeIterator(this->node.edges, true); }

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Update the node's supply and set last_update to the current date.

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraph_gui.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -217,8 +217,8 @@ void LinkGraphOverlay::AddLinks(const St

			




	
	
	
		
 
			continue;

			




	
	
	
		
 
		}

			




	
	
	
		
 
		const LinkGraph &lg = *LinkGraph::Get(ge.link_graph);

			




	
	
	
		
 
		ConstEdge edge = lg[ge.node][to->goods[c].node];

			




	
	
	
		
 
		if (edge.Capacity() > 0) {

			




	
	
	
		
 
		if (lg[ge.node].HasEdgeTo(to->goods[c].node)) {

			




	
	
	
		
 
			ConstEdge edge = lg[ge.node][to->goods[c].node];

			




	
	
	
		
 
			this->AddStats(c, lg.Monthly(edge.Capacity()), lg.Monthly(edge.Usage()),

			




	
	
	
		
 
					ge.flows.GetFlowVia(to->index),

			




	
	
	
		
 
					edge.TravelTime() / DAY_TICKS,

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraphjob.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -124,11 +124,12 @@ LinkGraphJob::~LinkGraphJob()

			




	
	
	
		
 
		FlowStatMap &flows = from.Flows();

			




	
	
	
		
 

			




	
	
	
		
 
		for (EdgeIterator it(from.Begin()); it != from.End(); ++it) {

			




	
	
	
		
 
			if (from[it->first].Flow() == 0) continue;

			




	
	
	
		
 
			if (it->second.Flow() == 0) continue;

			




	
	
	
		
 
			StationID to = (*this)[it->first].Station();

			




	
	
	
		
 
			Station *st2 = Station::GetIfValid(to);

			




	
	
	
		
 
			if (st2 == nullptr || st2->goods[this->Cargo()].link_graph != this->link_graph.index ||

			




	
	
	
		
 
					st2->goods[this->Cargo()].node != it->first ||

			




	
	
	
		
 
					!(*lg)[node_id].HasEdgeTo(it->first) ||

			




	
	
	
		
 
					(*lg)[node_id][it->first].LastUpdate() == INVALID_DATE) {

			




	
	
	
		
 
				/* Edge has been removed. Delete flows. */

			




	
	
	
		
 
				StationIDStack erased = flows.DeleteFlows(to);

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraphjob.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -133,12 +133,12 @@ public:

			




	
	
	
		
 
		 * @param base_anno Array of annotations to be iterated.

			




	
	
	
		
 
		 * @param current Start offset of iteration.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		EdgeIterator(span<const LinkGraph::BaseEdge> base, span<EdgeAnnotation> base_anno, NodeID current) :

			




	
	
	
		
 
				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, current),

			




	
	
	
		
 
		EdgeIterator(span<const LinkGraph::BaseEdge> base, span<EdgeAnnotation> base_anno, bool end) :

			




	
	
	
		
 
				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, end),

			




	
	
	
		
 
				base_anno(base_anno) {}

			




	
	
	
		
 

			




	
	
	
		
 
		EdgeIterator() :

			




	
	
	
		
 
				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(span<const LinkGraph::BaseEdge>(), INVALID_NODE),

			




	
	
	
		
 
				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(span<const LinkGraph::BaseEdge>(), true),

			




	
	
	
		
 
				base_anno() {}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -148,7 +148,7 @@ public:

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		std::pair<NodeID, Edge> operator*() const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return std::pair<NodeID, Edge>(this->current, Edge(this->base[this->current], this->base_anno[this->current]));

			




	
	
	
		
 
			return std::pair<NodeID, Edge>(this->base[this->current].dest_node, Edge(this->base[this->current], this->base_anno[this->current]));

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -187,21 +187,26 @@ public:

			




	
	
	
		
 
		 * @param to Remote end of the edge.

			




	
	
	
		
 
		 * @return Edge between this node and "to".

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		Edge operator[](NodeID to) const { return Edge(this->node.edges[to], this->edge_annos[to]); }

			




	
	
	
		
 
		Edge operator[](NodeID to) const

			




	
	
	
		
 
		{

			




	
	
	
		
 
			assert(this->HasEdgeTo(to));

			




	
	
	
		
 
			auto index = std::distance(this->node.edges.begin(), this->GetEdge(to));

			




	
	
	
		
 
			return Edge(this->node.edges[index], this->edge_annos[index]);

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * 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->node.edges, this->edge_annos, index); }

			




	
	
	
		
 
		EdgeIterator Begin() const { return EdgeIterator(this->node.edges, this->edge_annos, false); }

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * 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->node.edges, this->edge_annos, INVALID_NODE); }

			




	
	
	
		
 
		EdgeIterator End() const { return EdgeIterator(this->node.edges, this->edge_annos, true); }

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get amount of supply that hasn't been delivered, yet.

			




        

    


    
    

    

        

                

                    src/saveload/linkgraph_sl.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -36,48 +36,60 @@ public:

			




	
	
	
		
 
		SLE_CONDVAR(Edge, travel_time_sum,          SLE_UINT64, SLV_LINKGRAPH_TRAVEL_TIME, SL_MAX_VERSION),

			




	
	
	
		
 
		    SLE_VAR(Edge, last_unrestricted_update, SLE_INT32),

			




	
	
	
		
 
		SLE_CONDVAR(Edge, last_restricted_update,   SLE_INT32, SLV_187, SL_MAX_VERSION),

			




	
	
	
		
 
		    SLE_VAR(Edge, next_edge,                SLE_UINT16),

			




	
	
	
		
 
		    SLE_VAR(Edge, dest_node,                SLE_UINT16),

			




	
	
	
		
 
		SLE_CONDVARNAME(Edge, dest_node, "next_edge", SLE_UINT16, SL_MIN_VERSION, SLV_LINKGRAPH_EDGES),

			




	
	
	
		
 
	};

			




	
	
	
		
 
	inline const static SaveLoadCompatTable compat_description = _linkgraph_edge_sl_compat;

			




	
	
	
		
 

			




	
	
	
		
 
	void Save(Node *bn) const override

			




	
	
	
		
 
	{

			




	
	
	
		
 
		uint16 size = 0;

			




	
	
	
		
 
		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->nodes[_linkgraph_from].edges[to].next_edge) {

			




	
	
	
		
 
			size++;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		SlSetStructListLength(size);

			




	
	
	
		
 
		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->nodes[_linkgraph_from].edges[to].next_edge) {

			




	
	
	
		
 
			SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetDescription());

			




	
	
	
		
 
		SlSetStructListLength(bn->edges.size());

			




	
	
	
		
 
		for (Edge &e : bn->edges) {

			




	
	
	
		
 
			SlObject(&e, this->GetDescription());

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	void Load(Node *bn) const override

			




	
	
	
		
 
	{

			




	
	
	
		
 
		uint16 max_size = _linkgraph->Size();

			




	
	
	
		
 
		_linkgraph->nodes[_linkgraph_from].edges.resize(max_size);

			




	
	
	
		
 
		if (IsSavegameVersionBefore(SLV_LINKGRAPH_EDGES)) {

			




	
	
	
		
 
			uint16 max_size = _linkgraph->Size();

			




	
	
	
		
 
			std::vector<Edge> edges(max_size);

			




	
	
	
		
 

			




	
	
	
		
 
		if (IsSavegameVersionBefore(SLV_191)) {

			




	
	
	
		
 
			/* We used to save the full matrix ... */

			




	
	
	
		
 
			for (NodeID to = 0; to < max_size; ++to) {

			




	
	
	
		
 
				SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetLoadDescription());

			




	
	
	
		
 
			}

			




	
	
	
		
 
			return;

			




	
	
	
		
 
		}

			




	
	
	
		
 
			if (IsSavegameVersionBefore(SLV_191)) {

			




	
	
	
		
 
				/* We used to save the full matrix ... */

			




	
	
	
		
 
				for (NodeID to = 0; to < max_size; ++to) {

			




	
	
	
		
 
					SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetLoadDescription());

			




	
	
	
		
 
				}

			




	
	
	
		
 
			} else {

			




	
	
	
		
 
				size_t used_size = IsSavegameVersionBefore(SLV_SAVELOAD_LIST_LENGTH) ? max_size : SlGetStructListLength(UINT16_MAX);

			




	
	
	
		
 

			




	
	
	
		
 
				/* ... but as that wasted a lot of space we save a sparse matrix now. */

			




	
	
	
		
 
				for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = edges[to].dest_node) {

			




	
	
	
		
 
					if (used_size == 0) SlErrorCorrupt("Link graph structure overflow");

			




	
	
	
		
 
					used_size--;

			




	
	
	
		
 

			




	
	
	
		
 
		size_t used_size = IsSavegameVersionBefore(SLV_SAVELOAD_LIST_LENGTH) ? max_size : SlGetStructListLength(UINT16_MAX);

			




	
	
	
		
 
					if (to >= max_size) SlErrorCorrupt("Link graph structure overflow");

			




	
	
	
		
 
					SlObject(&edges[to], this->GetLoadDescription());

			




	
	
	
		
 
				}

			




	
	
	
		
 

			




	
	
	
		
 
				if (!IsSavegameVersionBefore(SLV_SAVELOAD_LIST_LENGTH) && used_size > 0) SlErrorCorrupt("Corrupted link graph");

			




	
	
	
		
 
			}

			




	
	
	
		
 

			




	
	
	
		
 
		/* ... but as that wasted a lot of space we save a sparse matrix now. */

			




	
	
	
		
 
		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->nodes[_linkgraph_from].edges[to].next_edge) {

			




	
	
	
		
 
			if (used_size == 0) SlErrorCorrupt("Link graph structure overflow");

			




	
	
	
		
 
			used_size--;

			




	
	
	
		
 

			




	
	
	
		
 
			if (to >= max_size) SlErrorCorrupt("Link graph structure overflow");

			




	
	
	
		
 
			SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetLoadDescription());

			




	
	
	
		
 
			/* Build edge list from edge matrix. */

			




	
	
	
		
 
			for (NodeID to = edges[_linkgraph_from].dest_node; to != INVALID_NODE; to = edges[to].dest_node) {

			




	
	
	
		
 
				bn->edges.push_back(edges[to]);

			




	
	
	
		
 
				bn->edges.back().dest_node = to;

			




	
	
	
		
 
			}

			




	
	
	
		
 
			/* Sort by destination. */

			




	
	
	
		
 
			std::sort(bn->edges.begin(), bn->edges.end());

			




	
	
	
		
 
		} else {

			




	
	
	
		
 
			/* Edge data is now a simple vector and not any kind of matrix. */

			




	
	
	
		
 
			size_t size = SlGetStructListLength(UINT16_MAX);

			




	
	
	
		
 
			for (size_t i = 0; i < size; i++) {

			




	
	
	
		
 
				bn->edges.emplace_back();

			




	
	
	
		
 
				SlObject(&bn->edges.back(), this->GetLoadDescription());

			




	
	
	
		
 
			}

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		if (!IsSavegameVersionBefore(SLV_SAVELOAD_LIST_LENGTH) && used_size > 0) SlErrorCorrupt("Corrupted link graph");

			




	
	
	
		
 
	}

			




	
	
	
		
 
};

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    src/saveload/saveload.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -345,6 +345,8 @@ enum SaveLoadVersion : uint16 {

			




	
	
	
		
 
	SLV_MULTITRACK_LEVEL_CROSSINGS,         ///< 302  PR#9931 v13.0  Multi-track level crossings.

			




	
	
	
		
 
	SLV_NEWGRF_ROAD_STOPS,                  ///< 303  PR#10144 NewGRF road stops.

			




	
	
	
		
 

			




	
	
	
		
 
	SLV_LINKGRAPH_EDGES,                    ///< 303  PR#10314 Explicitly store link graph edges destination.

			




	
	
	
		
 

			




	
	
	
		
 
	SL_MAX_VERSION,                         ///< Highest possible saveload version

			




	
	
	
		
 
};

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    src/station.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -106,7 +106,7 @@ Station::~Station()

			




	
	
	
		
 
		for (NodeID node = 0; node < lg->Size(); ++node) {

			




	
	
	
		
 
			Station *st = Station::Get((*lg)[node].Station());

			




	
	
	
		
 
			st->goods[c].flows.erase(this->index);

			




	
	
	
		
 
			if ((*lg)[node][this->goods[c].node].LastUpdate() != INVALID_DATE) {

			




	
	
	
		
 
			if ((*lg)[node].HasEdgeTo(this->goods[c].node) && (*lg)[node][this->goods[c].node].LastUpdate() != INVALID_DATE) {

			




	
	
	
		
 
				st->goods[c].flows.DeleteFlows(this->index);

			




	
	
	
		
 
				RerouteCargo(st, c, this->index, st->index);

			




	
	
	
		
 
			}

			




        

    


    
    

    

        

                

                    src/station_cmd.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -3720,11 +3720,11 @@ void DeleteStaleLinks(Station *from)

			




	
	
	
		
 
		LinkGraph *lg = LinkGraph::GetIfValid(ge.link_graph);

			




	
	
	
		
 
		if (lg == nullptr) continue;

			




	
	
	
		
 
		Node node = (*lg)[ge.node];

			




	
	
	
		
 
		for (EdgeIterator it(node.Begin()); it != node.End();) {

			




	
	
	
		
 
		std::vector<NodeID> to_remove{};

			




	
	
	
		
 
		for (EdgeIterator it(node.Begin()); it != node.End(); ++it) {

			




	
	
	
		
 
			Edge edge = it->second;

			




	
	
	
		
 
			Station *to = Station::Get((*lg)[it->first].Station());

			




	
	
	
		
 
			assert(to->goods[c].node == it->first);

			




	
	
	
		
 
			++it; // Do that before removing the edge. Anything else may crash.

			




	
	
	
		
 
			assert(_date >= edge.LastUpdate());

			




	
	
	
		
 
			uint timeout = LinkGraph::MIN_TIMEOUT_DISTANCE + (DistanceManhattan(from->xy, to->xy) >> 3);

			




	
	
	
		
 
			if ((uint)(_date - edge.LastUpdate()) > timeout) {

			




	
	
		
 
@@ -3778,7 +3778,7 @@ void DeleteStaleLinks(Station *from)

			




	
	
	
		
 

			




	
	
	
		
 
				if (!updated) {

			




	
	
	
		
 
					/* If it's still considered dead remove it. */

			




	
	
	
		
 
					node.RemoveEdge(to->goods[c].node);

			




	
	
	
		
 
					to_remove.emplace_back(to->goods[c].node);

			




	
	
	
		
 
					ge.flows.DeleteFlows(to->index);

			




	
	
	
		
 
					RerouteCargo(from, c, to->index, from->index);

			




	
	
	
		
 
				}

			




	
	
		
 
@@ -3790,6 +3790,9 @@ void DeleteStaleLinks(Station *from)

			




	
	
	
		
 
				edge.Release();

			




	
	
	
		
 
			}

			




	
	
	
		
 
		}

			




	
	
	
		
 
		/* Remove dead edges. */

			




	
	
	
		
 
		for (NodeID r : to_remove) node.RemoveEdge(r);

			




	
	
	
		
 

			




	
	
	
		
 
		assert(_date >= lg->LastCompression());

			




	
	
	
		
 
		if ((uint)(_date - lg->LastCompression()) > LinkGraph::COMPRESSION_INTERVAL) {

			




	
	
	
		
 
			lg->Compress();

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: code.theleruby.com-48
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support