# HG changeset patch # User athos # Date 1085497871 0 # Node ID d306e777117ec00e25dd38ebe9a31219d7fb65f4 # Parent edb42cb9d352a5d95ef636bb18a88f4fd8819c27 Corrected some obvious errors. diff -r edb42cb9d352 -r d306e777117e src/hugo/mincostflows.h --- a/src/hugo/mincostflows.h Tue May 25 13:13:52 2004 +0000 +++ b/src/hugo/mincostflows.h Tue May 25 15:11:11 2004 +0000 @@ -11,7 +11,7 @@ #include #include #include -#include +#include namespace hugo { @@ -90,7 +90,8 @@ //To store the flow EdgeIntMap flow; //To store the potentila (dual variables) - typename Graph::template NodeMap potential; + typedef typename Graph::template NodeMap PotentialMap; + PotentialMap potential; Length total_length; @@ -184,7 +185,7 @@ ///Returns a const reference to the NodeMap \c potential (the dual solution). /// \pre \ref run() must be called before using this function. - const EdgeIntMap &getPotential() const { return potential;} + const PotentialMap &getPotential() const { return potential;} ///This function checks, whether the given solution is optimal ///Running after a \c run() should return with true diff -r edb42cb9d352 -r d306e777117e src/work/athos/makefile --- a/src/work/athos/makefile Tue May 25 13:13:52 2004 +0000 +++ b/src/work/athos/makefile Tue May 25 15:11:11 2004 +0000 @@ -1,4 +1,4 @@ -BINARIES = minlengthpaths_test minlength_demo +BINARIES = min_cost_flow INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos} include ../makefile diff -r edb42cb9d352 -r d306e777117e src/work/athos/min_cost_flow.cc --- a/src/work/athos/min_cost_flow.cc Tue May 25 13:13:52 2004 +0000 +++ b/src/work/athos/min_cost_flow.cc Tue May 25 15:11:11 2004 +0000 @@ -1,5 +1,5 @@ #include -#include "test_tools.h" +//#include "test_tools.h" #include #include //#include @@ -51,16 +51,16 @@ Edge v5_t=graph.addEdge(v5, t); - ListGraph::EdgeMap length(graph); + ListGraph::EdgeMap cost(graph); - length.set(s_v1, 6); - length.set(v1_v2, 4); - length.set(s_v3, 10); - length.set(v2_v4, 5); - length.set(v2_v5, 1); - length.set(v3_v5, 4); - length.set(v4_t, 8); - length.set(v5_t, 8); + cost.set(s_v1, 6); + cost.set(v1_v2, 4); + cost.set(s_v3, 10); + cost.set(v2_v4, 5); + cost.set(v2_v5, 1); + cost.set(v3_v5, 4); + cost.set(v4_t, 8); + cost.set(v5_t, 8); /* ListGraph::EdgeMap capacity(graph); @@ -79,25 +79,25 @@ std::cout << "Enhanced capacity scaling algorithm test (for the mincostflow problem)..." << std::endl; MinCostFlow< ListGraph, ListGraph::EdgeMap, ListGraph::NodeMap > - min_cost_flow_test(graph, length, supply_demand); + min_cost_flow_test(graph, cost, supply_demand); int k=1; /* - check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total length should be 19"); + check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19"); check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); k=2; - check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total length should be 41"); + check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41"); check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); k=4; - check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total length should be 64"); + check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64"); check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); diff -r edb42cb9d352 -r d306e777117e src/work/athos/mincostflow.h --- a/src/work/athos/mincostflow.h Tue May 25 13:13:52 2004 +0000 +++ b/src/work/athos/mincostflow.h Tue May 25 15:11:11 2004 +0000 @@ -11,16 +11,16 @@ #include #include #include -#include -#include +#include +#include namespace hugo { /// \addtogroup galgs /// @{ - ///\brief Implementation of an algorithm for finding the minimum cost flow - /// of given value in an uncapacitated network + ///\brief Implementation of an algorithm for solving the minimum cost general + /// flow problem in an uncapacitated network /// /// /// The class \ref hugo::MinCostFlow "MinCostFlow" implements @@ -30,17 +30,17 @@ /// /// \warning It is assumed here that the problem has a feasible solution /// - /// The range of the length (weight) function is nonnegative reals but + /// The range of the cost (weight) function is nonnegative reals but /// the range of capacity function is the set of nonnegative integers. /// It is not a polinomial time algorithm for counting the minimum cost /// maximal flow, since it counts the minimum cost flow for every value 0..M /// where \c M is the value of the maximal flow. /// ///\author Attila Bernath - template + template class MinCostFlow { - typedef typename LengthMap::ValueType Length; + typedef typename CostMap::ValueType Cost; typedef typename SupplyDemandMap::ValueType SupplyDemand; @@ -49,63 +49,64 @@ typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::template EdgeMap EdgeIntMap; + typedef typename Graph::template EdgeMap FlowMap; + typedef ConstMap ConstEdgeMap; // typedef ConstMap ConstMap; - typedef ResGraphWrapper ResGraphType; - typedef typename ResGraphType::Edge ResGraphEdge; + typedef ResGraphWrapper ResGraph; + typedef typename ResGraph::Edge ResGraphEdge; - class ModLengthMap { - //typedef typename ResGraphType::template NodeMap NodeMap; - typedef typename Graph::template NodeMap NodeMap; - const ResGraphType& res_graph; + class ModCostMap { + //typedef typename ResGraph::template NodeMap NodeMap; + typedef typename Graph::template NodeMap NodeMap; + const ResGraph& res_graph; // const EdgeIntMap& rev; - const LengthMap &ol; + const CostMap &ol; const NodeMap &pot; public : - typedef typename LengthMap::KeyType KeyType; - typedef typename LengthMap::ValueType ValueType; + typedef typename CostMap::KeyType KeyType; + typedef typename CostMap::ValueType ValueType; - ValueType operator[](typename ResGraphType::Edge e) const { + ValueType operator[](typename ResGraph::Edge e) const { if (res_graph.forward(e)) return ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]); else return -ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]); } - ModLengthMap(const ResGraphType& _res_graph, - const LengthMap &o, const NodeMap &p) : + ModCostMap(const ResGraph& _res_graph, + const CostMap &o, const NodeMap &p) : res_graph(_res_graph), /*rev(_rev),*/ ol(o), pot(p){}; - };//ModLengthMap + };//ModCostMap protected: //Input const Graph& graph; - const LengthMap& length; + const CostMap& cost; const SupplyDemandMap& supply_demand;//supply or demand of nodes //auxiliary variables //To store the flow - EdgeIntMap flow; + FlowMap flow; //To store the potentila (dual variables) - typename Graph::template NodeMap potential; + typename Graph::template NodeMap potential; //To store excess-deficit values SupplyDemandMap excess_deficit; - Length total_length; + Cost total_cost; public : - MinCostFlow(Graph& _graph, LengthMap& _length, SupplyDemandMap& _supply_demand) : graph(_graph), - length(_length), supply_demand(_supply_demand), flow(_graph), potential(_graph){ } + MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph), + cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ } ///Runs the algorithm. @@ -117,7 +118,7 @@ void run() { //Resetting variables from previous runs - //total_length = 0; + //total_cost = 0; typedef typename Graph::template NodeMap HeapMap; typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap, @@ -175,10 +176,11 @@ //can be the maximum deficit here SupplyDemand max_excess = delta; - //ConstMap ConstEdgeMap; - + ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph + ConstEdgeMap const_inf_map(MAX_INT); + //We need a residual graph which is uncapacitated - ResGraphType res_graph(graph, flow); + ResGraph res_graph(graph, const_inf_map, flow); //An EdgeMap to tell which arcs are abundant template typename Graph::EdgeMap abundant_arcs(graph); @@ -195,7 +197,7 @@ typedef ResGraphWrapper ResAbGraph; //Again uncapacitated - ResAbGraph res_ab_graph(abundant_graph, flow); + ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow); //We need things for the bfs typename ResAbGraph::NodeMap bfs_reached(res_ab_graph); @@ -209,9 +211,9 @@ NullMap > bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy); - ModLengthMap mod_length(res_graph, length, potential); + ModCostMap mod_cost(res_graph, cost, potential); - Dijkstra dijkstra(res_graph, mod_length); + Dijkstra dijkstra(res_graph, mod_cost); while (max_excess > 0){ @@ -315,7 +317,7 @@ */ //We have to change the potential - FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){ + FOR_EACH_LOC(typename ResGraph::NodeIt, n, res_graph){ potential[n] += dijkstra.distMap()[n]; } @@ -328,11 +330,11 @@ n = dijkstra.predNode(n); res_graph.augment(e,delta); /* - //Let's update the total length + //Let's update the total cost if (res_graph.forward(e)) - total_length += length[e]; + total_cost += cost[e]; else - total_length -= length[e]; + total_cost -= cost[e]; */ } @@ -400,10 +402,10 @@ - ///This function gives back the total length of the found paths. + ///This function gives back the total cost of the found paths. ///Assumes that \c run() has been run and nothing changed since then. - Length totalLength(){ - return total_length; + Cost totalCost(){ + return total_cost; } ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must @@ -420,11 +422,11 @@ /// ///\todo Is this OK here? bool checkComplementarySlackness(){ - Length mod_pot; - Length fl_e; + Cost mod_pot; + Cost fl_e; FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){ //C^{\Pi}_{i,j} - mod_pot = length[e]-potential[graph.head(e)]+potential[graph.tail(e)]; + mod_pot = cost[e]-potential[graph.head(e)]+potential[graph.tail(e)]; fl_e = flow[e]; // std::cout << fl_e << std::endl; if (0