# HG changeset patch
# User athos
# Date 1081186384 0
# Node ID 4d15193e3a5d59e6a6d678fae8e07eb834ca3061
# Parent  6720705c9095177e804f3375ff56fcfdcf8cd625
Compiles and segfaults again. Renamed from Suurballe.

diff -r 6720705c9095 -r 4d15193e3a5d src/work/athos/minlengthpaths.h
--- a/src/work/athos/minlengthpaths.h	Mon Apr 05 17:25:40 2004 +0000
+++ b/src/work/athos/minlengthpaths.h	Mon Apr 05 17:33:04 2004 +0000
@@ -1,108 +1,129 @@
 // -*- c++ -*-
-#ifndef HUGO_SUURBALLE_H
-#define HUGO_SUURBALLE_H
+#ifndef HUGO_MINLENGTHPATHS_H
+#define HUGO_MINLENGTHPATHS_H
 
 ///\file
-///\brief Suurballe algorithm.
+///\brief An algorithm for finding k paths of minimal total length.
 
 #include <iostream>
 #include <dijkstra.h>
 #include <graph_wrapper.h>
+#include <maps.h>
+
 namespace hugo {
 
 
-///\brief Implementation of Suurballe's algorithm
+///\brief Implementation of an algorithm for finding k paths between 2 nodes 
+  /// of minimal total length 
 ///
-/// The class \ref hugo::Suurballe "Suurballe" implements
-/// Suurballe's algorithm which seeks for k edge-disjoint paths
+/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
+/// an algorithm which finds k edge-disjoint paths
 /// from a given source node to a given target node in an
-/// edge-weighted directed graph having minimal total cost.
+/// edge-weighted directed graph having minimal total weigth (length).
 /// 
 /// 
 
   template <typename Graph, typename T, 
     typename LengthMap=typename Graph::EdgeMap<T> >
-  class Suurballe {
+  class MinLengthPaths {
 
 
-    //Writing maps 
-    class ConstMap {
-    public :
-      typedef int ValueType;
-      typedef typename Graph::Edge KeyType;
+//      class ConstMap {
+//      public :
+//        typedef int ValueType;
+//        typedef typename Graph::Edge KeyType;
 
-      int operator[](typename Graph::Edge e) const { 
-	return 1;
-      } 
-    };
-    /*
-    //    template <typename Graph, typename T>
-    class ModLengthMap {   
-      typedef typename Graph::EdgeMap<T> EdgeMap;
-      typedef typename Graph::NodeMap<T> NodeMap;
-
-      const EdgeMap &ol;   
-      const NodeMap &pot;     
-    public :
-      typedef typename EdgeMap::KeyType KeyType;
-      typedef typename EdgeMap::ValueType ValueType;
-
-      double operator[](typename Graph::EdgeIt e) const {     
-	return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
-      }     
-
-      ModLengthMap(const EdgeMap &o,
-		   const NodeMap &p) : 
-	ol(o), pot(p){}; 
-    };
-    */
+//        int operator[](typename Graph::Edge e) const { 
+//  	return 1;
+//        } 
+//      };
 
 
     typedef typename Graph::Node Node;
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::EdgeMap<int> EdgeIntMap;
+
+    typedef ConstMap<Edge,int> ConstMap;
+
     typedef TrivGraphWrapper<const Graph> TrivGraphType;
-    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
+    typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
       ConstMap> ResGraphType;
 
+
+    //template <typename Graph, typename T>
+    class ModLengthMap {   
+      typedef typename ResGraphType::NodeMap<T> NodeMap;
+      const ResGraphType& G;
+      const EdgeIntMap& rev; 
+      const LengthMap &ol;   
+      const NodeMap &pot;     
+    public :
+      typedef typename LengthMap::KeyType KeyType;
+      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;
+	}
+	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
+      }     
+
+      ModLengthMap(  const ResGraphType& _G, const EdgeIntMap& _rev, 
+		     const LengthMap &o,  const NodeMap &p) : 
+	G(_G), rev(_rev), ol(o), pot(p){}; 
+    };
+    
+
     const Graph& G;
     const LengthMap& length;
 
+    //auxiliary variable
+    //The value is 1 iff the edge is reversed
+    EdgeIntMap reversed; 
 
-    //auxiliary variables
-    
-    typename Graph::EdgeMap<int> reversed; 
-    typename Graph::NodeMap<T> dijkstra_dist; 
     
   public :
     
 
-    Suurballe(Graph& _G, LengthMap& _length) : G(_G), 
-      length(_length), reversed(_G), dijkstra_dist(_G){ }
+    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
+      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
 
-    ///Runs Suurballe's algorithm
+    ///Runs the algorithm
     
-    ///Runs Suurballe's algorithm
-    ///Returns true iff there are k edge-disjoint paths from s to t
-    bool run(Node s, Node t, int k) {
+    ///Runs the algorithm
+    ///Returns k if there are at least k edge-disjoint paths from s to t.
+    ///Otherwise it returns the number of edge-disjoint paths from s to t.
+    int run(Node s, Node t, int k) {
+      ConstMap const1map(1);
 
-      LengthMap mod_length_c = length;
-      ConstMap const1map;
-      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
-      TrivGraphType ize(G);
-      ResGraphType res_graph(ize, reversed, const1map);
-      //ModLengthMap modified_length(length, dijkstra_dist);
-      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
-      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
-      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
+      ResGraphType res_graph(G, reversed, const1map);
+
+      //Initialize the copy of the Dijkstra potential to zero
+      typename ResGraphType::NodeMap<T> dijkstra_dist(G);
+      ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
+
+      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
       
       for (int i=0; i<k; ++i){
 	dijkstra.run(s);
 	if (!dijkstra.reached(t)){
 	  //There is no k path from s to t
-	  return false;
+	  return ++i;
 	};
+	
+	{
+	  //We have to copy the potential
+	  typename ResGraphType::NodeIt n;
+	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
+	      dijkstra_dist[n] += dijkstra.distMap()[n];
+	  }
+	}
+
+
+	/*
 	{
 	  //We have to copy the potential
 	  typename ResGraphType::EdgeIt e;
@@ -113,7 +134,8 @@
 	      dijkstra.distMap()[res_graph.tail(e)];
 	  }
 	}
-	
+	*/
+
 	//Reversing the sortest path
 	Node n=t;
 	Edge e;
@@ -125,18 +147,18 @@
 
 	  
       }
-      return true;
+      return k;
     }
            
       
 
 
 
-  };//class Suurballe
+  };//class MinLengthPaths
 
 
 
 
 } //namespace hugo
 
-#endif //HUGO_SUURBALLE_H
+#endif //HUGO_MINLENGTHPATHS_H
diff -r 6720705c9095 -r 4d15193e3a5d src/work/athos/suurballe.cc
--- a/src/work/athos/suurballe.cc	Mon Apr 05 17:25:40 2004 +0000
+++ b/src/work/athos/suurballe.cc	Mon Apr 05 17:33:04 2004 +0000
@@ -4,7 +4,7 @@
 //#include <string>
 
 #include <list_graph.h>
-#include <suurballe.h>
+#include <minlengthpaths.h>
 
 using namespace hugo;
 
@@ -119,7 +119,7 @@
 
   
   int k=3;
-  Suurballe<ListGraph, int> surb_test(graph, length);
+  MinLengthPaths<ListGraph, int> surb_test(graph, length);
   std::cout << surb_test.run(s,t,k)<<std::endl;
 
   return 0;