Changeset 672:6c7bd0edd1d7 in lemon-0.x

Timestamp:

06/02/04 11:45:50 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Seems to work. More tests required.

Location:

src/work

Files:

• athos/min_cost_flow.cc (modified) (4 diffs)
• athos/mincostflow.h (modified) (9 diffs)
• makefile (modified) (1 diff)

src/work/athos/min_cost_flow.cc

@@ -12 +12 @@
 
 bool passed = true;
-/*
+
 void check(bool rc, char *msg="") {
   passed = passed && rc;
@@ -21 +21 @@
   }
 }
-*/
+
 
 
@@ -91 +91 @@
   min_cost_flow_test.run();
   //int k=1;
+  check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?");
 
   /*
@@ -110 +111 @@
   check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
-
+  */
   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
        << endl;
 
   return passed ? 0 : 1;
-  */
+  
 }

src/work/athos/mincostflow.h

@@ -100 +100 @@
     typedef typename Graph::template NodeMap<Cost> PotentialMap;
     PotentialMap potential;
-    //To store excess-deficit values
-    SupplyDemandMap excess_deficit;
     
 
@@ -115 +113 @@
      supply_demand(_supply_demand), 
      flow(_graph), 
-     potential(_graph),
-     excess_deficit(_graph){ }
+     potential(_graph){ }
 
     
@@ -127 +124 @@
     void run() {
 
+      //To store excess-deficit values
+      SupplyDemandMap excess_deficit(graph);
+
       //Resetting variables from previous runs
       //total_cost = 0;
+
 
       typedef typename Graph::template NodeMap<int> HeapMap;
@@ -197 +198 @@
       //Let's construct the sugraph consisting only of the abundant edges
       typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
+
       ConstNodeMap const_true_map(true);
       typedef SubGraphWrapper< const Graph, ConstNodeMap, 
@@ -321 +323 @@
 
         Node s = excess_nodes.top(); 
-        SupplyDemand max_excess = excess_nodes[s];
+        max_excess = excess_nodes[s];
         Node t = deficit_nodes.top(); 
         if (max_excess < deficit_nodes[t]){
@@ -371 +373 @@
 
           //Update the excess_nodes heap
-          if (delta >= excess_nodes[s]){
+          if (delta > excess_nodes[s]){
             if (delta > excess_nodes[s])
               deficit_nodes.push(s,delta - excess_nodes[s]);
@@ -381 +383 @@
           }
           //Update the deficit_nodes heap
-          if (delta >= deficit_nodes[t]){
+          if (delta > deficit_nodes[t]){
             if (delta > deficit_nodes[t])
               excess_nodes.push(t,delta - deficit_nodes[t]);
@@ -445 +447 @@
     ///This function checks, whether the given solution is optimal
     ///Running after a \c run() should return with true
-    ///In this "state of the art" this only check optimality, doesn't bother with feasibility
+    ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
     ///
     ///\todo Is this OK here?
@@ -456 +458 @@
         fl_e = flow[e];
         //      std::cout << fl_e << std::endl;
-        if (0<fl_e && fl_e<capacity[e]){
-          if (mod_pot != 0)
-            return false;
-        }
-        else{
-          if (mod_pot > 0 && fl_e != 0)
-            return false;
-          if (mod_pot < 0 && fl_e != capacity[e])
-            return false;
-        }
+        if (mod_pot > 0 && fl_e != 0)
+          return false;
+
       }
       return true;
     }
-    
+
+    /*
+    //For testing purposes only
+    //Lists the node_properties
+    void write_property_vector(const SupplyDemandMap& a,
+                               char* prop_name="property"){
+      FOR_EACH_LOC(typename Graph::NodeIt, i, graph){
+        cout<<"Node id.: "<<graph.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
+      }
+      cout<<endl;
+    }
+    */
+    bool checkFeasibility(){
+      SupplyDemandMap supdem(graph);
+      FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
+
+        if ( flow[e] < 0){
+
+          return false;
+        }
+        supdem[graph.tail(e)] += flow[e];
+        supdem[graph.head(e)] -= flow[e];
+      }
+      //write_property_vector(supdem, "supdem");
+      //write_property_vector(supply_demand, "supply_demand");
+
+      FOR_EACH_LOC(typename Graph::NodeIt, n, graph){
+
+        if ( supdem[n] != supply_demand[n]){
+          //cout<<"Node id.: "<<graph.id(n)<<" : "<<supdem[n]<<", should be: "<<supply_demand[n]<<endl;
+          return false;
+        }
+      }
+
+      return true;
+    }
+
+    bool checkOptimality(){
+      return checkFeasibility() && checkComplementarySlackness();
+    }
 
   }; //class MinCostFlow

src/work/makefile

@@ -1 +1 @@
 INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
-CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
 
 BINARIES ?= bin_heap_demo