1.1 --- a/lemon/path.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/path.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -40,7 +40,7 @@
1.4 /// \brief A structure for representing directed paths in a digraph.
1.5 ///
1.6 /// A structure for representing directed path in a digraph.
1.7 - /// \tparam _Digraph The digraph type in which the path is.
1.8 + /// \tparam GR The digraph type in which the path is.
1.9 ///
1.10 /// In a sense, the path can be treated as a list of arcs. The
1.11 /// lemon path type stores just this list. As a consequence, it
1.12 @@ -52,11 +52,11 @@
1.13 /// insertion and erase is done in O(1) (amortized) time. The
1.14 /// implementation uses two vectors for storing the front and back
1.15 /// insertions.
1.16 - template <typename _Digraph>
1.17 + template <typename GR>
1.18 class Path {
1.19 public:
1.20
1.21 - typedef _Digraph Digraph;
1.22 + typedef GR Digraph;
1.23 typedef typename Digraph::Arc Arc;
1.24
1.25 /// \brief Default constructor
1.26 @@ -137,7 +137,7 @@
1.27
1.28 /// \brief The nth arc.
1.29 ///
1.30 - /// \pre n is in the [0..length() - 1] range
1.31 + /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.32 const Arc& nth(int n) const {
1.33 return n < int(head.size()) ? *(head.rbegin() + n) :
1.34 *(tail.begin() + (n - head.size()));
1.35 @@ -145,7 +145,7 @@
1.36
1.37 /// \brief Initialize arc iterator to point to the nth arc
1.38 ///
1.39 - /// \pre n is in the [0..length() - 1] range
1.40 + /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.41 ArcIt nthIt(int n) const {
1.42 return ArcIt(*this, n);
1.43 }
1.44 @@ -228,7 +228,7 @@
1.45 /// \brief A structure for representing directed paths in a digraph.
1.46 ///
1.47 /// A structure for representing directed path in a digraph.
1.48 - /// \tparam _Digraph The digraph type in which the path is.
1.49 + /// \tparam GR The digraph type in which the path is.
1.50 ///
1.51 /// In a sense, the path can be treated as a list of arcs. The
1.52 /// lemon path type stores just this list. As a consequence it
1.53 @@ -240,11 +240,11 @@
1.54 /// erasure is amortized O(1) time. This implementation is faster
1.55 /// then the \c Path type because it use just one vector for the
1.56 /// arcs.
1.57 - template <typename _Digraph>
1.58 + template <typename GR>
1.59 class SimplePath {
1.60 public:
1.61
1.62 - typedef _Digraph Digraph;
1.63 + typedef GR Digraph;
1.64 typedef typename Digraph::Arc Arc;
1.65
1.66 /// \brief Default constructor
1.67 @@ -329,7 +329,7 @@
1.68
1.69 /// \brief The nth arc.
1.70 ///
1.71 - /// \pre n is in the [0..length() - 1] range
1.72 + /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.73 const Arc& nth(int n) const {
1.74 return data[n];
1.75 }
1.76 @@ -392,7 +392,7 @@
1.77 /// \brief A structure for representing directed paths in a digraph.
1.78 ///
1.79 /// A structure for representing directed path in a digraph.
1.80 - /// \tparam _Digraph The digraph type in which the path is.
1.81 + /// \tparam GR The digraph type in which the path is.
1.82 ///
1.83 /// In a sense, the path can be treated as a list of arcs. The
1.84 /// lemon path type stores just this list. As a consequence it
1.85 @@ -404,11 +404,11 @@
1.86 /// of the arc in the path. The length can be computed in O(n)
1.87 /// time. The front and back insertion and erasure is O(1) time
1.88 /// and it can be splited and spliced in O(1) time.
1.89 - template <typename _Digraph>
1.90 + template <typename GR>
1.91 class ListPath {
1.92 public:
1.93
1.94 - typedef _Digraph Digraph;
1.95 + typedef GR Digraph;
1.96 typedef typename Digraph::Arc Arc;
1.97
1.98 protected:
1.99 @@ -507,7 +507,7 @@
1.100 /// \brief The nth arc.
1.101 ///
1.102 /// This function looks for the nth arc in O(n) time.
1.103 - /// \pre n is in the [0..length() - 1] range
1.104 + /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.105 const Arc& nth(int n) const {
1.106 Node *node = first;
1.107 for (int i = 0; i < n; ++i) {
1.108 @@ -732,7 +732,7 @@
1.109 /// \brief A structure for representing directed paths in a digraph.
1.110 ///
1.111 /// A structure for representing directed path in a digraph.
1.112 - /// \tparam _Digraph The digraph type in which the path is.
1.113 + /// \tparam GR The digraph type in which the path is.
1.114 ///
1.115 /// In a sense, the path can be treated as a list of arcs. The
1.116 /// lemon path type stores just this list. As a consequence it
1.117 @@ -746,11 +746,11 @@
1.118 /// Being the the most memory efficient path type in LEMON,
1.119 /// it is intented to be
1.120 /// used when you want to store a large number of paths.
1.121 - template <typename _Digraph>
1.122 + template <typename GR>
1.123 class StaticPath {
1.124 public:
1.125
1.126 - typedef _Digraph Digraph;
1.127 + typedef GR Digraph;
1.128 typedef typename Digraph::Arc Arc;
1.129
1.130 /// \brief Default constructor
1.131 @@ -833,7 +833,7 @@
1.132
1.133 /// \brief The nth arc.
1.134 ///
1.135 - /// \pre n is in the [0..length() - 1] range
1.136 + /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.137 const Arc& nth(int n) const {
1.138 return arcs[n];
1.139 }
1.140 @@ -929,9 +929,8 @@
1.141 };
1.142
1.143 template <typename Target, typename Source,
1.144 - bool buildEnable = BuildTagIndicator<Target>::value,
1.145 - bool revEnable = RevPathTagIndicator<Source>::value>
1.146 - struct PathCopySelector {
1.147 + bool buildEnable = BuildTagIndicator<Target>::value>
1.148 + struct PathCopySelectorForward {
1.149 static void copy(Target& target, const Source& source) {
1.150 target.clear();
1.151 for (typename Source::ArcIt it(source); it != INVALID; ++it) {
1.152 @@ -941,7 +940,16 @@
1.153 };
1.154
1.155 template <typename Target, typename Source>
1.156 - struct PathCopySelector<Target, Source, false, true> {
1.157 + struct PathCopySelectorForward<Target, Source, true> {
1.158 + static void copy(Target& target, const Source& source) {
1.159 + target.clear();
1.160 + target.build(source);
1.161 + }
1.162 + };
1.163 +
1.164 + template <typename Target, typename Source,
1.165 + bool buildEnable = BuildTagIndicator<Target>::value>
1.166 + struct PathCopySelectorBackward {
1.167 static void copy(Target& target, const Source& source) {
1.168 target.clear();
1.169 for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
1.170 @@ -951,21 +959,29 @@
1.171 };
1.172
1.173 template <typename Target, typename Source>
1.174 - struct PathCopySelector<Target, Source, true, false> {
1.175 - static void copy(Target& target, const Source& source) {
1.176 - target.clear();
1.177 - target.build(source);
1.178 - }
1.179 - };
1.180 -
1.181 - template <typename Target, typename Source>
1.182 - struct PathCopySelector<Target, Source, true, true> {
1.183 + struct PathCopySelectorBackward<Target, Source, true> {
1.184 static void copy(Target& target, const Source& source) {
1.185 target.clear();
1.186 target.buildRev(source);
1.187 }
1.188 };
1.189
1.190 +
1.191 + template <typename Target, typename Source,
1.192 + bool revEnable = RevPathTagIndicator<Source>::value>
1.193 + struct PathCopySelector {
1.194 + static void copy(Target& target, const Source& source) {
1.195 + PathCopySelectorForward<Target, Source>::copy(target, source);
1.196 + }
1.197 + };
1.198 +
1.199 + template <typename Target, typename Source>
1.200 + struct PathCopySelector<Target, Source, true> {
1.201 + static void copy(Target& target, const Source& source) {
1.202 + PathCopySelectorBackward<Target, Source>::copy(target, source);
1.203 + }
1.204 + };
1.205 +
1.206 }
1.207
1.208
1.209 @@ -999,18 +1015,20 @@
1.210
1.211 /// \brief The source of a path
1.212 ///
1.213 - /// This function returns the source of the given path.
1.214 + /// This function returns the source node of the given path.
1.215 + /// If the path is empty, then it returns \c INVALID.
1.216 template <typename Digraph, typename Path>
1.217 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1.218 - return digraph.source(path.front());
1.219 + return path.empty() ? INVALID : digraph.source(path.front());
1.220 }
1.221
1.222 /// \brief The target of a path
1.223 ///
1.224 - /// This function returns the target of the given path.
1.225 + /// This function returns the target node of the given path.
1.226 + /// If the path is empty, then it returns \c INVALID.
1.227 template <typename Digraph, typename Path>
1.228 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1.229 - return digraph.target(path.back());
1.230 + return path.empty() ? INVALID : digraph.target(path.back());
1.231 }
1.232
1.233 /// \brief Class which helps to iterate through the nodes of a path