mcf.h

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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */
 
#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 */