Changeset 322:a42dacfd0e3e in lemon-0.x for src/work

Timestamp:

04/14/04 15:30:05 (21 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

The paths are stored in vectors, assumed there is no circle of length 0

Location:

src/work/athos

Files:

• makefile (modified) (1 diff)
• minlengthpaths.h (modified) (7 diffs)

src/work/athos/makefile

@@ -7 +7 @@
 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
 #LEDAINCLUDE ?= -I$(LEDAROOT)/incl
-CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
 
 #LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo

src/work/athos/minlengthpaths.h

@@ -10 +10 @@
 #include <graph_wrapper.h>
 #include <maps.h>
+#include <vector>
+
 
 namespace hugo {
+
 
 
@@ -49 +52 @@
 
       ValueType operator[](typename ResGraphType::Edge e) const {     
-        if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
-          ///\TODO This has to be removed
-          std::cout<<"Negative length!!"<<std::endl;
-        }
+        //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
+        //  std::cout<<"Negative length!!"<<std::endl;
+        //}
         return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
       }     
@@ -65 +67 @@
     const LengthMap& length;
 
-    //auxiliry variable
+    //auxiliry variables
+
     //The value is 1 iff the edge is reversed. 
     //If the algorithm has finished, the edges of the seeked paths are 
@@ -71 +74 @@
     EdgeIntMap reversed; 
     
+    //Container to store found paths
+    std::vector< std::vector<Edge> > paths;
+
   public :
 
@@ -77 +83 @@
       length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
 
-    ///Runs the algorithm
     
     ///Runs the algorithm
@@ -93 +98 @@
 
       Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
-      
-      for (int i=0; i<k; ++i){
+
+      int i;
+      for (i=0; i<k; ++i){
         dijkstra.run(s);
         if (!dijkstra.reached(t)){
           //There are no k paths from s to t
-          return i;
+          break;
         };
         
@@ -121 +127 @@
           
       }
-      return k;
-    }
+      
+      //Let's find the paths
+      //We put the paths into vectors (just for now). In the meantime we lose 
+      //the information stored in 'reversed'
+      //We suppose the lengths to be positive now.
+      paths.clear();
+      paths.resize(k);
+      for (int j=0; j<i; ++j){
+        Node n=s;
+        OutEdgeIt e;
+
+        while (n!=t){
 
 
+          G.first(e,n);
+          
+          while (!reversed[e]){
+            G.next(e);
+          }
+          n = G.head(e);
+          paths[j].push_back(e);
+          reversed[e] = 1-reversed[e];
+        }
+        
+      }
 
+      return i;
+    }