Changeset 310:76c005b15354 in lemon-0.x for src/work/klao

Timestamp:

04/05/04 20:24:37 (21 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

Converted the "minlengthpaths" alg. to the new style graph_wrappers.

Location:

src/work/klao

Files:

• Makefile (modified) (1 diff)
• minlengthpaths.cc (modified) (1 diff)
• minlengthpaths.h (modified) (8 diffs)

src/work/klao/Makefile

@@ -1 @@
-BINARIES = path_test map_test
+BINARIES = path_test map_test minlengthpaths
 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos}
 include ../makefile

src/work/klao/minlengthpaths.cc

@@ -120 +120 @@
   
   int k=3;
-  MinLengthPaths<ListGraph, int> surb_test(graph, length);
-  std::cout << surb_test.run(s,t,k)<<std::endl;
+  MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
+    surb_test(graph, length);
+  std::cout << surb_test.run(s,t,k) << std::endl;
 
   return 0;

src/work/klao/minlengthpaths.h

@@ -14 +14 @@
 
 
-///\brief Implementation of an algorithm for finding k paths between 2 nodes 
+  ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
   /// of minimal total length 
-///
-/// 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 weigth (length).
-/// 
-/// 
+  ///
+  /// 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 weigth (length).
 
-  template <typename Graph, typename T, 
-    typename LengthMap=typename Graph::EdgeMap<T> >
+  template <typename Graph, typename LengthMap>
   class MinLengthPaths {
 
-
-//      class ConstMap {
-//      public :
-//        typedef int ValueType;
-//        typedef typename Graph::Edge KeyType;
-
-//        int operator[](typename Graph::Edge e) const { 
-//      return 1;
-//        } 
-//      };
-
+    typedef typename LengthMap::ValueType Length;
 
     typedef typename Graph::Node Node;
@@ -48 +35 @@
     typedef ConstMap<Edge,int> ConstMap;
 
-    typedef TrivGraphWrapper<const Graph> TrivGraphType;
-    typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
-      ConstMap> ResGraphType;
+    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
 
 
-    //template <typename Graph, typename T>
     class ModLengthMap {   
-      typedef typename ResGraphType::NodeMap<T> NodeMap;
+      typedef typename ResGraphType::NodeMap<Length> NodeMap;
       const ResGraphType& G;
-      const EdgeIntMap& rev; 
-      const LengthMap &ol;   
-      const NodeMap &pot;     
+      const EdgeIntMap& rev;
+      const LengthMap &ol;
+      const NodeMap &pot;
     public :
       typedef typename LengthMap::KeyType KeyType;
@@ -72 +56 @@
       }     
 
-      ModLengthMap(  const ResGraphType& _G, const EdgeIntMap& _rev, 
-                     const LengthMap &o,  const NodeMap &p) : 
+      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
+                   const LengthMap &o,  const NodeMap &p) : 
         G(_G), rev(_rev), ol(o), pot(p){}; 
     };
@@ -87 +71 @@
     
   public :
-    
+
 
     MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
@@ -103 +87 @@
 
       //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);
+      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
+      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
 
       Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
@@ -112 +96 @@
         if (!dijkstra.reached(t)){
           //There is no k path from s to t
-          return ++i;
+          /// \TODO mit keresett itt ez a ++?
+          return i;
         };
         
@@ -123 +108 @@
         }
 
-
-        /*
-        {
-          //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
@@ -150 +122 @@
       return k;
     }
-           
-      
 
 
 
-  };//class MinLengthPaths
 
 
+  }; //class MinLengthPaths