# HG changeset patch
# User athos
# Date 1081949405 0
# Node ID a42dacfd0e3e885f75b000b6b2ecaea256de01e8
# Parent  048b965204b54e17896a0ff8132fed08fef3ed12
The paths are stored in vectors, assumed there is no circle of length 0

diff -r 048b965204b5 -r a42dacfd0e3e src/work/athos/makefile
--- a/src/work/athos/makefile	Wed Apr 14 12:24:55 2004 +0000
+++ b/src/work/athos/makefile	Wed Apr 14 13:30:05 2004 +0000
@@ -6,7 +6,7 @@
 #BOOSTROOT ?= /home/marci/boost
 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
 BINARIES = suurballe
diff -r 048b965204b5 -r a42dacfd0e3e src/work/athos/minlengthpaths.h
--- a/src/work/athos/minlengthpaths.h	Wed Apr 14 12:24:55 2004 +0000
+++ b/src/work/athos/minlengthpaths.h	Wed Apr 14 13:30:05 2004 +0000
@@ -9,10 +9,13 @@
 #include <dijkstra.h>
 #include <graph_wrapper.h>
 #include <maps.h>
+#include <vector>
+
 
 namespace hugo {
 
 
+
   ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
   /// of minimal total length 
   ///
@@ -48,10 +51,9 @@
       typedef typename LengthMap::ValueType ValueType;
 
       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)]);   
       }     
 
@@ -64,19 +66,22 @@
     const Graph& G;
     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 
     //exactly those that are reversed 
     EdgeIntMap reversed; 
     
+    //Container to store found paths
+    std::vector< std::vector<Edge> > paths;
+
   public :
 
 
     MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
       length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
 
-    ///Runs the algorithm
     
     ///Runs the algorithm
     ///Returns k if there are at least k edge-disjoint paths from s to t.
@@ -92,12 +97,13 @@
       ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
 
       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;
 	};
 	
 	{
@@ -120,13 +126,36 @@
 
 	  
       }
-      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;
     }
 
 
-
-
-
   }; //class MinLengthPaths