1.1 --- a/src/hugo/mincostflows.h Tue May 25 13:13:52 2004 +0000
1.2 +++ b/src/hugo/mincostflows.h Tue May 25 15:11:11 2004 +0000
1.3 @@ -11,7 +11,7 @@
1.4 #include <hugo/graph_wrapper.h>
1.5 #include <hugo/maps.h>
1.6 #include <vector>
1.7 -#include <for_each_macros.h>
1.8 +#include <hugo/for_each_macros.h>
1.9
1.10 namespace hugo {
1.11
1.12 @@ -90,7 +90,8 @@
1.13 //To store the flow
1.14 EdgeIntMap flow;
1.15 //To store the potentila (dual variables)
1.16 - typename Graph::template NodeMap<Length> potential;
1.17 + typedef typename Graph::template NodeMap<Length> PotentialMap;
1.18 + PotentialMap potential;
1.19
1.20
1.21 Length total_length;
1.22 @@ -184,7 +185,7 @@
1.23
1.24 ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.25 /// \pre \ref run() must be called before using this function.
1.26 - const EdgeIntMap &getPotential() const { return potential;}
1.27 + const PotentialMap &getPotential() const { return potential;}
1.28
1.29 ///This function checks, whether the given solution is optimal
1.30 ///Running after a \c run() should return with true
2.1 --- a/src/work/athos/makefile Tue May 25 13:13:52 2004 +0000
2.2 +++ b/src/work/athos/makefile Tue May 25 15:11:11 2004 +0000
2.3 @@ -1,4 +1,4 @@
2.4 -BINARIES = minlengthpaths_test minlength_demo
2.5 +BINARIES = min_cost_flow
2.6 INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
2.7 include ../makefile
2.8
3.1 --- a/src/work/athos/min_cost_flow.cc Tue May 25 13:13:52 2004 +0000
3.2 +++ b/src/work/athos/min_cost_flow.cc Tue May 25 15:11:11 2004 +0000
3.3 @@ -1,5 +1,5 @@
3.4 #include <iostream>
3.5 -#include "test_tools.h"
3.6 +//#include "test_tools.h"
3.7 #include <hugo/list_graph.h>
3.8 #include <mincostflow.h>
3.9 //#include <path.h>
3.10 @@ -51,16 +51,16 @@
3.11 Edge v5_t=graph.addEdge(v5, t);
3.12
3.13
3.14 - ListGraph::EdgeMap<int> length(graph);
3.15 + ListGraph::EdgeMap<int> cost(graph);
3.16
3.17 - length.set(s_v1, 6);
3.18 - length.set(v1_v2, 4);
3.19 - length.set(s_v3, 10);
3.20 - length.set(v2_v4, 5);
3.21 - length.set(v2_v5, 1);
3.22 - length.set(v3_v5, 4);
3.23 - length.set(v4_t, 8);
3.24 - length.set(v5_t, 8);
3.25 + cost.set(s_v1, 6);
3.26 + cost.set(v1_v2, 4);
3.27 + cost.set(s_v3, 10);
3.28 + cost.set(v2_v4, 5);
3.29 + cost.set(v2_v5, 1);
3.30 + cost.set(v3_v5, 4);
3.31 + cost.set(v4_t, 8);
3.32 + cost.set(v5_t, 8);
3.33
3.34 /*
3.35 ListGraph::EdgeMap<int> capacity(graph);
3.36 @@ -79,25 +79,25 @@
3.37 std::cout << "Enhanced capacity scaling algorithm test (for the mincostflow problem)..." << std::endl;
3.38
3.39 MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
3.40 - min_cost_flow_test(graph, length, supply_demand);
3.41 + min_cost_flow_test(graph, cost, supply_demand);
3.42
3.43 int k=1;
3.44
3.45 /*
3.46 - check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total length should be 19");
3.47 + check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
3.48
3.49 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
3.50
3.51 k=2;
3.52
3.53 - check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total length should be 41");
3.54 + check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41");
3.55
3.56 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
3.57
3.58
3.59 k=4;
3.60
3.61 - check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total length should be 64");
3.62 + check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64");
3.63
3.64 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
3.65
4.1 --- a/src/work/athos/mincostflow.h Tue May 25 13:13:52 2004 +0000
4.2 +++ b/src/work/athos/mincostflow.h Tue May 25 15:11:11 2004 +0000
4.3 @@ -11,16 +11,16 @@
4.4 #include <hugo/maps.h>
4.5 #include <vector>
4.6 #include <list>
4.7 -#include <for_each_macros.h>
4.8 -#include <hugo/union_find.h>
4.9 +#include <hugo/for_each_macros.h>
4.10 +#include <hugo/unionfind.h>
4.11
4.12 namespace hugo {
4.13
4.14 /// \addtogroup galgs
4.15 /// @{
4.16
4.17 - ///\brief Implementation of an algorithm for finding the minimum cost flow
4.18 - /// of given value in an uncapacitated network
4.19 + ///\brief Implementation of an algorithm for solving the minimum cost general
4.20 + /// flow problem in an uncapacitated network
4.21 ///
4.22 ///
4.23 /// The class \ref hugo::MinCostFlow "MinCostFlow" implements
4.24 @@ -30,17 +30,17 @@
4.25 ///
4.26 /// \warning It is assumed here that the problem has a feasible solution
4.27 ///
4.28 - /// The range of the length (weight) function is nonnegative reals but
4.29 + /// The range of the cost (weight) function is nonnegative reals but
4.30 /// the range of capacity function is the set of nonnegative integers.
4.31 /// It is not a polinomial time algorithm for counting the minimum cost
4.32 /// maximal flow, since it counts the minimum cost flow for every value 0..M
4.33 /// where \c M is the value of the maximal flow.
4.34 ///
4.35 ///\author Attila Bernath
4.36 - template <typename Graph, typename LengthMap, typename SupplyDemandMap>
4.37 + template <typename Graph, typename CostMap, typename SupplyDemandMap>
4.38 class MinCostFlow {
4.39
4.40 - typedef typename LengthMap::ValueType Length;
4.41 + typedef typename CostMap::ValueType Cost;
4.42
4.43
4.44 typedef typename SupplyDemandMap::ValueType SupplyDemand;
4.45 @@ -49,63 +49,64 @@
4.46 typedef typename Graph::NodeIt NodeIt;
4.47 typedef typename Graph::Edge Edge;
4.48 typedef typename Graph::OutEdgeIt OutEdgeIt;
4.49 - typedef typename Graph::template EdgeMap<int> EdgeIntMap;
4.50 + typedef typename Graph::template EdgeMap<SupplyDemand> FlowMap;
4.51 + typedef ConstMap<Edge,SupplyDemand> ConstEdgeMap;
4.52
4.53 // typedef ConstMap<Edge,int> ConstMap;
4.54
4.55 - typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
4.56 - typedef typename ResGraphType::Edge ResGraphEdge;
4.57 + typedef ResGraphWrapper<const Graph,int,ConstEdgeMap,FlowMap> ResGraph;
4.58 + typedef typename ResGraph::Edge ResGraphEdge;
4.59
4.60 - class ModLengthMap {
4.61 - //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
4.62 - typedef typename Graph::template NodeMap<Length> NodeMap;
4.63 - const ResGraphType& res_graph;
4.64 + class ModCostMap {
4.65 + //typedef typename ResGraph::template NodeMap<Cost> NodeMap;
4.66 + typedef typename Graph::template NodeMap<Cost> NodeMap;
4.67 + const ResGraph& res_graph;
4.68 // const EdgeIntMap& rev;
4.69 - const LengthMap &ol;
4.70 + const CostMap &ol;
4.71 const NodeMap &pot;
4.72 public :
4.73 - typedef typename LengthMap::KeyType KeyType;
4.74 - typedef typename LengthMap::ValueType ValueType;
4.75 + typedef typename CostMap::KeyType KeyType;
4.76 + typedef typename CostMap::ValueType ValueType;
4.77
4.78 - ValueType operator[](typename ResGraphType::Edge e) const {
4.79 + ValueType operator[](typename ResGraph::Edge e) const {
4.80 if (res_graph.forward(e))
4.81 return ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]);
4.82 else
4.83 return -ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]);
4.84 }
4.85
4.86 - ModLengthMap(const ResGraphType& _res_graph,
4.87 - const LengthMap &o, const NodeMap &p) :
4.88 + ModCostMap(const ResGraph& _res_graph,
4.89 + const CostMap &o, const NodeMap &p) :
4.90 res_graph(_res_graph), /*rev(_rev),*/ ol(o), pot(p){};
4.91 - };//ModLengthMap
4.92 + };//ModCostMap
4.93
4.94
4.95 protected:
4.96
4.97 //Input
4.98 const Graph& graph;
4.99 - const LengthMap& length;
4.100 + const CostMap& cost;
4.101 const SupplyDemandMap& supply_demand;//supply or demand of nodes
4.102
4.103
4.104 //auxiliary variables
4.105
4.106 //To store the flow
4.107 - EdgeIntMap flow;
4.108 + FlowMap flow;
4.109 //To store the potentila (dual variables)
4.110 - typename Graph::template NodeMap<Length> potential;
4.111 + typename Graph::template NodeMap<Cost> potential;
4.112 //To store excess-deficit values
4.113 SupplyDemandMap excess_deficit;
4.114
4.115
4.116 - Length total_length;
4.117 + Cost total_cost;
4.118
4.119
4.120 public :
4.121
4.122
4.123 - MinCostFlow(Graph& _graph, LengthMap& _length, SupplyDemandMap& _supply_demand) : graph(_graph),
4.124 - length(_length), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
4.125 + MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph),
4.126 + cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
4.127
4.128
4.129 ///Runs the algorithm.
4.130 @@ -117,7 +118,7 @@
4.131 void run() {
4.132
4.133 //Resetting variables from previous runs
4.134 - //total_length = 0;
4.135 + //total_cost = 0;
4.136
4.137 typedef typename Graph::template NodeMap<int> HeapMap;
4.138 typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
4.139 @@ -175,10 +176,11 @@
4.140 //can be the maximum deficit here
4.141 SupplyDemand max_excess = delta;
4.142
4.143 - //ConstMap<Edge,SupplyDemand> ConstEdgeMap;
4.144 -
4.145 + ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph
4.146 + ConstEdgeMap const_inf_map(MAX_INT);
4.147 +
4.148 //We need a residual graph which is uncapacitated
4.149 - ResGraphType res_graph(graph, flow);
4.150 + ResGraph res_graph(graph, const_inf_map, flow);
4.151
4.152 //An EdgeMap to tell which arcs are abundant
4.153 template typename Graph::EdgeMap<bool> abundant_arcs(graph);
4.154 @@ -195,7 +197,7 @@
4.155 typedef ResGraphWrapper<const AbundantGraph,int,CapacityMap,EdgeIntMap>
4.156 ResAbGraph;
4.157 //Again uncapacitated
4.158 - ResAbGraph res_ab_graph(abundant_graph, flow);
4.159 + ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);
4.160
4.161 //We need things for the bfs
4.162 typename ResAbGraph::NodeMap<bool> bfs_reached(res_ab_graph);
4.163 @@ -209,9 +211,9 @@
4.164 NullMap<typename ResAbGraph::Node, int> >
4.165 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
4.166
4.167 - ModLengthMap mod_length(res_graph, length, potential);
4.168 + ModCostMap mod_cost(res_graph, cost, potential);
4.169
4.170 - Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
4.171 + Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);
4.172
4.173
4.174 while (max_excess > 0){
4.175 @@ -315,7 +317,7 @@
4.176 */
4.177
4.178 //We have to change the potential
4.179 - FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
4.180 + FOR_EACH_LOC(typename ResGraph::NodeIt, n, res_graph){
4.181 potential[n] += dijkstra.distMap()[n];
4.182 }
4.183
4.184 @@ -328,11 +330,11 @@
4.185 n = dijkstra.predNode(n);
4.186 res_graph.augment(e,delta);
4.187 /*
4.188 - //Let's update the total length
4.189 + //Let's update the total cost
4.190 if (res_graph.forward(e))
4.191 - total_length += length[e];
4.192 + total_cost += cost[e];
4.193 else
4.194 - total_length -= length[e];
4.195 + total_cost -= cost[e];
4.196 */
4.197 }
4.198
4.199 @@ -400,10 +402,10 @@
4.200
4.201
4.202
4.203 - ///This function gives back the total length of the found paths.
4.204 + ///This function gives back the total cost of the found paths.
4.205 ///Assumes that \c run() has been run and nothing changed since then.
4.206 - Length totalLength(){
4.207 - return total_length;
4.208 + Cost totalCost(){
4.209 + return total_cost;
4.210 }
4.211
4.212 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
4.213 @@ -420,11 +422,11 @@
4.214 ///
4.215 ///\todo Is this OK here?
4.216 bool checkComplementarySlackness(){
4.217 - Length mod_pot;
4.218 - Length fl_e;
4.219 + Cost mod_pot;
4.220 + Cost fl_e;
4.221 FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
4.222 //C^{\Pi}_{i,j}
4.223 - mod_pot = length[e]-potential[graph.head(e)]+potential[graph.tail(e)];
4.224 + mod_pot = cost[e]-potential[graph.head(e)]+potential[graph.tail(e)];
4.225 fl_e = flow[e];
4.226 // std::cout << fl_e << std::endl;
4.227 if (0<fl_e && fl_e<capacity[e]){