Changeset 306:4d15193e3a5d in lemon-0.x

Timestamp:

04/05/04 19:33:04 (21 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Compiles and segfaults again. Renamed from Suurballe.

Location:

src/work/athos

Files:

• minlengthpaths.h (modified) (8 diffs)
• suurballe.cc (modified) (2 diffs)

src/work/athos/minlengthpaths.h

@@ -1 +1 @@
 // -*- 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).
 /// 
 /// 
@@ -23 +26 @@
   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;
+//        } 
+//      };
 
 
@@ -63 +44 @@
     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){
@@ -102 +112 @@
         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
@@ -114 +135 @@
           }
         }
-        
+        */
+
         //Reversing the sortest path
         Node n=t;
@@ -126 +148 @@
           
       }
-      return true;
+      return k;
     }
            
@@ -133 +155 @@
 
 
-  };//class Suurballe
+  };//class MinLengthPaths
 
 
@@ -140 +162 @@
 } //namespace hugo
 
-#endif //HUGO_SUURBALLE_H
+#endif //HUGO_MINLENGTHPATHS_H

src/work/athos/suurballe.cc

@@ -5 +5 @@
 
 #include <list_graph.h>
-#include <suurballe.h>
+#include <minlengthpaths.h>
 
 using namespace hugo;
@@ -120 +120 @@
   
   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;