Changeset 554:2d27cbaa982d in lemon-0.x

Timestamp:

05/06/04 17:47:42 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Method checkSolution() added.

Location:

src/work/athos

Files:

• mincostflows.h (modified) (2 diffs)
• mincostflows_test.cc (modified) (1 diff)

src/work/athos/mincostflows.h

@@ -188 +188 @@
     //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
     bool checkSolution(){
       Length mod_pot;
@@ -193 +194 @@
       FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
         //C^{\Pi}_{i,j}
-        mod_pot = length[e]-potential[G.head(e)]+potential[G.head(e)];
+        mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
         fl_e = flow[e];
+        //      std::cout << fl_e << std::endl;
         if (0<fl_e && fl_e<capacity[e]){
           if (mod_pot != 0)

src/work/athos/mincostflows_test.cc

@@ -72 +72 @@
   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
 
+  check(surb_test.checkSolution(), "Is the primal-dual solution pair really optimal?");
+
   k=1;
   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
+
+  check(surb_test.checkSolution(), "Is the primal-dual solution pair really optimal?");
   
   //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;