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