alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@96: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@96: * alpar@1092: * Copyright (C) 2003-2013 alpar@96: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@96: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@96: * alpar@96: * Permission to use, modify and distribute this software is granted alpar@96: * provided that this copyright notice appears in all copies. For alpar@96: * precise terms see the accompanying LICENSE file. alpar@96: * alpar@96: * This software is provided "AS IS" with no warranty of any kind, alpar@96: * express or implied, and with no claim as to its suitability for any alpar@96: * purpose. alpar@96: * alpar@96: */ alpar@96: alpar@96: ///\ingroup paths alpar@96: ///\file alpar@96: ///\brief Classes for representing paths in digraphs. alpar@96: /// alpar@96: alpar@96: #ifndef LEMON_PATH_H alpar@96: #define LEMON_PATH_H alpar@96: alpar@96: #include alpar@96: #include alpar@96: alpar@96: #include deba@220: #include alpar@100: #include ggab90@1130: #include alpar@96: alpar@96: namespace lemon { alpar@96: alpar@96: /// \addtogroup paths alpar@96: /// @{ alpar@96: alpar@96: alpar@96: /// \brief A structure for representing directed paths in a digraph. alpar@96: /// alpar@96: /// A structure for representing directed path in a digraph. kpeter@559: /// \tparam GR The digraph type in which the path is. alpar@96: /// kpeter@1201: /// In a sense, a path can be treated as a list of arcs. The kpeter@1201: /// LEMON path type simply stores this list. As a consequence, it kpeter@1201: /// cannot enumerate the nodes in the path, and the source node of kpeter@1201: /// a zero-length path is undefined. alpar@96: /// alpar@96: /// This implementation is a back and front insertable and erasable alpar@96: /// path type. It can be indexed in O(1) time. The front and back alpar@97: /// insertion and erase is done in O(1) (amortized) time. The alpar@97: /// implementation uses two vectors for storing the front and back alpar@97: /// insertions. kpeter@559: template alpar@96: class Path { alpar@96: public: alpar@96: kpeter@559: typedef GR Digraph; alpar@96: typedef typename Digraph::Arc Arc; alpar@96: alpar@96: /// \brief Default constructor alpar@96: /// alpar@96: /// Default constructor alpar@96: Path() {} alpar@96: alpar@990: /// \brief Copy constructor alpar@990: /// alpar@990: Path(const Path& cpath) { alpar@990: pathCopy(cpath, *this); alpar@990: } alpar@990: alpar@96: /// \brief Template copy constructor alpar@96: /// alpar@97: /// This constuctor initializes the path from any other path type. alpar@97: /// It simply makes a copy of the given path. alpar@96: template alpar@96: Path(const CPath& cpath) { kpeter@516: pathCopy(cpath, *this); alpar@96: } alpar@96: alpar@990: /// \brief Copy assignment alpar@990: /// alpar@990: Path& operator=(const Path& cpath) { alpar@990: pathCopy(cpath, *this); alpar@990: return *this; alpar@990: } alpar@990: alpar@96: /// \brief Template copy assignment alpar@96: /// alpar@97: /// This operator makes a copy of a path of any other type. alpar@96: template alpar@96: Path& operator=(const CPath& cpath) { kpeter@516: pathCopy(cpath, *this); alpar@96: return *this; alpar@96: } alpar@96: ladanyi@236: /// \brief LEMON style iterator for path arcs alpar@96: /// alpar@96: /// This class is used to iterate on the arcs of the paths. alpar@96: class ArcIt { alpar@96: friend class Path; alpar@96: public: alpar@96: /// \brief Default constructor alpar@96: ArcIt() {} alpar@96: /// \brief Invalid constructor alpar@96: ArcIt(Invalid) : path(0), idx(-1) {} alpar@97: /// \brief Initializate the iterator to the first arc of path alpar@209: ArcIt(const Path &_path) alpar@96: : path(&_path), idx(_path.empty() ? -1 : 0) {} alpar@96: alpar@96: private: alpar@96: alpar@209: ArcIt(const Path &_path, int _idx) alpar@96: : path(&_path), idx(_idx) {} alpar@96: alpar@96: public: alpar@96: alpar@96: /// \brief Conversion to Arc alpar@96: operator const Arc&() const { alpar@96: return path->nth(idx); alpar@96: } alpar@96: alpar@96: /// \brief Next arc alpar@209: ArcIt& operator++() { alpar@96: ++idx; alpar@209: if (idx >= path->length()) idx = -1; alpar@209: return *this; alpar@96: } alpar@96: alpar@96: /// \brief Comparison operator alpar@96: bool operator==(const ArcIt& e) const { return idx==e.idx; } alpar@96: /// \brief Comparison operator alpar@96: bool operator!=(const ArcIt& e) const { return idx!=e.idx; } alpar@96: /// \brief Comparison operator alpar@96: bool operator<(const ArcIt& e) const { return idx arcs() const { ggab90@1130: return LemonRangeWrapper1(*this); ggab90@1130: } ggab90@1130: ggab90@1130: alpar@96: /// \brief Length of the path. alpar@96: int length() const { return head.size() + tail.size(); } alpar@97: /// \brief Return whether the path is empty. alpar@96: bool empty() const { return head.empty() && tail.empty(); } alpar@96: alpar@97: /// \brief Reset the path to an empty one. alpar@96: void clear() { head.clear(); tail.clear(); } alpar@96: kpeter@920: /// \brief The n-th arc. alpar@96: /// kpeter@1201: /// Gives back the n-th arc. This function runs in O(1) time. kpeter@1201: /// \pre \c n is in the range [0..length() - 1]. alpar@96: const Arc& nth(int n) const { alpar@96: return n < int(head.size()) ? *(head.rbegin() + n) : alpar@96: *(tail.begin() + (n - head.size())); alpar@96: } alpar@96: kpeter@920: /// \brief Initialize arc iterator to point to the n-th arc alpar@96: /// kpeter@559: /// \pre \c n is in the [0..length() - 1] range. alpar@96: ArcIt nthIt(int n) const { alpar@96: return ArcIt(*this, n); alpar@96: } alpar@96: kpeter@1202: /// \brief The n-th arc. kpeter@1202: /// kpeter@1202: /// Gives back the n-th arc. This operator is just an alias for \ref nth(), kpeter@1202: /// it runs in O(1) time. kpeter@1202: /// \pre \c n is in the range [0..length() - 1]. kpeter@1202: const Arc& operator[](int n) const { kpeter@1202: return nth(n); kpeter@1202: } kpeter@1202: alpar@97: /// \brief The first arc of the path alpar@96: const Arc& front() const { alpar@96: return head.empty() ? tail.front() : head.back(); alpar@96: } alpar@96: alpar@96: /// \brief Add a new arc before the current path alpar@96: void addFront(const Arc& arc) { alpar@96: head.push_back(arc); alpar@96: } alpar@96: alpar@96: /// \brief Erase the first arc of the path alpar@96: void eraseFront() { alpar@96: if (!head.empty()) { alpar@96: head.pop_back(); alpar@96: } else { alpar@96: head.clear(); alpar@96: int halfsize = tail.size() / 2; alpar@96: head.resize(halfsize); alpar@96: std::copy(tail.begin() + 1, tail.begin() + halfsize + 1, alpar@96: head.rbegin()); alpar@96: std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin()); alpar@96: tail.resize(tail.size() - halfsize - 1); alpar@96: } alpar@96: } alpar@96: alpar@97: /// \brief The last arc of the path alpar@96: const Arc& back() const { alpar@96: return tail.empty() ? head.front() : tail.back(); alpar@96: } alpar@96: alpar@96: /// \brief Add a new arc behind the current path alpar@96: void addBack(const Arc& arc) { alpar@96: tail.push_back(arc); alpar@96: } alpar@96: alpar@96: /// \brief Erase the last arc of the path alpar@96: void eraseBack() { alpar@96: if (!tail.empty()) { alpar@96: tail.pop_back(); alpar@96: } else { alpar@96: int halfsize = head.size() / 2; alpar@96: tail.resize(halfsize); alpar@96: std::copy(head.begin() + 1, head.begin() + halfsize + 1, alpar@96: tail.rbegin()); alpar@96: std::copy(head.begin() + halfsize + 1, head.end(), head.begin()); alpar@96: head.resize(head.size() - halfsize - 1); alpar@96: } alpar@96: } alpar@96: alpar@96: typedef True BuildTag; alpar@96: alpar@96: template alpar@96: void build(const CPath& path) { alpar@96: int len = path.length(); alpar@96: tail.reserve(len); alpar@96: for (typename CPath::ArcIt it(path); it != INVALID; ++it) { alpar@96: tail.push_back(it); alpar@96: } alpar@96: } alpar@96: alpar@96: template alpar@96: void buildRev(const CPath& path) { alpar@96: int len = path.length(); alpar@96: head.reserve(len); alpar@96: for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { alpar@96: head.push_back(it); alpar@96: } alpar@96: } alpar@96: alpar@96: protected: alpar@96: typedef std::vector Container; alpar@96: Container head, tail; alpar@96: alpar@96: }; alpar@96: alpar@96: /// \brief A structure for representing directed paths in a digraph. alpar@96: /// alpar@96: /// A structure for representing directed path in a digraph. kpeter@559: /// \tparam GR The digraph type in which the path is. alpar@96: /// kpeter@1201: /// In a sense, a path can be treated as a list of arcs. The kpeter@1201: /// LEMON path type simply stores this list. As a consequence, it kpeter@1201: /// cannot enumerate the nodes in the path, and the source node of kpeter@1201: /// a zero-length path is undefined. alpar@96: /// alpar@96: /// This implementation is a just back insertable and erasable path alpar@96: /// type. It can be indexed in O(1) time. The back insertion and alpar@96: /// erasure is amortized O(1) time. This implementation is faster kpeter@1201: /// than the \c Path type because it use just one vector for the alpar@96: /// arcs. kpeter@559: template alpar@96: class SimplePath { alpar@96: public: alpar@96: kpeter@559: typedef GR Digraph; alpar@96: typedef typename Digraph::Arc Arc; alpar@96: alpar@96: /// \brief Default constructor alpar@96: /// alpar@96: /// Default constructor alpar@96: SimplePath() {} alpar@96: alpar@990: /// \brief Copy constructor alpar@990: /// alpar@990: SimplePath(const SimplePath& cpath) { alpar@990: pathCopy(cpath, *this); alpar@990: } alpar@990: alpar@96: /// \brief Template copy constructor alpar@96: /// alpar@96: /// This path can be initialized with any other path type. It just alpar@96: /// makes a copy of the given path. alpar@96: template alpar@96: SimplePath(const CPath& cpath) { kpeter@516: pathCopy(cpath, *this); alpar@96: } alpar@96: alpar@990: /// \brief Copy assignment alpar@990: /// alpar@990: SimplePath& operator=(const SimplePath& cpath) { alpar@990: pathCopy(cpath, *this); alpar@990: return *this; alpar@990: } alpar@990: alpar@96: /// \brief Template copy assignment alpar@96: /// alpar@96: /// This path can be initialized with any other path type. It just alpar@96: /// makes a copy of the given path. alpar@96: template alpar@96: SimplePath& operator=(const CPath& cpath) { kpeter@516: pathCopy(cpath, *this); alpar@96: return *this; alpar@96: } alpar@96: alpar@96: /// \brief Iterator class to iterate on the arcs of the paths alpar@96: /// alpar@96: /// This class is used to iterate on the arcs of the paths alpar@96: /// alpar@96: /// Of course it converts to Digraph::Arc alpar@96: class ArcIt { alpar@96: friend class SimplePath; alpar@96: public: alpar@96: /// Default constructor alpar@96: ArcIt() {} alpar@96: /// Invalid constructor alpar@96: ArcIt(Invalid) : path(0), idx(-1) {} alpar@96: /// \brief Initializate the constructor to the first arc of path alpar@209: ArcIt(const SimplePath &_path) alpar@96: : path(&_path), idx(_path.empty() ? -1 : 0) {} alpar@96: alpar@96: private: alpar@96: alpar@96: /// Constructor with starting point alpar@209: ArcIt(const SimplePath &_path, int _idx) kpeter@1044: : path(&_path), idx(_idx) {} alpar@96: alpar@96: public: alpar@96: alpar@96: ///Conversion to Digraph::Arc alpar@96: operator const Arc&() const { alpar@96: return path->nth(idx); alpar@96: } alpar@96: alpar@96: /// Next arc alpar@209: ArcIt& operator++() { alpar@96: ++idx; alpar@209: if (idx >= path->length()) idx = -1; alpar@209: return *this; alpar@96: } alpar@96: alpar@96: /// Comparison operator alpar@96: bool operator==(const ArcIt& e) const { return idx==e.idx; } alpar@96: /// Comparison operator alpar@96: bool operator!=(const ArcIt& e) const { return idx!=e.idx; } alpar@96: /// Comparison operator alpar@96: bool operator<(const ArcIt& e) const { return idx arcs() const { ggab90@1130: return LemonRangeWrapper1(*this); ggab90@1130: } ggab90@1130: ggab90@1130: alpar@96: /// \brief Length of the path. alpar@96: int length() const { return data.size(); } alpar@97: /// \brief Return true if the path is empty. alpar@96: bool empty() const { return data.empty(); } alpar@96: alpar@97: /// \brief Reset the path to an empty one. alpar@96: void clear() { data.clear(); } alpar@96: kpeter@920: /// \brief The n-th arc. alpar@96: /// kpeter@1201: /// Gives back the n-th arc. This function runs in O(1) time. kpeter@1201: /// \pre \c n is in the range [0..length() - 1]. alpar@96: const Arc& nth(int n) const { alpar@96: return data[n]; alpar@96: } alpar@96: kpeter@920: /// \brief Initializes arc iterator to point to the n-th arc. alpar@96: ArcIt nthIt(int n) const { alpar@96: return ArcIt(*this, n); alpar@96: } alpar@96: kpeter@1202: /// \brief The n-th arc. kpeter@1202: /// kpeter@1202: /// Gives back the n-th arc. This operator is just an alias for \ref nth(), kpeter@1202: /// it runs in O(1) time. kpeter@1202: /// \pre \c n is in the range [0..length() - 1]. kpeter@1202: const Arc& operator[](int n) const { kpeter@1202: return data[n]; kpeter@1202: } kpeter@1202: alpar@97: /// \brief The first arc of the path. alpar@96: const Arc& front() const { alpar@96: return data.front(); alpar@96: } alpar@96: alpar@97: /// \brief The last arc of the path. alpar@96: const Arc& back() const { alpar@96: return data.back(); alpar@96: } alpar@96: alpar@96: /// \brief Add a new arc behind the current path. alpar@96: void addBack(const Arc& arc) { alpar@96: data.push_back(arc); alpar@96: } alpar@96: alpar@96: /// \brief Erase the last arc of the path alpar@96: void eraseBack() { alpar@96: data.pop_back(); alpar@96: } alpar@96: alpar@96: typedef True BuildTag; alpar@96: alpar@96: template alpar@96: void build(const CPath& path) { alpar@96: int len = path.length(); alpar@96: data.resize(len); alpar@96: int index = 0; alpar@96: for (typename CPath::ArcIt it(path); it != INVALID; ++it) { alpar@96: data[index] = it;; alpar@96: ++index; alpar@96: } alpar@96: } alpar@96: alpar@96: template alpar@96: void buildRev(const CPath& path) { alpar@96: int len = path.length(); alpar@96: data.resize(len); alpar@96: int index = len; alpar@96: for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { alpar@96: --index; alpar@96: data[index] = it;; alpar@96: } alpar@96: } alpar@96: alpar@96: protected: alpar@96: typedef std::vector Container; alpar@96: Container data; alpar@96: alpar@96: }; alpar@96: alpar@96: /// \brief A structure for representing directed paths in a digraph. alpar@96: /// alpar@96: /// A structure for representing directed path in a digraph. kpeter@559: /// \tparam GR The digraph type in which the path is. alpar@96: /// kpeter@1201: /// In a sense, a path can be treated as a list of arcs. The kpeter@1201: /// LEMON path type simply stores this list. As a consequence, it kpeter@1201: /// cannot enumerate the nodes in the path, and the source node of kpeter@1201: /// a zero-length path is undefined. alpar@96: /// alpar@96: /// This implementation is a back and front insertable and erasable alpar@96: /// path type. It can be indexed in O(k) time, where k is the rank alpar@96: /// of the arc in the path. The length can be computed in O(n) alpar@96: /// time. The front and back insertion and erasure is O(1) time alpar@96: /// and it can be splited and spliced in O(1) time. kpeter@559: template alpar@96: class ListPath { alpar@96: public: alpar@96: kpeter@559: typedef GR Digraph; alpar@96: typedef typename Digraph::Arc Arc; alpar@96: alpar@96: protected: alpar@96: alpar@209: // the std::list<> is incompatible alpar@96: // hard to create invalid iterator alpar@96: struct Node { alpar@96: Arc arc; alpar@96: Node *next, *prev; alpar@96: }; alpar@96: alpar@96: Node *first, *last; alpar@96: alpar@96: std::allocator alloc; alpar@96: alpar@96: public: alpar@209: alpar@96: /// \brief Default constructor alpar@96: /// alpar@96: /// Default constructor alpar@96: ListPath() : first(0), last(0) {} alpar@96: alpar@990: /// \brief Copy constructor alpar@990: /// alpar@990: ListPath(const ListPath& cpath) : first(0), last(0) { alpar@990: pathCopy(cpath, *this); alpar@990: } alpar@990: alpar@96: /// \brief Template copy constructor alpar@96: /// alpar@96: /// This path can be initialized with any other path type. It just alpar@96: /// makes a copy of the given path. alpar@96: template alpar@96: ListPath(const CPath& cpath) : first(0), last(0) { kpeter@516: pathCopy(cpath, *this); alpar@96: } alpar@96: alpar@96: /// \brief Destructor of the path alpar@96: /// alpar@96: /// Destructor of the path alpar@96: ~ListPath() { alpar@96: clear(); alpar@96: } alpar@96: alpar@990: /// \brief Copy assignment alpar@990: /// alpar@990: ListPath& operator=(const ListPath& cpath) { alpar@990: pathCopy(cpath, *this); alpar@990: return *this; alpar@990: } alpar@990: alpar@96: /// \brief Template copy assignment alpar@96: /// alpar@96: /// This path can be initialized with any other path type. It just alpar@96: /// makes a copy of the given path. alpar@96: template alpar@96: ListPath& operator=(const CPath& cpath) { kpeter@516: pathCopy(cpath, *this); alpar@96: return *this; alpar@96: } alpar@96: alpar@96: /// \brief Iterator class to iterate on the arcs of the paths alpar@96: /// alpar@96: /// This class is used to iterate on the arcs of the paths alpar@96: /// alpar@96: /// Of course it converts to Digraph::Arc alpar@96: class ArcIt { alpar@96: friend class ListPath; alpar@96: public: alpar@96: /// Default constructor alpar@96: ArcIt() {} alpar@96: /// Invalid constructor alpar@96: ArcIt(Invalid) : path(0), node(0) {} alpar@96: /// \brief Initializate the constructor to the first arc of path alpar@209: ArcIt(const ListPath &_path) alpar@96: : path(&_path), node(_path.first) {} alpar@96: alpar@96: protected: alpar@96: alpar@209: ArcIt(const ListPath &_path, Node *_node) alpar@96: : path(&_path), node(_node) {} alpar@96: alpar@96: alpar@96: public: alpar@96: alpar@96: ///Conversion to Digraph::Arc alpar@96: operator const Arc&() const { alpar@96: return node->arc; alpar@96: } alpar@96: alpar@96: /// Next arc alpar@209: ArcIt& operator++() { alpar@96: node = node->next; alpar@209: return *this; alpar@96: } alpar@96: alpar@96: /// Comparison operator alpar@96: bool operator==(const ArcIt& e) const { return node==e.node; } alpar@96: /// Comparison operator alpar@96: bool operator!=(const ArcIt& e) const { return node!=e.node; } alpar@96: /// Comparison operator alpar@96: bool operator<(const ArcIt& e) const { return node arcs() const { ggab90@1130: return LemonRangeWrapper1(*this); ggab90@1130: } ggab90@1130: ggab90@1130: kpeter@920: /// \brief The n-th arc. alpar@96: /// kpeter@920: /// This function looks for the n-th arc in O(n) time. kpeter@1201: /// \pre \c n is in the range [0..length() - 1]. alpar@96: const Arc& nth(int n) const { alpar@96: Node *node = first; alpar@96: for (int i = 0; i < n; ++i) { alpar@96: node = node->next; alpar@96: } alpar@96: return node->arc; alpar@96: } alpar@96: kpeter@920: /// \brief Initializes arc iterator to point to the n-th arc. alpar@96: ArcIt nthIt(int n) const { alpar@96: Node *node = first; alpar@96: for (int i = 0; i < n; ++i) { alpar@96: node = node->next; alpar@96: } alpar@96: return ArcIt(*this, node); alpar@96: } alpar@96: kpeter@1202: /// \brief The n-th arc. kpeter@1202: /// kpeter@1202: /// Looks for the n-th arc in O(n) time. This operator is just an alias kpeter@1202: /// for \ref nth(). kpeter@1202: /// \pre \c n is in the range [0..length() - 1]. kpeter@1202: const Arc& operator[](int n) const { kpeter@1202: return nth(n); kpeter@1202: } kpeter@1202: alpar@96: /// \brief Length of the path. alpar@96: int length() const { alpar@96: int len = 0; alpar@96: Node *node = first; alpar@96: while (node != 0) { alpar@96: node = node->next; alpar@96: ++len; alpar@96: } alpar@96: return len; alpar@96: } alpar@96: alpar@97: /// \brief Return true if the path is empty. alpar@96: bool empty() const { return first == 0; } alpar@96: alpar@97: /// \brief Reset the path to an empty one. alpar@96: void clear() { alpar@96: while (first != 0) { alpar@96: last = first->next; alpar@96: alloc.destroy(first); alpar@96: alloc.deallocate(first, 1); alpar@96: first = last; alpar@96: } alpar@96: } alpar@96: alpar@97: /// \brief The first arc of the path alpar@96: const Arc& front() const { alpar@96: return first->arc; alpar@96: } alpar@96: alpar@96: /// \brief Add a new arc before the current path alpar@96: void addFront(const Arc& arc) { alpar@96: Node *node = alloc.allocate(1); alpar@96: alloc.construct(node, Node()); alpar@96: node->prev = 0; alpar@96: node->next = first; alpar@96: node->arc = arc; alpar@96: if (first) { alpar@96: first->prev = node; alpar@96: first = node; alpar@96: } else { alpar@96: first = last = node; alpar@96: } alpar@96: } alpar@96: alpar@96: /// \brief Erase the first arc of the path alpar@96: void eraseFront() { alpar@96: Node *node = first; alpar@96: first = first->next; alpar@96: if (first) { alpar@96: first->prev = 0; alpar@96: } else { alpar@96: last = 0; alpar@96: } alpar@96: alloc.destroy(node); alpar@96: alloc.deallocate(node, 1); alpar@96: } alpar@96: alpar@97: /// \brief The last arc of the path. alpar@96: const Arc& back() const { alpar@96: return last->arc; alpar@96: } alpar@96: alpar@96: /// \brief Add a new arc behind the current path. alpar@96: void addBack(const Arc& arc) { alpar@96: Node *node = alloc.allocate(1); alpar@96: alloc.construct(node, Node()); alpar@96: node->next = 0; alpar@96: node->prev = last; alpar@96: node->arc = arc; alpar@96: if (last) { alpar@96: last->next = node; alpar@96: last = node; alpar@96: } else { alpar@96: last = first = node; alpar@96: } alpar@96: } alpar@96: alpar@96: /// \brief Erase the last arc of the path alpar@96: void eraseBack() { alpar@96: Node *node = last; alpar@96: last = last->prev; alpar@96: if (last) { alpar@96: last->next = 0; alpar@96: } else { alpar@96: first = 0; alpar@96: } alpar@96: alloc.destroy(node); alpar@96: alloc.deallocate(node, 1); alpar@96: } alpar@96: alpar@97: /// \brief Splice a path to the back of the current path. alpar@96: /// alpar@97: /// It splices \c tpath to the back of the current path and \c alpar@96: /// tpath becomes empty. The time complexity of this function is alpar@96: /// O(1). alpar@96: void spliceBack(ListPath& tpath) { alpar@96: if (first) { alpar@96: if (tpath.first) { alpar@96: last->next = tpath.first; alpar@96: tpath.first->prev = last; alpar@96: last = tpath.last; alpar@96: } alpar@96: } else { alpar@96: first = tpath.first; alpar@96: last = tpath.last; alpar@96: } alpar@96: tpath.first = tpath.last = 0; alpar@96: } alpar@96: alpar@97: /// \brief Splice a path to the front of the current path. alpar@96: /// alpar@97: /// It splices \c tpath before the current path and \c tpath alpar@96: /// becomes empty. The time complexity of this function alpar@96: /// is O(1). alpar@96: void spliceFront(ListPath& tpath) { alpar@96: if (first) { alpar@96: if (tpath.first) { alpar@96: first->prev = tpath.last; alpar@96: tpath.last->next = first; alpar@96: first = tpath.first; alpar@96: } alpar@96: } else { alpar@96: first = tpath.first; alpar@96: last = tpath.last; alpar@96: } alpar@96: tpath.first = tpath.last = 0; alpar@96: } alpar@96: alpar@97: /// \brief Splice a path into the current path. alpar@96: /// alpar@96: /// It splices the \c tpath into the current path before the alpar@96: /// position of \c it iterator and \c tpath becomes empty. The alpar@97: /// time complexity of this function is O(1). If the \c it is alpar@97: /// \c INVALID then it will splice behind the current path. alpar@96: void splice(ArcIt it, ListPath& tpath) { alpar@96: if (it.node) { alpar@96: if (tpath.first) { alpar@96: tpath.first->prev = it.node->prev; alpar@96: if (it.node->prev) { alpar@96: it.node->prev->next = tpath.first; alpar@96: } else { alpar@96: first = tpath.first; alpar@96: } alpar@96: it.node->prev = tpath.last; alpar@96: tpath.last->next = it.node; alpar@96: } alpar@96: } else { alpar@96: if (first) { alpar@96: if (tpath.first) { alpar@96: last->next = tpath.first; alpar@96: tpath.first->prev = last; alpar@96: last = tpath.last; alpar@96: } alpar@96: } else { alpar@96: first = tpath.first; alpar@96: last = tpath.last; alpar@96: } alpar@96: } alpar@96: tpath.first = tpath.last = 0; alpar@96: } alpar@96: alpar@97: /// \brief Split the current path. alpar@96: /// alpar@97: /// It splits the current path into two parts. The part before alpar@97: /// the iterator \c it will remain in the current path and the part alpar@97: /// starting with alpar@97: /// \c it will put into \c tpath. If \c tpath have arcs alpar@97: /// before the operation they are removed first. The time kpeter@1201: /// complexity of this function is O(1) plus the time of emtying alpar@97: /// \c tpath. If \c it is \c INVALID then it just clears \c tpath alpar@96: void split(ArcIt it, ListPath& tpath) { alpar@96: tpath.clear(); alpar@96: if (it.node) { alpar@96: tpath.first = it.node; alpar@96: tpath.last = last; alpar@96: if (it.node->prev) { alpar@96: last = it.node->prev; alpar@96: last->next = 0; alpar@96: } else { alpar@96: first = last = 0; alpar@96: } alpar@96: it.node->prev = 0; alpar@96: } alpar@96: } alpar@96: alpar@96: alpar@96: typedef True BuildTag; alpar@96: alpar@96: template alpar@96: void build(const CPath& path) { alpar@96: for (typename CPath::ArcIt it(path); it != INVALID; ++it) { alpar@96: addBack(it); alpar@96: } alpar@96: } alpar@96: alpar@96: template alpar@96: void buildRev(const CPath& path) { alpar@96: for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { alpar@96: addFront(it); alpar@96: } alpar@96: } alpar@96: alpar@96: }; alpar@96: alpar@96: /// \brief A structure for representing directed paths in a digraph. alpar@96: /// alpar@96: /// A structure for representing directed path in a digraph. kpeter@559: /// \tparam GR The digraph type in which the path is. alpar@96: /// kpeter@1201: /// In a sense, a path can be treated as a list of arcs. The kpeter@1201: /// LEMON path type simply stores this list. As a consequence, it kpeter@1201: /// cannot enumerate the nodes in the path, and the source node of kpeter@1201: /// a zero-length path is undefined. alpar@96: /// alpar@97: /// This implementation is completly static, i.e. it can be copy constucted alpar@97: /// or copy assigned from another path, but otherwise it cannot be alpar@97: /// modified. alpar@97: /// kpeter@1201: /// Being the most memory-efficient path type in LEMON, it is kpeter@1201: /// intented to be used when you want to store a large number of paths. kpeter@559: template alpar@96: class StaticPath { alpar@96: public: alpar@96: kpeter@559: typedef GR Digraph; alpar@96: typedef typename Digraph::Arc Arc; alpar@96: alpar@96: /// \brief Default constructor alpar@96: /// alpar@96: /// Default constructor ggab90@1130: StaticPath() : len(0), _arcs(0) {} alpar@209: alpar@990: /// \brief Copy constructor alpar@990: /// ggab90@1130: StaticPath(const StaticPath& cpath) : _arcs(0) { alpar@990: pathCopy(cpath, *this); alpar@990: } alpar@990: alpar@96: /// \brief Template copy constructor alpar@96: /// alpar@97: /// This path can be initialized from any other path type. alpar@96: template ggab90@1130: StaticPath(const CPath& cpath) : _arcs(0) { kpeter@516: pathCopy(cpath, *this); alpar@96: } alpar@96: alpar@96: /// \brief Destructor of the path alpar@96: /// alpar@96: /// Destructor of the path alpar@96: ~StaticPath() { ggab90@1130: if (_arcs) delete[] _arcs; alpar@96: } alpar@96: alpar@990: /// \brief Copy assignment alpar@990: /// alpar@990: StaticPath& operator=(const StaticPath& cpath) { alpar@990: pathCopy(cpath, *this); alpar@990: return *this; alpar@990: } alpar@990: alpar@96: /// \brief Template copy assignment alpar@96: /// alpar@97: /// This path can be made equal to any other path type. It simply alpar@96: /// makes a copy of the given path. alpar@96: template alpar@96: StaticPath& operator=(const CPath& cpath) { kpeter@516: pathCopy(cpath, *this); alpar@96: return *this; alpar@96: } alpar@96: alpar@96: /// \brief Iterator class to iterate on the arcs of the paths alpar@96: /// alpar@96: /// This class is used to iterate on the arcs of the paths alpar@96: /// alpar@96: /// Of course it converts to Digraph::Arc alpar@96: class ArcIt { alpar@96: friend class StaticPath; alpar@96: public: alpar@96: /// Default constructor alpar@96: ArcIt() {} alpar@96: /// Invalid constructor alpar@96: ArcIt(Invalid) : path(0), idx(-1) {} alpar@96: /// Initializate the constructor to the first arc of path alpar@209: ArcIt(const StaticPath &_path) alpar@96: : path(&_path), idx(_path.empty() ? -1 : 0) {} alpar@96: alpar@96: private: alpar@96: alpar@96: /// Constructor with starting point alpar@209: ArcIt(const StaticPath &_path, int _idx) alpar@96: : idx(_idx), path(&_path) {} alpar@96: alpar@96: public: alpar@96: alpar@96: ///Conversion to Digraph::Arc alpar@96: operator const Arc&() const { alpar@96: return path->nth(idx); alpar@96: } alpar@96: alpar@96: /// Next arc alpar@209: ArcIt& operator++() { alpar@96: ++idx; alpar@209: if (idx >= path->length()) idx = -1; alpar@209: return *this; alpar@96: } alpar@96: alpar@96: /// Comparison operator alpar@96: bool operator==(const ArcIt& e) const { return idx==e.idx; } alpar@96: /// Comparison operator alpar@96: bool operator!=(const ArcIt& e) const { return idx!=e.idx; } alpar@96: /// Comparison operator alpar@96: bool operator<(const ArcIt& e) const { return idx arcs() const { ggab90@1130: return LemonRangeWrapper1(*this); ggab90@1130: } ggab90@1130: alpar@96: kpeter@920: /// \brief The n-th arc. alpar@96: /// kpeter@1201: /// Gives back the n-th arc. This function runs in O(1) time. kpeter@1201: /// \pre \c n is in the range [0..length() - 1]. alpar@96: const Arc& nth(int n) const { ggab90@1130: return _arcs[n]; alpar@96: } alpar@96: kpeter@920: /// \brief The arc iterator pointing to the n-th arc. alpar@96: ArcIt nthIt(int n) const { alpar@96: return ArcIt(*this, n); alpar@96: } alpar@96: kpeter@1202: /// \brief The n-th arc. kpeter@1202: /// kpeter@1202: /// Gives back the n-th arc. This operator is just an alias for \ref nth(), kpeter@1202: /// it runs in O(1) time. kpeter@1202: /// \pre \c n is in the range [0..length() - 1]. kpeter@1202: const Arc& operator[](int n) const { kpeter@1202: return _arcs[n]; kpeter@1202: } kpeter@1202: alpar@97: /// \brief The length of the path. alpar@96: int length() const { return len; } alpar@96: alpar@97: /// \brief Return true when the path is empty. alpar@96: int empty() const { return len == 0; } alpar@96: kpeter@1201: /// \brief Reset the path to an empty one. alpar@96: void clear() { alpar@96: len = 0; ggab90@1130: if (_arcs) delete[] _arcs; ggab90@1130: _arcs = 0; alpar@96: } alpar@96: alpar@97: /// \brief The first arc of the path. alpar@96: const Arc& front() const { ggab90@1130: return _arcs[0]; alpar@96: } alpar@96: alpar@97: /// \brief The last arc of the path. alpar@96: const Arc& back() const { ggab90@1130: return _arcs[len - 1]; alpar@96: } alpar@96: alpar@96: alpar@96: typedef True BuildTag; alpar@96: alpar@96: template alpar@96: void build(const CPath& path) { alpar@96: len = path.length(); ggab90@1130: _arcs = new Arc[len]; alpar@96: int index = 0; alpar@96: for (typename CPath::ArcIt it(path); it != INVALID; ++it) { ggab90@1130: _arcs[index] = it; alpar@96: ++index; alpar@96: } alpar@96: } alpar@96: alpar@96: template alpar@96: void buildRev(const CPath& path) { alpar@96: len = path.length(); ggab90@1130: _arcs = new Arc[len]; alpar@96: int index = len; alpar@96: for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { alpar@96: --index; ggab90@1130: _arcs[index] = it; alpar@96: } alpar@96: } alpar@96: alpar@96: private: alpar@96: int len; ggab90@1130: Arc* _arcs; alpar@96: }; alpar@96: alpar@98: /////////////////////////////////////////////////////////////////////// alpar@98: // Additional utilities alpar@98: /////////////////////////////////////////////////////////////////////// alpar@98: alpar@98: namespace _path_bits { alpar@98: alpar@98: template deba@144: struct RevPathTagIndicator { alpar@98: static const bool value = false; alpar@98: }; alpar@98: deba@144: template deba@144: struct RevPathTagIndicator< alpar@209: Path, deba@144: typename enable_if::type deba@144: > { deba@144: static const bool value = true; deba@144: }; deba@144: deba@144: template deba@144: struct BuildTagIndicator { deba@144: static const bool value = false; deba@144: }; deba@144: deba@144: template deba@144: struct BuildTagIndicator< alpar@209: Path, deba@144: typename enable_if::type alpar@98: > { alpar@98: static const bool value = true; alpar@98: }; alpar@98: kpeter@516: template ::value> kpeter@498: struct PathCopySelectorForward { kpeter@516: static void copy(const From& from, To& to) { kpeter@516: to.clear(); kpeter@516: for (typename From::ArcIt it(from); it != INVALID; ++it) { kpeter@516: to.addBack(it); alpar@98: } alpar@98: } alpar@98: }; alpar@98: kpeter@516: template kpeter@516: struct PathCopySelectorForward { kpeter@516: static void copy(const From& from, To& to) { kpeter@516: to.clear(); kpeter@516: to.build(from); kpeter@498: } kpeter@498: }; kpeter@498: kpeter@516: template ::value> kpeter@498: struct PathCopySelectorBackward { kpeter@516: static void copy(const From& from, To& to) { kpeter@516: to.clear(); kpeter@516: for (typename From::RevArcIt it(from); it != INVALID; ++it) { kpeter@516: to.addFront(it); alpar@98: } alpar@98: } alpar@98: }; alpar@98: kpeter@516: template kpeter@516: struct PathCopySelectorBackward { kpeter@516: static void copy(const From& from, To& to) { kpeter@516: to.clear(); kpeter@516: to.buildRev(from); alpar@98: } alpar@98: }; alpar@98: alpar@877: kpeter@516: template ::value> kpeter@498: struct PathCopySelector { kpeter@516: static void copy(const From& from, To& to) { kpeter@516: PathCopySelectorForward::copy(from, to); alpar@877: } kpeter@498: }; kpeter@498: kpeter@516: template kpeter@516: struct PathCopySelector { kpeter@516: static void copy(const From& from, To& to) { kpeter@516: PathCopySelectorBackward::copy(from, to); alpar@877: } kpeter@498: }; kpeter@498: alpar@98: } alpar@98: alpar@98: alpar@98: /// \brief Make a copy of a path. alpar@98: /// kpeter@516: /// This function makes a copy of a path. kpeter@516: template kpeter@516: void pathCopy(const From& from, To& to) { kpeter@516: checkConcept, From>(); kpeter@516: _path_bits::PathCopySelector::copy(from, to); kpeter@516: } kpeter@516: kpeter@516: /// \brief Deprecated version of \ref pathCopy(). kpeter@516: /// kpeter@516: /// Deprecated version of \ref pathCopy() (only for reverse compatibility). kpeter@516: template kpeter@516: void copyPath(To& to, const From& from) { kpeter@516: pathCopy(from, to); alpar@98: } alpar@98: alpar@98: /// \brief Check the consistency of a path. alpar@98: /// alpar@98: /// This function checks that the target of each arc is the same alpar@209: /// as the source of the next one. alpar@209: /// alpar@98: template alpar@98: bool checkPath(const Digraph& digraph, const Path& path) { alpar@98: typename Path::ArcIt it(path); alpar@98: if (it == INVALID) return true; alpar@98: typename Digraph::Node node = digraph.target(it); alpar@98: ++it; alpar@98: while (it != INVALID) { alpar@98: if (digraph.source(it) != node) return false; alpar@98: node = digraph.target(it); alpar@98: ++it; alpar@98: } alpar@98: return true; alpar@98: } alpar@98: alpar@98: /// \brief The source of a path alpar@98: /// kpeter@514: /// This function returns the source node of the given path. kpeter@514: /// If the path is empty, then it returns \c INVALID. alpar@98: template alpar@98: typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { kpeter@514: return path.empty() ? INVALID : digraph.source(path.front()); alpar@98: } alpar@98: alpar@98: /// \brief The target of a path alpar@98: /// kpeter@514: /// This function returns the target node of the given path. kpeter@514: /// If the path is empty, then it returns \c INVALID. alpar@98: template alpar@98: typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { kpeter@514: return path.empty() ? INVALID : digraph.target(path.back()); alpar@98: } alpar@98: kpeter@1201: /// \brief Class for iterating through the nodes of a path alpar@98: /// kpeter@1201: /// Class for iterating through the nodes of a path. alpar@98: /// kpeter@1201: /// In a sense, a path can be treated as a list of arcs. The kpeter@1201: /// LEMON path type simply stores this list. As a consequence, it kpeter@1201: /// cannot enumerate the nodes in the path, and the source node of kpeter@1201: /// a zero-length path is undefined. kpeter@1201: /// kpeter@1201: /// However, this class implements a node iterator for path structures. kpeter@1201: /// To provide this feature, the underlying digraph should be passed to alpar@98: /// the constructor of the iterator. alpar@98: template alpar@98: class PathNodeIt { alpar@98: private: alpar@98: const typename Path::Digraph *_digraph; alpar@98: typename Path::ArcIt _it; alpar@98: typename Path::Digraph::Node _nd; alpar@98: alpar@98: public: alpar@98: alpar@98: typedef typename Path::Digraph Digraph; alpar@98: typedef typename Digraph::Node Node; alpar@209: alpar@98: /// Default constructor alpar@98: PathNodeIt() {} alpar@98: /// Invalid constructor alpar@209: PathNodeIt(Invalid) alpar@98: : _digraph(0), _it(INVALID), _nd(INVALID) {} alpar@98: /// Constructor alpar@209: PathNodeIt(const Digraph& digraph, const Path& path) alpar@98: : _digraph(&digraph), _it(path) { alpar@98: _nd = (_it != INVALID ? _digraph->source(_it) : INVALID); alpar@98: } alpar@98: /// Constructor alpar@209: PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) alpar@98: : _digraph(&digraph), _it(path), _nd(src) {} alpar@98: alpar@98: ///Conversion to Digraph::Node alpar@98: operator Node() const { alpar@98: return _nd; alpar@98: } alpar@98: alpar@98: /// Next node alpar@98: PathNodeIt& operator++() { alpar@98: if (_it == INVALID) _nd = INVALID; alpar@98: else { alpar@209: _nd = _digraph->target(_it); alpar@209: ++_it; alpar@98: } alpar@98: return *this; alpar@98: } alpar@98: alpar@98: /// Comparison operator alpar@209: bool operator==(const PathNodeIt& n) const { alpar@209: return _it == n._it && _nd == n._nd; alpar@98: } alpar@98: /// Comparison operator alpar@209: bool operator!=(const PathNodeIt& n) const { alpar@209: return _it != n._it || _nd != n._nd; alpar@98: } alpar@98: /// Comparison operator alpar@209: bool operator<(const PathNodeIt& n) const { alpar@98: return (_it < n._it && _nd != INVALID); alpar@98: } alpar@209: alpar@98: }; alpar@209: ggab90@1130: /// \brief Gets the collection of the nodes of the path. ggab90@1130: /// ggab90@1130: /// This function can be used for iterating on the ggab90@1130: /// nodes of the path. It returns a wrapped ggab90@1130: /// PathNodeIt, which looks like an STL container ggab90@1130: /// (by having begin() and end()) which you can use in range-based ggab90@1130: /// for loops, STL algorithms, etc. ggab90@1130: /// For example you can write: ggab90@1130: ///\code ggab90@1130: /// for(auto u: pathNodes(g,p)) ggab90@1130: /// doSomething(u); ggab90@1130: ///\endcode ggab90@1130: template ggab90@1130: LemonRangeWrapper2, typename Path::Digraph, Path> ggab90@1130: pathNodes(const typename Path::Digraph &g, const Path &p) { ggab90@1130: return ggab90@1130: LemonRangeWrapper2, typename Path::Digraph, Path>(g,p); ggab90@1130: } ggab90@1130: alpar@96: ///@} alpar@96: alpar@96: } // namespace lemon alpar@96: alpar@96: #endif // LEMON_PATH_H