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 <queue>
   6
   7 #include "../safeguards.h"
   8
   9 typedef std::queue<NodeID> NodeList;
  10
  11 /**
  12  * Scale various things according to symmetric/asymmetric distribution.
  13  */
  14 class Scaler {
  15 public:
  16         void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
  17 };
  18
  19 /**
  20  * Scaler for symmetric distribution.
  21  */
  22 class SymmetricScaler : public Scaler {
  23 public:
  24         /**
  25          * Constructor.
  26          * @param mod_size Size modifier to be used. Determines how much demands
  27          *                 increase with the supply of the remote station.
  28          */
  29         inline SymmetricScaler(uint mod_size) : mod_size(mod_size), supply_sum(0),
  30                 demand_per_node(0)
  31         {}
  32
  33         /**
  34          * Count a node's supply into the sum of supplies.
  35          * @param node Node.
  36          */
  37         inline void AddNode(const Node &node)
  38         {
  39                 this->supply_sum += node.Supply();
  40         }
  41
  42         /**
  43          * Calculate the mean demand per node using the sum of supplies.
  44          * @param num_demands Number of accepting nodes.
  45          */
  46         inline void SetDemandPerNode(uint num_demands)
  47         {
  48                 this->demand_per_node = max(this->supply_sum / num_demands, 1U);
  49         }
  50
  51         /**
  52          * Get the effective supply of one node towards another one. In symmetric
  53          * distribution the supply of the other node is weighed in.
  54          * @param from The supplying node.
  55          * @param to The receiving node.
  56          * @return Effective supply.
  57          */
  58         inline uint EffectiveSupply(const Node &from, const Node &to)
  59         {
  60                 return max(from.Supply() * max(1U, to.Supply()) * this->mod_size / 100 / this->demand_per_node, 1U);
  61         }
  62
  63         /**
  64          * Check if there is any acceptance left for this node. In symmetric distribution
  65          * nodes only accept anything if they also supply something. So if
  66          * undelivered_supply == 0 at the node there isn't any demand left either.
  67          * @param to Node to be checked.
  68          * @return If demand is left.
  69          */
  70         inline bool HasDemandLeft(const Node &to)
  71         {
  72                 return (to.Supply() == 0 || to.UndeliveredSupply() > 0) && to.Demand() > 0;
  73         }
  74
  75         void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
  76
  77 private:
  78         uint mod_size;        ///< Size modifier. Determines how much demands increase with the supply of the remote station.
  79         uint supply_sum;      ///< Sum of all supplies in the component.
  80         uint demand_per_node; ///< Mean demand associated with each node.
  81 };
  82
  83 /**
  84  * A scaler for asymmetric distribution.
  85  */
  86 class AsymmetricScaler : public Scaler {
  87 public:
  88         /**
  89          * Nothing to do here.
  90          * @param unused.
  91          */
  92         inline void AddNode(const Node &)
  93         {
  94         }
  95
  96         /**
  97          * Nothing to do here.
  98          * @param unused.
  99          */
 100         inline void SetDemandPerNode(uint)
 101         {
 102         }
 103
 104         /**
 105          * Get the effective supply of one node towards another one.
 106          * @param from The supplying node.
 107          * @param unused.
 108          */
 109         inline uint EffectiveSupply(const Node &from, const Node &)
 110         {
 111                 return from.Supply();
 112         }
 113
 114         /**
 115          * Check if there is any acceptance left for this node. In asymmetric distribution
 116          * nodes always accept as long as their demand > 0.
 117          * @param to The node to be checked.
 118          * @param to_anno Unused.
 119          */
 120         inline bool HasDemandLeft(const Node &to) { return to.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].Demand() > 0) {
 134                 uint demand_back = demand_forw * this->mod_size / 100;
 135                 uint undelivered = job[to_id].UndeliveredSupply();
 136                 if (demand_back > undelivered) {
 137                         demand_back = undelivered;
 138                         demand_forw = 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].Supply() > 0) {
 175                         supplies.push(node);
 176                         num_supplies++;
 177                 }
 178                 if (job[node].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 supply = scaler.EffectiveSupply(job[from_id], job[to_id]);
 209                         assert(supply > 0);
 210
 211                         /* Scale the distance by mod_dist around max_distance */
 212                         int32 distance = this->max_distance - (this->max_distance -
 213                                         (int32)DistanceMaxPlusManhattan(job[from_id].XY(), job[to_id].XY())) *
 214                                         this->mod_dist / 100;
 215
 216                         /* Scale the accuracy by distance around accuracy / 2 */
 217                         int32 divisor = this->accuracy * (this->mod_dist - 50) / 100 +
 218                                         this->accuracy * distance / this->max_distance + 1;
 219
 220                         assert(divisor > 0);
 221
 222                         uint demand_forw = 0;
 223                         if (divisor <= supply) {
 224                                 /* At first only distribute demand if
 225                                  * effective supply / accuracy divisor >= 1
 226                                  * Others are too small or too far away to be considered. */
 227                                 demand_forw = supply / divisor;
 228                         } else if (++chance > this->accuracy * num_demands * num_supplies) {
 229                                 /* After some trying, if there is still supply left, distribute
 230                                  * demand also to other nodes. */
 231                                 demand_forw = 1;
 232                         }
 233
 234                         demand_forw = min(demand_forw, job[from_id].UndeliveredSupply());
 235
 236                         scaler.SetDemands(job, from_id, to_id, demand_forw);
 237
 238                         if (scaler.HasDemandLeft(job[to_id])) {
 239                                 demands.push(to_id);
 240                         } else {
 241                                 num_demands--;
 242                         }
 243
 244                         if (job[from_id].UndeliveredSupply() == 0) break;
 245                 }
 246
 247                 if (job[from_id].UndeliveredSupply() != 0) {
 248                         supplies.push(from_id);
 249                 } else {
 250                         num_supplies--;
 251                 }
 252         }
 253 }
 254
 255 /**
 256  * Create the DemandCalculator and immediately do the calculation.
 257  * @param job Job to calculate the demands for.
 258  */
 259 DemandCalculator::DemandCalculator(LinkGraphJob &job) :
 260         max_distance(DistanceMaxPlusManhattan(TileXY(0,0), TileXY(MapMaxX(), MapMaxY())))
 261 {
 262         const LinkGraphSettings &settings = job.Settings();
 263         CargoID cargo = job.Cargo();
 264
 265         this->accuracy = settings.accuracy;
 266         this->mod_dist = settings.demand_distance;
 267         if (this->mod_dist > 100) {
 268                 /* Increase effect of mod_dist > 100 */
 269                 int over100 = this->mod_dist - 100;
 270                 this->mod_dist = 100 + over100 * over100;
 271         }
 272
 273         switch (settings.GetDistributionType(cargo)) {
 274                 case DT_SYMMETRIC:
 275                         this->CalcDemand<SymmetricScaler>(job, SymmetricScaler(settings.demand_size));
 276                         break;
 277                 case DT_ASYMMETRIC:
 278                         this->CalcDemand<AsymmetricScaler>(job, AsymmetricScaler());
 279                         break;
 280                 default:
 281                         /* Nothing to do. */
 282                         break;
 283         }
 284 }