# HG changeset patch
# User deba
# Date 1161082257 0
# Node ID 269a0dcee70bc5c3e6e0b73d8fef21e92d894f85
# Parent  9c472eee236f36b512867e057911b1e5d3310adf
Update the Path concept
Concept check for paths

DirPath renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed
  // I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

diff -r 9c472eee236f -r 269a0dcee70b lemon/concept/path.h
--- a/lemon/concept/path.h	Tue Oct 17 10:42:19 2006 +0000
+++ b/lemon/concept/path.h	Tue Oct 17 10:50:57 2006 +0000
@@ -37,21 +37,22 @@
     //! \brief A skeleton structure for representing directed paths in a graph.
     //!
     //! A skeleton structure for representing directed paths in a graph.
-    //! \param GR The graph type in which the path is.
+    //! \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 GR>
+    template<typename _Graph>
     class Path {
     public:
 
       /// Type of the underlying graph.
-      typedef /*typename*/ GR Graph;
+      typedef _Graph Graph;
       /// Edge type of the underlying graph.
-      typedef typename Graph::Edge GraphEdge;
+      typedef typename Graph::Edge Edge;
       /// Node type of the underlying graph.
-     typedef typename Graph::Node GraphNode;
+      typedef typename Graph::Node Node;
+
       class NodeIt;
       class EdgeIt;
 
@@ -61,8 +62,9 @@
 	ignore_unused_variable_warning(_g);
       }
 
-      /// Length of the path.
+      /// 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;}
 
@@ -73,19 +75,12 @@
       ///
       /// Starting point of the path.
       /// Returns INVALID if the path is empty.
-      GraphNode/*It*/ target() const {return INVALID;}
+      Node target() const {return INVALID;}
       /// \brief End point of the path.
       ///
       /// End point of the path.
       /// Returns INVALID if the path is empty.
-      GraphNode/*It*/ source() const {return INVALID;}
-
-      /// \brief First NodeIt/EdgeIt.
-      ///
-      /// Initializes node or edge iterator to point to the first
-      /// node or edge.
-      template<typename It>
-      It& first(It &i) const { return i=It(*this); }
+      Node source() const {return INVALID;}
 
       /// \brief The target of an edge.
       ///
@@ -99,49 +94,11 @@
       /// given edge iterator.
       NodeIt source(const EdgeIt&) const {return INVALID;}
 
-
-      /* Iterator classes */
-
-      /**
-       * \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 {
-      public:
-	/// Default constructor
-	EdgeIt() {}
-	/// Invalid constructor
-	EdgeIt(Invalid) {}
-	/// Constructor with starting point
-	EdgeIt(const Path &) {}
-
-	operator GraphEdge () const {}
-
-	/// 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
-//      /// \todo It is not clear what is the "natural" ordering.
-// 	bool operator<(const EdgeIt& e) const {}
-
-      };
-
-      /**
-       * \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.
-       *
-       */
+      /// \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
@@ -152,7 +109,7 @@
 	NodeIt(const Path &) {}
 
 	///Conversion to Graph::Node
-	operator const GraphNode& () const {}
+	operator Node() const { return INVALID; }
 	/// Next node
 	NodeIt& operator++() {return *this;}
 
@@ -160,36 +117,63 @@
 	bool operator==(const NodeIt&) const {return true;}
 	/// Comparison operator
 	bool operator!=(const NodeIt&) const {return true;}
-// 	/// Comparison operator
-//      /// \todo It is not clear what is the "natural" ordering.
-// 	bool operator<(const NodeIt& e) const {}
+ 	/// 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
+      class EdgeIt {
+      public:
+	/// Default constructor
+	EdgeIt() {}
+	/// Invalid constructor
+	EdgeIt(Invalid) {}
+	/// Constructor with starting point
+	EdgeIt(const Path &) {}
+
+	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;}
+
+      };
+
+
       friend class Builder;
 
-      /**
-       * \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.
-       *
-       * 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).
-       */
+      /// \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.
+      ///
+      /// 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 {
       public:
 
-        Path &P;
+        /// Constructor
 
-	///\param _p the path you want to fill in.
+        /// Constructor
+	/// \param _path the path you want to fill in.
 	///
 
-	Builder(Path &_p) : P(_p) {}
+	Builder(Path &_path) { ignore_unused_variable_warning(_path); }
 
 	/// Sets the starting node of the path.
 
@@ -199,23 +183,26 @@
 	/// (And you \em must \em not use it later).
 	/// \sa pushFront()
 	/// \sa pushBack()
-	void setStartNode(const GraphNode &) {}
+	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 GraphEdge&) {}
+	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 GraphEdge&) {}
+	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.
@@ -231,6 +218,72 @@
 	///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;
+      };
+
     };
 
   ///@}
diff -r 9c472eee236f -r 269a0dcee70b lemon/path.h
--- a/lemon/path.h	Tue Oct 17 10:42:19 2006 +0000
+++ b/lemon/path.h	Tue Oct 17 10:50:57 2006 +0000
@@ -21,15 +21,14 @@
 ///\file
 ///\brief Classes for representing paths in graphs.
 ///
-///\todo Iterators have obsolete style
 
 #ifndef LEMON_PATH_H
 #define LEMON_PATH_H
 
-#include <deque>
 #include <vector>
 #include <algorithm>
 
+#include <lemon/error.h>
 #include <lemon/bits/invalid.h>
 
 namespace lemon {
@@ -42,7 +41,6 @@
   //!
   //! A structure for representing directed path in a graph.
   //! \param Graph The graph type in which the path is.
-  //! \param DM DebugMode, defaults to DefaultDebugMode.
   //!
   //! 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
@@ -50,640 +48,383 @@
   //!
   //! \todo Thoroughfully check all the range and consistency tests.
   template<typename Graph>
-  class DirPath {
+  class Path {
   public:
     /// Edge type of the underlying graph.
-    typedef typename Graph::Edge GraphEdge;
+    typedef typename Graph::Edge Edge;
     /// Node type of the underlying graph.
-    typedef typename Graph::Node GraphNode;
+    typedef typename Graph::Node Node;
+
     class NodeIt;
     class EdgeIt;
 
-  protected:
-    const Graph *gr;
-    typedef std::vector<GraphEdge> Container;
-    Container edges;
+    struct PathError : public LogicError {
+      virtual const char* what() const throw() {
+        return "lemon::PathError";
+      }      
+    };
 
   public:
 
+    /// \brief Constructor
+    ///
+    /// Constructor 
     /// \param _G The graph in which the path is.
-    ///
-    DirPath(const Graph &_G) : gr(&_G) {}
-
+    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!
-    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
-      gr = P.gr;
-      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
+    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);
     }
 
     /// \brief Subpath constructor.
     ///
     /// Subpath defined by two edges. Contains edges in [a,b)
     /// \warning It is an error if the two edges are not in order!
-    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
-      gr = P.gr;
-      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
+    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);
     }
 
-    /// Length of the path.
+    /// \brief Length of the path.
+    ///
+    /// 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(); }
-    /// Returns whether the path is empty.
-    bool empty() const { return edges.empty(); }
 
+    /// \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(); }
+    void clear() { edges.clear(); start = INVALID; }
 
     /// \brief Starting point of the path.
     ///
     /// Starting point of the path.
     /// Returns INVALID if the path is empty.
-    GraphNode source() const {
-      return empty() ? INVALID : gr->source(edges[0]);
+    Node source() const {
+      return start;
     }
     /// \brief End point of the path.
     ///
     /// End point of the path.
     /// Returns INVALID if the path is empty.
-    GraphNode target() const {
-      return empty() ? INVALID : gr->target(edges[length()-1]);
+    Node target() const {
+      return length() == 0 ? start : graph->target(edges[length()-1]);
     }
 
-    /// \brief Initializes node or edge iterator to point to the first
-    /// node or edge.
+    /// \brief Gives back a node iterator to point to the node of a
+    /// given index.
     ///
-    /// \sa nth
-    template<typename It>
-    It& first(It &i) const { return i=It(*this); }
-
-    /// \brief Initializes node iterator to point to the node of a given index.
-    NodeIt& nth(NodeIt &i, int n) const {
-      return i=NodeIt(*this, n);
+    /// 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 Initializes edge iterator to point to the edge of a given index.
-    EdgeIt& nth(EdgeIt &i, int n) const {
-      return i=EdgeIt(*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.idx+1);
+      return NodeIt(*this, e.id + 1);
     }
 
-    /// \brief Returns node iterator pointing to the source node of the
-    /// given edge iterator.
-    NodeIt source(const EdgeIt& e) const {
-      return NodeIt(*this, e.idx);
-    }
 
+    /// \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 {
+      friend class Path;
+    public:
 
-    /* Iterator classes */
+      /// \brief Default constructor
+      ///
+      /// Default constructor
+      NodeIt() {}
 
-    /**
-     * \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
-     *
-     */
+      /// \brief Invalid constructor
+      ///
+      /// Invalid constructor
+      NodeIt(Invalid) : id(-1), path(0) {}
+
+      /// \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; 
+      }
+
+      /// \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; 
+        return *this; 
+      }
+
+      /// \brief Comparison operator
+      ///
+      /// Comparison operator
+      bool operator==(const NodeIt& n) const { return id == n.id; }
+
+      /// \brief Comparison operator
+      ///
+      /// Comparison operator
+      bool operator!=(const NodeIt& n) const { return id != n.id; }
+
+      /// \brief Comparison operator
+      ///
+      /// Comparison operator
+      bool operator<(const NodeIt& n) const { return id < n.id; }
+
+    private:
+      int id;
+      const Path *path;
+    };
+
+    /// \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 DirPath;
+      friend class Path;
+    public:
 
-      int idx;
-      const DirPath *p;
-    public:
+      /// \brief Default constructor
+      ///
       /// Default constructor
       EdgeIt() {}
+
+      /// \brief Invalid constructor
+      ///
       /// Invalid constructor
-      EdgeIt(Invalid) : idx(-1), p(0) {}
+      EdgeIt(Invalid) : id(-1), path(0) {}
+
+      /// \brief Constructor with starting point
+      ///
       /// Constructor with starting point
-      EdgeIt(const DirPath &_p, int _idx = 0) :
-	idx(_idx), p(&_p) { validate(); }
-
-      ///Validity check
-      bool valid() const { return idx!=-1; }
-
-      ///Conversion to Graph::Edge
-      operator GraphEdge () const {
-	return valid() ? p->edges[idx] : INVALID;
+      EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
+        if (id >= path->length()) id = -1;
       }
 
-      /// Next edge
-      EdgeIt& operator++() { ++idx; validate(); return *this; }
+      /// \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
+      EdgeIt& operator++() { 
+        ++id; 
+        if (id >= path->length()) id = -1;
+        return *this; 
+      }
+
+      /// \brief Comparison operator
+      ///
       /// Comparison operator
-      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+      bool operator==(const EdgeIt& e) const { return id == e.id; }
+
+      /// \brief Comparison operator
+      ///
       /// Comparison operator
-      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+      bool operator!=(const EdgeIt& e) const { return id != e.id; }
+
+      /// \brief Comparison operator
+      ///
       /// Comparison operator
-      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
+      bool operator<(const EdgeIt& e) const { return id < e.id; }
 
     private:
-      void validate() { if(idx >= p->length() ) idx=-1; }
+
+      int id;
+      const Path *path;
     };
 
-    /**
-     * \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 {
-      friend class DirPath;
+  protected:
 
-      int idx;
-      const DirPath *p;
-    public:
-      /// Default constructor
-      NodeIt() {}
-      /// Invalid constructor
-      NodeIt(Invalid) : idx(-1), p(0) {}
-      /// Constructor with starting point
-      NodeIt(const DirPath &_p, int _idx = 0) :
-	idx(_idx), p(&_p) { validate(); }
+    const Graph *graph;
 
-      ///Validity check
-      bool valid() const { return idx!=-1; }
+    typedef std::vector<Edge> Container;
+    Container edges;
+    Node start;
 
-      ///Conversion to Graph::Node
-      operator GraphNode () const {
-	if(idx >= p->length())
-	  return p->target();
-	else if(idx >= 0)
-	  return p->gr->source(p->edges[idx]);
-	else
-	  return INVALID;
-      }
-      /// Next node
-      NodeIt& operator++() { ++idx; validate(); return *this; }
-
-      /// Comparison operator
-      bool operator==(const NodeIt& e) const { return idx==e.idx; }
-      /// Comparison operator
-      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
-      /// Comparison operator
-      bool operator<(const NodeIt& e) const { return idx<e.idx; }
-
-    private:
-      void validate() { if(idx > p->length() ) idx=-1; }
-    };
+  public:
 
     friend class Builder;
 
-    /**
-     * \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 DirPath the original path remains unchanged until the
-     * commit. However we don't recomend that you use this feature.
-     */
+    /// \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 {
-      DirPath &P;
-      Container front, back;
+    public:
+      /// \brief Constructor
+      ///
+      /// Constructor
+      /// \param _path the path you want to fill in.
+      Builder(Path &_path) : path(_path), start(INVALID) {}
 
-    public:
-      ///\param _p the path you want to fill in.
+      /// \brief Destructor
       ///
-      Builder(DirPath &_p) : P(_p) {}
+      /// Destructor
+      ~Builder() {
+        LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 
+                     PathError());
+      }
 
-      /// Sets the starting node of the path.
+      /// \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;
+      }
 
-      /// 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 GraphNode &) {}
-
-      ///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 GraphEdge& e) {
+      /// \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);
       }
 
-      ///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 GraphEdge& 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);
       }
 
-      ///Commit the changes to the path.
+      /// \brief Commit the changes to the path.
+      ///
+      /// Commit the changes to the path.
       void commit() {
-	if( !front.empty() || !back.empty() ) {
+	if( !front.empty() || !back.empty() || start != INVALID) {
 	  Container tmp;
-	  tmp.reserve(front.size()+back.size()+P.length());
+	  tmp.reserve(front.size() + back.size() + path.length());
 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
-	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
+	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
 	  tmp.insert(tmp.end(), back.begin(), back.end());
-	  P.edges.swap(tmp);
+	  path.edges.swap(tmp);
+          if (!front.empty()) {
+            path.start = path.graph->source(front.back());
+          } else {
+            path.start = start;
+          }
+          start = INVALID;
 	  front.clear();
 	  back.clear();
 	}
       }
 
-      ///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.
-
+      /// \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);}
 
-      ///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.
-
+      /// \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:
-      bool empty() {
-	return front.empty() && back.empty() && P.empty();
-      }
 
-      GraphNode source() const {
-	if( ! front.empty() )
-	  return P.gr->source(front[front.size()-1]);
-	else if( ! P.empty() )
-	  return P.gr->source(P.edges[0]);
-	else if( ! back.empty() )
-	  return P.gr->source(back[0]);
-	else
-	  return INVALID;
-      }
-      GraphNode target() const {
-	if( ! back.empty() )
-	  return P.gr->target(back[back.size()-1]);
-	else if( ! P.empty() )
-	  return P.gr->target(P.edges[P.length()-1]);
-	else if( ! front.empty() )
-	  return P.gr->target(front[0]);
-	else
-	  return INVALID;
-      }
+      Path &path;
+      Container front, back;
+      Node start;
 
     };
 
   };
 
-
-
-
-
-
-
-
-
-
-  /**********************************************************************/
-
-
-  //! \brief A structure for representing undirected path in a graph.
-  //!
-  //! A structure for representing undirected path in a graph. Ie. this is
-  //! a path in a \e directed graph but the edges should not be directed
-  //! forward.
-  //!
-  //! \param Graph The graph type in which the path is.
-  //! \param DM DebugMode, defaults to DefaultDebugMode.
-  //!
-  //! 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.
-  /// \todo May we need just path for undirected graph instead of this.
-  template<typename Graph>
-  class UPath {
-  public:
-    /// Edge type of the underlying graph.
-    typedef typename Graph::Edge GraphEdge;
-     /// Node type of the underlying graph.
-   typedef typename Graph::Node GraphNode;
-    class NodeIt;
-    class EdgeIt;
-
-  protected:
-    const Graph *gr;
-    typedef std::vector<GraphEdge> Container;
-    Container edges;
-
-  public:
-
-    /// \param _G The graph in which the path is.
-    ///
-    UPath(const Graph &_G) : gr(&_G) {}
-
-    /// \brief Subpath constructor.
-    ///
-    /// Subpath defined by two nodes.
-    /// \warning It is an error if the two edges are not in order!
-    UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
-      gr = P.gr;
-      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
-    }
-
-    /// \brief Subpath constructor.
-    ///
-    /// Subpath defined by two edges. Contains edges in [a,b)
-    /// \warning It is an error if the two edges are not in order!
-    UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
-      gr = P.gr;
-      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
-    }
-
-    /// Length of the path.
-    size_t length() const { return edges.size(); }
-    /// Returns whether the path is empty.
-    bool empty() const { return edges.empty(); }
-
-    /// Resets the path to an empty path.
-    void clear() { edges.clear(); }
-
-    /// \brief Starting point of the path.
-    ///
-    /// Starting point of the path.
-    /// Returns INVALID if the path is empty.
-    GraphNode source() const {
-      return empty() ? INVALID : gr->source(edges[0]);
-    }
-    /// \brief End point of the path.
-    ///
-    /// End point of the path.
-    /// Returns INVALID if the path is empty.
-    GraphNode target() const {
-      return empty() ? INVALID : gr->target(edges[length()-1]);
-    }
-
-    /// \brief Initializes node or edge iterator to point to the first
-    /// node or edge.
-    ///
-    /// \sa nth
-    template<typename It>
-    It& first(It &i) const { return i=It(*this); }
-
-    /// \brief Initializes node iterator to point to the node of a given index.
-    NodeIt& nth(NodeIt &i, int n) const {
-      return i=NodeIt(*this, n);
-    }
-
-    /// \brief Initializes edge iterator to point to the edge of a given index.
-    EdgeIt& nth(EdgeIt &i, int n) const {
-      return i=EdgeIt(*this, n);
-    }
-
-    /// Checks validity of a node or edge iterator.
-    template<typename It>
-    static
-    bool valid(const It &i) { return i.valid(); }
-
-    /// Steps the given node or edge iterator.
-    template<typename It>
-    static
-    It& next(It &e) {
-      return ++e;
-    }
-
-    /// \brief Returns node iterator pointing to the target node of the
-    /// given edge iterator.
-    NodeIt target(const EdgeIt& e) const {
-      return NodeIt(*this, e.idx+1);
-    }
-
-    /// \brief Returns node iterator pointing to the source node of the
-    /// given edge iterator.
-    NodeIt source(const EdgeIt& e) const {
-      return NodeIt(*this, e.idx);
-    }
-
-
-
-    /**
-     * \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
-     *
-     * \todo Its interface differs from the standard edge iterator.
-     * Yes, it shouldn't.
-     */
-    class EdgeIt {
-      friend class UPath;
-
-      int idx;
-      const UPath *p;
-    public:
-      /// Default constructor
-      EdgeIt() {}
-      /// Invalid constructor
-      EdgeIt(Invalid) : idx(-1), p(0) {}
-      /// Constructor with starting point
-      EdgeIt(const UPath &_p, int _idx = 0) :
-	idx(_idx), p(&_p) { validate(); }
-
-      ///Validity check
-      bool valid() const { return idx!=-1; }
-
-      ///Conversion to Graph::Edge
-      operator GraphEdge () const {
-	return valid() ? p->edges[idx] : INVALID;
-      }
-      /// Next edge
-     EdgeIt& operator++() { ++idx; validate(); 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:
-      // FIXME: comparison between signed and unsigned...
-      // Jo ez igy? Vagy esetleg legyen a length() int?
-      void validate() { if( size_t(idx) >= p->length() ) idx=-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
-     *
-     * \todo Its interface differs from the standard node iterator.
-     * Yes, it shouldn't.
-     */
-    class NodeIt {
-      friend class UPath;
-
-      int idx;
-      const UPath *p;
-    public:
-      /// Default constructor
-      NodeIt() {}
-      /// Invalid constructor
-      NodeIt(Invalid) : idx(-1), p(0) {}
-      /// Constructor with starting point
-      NodeIt(const UPath &_p, int _idx = 0) :
-	idx(_idx), p(&_p) { validate(); }
-
-      ///Validity check
-      bool valid() const { return idx!=-1; }
-
-      ///Conversion to Graph::Node
-      operator const GraphNode& () const {
-	if(idx >= p->length())
-	  return p->target();
-	else if(idx >= 0)
-	  return p->gr->source(p->edges[idx]);
-	else
-	  return INVALID;
-      }
-      /// Next node
-      NodeIt& operator++() { ++idx; validate(); return *this; }
-
-      /// Comparison operator
-      bool operator==(const NodeIt& e) const { return idx==e.idx; }
-      /// Comparison operator
-      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
-       /// Comparison operator
-     bool operator<(const NodeIt& e) const { return idx<e.idx; }
-
-    private:
-      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
-    };
-
-    friend class Builder;
-
-    /**
-     * \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 ot it have undefined result). But
-     * in the case of UPath the original path is unchanged until the
-     * commit. However we don't recomend that you use this feature.
-     */
-    class Builder {
-      UPath &P;
-      Container front, back;
-
-    public:
-      ///\param _p the path you want to fill in.
-      ///
-      Builder(UPath &_p) : P(_p) {}
-
-      /// 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 GraphNode &) {}
-
-      ///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 GraphEdge& e) {
-	front.push_back(e);
-      }
-
-      ///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 GraphEdge& e) {
-	back.push_back(e);
-      }
-
-      ///Commit the changes to the path.
-      void commit() {
-	if( !(front.empty() && back.empty()) ) {
-	  Container tmp;
-	  tmp.reserve(front.size()+back.size()+P.length());
-	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
-	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
-	  tmp.insert(tmp.end(), back.begin(), back.end());
-	  P.edges.swap(tmp);
-	  front.clear();
-	  back.clear();
-	}
-      }
-
-
-      ///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);}
-
-      ///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:
-      bool empty() {
-	return front.empty() && back.empty() && P.empty();
-      }
-
-      GraphNode source() const {
-	if( ! front.empty() )
-	  return P.gr->source(front[front.size()-1]);
-	else if( ! P.empty() )
-	  return P.gr->source(P.edges[0]);
-	else if( ! back.empty() )
-	  return P.gr->source(back[0]);
-	else
-	  return INVALID;
-      }
-      GraphNode target() const {
-	if( ! back.empty() )
-	  return P.gr->target(back[back.size()-1]);
-	else if( ! P.empty() )
-	  return P.gr->target(P.edges[P.length()-1]);
-	else if( ! front.empty() )
-	  return P.gr->target(front[0]);
-	else
-	  return INVALID;
-      }
-
-    };
-
-  };
-
-
   ///@}
 
 } // namespace lemon
diff -r 9c472eee236f -r 269a0dcee70b test/bfs_test.cc
--- a/test/bfs_test.cc	Tue Oct 17 10:42:19 2006 +0000
+++ b/test/bfs_test.cc	Tue Oct 17 10:50:57 2006 +0000
@@ -59,7 +59,7 @@
   //  pn = bfs_test.predNodeMap();
   b  = bfs_test.reached(n);
 
-  DirPath<Graph> pp(G);
+  Path<Graph> pp(G);
   bfs_test.getPath(pp,n);
 }
 
@@ -109,7 +109,7 @@
   
   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
 
-  DirPath<Graph> p(G);
+  Path<Graph> p(G);
   check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
   check(p.length()==3,"getPath() found a wrong path.");
   
diff -r 9c472eee236f -r 269a0dcee70b test/dfs_test.cc
--- a/test/dfs_test.cc	Tue Oct 17 10:42:19 2006 +0000
+++ b/test/dfs_test.cc	Tue Oct 17 10:50:57 2006 +0000
@@ -59,7 +59,7 @@
   //  pn = dfs_test.predNodeMap();
   b  = dfs_test.reached(n);
 
-  DirPath<Graph> pp(G);
+  Path<Graph> pp(G);
   dfs_test.getPath(pp,n);
 }
 
@@ -108,7 +108,7 @@
   Dfs<Graph> dfs_test(G);
   dfs_test.run(s);  
   
-  DirPath<Graph> p(G);
+  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.");
   
diff -r 9c472eee236f -r 269a0dcee70b test/dijkstra_test.cc
--- a/test/dijkstra_test.cc	Tue Oct 17 10:42:19 2006 +0000
+++ b/test/dijkstra_test.cc	Tue Oct 17 10:50:57 2006 +0000
@@ -63,7 +63,7 @@
   //  pn = dijkstra_test.predNodeMap();
   b  = dijkstra_test.reached(n);
 
-  DirPath<Graph> pp(G);
+  Path<Graph> pp(G);
   dijkstra_test.getPath(pp,n);
 }
 
@@ -120,7 +120,7 @@
   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
 
 
-  DirPath<Graph> p(G);
+  Path<Graph> p(G);
   check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
   check(p.length()==4,"getPath() found a wrong path.");
   
diff -r 9c472eee236f -r 269a0dcee70b test/path_test.cc
--- a/test/path_test.cc	Tue Oct 17 10:42:19 2006 +0000
+++ b/test/path_test.cc	Tue Oct 17 10:50:57 2006 +0000
@@ -18,81 +18,91 @@
 
 #include <string>
 #include <iostream>
+
 #include <lemon/concept/path.h>
+#include <lemon/concept/graph.h>
+
 #include <lemon/path.h>
 #include <lemon/list_graph.h>
 
+#include "test_tools.h"
+
 using namespace std;
 using namespace lemon;
-using namespace lemon::concept;
 
-template<class Path> void checkCompilePath(Path &P) 
-{
-  typedef typename Path::EdgeIt EdgeIt;
-  typedef typename Path::NodeIt NodeIt;
-  typedef typename Path::GraphNode GraphNode;
-  typedef typename Path::GraphEdge GraphEdge;
-  //typedef typename Path::Builder Builder;
-  //??? ha csinalok ilyet es siman Builderrel peldanyositok, akkor warningol. Talan friend miatt? De ki az?
-
-  EdgeIt ei;
-  NodeIt ni;
-  GraphNode gn;
-  GraphEdge ge;
-
-  size_t st;
-  bool b;
-
-  //Path(const Graph &_G) {}      //the constructor has been already called
-
-  st=P.length();                  //size_t length() const {return 0;}
-  b=P.empty();                    //bool empty() const {}
-  P.clear();                      //void clear() {}
-
-  gn=P.target();                    //GraphNode/*It*/ target() const {return INVALID;}
-  gn=P.source();                    //GraphNode/*It*/ source() const {return INVALID;}
-
-  ei=P.first(ei);                 //It& first(It &i) const { return i=It(*this); }
-
-  ni=P.target(ei);                  //NodeIt target(const EdgeIt& e) const {}
-  ni=P.source(ei);                  //NodeIt source(const EdgeIt& e) const {}
-
-
-  ListGraph lg;
-  Path p(lg);
-
-  EdgeIt i;	                  //EdgeIt() {}
-  EdgeIt j(INVALID);	          //EdgeIt(Invalid) {}
-  EdgeIt k(p);	                  //EdgeIt(const Path &_p) {}
-
-  i=++j;	                  //EdgeIt& operator++() {}
-  ++k;
-  b=(i==j);	                  //bool operator==(const EdgeIt& e) const {return true;}
-  b=(i!=j);	                  //bool operator!=(const EdgeIt& e) const {return true;}
-
-
-  NodeIt l;                       //NodeIt() {}
-  NodeIt m(INVALID);	          //NodeIt(Invalid) {}
-  NodeIt n(p);	                  //NodeIt(const Path &_p) {}
-
-  l=++m;                          //NodeIt& operator++() {}
-  b=(m==n);                       //bool operator==(const NodeIt& e) const {}
-  b=(m!=n);                   	  //bool operator!=(const NodeIt& e) const {}
-
-  typename Path::Builder builder(p);     //Builder(Path &_P) : P(_P) {}
-  builder.setStartNode(gn);     	 //void setStartNode(const GraphNode &) {}
-  builder.pushFront(ge);	         //void pushFront(const GraphEdge& e) {}
-  builder.pushBack(ge);	                 //void pushBack(const GraphEdge& e) {}
-  builder.commit();	                 //void commit() {}
-  builder.reserveFront(st);	         //void reserveFront(size_t r) {}
-  builder.reserveBack(st);	         //void reserveBack(size_t r) {}
-
+void check_concepts() {
+  checkConcept<concept::Path<concept::Graph>, 
+    concept::Path<concept::Graph> >();
+  checkConcept<concept::Path<concept::Graph>, 
+    Path<concept::Graph> >();
+  checkConcept<concept::Path<ListGraph>, Path<ListGraph> >();
 }
 
-template void checkCompilePath< concept::Path<ListGraph> >(concept::Path<ListGraph> &);
-template void checkCompilePath< DirPath<ListGraph> >(DirPath<ListGraph> &);
-template void checkCompilePath< UPath<ListGraph> >(UPath<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);
 
-int main() 
-{
+  {
+    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");
+    }
+    
+  }
+  
+  return 0;
 }