Changeset - r26916:2753c2f94e2d
Parent rev.
Child rev.
[Not reviewed]
master
0 7 0
Michael Lutz - 17 months ago 2023-01-01 16:12:56
michi@icosahedron.de
Codechange: [Linkgraph] Store edges in each node and not in a global matrix.
7 files changed with 101 insertions and 139 deletions:
src/core/span_type.hpp
2
src/linkgraph/linkgraph.cpp
28
40
src/linkgraph/linkgraph.h
42
49
src/linkgraph/linkgraphjob.cpp
2
29
src/linkgraph/linkgraphjob.h
19
12
src/linkgraph/mcf.cpp
1
3
src/saveload/linkgraph_sl.cpp
7
6
0 comments (0 inline, 0 general)
src/core/span_type.hpp
➞
Show inline comments
 
@@ -94,6 +94,8 @@ public:
 

			




	
	
	
		
 
	constexpr reference operator[](size_type idx) const { return first[idx]; }

			




	
	
	
		
 

			




	
	
	
		
 
	constexpr pointer data() const noexcept { return first; }

			




	
	
	
		
 

			




	
	
	
		
 
private:

			




	
	
	
		
 
	pointer first;

			




	
	
	
		
 
	pointer last;

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraph.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -23,7 +23,7 @@ INSTANTIATE_POOL_METHODS(LinkGraph)

			




	
	
	
		
 
 * @param st ID of the associated station.

			




	
	
	
		
 
 * @param demand Demand for cargo at the station.

			




	
	
	
		
 
 */

			




	
	
	
		
 
inline void LinkGraph::BaseNode::Init(TileIndex xy, StationID st, uint demand)

			




	
	
	
		
 
LinkGraph::BaseNode::BaseNode(TileIndex xy, StationID st, uint demand)

			




	
	
	
		
 
{

			




	
	
	
		
 
	this->xy = xy;

			




	
	
	
		
 
	this->supply = 0;

			




	
	
		
 
@@ -35,7 +35,7 @@ inline void LinkGraph::BaseNode::Init(Ti

			




	
	
	
		
 
/**

			




	
	
	
		
 
 * Create an edge.

			




	
	
	
		
 
 */

			




	
	
	
		
 
inline void LinkGraph::BaseEdge::Init()

			




	
	
	
		
 
LinkGraph::BaseEdge::BaseEdge()

			




	
	
	
		
 
{

			




	
	
	
		
 
	this->capacity = 0;

			




	
	
	
		
 
	this->usage = 0;

			




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

			




	
	
	
		
 
		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->edges[node1][node2];

			




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

			




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

			




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

			




	
	
	
		
 
		}

			




	
	
		
 
@@ -70,7 +70,7 @@ void LinkGraph::Compress()

			




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

			




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

			




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

			




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

			




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

			




	
	
	
		
 
			if (edge.capacity > 0) {

			




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

			




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

			




	
	
		
 
@@ -101,10 +101,10 @@ void LinkGraph::Merge(LinkGraph *other)

			




	
	
	
		
 
		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->edges[new_node][first + node2];

			




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

			




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

			




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

			




	
	
	
		
 
			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);

			




	
	
		
 
@@ -114,8 +114,8 @@ void LinkGraph::Merge(LinkGraph *other)

			




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

			




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

			




	
	
	
		
 
		}

			




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

			




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

			




	
	
	
		
 
		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;

			




	
	
		
 
@@ -132,7 +132,7 @@ void LinkGraph::RemoveNode(NodeID id)

			




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

			




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

			




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

			




	
	
	
		
 
		BaseEdge *node_edges = this->edges[i];

			




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

			




	
	
	
		
 
		NodeID prev = i;

			




	
	
	
		
 
		NodeID next = node_edges[i].next_edge;

			




	
	
	
		
 
		while (next != INVALID_NODE) {

			




	
	
		
 
@@ -150,10 +150,9 @@ void LinkGraph::RemoveNode(NodeID id)

			




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

			




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

			




	
	
	
		
 
	this->nodes.pop_back();

			




	
	
	
		
 
	this->edges.EraseColumn(id);

			




	
	
	
		
 
	/* Not doing EraseRow here, as having the extra invalid row doesn't hurt

			




	
	
	
		
 
	 * and removing it would trigger a lot of memmove. The data has already

			




	
	
	
		
 
	 * been copied around in the loop above. */

			




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

			




	
	
	
		
 
		n.edges.pop_back();

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/**

			




	
	
		
 
@@ -169,23 +168,15 @@ NodeID LinkGraph::AddNode(const Station 

			




	
	
	
		
 
	const GoodsEntry &good = st->goods[this->cargo];

			




	
	
	
		
 

			




	
	
	
		
 
	NodeID new_node = this->Size();

			




	
	
	
		
 
	this->nodes.emplace_back();

			




	
	
	
		
 
	/* Avoid reducing the height of the matrix as that is expensive and we

			




	
	
	
		
 
	 * most likely will increase it again later which is again expensive. */

			




	
	
	
		
 
	this->edges.Resize(new_node + 1U, std::max(new_node + 1U, this->edges.Height()));

			




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

			




	
	
	
		
 

			




	
	
	
		
 
	this->nodes[new_node].Init(st->xy, st->index,

			




	
	
	
		
 
			HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));

			




	
	
	
		
 

			




	
	
	
		
 
	BaseEdge *new_edges = this->edges[new_node];

			




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

			




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

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




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

			




	
	
	
		
 
	new_edges[new_node].next_edge = INVALID_NODE;

			




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

			




	
	
	
		
 

			




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

			




	
	
	
		
 
		new_edges[i].Init();

			




	
	
	
		
 
		this->edges[i][new_node].Init();

			




	
	
	
		
 
	}

			




	
	
	
		
 
	return new_node;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
		
 
@@ -200,8 +191,8 @@ 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->edges[to];

			




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

			




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

			




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

			




	
	
	
		
 
	edge.capacity = capacity;

			




	
	
	
		
 
	edge.usage = usage;

			




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

			




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

			




	
	
	
		
 
{

			




	
	
	
		
 
	assert(capacity > 0);

			




	
	
	
		
 
	assert(usage <= capacity);

			




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

			




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

			




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

			




	
	
	
		
 
	} else {

			




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

			




	
	
		
 
@@ -236,7 +227,7 @@ void LinkGraph::Node::UpdateEdge(NodeID 

			




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

			




	
	
	
		
 
{

			




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

			




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

			




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

			




	
	
	
		
 
	edge.capacity = 0;

			




	
	
	
		
 
	edge.last_unrestricted_update = INVALID_DATE;

			




	
	
	
		
 
	edge.last_restricted_update = INVALID_DATE;

			




	
	
		
 
@@ -244,16 +235,16 @@ void LinkGraph::Node::RemoveEdge(NodeID 

			




	
	
	
		
 
	edge.travel_time_sum = 0;

			




	
	
	
		
 

			




	
	
	
		
 
	NodeID prev = this->index;

			




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

			




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

			




	
	
	
		
 
	while (next != INVALID_NODE) {

			




	
	
	
		
 
		if (next == to) {

			




	
	
	
		
 
			/* Will be removed, skip it. */

			




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

			




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

			




	
	
	
		
 
			edge.next_edge = INVALID_NODE;

			




	
	
	
		
 
			break;

			




	
	
	
		
 
		} else {

			




	
	
	
		
 
			prev = next;

			




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

			




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

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
		
 
@@ -305,12 +296,9 @@ void LinkGraph::Edge::Update(uint capaci

			




	
	
	
		
 
void LinkGraph::Init(uint size)

			




	
	
	
		
 
{

			




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

			




	
	
	
		
 
	this->edges.Resize(size, size);

			




	
	
	
		
 
	this->nodes.resize(size);

			




	
	
	
		
 

			




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

			




	
	
	
		
 
		this->nodes[i].Init();

			




	
	
	
		
 
		BaseEdge *column = this->edges[i];

			




	
	
	
		
 
		for (uint j = 0; j < size; ++j) column[j].Init();

			




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

			




	
	
	
		
 
		n.edges.resize(size);

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraph.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -12,7 +12,6 @@

			




	
	
	
		
 

			




	
	
	
		
 
#include "../core/pool_type.hpp"

			




	
	
	
		
 
#include "../core/smallmap_type.hpp"

			




	
	
	
		
 
#include "../core/smallmatrix_type.hpp"

			




	
	
	
		
 
#include "../station_base.h"

			




	
	
	
		
 
#include "../cargotype.h"

			




	
	
	
		
 
#include "../date_func.h"

			




	
	
		
 
@@ -38,21 +37,6 @@ extern LinkGraphPool _link_graph_pool;

			




	
	
	
		
 
 */

			




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

			




	
	
	
		
 
public:

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * Node of the link graph. contains all relevant information from the associated

			




	
	
	
		
 
	 * station. It's copied so that the link graph job can work on its own data set

			




	
	
	
		
 
	 * in a separate thread.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	struct BaseNode {

			




	
	
	
		
 
		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(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * 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

			




	
	
		
 
@@ -66,7 +50,25 @@ public:

			




	
	
	
		
 
		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();

			




	
	
	
		
 

			




	
	
	
		
 
		BaseEdge();

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * Node of the link graph. contains all relevant information from the associated

			




	
	
	
		
 
	 * station. It's copied so that the link graph job can work on its own data set

			




	
	
	
		
 
	 * in a separate thread.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	struct BaseNode {

			




	
	
	
		
 
		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.

			




	
	
	
		
 

			




	
	
	
		
 
		std::vector<BaseEdge> edges;

			




	
	
	
		
 

			




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

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -125,26 +127,22 @@ public:

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * Wrapper for a node (const or not) allowing retrieval, but no modification.

			




	
	
	
		
 
	 * @tparam Tedge Actual node class, may be "const BaseNode" or just "BaseNode".

			




	
	
	
		
 
	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".

			




	
	
	
		
 
	 * @tparam Tnode Actual node class, may be "const BaseNode" or just "BaseNode".

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	template<typename Tnode, typename Tedge>

			




	
	
	
		
 
	template<typename Tnode>

			




	
	
	
		
 
	class NodeWrapper {

			




	
	
	
		
 
	protected:

			




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

			




	
	
	
		
 
		Tedge *edges; ///< Outgoing edges for wrapped node.

			




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

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
	public:

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Wrap a node.

			




	
	
	
		
 
		 * @param node Node to be wrapped.

			




	
	
	
		
 
		 * @param edges Outgoing edges for node to be wrapped.

			




	
	
	
		
 
		 * @param index ID of node to be wrapped.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),

			




	
	
	
		
 
			edges(edges), index(index) {}

			




	
	
	
		
 
		NodeWrapper(Tnode &node, NodeID index) : node(node), index(index) {}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get supply of wrapped node.

			




	
	
		
 
@@ -187,8 +185,8 @@ public:

			




	
	
	
		
 
	template <class Tedge, class Tedge_wrapper, class Titer>

			




	
	
	
		
 
	class BaseEdgeIterator {

			




	
	
	
		
 
	protected:

			




	
	
	
		
 
		Tedge *base;    ///< Array of edges being iterated.

			




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

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




	
	
		
 
@@ -218,7 +216,7 @@ public:

			




	
	
	
		
 
		 * @param base Array of edges to be iterated.

			




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

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		BaseEdgeIterator (Tedge *base, NodeID current) :

			




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

			




	
	
	
		
 
			base(base),

			




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

			




	
	
	
		
 
		{}

			




	
	
		
 
@@ -254,7 +252,7 @@ public:

			




	
	
	
		
 
		template<class Tother>

			




	
	
	
		
 
		bool operator==(const Tother &other)

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return this->base == other.base && this->current == other.current;

			




	
	
	
		
 
			return this->base.data() == other.base.data() && this->current == other.current;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -267,7 +265,7 @@ public:

			




	
	
	
		
 
		template<class Tother>

			




	
	
	
		
 
		bool operator!=(const Tother &other)

			




	
	
	
		
 
		{

			




	
	
	
		
 
			return this->base != other.base || this->current != other.current;

			




	
	
	
		
 
			return this->base.data() != other.base.data() || this->current != other.current;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -319,7 +317,7 @@ public:

			




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

			




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

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		ConstEdgeIterator(const BaseEdge *edges, NodeID current) :

			




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

			




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

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
		
 
@@ -334,7 +332,7 @@ public:

			




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

			




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

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		EdgeIterator(BaseEdge *edges, NodeID current) :

			




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

			




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

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
		
 
@@ -342,16 +340,14 @@ public:

			




	
	
	
		
 
	 * Constant node class. Only retrieval operations are allowed on both the

			




	
	
	
		
 
	 * node itself and its edges.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {

			




	
	
	
		
 
	class ConstNode : public NodeWrapper<const BaseNode> {

			




	
	
	
		
 
	public:

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Constructor.

			




	
	
	
		
 
		 * @param lg LinkGraph to get the node from.

			




	
	
	
		
 
		 * @param node ID of the node.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		ConstNode(const LinkGraph *lg, NodeID node) :

			




	
	
	
		
 
			NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)

			




	
	
	
		
 
		{}

			




	
	
	
		
 
		ConstNode(const LinkGraph *lg, NodeID node) : NodeWrapper<const BaseNode>(lg->nodes[node], node) {}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get a ConstEdge. This is not a reference as the wrapper objects are

			




	
	
		
 
@@ -359,34 +355,32 @@ public:

			




	
	
	
		
 
		 * @param to ID of end node of edge.

			




	
	
	
		
 
		 * @return Constant edge wrapper.

			




	
	
	
		
 
		 */

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




	
	
	
		
 
		 * @return Constant edge iterator.

			




	
	
	
		
 
		 */

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




	
	
	
		
 
		 * @return Constant edge iterator.

			




	
	
	
		
 
		 */

			




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

			




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

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * Updatable node class. The node itself as well as its edges can be modified.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	class Node : public NodeWrapper<BaseNode, BaseEdge> {

			




	
	
	
		
 
	class Node : public NodeWrapper<BaseNode> {

			




	
	
	
		
 
	public:

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Constructor.

			




	
	
	
		
 
		 * @param lg LinkGraph to get the node from.

			




	
	
	
		
 
		 * @param node ID of the node.

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		Node(LinkGraph *lg, NodeID node) :

			




	
	
	
		
 
			NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)

			




	
	
	
		
 
		{}

			




	
	
	
		
 
		Node(LinkGraph *lg, NodeID node) : NodeWrapper<BaseNode>(lg->nodes[node], node) {}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Get an Edge. This is not a reference as the wrapper objects are not

			




	
	
		
 
@@ -394,19 +388,19 @@ public:

			




	
	
	
		
 
		 * @param to ID of end node of edge.

			




	
	
	
		
 
		 * @return Edge wrapper.

			




	
	
	
		
 
		 */

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




	
	
	
		
 
		 * @return Edge iterator.

			




	
	
	
		
 
		 */

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




	
	
	
		
 
		 * @return Constant edge iterator.

			




	
	
	
		
 
		 */

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




	
	
		
 
@@ -442,7 +436,6 @@ public:

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	typedef std::vector<BaseNode> NodeVector;

			




	
	
	
		
 
	typedef SmallMatrix<BaseEdge> EdgeMatrix;

			




	
	
	
		
 

			




	
	
	
		
 
	/** Minimum effective distance for timeout calculation. */

			




	
	
	
		
 
	static const uint MIN_TIMEOUT_DISTANCE = 32;

			




	
	
		
 
@@ -539,11 +532,11 @@ protected:

			




	
	
	
		
 
	friend SaveLoadTable GetLinkGraphJobDesc();

			




	
	
	
		
 
	friend class SlLinkgraphNode;

			




	
	
	
		
 
	friend class SlLinkgraphEdge;

			




	
	
	
		
 
	friend class LinkGraphJob;

			




	
	
	
		
 

			




	
	
	
		
 
	CargoID cargo;         ///< Cargo of this component's link graph.

			




	
	
	
		
 
	Date last_compression; ///< Last time the capacities and supplies were compressed.

			




	
	
	
		
 
	NodeVector nodes;      ///< Nodes in the component.

			




	
	
	
		
 
	EdgeMatrix edges;      ///< Edges in the component.

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
#endif /* LINKGRAPH_H */

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraphjob.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -180,40 +180,13 @@ LinkGraphJob::~LinkGraphJob()

			




	
	
	
		
 
void LinkGraphJob::Init()

			




	
	
	
		
 
{

			




	
	
	
		
 
	uint size = this->Size();

			




	
	
	
		
 
	this->nodes.resize(size);

			




	
	
	
		
 
	this->edges.Resize(size, size);

			




	
	
	
		
 
	this->nodes.reserve(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();

			




	
	
	
		
 
		}

			




	
	
	
		
 
		this->nodes.emplace_back(this->link_graph.nodes[i]);

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/**

			




	
	
	
		
 
 * 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.

			




        

    


    
    

    

        

                

                    src/linkgraph/linkgraphjob.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -36,7 +36,6 @@ private:

			




	
	
	
		
 
		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();

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
		
 
@@ -46,11 +45,16 @@ private:

			




	
	
	
		
 
		uint undelivered_supply; ///< Amount of supply that hasn't been distributed yet.

			




	
	
	
		
 
		PathList paths;          ///< Paths through this node, sorted so that those with flow == 0 are in the back.

			




	
	
	
		
 
		FlowStatMap flows;       ///< Planned flows to other nodes.

			




	
	
	
		
 
		void Init(uint supply);

			




	
	
	
		
 

			




	
	
	
		
 
		std::vector<EdgeAnnotation> edges;

			




	
	
	
		
 

			




	
	
	
		
 
		NodeAnnotation(const LinkGraph::BaseNode &node) : undelivered_supply(node.supply), paths(), flows()

			




	
	
	
		
 
		{

			




	
	
	
		
 
			this->edges.resize(node.edges.size());

			




	
	
	
		
 
		}

			




	
	
	
		
 
	};

			




	
	
	
		
 

			




	
	
	
		
 
	typedef std::vector<NodeAnnotation> NodeAnnotationVector;

			




	
	
	
		
 
	typedef SmallMatrix<EdgeAnnotation> EdgeAnnotationMatrix;

			




	
	
	
		
 

			




	
	
	
		
 
	friend SaveLoadTable GetLinkGraphJobDesc();

			




	
	
	
		
 
	friend class LinkGraphSchedule;

			




	
	
		
 
@@ -61,7 +65,6 @@ protected:

			




	
	
	
		
 
	std::thread thread;               ///< Thread the job is running in or a default-constructed thread if it's running in the main thread.

			




	
	
	
		
 
	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.

			




	
	
	
		
 
	std::atomic<bool> job_completed;  ///< Is the job still running. This is accessed by multiple threads and reads may be stale.

			




	
	
	
		
 
	std::atomic<bool> job_aborted;    ///< Has the job been aborted. This is accessed by multiple threads and reads may be stale.

			




	
	
	
		
 

			




	
	
		
 
@@ -146,7 +149,7 @@ public:

			




	
	
	
		
 
	 * Iterator for job edges.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	class EdgeIterator : public LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator> {

			




	
	
	
		
 
		EdgeAnnotation *base_anno; ///< Array of annotations to be (indirectly) iterated.

			




	
	
	
		
 
		span<EdgeAnnotation> base_anno; ///< Array of annotations to be (indirectly) iterated.

			




	
	
	
		
 
	public:

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Constructor.

			




	
	
		
 
@@ -154,10 +157,14 @@ public:

			




	
	
	
		
 
		 * @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) :

			




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

			




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

			




	
	
	
		
 
				base_anno(base_anno) {}

			




	
	
	
		
 

			




	
	
	
		
 
		EdgeIterator() :

			




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

			




	
	
	
		
 
				base_anno() {}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
	
		
 
		 * Dereference.

			




	
	
	
		
 
		 * @return Pair of the edge currently pointed to and the ID of its

			




	
	
		
 
@@ -184,8 +191,8 @@ public:

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	class Node : public LinkGraph::ConstNode {

			




	
	
	
		
 
	private:

			




	
	
	
		
 
		NodeAnnotation &node_anno;  ///< Annotation being wrapped.

			




	
	
	
		
 
		EdgeAnnotation *edge_annos; ///< Edge annotations belonging to this node.

			




	
	
	
		
 
		NodeAnnotation       &node_anno; ///< Annotation being wrapped.

			




	
	
	
		
 
		span<EdgeAnnotation> edge_annos; ///< Edge annotations belonging to this node.

			




	
	
	
		
 
	public:

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -195,7 +202,7 @@ public:

			




	
	
	
		
 
		 */

			




	
	
	
		
 
		Node (LinkGraphJob *lgj, NodeID node) :

			




	
	
	
		
 
			LinkGraph::ConstNode(&lgj->link_graph, node),

			




	
	
	
		
 
			node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node])

			




	
	
	
		
 
			node_anno(lgj->nodes[node]), edge_annos(lgj->nodes[node].edges)

			




	
	
	
		
 
		{}

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




	
	
		
 
@@ -204,21 +211,21 @@ public:

			




	
	
	
		
 
		 * @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]); }

			




	
	
	
		
 
		Edge operator[](NodeID to) const { return Edge(this->node.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); }

			




	
	
	
		
 
		EdgeIterator Begin() const { return EdgeIterator(this->node.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); }

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		/**

			




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

			




        

    


    
    

    

        

                

                    src/linkgraph/mcf.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -103,9 +103,7 @@ public:

			




	
	
	
		
 
	 * Construct a GraphEdgeIterator.

			




	
	
	
		
 
	 * @param job Job to iterate on.

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	GraphEdgeIterator(LinkGraphJob &job) : job(job),

			




	
	
	
		
 
		i(nullptr, nullptr, INVALID_NODE), end(nullptr, nullptr, INVALID_NODE)

			




	
	
	
		
 
	{}

			




	
	
	
		
 
	GraphEdgeIterator(LinkGraphJob &job) : job(job), i(), end() {}

			




	
	
	
		
 

			




	
	
	
		
 
	/**

			




	
	
	
		
 
	 * Setup the node to start iterating at.

			




        

    


    
    

    

        

                

                    src/saveload/linkgraph_sl.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -43,24 +43,25 @@ public:

			




	
	
	
		
 
	void Save(Node *bn) const override

			




	
	
	
		
 
	{

			




	
	
	
		
 
		uint16 size = 0;

			




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

			




	
	
	
		
 
		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->edges[_linkgraph_from][to].next_edge) {

			




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

			




	
	
	
		
 
		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());

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	void Load(Node *bn) const override

			




	
	
	
		
 
	{

			




	
	
	
		
 
		uint16 max_size = _linkgraph->Size();

			




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

			




	
	
	
		
 

			




	
	
	
		
 
		if (IsSavegameVersionBefore(SLV_191)) {

			




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

			




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

			




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

			




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

			




	
	
	
		
 
			}

			




	
	
	
		
 
			return;

			




	
	
	
		
 
		}

			




	
	
		
 
@@ -68,12 +69,12 @@ public:

			




	
	
	
		
 
		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 = _linkgraph->edges[_linkgraph_from][to].next_edge) {

			




	
	
	
		
 
		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->edges[_linkgraph_from][to], this->GetLoadDescription());

			




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

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




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

			




        

    



    


    



    



      

      





    
    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