1.1 --- a/test/min_cost_flow_test.cc Fri Aug 05 09:33:42 2011 +0200
1.2 +++ b/test/min_cost_flow_test.cc Mon Aug 08 12:36:16 2011 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2011
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -47,7 +47,7 @@
1.13 " 10 -2 0 0 0 -7 -2\n"
1.14 " 11 0 0 0 0 -10 0\n"
1.15 " 12 -20 -27 0 -30 -30 -20\n"
1.16 - "\n"
1.17 + "\n"
1.18 "@arcs\n"
1.19 " cost cap low1 low2 low3\n"
1.20 " 1 2 70 11 0 8 8\n"
1.21 @@ -93,7 +93,7 @@
1.22 struct Constraints {
1.23 void constraints() {
1.24 checkConcept<concepts::Digraph, GR>();
1.25 -
1.26 +
1.27 const Constraints& me = *this;
1.28
1.29 MCF mcf(me.g);
1.30 @@ -122,7 +122,7 @@
1.31 typedef concepts::ReadMap<Arc, Cost> CAM;
1.32 typedef concepts::WriteMap<Arc, Value> FlowMap;
1.33 typedef concepts::WriteMap<Node, Cost> PotMap;
1.34 -
1.35 +
1.36 GR g;
1.37 VAM lower;
1.38 VAM upper;
1.39 @@ -176,7 +176,7 @@
1.40 template < typename GR, typename LM, typename UM,
1.41 typename CM, typename SM, typename FM, typename PM >
1.42 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
1.43 - const CM& cost, const SM& supply, const FM& flow,
1.44 + const CM& cost, const SM& supply, const FM& flow,
1.45 const PM& pi, SupplyType type )
1.46 {
1.47 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.48 @@ -189,7 +189,7 @@
1.49 (red_cost > 0 && flow[e] == lower[e]) ||
1.50 (red_cost < 0 && flow[e] == upper[e]);
1.51 }
1.52 -
1.53 +
1.54 for (NodeIt n(gr); opt && n != INVALID; ++n) {
1.55 typename SM::Value sum = 0;
1.56 for (OutArcIt e(gr, n); e != INVALID; ++e)
1.57 @@ -202,7 +202,7 @@
1.58 opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
1.59 }
1.60 }
1.61 -
1.62 +
1.63 return opt;
1.64 }
1.65
1.66 @@ -227,7 +227,7 @@
1.67 red_supply[gr.target(a)] += lower[a];
1.68 }
1.69 }
1.70 -
1.71 +
1.72 for (NodeIt n(gr); n != INVALID; ++n) {
1.73 dual_cost -= red_supply[n] * pi[n];
1.74 }
1.75 @@ -236,7 +236,7 @@
1.76 cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
1.77 dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
1.78 }
1.79 -
1.80 +
1.81 return dual_cost == total;
1.82 }
1.83
1.84 @@ -308,7 +308,7 @@
1.85 .node("source", v)
1.86 .node("target", w)
1.87 .run();
1.88 -
1.89 +
1.90 // Build test digraphs with negative costs
1.91 Digraph neg_gr;
1.92 Node n1 = neg_gr.addNode();
1.93 @@ -318,7 +318,7 @@
1.94 Node n5 = neg_gr.addNode();
1.95 Node n6 = neg_gr.addNode();
1.96 Node n7 = neg_gr.addNode();
1.97 -
1.98 +
1.99 Arc a1 = neg_gr.addArc(n1, n2);
1.100 Arc a2 = neg_gr.addArc(n1, n3);
1.101 Arc a3 = neg_gr.addArc(n2, n4);
1.102 @@ -328,17 +328,17 @@
1.103 Arc a7 = neg_gr.addArc(n5, n6);
1.104 Arc a8 = neg_gr.addArc(n6, n7);
1.105 Arc a9 = neg_gr.addArc(n7, n5);
1.106 -
1.107 +
1.108 Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
1.109 ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
1.110 Digraph::NodeMap<int> neg_s(neg_gr, 0);
1.111 -
1.112 +
1.113 neg_l2[a7] = 1000;
1.114 neg_l2[a8] = -1000;
1.115 -
1.116 +
1.117 neg_s[n1] = 100;
1.118 neg_s[n4] = -100;
1.119 -
1.120 +
1.121 neg_c[a1] = 100;
1.122 neg_c[a2] = 30;
1.123 neg_c[a3] = 20;
1.124 @@ -422,7 +422,7 @@
1.125 neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
1.126 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
1.127 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18");
1.128 -
1.129 +
1.130 NetworkSimplex<Digraph> negs_mcf(negs_gr);
1.131 negs_mcf.costMap(negs_c).supplyMap(negs_s);
1.132 checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,