mcf.h

Go to the documentation of this file.

 
#ifndef MCF_H
#define MCF_H
 
#include "linkgraphjob_base.h"
 
typedef std::vector<Path *> PathVector;
 
class MultiCommodityFlow {
protected:
  MultiCommodityFlow(LinkGraphJob &job) : job(job),
      max_saturation(job.Settings().short_path_saturation)
  {}
 
  template<class Tannotation, class Tedge_iterator>
  void Dijkstra(NodeID from, PathVector &paths);
 
  uint PushFlow(Node &node, NodeID to, Path *path, uint accuracy, uint max_saturation);
 
  void CleanupPaths(NodeID source, PathVector &paths);
 
  LinkGraphJob &job;   
  uint max_saturation; 
};
 
class MCF1stPass : public MultiCommodityFlow {
private:
  bool EliminateCycles();
  bool EliminateCycles(PathVector &path, NodeID origin_id, NodeID next_id);
  void EliminateCycle(PathVector &path, Path *cycle_begin, uint flow);
  uint FindCycleFlow(const PathVector &path, const Path *cycle_begin);
public:
  MCF1stPass(LinkGraphJob &job);
};
 
class MCF2ndPass : public MultiCommodityFlow {
public:
  MCF2ndPass(LinkGraphJob &job);
};
 
template<class Tpass>
class MCFHandler : public ComponentHandler {
public:
 
  void Run(LinkGraphJob &job) const override { Tpass pass(job); }
};
 
#endif /* MCF_H */