# HG changeset patch
# User athos
# Date 1081176992 0
# Node ID 54e8905344ba28a4ba9e2a07caf58ee5f4e2fe4a
# Parent  315d826faa8f39177810a7bcd199a5d5b33c2c99
Renaming Suurballe to minlengthpaths

diff -r 315d826faa8f -r 54e8905344ba src/work/athos/minlengthpaths.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/minlengthpaths.h	Mon Apr 05 14:56:32 2004 +0000
@@ -0,0 +1,142 @@
+// -*- c++ -*-
+#ifndef HUGO_SUURBALLE_H
+#define HUGO_SUURBALLE_H
+
+///\file
+///\brief Suurballe algorithm.
+
+#include <iostream>
+#include <dijkstra.h>
+#include <graph_wrapper.h>
+namespace hugo {
+
+
+///\brief Implementation of Suurballe's algorithm
+///
+/// The class \ref hugo::Suurballe "Suurballe" implements
+/// Suurballe's algorithm which seeks for k edge-disjoint paths
+/// from a given source node to a given target node in an
+/// edge-weighted directed graph having minimal total cost.
+/// 
+/// 
+
+  template <typename Graph, typename T, 
+    typename LengthMap=typename Graph::EdgeMap<T> >
+  class Suurballe {
+
+
+    //Writing maps 
+    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){}; 
+    };
+    */
+
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef TrivGraphWrapper<const Graph> TrivGraphType;
+    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
+      ConstMap> ResGraphType;
+
+    const Graph& G;
+    const LengthMap& length;
+
+
+    //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){ }
+
+    ///Runs Suurballe's 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) {
+
+      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);
+      
+      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;
+	};
+	{
+	  //We have to copy the potential
+	  typename ResGraphType::EdgeIt e;
+	  for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
+	    //dijkstra_dist[e] = dijkstra.distMap()[e];
+	    mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - 
+	      dijkstra.distMap()[res_graph.head(e)] +  
+	      dijkstra.distMap()[res_graph.tail(e)];
+	  }
+	}
+	
+	//Reversing the sortest path
+	Node n=t;
+	Edge e;
+	while (n!=s){
+	  e = dijkstra.pred(n);
+	  n = dijkstra.predNode(n);
+	  reversed[e] = 1-reversed[e];
+	}
+
+	  
+      }
+      return true;
+    }
+           
+      
+
+
+
+  };//class Suurballe
+
+
+
+
+} //namespace hugo
+
+#endif //HUGO_SUURBALLE_H