diff --git a/lemon/path.h b/lemon/path.h --- a/lemon/path.h +++ b/lemon/path.h @@ -40,7 +40,7 @@ /// \brief A structure for representing directed paths in a digraph. /// /// 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 /// lemon path type stores just this list. As a consequence, it @@ -52,11 +52,11 @@ /// insertion and erase is done in O(1) (amortized) time. 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 Default constructor @@ -137,7 +137,7 @@ /// \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) : *(tail.begin() + (n - head.size())); @@ -145,7 +145,7 @@ /// \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); } @@ -228,7 +228,7 @@ /// \brief A structure for representing directed paths in a digraph. /// /// 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 /// lemon path type stores just this list. As a consequence it @@ -240,11 +240,11 @@ /// 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 + template class SimplePath { public: - typedef _Digraph Digraph; + typedef GR Digraph; typedef typename Digraph::Arc Arc; /// \brief Default constructor @@ -329,7 +329,7 @@ /// \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]; } @@ -392,7 +392,7 @@ /// \brief A structure for representing directed paths in a digraph. /// /// 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 /// lemon path type stores just this list. As a consequence it @@ -404,11 +404,11 @@ /// 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 + template class ListPath { public: - typedef _Digraph Digraph; + typedef GR Digraph; typedef typename Digraph::Arc Arc; protected: @@ -507,7 +507,7 @@ /// \brief The nth 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; for (int i = 0; i < n; ++i) { @@ -732,7 +732,7 @@ /// \brief A structure for representing directed paths in a digraph. /// /// 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 /// lemon path type stores just this list. As a consequence it @@ -746,11 +746,11 @@ /// Being the the most memory efficient path type in LEMON, /// 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 Default constructor @@ -833,7 +833,7 @@ /// \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]; } @@ -929,9 +929,8 @@ }; template ::value, - bool revEnable = RevPathTagIndicator::value> - struct PathCopySelector { + bool buildEnable = BuildTagIndicator::value> + struct PathCopySelectorForward { static void copy(Target& target, const Source& source) { target.clear(); for (typename Source::ArcIt it(source); it != INVALID; ++it) { @@ -941,7 +940,16 @@ }; template - struct PathCopySelector { + struct PathCopySelectorForward { + static void copy(Target& target, const Source& source) { + target.clear(); + target.build(source); + } + }; + + template ::value> + struct PathCopySelectorBackward { static void copy(Target& target, const Source& source) { target.clear(); for (typename Source::RevArcIt it(source); it != INVALID; ++it) { @@ -951,21 +959,29 @@ }; template - struct PathCopySelector { - static void copy(Target& target, const Source& source) { - target.clear(); - target.build(source); - } - }; - - template - struct PathCopySelector { + struct PathCopySelectorBackward { static void copy(Target& target, const Source& source) { target.clear(); target.buildRev(source); } }; + + template ::value> + struct PathCopySelector { + static void copy(Target& target, const Source& source) { + PathCopySelectorForward::copy(target, source); + } + }; + + template + struct PathCopySelector { + static void copy(Target& target, const Source& source) { + PathCopySelectorBackward::copy(target, source); + } + }; + } @@ -999,18 +1015,20 @@ /// \brief The source of a path /// - /// This function returns the source of the given path. + /// This function returns the source node of the given path. + /// If the path is empty, then it returns \c INVALID. template typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { - return digraph.source(path.front()); + return path.empty() ? INVALID : digraph.source(path.front()); } /// \brief The target of a path /// - /// This function returns the target of the given path. + /// This function returns the target node of the given path. + /// If the path is empty, then it returns \c INVALID. template typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { - return digraph.target(path.back()); + return path.empty() ? INVALID : digraph.target(path.back()); } /// \brief Class which helps to iterate through the nodes of a path