r669:4faca85d40e6
Tue, 12 May 2009 20:08:23
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -72,84 +72,87 @@ |
| 72 | 72 |
"11 10 20 14 0 6 -20\n" |
| 73 | 73 |
"12 11 30 10 0 0 -10\n" |
| 74 | 74 |
"\n" |
| 75 | 75 |
"@attributes\n" |
| 76 | 76 |
"source 1\n" |
| 77 | 77 |
"target 12\n"; |
| 78 | 78 |
|
| 79 | 79 |
|
| 80 | 80 |
enum SupplyType {
|
| 81 | 81 |
EQ, |
| 82 | 82 |
GEQ, |
| 83 | 83 |
LEQ |
| 84 | 84 |
}; |
| 85 | 85 |
|
| 86 | 86 |
// Check the interface of an MCF algorithm |
| 87 | 87 |
template <typename GR, typename Value, typename Cost> |
| 88 | 88 |
class McfClassConcept |
| 89 | 89 |
{
|
| 90 | 90 |
public: |
| 91 | 91 |
|
| 92 | 92 |
template <typename MCF> |
| 93 | 93 |
struct Constraints {
|
| 94 | 94 |
void constraints() {
|
| 95 | 95 |
checkConcept<concepts::Digraph, GR>(); |
| 96 |
|
|
| 97 |
const Constraints& me = *this; |
|
| 96 | 98 |
|
| 97 |
MCF mcf(g); |
|
| 99 |
MCF mcf(me.g); |
|
| 98 | 100 |
const MCF& const_mcf = mcf; |
| 99 | 101 |
|
| 100 | 102 |
b = mcf.reset() |
| 101 |
.lowerMap(lower) |
|
| 102 |
.upperMap(upper) |
|
| 103 |
.costMap(cost) |
|
| 104 |
.supplyMap(sup) |
|
| 105 |
. |
|
| 103 |
.lowerMap(me.lower) |
|
| 104 |
.upperMap(me.upper) |
|
| 105 |
.costMap(me.cost) |
|
| 106 |
.supplyMap(me.sup) |
|
| 107 |
.stSupply(me.n, me.n, me.k) |
|
| 106 | 108 |
.run(); |
| 107 | 109 |
|
| 108 | 110 |
c = const_mcf.totalCost(); |
| 109 | 111 |
x = const_mcf.template totalCost<double>(); |
| 110 |
v = const_mcf.flow(a); |
|
| 111 |
c = const_mcf.potential(n); |
|
| 112 |
v = const_mcf.flow(me.a); |
|
| 113 |
c = const_mcf.potential(me.n); |
|
| 112 | 114 |
const_mcf.flowMap(fm); |
| 113 | 115 |
const_mcf.potentialMap(pm); |
| 114 | 116 |
} |
| 115 | 117 |
|
| 116 | 118 |
typedef typename GR::Node Node; |
| 117 | 119 |
typedef typename GR::Arc Arc; |
| 118 | 120 |
typedef concepts::ReadMap<Node, Value> NM; |
| 119 | 121 |
typedef concepts::ReadMap<Arc, Value> VAM; |
| 120 | 122 |
typedef concepts::ReadMap<Arc, Cost> CAM; |
| 121 | 123 |
typedef concepts::WriteMap<Arc, Value> FlowMap; |
| 122 | 124 |
typedef concepts::WriteMap<Node, Cost> PotMap; |
| 125 |
|
|
| 126 |
GR g; |
|
| 127 |
VAM lower; |
|
| 128 |
VAM upper; |
|
| 129 |
CAM cost; |
|
| 130 |
NM sup; |
|
| 131 |
Node n; |
|
| 132 |
Arc a; |
|
| 133 |
Value k; |
|
| 123 | 134 |
|
| 124 |
const GR &g; |
|
| 125 |
const VAM &lower; |
|
| 126 |
const VAM &upper; |
|
| 127 |
const CAM &cost; |
|
| 128 |
const NM ⊃ |
|
| 129 |
const Node &n; |
|
| 130 |
const Arc &a; |
|
| 131 |
const Value &k; |
|
| 132 | 135 |
FlowMap fm; |
| 133 | 136 |
PotMap pm; |
| 134 | 137 |
bool b; |
| 135 | 138 |
double x; |
| 136 | 139 |
typename MCF::Value v; |
| 137 | 140 |
typename MCF::Cost c; |
| 138 | 141 |
}; |
| 139 | 142 |
|
| 140 | 143 |
}; |
| 141 | 144 |
|
| 142 | 145 |
|
| 143 | 146 |
// Check the feasibility of the given flow (primal soluiton) |
| 144 | 147 |
template < typename GR, typename LM, typename UM, |
| 145 | 148 |
typename SM, typename FM > |
| 146 | 149 |
bool checkFlow( const GR& gr, const LM& lower, const UM& upper, |
| 147 | 150 |
const SM& supply, const FM& flow, |
| 148 | 151 |
SupplyType type = EQ ) |
| 149 | 152 |
{
|
| 150 | 153 |
TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
| 151 | 154 |
|
| 152 | 155 |
for (ArcIt e(gr); e != INVALID; ++e) {
|
| 153 | 156 |
if (flow[e] < lower[e] || flow[e] > upper[e]) return false; |
| 154 | 157 |
} |
| 155 | 158 |
|
0 comments (0 inline)