# Changeset 858:2305167d2491 in lemon

Ignore:
Timestamp:
11/05/09 16:01:39 (10 years ago)
Branch:
1.1
Parents:
857:989c6629d045 (diff), 551:c6acc34f98dc (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge fix #321

Files:
2 edited

Unmodified
Removed
• ## lemon/path.h

 r551 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// /// A structure for representing directed path in a digraph. /// \tparam _Digraph The digraph type in which the path is. /// \tparam GR The digraph type in which the path is. /// /// In a sense, the path can be treated as a list of arcs. The /// implementation uses two vectors for storing the front and back /// insertions. template template class Path { public: typedef _Digraph Digraph; typedef GR Digraph; typedef typename Digraph::Arc Arc; /// \brief The nth arc. /// /// \pre n is in the [0..length() - 1] range /// \pre \c n is in the [0..length() - 1] range. const Arc& nth(int n) const { return n < int(head.size()) ? *(head.rbegin() + n) : /// \brief Initialize arc iterator to point to the nth arc /// /// \pre n is in the [0..length() - 1] range /// \pre \c n is in the [0..length() - 1] range. ArcIt nthIt(int n) const { return ArcIt(*this, n); /// /// A structure for representing directed path in a digraph. /// \tparam _Digraph The digraph type in which the path is. /// \tparam GR The digraph type in which the path is. /// /// In a sense, the path can be treated as a list of arcs. The /// then the \c Path type because it use just one vector for the /// arcs. template template class SimplePath { public: typedef _Digraph Digraph; typedef GR Digraph; typedef typename Digraph::Arc Arc; /// \brief The nth arc. /// /// \pre n is in the [0..length() - 1] range /// \pre \c n is in the [0..length() - 1] range. const Arc& nth(int n) const { return data[n]; /// /// A structure for representing directed path in a digraph. /// \tparam _Digraph The digraph type in which the path is. /// \tparam GR The digraph type in which the path is. /// /// In a sense, the path can be treated as a list of arcs. The /// time. The front and back insertion and erasure is O(1) time /// and it can be splited and spliced in O(1) time. template template class ListPath { public: typedef _Digraph Digraph; typedef GR Digraph; typedef typename Digraph::Arc Arc; /// /// This function looks for the nth arc in O(n) time. /// \pre n is in the [0..length() - 1] range /// \pre \c n is in the [0..length() - 1] range. const Arc& nth(int n) const { Node *node = first; /// /// A structure for representing directed path in a digraph. /// \tparam _Digraph The digraph type in which the path is. /// \tparam GR The digraph type in which the path is. /// /// In a sense, the path can be treated as a list of arcs. The /// it is intented to be /// used when you want to store a large number of paths. template template class StaticPath { public: typedef _Digraph Digraph; typedef GR Digraph; typedef typename Digraph::Arc Arc; /// \brief The nth arc. /// /// \pre n is in the [0..length() - 1] range /// \pre \c n is in the [0..length() - 1] range. const Arc& nth(int n) const { return arcs[n];
• ## lemon/path.h

 r798 template Path(const CPath& cpath) { copyPath(*this, cpath); pathCopy(cpath, *this); } template Path& operator=(const CPath& cpath) { copyPath(*this, cpath); pathCopy(cpath, *this); return *this; } template SimplePath(const CPath& cpath) { copyPath(*this, cpath); pathCopy(cpath, *this); } template SimplePath& operator=(const CPath& cpath) { copyPath(*this, cpath); pathCopy(cpath, *this); return *this; } template ListPath(const CPath& cpath) : first(0), last(0) { copyPath(*this, cpath); pathCopy(cpath, *this); } template ListPath& operator=(const CPath& cpath) { copyPath(*this, cpath); pathCopy(cpath, *this); return *this; } template StaticPath(const CPath& cpath) : arcs(0) { copyPath(*this, cpath); pathCopy(cpath, *this); } template StaticPath& operator=(const CPath& cpath) { copyPath(*this, cpath); pathCopy(cpath, *this); return *this; } }; template ::value> template ::value> struct PathCopySelectorForward { static void copy(Target& target, const Source& source) { target.clear(); for (typename Source::ArcIt it(source); it != INVALID; ++it) { target.addBack(it); static void copy(const From& from, To& to) { to.clear(); for (typename From::ArcIt it(from); it != INVALID; ++it) { to.addBack(it); } } }; template struct PathCopySelectorForward { static void copy(Target& target, const Source& source) { target.clear(); target.build(source); } }; template ::value> template struct PathCopySelectorForward { static void copy(const From& from, To& to) { to.clear(); to.build(from); } }; template ::value> struct PathCopySelectorBackward { static void copy(Target& target, const Source& source) { target.clear(); for (typename Source::RevArcIt it(source); it != INVALID; ++it) { target.addFront(it); static void copy(const From& from, To& to) { to.clear(); for (typename From::RevArcIt it(from); it != INVALID; ++it) { to.addFront(it); } } }; template struct PathCopySelectorBackward { static void copy(Target& target, const Source& source) { target.clear(); target.buildRev(source); template struct PathCopySelectorBackward { static void copy(const From& from, To& to) { to.clear(); to.buildRev(from); } }; template ::value> template ::value> struct PathCopySelector { static void copy(Target& target, const Source& source) { PathCopySelectorForward::copy(target, source); static void copy(const From& from, To& to) { PathCopySelectorForward::copy(from, to); } }; template struct PathCopySelector { static void copy(Target& target, const Source& source) { PathCopySelectorBackward::copy(target, source); template struct PathCopySelector { static void copy(const From& from, To& to) { PathCopySelectorBackward::copy(from, to); } }; /// \brief Make a copy of a path. /// ///  This function makes a copy of a path. template void copyPath(Target& target, const Source& source) { checkConcept, Source>(); _path_bits::PathCopySelector::copy(target, source); /// This function makes a copy of a path. template void pathCopy(const From& from, To& to) { checkConcept, From>(); _path_bits::PathCopySelector::copy(from, to); } /// \brief Deprecated version of \ref pathCopy(). /// /// Deprecated version of \ref pathCopy() (only for reverse compatibility). template void copyPath(To& to, const From& from) { pathCopy(from, to); }
Note: See TracChangeset for help on using the changeset viewer.