src/linkgraph/demands.cpp

   1 /** @file demands.cpp Definition of demand calculating link graph handler. */
   2
   3 #include "../stdafx.h"
   4 #include "demands.h"
   5 #include "../core/math_func.hpp"
   6 #include <queue>
   7
   8 #include "../safeguards.h"
   9
  10 typedef std::queue<NodeID> NodeList;
  11
  12 /**
  13  * Scale various things according to symmetric/asymmetric distribution.
  14  */
  15 class Scaler {
  16 public:
  17         void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
  18 };
  19
  20 /**
  21  * Scaler for symmetric distribution.
  22  */
  23 class SymmetricScaler : public Scaler {
  24 public:
  25         /**
  26          * Constructor.
  27          * @param mod_size Size modifier to be used. Determines how much demands
  28          *                 increase with the supply of the remote station.
  29          */
  30         inline SymmetricScaler(uint mod_size) : mod_size(mod_size), supply_sum(0),
  31                 demand_per_node(0)
  32         {}
  33
  34         /**
  35          * Count a node's supply into the sum of supplies.
  36          * @param node Node.
  37          */
  38         inline void AddNode(const Node &node)
  39         {
  40                 this->supply_sum += node.base.supply;
  41         }
  42
  43         /**
  44          * Calculate the mean demand per node using the sum of supplies.
  45          * @param num_demands Number of accepting nodes.
  46          */
  47         inline void SetDemandPerNode(uint num_demands)
  48         {
  49                 this->demand_per_node = std::max(this->supply_sum / num_demands, 1U);
  50         }
  51
  52         /**
  53          * Get the effective supply of one node towards another one. In symmetric
  54          * distribution the supply of the other node is weighed in.
  55          * @param from The supplying node.
  56          * @param to The receiving node.
  57          * @return Effective supply.
  58          */
  59         inline uint EffectiveSupply(const Node &from, const Node &to)
  60         {
  61                 return std::max(from.base.supply * std::max(1U, to.base.supply) * this->mod_size / 100 / this->demand_per_node, 1U);
  62         }
  63
  64         /**
  65          * Check if there is any acceptance left for this node. In symmetric distribution
  66          * nodes only accept anything if they also supply something. So if
  67          * undelivered_supply == 0 at the node there isn't any demand left either.
  68          * @param to Node to be checked.
  69          * @return If demand is left.
  70          */
  71         inline bool HasDemandLeft(const Node &to)
  72         {
  73                 return (to.base.supply == 0 || to.undelivered_supply > 0) && to.base.demand > 0;
  74         }
  75
  76         void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
  77
  78 private:
  79         uint mod_size;        ///< Size modifier. Determines how much demands increase with the supply of the remote station.
  80         uint supply_sum;      ///< Sum of all supplies in the component.
  81         uint demand_per_node; ///< Mean demand associated with each node.
  82 };
  83
  84 /**
  85  * A scaler for asymmetric distribution.
  86  */
  87 class AsymmetricScaler : public Scaler {
  88 public:
  89         /**
  90          * Nothing to do here.
  91          * @param unused.
  92          */
  93         inline void AddNode(const Node &)
  94         {
  95         }
  96
  97         /**
  98          * Nothing to do here.
  99          * @param unused.
 100          */
 101         inline void SetDemandPerNode(uint)
 102         {
 103         }
 104
 105         /**
 106          * Get the effective supply of one node towards another one.
 107          * @param from The supplying node.
 108          * @param unused.
 109          */
 110         inline uint EffectiveSupply(const Node &from, const Node &)
 111         {
 112                 return from.base.supply;
 113         }
 114
 115         /**
 116          * Check if there is any acceptance left for this node. In asymmetric distribution
 117          * nodes always accept as long as their demand > 0.
 118          * @param to The node to be checked.
 119          */
 120         inline bool HasDemandLeft(const Node &to) { return to.base.demand > 0; }
 121 };
 122
 123 /**
 124  * Set the demands between two nodes using the given base demand. In symmetric mode
 125  * this sets demands in both directions.
 126  * @param job The link graph job.
 127  * @param from_id The supplying node.
 128  * @param to_id The receiving node.
 129  * @param demand_forw Demand calculated for the "forward" direction.
 130  */
 131 void SymmetricScaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
 132 {
 133         if (job[from_id].base.demand > 0) {
 134                 uint demand_back = demand_forw * this->mod_size / 100;
 135                 uint undelivered = job[to_id].undelivered_supply;
 136                 if (demand_back > undelivered) {
 137                         demand_back = undelivered;
 138                         demand_forw = std::max(1U, demand_back * 100 / this->mod_size);
 139                 }
 140                 this->Scaler::SetDemands(job, to_id, from_id, demand_back);
 141         }
 142
 143         this->Scaler::SetDemands(job, from_id, to_id, demand_forw);
 144 }
 145
 146 /**
 147  * Set the demands between two nodes using the given base demand. In asymmetric mode
 148  * this only sets demand in the "forward" direction.
 149  * @param job The link graph job.
 150  * @param from_id The supplying node.
 151  * @param to_id The receiving node.
 152  * @param demand_forw Demand calculated for the "forward" direction.
 153  */
 154 inline void Scaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
 155 {
 156         job[from_id].DeliverSupply(to_id, demand_forw);
 157 }
 158
 159 /**
 160  * Do the actual demand calculation, called from constructor.
 161  * @param job Job to calculate the demands for.
 162  * @tparam Tscaler Scaler to be used for scaling demands.
 163  */
 164 template <class Tscaler>
 165 void DemandCalculator::CalcDemand(LinkGraphJob &job, Tscaler scaler)
 166 {
 167         NodeList supplies;
 168         NodeList demands;
 169         uint num_supplies = 0;
 170         uint num_demands = 0;
 171
 172         for (NodeID node = 0; node < job.Size(); node++) {
 173                 scaler.AddNode(job[node]);
 174                 if (job[node].base.supply > 0) {
 175                         supplies.push(node);
 176                         num_supplies++;
 177                 }
 178                 if (job[node].base.demand > 0) {
 179                         demands.push(node);
 180                         num_demands++;
 181                 }
 182         }
 183
 184         if (num_supplies == 0 || num_demands == 0) return;
 185
 186         /* Mean acceptance attributed to each node. If the distribution is
 187          * symmetric this is relative to remote supply, otherwise it is
 188          * relative to remote demand. */
 189         scaler.SetDemandPerNode(num_demands);
 190         uint chance = 0;
 191
 192         while (!supplies.empty() && !demands.empty()) {
 193                 NodeID from_id = supplies.front();
 194                 supplies.pop();
 195
 196                 for (uint i = 0; i < num_demands; ++i) {
 197                         assert(!demands.empty());
 198                         NodeID to_id = demands.front();
 199                         demands.pop();
 200                         if (from_id == to_id) {
 201                                 /* Only one node with supply and demand left */
 202                                 if (demands.empty() && supplies.empty()) return;
 203
 204                                 demands.push(to_id);
 205                                 continue;
 206                         }
 207
 208                         int32_t supply = scaler.EffectiveSupply(job[from_id], job[to_id]);
 209                         assert(supply > 0);
 210
 211                         constexpr int32_t divisor_scale = 16;
 212
 213                         int32_t scaled_distance = this->base_distance;
 214                         if (this->mod_dist > 0) {
 215                                 const int32_t distance = DistanceMaxPlusManhattan(job[from_id].base.xy, job[to_id].base.xy);
 216                                 /* Scale distance around base_distance by (mod_dist * (100 / 1024)).
 217                                  * mod_dist may be > 1024, so clamp result to be non-negative */
 218                                 scaled_distance = std::max(0, this->base_distance + (((distance - this->base_distance) * this->mod_dist) / 1024));
 219                         }
 220
 221                         /* Scale the accuracy by distance around accuracy / 2 */
 222                         const int32_t divisor = divisor_scale + ((this->accuracy * scaled_distance * divisor_scale) / (this->base_distance * 2));
 223                         assert(divisor >= divisor_scale);
 224
 225                         uint demand_forw = 0;
 226                         if (divisor <= (supply * divisor_scale)) {
 227                                 /* At first only distribute demand if
 228                                  * effective supply / accuracy divisor >= 1
 229                                  * Others are too small or too far away to be considered. */
 230                                 demand_forw = (supply * divisor_scale) / divisor;
 231                         } else if (++chance > this->accuracy * num_demands * num_supplies) {
 232                                 /* After some trying, if there is still supply left, distribute
 233                                  * demand also to other nodes. */
 234                                 demand_forw = 1;
 235                         }
 236
 237                         demand_forw = std::min(demand_forw, job[from_id].undelivered_supply);
 238
 239                         scaler.SetDemands(job, from_id, to_id, demand_forw);
 240
 241                         if (scaler.HasDemandLeft(job[to_id])) {
 242                                 demands.push(to_id);
 243                         } else {
 244                                 num_demands--;
 245                         }
 246
 247                         if (job[from_id].undelivered_supply == 0) break;
 248                 }
 249
 250                 if (job[from_id].undelivered_supply != 0) {
 251                         supplies.push(from_id);
 252                 } else {
 253                         num_supplies--;
 254                 }
 255         }
 256 }
 257
 258 /**
 259  * Create the DemandCalculator and immediately do the calculation.
 260  * @param job Job to calculate the demands for.
 261  */
 262 DemandCalculator::DemandCalculator(LinkGraphJob &job) :
 263         base_distance(IntSqrt(DistanceMaxPlusManhattan(TileXY(0,0), TileXY(Map::MaxX(), Map::MaxY()))))
 264 {
 265         const LinkGraphSettings &settings = job.Settings();
 266         CargoID cargo = job.Cargo();
 267
 268         this->accuracy = settings.accuracy;
 269         this->mod_dist = settings.demand_distance;
 270         if (this->mod_dist > 100) {
 271                 /* Increase effect of mod_dist > 100.
 272                  * Quadratic:
 273                  *   100 --> 100
 274                  *   150 --> 308
 275                  *   200 --> 933
 276                  *   255 --> 2102
 277                  */
 278                 int over100 = this->mod_dist - 100;
 279                 this->mod_dist = 100 + ((over100 * over100) / 12);
 280         }
 281
 282         switch (settings.GetDistributionType(cargo)) {
 283                 case DT_SYMMETRIC:
 284                         this->CalcDemand<SymmetricScaler>(job, SymmetricScaler(settings.demand_size));
 285                         break;
 286                 case DT_ASYMMETRIC:
 287                         this->CalcDemand<AsymmetricScaler>(job, AsymmetricScaler());
 288                         break;
 289                 default:
 290                         /* Nothing to do. */
 291                         break;
 292         }
 293 }