Changeset 511:325c9430723e in lemon-0.x for src/work/athos/minlengthpaths.h

Timestamp:

05/03/04 12:27:20 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

getPath() function implemented.

File:

• src/work/athos/minlengthpaths.h (modified) (10 diffs)

src/work/athos/minlengthpaths.h

@@ -11 +11 @@
 #include <graph_wrapper.h>
 #include <maps.h>
-#include <vector>
+#include <vector.h>
 
 
@@ -32 +32 @@
 
     typedef typename LengthMap::ValueType Length;
-
+    
     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 typename Graph::template EdgeMap<int> EdgeIntMap;
 
     typedef ConstMap<Edge,int> ConstMap;
@@ -43 +43 @@
     typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
 
-
     class ModLengthMap {   
-      typedef typename ResGraphType::NodeMap<Length> NodeMap;
+      typedef typename ResGraphType::template NodeMap<Length> NodeMap;
       const ResGraphType& G;
       const EdgeIntMap& rev;
@@ -53 +52 @@
       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 ){
@@ -60 +59 @@
         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){}; 
-    };
+    };//ModLengthMap
+
+
     
 
@@ -79 +80 @@
     //Container to store found paths
     std::vector< std::vector<Edge> > paths;
+    //typedef DirPath<Graph> DPath;
+    //DPath paths;
+
+
+    Length total_length;
 
   public :
@@ -95 +101 @@
       ConstMap const1map(1);
 
+
       //We need a residual graph, in which some of the edges are reversed
       ResGraphType res_graph(G, const1map, reversed);
 
       //Initialize the copy of the Dijkstra potential to zero
-      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
+      typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
       ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
 
@@ -134 +141 @@
       
       //Let's find the paths
-      //We put the paths into vectors (just for now). In the meantime we lose 
-      //the information stored in 'reversed'
+      //We put the paths into stl vectors (as an inner representation). 
+      //In the meantime we lose the information stored in 'reversed'.
       //We suppose the lengths to be positive now.
+
+      //Meanwhile we put the total length of the found paths 
+      //in the member variable total_length
       paths.clear();
+      total_length=0;
       paths.resize(k);
       for (int j=0; j<i; ++j){
@@ -153 +164 @@
           n = G.head(e);
           paths[j].push_back(e);
+          total_length += length[e];
           reversed[e] = 1-reversed[e];
         }
@@ -161 +173 @@
     }
 
+    ///This function gives back the total length of the found paths.
+    ///Assumes that \c run() has been run and nothing changed since then.
+    Length totalLength(){
+      return total_length;
+    }
+
+    ///This function gives back the \c j-th path in argument p.
+    ///Assumes that \c run() has been run and nothing changed since then.
+    /// \warning It is assumed that \c p is constructed to be a path of graph \c G.
+    template<typename DirPath>
+    void getPath(DirPath& p, int j){
+      p.clear();
+      typename DirPath::Builder B(p);
+      for(typename std::vector<Edge>::iterator i=paths[j].begin(); 
+          i!=paths[j].end(); ++i ){
+        B.pushBack(*j);
+      }
+
+      B.commit();
+    }
 
   }; //class MinLengthPaths