Index: lemon/path.h
===================================================================
--- lemon/path.h	(revision 2084)
+++ lemon/path.h	(revision 2247)
@@ -22,13 +22,12 @@
 ///\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>
 
@@ -43,5 +42,4 @@
   //! 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
@@ -51,31 +49,37 @@
   //! \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);
     }
 
@@ -84,16 +88,27 @@
     /// 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);
-    }
-
-    /// Length of the path.
+    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);
+    }
+
+    /// \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.
@@ -101,6 +116,6 @@
     /// 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.
@@ -108,192 +123,278 @@
     /// 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);
+    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.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);
-    }
-
-
-    /* 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
-     *
-     */
+      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 {
+      friend class Path;
+    public:
+
+      /// \brief Default constructor
+      ///
+      /// Default constructor
+      NodeIt() {}
+
+      /// \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;
-
-      int idx;
-      const DirPath *p;
+      friend class Path;
     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;
-      }
-
-      /// 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; }
+      EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
+        if (id >= path->length()) id = -1;
+      }
+
+      /// \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 id == e.id; }
+
+      /// \brief Comparison operator
+      ///
+      /// Comparison operator
+      bool operator!=(const EdgeIt& e) const { return id != e.id; }
+
+      /// \brief Comparison operator
+      ///
+      /// Comparison operator
+      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;
-
-      int idx;
-      const DirPath *p;
+  protected:
+
+    const Graph *graph;
+
+    typedef std::vector<Edge> Container;
+    Container edges;
+    Node start;
+
+  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 Path the original path remains
+    /// unchanged until the commit. However we don't recomend that you
+    /// use this feature.
+    class Builder {
     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(); }
-
-      ///Validity check
-      bool valid() const { return idx!=-1; }
-
-      ///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; }
-    };
-
-    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.
-     */
-    class Builder {
-      DirPath &P;
-      Container front, back;
-
-    public:
-      ///\param _p the path you want to fill in.
-      ///
-      Builder(DirPath &_p) : P(_p) {}
-
-      /// Sets the starting node of the path.
-
+      /// \brief Constructor
+      ///
+      /// Constructor
+      /// \param _path the path you want to fill in.
+      Builder(Path &_path) : path(_path), start(INVALID) {}
+
+      /// \brief Destructor
+      ///
+      /// Destructor
+      ~Builder() {
+        LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 
+                     PathError());
+      }
+
+      /// \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 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) {
+      /// 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;
+      }
+
+      /// \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();
@@ -301,43 +402,23 @@
       }
 
-      ///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;
 
     };
@@ -345,344 +426,4 @@
   };
 
-
-
-
-
-
-
-
-
-
-  /**********************************************************************/
-
-
-  //! \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;
-      }
-
-    };
-
-  };
-
-
   ///@}
 
