//! \brief A structure for representing directed paths in a graph.

   /// \brief A structure for representing directed paths in a graph.

   //!

   ///

   //! A structure for representing directed path in a graph.

   /// A structure for representing directed path in a graph.

   //! \param Graph 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 is has \c NodeIt

   /// In a sense, the path can be treated as a list of edges. The

   //! and \c EdgeIt with the same usage. These types converts to the \c Node

   /// lemon path type stores just this list. As a consequence it

   //! and \c Edge of the original graph.

   /// cannot enumerate the nodes in the path and the zero length paths

   //!

   /// cannot store the source.

   //! \todo Thoroughfully check all the range and consistency tests.

   ///

   template<typename Graph>

   /// This implementation is a back and front insertable and erasable

   /// path type. It can be indexed in O(1) time. The front and back

   /// insertion and erasure is amortized O(1) time. The

   /// impelementation is based on two opposite organized vectors.

   template <typename _Graph>

     /// Edge type of the underlying graph.

     typedef _Graph Graph;

     /// Node type of the underlying graph.

     typedef typename Graph::Node Node;

     /// \brief Default constructor

     ///

     class NodeIt;

     /// Default constructor

     class EdgeIt;

     Path() {}

     struct PathError : public LogicError {

     /// \brief Template copy constructor

       virtual const char* what() const throw() {

     ///

         return "lemon::PathError";

     /// 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) {

   public:

       copyPath(*this, cpath);

     }

     /// \brief Constructor

     ///

     /// \brief Template copy assignment

     /// Constructor 

     ///

     /// \param _G The graph in which the path is.

     /// This path can be initialized with any other path type. It just

     Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}

     /// makes a copy of the given path.

     template <typename CPath>

     /// \brief Subpath constructor.

     Path& operator=(const CPath& cpath) {

     ///

       copyPath(*this, cpath);

     /// Subpath defined by two nodes.

       return *this;

     /// \warning It is an error if the two edges are not in order!

     }

     Path(const Path &other, const NodeIt &a, const NodeIt &b) {

       graph = other.graph; 

     /// \brief Lemon style iterator for path edges

       start = a;

     ///

       edges.insert(edges.end(), 

     /// This class is used to iterate on the edges of the paths.

                    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!

     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(); }

     /// \brief Returns whether the path is empty.

     ///

     /// Returns true when the path does not contain neither edge nor

     /// node.

     bool empty() const { return start == INVALID; }

     /// \brief Resets the path to an empty path.

     ///

     /// Resets the path to an empty path.

     void clear() { edges.clear(); start = INVALID; }

     /// \brief Starting point of the path.

     ///

     /// Starting point of the path.

     /// Returns INVALID if the path is empty.

     Node source() const {

       return start;

     }

     /// \brief End point of the path.

     ///

     /// End point of the path.

     /// Returns INVALID if the path is empty.

     Node target() const {

       return length() == 0 ? start : graph->target(edges[length()-1]);

     }

     /// \brief Gives back a node iterator to point to the node of a

     /// given index.

     ///

     /// Gives back a node iterator to point to the node of a given

     /// index.

     /// \pre n should less or equal to \c length()

     NodeIt nthNode(int n) const {

       return NodeIt(*this, n);

     }

     /// \brief Gives back an edge iterator to point to the edge of a

     /// given index.

     ///

     /// Gives back an edge iterator to point to the node of a given

     /// index.  

     /// \pre n should less than \c length()

     EdgeIt nthEdge(int n) const {

       return EdgeIt(*this, n);

     }

     /// \brief Returns node iterator pointing to the source node of the

     /// given edge iterator.

     ///

     /// Returns node iterator pointing to the source node of the given

     /// edge iterator.

     NodeIt source(const EdgeIt& e) const {

       return NodeIt(*this, e.id);

     }

     /// \brief Returns node iterator pointing to the target node of the

     /// given edge iterator.

     ///

     /// Returns node iterator pointing to the target node of the given

     /// edge iterator.

     NodeIt target(const EdgeIt& e) const {

       return NodeIt(*this, e.id + 1);

     }

     /// \brief Iterator class to iterate on the nodes of the paths

     ///

     /// This class is used to iterate on the nodes of the paths

     ///

     /// Of course it converts to Graph::Node

     class NodeIt {

       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

       ///

       EdgeIt() {}

       /// \brief Invalid constructor

       EdgeIt(Invalid) : path(0), idx(-1) {}

       /// \brief Initializate the constructor to the first edge of path

       EdgeIt(const Path &_path) 

         : path(&_path), idx(_path.empty() ? -1 : 0) {}

     private:

       EdgeIt(const Path &_path, int _idx) 

         : idx(_idx), path(&_path) {}

     public:

       /// \brief Conversion to Edge

       operator const Edge&() const {

         return path->nth(idx);

       }

       /// \brief Next edge

       EdgeIt& operator++() { 

         ++idx;

         if (idx >= path->length()) idx = -1; 

         return *this; 

       }

       /// \brief Comparison operator

       bool operator==(const EdgeIt& e) const { return idx==e.idx; }

       /// \brief Comparison operator

       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }

       /// \brief Comparison operator

       bool operator<(const EdgeIt& 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 edge.

     ///

     /// \pre n is in the [0..length() - 1] range

     const Edge& nth(int n) const {

       return n < (int)head.size() ? *(head.rbegin() + n) :

         *(tail.begin() + (n - head.size()));

     }

     /// \brief Initializes edge iterator to point to the nth edge

     ///

     /// \pre n is in the [0..length() - 1] range

     EdgeIt nthIt(int n) const {

       return EdgeIt(*this, n);

     }

     /// \brief Gives back the first edge of the path

     const Edge& front() const {

       return head.empty() ? tail.front() : head.back();

     }

     /// \brief Add a new edge before the current path

     void addFront(const Edge& edge) {

       head.push_back(edge);

     }

     /// \brief Erase the first edge of the path

     void eraseFront() {

       if (!head.empty()) {

         head.pop_back();

       } else {

         head.clear();

         int halfsize = tail.size() / 2;

         head.resize(halfsize);

         std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,

                   head.rbegin());

         std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());

         tail.resize(tail.size() - halfsize - 1);

       }

     }

     /// \brief Gives back the last edge of the path

     const Edge& back() const {

       return tail.empty() ? head.front() : tail.back();

     }

     /// \brief Add a new edge behind the current path

     void addBack(const Edge& edge) {

       tail.push_back(edge);

     }

     /// \brief Erase the last edge of the path

     void eraseBack() {

       if (!tail.empty()) {

         tail.pop_back();

       } else {

         int halfsize = head.size() / 2;

         tail.resize(halfsize);

         std::copy(head.begin() + 1, head.begin() + halfsize + 1,

                   tail.rbegin());

         std::copy(head.begin() + halfsize + 1, head.end(), head.begin());

         head.resize(head.size() - halfsize - 1);

       }

     }

     typedef True BuildTag;

     template <typename CPath>

     void build(const CPath& path) {

       int len = path.length();

       tail.reserve(len);

       for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {

         tail.push_back(it);

       }

     }

     template <typename CPath>

     void buildRev(const CPath& path) {

       int len = path.length();

       head.reserve(len);

       for (typename CPath::RevIt it(path); it != INVALID; ++it) {

         head.push_back(it);

       }

     }

   protected:

     typedef std::vector<Edge> Container;

     Container head, tail;

   };

   /// \brief A structure for representing directed paths in a graph.

   ///

   /// A structure for representing directed path in a graph.

   /// \param Graph The graph type in which the path is.

   ///

   /// In a sense, the path can be treated as a list of edges. The

   /// lemon path type stores just this list. As a consequence it

   /// cannot enumerate the nodes in the path and the zero length paths

   /// cannot store the source.

   ///

   /// This implementation is a just back insertable and erasable path

   /// type. It can be indexed in O(1) time. The back insertion and

   /// erasure is amortized O(1) time. This implementation is faster

   /// then the \c Path type because it use just one vector for the

   /// edges.

   template <typename _Graph>

   class SimplePath {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Edge Edge;

     /// \brief Default constructor

     ///

     /// Default constructor

     SimplePath() {}

     /// \brief Template copy constructor

     ///

     /// This path can be initialized with any other path type. It just

     /// makes a copy of the given path.

     template <typename CPath>

     SimplePath(const CPath& cpath) {

       copyPath(*this, cpath);

     }

     /// \brief Template copy assignment

     ///

     /// This path can be initialized with any other path type. It just

     /// makes a copy of the given path.

     template <typename CPath>

     SimplePath& operator=(const CPath& cpath) {

       copyPath(*this, cpath);

       return *this;

     }

     /// \brief Iterator class to iterate on the edges of the paths

     ///

     /// This class is used to iterate on the edges of the paths

     ///

     /// Of course it converts to Graph::Edge

     class EdgeIt {

       friend class SimplePath;

     public:

       EdgeIt(Invalid) : id(-1), path(0) {}

       EdgeIt(Invalid) : path(0), idx(-1) {}

       /// \brief Initializate the constructor to the first edge of path

       /// \brief Constructor with starting point

       EdgeIt(const SimplePath &_path) 

       ///

         : path(&_path), idx(_path.empty() ? -1 : 0) {}

     private:

       EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 

       EdgeIt(const SimplePath &_path, int _idx) 

         if (id >= path->length()) id = -1;

         : idx(_idx), path(&_path) {}

       }

     public:

       /// \brief Conversion to Graph::Edge

       ///

       ///Conversion to Graph::Edge

       /// Conversion to Graph::Edge

       operator const Edge&() const {

       operator Edge() const {

         return path->nth(idx);

 	return id != -1 ? path->edges[id] : INVALID;

       }

       }

       /// Next edge

       /// \brief Steps to the next edge

       ///

       /// Steps to the next edge

         ++id; 

         ++idx;

         if (id >= path->length()) id = -1;

         if (idx >= path->length()) idx = -1; 

       bool operator==(const EdgeIt& e) const { return id == e.id; }

       bool operator==(const EdgeIt& e) const { return idx==e.idx; }

       /// \brief Comparison operator

       ///

       bool operator!=(const EdgeIt& e) const { return id != e.id; }

       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }

       /// \brief Comparison operator

       ///

       bool operator<(const EdgeIt& e) const { return id < e.id; }

       bool operator<(const EdgeIt& e) const { return idx<e.idx; }

       const SimplePath *path;

       int id;

       int idx;

       const Path *path;

     Container edges;

     Container data;

     Node start;

   };

   /// \brief A structure for representing directed paths in a graph.

   ///

   /// A structure for representing directed path in a graph.

   /// \param Graph The graph type in which the path is.

   ///

   /// In a sense, the path can be treated as a list of edges. The

   /// lemon path type stores just this list. As a consequence it

   /// cannot enumerate the nodes in the path and the zero length paths

   /// cannot store the source.

   ///

   /// This implementation is a back and front insertable and erasable

   /// path type. It can be indexed in O(k) time, where k is the rank

   /// of the edge in the path. The length can be computed in O(n)

   /// time. The front and back insertion and erasure is O(1) time

   /// and it can be splited and spliced in O(1) time.

   template <typename _Graph>

   class ListPath {

     friend class Builder;

     typedef _Graph Graph;

     typedef typename Graph::Edge Edge;

     /// \brief Class to build paths

     ///

   protected:

     /// This class is used to fill a path with edges.

     ///

     // the std::list<> is incompatible 

     /// You can push new edges to the front and to the back of the

     // hard to create invalid iterator

     /// path in arbitrary order then you should commit these changes

     struct Node {

     /// to the graph.

       Edge edge;

     ///

       Node *next, *prev;

     /// 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

     Node *first, *last;

     /// is in a "transitional" state (operations on it have undefined

     /// result). But in the case of Path the original path remains

     std::allocator<Node> alloc;

     /// unchanged until the commit. However we don't recomend that you

     /// use this feature.

   public:

     class Builder {

     /// \brief Default constructor

     ///

     /// Default constructor

     ListPath() : first(0), last(0) {}

     /// \brief Template copy constructor

     ///

     /// This path can be initialized with any other path type. It just

     /// makes a copy of the given path.

     template <typename CPath>

     ListPath(const CPath& cpath) : first(0), last(0) {

       copyPath(*this, cpath);

     }

     /// \brief Destructor of the path

     ///

     /// Destructor of the path

     ~ListPath() {

       clear();

     }

     /// \brief Template copy assignment

     ///

     /// This path can be initialized with any other path type. It just

     /// makes a copy of the given path.

     template <typename CPath>

     ListPath& operator=(const CPath& cpath) {

       copyPath(*this, cpath);

       return *this;

     }

     /// \brief Iterator class to iterate on the edges of the paths

     ///

     /// This class is used to iterate on the edges of the paths

     ///

     /// Of course it converts to Graph::Edge

     class EdgeIt {

       friend class ListPath;

       /// \brief Constructor

       /// Default constructor

       ///

       EdgeIt() {}

       /// Constructor

       /// Invalid constructor

       /// \param _path the path you want to fill in.

       EdgeIt(Invalid) : path(0), node(0) {}

       Builder(Path &_path) : path(_path), start(INVALID) {}

       /// \brief Initializate the constructor to the first edge of path

       EdgeIt(const ListPath &_path) 

       /// \brief Destructor

         : path(&_path), node(_path.first) {}

       ///

       /// Destructor

     protected:

       ~Builder() {

         LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 

       EdgeIt(const ListPath &_path, Node *_node) 

                      PathError());

         : path(&_path), node(_node) {}

       }

       /// \brief Sets the starting node of the path.

     public:

       ///

       /// Sets the starting node of the path. Edge added to the path

       ///Conversion to Graph::Edge

       /// afterwards have to be incident to this node.  It should be

       operator const Edge&() const {

       /// called if and only if the path is empty and before any call

         return node->edge;

       /// to \ref pushFront() or \ref pushBack()

       }

       void setStartNode(const Node &_start) {

         LEMON_ASSERT(path.empty() && start == INVALID, PathError());

       /// Next edge

         start = _start;

       EdgeIt& operator++() { 

       }

         node = node->next;

         return *this; 

       /// \brief Push a new edge to the front of the path

       }

       ///

       /// Push a new edge to the front of the path.  

       /// Comparison operator

       /// \sa setStartNode

       bool operator==(const EdgeIt& e) const { return node==e.node; }

       void pushFront(const Edge& e) {

       /// Comparison operator

         LEMON_ASSERT(front.empty() || 

       bool operator!=(const EdgeIt& e) const { return node!=e.node; }

                      (path.graph->source(front.back()) == 

       /// Comparison operator

                       path.graph->target(e)), PathError());

       bool operator<(const EdgeIt& e) const { return node<e.node; }

         LEMON_ASSERT(path.empty() || 

                      (path.source() == path.graph->target(e)), PathError());

     private:

         LEMON_ASSERT(!path.empty() || !front.empty() ||

       const ListPath *path;

                      (start == path.graph->target(e)), PathError());

       Node *node;

 	front.push_back(e);

     };

       }

     /// \brief Gives back the nth edge.

       /// \brief Push a new edge to the back of the path

     ///

       ///

     /// Gives back the nth edge in O(n) time.

       /// Push a new edge to the back of the path.

     /// \pre n is in the [0..length() - 1] range

       /// \sa setStartNode

     const Edge& nth(int n) const {

       void pushBack(const Edge& e) {

       Node *node = first;

         LEMON_ASSERT(back.empty() || 

       for (int i = 0; i < n; ++i) {

                      (path.graph->target(back.back()) == 

         node = node->next;

                       path.graph->source(e)), PathError());

       }

         LEMON_ASSERT(path.empty() || 

       return node->edge;

                      (path.target() == path.graph->source(e)), PathError());

     }

         LEMON_ASSERT(!path.empty() || !back.empty() ||

                      (start == path.graph->source(e)), PathError());

     /// \brief Initializes edge iterator to point to the nth edge.

 	back.push_back(e);

     EdgeIt nthIt(int n) const {

       }

       Node *node = first;

       for (int i = 0; i < n; ++i) {

       /// \brief Commit the changes to the path.

         node = node->next;

       ///

       }

       /// Commit the changes to the path.

       return EdgeIt(*this, node);

       void commit() {

     }

 	if( !front.empty() || !back.empty() || start != INVALID) {

 	  Container tmp;

     /// \brief Length of the path.

 	  tmp.reserve(front.size() + back.size() + path.length());

     int length() const {

 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());

       int len = 0;

 	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());

       Node *node = first;

 	  tmp.insert(tmp.end(), back.begin(), back.end());

       while (node != 0) {

 	  path.edges.swap(tmp);

         node = node->next;

           if (!front.empty()) {

         ++len;

             path.start = path.graph->source(front.back());

       }

       return len;

     }

     /// \brief Returns whether the path is empty.

     bool empty() const { return first == 0; }

     /// \brief Resets the path to an empty path.

     void clear() {

       while (first != 0) {

         last = first->next;

         alloc.destroy(first);

         alloc.deallocate(first, 1);

         first = last;

       }

     }

     /// \brief Gives back the first edge of the path

     const Edge& front() const {

       return first->edge;

     }

     /// \brief Add a new edge before the current path

     void addFront(const Edge& edge) {

       Node *node = alloc.allocate(1);

       alloc.construct(node, Node());

       node->prev = 0;

       node->next = first;

       node->edge = edge;

       if (first) {

         first->prev = node;

         first = node;

       } else {

         first = last = node;

       }

     }

     /// \brief Erase the first edge of the path

     void eraseFront() {

       Node *node = first;

       first = first->next;

       if (first) {

         first->prev = 0;

       } else {

         last = 0;

       }

       alloc.destroy(node);

       alloc.deallocate(node, 1);

     }

     /// \brief Gives back the last edge of the path.

     const Edge& back() const {

       return last->edge;

     }

     /// \brief Add a new edge behind the current path.

     void addBack(const Edge& edge) {

       Node *node = alloc.allocate(1);

       alloc.construct(node, Node());

       node->next = 0;

       node->prev = last;

       node->edge = edge;

       if (last) {

         last->next = node;

         last = node;

       } else {

         last = first = node;

       }

     }

     /// \brief Erase the last edge of the path

     void eraseBack() {

       Node *node = last;

       last = last->prev;

       if (last) {

         last->next = 0;

       } else {

         first = 0;

       }

       alloc.destroy(node);

       alloc.deallocate(node, 1);

     }

     /// \brief Splicing the given path to the current path.

     ///

     /// It splices the \c tpath to the back of the current path and \c

     /// tpath becomes empty. The time complexity of this function is

     /// O(1).

     void spliceBack(ListPath& tpath) {

       if (first) {

         if (tpath.first) {

           last->next = tpath.first;

           tpath.first->prev = last;

           last = tpath.last;

         }

       } else {

         first = tpath.first;

         last = tpath.last;

       }

       tpath.first = tpath.last = 0;

     }

     /// \brief Splicing the given path to the current path.

     ///

     /// It splices the \c tpath before the current path and \c tpath

     /// becomes empty. The time complexity of this function

     /// is O(1).

     void spliceFront(ListPath& tpath) {

       if (first) {

         if (tpath.first) {

           first->prev = tpath.last;

           tpath.last->next = first;

           first = tpath.first;

         }

       } else {

         first = tpath.first;

         last = tpath.last;

       }

       tpath.first = tpath.last = 0;

     }

     /// \brief Splicing the given path into the current path.

     ///

     /// It splices the \c tpath into the current path before the

     /// position of \c it iterator and \c tpath becomes empty. The

     /// time complexity of this function is O(1). If the \c it is \c

     /// INVALID then it will splice behind the current path.

     void splice(EdgeIt it, ListPath& tpath) {

       if (it.node) {

         if (tpath.first) {

           tpath.first->prev = it.node->prev;

           if (it.node->prev) {

             it.node->prev->next = tpath.first;

             path.start = start;

             first = tpath.first;

           start = INVALID;

           it.node->prev = tpath.last;

 	  front.clear();

           tpath.last->next = it.node;

 	  back.clear();

         }

 	}

       } else {

       }

         if (first) {

           if (tpath.first) {

       /// \brief Reserve storage for the builder in advance.

             last->next = tpath.first;

       ///

             tpath.first->prev = last;

       /// If you know a reasonable upper bound of the number of the

             last = tpath.last;

       /// edges to add to the front, using this function you can speed

           }

       /// up the building.

         } else {

       void reserveFront(size_t r) {front.reserve(r);}

           first = tpath.first;

           last = tpath.last;

       /// \brief Reserve storage for the builder in advance.

         }

       ///

       }

       /// If you know a reasonable upper bound of the number of the

       tpath.first = tpath.last = 0;

       /// edges to add to the back, using this function you can speed

     }

       /// up the building.

       void reserveBack(size_t r) {back.reserve(r);}

     /// \brief Spliting the current path.

     ///

     /// It splits the current path into two parts. The part before \c

     /// it iterator will remain in the current path and the part from

     /// the it will put into the \c tpath. If the \c tpath had edges

     /// before the operation they will be removed first.  The time

     /// complexity of this function is O(1) plus the clearing of \c

     /// tpath. If the \c it is \c INVALID then it just clears \c

     /// tpath.

     void split(EdgeIt it, ListPath& tpath) {

       tpath.clear();

       if (it.node) {

         tpath.first = it.node;

         tpath.last = last;

         if (it.node->prev) {

           last = it.node->prev;

           last->next = 0;

         } else {

           first = last = 0;

         }

         it.node->prev = 0;

       }

     }

     typedef True BuildTag;

     template <typename CPath>

     void build(const CPath& path) {

       for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {

         addBack(it);

       }

     }

     template <typename CPath>

     void buildRev(const CPath& path) {

       for (typename CPath::RevIt it(path); it != INVALID; ++it) {

         addFront(it);

       }

     }

   };

   /// \brief A structure for representing directed paths in a graph.

   ///

   /// A structure for representing directed path in a graph.

   /// \param Graph The graph type in which the path is.

   ///

   /// In a sense, the path can be treated as a list of edges. The

   /// lemon path type stores just this list. As a consequence it

   /// cannot enumerate the nodes in the path and the zero length paths

   /// cannot store the source.

   ///

   /// This implementation is completly static, so it cannot be

   /// modified exclude the assign an other path. It is intented to be

   /// used when you want to store a large amount paths because it is

   /// the most memory efficient path type in the lemon.

   template <typename _Graph>

   class StaticPath {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Edge Edge;

     /// \brief Default constructor

     ///

     /// Default constructor

     StaticPath() : len(0), edges(0) {}

     /// \brief Template copy constructor

     ///

     /// This path can be initialized with any other path type. It just

     /// makes a copy of the given path.

     template <typename CPath>

     StaticPath(const CPath& cpath) : edges(0) {

       copyPath(*this, cpath);

     }

     /// \brief Destructor of the path

     ///

     /// Destructor of the path

     ~StaticPath() {

       if (edges) delete[] edges;

     }

     /// \brief Template copy assignment

     ///

     /// This path can be initialized with any other path type. It just

     /// makes a copy of the given path.

     template <typename CPath>

     StaticPath& operator=(const CPath& cpath) {

       copyPath(*this, cpath);

       return *this;

     }

     /// \brief Iterator class to iterate on the edges of the paths

     ///

     /// This class is used to iterate on the edges of the paths

     ///

     /// Of course it converts to Graph::Edge

     class EdgeIt {

       friend class StaticPath;

     public:

       /// Default constructor

       EdgeIt() {}

       /// Invalid constructor

       EdgeIt(Invalid) : path(0), idx(-1) {}

       /// Initializate the constructor to the first edge of path

       EdgeIt(const StaticPath &_path) 

         : path(&_path), idx(_path.empty() ? -1 : 0) {}

       Path &path;

       /// Constructor with starting point

       Container front, back;

       EdgeIt(const StaticPath &_path, int _idx) 

       Node start;

         : idx(_idx), path(&_path) {}

     public:

       ///Conversion to Graph::Edge

       operator const Edge&() const {

         return path->nth(idx);

       }

       /// Next edge

       EdgeIt& operator++() { 

         ++idx;

         if (idx >= path->length()) idx = -1; 

         return *this; 

       }

       /// Comparison operator

       bool operator==(const EdgeIt& e) const { return idx==e.idx; }

       /// Comparison operator

       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }

       /// Comparison operator

       bool operator<(const EdgeIt& e) const { return idx<e.idx; }

     private:

       const StaticPath *path;

       int idx;