linkgraph.cpp

Go to the documentation of this file.

/*
 * 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 <http://www.gnu.org/licenses/>.
 */
 
#include "../stdafx.h"
#include "../core/pool_func.hpp"
#include "linkgraph.h"
 
#include "../safeguards.h"
 
/* Initialize the link-graph-pool */
LinkGraphPool _link_graph_pool("LinkGraph");
INSTANTIATE_POOL_METHODS(LinkGraph)
 
 
inline void LinkGraph::BaseNode::Init(TileIndex xy, StationID st, uint demand)
{
  this->xy = xy;
  this->supply = 0;
  this->demand = demand;
  this->station = st;
  this->last_update = INVALID_DATE;
}
 
inline void LinkGraph::BaseEdge::Init()
{
  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;
}
 
void LinkGraph::ShiftDates(int interval)
{
  this->last_compression += 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->edges[node1][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;
    }
  }
}
 
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->edges[node1][node2];
      if (edge.capacity > 0) {
        uint new_capacity = std::max(1U, edge.capacity / 2);
        if (edge.capacity < (1 << 16)) {
          edge.travel_time_sum = edge.travel_time_sum * new_capacity / edge.capacity;
        } else if (edge.travel_time_sum != 0) {
          edge.travel_time_sum = std::max(1ULL, edge.travel_time_sum / 2);
        }
        edge.capacity = new_capacity;
        edge.usage /= 2;
      }
    }
  }
}
 
void LinkGraph::Merge(LinkGraph *other)
{
  Date age = _date - this->last_compression + 1;
  Date other_age = _date - other->last_compression + 1;
  NodeID first = this->Size();
  for (NodeID node1 = 0; node1 < other->Size(); ++node1) {
    Station *st = Station::Get(other->nodes[node1].station);
    NodeID new_node = this->AddNode(st);
    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->edges[new_node][first + node2];
      BaseEdge &backward = this->edges[first + node2][new_node];
      forward = other->edges[node1][node2];
      backward = other->edges[node2][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;
    }
    BaseEdge &new_start = this->edges[new_node][new_node];
    new_start = other->edges[node1][node1];
    if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;
  }
  delete other;
}
 
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);
    BaseEdge *node_edges = this->edges[i];
    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();
  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. */
}
 
NodeID LinkGraph::AddNode(const Station *st)
{
  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[new_node].Init(st->xy, st->index,
      HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));
 
  BaseEdge *new_edges = this->edges[new_node];
 
  /* Reset the first edge starting at the new node */
  new_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;
}
 
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];
  edge.capacity = capacity;
  edge.usage = usage;
  edge.travel_time_sum = 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;
}
 
void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode)
{
  assert(capacity > 0);
  assert(usage <= capacity);
  if (this->edges[to].capacity == 0) {
    this->AddEdge(to, capacity, usage, travel_time, mode);
  } else {
    (*this)[to].Update(capacity, usage, travel_time, mode);
  }
}
 
void LinkGraph::Node::RemoveEdge(NodeID to)
{
  if (this->index == to) return;
  BaseEdge &edge = this->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->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;
      edge.next_edge = INVALID_NODE;
      break;
    } else {
      prev = next;
      next = this->edges[next].next_edge;
    }
  }
}
 
void LinkGraph::Edge::Update(uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode)
{
  assert(this->edge.capacity > 0);
  assert(capacity >= usage);
 
  if (mode & EUM_INCREASE) {
    if (this->edge.travel_time_sum == 0) {
      this->edge.travel_time_sum = (this->edge.capacity + capacity) * travel_time;
    } else if (travel_time == 0) {
      this->edge.travel_time_sum += this->edge.travel_time_sum / this->edge.capacity * capacity;
    } else {
      this->edge.travel_time_sum += travel_time * capacity;
    }
    this->edge.capacity += capacity;
    this->edge.usage += usage;
  } else if (mode & EUM_REFRESH) {
    if (this->edge.travel_time_sum == 0) {
      this->edge.capacity = std::max(this->edge.capacity, capacity);
      this->edge.travel_time_sum = travel_time * this->edge.capacity;
    } else if (capacity > this->edge.capacity) {
      this->edge.travel_time_sum = this->edge.travel_time_sum / this->edge.capacity * capacity;
      this->edge.capacity = capacity;
    }
    this->edge.usage = std::max(this->edge.usage, usage);
  }
  if (mode & EUM_UNRESTRICTED) this->edge.last_unrestricted_update = _date;
  if (mode & EUM_RESTRICTED) this->edge.last_restricted_update = _date;
}
 
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();
  }
}