Index: src/work/athos/makefile =================================================================== --- src/work/athos/makefile (revision 607) +++ src/work/athos/makefile (revision 661) @@ -1,3 +1,3 @@ -BINARIES = minlengthpaths_test minlength_demo +BINARIES = min_cost_flow INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos} include ../makefile Index: src/work/athos/min_cost_flow.cc =================================================================== --- src/work/athos/min_cost_flow.cc (revision 659) +++ src/work/athos/min_cost_flow.cc (revision 661) @@ -1,4 +1,4 @@ #include -#include "test_tools.h" +//#include "test_tools.h" #include #include @@ -52,14 +52,14 @@ - 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); /* @@ -80,10 +80,10 @@ 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?"); @@ -91,5 +91,5 @@ 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?"); @@ -98,5 +98,5 @@ 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?"); Index: src/work/athos/mincostflow.h =================================================================== --- src/work/athos/mincostflow.h (revision 659) +++ src/work/athos/mincostflow.h (revision 661) @@ -12,6 +12,6 @@ #include #include -#include -#include +#include +#include namespace hugo { @@ -20,6 +20,6 @@ /// @{ - ///\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 /// /// @@ -31,5 +31,5 @@ /// \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 @@ -38,8 +38,8 @@ /// ///\author Attila Bernath - template + template class MinCostFlow { - typedef typename LengthMap::ValueType Length; + typedef typename CostMap::ValueType Cost; @@ -50,23 +50,24 @@ 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; - - class ModLengthMap { - //typedef typename ResGraphType::template NodeMap NodeMap; - typedef typename Graph::template NodeMap NodeMap; - const ResGraphType& res_graph; + typedef ResGraphWrapper ResGraph; + typedef typename ResGraph::Edge ResGraphEdge; + + 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)]); @@ -75,8 +76,8 @@ } - 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 @@ -85,5 +86,5 @@ //Input const Graph& graph; - const LengthMap& length; + const CostMap& cost; const SupplyDemandMap& supply_demand;//supply or demand of nodes @@ -92,12 +93,12 @@ //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; @@ -105,6 +106,6 @@ - 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){ } @@ -118,5 +119,5 @@ //Resetting variables from previous runs - //total_length = 0; + //total_cost = 0; typedef typename Graph::template NodeMap HeapMap; @@ -176,8 +177,9 @@ 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 @@ -196,5 +198,5 @@ 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 @@ -210,7 +212,7 @@ bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy); - ModLengthMap mod_length(res_graph, length, potential); - - Dijkstra dijkstra(res_graph, mod_length); + ModCostMap mod_cost(res_graph, cost, potential); + + Dijkstra dijkstra(res_graph, mod_cost); @@ -316,5 +318,5 @@ //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]; } @@ -329,9 +331,9 @@ 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]; */ } @@ -401,8 +403,8 @@ - ///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; } @@ -421,9 +423,9 @@ ///\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;