# HG changeset patch
# User deba
# Date 1168252799 0
# Node ID 27aa03cd3121970af5c1766491e3ccf1341e4865
# Parent  c1e936e6a46b7a0aebef4245fc44342f8daaa203
New path concept and path structures

TODO: BellmanFord::negativeCycle()

diff -r c1e936e6a46b -r 27aa03cd3121 lemon/Makefile.am
--- a/lemon/Makefile.am	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/Makefile.am	Mon Jan 08 10:39:59 2007 +0000
@@ -86,6 +86,7 @@
 	lemon/mip_cplex.h \
 	lemon/nagamochi_ibaraki.h \
 	lemon/path.h \
+	lemon/path_utils.h \
 	lemon/polynomial.h \
 	lemon/preflow.h \
 	lemon/prim.h \
@@ -121,6 +122,7 @@
 	lemon/bits/item_writer.h \
 	lemon/bits/map_extender.h \
 	lemon/bits/mingw32_time.h \
+	lemon/bits/path_dump.h \
 	lemon/bits/traits.h \
 	lemon/bits/utility.h \
 	lemon/bits/variant.h \
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/bellman_ford.h
--- a/lemon/bellman_ford.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/bellman_ford.h	Mon Jan 08 10:39:59 2007 +0000
@@ -25,6 +25,7 @@
 ///
 
 #include <lemon/list_graph.h>
+#include <lemon/bits/path_dump.h>
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
@@ -427,7 +428,7 @@
     /// calculates the at most \f$ k \f$ length path lengths.
     ///
     /// \warning The paths with limited edge number cannot be retrieved
-    /// easily with \ref getPath() or \ref predEdge() functions. If you
+    /// easily with \ref path() or \ref predEdge() functions. If you
     /// need the shortest path and not just the distance you should store
     /// after each iteration the \ref predEdgeMap() map and manually build
     /// the path.
@@ -540,7 +541,7 @@
     /// most \c num edge.
     ///
     /// \warning The paths with limited edge number cannot be retrieved
-    /// easily with \ref getPath() or \ref predEdge() functions. If you
+    /// easily with \ref path() or \ref predEdge() functions. If you
     /// need the shortest path and not just the distance you should store
     /// after each iteration the \ref predEdgeMap() map and manually build
     /// the path.
@@ -658,70 +659,56 @@
       int _index;
     };
 
-    /// \brief Copies the shortest path to \c t into \c p
+    typedef PredMapPath<Graph, PredMap> Path;
+
+    /// \brief Gives back the shortest path.
     ///    
-    /// This function copies the shortest path to \c t into \c p.
-    /// If it \c t is a source itself or unreachable, then it does not
-    /// alter \c p.
-    ///
-    /// \return Returns \c true if a path to \c t was actually copied to \c p,
-    /// \c false otherwise.
-    /// \sa DirPath
-    template <typename Path>
-    bool getPath(Path &p, Node t) {
-      if(reached(t)) {
-	p.clear();
-	typename Path::Builder b(p);
-	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
-	  b.pushFront(predEdge(t));
-	b.commit();
-	return true;
-      }
-      return false;
+    /// Gives back the shortest path.
+    /// \pre The \c t should be reachable from the source.
+    Path path(Node t) 
+    {
+      return Path(*graph, *_pred, t);
     }
 
-    /// \brief Copies a negative cycle into path \c p.
-    ///    
-    /// This function copies a negative cycle into path \c p.
-    /// If the algorithm have not found yet negative cycle it will not change
-    /// the given path and gives back false.
-    ///
-    /// \return Returns \c true if a cycle was actually copied to \c p,
-    /// \c false otherwise.
-    /// \sa DirPath
-    template <typename Path>
-    bool getNegativeCycle(Path& p) {
-      typename Graph::template NodeMap<int> state(*graph, 0);
-      for (ActiveIt it(*this); it != INVALID; ++it) {
-        if (state[it] == 0) {
-          for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
-            if (state[t] == 0) {
-              state[t] = 1;
-            } else if (state[t] == 2) {
-              break;
-            } else {
-              p.clear();
-              typename Path::Builder b(p);
-              b.setStartNode(t);
-              b.pushFront(predEdge(t));
-              for(Node s = predNode(t); s != t; s = predNode(s)) {
-                b.pushFront(predEdge(s));
-              }
-              b.commit();
-              return true;
-            }
-          }
-          for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
-            if (state[t] == 1) {
-              state[t] = 2;
-            } else {
-              break;
-            }
-          }
-        }
-      }
-      return false;
-    }
+
+    // TODO : implement negative cycle
+//     /// \brief Gives back a negative cycle.
+//     ///    
+//     /// This function gives back a negative cycle.
+//     /// If the algorithm have not found yet negative cycle it will give back
+//     /// an empty path.
+//     Path negativeCycle() {
+//       typename Graph::template NodeMap<int> state(*graph, 0);
+//       for (ActiveIt it(*this); it != INVALID; ++it) {
+//         if (state[it] == 0) {
+//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
+//             if (state[t] == 0) {
+//               state[t] = 1;
+//             } else if (state[t] == 2) {
+//               break;
+//             } else {
+//               p.clear();
+//               typename Path::Builder b(p);
+//               b.setStartNode(t);
+//               b.pushFront(predEdge(t));
+//               for(Node s = predNode(t); s != t; s = predNode(s)) {
+//                 b.pushFront(predEdge(s));
+//               }
+//               b.commit();
+//               return true;
+//             }
+//           }
+//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
+//             if (state[t] == 1) {
+//               state[t] = 2;
+//             } else {
+//               break;
+//             }
+//           }
+//         }
+//       }
+//       return false;
+//     }
 	  
     /// \brief The distance of a node from the root.
     ///
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/bfs.h
--- a/lemon/bfs.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/bfs.h	Mon Jan 08 10:39:59 2007 +0000
@@ -25,6 +25,7 @@
 
 #include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
+#include <lemon/bits/path_dump.h>
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
@@ -676,26 +677,15 @@
     
     ///@{
 
-    ///Copies the shortest path to \c t into \c p
+    typedef PredMapPath<Graph, PredMap> Path;
+
+    ///Gives back the shortest path.
     
-    ///This function copies the shortest path to \c t into \c p.
-    ///If \c t is a source itself or unreachable, then it does not
-    ///alter \c p.
-    ///\return Returns \c true if a path to \c t was actually copied to \c p,
-    ///\c false otherwise.
-    ///\sa DirPath
-    template<class P>
-    bool getPath(P &p,Node t) 
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t) 
     {
-      if(reached(t)) {
-	p.clear();
-	typename P::Builder b(p);
-	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
-	  b.pushFront(predEdge(t));
-	b.commit();
-	return true;
-      }
-      return false;
+      return Path(*G, *_pred, t);
     }
 
     ///The distance of a node from the root(s).
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/bits/path_dump.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bits/path_dump.h	Mon Jan 08 10:39:59 2007 +0000
@@ -0,0 +1,169 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BITS_PRED_MAP_PATH_H
+#define LEMON_BITS_PRED_MAP_PATH_H
+
+namespace lemon {
+
+  template <typename _Graph, typename _PredMap>
+  class PredMapPath {
+  public:
+    typedef True RevPathTag;
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+    typedef _PredMap PredMap;
+
+    PredMapPath(const Graph& _graph, const PredMap& _predMap,
+                typename Graph::Node _target)
+      : graph(_graph), predMap(_predMap), target(_target) {}
+
+    int length() const {
+      int len = 0;
+      typename Graph::Node node = target;
+      typename Graph::Edge edge;
+      while ((edge = predMap[node]) != INVALID) {
+        node = graph.source(edge);
+        ++len;
+      }
+      return len;
+    }
+
+    bool empty() const {
+      return predMap[target] != INVALID;
+    }
+
+    class RevIt {
+    public:
+      RevIt() {}
+      RevIt(Invalid) : path(0), current(INVALID) {}
+      RevIt(const PredMapPath& _path) 
+        : path(&_path), current(_path.target) {}
+
+      operator const typename Graph::Edge() const {
+        return path->predMap[current];
+      }
+
+      RevIt& operator++() {
+        current = path->graph.source(path->predMap[current]);
+        if (path->predMap[current] == INVALID) current = INVALID;
+        return *this;
+      }
+
+      bool operator==(const RevIt& e) const { 
+        return current == e.current; 
+      }
+
+      bool operator!=(const RevIt& e) const {
+        return current != e.current; 
+      }
+
+      bool operator<(const RevIt& e) const { 
+        return current < e.current; 
+      }
+      
+    private:
+      const PredMapPath* path;
+      typename Graph::Node current;
+    };
+
+  private:
+    const Graph& graph;
+    const PredMap& predMap;
+    typename Graph::Node target;
+  };
+
+
+  template <typename _Graph, typename _PredMatrixMap>
+  class PredMatrixMapPath {
+  public:
+    typedef True RevPathTag;
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+    typedef _PredMatrixMap PredMatrixMap;
+
+    PredMatrixMapPath(const Graph& _graph, 
+                      const PredMatrixMap& _predMatrixMap,
+                      typename Graph::Node _source, 
+                      typename Graph::Node _target)
+      : graph(_graph), predMatrixMap(_predMatrixMap), 
+        source(_source), target(_target) {}
+
+    int length() const {
+      int len = 0;
+      typename Graph::Node node = target;
+      typename Graph::Edge edge;
+      while ((edge = predMatrixMap(source, node)) != INVALID) {
+        node = graph.source(edge);
+        ++len;
+      }
+      return len;
+    }
+
+    bool empty() const {
+      return source != target;
+    }
+
+    class RevIt {
+    public:
+      RevIt() {}
+      RevIt(Invalid) : path(0), current(INVALID) {}
+      RevIt(const PredMatrixMapPath& _path) 
+        : path(&_path), current(_path.target) {}
+
+      operator const typename Graph::Edge() const {
+        return path->predMatrixMap(path->source, current);
+      }
+
+      RevIt& operator++() {
+        current = 
+          path->graph.source(path->predMatrixMap(path->source, current));
+        if (path->predMatrixMap(path->source, current) == INVALID) 
+          current = INVALID;
+        return *this;
+      }
+
+      bool operator==(const RevIt& e) const { 
+        return current == e.current; 
+      }
+
+      bool operator!=(const RevIt& e) const {
+        return current != e.current; 
+      }
+
+      bool operator<(const RevIt& e) const { 
+        return current < e.current; 
+      }
+      
+    private:
+      const PredMatrixMapPath* path;
+      typename Graph::Node current;
+    };
+
+  private:
+    const Graph& graph;
+    const PredMatrixMap& predMatrixMap;
+    typename Graph::Node source;
+    typename Graph::Node target;
+  };
+
+}
+
+#endif
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/concepts/path.h
--- a/lemon/concepts/path.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/concepts/path.h	Mon Jan 08 10:39:59 2007 +0000
@@ -26,23 +26,28 @@
 #define LEMON_CONCEPT_PATH_H
 
 #include <lemon/bits/invalid.h>
+#include <lemon/bits/utility.h>
 #include <lemon/concept_check.h>
 
 namespace lemon {
   namespace concepts {
+
     /// \addtogroup concept
     /// @{
 
-
-    //! \brief A skeleton structure for representing directed paths in a graph.
-    //!
-    //! A skeleton structure for representing directed paths in a graph.
-    //! \param _Graph The graph type in which the path is.
-    //!
-    //! In a sense, the path can be treated as a graph, for it has \c NodeIt
-    //! and \c EdgeIt with the same usage. These types converts to the \c Node
-    //! and \c Edge of the original graph.
-    template<typename _Graph>
+    /// \brief A skeleton structure for representing directed paths in
+    /// a graph.
+    ///
+    /// A skeleton structure for representing directed paths in a
+    /// graph.  
+    /// \param _Graph The graph type in which the path is.
+    ///
+    /// In a sense, the path can be treated as a list of edges. The
+    /// lemon path type stores just this list. As a consequence it
+    /// cannot enumerate the nodes in the path and the zero length
+    /// paths cannot store the source.
+    ///
+    template <typename _Graph>
     class Path {
     public:
 
@@ -50,20 +55,22 @@
       typedef _Graph Graph;
       /// Edge type of the underlying graph.
       typedef typename Graph::Edge Edge;
-      /// Node type of the underlying graph.
-      typedef typename Graph::Node Node;
 
-      class NodeIt;
       class EdgeIt;
 
-      /// \param _g The graph in which the path is.
-      ///
-      Path(const Graph &_g) {
-	ignore_unused_variable_warning(_g);
-      }
+      /// \brief Default constructor
+      Path() {}
+
+      /// \brief Template constructor
+      template <typename CPath>
+      Path(const CPath& cpath) {}
+
+      /// \brief Template assigment
+      template <typename CPath>
+      Path& operator=(const CPath& cpath) {}
 
       /// Length of the path ie. the number of edges in the path.
-      int length() const {return 0;}
+      int length() const { return 0;}
 
       /// Returns whether the path is empty.
       bool empty() const { return true;}
@@ -71,71 +78,19 @@
       /// Resets the path to an empty path.
       void clear() {}
 
-      /// \brief Starting point of the path.
+      /// \brief Lemon style iterator for path edges
       ///
-      /// Starting point of the path.
-      /// Returns INVALID if the path is empty.
-      Node target() const {return INVALID;}
-      /// \brief End point of the path.
-      ///
-      /// End point of the path.
-      /// Returns INVALID if the path is empty.
-      Node source() const {return INVALID;}
-
-      /// \brief The target of an edge.
-      ///
-      /// Returns node iterator pointing to the target node of the
-      /// given edge iterator.
-      NodeIt target(const EdgeIt&) const {return INVALID;}
-
-      /// \brief The source of an edge.
-      ///
-      /// Returns node iterator pointing to the source node of the
-      /// given edge iterator.
-      NodeIt source(const EdgeIt&) const {return INVALID;}
-
-      /// \brief Iterator class to iterate on the nodes of the paths
-      ///
-      /// This class is used to iterate on the nodes of the paths
-      ///
-      /// Of course it converts to Graph::Node.
-      class NodeIt {
-      public:
-	/// Default constructor
-	NodeIt() {}
-	/// Invalid constructor
-	NodeIt(Invalid) {}
-	/// Constructor with starting point
-	NodeIt(const Path &) {}
-
-	///Conversion to Graph::Node
-	operator Node() const { return INVALID; }
-	/// Next node
-	NodeIt& operator++() {return *this;}
-
-	/// Comparison operator
-	bool operator==(const NodeIt&) const {return true;}
-	/// Comparison operator
-	bool operator!=(const NodeIt&) const {return true;}
- 	/// Comparison operator
- 	bool operator<(const NodeIt&) const {return false;}
-
-      };
-
-      /// \brief Iterator class to iterate on the edges of the paths
-      ///
-      /// This class is used to iterate on the edges of the paths
-      ///
-      /// Of course it converts to Graph::Edge
+      /// This class is used to iterate on the edges of the paths.
       class EdgeIt {
       public:
 	/// Default constructor
 	EdgeIt() {}
 	/// Invalid constructor
 	EdgeIt(Invalid) {}
-	/// Constructor with starting point
+	/// Constructor for first edge
 	EdgeIt(const Path &) {}
 
+        /// Conversion to Edge
 	operator Edge() const { return INVALID; }
 
 	/// Next edge
@@ -150,143 +105,205 @@
 
       };
 
+      template <typename _Path>
+      struct Constraints {
+        void constraints() {
+          Path<Graph> pc;
+          _Path p, pp(pc);
+          int l = p.length();
+          int e = p.empty();
+          p.clear();
 
-      friend class Builder;
+          p = pc;
 
-      /// \brief Class to build paths
+          typename _Path::EdgeIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename Graph::Edge ed = i;
+
+          e = (i == ii);
+          e = (i != ii);
+          e = (i < ii);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(pp);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ii);
+          ignore_unused_variable_warning(ed);
+        }
+      };
+
+    };
+
+    namespace _path_bits {
+      
+      template <typename _Graph, typename _Path, typename RevPathTag = void>
+      struct PathDumperConstraints {
+        void constraints() {
+          int l = p.length();
+          int e = p.empty();
+
+          typename _Path::EdgeIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename _Graph::Edge ed = i;
+
+          e = (i == ii);
+          e = (i != ii);
+          e = (i < ii);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ii);
+          ignore_unused_variable_warning(ed);
+        }
+        _Path& p;
+      };
+
+      template <typename _Graph, typename _Path>
+      struct PathDumperConstraints<
+        _Graph, _Path, 
+        typename enable_if<typename _Path::RevPathTag, void>::type
+      > {
+        void constraints() {
+          int l = p.length();
+          int e = p.empty();
+
+          typename _Path::RevIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename _Graph::Edge ed = i;
+
+          e = (i == ii);
+          e = (i != ii);
+          e = (i < ii);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ii);
+          ignore_unused_variable_warning(ed);
+        }
+        _Path& p;
+      };
+    
+    }
+
+
+    /// \brief A skeleton structure for path dumpers.
+    ///
+    /// A skeleton structure for path dumpers. The path dumpers are
+    /// the generalization of the paths. The path dumpers can
+    /// enumerate the edges of the path wheter in forward or in
+    /// backward order.  In most time these classes are not used
+    /// directly rather it used to assign a dumped class to a real
+    /// path type.
+    ///
+    /// The main purpose of this concept is that the shortest path
+    /// algorithms can enumerate easily the edges in reverse order.
+    /// If we would like to give back a real path from these
+    /// algorithms then we should create a temporarly path object. In
+    /// Lemon such algorithms gives back a path dumper what can
+    /// assigned to a real path and the dumpers can be implemented as
+    /// an adaptor class to the predecessor map.
+
+    /// \param _Graph  The graph type in which the path is.
+    ///
+    /// The paths can be constructed from any path type by a
+    /// template constructor or a template assignment operator.
+    /// 
+    template <typename _Graph>
+    class PathDumper {
+    public:
+
+      /// Type of the underlying graph.
+      typedef _Graph Graph;
+      /// Edge type of the underlying graph.
+      typedef typename Graph::Edge Edge;
+
+      /// Length of the path ie. the number of edges in the path.
+      int length() const { return 0;}
+
+      /// Returns whether the path is empty.
+      bool empty() const { return true;}
+
+      /// \brief Forward or reverse dumping
       ///
-      /// This class is used to fill a path with edges.
+      /// If the RevPathTag is defined and true then reverse dumping
+      /// is provided in the path proxy. In this case instead of the
+      /// EdgeIt the RevIt iterator should be implemented in the
+      /// proxy.
+      typedef False RevPathTag;
+
+      /// \brief Lemon style iterator for path edges
       ///
-      /// You can push new edges to the front and to the back of the path in
-      /// arbitrary order then you should commit these changes to the graph.
+      /// This class is used to iterate on the edges of the paths.
+      class EdgeIt {
+      public:
+	/// Default constructor
+	EdgeIt() {}
+	/// Invalid constructor
+	EdgeIt(Invalid) {}
+	/// Constructor for first edge
+	EdgeIt(const PathDumper&) {}
+
+        /// Conversion to Edge
+	operator Edge() const { return INVALID; }
+
+	/// Next edge
+	EdgeIt& operator++() {return *this;}
+
+	/// Comparison operator
+	bool operator==(const EdgeIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const EdgeIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const EdgeIt&) const {return false;}
+
+      };
+
+      /// \brief Lemon style iterator for path edges
       ///
-      /// While the builder is active (after the first modifying
-      /// operation and until the call of \ref commit()) the
-      /// underlining Path is in a "transitional" state (operations on
-      /// it have undefined result).
-      class Builder {
+      /// This class is used to iterate on the edges of the paths in
+      /// reverse direction.
+      class RevIt {
       public:
+	/// Default constructor
+	RevIt() {}
+	/// Invalid constructor
+	RevIt(Invalid) {}
+	/// Constructor for first edge
+	RevIt(const PathDumper &) {}
 
-        /// Constructor
+        /// Conversion to Edge
+	operator Edge() const { return INVALID; }
 
-        /// Constructor
-	/// \param _path the path you want to fill in.
-	///
+	/// Next edge
+	RevIt& operator++() {return *this;}
 
-	Builder(Path &_path) { ignore_unused_variable_warning(_path); }
+	/// Comparison operator
+	bool operator==(const RevIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const RevIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const RevIt&) const {return false;}
 
-	/// Sets the starting node of the path.
-
-	/// Sets the starting node of the path. Edge added to the path
-	/// afterwards have to be incident to this node.
-	/// You \em must start building an empty path with these functions.
-	/// (And you \em must \em not use it later).
-	/// \sa pushFront()
-	/// \sa pushBack()
-	void setStartNode(const Node &) {}
-
-	///Push a new edge to the front of the path
-
-	///Push a new edge to the front of the path.
-	///If the path is empty, you \em must call \ref setStartNode() before
-	///the first use of \ref pushFront().
-	void pushFront(const Edge&) {}
-
-	///Push a new edge to the back of the path
-
-	///Push a new edge to the back of the path.
-	///If the path is empty, you \em must call \ref setStartNode() before
-	///the first use of \ref pushBack().
-	void pushBack(const Edge&) {}
-
-	///Commit the changes to the path.
-
-	///Commit the changes to the path.
-        ///
-	void commit() {}
-
-	///Reserve (front) storage for the builder in advance.
-
-	///If you know a reasonable upper bound on the number of the edges
-	///to add to the front of the path,
-	///using this function you may speed up the building.
-	void reserveFront(size_t) {}
-	///Reserve (back) storage for the builder in advance.
-
-	///If you know a reasonable upper bound on the number of the edges
-	///to add to the back of the path,
-	///using this function you may speed up the building.
-	void reserveBack(size_t) {}
       };
 
       template <typename _Path>
       struct Constraints {
-	void constraints() {
-          typedef typename _Path::Node Node;
-          typedef typename _Path::NodeIt NodeIt;
-          typedef typename Graph::Node GraphNode;
-
-          typedef typename _Path::Edge Edge;
-          typedef typename _Path::EdgeIt EdgeIt;
-          typedef typename Graph::Edge GraphEdge;
-
-          typedef typename _Path::Builder Builder;
-
-          path = _Path(graph);
-
-          bool b = cpath.empty();
-          int l = cpath.length();
-
-          Node gn;
-          Edge ge;
-          gn = cpath.source();
-          gn = cpath.target();
-
-          NodeIt nit;
-          EdgeIt eit(INVALID);
-          nit = path.source(eit);
-          nit = path.target(eit);
-          
-          nit = NodeIt();
-          nit = NodeIt(cpath);
-          nit = INVALID;
-          gn = nit;
-          ++nit;
-          b = nit == nit;
-          b = nit != nit;
-          b = nit < nit;
-
-          eit = EdgeIt();
-          eit = EdgeIt(cpath);
-          eit = INVALID;
-          ge = eit;
-          ++eit;
-          b = eit == eit;
-          b = eit != eit;
-          b = eit < eit;
-
-          size_t st = 0;
-
-          Builder builder(path); 
-          builder.setStartNode(gn);
-          builder.pushFront(ge);
-          builder.pushBack(ge);
-          builder.commit();
-          builder.reserveFront(st);
-          builder.reserveBack(st);
-          
-          ignore_unused_variable_warning(l);
-          ignore_unused_variable_warning(b);
-	}
-
-        const Graph& graph;
-        const _Path& cpath;
-        _Path& path;
+        void constraints() {
+          function_requires<_path_bits::
+            PathDumperConstraints<Graph, _Path> >();
+        }
       };
 
     };
 
-  ///@}
+
+    ///@}
   }
 
 } // namespace lemon
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/dag_shortest_path.h
--- a/lemon/dag_shortest_path.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/dag_shortest_path.h	Mon Jan 08 10:39:59 2007 +0000
@@ -722,26 +722,15 @@
     
     ///@{
 
-    /// \brief Copies the shortest path to \c t into \c p
-    ///    
-    /// This function copies the shortest path to \c t into \c p.
-    /// If it \c t is a source itself or unreachable, then it does not
-    /// alter \c p.
-    ///
-    /// \return Returns \c true if a path to \c t was actually copied to \c p,
-    /// \c false otherwise.
-    /// \sa DirPath
-    template <typename Path>
-    bool getPath(Path &p, Node t) {
-      if(reached(t)) {
-	p.clear();
-	typename Path::Builder b(p);
-	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
-	  b.pushFront(predEdge(t));
-	b.commit();
-	return true;
-      }
-      return false;
+    typedef PredMapPath<Graph, PredMap> Path;
+
+    ///Gives back the shortest path.
+    
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t) 
+    {
+      return Path(*graph, *_pred, t);
     }
 	  
     /// \brief The distance of a node from the root.
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/dfs.h
--- a/lemon/dfs.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/dfs.h	Mon Jan 08 10:39:59 2007 +0000
@@ -25,6 +25,7 @@
 
 #include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
+#include <lemon/bits/path_dump.h>
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
@@ -652,27 +653,15 @@
     
     ///@{
 
-    ///Copies the path to \c t on the DFS tree into \c p
+    typedef PredMapPath<Graph, PredMap> Path;
+
+    ///Gives back the shortest path.
     
-    ///This function copies the path to \c t on the DFS tree  into \c p.
-    ///If \c t is a source itself or unreachable, then it does not
-    ///alter \c p.
-    ///
-    ///\return Returns \c true if a path to \c t was actually copied to \c p,
-    ///\c false otherwise.
-    ///\sa DirPath
-    template<class P>
-    bool getPath(P &p,Node t) 
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t) 
     {
-      if(reached(t)) {
-	p.clear();
-	typename P::Builder b(p);
-	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
-	  b.pushFront(predEdge(t));
-	b.commit();
-	return true;
-      }
-      return false;
+      return Path(*G, *_pred, t);
     }
 
     ///The distance of a node from the root(s).
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/dijkstra.h
--- a/lemon/dijkstra.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/dijkstra.h	Mon Jan 08 10:39:59 2007 +0000
@@ -27,10 +27,12 @@
 
 #include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
+#include <lemon/bits/path_dump.h>
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
 
+
 namespace lemon {
 
   template<class T> T dijkstraZero() {return 0;}
@@ -717,28 +719,17 @@
     
     ///@{
 
-    ///Copies the shortest path to \c t into \c p
+    typedef PredMapPath<Graph, PredMap> Path;
+
+    ///Gives back the shortest path.
     
-    ///This function copies the shortest path to \c t into \c p.
-    ///If it \c t is a source itself or unreachable, then it does not
-    ///alter \c p.
-    ///\return Returns \c true if a path to \c t was actually copied to \c p,
-    ///\c false otherwise.
-    ///\sa DirPath
-    template<class P>
-    bool getPath(P &p,Node t) 
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t) 
     {
-      if(reached(t)) {
-	p.clear();
-	typename P::Builder b(p);
-	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
-	  b.pushFront(predEdge(t));
-	b.commit();
-	return true;
-      }
-      return false;
+      return Path(*G, *_pred, t);
     }
-	  
+
     ///The distance of a node from the root.
 
     ///Returns the distance of a node from the root.
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/floyd_warshall.h
--- a/lemon/floyd_warshall.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/floyd_warshall.h	Mon Jan 08 10:39:59 2007 +0000
@@ -26,6 +26,7 @@
 
 #include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
+#include <lemon/bits/path_dump.h>
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
 #include <lemon/matrix_maps.h>
@@ -480,27 +481,15 @@
     
     ///@{
 
-    /// \brief Copies the shortest path to \c t into \c p
-    ///    
-    /// This function copies the shortest path to \c t into \c p.
-    /// If it \c t is a source itself or unreachable, then it does not
-    /// alter \c p.
-    /// \return Returns \c true if a path to \c t was actually copied to \c p,
-    /// \c false otherwise.
-    /// \sa DirPath
-    template <typename Path>
-    bool getPath(Path &p, Node source, Node target) {
-      if (connected(source, target)) {
-	p.clear();
-	typename Path::Builder b(target);
-	for(b.setStartNode(target); predEdge(source, target) != INVALID;
-	    target = predNode(target)) {
-	  b.pushFront(predEdge(source, target));
-	}
-	b.commit();
-	return true;
-      }
-      return false;
+    typedef PredMatrixMapPath<Graph, PredMap> Path;
+
+    ///Gives back the shortest path.
+    
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the \c t.
+    Path path(Node s, Node t) 
+    {
+      return Path(*graph, *_pred, s, t);
     }
 	  
     /// \brief The distance between two nodes.
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/johnson.h
--- a/lemon/johnson.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/johnson.h	Mon Jan 08 10:39:59 2007 +0000
@@ -28,6 +28,7 @@
 #include <lemon/graph_utils.h>
 #include <lemon/dijkstra.h>
 #include <lemon/bellman_ford.h>
+#include <lemon/bits/path_dump.h>
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
@@ -629,27 +630,15 @@
     
     ///@{
 
-    /// \brief Copies the shortest path to \c t into \c p
-    ///    
-    /// This function copies the shortest path to \c t into \c p.
-    /// If it \c t is a source itself or unreachable, then it does not
-    /// alter \c p.
-    /// \return Returns \c true if a path to \c t was actually copied to \c p,
-    /// \c false otherwise.
-    /// \sa DirPath
-    template <typename Path>
-    bool getPath(Path &p, Node source, Node target) {
-      if (connected(source, target)) {
-	p.clear();
-	typename Path::Builder b(target);
-	for(b.setStartNode(target); predEdge(source, target) != INVALID;
-	    target = predNode(target)) {
-	  b.pushFront(predEdge(source, target));
-	}
-	b.commit();
-	return true;
-      }
-      return false;
+    typedef PredMatrixMapPath<Graph, PredMap> Path;
+
+    ///Gives back the shortest path.
+    
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the \c t.
+    Path path(Node s, Node t) 
+    {
+      return Path(*graph, *_pred, s, t);
     }
 	  
     /// \brief The distance between two nodes.
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/path.h
--- a/lemon/path.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/path.h	Mon Jan 08 10:39:59 2007 +0000
@@ -28,6 +28,7 @@
 #include <vector>
 #include <algorithm>
 
+#include <lemon/path_utils.h>
 #include <lemon/error.h>
 #include <lemon/bits/invalid.h>
 
@@ -37,392 +38,858 @@
   /// @{
 
 
-  //! \brief A structure for representing directed paths in a graph.
-  //!
-  //! A structure for representing directed path in a graph.
-  //! \param Graph The graph type in which the path is.
-  //!
-  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
-  //! and \c EdgeIt with the same usage. These types converts to the \c Node
-  //! and \c Edge of the original graph.
-  //!
-  //! \todo Thoroughfully check all the range and consistency tests.
-  template<typename Graph>
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of edges. The
+  /// lemon path type stores just this list. As a consequence it
+  /// cannot enumerate the nodes in the path and the zero length paths
+  /// cannot store the source.
+  ///
+  /// This implementation is a back and front insertable and erasable
+  /// path type. It can be indexed in O(1) time. The front and back
+  /// insertion and erasure is amortized O(1) time. The
+  /// impelementation is based on two opposite organized vectors.
+  template <typename _Graph>
   class Path {
   public:
-    /// Edge type of the underlying graph.
+
+    typedef _Graph Graph;
     typedef typename Graph::Edge Edge;
-    /// Node type of the underlying graph.
-    typedef typename Graph::Node Node;
 
-    class NodeIt;
-    class EdgeIt;
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    Path() {}
 
-    struct PathError : public LogicError {
-      virtual const char* what() const throw() {
-        return "lemon::PathError";
-      }      
-    };
-
-  public:
-
-    /// \brief Constructor
+    /// \brief Template copy constructor
     ///
-    /// Constructor 
-    /// \param _G The graph in which the path is.
-    Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
-    
-    /// \brief Subpath constructor.
-    ///
-    /// Subpath defined by two nodes.
-    /// \warning It is an error if the two edges are not in order!
-    Path(const Path &other, const NodeIt &a, const NodeIt &b) {
-      graph = other.graph; 
-      start = a;
-      edges.insert(edges.end(), 
-                   other.edges.begin() + a.id, other.edges.begin() + b.id);
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    Path(const CPath& cpath) {
+      copyPath(*this, cpath);
     }
 
-    /// \brief Subpath constructor.
+    /// \brief Template copy assignment
     ///
-    /// Subpath defined by two edges. Contains edges in [a,b)
-    /// \warning It is an error if the two edges are not in order!
-    Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
-      graph = other.graph;
-      start = graph->source(a);
-      edges.insert(edges.end(), 
-                   other.edges.begin() + a.id, other.edges.begin() + b.id);
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    Path& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
     }
 
-    /// \brief Length of the path.
+    /// \brief Lemon style iterator for path edges
     ///
-    /// The number of the edges in the path. It can be zero if the
-    /// path has only one node or it is empty.
-    int length() const { return edges.size(); }
-
-    /// \brief Returns whether the path is empty.
-    ///
-    /// Returns true when the path does not contain neither edge nor
-    /// node.
-    bool empty() const { return start == INVALID; }
-
-    /// \brief Resets the path to an empty path.
-    ///
-    /// Resets the path to an empty path.
-    void clear() { edges.clear(); start = INVALID; }
-
-    /// \brief Starting point of the path.
-    ///
-    /// Starting point of the path.
-    /// Returns INVALID if the path is empty.
-    Node source() const {
-      return start;
-    }
-    /// \brief End point of the path.
-    ///
-    /// End point of the path.
-    /// Returns INVALID if the path is empty.
-    Node target() const {
-      return length() == 0 ? start : graph->target(edges[length()-1]);
-    }
-
-    /// \brief Gives back a node iterator to point to the node of a
-    /// given index.
-    ///
-    /// Gives back a node iterator to point to the node of a given
-    /// index.
-    /// \pre n should less or equal to \c length()
-    NodeIt nthNode(int n) const {
-      return NodeIt(*this, n);
-    }
-
-    /// \brief Gives back an edge iterator to point to the edge of a
-    /// given index.
-    ///
-    /// Gives back an edge iterator to point to the node of a given
-    /// index.  
-    /// \pre n should less than \c length()
-    EdgeIt nthEdge(int n) const {
-      return EdgeIt(*this, n);
-    }
-
-    /// \brief Returns node iterator pointing to the source node of the
-    /// given edge iterator.
-    ///
-    /// Returns node iterator pointing to the source node of the given
-    /// edge iterator.
-    NodeIt source(const EdgeIt& e) const {
-      return NodeIt(*this, e.id);
-    }
-
-    /// \brief Returns node iterator pointing to the target node of the
-    /// given edge iterator.
-    ///
-    /// Returns node iterator pointing to the target node of the given
-    /// edge iterator.
-    NodeIt target(const EdgeIt& e) const {
-      return NodeIt(*this, e.id + 1);
-    }
-
-
-    /// \brief Iterator class to iterate on the nodes of the paths
-    ///
-    /// This class is used to iterate on the nodes of the paths
-    ///
-    /// Of course it converts to Graph::Node
-    class NodeIt {
+    /// This class is used to iterate on the edges of the paths.
+    class EdgeIt {
       friend class Path;
     public:
+      /// \brief Default constructor
+      EdgeIt() {}
+      /// \brief Invalid constructor
+      EdgeIt(Invalid) : path(0), idx(-1) {}
+      /// \brief Initializate the constructor to the first edge of path
+      EdgeIt(const Path &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 
-      /// \brief Default constructor
-      ///
-      /// Default constructor
-      NodeIt() {}
+    private:
 
-      /// \brief Invalid constructor
-      ///
-      /// Invalid constructor
-      NodeIt(Invalid) : id(-1), path(0) {}
+      EdgeIt(const Path &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
 
-      /// \brief Constructor with starting point
-      /// 
-      /// Constructor with starting point
-      NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
-        if (id > path->length()) id = -1; 
+    public:
+
+      /// \brief Conversion to Edge
+      operator const Edge&() const {
+        return path->nth(idx);
       }
 
-      /// \brief Conversion to Graph::Node
-      ///
-      /// Conversion to Graph::Node
-      operator Node() const {
-	if (id > 0) {
-	  return path->graph->target(path->edges[id - 1]);
-	} else if (id == 0) {
-	  return path->start;
-	} else {
-	  return INVALID;
-        }
-      }
-
-      /// \brief Steps to the next node
-      ///
-      /// Steps to the next node
-      NodeIt& operator++() { 
-        ++id; 
-        if (id > path->length()) id = -1; 
+      /// \brief Next edge
+      EdgeIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
         return *this; 
       }
 
       /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator==(const NodeIt& n) const { return id == n.id; }
-
+      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
       /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator!=(const NodeIt& n) const { return id != n.id; }
-
+      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
       /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator<(const NodeIt& n) const { return id < n.id; }
+      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
 
     private:
-      int id;
       const Path *path;
+      int idx;
     };
 
+    /// \brief Length of the path.
+    int length() const { return head.size() + tail.size(); }
+    /// \brief Returns whether the path is empty.
+    bool empty() const { return head.empty() && tail.empty(); }
+
+    /// \brief Resets the path to an empty path.
+    void clear() { head.clear(); tail.clear(); }
+
+    /// \brief Gives back the nth edge.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      return n < (int)head.size() ? *(head.rbegin() + n) :
+        *(tail.begin() + (n - head.size()));
+    }
+
+    /// \brief Initializes edge iterator to point to the nth edge
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    EdgeIt nthIt(int n) const {
+      return EdgeIt(*this, n);
+    }
+
+    /// \brief Gives back the first edge of the path
+    const Edge& front() const {
+      return head.empty() ? tail.front() : head.back();
+    }
+
+    /// \brief Add a new edge before the current path
+    void addFront(const Edge& edge) {
+      head.push_back(edge);
+    }
+
+    /// \brief Erase the first edge of the path
+    void eraseFront() {
+      if (!head.empty()) {
+        head.pop_back();
+      } else {
+        head.clear();
+        int halfsize = tail.size() / 2;
+        head.resize(halfsize);
+        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
+                  head.rbegin());
+        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
+        tail.resize(tail.size() - halfsize - 1);
+      }
+    }
+
+    /// \brief Gives back the last edge of the path
+    const Edge& back() const {
+      return tail.empty() ? head.front() : tail.back();
+    }
+
+    /// \brief Add a new edge behind the current path
+    void addBack(const Edge& edge) {
+      tail.push_back(edge);
+    }
+
+    /// \brief Erase the last edge of the path
+    void eraseBack() {
+      if (!tail.empty()) {
+        tail.pop_back();
+      } else {
+        int halfsize = head.size() / 2;
+        tail.resize(halfsize);
+        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
+                  tail.rbegin());
+        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
+        head.resize(head.size() - halfsize - 1);
+      }
+    }
+
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      int len = path.length();
+      tail.reserve(len);
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        tail.push_back(it);
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      int len = path.length();
+      head.reserve(len);
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        head.push_back(it);
+      }
+    }
+
+  protected:
+    typedef std::vector<Edge> Container;
+    Container head, tail;
+
+  };
+
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of edges. The
+  /// lemon path type stores just this list. As a consequence it
+  /// cannot enumerate the nodes in the path and the zero length paths
+  /// cannot store the source.
+  ///
+  /// This implementation is a just back insertable and erasable path
+  /// type. It can be indexed in O(1) time. The back insertion and
+  /// erasure is amortized O(1) time. This implementation is faster
+  /// then the \c Path type because it use just one vector for the
+  /// edges.
+  template <typename _Graph>
+  class SimplePath {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    SimplePath() {}
+
+    /// \brief Template copy constructor
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    SimplePath(const CPath& cpath) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Template copy assignment
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    SimplePath& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
     /// \brief Iterator class to iterate on the edges of the paths
     ///
     /// This class is used to iterate on the edges of the paths
+    ///
     /// Of course it converts to Graph::Edge
     class EdgeIt {
-      friend class Path;
+      friend class SimplePath;
+    public:
+      /// Default constructor
+      EdgeIt() {}
+      /// Invalid constructor
+      EdgeIt(Invalid) : path(0), idx(-1) {}
+      /// \brief Initializate the constructor to the first edge of path
+      EdgeIt(const SimplePath &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
+
+    private:
+
+      /// Constructor with starting point
+      EdgeIt(const SimplePath &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
+
     public:
 
-      /// \brief Default constructor
-      ///
-      /// Default constructor
-      EdgeIt() {}
-
-      /// \brief Invalid constructor
-      ///
-      /// Invalid constructor
-      EdgeIt(Invalid) : id(-1), path(0) {}
-
-      /// \brief Constructor with starting point
-      ///
-      /// Constructor with starting point
-      EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
-        if (id >= path->length()) id = -1;
+      ///Conversion to Graph::Edge
+      operator const Edge&() const {
+        return path->nth(idx);
       }
 
-      /// \brief Conversion to Graph::Edge
-      ///
-      /// Conversion to Graph::Edge
-      operator Edge() const {
-	return id != -1 ? path->edges[id] : INVALID;
-      }
-
-      /// \brief Steps to the next edge
-      ///
-      /// Steps to the next edge
+      /// Next edge
       EdgeIt& operator++() { 
-        ++id; 
-        if (id >= path->length()) id = -1;
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
         return *this; 
       }
 
-      /// \brief Comparison operator
-      ///
       /// Comparison operator
-      bool operator==(const EdgeIt& e) const { return id == e.id; }
+      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+      /// Comparison operator
+      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
 
-      /// \brief Comparison operator
-      ///
+    private:
+      const SimplePath *path;
+      int idx;
+    };
+
+    /// \brief Length of the path.
+    int length() const { return data.size(); }
+    /// \brief Returns whether the path is empty.
+    bool empty() const { return data.empty(); }
+
+    /// \brief Resets the path to an empty path.
+    void clear() { data.clear(); }
+
+    /// \brief Gives back the nth edge.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      return data[n];
+    }
+
+    /// \brief  Initializes edge iterator to point to the nth edge.
+    EdgeIt nthIt(int n) const {
+      return EdgeIt(*this, n);
+    }
+
+    /// \brief Gives back the last edge of the path.
+    const Edge& back() const {
+      return data.back();
+    }
+
+    /// \brief Add a new edge behind the current path.
+    void addBack(const Edge& edge) {
+      data.push_back(edge);
+    }
+
+    /// \brief Erase the last edge of the path
+    void eraseBack() {
+      data.pop_back();
+    }
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      int len = path.length();
+      data.resize(len);
+      int index = 0;
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        data[index] = it;;
+        ++index;
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      int len = path.length();
+      data.resize(len);
+      int index = len;
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        --index;
+        data[index] = it;;
+      }
+    }
+
+  protected:
+    typedef std::vector<Edge> Container;
+    Container data;
+
+  };
+
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of edges. The
+  /// lemon path type stores just this list. As a consequence it
+  /// cannot enumerate the nodes in the path and the zero length paths
+  /// cannot store the source.
+  ///
+  /// This implementation is a back and front insertable and erasable
+  /// path type. It can be indexed in O(k) time, where k is the rank
+  /// of the edge in the path. The length can be computed in O(n)
+  /// time. The front and back insertion and erasure is O(1) time
+  /// and it can be splited and spliced in O(1) time.
+  template <typename _Graph>
+  class ListPath {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+
+  protected:
+
+    // the std::list<> is incompatible 
+    // hard to create invalid iterator
+    struct Node {
+      Edge edge;
+      Node *next, *prev;
+    };
+
+    Node *first, *last;
+
+    std::allocator<Node> alloc;
+
+  public:
+ 
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    ListPath() : first(0), last(0) {}
+
+    /// \brief Template copy constructor
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    ListPath(const CPath& cpath) : first(0), last(0) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Destructor of the path
+    ///
+    /// Destructor of the path
+    ~ListPath() {
+      clear();
+    }
+
+    /// \brief Template copy assignment
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    ListPath& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
+    /// \brief Iterator class to iterate on the edges of the paths
+    ///
+    /// This class is used to iterate on the edges of the paths
+    ///
+    /// Of course it converts to Graph::Edge
+    class EdgeIt {
+      friend class ListPath;
+    public:
+      /// Default constructor
+      EdgeIt() {}
+      /// Invalid constructor
+      EdgeIt(Invalid) : path(0), node(0) {}
+      /// \brief Initializate the constructor to the first edge of path
+      EdgeIt(const ListPath &_path) 
+        : path(&_path), node(_path.first) {}
+
+    protected:
+
+      EdgeIt(const ListPath &_path, Node *_node) 
+        : path(&_path), node(_node) {}
+
+
+    public:
+
+      ///Conversion to Graph::Edge
+      operator const Edge&() const {
+        return node->edge;
+      }
+
+      /// Next edge
+      EdgeIt& operator++() { 
+        node = node->next;
+        return *this; 
+      }
+
       /// Comparison operator
-      bool operator!=(const EdgeIt& e) const { return id != e.id; }
+      bool operator==(const EdgeIt& e) const { return node==e.node; }
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return node!=e.node; }
+      /// Comparison operator
+      bool operator<(const EdgeIt& e) const { return node<e.node; }
 
-      /// \brief Comparison operator
-      ///
-      /// Comparison operator
-      bool operator<(const EdgeIt& e) const { return id < e.id; }
+    private:
+      const ListPath *path;
+      Node *node;
+    };
+
+    /// \brief Gives back the nth edge.
+    ///
+    /// Gives back the nth edge in O(n) time.
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      Node *node = first;
+      for (int i = 0; i < n; ++i) {
+        node = node->next;
+      }
+      return node->edge;
+    }
+
+    /// \brief Initializes edge iterator to point to the nth edge.
+    EdgeIt nthIt(int n) const {
+      Node *node = first;
+      for (int i = 0; i < n; ++i) {
+        node = node->next;
+      }
+      return EdgeIt(*this, node);
+    }
+
+    /// \brief Length of the path.
+    int length() const {
+      int len = 0;
+      Node *node = first;
+      while (node != 0) {
+        node = node->next;
+        ++len;
+      }
+      return len;
+    }
+
+    /// \brief Returns whether the path is empty.
+    bool empty() const { return first == 0; }
+
+    /// \brief Resets the path to an empty path.
+    void clear() {
+      while (first != 0) {
+        last = first->next;
+        alloc.destroy(first);
+        alloc.deallocate(first, 1);
+        first = last;
+      }
+    }
+
+    /// \brief Gives back the first edge of the path
+    const Edge& front() const {
+      return first->edge;
+    }
+
+    /// \brief Add a new edge before the current path
+    void addFront(const Edge& edge) {
+      Node *node = alloc.allocate(1);
+      alloc.construct(node, Node());
+      node->prev = 0;
+      node->next = first;
+      node->edge = edge;
+      if (first) {
+        first->prev = node;
+        first = node;
+      } else {
+        first = last = node;
+      }
+    }
+
+    /// \brief Erase the first edge of the path
+    void eraseFront() {
+      Node *node = first;
+      first = first->next;
+      if (first) {
+        first->prev = 0;
+      } else {
+        last = 0;
+      }
+      alloc.destroy(node);
+      alloc.deallocate(node, 1);
+    }
+
+    /// \brief Gives back the last edge of the path.
+    const Edge& back() const {
+      return last->edge;
+    }
+
+    /// \brief Add a new edge behind the current path.
+    void addBack(const Edge& edge) {
+      Node *node = alloc.allocate(1);
+      alloc.construct(node, Node());
+      node->next = 0;
+      node->prev = last;
+      node->edge = edge;
+      if (last) {
+        last->next = node;
+        last = node;
+      } else {
+        last = first = node;
+      }
+    }
+
+    /// \brief Erase the last edge of the path
+    void eraseBack() {
+      Node *node = last;
+      last = last->prev;
+      if (last) {
+        last->next = 0;
+      } else {
+        first = 0;
+      }
+      alloc.destroy(node);
+      alloc.deallocate(node, 1);
+    }
+
+    /// \brief Splicing the given path to the current path.
+    ///
+    /// It splices the \c tpath to the back of the current path and \c
+    /// tpath becomes empty. The time complexity of this function is
+    /// O(1).
+    void spliceBack(ListPath& tpath) {
+      if (first) {
+        if (tpath.first) {
+          last->next = tpath.first;
+          tpath.first->prev = last;
+          last = tpath.last;
+        }
+      } else {
+        first = tpath.first;
+        last = tpath.last;
+      }
+      tpath.first = tpath.last = 0;
+    }
+
+    /// \brief Splicing the given path to the current path.
+    ///
+    /// It splices the \c tpath before the current path and \c tpath
+    /// becomes empty. The time complexity of this function
+    /// is O(1).
+    void spliceFront(ListPath& tpath) {
+      if (first) {
+        if (tpath.first) {
+          first->prev = tpath.last;
+          tpath.last->next = first;
+          first = tpath.first;
+        }
+      } else {
+        first = tpath.first;
+        last = tpath.last;
+      }
+      tpath.first = tpath.last = 0;
+    }
+
+    /// \brief Splicing the given path into the current path.
+    ///
+    /// It splices the \c tpath into the current path before the
+    /// position of \c it iterator and \c tpath becomes empty. The
+    /// time complexity of this function is O(1). If the \c it is \c
+    /// INVALID then it will splice behind the current path.
+    void splice(EdgeIt it, ListPath& tpath) {
+      if (it.node) {
+        if (tpath.first) {
+          tpath.first->prev = it.node->prev;
+          if (it.node->prev) {
+            it.node->prev->next = tpath.first;
+          } else {
+            first = tpath.first;
+          }
+          it.node->prev = tpath.last;
+          tpath.last->next = it.node;
+        }
+      } else {
+        if (first) {
+          if (tpath.first) {
+            last->next = tpath.first;
+            tpath.first->prev = last;
+            last = tpath.last;
+          }
+        } else {
+          first = tpath.first;
+          last = tpath.last;
+        }
+      }
+      tpath.first = tpath.last = 0;
+    }
+
+    /// \brief Spliting the current path.
+    ///
+    /// It splits the current path into two parts. The part before \c
+    /// it iterator will remain in the current path and the part from
+    /// the it will put into the \c tpath. If the \c tpath had edges
+    /// before the operation they will be removed first.  The time
+    /// complexity of this function is O(1) plus the clearing of \c
+    /// tpath. If the \c it is \c INVALID then it just clears \c
+    /// tpath.
+    void split(EdgeIt it, ListPath& tpath) {
+      tpath.clear();
+      if (it.node) {
+        tpath.first = it.node;
+        tpath.last = last;
+        if (it.node->prev) {
+          last = it.node->prev;
+          last->next = 0;
+        } else {
+          first = last = 0;
+        }
+        it.node->prev = 0;
+      }
+    }
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        addBack(it);
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        addFront(it);
+      }
+    }
+
+  };
+
+  /// \brief A structure for representing directed paths in a graph.
+  ///
+  /// A structure for representing directed path in a graph.
+  /// \param Graph The graph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of edges. The
+  /// lemon path type stores just this list. As a consequence it
+  /// cannot enumerate the nodes in the path and the zero length paths
+  /// cannot store the source.
+  ///
+  /// This implementation is completly static, so it cannot be
+  /// modified exclude the assign an other path. It is intented to be
+  /// used when you want to store a large amount paths because it is
+  /// the most memory efficient path type in the lemon.
+  template <typename _Graph>
+  class StaticPath {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    StaticPath() : len(0), edges(0) {}
+    
+    /// \brief Template copy constructor
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    StaticPath(const CPath& cpath) : edges(0) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Destructor of the path
+    ///
+    /// Destructor of the path
+    ~StaticPath() {
+      if (edges) delete[] edges;
+    }
+
+    /// \brief Template copy assignment
+    ///
+    /// This path can be initialized with any other path type. It just
+    /// makes a copy of the given path.
+    template <typename CPath>
+    StaticPath& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
+    /// \brief Iterator class to iterate on the edges of the paths
+    ///
+    /// This class is used to iterate on the edges of the paths
+    ///
+    /// Of course it converts to Graph::Edge
+    class EdgeIt {
+      friend class StaticPath;
+    public:
+      /// Default constructor
+      EdgeIt() {}
+      /// Invalid constructor
+      EdgeIt(Invalid) : path(0), idx(-1) {}
+      /// Initializate the constructor to the first edge of path
+      EdgeIt(const StaticPath &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 
     private:
 
-      int id;
-      const Path *path;
+      /// Constructor with starting point
+      EdgeIt(const StaticPath &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
+
+    public:
+
+      ///Conversion to Graph::Edge
+      operator const Edge&() const {
+        return path->nth(idx);
+      }
+
+      /// Next edge
+      EdgeIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
+        return *this; 
+      }
+
+      /// Comparison operator
+      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+      /// Comparison operator
+      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
+
+    private:
+      const StaticPath *path;
+      int idx;
     };
 
-  protected:
+    /// \brief Gives back the nth edge.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Edge& nth(int n) const {
+      return edges[n];
+    }
 
-    const Graph *graph;
+    /// \brief Initializes edge iterator to point to the nth edge.
+    EdgeIt nthIt(int n) const {
+      return EdgeIt(*this, n);
+    }
 
-    typedef std::vector<Edge> Container;
-    Container edges;
-    Node start;
+    /// \brief Gives back the length of the path.
+    int length() const { return len; }
 
-  public:
+    /// \brief Returns true when the path is empty.
+    int empty() const { return len == 0; }
 
-    friend class Builder;
+    /// \break Erase all edge in the graph.
+    void clear() {
+      len = 0;
+      if (edges) delete[] edges;
+      edges = 0;
+    }
 
-    /// \brief Class to build paths
-    ///
-    /// This class is used to fill a path with edges.
-    ///
-    /// You can push new edges to the front and to the back of the
-    /// path in arbitrary order then you should commit these changes
-    /// to the graph.
-    ///
-    /// Fundamentally, for most "Paths" (classes fulfilling the
-    /// PathConcept) while the builder is active (after the first
-    /// modifying operation and until the commit()) the original Path
-    /// is in a "transitional" state (operations on it have undefined
-    /// result). But in the case of Path the original path remains
-    /// unchanged until the commit. However we don't recomend that you
-    /// use this feature.
-    class Builder {
-    public:
-      /// \brief Constructor
-      ///
-      /// Constructor
-      /// \param _path the path you want to fill in.
-      Builder(Path &_path) : path(_path), start(INVALID) {}
+    /// \brief Gives back the first edge of the path.
+    const Edge& front() const {
+      return edges[0];
+    }
 
-      /// \brief Destructor
-      ///
-      /// Destructor
-      ~Builder() {
-        LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 
-                     PathError());
+    /// \brief Gives back the last edge of the path.
+    const Edge& back() const {
+      return edges[len - 1];
+    }
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      len = path.length();
+      edges = new Edge[len];
+      int index = 0;
+      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
+        edges[index] = it;
+        ++index;
       }
+    }
 
-      /// \brief Sets the starting node of the path.
-      ///
-      /// Sets the starting node of the path. Edge added to the path
-      /// afterwards have to be incident to this node.  It should be
-      /// called if and only if the path is empty and before any call
-      /// to \ref pushFront() or \ref pushBack()
-      void setStartNode(const Node &_start) {
-        LEMON_ASSERT(path.empty() && start == INVALID, PathError());
-        start = _start;
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      len = path.length();
+      edges = new Edge[len];
+      int index = len;
+      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
+        --index;
+        edges[index] = it;
       }
+    }
 
-      /// \brief Push a new edge to the front of the path
-      ///
-      /// Push a new edge to the front of the path.  
-      /// \sa setStartNode
-      void pushFront(const Edge& e) {
-        LEMON_ASSERT(front.empty() || 
-                     (path.graph->source(front.back()) == 
-                      path.graph->target(e)), PathError());
-        LEMON_ASSERT(path.empty() || 
-                     (path.source() == path.graph->target(e)), PathError());
-        LEMON_ASSERT(!path.empty() || !front.empty() ||
-                     (start == path.graph->target(e)), PathError());
-	front.push_back(e);
-      }
-
-      /// \brief Push a new edge to the back of the path
-      ///
-      /// Push a new edge to the back of the path.
-      /// \sa setStartNode
-      void pushBack(const Edge& e) {
-        LEMON_ASSERT(back.empty() || 
-                     (path.graph->target(back.back()) == 
-                      path.graph->source(e)), PathError());
-        LEMON_ASSERT(path.empty() || 
-                     (path.target() == path.graph->source(e)), PathError());
-        LEMON_ASSERT(!path.empty() || !back.empty() ||
-                     (start == path.graph->source(e)), PathError());
-	back.push_back(e);
-      }
-
-      /// \brief Commit the changes to the path.
-      ///
-      /// Commit the changes to the path.
-      void commit() {
-	if( !front.empty() || !back.empty() || start != INVALID) {
-	  Container tmp;
-	  tmp.reserve(front.size() + back.size() + path.length());
-	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
-	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
-	  tmp.insert(tmp.end(), back.begin(), back.end());
-	  path.edges.swap(tmp);
-          if (!front.empty()) {
-            path.start = path.graph->source(front.back());
-          } else {
-            path.start = start;
-          }
-          start = INVALID;
-	  front.clear();
-	  back.clear();
-	}
-      }
-
-      /// \brief Reserve storage for the builder in advance.
-      ///
-      /// If you know a reasonable upper bound of the number of the
-      /// edges to add to the front, using this function you can speed
-      /// up the building.
-      void reserveFront(size_t r) {front.reserve(r);}
-
-      /// \brief Reserve storage for the builder in advance.
-      ///
-      /// If you know a reasonable upper bound of the number of the
-      /// edges to add to the back, using this function you can speed
-      /// up the building.
-      void reserveBack(size_t r) {back.reserve(r);}
-
-    private:
-
-      Path &path;
-      Container front, back;
-      Node start;
-
-    };
-
+  private:
+    int len;
+    Edge* edges;
   };
 
   ///@}
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/path_utils.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/path_utils.h	Mon Jan 08 10:39:59 2007 +0000
@@ -0,0 +1,140 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+
+///\ingroup paths
+///\file
+///\brief Classes for representing paths in graphs.
+///
+
+#ifndef LEMON_PATH_UTILS_H
+#define LEMON_PATH_UTILS_H
+
+#include <lemon/concepts/path.h>
+
+namespace lemon {
+
+  namespace _path_bits {
+
+    template <typename Path, typename Enable = void>
+    struct RevTagIndicator {
+      static const bool value = false;
+    };
+
+    template <typename Graph>
+    struct RevTagIndicator<
+      Graph, 
+      typename enable_if<typename Graph::RevTag, void>::type
+    > {
+      static const bool value = true;
+    };
+
+    template <typename Target, typename Source,
+              typename BuildEnable = void, typename RevEnable = void>
+    struct PathCopySelector {
+      static void copy(Target& target, const Source& source) {
+        source.clear();
+        for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
+          target.addBack(it);
+        }
+      }
+    };
+
+    template <typename Target, typename Source, typename BuildEnable>
+    struct PathCopySelector<
+      Target, Source, BuildEnable, 
+      typename enable_if<typename Source::RevPathTag, void>::type> {
+      static void copy(Target& target, const Source& source) {
+        source.clear();
+        for (typename Source::RevIt it(source); it != INVALID; ++it) {
+          target.addFront(it);
+        }
+      }
+    };
+
+    template <typename Target, typename Source, typename RevEnable>
+    struct PathCopySelector<
+      Target, Source, 
+      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
+      static void copy(Target& target, const Source& source) {
+        target.clear();
+        target.build(source);
+      }
+    };
+
+    template <typename Target, typename Source>
+    struct PathCopySelector<
+      Target, Source, 
+      typename enable_if<typename Target::BuildTag, void>::type,
+      typename enable_if<typename Source::RevPathTag, void>::type> {
+      static void copy(Target& target, const Source& source) {
+        target.clear();
+        target.buildRev(source);
+      }
+    };
+
+  }
+
+
+  /// \brief Make of copy of a path.
+  ///
+  ///  Make of copy of a path.
+  template <typename Target, typename Source>
+  void copyPath(Target& target, const Source& source) {
+    checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();
+    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
+  }
+
+  /// \brief Checks the path's consistency.
+  ///
+  /// Checks that each edge's target is the next's source. 
+  /// \Checks the path's consistency.
+  ///
+  /// Checks that each edge's target is the next's source. 
+  template <typename Graph, typename Path>
+  bool checkPath(const Graph& graph, const Path& path) {
+    typename Path::EdgeIt it(path);
+    if (it == INVALID) return true;
+    typename Graph::Node node = graph.target(it);
+    ++it;
+    while (it != INVALID) {
+      if (graph.source(it) != node) return false;
+      node = graph.target(it);
+      ++it;
+    }
+    return true;
+  }
+
+  /// \brief Gives back the source of the path
+  ///
+  /// Gives back the source of the path.
+  template <typename Graph, typename Path>
+  typename Graph::Node pathSource(const Graph& graph, const Path& path) {
+    return graph.source(path.front());
+  }
+
+  /// \brief Gives back the target of the path
+  ///
+  /// Gives back the target of the path.
+  template <typename Graph, typename Path>
+  typename Graph::Node pathTarget(const Graph& graph, const Path& path) {
+    return graph.target(path.back());
+  }
+}
+
+#endif
diff -r c1e936e6a46b -r 27aa03cd3121 lemon/suurballe.h
--- a/lemon/suurballe.h	Fri Jan 05 10:59:18 2007 +0000
+++ b/lemon/suurballe.h	Mon Jan 08 10:39:59 2007 +0000
@@ -26,6 +26,7 @@
 
 #include <lemon/maps.h>
 #include <vector>
+#include <lemon/path.h>
 #include <lemon/ssp_min_cost_flow.h>
 
 namespace lemon {
@@ -82,7 +83,7 @@
     SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
 
     //Container to store found paths
-    std::vector< std::vector<Edge> > paths;
+    std::vector<SimplePath<Graph> > paths;
 
   public :
 
@@ -134,7 +135,7 @@
 	    ++e;
 	  }
 	  n = G.target(e);
-	  paths[j].push_back(e);
+	  paths[j].addBack(e);
 	  reversed[e] = 1-reversed[e];
 	}
 	
@@ -170,6 +171,8 @@
       return min_cost_flow.checkComplementarySlackness();
     }
 
+    typedef SimplePath<Graph> Path; 
+
     /// \brief Read the found paths.
     ///
     /// This function gives back the \c j-th path in argument p.
@@ -181,25 +184,17 @@
     /// previous \c run, then the result here will be an empty path
     /// (\c j can be 0 as well).
     ///
-    /// \param Path The type of the path structure to put the result
-    /// to (must meet lemon path concept).
-    /// \param p The path to put the result to.
     /// \param j Which path you want to get from the found paths (in a
     /// real application you would get the found paths iteratively).
-    template<typename Path>
-    void getPath(Path& p, size_t j){
+    Path path(int j) const {
+      return paths[j];
+    }
 
-      p.clear();
-      if (j>paths.size()-1){
-	return;
-      }
-      typename Path::Builder B(p);
-      for(typename std::vector<Edge>::iterator i=paths[j].begin(); 
-	  i!=paths[j].end(); ++i ){
-	B.pushBack(*i);
-      }
-
-      B.commit();
+    /// \brief Gives back the number of the paths.
+    ///
+    /// Gives back the number of the constructed paths.
+    int pathNum() const {
+      return paths.size();
     }
 
   }; //class Suurballe
diff -r c1e936e6a46b -r 27aa03cd3121 test/all_pairs_shortest_path_test.cc
--- a/test/all_pairs_shortest_path_test.cc	Fri Jan 05 10:59:18 2007 +0000
+++ b/test/all_pairs_shortest_path_test.cc	Mon Jan 08 10:39:59 2007 +0000
@@ -29,6 +29,8 @@
 
 #include <lemon/fib_heap.h>
 
+#include <lemon/path.h>
+
 #include <lemon/time_measure.h>
 #include "test_tools.h"
 
@@ -90,6 +92,8 @@
     cout << "FloydWarshall: " << timer << endl;
   }    
 
+  bool checked_path = false;
+
   for (NodeIt it(graph); it != INVALID; ++it) {
     for (NodeIt jt(graph); jt != INVALID; ++jt) {
       check(johnson.connected(it, jt) == floyd.connected(it, jt),
@@ -97,6 +101,22 @@
       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
 	    "Wrong connection in all pairs shortest path");
       if (johnson.connected(it, jt)) {
+        if (it != jt && !checked_path) {
+          {
+            Path<Graph> path = johnson.path(it, jt);
+            check(checkPath(graph, path), "Wrong path.");
+            check(pathSource(graph, path) == it, "Wrong path.");
+            check(pathTarget(graph, path) == jt, "Wrong path.");
+          }
+          {
+            Path<Graph> path = floyd.path(it, jt);
+            check(checkPath(graph, path), "Wrong path.");
+            check(pathSource(graph, path) == it, "Wrong path.");
+            check(pathTarget(graph, path) == jt, "Wrong path.");
+          }
+          checked_path = true;
+          std::cout << "Path checked" << std::endl;
+        }
 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
 	      "Wrong distance in all pairs shortest path");
 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
diff -r c1e936e6a46b -r 27aa03cd3121 test/bfs_test.cc
--- a/test/bfs_test.cc	Fri Jan 05 10:59:18 2007 +0000
+++ b/test/bfs_test.cc	Mon Jan 08 10:39:59 2007 +0000
@@ -59,8 +59,7 @@
   //  pn = bfs_test.predNodeMap();
   b  = bfs_test.reached(n);
 
-  Path<Graph> pp(G);
-  bfs_test.getPath(pp,n);
+  Path<Graph> pp = bfs_test.path(n);
 }
 
 void check_Bfs_Function_Compile() 
@@ -109,9 +108,11 @@
   
   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
 
-  Path<Graph> p(G);
-  check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
+  Path<Graph> p = bfs_test.path(t);
   check(p.length()==3,"getPath() found a wrong path.");
+  check(checkPath(G, p),"path() found a wrong path.");
+  check(pathSource(G, p) == s,"path() found a wrong path.");
+  check(pathTarget(G, p) == t,"path() found a wrong path.");
   
 
   for(EdgeIt e(G); e==INVALID; ++e) {
diff -r c1e936e6a46b -r 27aa03cd3121 test/dfs_test.cc
--- a/test/dfs_test.cc	Fri Jan 05 10:59:18 2007 +0000
+++ b/test/dfs_test.cc	Mon Jan 08 10:39:59 2007 +0000
@@ -59,8 +59,7 @@
   //  pn = dfs_test.predNodeMap();
   b  = dfs_test.reached(n);
 
-  Path<Graph> pp(G);
-  dfs_test.getPath(pp,n);
+  Path<Graph> pp = dfs_test.path(n);
 }
 
 
@@ -108,9 +107,11 @@
   Dfs<Graph> dfs_test(G);
   dfs_test.run(s);  
   
-  Path<Graph> p(G);
-  check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
-  check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
+  Path<Graph> p = dfs_test.path(t);
+  check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
+  check(checkPath(G, p),"path() found a wrong path.");
+  check(pathSource(G, p) == s,"path() found a wrong path.");
+  check(pathTarget(G, p) == t,"path() found a wrong path.");
   
   for(NodeIt v(G); v!=INVALID; ++v) {
     check(dfs_test.reached(v),"Each node should be reached.");
diff -r c1e936e6a46b -r 27aa03cd3121 test/dijkstra_test.cc
--- a/test/dijkstra_test.cc	Fri Jan 05 10:59:18 2007 +0000
+++ b/test/dijkstra_test.cc	Mon Jan 08 10:39:59 2007 +0000
@@ -63,8 +63,7 @@
   //  pn = dijkstra_test.predNodeMap();
   b  = dijkstra_test.reached(n);
 
-  Path<Graph> pp(G);
-  dijkstra_test.getPath(pp,n);
+  Path<Graph> pp = dijkstra_test.path(n);
 }
 
 void check_Dijkstra_Function_Compile() 
@@ -120,9 +119,11 @@
   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
 
 
-  Path<Graph> p(G);
-  check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
+  Path<Graph> p = dijkstra_test.path(t);
   check(p.length()==4,"getPath() found a wrong path.");
+  check(checkPath(G, p),"path() found a wrong path.");
+  check(pathSource(G, p) == s,"path() found a wrong path.");
+  check(pathTarget(G, p) == t,"path() found a wrong path.");
   
 
   for(EdgeIt e(G); e!=INVALID; ++e) {
diff -r c1e936e6a46b -r 27aa03cd3121 test/path_test.cc
--- a/test/path_test.cc	Fri Jan 05 10:59:18 2007 +0000
+++ b/test/path_test.cc	Mon Jan 08 10:39:59 2007 +0000
@@ -31,78 +31,14 @@
 using namespace lemon;
 
 void check_concepts() {
-  checkConcept<concepts::Path<concepts::Graph>, 
-    concepts::Path<concepts::Graph> >();
-  checkConcept<concepts::Path<concepts::Graph>, 
-    Path<concepts::Graph> >();
+  checkConcept<concepts::Path<ListGraph>, concepts::Path<ListGraph> >();
   checkConcept<concepts::Path<ListGraph>, Path<ListGraph> >();
+  checkConcept<concepts::Path<ListGraph>, SimplePath<ListGraph> >();
+  checkConcept<concepts::Path<ListGraph>, StaticPath<ListGraph> >();
+  checkConcept<concepts::Path<ListGraph>, ListPath<ListGraph> >();
 }
 
 int main() {
-  check_concepts();
-  
-  ListGraph g;
-  
-  ListGraph::Node n1 = g.addNode();
-  ListGraph::Node n2 = g.addNode();
-  ListGraph::Node n3 = g.addNode();
-  ListGraph::Node n4 = g.addNode();
-  ListGraph::Node n5 = g.addNode();
- 
-  ListGraph::Edge e1 = g.addEdge(n1, n2);
-  ListGraph::Edge e2 = g.addEdge(n2, n3);
-  ListGraph::Edge e3 = g.addEdge(n3, n4);
-  ListGraph::Edge e4 = g.addEdge(n4, n5);
-  ListGraph::Edge e5 = g.addEdge(n5, n1);
-
-  {
-    Path<ListGraph> p(g);
-
-    check(p.empty(), "Wrong Path");
-    check(p.length() == 0, "Wrong Path");
-    
-    {
-      Path<ListGraph>::Builder b(p);
-      b.setStartNode(n3);
-      b.commit();
-    }
-
-    check(!p.empty(), "Wrong Path");
-    check(p.length() == 0, "Wrong Path");
-    check(p.source() == n3, "Wrong Path");
-    check(p.target() == n3, "Wrong Path");
-
-    {
-      Path<ListGraph>::Builder b(p);
-      b.pushBack(e3);
-      b.pushBack(e4);
-      b.pushFront(e2);
-      b.commit();
-    }
-
-    check(!p.empty(), "Wrong Path");
-    check(p.length() == 3, "Wrong Path");
-    check(p.source() == n2, "Wrong Path");
-    check(p.target() == n5, "Wrong Path");
-    
-    {
-      Path<ListGraph>::NodeIt it(p);
-      check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == INVALID, "Wrong Path");
-    }
-
-    {
-      Path<ListGraph>::EdgeIt it(p);
-      check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
-      check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
-      check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
-      check((ListGraph::Edge)it == INVALID, "Wrong Path");
-    }
-    
-  }
-  
+  check_concepts();  
   return 0;
 }