Changeset 551:d167149bde95 in lemon-0.x for src/work

Timestamp:

05/06/04 17:19:59 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Written hugo/ into includes.

Location:

src/work

Files:

• athos/makefile (modified) (1 diff)
• athos/mincostflows.h (modified) (3 diffs)
• athos/mincostflows_test.cc (modified) (1 diff)
• list_graph.h (modified) (1 diff)
• marci/graph_wrapper.h (modified) (1 diff)

src/work/athos/makefile

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

src/work/athos/mincostflows.h

@@ -8 +8 @@
 
 #include <iostream>
-#include <dijkstra.h>
+#include <hugo/dijkstra.h>
 #include <graph_wrapper.h>
-#include <maps.h>
-#include <vector.h>
+#include <hugo/maps.h>
+#include <vector>
 #include <for_each_macros.h>
 
@@ -86 +86 @@
     //auxiliary variables
 
-    //The value is 1 iff the edge is reversed. 
-    //If the algorithm has finished, the edges of the seeked paths are 
-    //exactly those that are reversed 
+    //To store the flow
     EdgeIntMap flow; 
+    //To store the potentila (dual variables)
     typename Graph::template NodeMap<Length> potential;
     
     //Container to store found paths
-    std::vector< std::vector<Edge> > paths;
+    //std::vector< std::vector<Edge> > paths;
     //typedef DirPath<Graph> DPath;
     //DPath paths;
@@ -187 +186 @@
     }
 
+    //This function checks, whether the given solution is optimal
+    //Running after a \c run() should return with true
+    bool checkSolution(){
+      Length mod_pot;
+      Length fl_e;
+      FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
+        //C^{\Pi}_{i,j}
+        mod_pot = length[e]-potential[G.head(e)]+potential[G.head(e)];
+        fl_e = flow[e];
+        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;
+        }
+      }
+      return true;
+    }
+    
     /*
       ///\todo To be implemented later

src/work/athos/mincostflows_test.cc

@@ -3 +3 @@
 #include <mincostflows.h>
 //#include <path.h>
-#include <maps.h>
+//#include <maps.h>
 
 using namespace std;

src/work/list_graph.h

@@ -6 +6 @@
 #include <vector>
 
-#include <invalid.h>
+#include <hugo/invalid.h>
 
 namespace hugo {

src/work/marci/graph_wrapper.h

@@ -11 +11 @@
 ///\author Marton Makai
 
-#include <invalid.h>
+#include <hugo/invalid.h>
 //#include <iter_map.h>