# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1201174279 0
# Node ID b55e501a90ee50e31c3633507975647029fa1235
# Parent  6ec5dbed8f1896434ffca37a48bd75d60ca0505d
Path related files ported from svn -r3435
but ItemReader/Writer for Path (originally belonging to path_utils.h)
hasn't ported yet.

diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/Makefile.am
--- a/lemon/Makefile.am	Wed Jan 23 16:26:41 2008 +0100
+++ b/lemon/Makefile.am	Thu Jan 24 11:31:19 2008 +0000
@@ -17,6 +17,8 @@
 lemon_HEADERS += \
         lemon/dim2.h \
 	lemon/maps.h \
+	lemon/path.h \
+	lemon/path_utils.h \
         lemon/random.h \
 	lemon/list_graph.h \
         lemon/tolerance.h
@@ -38,4 +40,5 @@
 	lemon/concepts/digraph.h \
 	lemon/concepts/graph.h \
 	lemon/concepts/maps.h \
+	lemon/concepts/path.h \
 	lemon/concepts/graph_components.h
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/concepts/path.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/concepts/path.h	Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,307 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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 concept
+///\file
+///\brief Classes for representing paths in digraphs.
+///
+///\todo Iterators have obsolete style
+
+#ifndef LEMON_CONCEPT_PATH_H
+#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 digraph.
+    ///
+    /// A skeleton structure for representing directed paths in a
+    /// digraph.  
+    /// \param _Digraph The digraph type in which the path is.
+    ///
+    /// In a sense, the path can be treated as a list of arcs. 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 _Digraph>
+    class Path {
+    public:
+
+      /// Type of the underlying digraph.
+      typedef _Digraph Digraph;
+      /// Arc type of the underlying digraph.
+      typedef typename Digraph::Arc Arc;
+
+      class ArcIt;
+
+      /// \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 arcs in the path.
+      int length() const { return 0;}
+
+      /// Returns whether the path is empty.
+      bool empty() const { return true;}
+
+      /// Resets the path to an empty path.
+      void clear() {}
+
+      /// \brief Lemon style iterator for path arcs
+      ///
+      /// This class is used to iterate on the arcs of the paths.
+      class ArcIt {
+      public:
+	/// Default constructor
+	ArcIt() {}
+	/// Invalid constructor
+	ArcIt(Invalid) {}
+	/// Constructor for first arc
+	ArcIt(const Path &) {}
+
+        /// Conversion to Arc
+	operator Arc() const { return INVALID; }
+
+	/// Next arc
+	ArcIt& operator++() {return *this;}
+
+	/// Comparison operator
+	bool operator==(const ArcIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const ArcIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const ArcIt&) const {return false;}
+
+      };
+
+      template <typename _Path>
+      struct Constraints {
+        void constraints() {
+          Path<Digraph> pc;
+          _Path p, pp(pc);
+          int l = p.length();
+          int e = p.empty();
+          p.clear();
+
+          p = pc;
+
+          typename _Path::ArcIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename Digraph::Arc 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 _Digraph, typename _Path, typename RevPathTag = void>
+      struct PathDumperConstraints {
+        void constraints() {
+          int l = p.length();
+          int e = p.empty();
+
+          typename _Path::ArcIt id, i(p);
+
+          ++i;
+          typename _Digraph::Arc ed = i;
+
+          e = (i == INVALID);
+          e = (i != INVALID);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ed);
+        }
+        _Path& p;
+      };
+
+      template <typename _Digraph, typename _Path>
+      struct PathDumperConstraints<
+        _Digraph, _Path, 
+        typename enable_if<typename _Path::RevPathTag, void>::type
+      > {
+        void constraints() {
+          int l = p.length();
+          int e = p.empty();
+
+          typename _Path::RevArcIt id, i(p);
+
+          ++i;
+          typename _Digraph::Arc ed = i;
+
+          e = (i == INVALID);
+          e = (i != INVALID);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          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 arcs 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 arcs 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 _Digraph  The digraph 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 _Digraph>
+    class PathDumper {
+    public:
+
+      /// Type of the underlying digraph.
+      typedef _Digraph Digraph;
+      /// Arc type of the underlying digraph.
+      typedef typename Digraph::Arc Arc;
+
+      /// Length of the path ie. the number of arcs in the path.
+      int length() const { return 0;}
+
+      /// Returns whether the path is empty.
+      bool empty() const { return true;}
+
+      /// \brief Forward or reverse dumping
+      ///
+      /// If the RevPathTag is defined and true then reverse dumping
+      /// is provided in the path dumper. In this case instead of the
+      /// ArcIt the RevArcIt iterator should be implemented in the
+      /// dumper.
+      typedef False RevPathTag;
+
+      /// \brief Lemon style iterator for path arcs
+      ///
+      /// This class is used to iterate on the arcs of the paths.
+      class ArcIt {
+      public:
+	/// Default constructor
+	ArcIt() {}
+	/// Invalid constructor
+	ArcIt(Invalid) {}
+	/// Constructor for first arc
+	ArcIt(const PathDumper&) {}
+
+        /// Conversion to Arc
+	operator Arc() const { return INVALID; }
+
+	/// Next arc
+	ArcIt& operator++() {return *this;}
+
+	/// Comparison operator
+	bool operator==(const ArcIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const ArcIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const ArcIt&) const {return false;}
+
+      };
+
+      /// \brief Lemon style iterator for path arcs
+      ///
+      /// This class is used to iterate on the arcs of the paths in
+      /// reverse direction.
+      class RevArcIt {
+      public:
+	/// Default constructor
+	RevArcIt() {}
+	/// Invalid constructor
+	RevArcIt(Invalid) {}
+	/// Constructor for first arc
+	RevArcIt(const PathDumper &) {}
+
+        /// Conversion to Arc
+	operator Arc() const { return INVALID; }
+
+	/// Next arc
+	RevArcIt& operator++() {return *this;}
+
+	/// Comparison operator
+	bool operator==(const RevArcIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const RevArcIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const RevArcIt&) const {return false;}
+
+      };
+
+      template <typename _Path>
+      struct Constraints {
+        void constraints() {
+          function_requires<_path_bits::
+            PathDumperConstraints<Digraph, _Path> >();
+        }
+      };
+
+    };
+
+
+    ///@}
+  }
+
+} // namespace lemon
+
+#endif // LEMON_CONCEPT_PATH_H
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/path.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/path.h	Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,903 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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 digraphs.
+///
+
+#ifndef LEMON_PATH_H
+#define LEMON_PATH_H
+
+#include <vector>
+#include <algorithm>
+
+#include <lemon/path_utils.h>
+#include <lemon/error.h>
+#include <lemon/bits/invalid.h>
+
+namespace lemon {
+
+  /// \addtogroup paths
+  /// @{
+
+
+  /// \brief A structure for representing directed paths in a digraph.
+  ///
+  /// A structure for representing directed path in a digraph.
+  /// \param Digraph The digraph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of arcs. 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 _Digraph>
+  class Path {
+  public:
+
+    typedef _Digraph Digraph;
+    typedef typename Digraph::Arc Arc;
+
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    Path() {}
+
+    /// \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>
+    Path(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>
+    Path& operator=(const CPath& cpath) {
+      copyPath(*this, cpath);
+      return *this;
+    }
+
+    /// \brief Lemon style iterator for path arcs
+    ///
+    /// This class is used to iterate on the arcs of the paths.
+    class ArcIt {
+      friend class Path;
+    public:
+      /// \brief Default constructor
+      ArcIt() {}
+      /// \brief Invalid constructor
+      ArcIt(Invalid) : path(0), idx(-1) {}
+      /// \brief Initializate the constructor to the first arc of path
+      ArcIt(const Path &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
+
+    private:
+
+      ArcIt(const Path &_path, int _idx) 
+        : path(&_path), idx(_idx) {}
+
+    public:
+
+      /// \brief Conversion to Arc
+      operator const Arc&() const {
+        return path->nth(idx);
+      }
+
+      /// \brief Next arc
+      ArcIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
+        return *this; 
+      }
+
+      /// \brief Comparison operator
+      bool operator==(const ArcIt& e) const { return idx==e.idx; }
+      /// \brief Comparison operator
+      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
+      /// \brief Comparison operator
+      bool operator<(const ArcIt& e) const { return idx<e.idx; }
+
+    private:
+      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 arc.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Arc& nth(int n) const {
+      return n < int(head.size()) ? *(head.rbegin() + n) :
+        *(tail.begin() + (n - head.size()));
+    }
+
+    /// \brief Initializes arc iterator to point to the nth arc
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    ArcIt nthIt(int n) const {
+      return ArcIt(*this, n);
+    }
+
+    /// \brief Gives back the first arc of the path
+    const Arc& front() const {
+      return head.empty() ? tail.front() : head.back();
+    }
+
+    /// \brief Add a new arc before the current path
+    void addFront(const Arc& arc) {
+      head.push_back(arc);
+    }
+
+    /// \brief Erase the first arc 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 arc of the path
+    const Arc& back() const {
+      return tail.empty() ? head.front() : tail.back();
+    }
+
+    /// \brief Add a new arc behind the current path
+    void addBack(const Arc& arc) {
+      tail.push_back(arc);
+    }
+
+    /// \brief Erase the last arc 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::ArcIt 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::RevArcIt it(path); it != INVALID; ++it) {
+        head.push_back(it);
+      }
+    }
+
+  protected:
+    typedef std::vector<Arc> Container;
+    Container head, tail;
+
+  };
+
+  /// \brief A structure for representing directed paths in a digraph.
+  ///
+  /// A structure for representing directed path in a digraph.
+  /// \param Digraph The digraph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of arcs. 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
+  /// arcs.
+  template <typename _Digraph>
+  class SimplePath {
+  public:
+
+    typedef _Digraph Digraph;
+    typedef typename Digraph::Arc Arc;
+
+    /// \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 arcs of the paths
+    ///
+    /// This class is used to iterate on the arcs of the paths
+    ///
+    /// Of course it converts to Digraph::Arc
+    class ArcIt {
+      friend class SimplePath;
+    public:
+      /// Default constructor
+      ArcIt() {}
+      /// Invalid constructor
+      ArcIt(Invalid) : path(0), idx(-1) {}
+      /// \brief Initializate the constructor to the first arc of path
+      ArcIt(const SimplePath &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
+
+    private:
+
+      /// Constructor with starting point
+      ArcIt(const SimplePath &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
+
+    public:
+
+      ///Conversion to Digraph::Arc
+      operator const Arc&() const {
+        return path->nth(idx);
+      }
+
+      /// Next arc
+      ArcIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
+        return *this; 
+      }
+
+      /// Comparison operator
+      bool operator==(const ArcIt& e) const { return idx==e.idx; }
+      /// Comparison operator
+      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
+      /// Comparison operator
+      bool operator<(const ArcIt& e) const { return idx<e.idx; }
+
+    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 arc.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Arc& nth(int n) const {
+      return data[n];
+    }
+
+    /// \brief  Initializes arc iterator to point to the nth arc.
+    ArcIt nthIt(int n) const {
+      return ArcIt(*this, n);
+    }
+
+    /// \brief Gives back the first arc of the path.
+    const Arc& front() const {
+      return data.front();
+    }
+
+    /// \brief Gives back the last arc of the path.
+    const Arc& back() const {
+      return data.back();
+    }
+
+    /// \brief Add a new arc behind the current path.
+    void addBack(const Arc& arc) {
+      data.push_back(arc);
+    }
+
+    /// \brief Erase the last arc 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::ArcIt 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::RevArcIt it(path); it != INVALID; ++it) {
+        --index;
+        data[index] = it;;
+      }
+    }
+
+  protected:
+    typedef std::vector<Arc> Container;
+    Container data;
+
+  };
+
+  /// \brief A structure for representing directed paths in a digraph.
+  ///
+  /// A structure for representing directed path in a digraph.
+  /// \param Digraph The digraph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of arcs. 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 arc 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 _Digraph>
+  class ListPath {
+  public:
+
+    typedef _Digraph Digraph;
+    typedef typename Digraph::Arc Arc;
+
+  protected:
+
+    // the std::list<> is incompatible 
+    // hard to create invalid iterator
+    struct Node {
+      Arc arc;
+      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 arcs of the paths
+    ///
+    /// This class is used to iterate on the arcs of the paths
+    ///
+    /// Of course it converts to Digraph::Arc
+    class ArcIt {
+      friend class ListPath;
+    public:
+      /// Default constructor
+      ArcIt() {}
+      /// Invalid constructor
+      ArcIt(Invalid) : path(0), node(0) {}
+      /// \brief Initializate the constructor to the first arc of path
+      ArcIt(const ListPath &_path) 
+        : path(&_path), node(_path.first) {}
+
+    protected:
+
+      ArcIt(const ListPath &_path, Node *_node) 
+        : path(&_path), node(_node) {}
+
+
+    public:
+
+      ///Conversion to Digraph::Arc
+      operator const Arc&() const {
+        return node->arc;
+      }
+
+      /// Next arc
+      ArcIt& operator++() { 
+        node = node->next;
+        return *this; 
+      }
+
+      /// Comparison operator
+      bool operator==(const ArcIt& e) const { return node==e.node; }
+      /// Comparison operator
+      bool operator!=(const ArcIt& e) const { return node!=e.node; }
+      /// Comparison operator
+      bool operator<(const ArcIt& e) const { return node<e.node; }
+
+    private:
+      const ListPath *path;
+      Node *node;
+    };
+
+    /// \brief Gives back the nth arc.
+    ///
+    /// Gives back the nth arc in O(n) time.
+    /// \pre n is in the [0..length() - 1] range
+    const Arc& nth(int n) const {
+      Node *node = first;
+      for (int i = 0; i < n; ++i) {
+        node = node->next;
+      }
+      return node->arc;
+    }
+
+    /// \brief Initializes arc iterator to point to the nth arc.
+    ArcIt nthIt(int n) const {
+      Node *node = first;
+      for (int i = 0; i < n; ++i) {
+        node = node->next;
+      }
+      return ArcIt(*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 arc of the path
+    const Arc& front() const {
+      return first->arc;
+    }
+
+    /// \brief Add a new arc before the current path
+    void addFront(const Arc& arc) {
+      Node *node = alloc.allocate(1);
+      alloc.construct(node, Node());
+      node->prev = 0;
+      node->next = first;
+      node->arc = arc;
+      if (first) {
+        first->prev = node;
+        first = node;
+      } else {
+        first = last = node;
+      }
+    }
+
+    /// \brief Erase the first arc 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 arc of the path.
+    const Arc& back() const {
+      return last->arc;
+    }
+
+    /// \brief Add a new arc behind the current path.
+    void addBack(const Arc& arc) {
+      Node *node = alloc.allocate(1);
+      alloc.construct(node, Node());
+      node->next = 0;
+      node->prev = last;
+      node->arc = arc;
+      if (last) {
+        last->next = node;
+        last = node;
+      } else {
+        last = first = node;
+      }
+    }
+
+    /// \brief Erase the last arc 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(ArcIt 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 arcs
+    /// 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(ArcIt 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::ArcIt it(path); it != INVALID; ++it) {
+        addBack(it);
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
+        addFront(it);
+      }
+    }
+
+  };
+
+  /// \brief A structure for representing directed paths in a digraph.
+  ///
+  /// A structure for representing directed path in a digraph.
+  /// \param Digraph The digraph type in which the path is.
+  ///
+  /// In a sense, the path can be treated as a list of arcs. 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 number of paths because it is
+  /// the most memory efficient path type in the lemon.
+  template <typename _Digraph>
+  class StaticPath {
+  public:
+
+    typedef _Digraph Digraph;
+    typedef typename Digraph::Arc Arc;
+
+    /// \brief Default constructor
+    ///
+    /// Default constructor
+    StaticPath() : len(0), arcs(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) : arcs(0) {
+      copyPath(*this, cpath);
+    }
+
+    /// \brief Destructor of the path
+    ///
+    /// Destructor of the path
+    ~StaticPath() {
+      if (arcs) delete[] arcs;
+    }
+
+    /// \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 arcs of the paths
+    ///
+    /// This class is used to iterate on the arcs of the paths
+    ///
+    /// Of course it converts to Digraph::Arc
+    class ArcIt {
+      friend class StaticPath;
+    public:
+      /// Default constructor
+      ArcIt() {}
+      /// Invalid constructor
+      ArcIt(Invalid) : path(0), idx(-1) {}
+      /// Initializate the constructor to the first arc of path
+      ArcIt(const StaticPath &_path) 
+        : path(&_path), idx(_path.empty() ? -1 : 0) {}
+
+    private:
+
+      /// Constructor with starting point
+      ArcIt(const StaticPath &_path, int _idx) 
+        : idx(_idx), path(&_path) {}
+
+    public:
+
+      ///Conversion to Digraph::Arc
+      operator const Arc&() const {
+        return path->nth(idx);
+      }
+
+      /// Next arc
+      ArcIt& operator++() { 
+        ++idx;
+        if (idx >= path->length()) idx = -1; 
+        return *this; 
+      }
+
+      /// Comparison operator
+      bool operator==(const ArcIt& e) const { return idx==e.idx; }
+      /// Comparison operator
+      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
+      /// Comparison operator
+      bool operator<(const ArcIt& e) const { return idx<e.idx; }
+
+    private:
+      const StaticPath *path;
+      int idx;
+    };
+
+    /// \brief Gives back the nth arc.
+    ///
+    /// \pre n is in the [0..length() - 1] range
+    const Arc& nth(int n) const {
+      return arcs[n];
+    }
+
+    /// \brief Initializes arc iterator to point to the nth arc.
+    ArcIt nthIt(int n) const {
+      return ArcIt(*this, n);
+    }
+
+    /// \brief Gives back the length of the path.
+    int length() const { return len; }
+
+    /// \brief Returns true when the path is empty.
+    int empty() const { return len == 0; }
+
+    /// \break Erase all arc in the digraph.
+    void clear() {
+      len = 0;
+      if (arcs) delete[] arcs;
+      arcs = 0;
+    }
+
+    /// \brief Gives back the first arc of the path.
+    const Arc& front() const {
+      return arcs[0];
+    }
+
+    /// \brief Gives back the last arc of the path.
+    const Arc& back() const {
+      return arcs[len - 1];
+    }
+
+
+    typedef True BuildTag;
+
+    template <typename CPath>
+    void build(const CPath& path) {
+      len = path.length();
+      arcs = new Arc[len];
+      int index = 0;
+      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
+        arcs[index] = it;
+        ++index;
+      }
+    }
+
+    template <typename CPath>
+    void buildRev(const CPath& path) {
+      len = path.length();
+      arcs = new Arc[len];
+      int index = len;
+      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
+        --index;
+        arcs[index] = it;
+      }
+    }
+
+  private:
+    int len;
+    Arc* arcs;
+  };
+
+  ///@}
+
+} // namespace lemon
+
+#endif // LEMON_PATH_H
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/path_utils.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/path_utils.h	Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,204 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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 digraphs.
+///
+
+#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 Digraph>
+    struct RevTagIndicator<
+      Digraph, 
+      typename enable_if<typename Digraph::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) {
+        target.clear();
+        for (typename Source::ArcIt 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) {
+        target.clear();
+        for (typename Source::RevArcIt 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::Digraph>, Source>();
+    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
+  }
+
+  /// \brief Checks the path's consistency.
+  ///
+  /// Checks that each arc's target is the next's source. 
+  /// 
+  template <typename Digraph, typename Path>
+  bool checkPath(const Digraph& digraph, const Path& path) {
+    typename Path::ArcIt it(path);
+    if (it == INVALID) return true;
+    typename Digraph::Node node = digraph.target(it);
+    ++it;
+    while (it != INVALID) {
+      if (digraph.source(it) != node) return false;
+      node = digraph.target(it);
+      ++it;
+    }
+    return true;
+  }
+
+  /// \brief Gives back the source of the path
+  ///
+  /// Gives back the source of the path.
+  template <typename Digraph, typename Path>
+  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
+    return digraph.source(path.front());
+  }
+
+  /// \brief Gives back the target of the path
+  ///
+  /// Gives back the target of the path.
+  template <typename Digraph, typename Path>
+  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
+    return digraph.target(path.back());
+  }
+
+  /// \brief Class which helps to iterate the nodes of a path
+  ///
+  /// In a sense, the path can be treated as a list of arcs. 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 node.
+  ///
+  /// This class implements the node iterator of a path structure. To
+  /// provide this feature, the underlying digraph should be given to
+  /// the constructor of the iterator.
+  template <typename Path>
+  class PathNodeIt {
+  private:
+    const typename Path::Digraph *_digraph;
+    typename Path::ArcIt _it;
+    typename Path::Digraph::Node _nd;
+
+  public:
+
+    typedef typename Path::Digraph Digraph;
+    typedef typename Digraph::Node Node;
+    
+    /// Default constructor
+    PathNodeIt() {}
+    /// Invalid constructor
+    PathNodeIt(Invalid) 
+      : _digraph(0), _it(INVALID), _nd(INVALID) {}
+    /// Constructor
+    PathNodeIt(const Digraph& digraph, const Path& path) 
+      : _digraph(&digraph), _it(path) {
+      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
+    }
+    /// Constructor
+    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) 
+      : _digraph(&digraph), _it(path), _nd(src) {}
+
+    ///Conversion to Digraph::Node
+    operator Node() const {
+      return _nd;
+    }
+
+    /// Next node
+    PathNodeIt& operator++() {
+      if (_it == INVALID) _nd = INVALID;
+      else {
+	_nd = _digraph->target(_it);
+	++_it;
+      }
+      return *this;
+    }
+
+    /// Comparison operator
+    bool operator==(const PathNodeIt& n) const { 
+      return _it == n._it && _nd == n._nd; 
+    }
+    /// Comparison operator
+    bool operator!=(const PathNodeIt& n) const { 
+      return _it != n._it || _nd != n._nd; 
+    }
+    /// Comparison operator
+    bool operator<(const PathNodeIt& n) const { 
+      return (_it < n._it && _nd != INVALID);
+    }
+    
+  };
+  
+}
+
+#endif
diff -r 6ec5dbed8f18 -r b55e501a90ee test/Makefile.am
--- a/test/Makefile.am	Wed Jan 23 16:26:41 2008 +0100
+++ b/test/Makefile.am	Thu Jan 24 11:31:19 2008 +0000
@@ -11,6 +11,7 @@
         test/dim_test \
 	test/graph_test \
         test/random_test \
+        test/path_test \
         test/test_tools_fail \
         test/test_tools_pass
 
@@ -20,6 +21,7 @@
 test_digraph_test_SOURCES = test/digraph_test.cc
 test_dim_test_SOURCES = test/dim_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
+test_path_test_SOURCES = test/path_test.cc
 test_random_test_SOURCES = test/random_test.cc
 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
diff -r 6ec5dbed8f18 -r b55e501a90ee test/path_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/path_test.cc	Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,44 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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.
+ *
+ */
+
+#include <string>
+#include <iostream>
+
+#include <lemon/concepts/path.h>
+#include <lemon/concepts/digraph.h>
+
+#include <lemon/path.h>
+#include <lemon/list_graph.h>
+
+#include "test_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+void check_concepts() {
+  checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
+}
+
+int main() {
+  check_concepts();  
+  return 0;
+}