src/linkgraph/mcf.h

   1 /** @file mcf.h Declaration of Multi-Commodity-Flow solver */
   2
   3 #ifndef MCF_H
   4 #define MCF_H
   5
   6 #include "linkgraphjob_base.h"
   7
   8 typedef std::vector<Path *> PathVector;
   9
  10 /**
  11  * Multi-commodity flow calculating base class.
  12  */
  13 class MultiCommodityFlow {
  14 protected:
  15         /**
  16          * Constructor.
  17          * @param job Link graph job being executed.
  18          */
  19         MultiCommodityFlow(LinkGraphJob &job) : job(job),
  20                         max_saturation(job.Settings().short_path_saturation)
  21         {}
  22
  23         template<class Tannotation, class Tedge_iterator>
  24         void Dijkstra(NodeID from, PathVector &paths);
  25
  26         uint PushFlow(Node &node, NodeID to, Path *path, uint accuracy, uint max_saturation);
  27
  28         void CleanupPaths(NodeID source, PathVector &paths);
  29
  30         LinkGraphJob &job;   ///< Job we're working with.
  31         uint max_saturation; ///< Maximum saturation for edges.
  32 };
  33
  34 /**
  35  * First pass of the MCF calculation. Saturates shortest paths first, creates
  36  * new paths if needed, eliminates cycles. This calculation is of exponential
  37  * complexity in the number of nodes but the constant factors are sufficiently
  38  * small to make it usable for most real-life link graph components. You can
  39  * deal with performance problems that might occur here in multiple ways:
  40  * - The overall accuracy is used here to determine how much flow is assigned
  41  *   in each loop. The lower the accuracy, the more flow is assigned, the less
  42  *   loops it takes to assign all flow.
  43  * - The short_path_saturation setting determines when this pass stops. The
  44  *   lower you set it, the less flow will be assigned in this pass, the less
  45  *   time it will take.
  46  * - You can increase the recalculation interval to allow for longer running
  47  *   times without creating lags.
  48  */
  49 class MCF1stPass : public MultiCommodityFlow {
  50 private:
  51         bool EliminateCycles();
  52         bool EliminateCycles(PathVector &path, NodeID origin_id, NodeID next_id);
  53         void EliminateCycle(PathVector &path, Path *cycle_begin, uint flow);
  54         uint FindCycleFlow(const PathVector &path, const Path *cycle_begin);
  55 public:
  56         MCF1stPass(LinkGraphJob &job);
  57 };
  58
  59 /**
  60  * Second pass of the MCF calculation. Saturates paths with most capacity left
  61  * first and doesn't create any paths along edges that haven't been visited in
  62  * the first pass. This is why it doesn't have to do any cycle detection and
  63  * elimination. As cycle detection is the most intense problem in the first
  64  * pass this pass is cheaper. The accuracy is used here, too.
  65  */
  66 class MCF2ndPass : public MultiCommodityFlow {
  67 public:
  68         MCF2ndPass(LinkGraphJob &job);
  69 };
  70
  71 /**
  72  * Link graph handler for MCF. Creates MultiCommodityFlow instance according to
  73  * the template parameter.
  74  */
  75 template<class Tpass>
  76 class MCFHandler : public ComponentHandler {
  77 public:
  78
  79         /**
  80          * Run the calculation.
  81          * @param graph Component to be calculated.
  82          */
  83         void Run(LinkGraphJob &job) const override { Tpass pass(job); }
  84 };
  85
  86 #endif /* MCF_H */