Changeset 661:d306e777117e in lemon-0.x

Timestamp:

05/25/04 17:11:11 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@864

Message:

Corrected some obvious errors.

Location:

src

Files:

• hugo/mincostflows.h (modified) (3 diffs)
• work/athos/makefile (modified) (1 diff)
• work/athos/min_cost_flow.cc (modified) (5 diffs)
• work/athos/mincostflow.h (modified) (17 diffs)

src/hugo/mincostflows.h

@@ -12 +12 @@
 #include <hugo/maps.h>
 #include <vector>
-#include <for_each_macros.h>
+#include <hugo/for_each_macros.h>
 
 namespace hugo {
@@ -91 +91 @@
     EdgeIntMap flow; 
     //To store the potentila (dual variables)
-    typename Graph::template NodeMap<Length> potential;
+    typedef typename Graph::template NodeMap<Length> PotentialMap;
+    PotentialMap potential;
     
 
@@ -185 +186 @@
   ///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

src/work/athos/makefile

@@ -1 @@
-BINARIES = minlengthpaths_test minlength_demo
+BINARIES = min_cost_flow
 INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos} 
 include ../makefile

src/work/athos/min_cost_flow.cc

@@ -1 +1 @@
 #include <iostream>
-#include "test_tools.h"
+//#include "test_tools.h"
 #include <hugo/list_graph.h>
 #include <mincostflow.h>
@@ -52 +52 @@
   
 
-  ListGraph::EdgeMap<int> length(graph);
+  ListGraph::EdgeMap<int> 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 +80 @@
 
   MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
-    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 +91 @@
   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 +98 @@
   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?");

src/work/athos/mincostflow.h

@@ -12 +12 @@
 #include <vector>
 #include <list>
-#include <for_each_macros.h>
-#include <hugo/union_find.h>
+#include <hugo/for_each_macros.h>
+#include <hugo/unionfind.h>
 
 namespace hugo {
@@ -20 +20 @@
 /// @{
 
-  ///\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 +31 @@
   /// \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 +38 @@
   ///
   ///\author Attila Bernath
-  template <typename Graph, typename LengthMap, typename SupplyDemandMap>
+  template <typename Graph, typename CostMap, typename SupplyDemandMap>
   class MinCostFlow {
 
-    typedef typename LengthMap::ValueType Length;
+    typedef typename CostMap::ValueType Cost;
 
 
@@ -50 +50 @@
     typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
+    typedef typename Graph::template EdgeMap<SupplyDemand> FlowMap;
+    typedef ConstMap<Edge,SupplyDemand> ConstEdgeMap;
 
     //    typedef ConstMap<Edge,int> ConstMap;
 
-    typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
-    typedef typename ResGraphType::Edge ResGraphEdge;
-
-    class ModLengthMap {   
-      //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
-      typedef typename Graph::template NodeMap<Length> NodeMap;
-      const ResGraphType& res_graph;
+    typedef ResGraphWrapper<const Graph,int,ConstEdgeMap,FlowMap> ResGraph;
+    typedef typename ResGraph::Edge ResGraphEdge;
+
+    class ModCostMap {   
+      //typedef typename ResGraph::template NodeMap<Cost> NodeMap;
+      typedef typename Graph::template NodeMap<Cost> 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 +76 @@
       }     
         
-      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 +86 @@
     //Input
     const Graph& graph;
-    const LengthMap& length;
+    const CostMap& cost;
     const SupplyDemandMap& supply_demand;//supply or demand of nodes
 
@@ -92 +93 @@
 
     //To store the flow
-    EdgeIntMap flow; 
+    FlowMap flow; 
     //To store the potentila (dual variables)
-    typename Graph::template NodeMap<Length> potential;
+    typename Graph::template NodeMap<Cost> potential;
     //To store excess-deficit values
     SupplyDemandMap excess_deficit;
     
 
-    Length total_length;
+    Cost total_cost;
 
 
@@ -105 +106 @@
 
 
-    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 +119 @@
 
       //Resetting variables from previous runs
-      //total_length = 0;
+      //total_cost = 0;
 
       typedef typename Graph::template NodeMap<int> HeapMap;
@@ -176 +177 @@
       SupplyDemand max_excess = delta;
       
-      //ConstMap<Edge,SupplyDemand> 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 +198 @@
         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 +212 @@
         bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
       
-      ModLengthMap mod_length(res_graph, length, potential);
-
-      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
+      ModCostMap mod_cost(res_graph, cost, potential);
+
+      Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);
 
 
@@ -316 +318 @@
           
           //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 +331 @@
             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 +403 @@
 
 
-    ///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 +423 @@
     ///\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;