# HG changeset patch
# User athos
# Date 1081177001 0
# Node ID 60b578e3d5076941f56b64b2de02d5c92626db5d
# Parent  54e8905344ba28a4ba9e2a07caf58ee5f4e2fe4a
Renaming Suurballe to minlengthpaths

diff -r 54e8905344ba -r 60b578e3d507 src/work/athos/suurballe.h
--- a/src/work/athos/suurballe.h	Mon Apr 05 14:56:32 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,142 +0,0 @@
-// -*- 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