1.1 --- a/lemon/path.h Sun Mar 19 14:38:08 2017 +0100
1.2 +++ b/lemon/path.h Sat Feb 17 23:44:15 2018 +0100
1.3 @@ -43,10 +43,10 @@
1.4 /// A structure for representing directed path in a digraph.
1.5 /// \tparam GR The digraph type in which the path is.
1.6 ///
1.7 - /// In a sense, the path can be treated as a list of arcs. The
1.8 - /// LEMON path type stores just this list. As a consequence, it
1.9 - /// cannot enumerate the nodes of the path and the source node of
1.10 - /// a zero length path is undefined.
1.11 + /// In a sense, a path can be treated as a list of arcs. The
1.12 + /// LEMON path type simply stores this list. As a consequence, it
1.13 + /// cannot enumerate the nodes in the path, and the source node of
1.14 + /// a zero-length path is undefined.
1.15 ///
1.16 /// This implementation is a back and front insertable and erasable
1.17 /// path type. It can be indexed in O(1) time. The front and back
1.18 @@ -168,7 +168,8 @@
1.19
1.20 /// \brief The n-th arc.
1.21 ///
1.22 - /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.23 + /// Gives back the n-th arc. This function runs in O(1) time.
1.24 + /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
1.25 const Arc& nth(int n) const {
1.26 return n < int(head.size()) ? *(head.rbegin() + n) :
1.27 *(tail.begin() + (n - head.size()));
1.28 @@ -261,15 +262,15 @@
1.29 /// A structure for representing directed path in a digraph.
1.30 /// \tparam GR The digraph type in which the path is.
1.31 ///
1.32 - /// In a sense, the path can be treated as a list of arcs. The
1.33 - /// LEMON path type stores just this list. As a consequence it
1.34 - /// cannot enumerate the nodes in the path and the zero length paths
1.35 - /// cannot store the source.
1.36 + /// In a sense, a path can be treated as a list of arcs. The
1.37 + /// LEMON path type simply stores this list. As a consequence, it
1.38 + /// cannot enumerate the nodes in the path, and the source node of
1.39 + /// a zero-length path is undefined.
1.40 ///
1.41 /// This implementation is a just back insertable and erasable path
1.42 /// type. It can be indexed in O(1) time. The back insertion and
1.43 /// erasure is amortized O(1) time. This implementation is faster
1.44 - /// then the \c Path type because it use just one vector for the
1.45 + /// than the \c Path type because it use just one vector for the
1.46 /// arcs.
1.47 template <typename GR>
1.48 class SimplePath {
1.49 @@ -390,7 +391,8 @@
1.50
1.51 /// \brief The n-th arc.
1.52 ///
1.53 - /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.54 + /// Gives back the n-th arc. This function runs in O(1) time.
1.55 + /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
1.56 const Arc& nth(int n) const {
1.57 return data[n];
1.58 }
1.59 @@ -455,10 +457,10 @@
1.60 /// A structure for representing directed path in a digraph.
1.61 /// \tparam GR The digraph type in which the path is.
1.62 ///
1.63 - /// In a sense, the path can be treated as a list of arcs. The
1.64 - /// LEMON path type stores just this list. As a consequence it
1.65 - /// cannot enumerate the nodes in the path and the zero length paths
1.66 - /// cannot store the source.
1.67 + /// In a sense, a path can be treated as a list of arcs. The
1.68 + /// LEMON path type simply stores this list. As a consequence, it
1.69 + /// cannot enumerate the nodes in the path, and the source node of
1.70 + /// a zero-length path is undefined.
1.71 ///
1.72 /// This implementation is a back and front insertable and erasable
1.73 /// path type. It can be indexed in O(k) time, where k is the rank
1.74 @@ -598,7 +600,7 @@
1.75 /// \brief The n-th arc.
1.76 ///
1.77 /// This function looks for the n-th arc in O(n) time.
1.78 - /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.79 + /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
1.80 const Arc& nth(int n) const {
1.81 Node *node = first;
1.82 for (int i = 0; i < n; ++i) {
1.83 @@ -784,7 +786,7 @@
1.84 /// starting with
1.85 /// \c it will put into \c tpath. If \c tpath have arcs
1.86 /// before the operation they are removed first. The time
1.87 - /// complexity of this function is O(1) plus the the time of emtying
1.88 + /// complexity of this function is O(1) plus the time of emtying
1.89 /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
1.90 void split(ArcIt it, ListPath& tpath) {
1.91 tpath.clear();
1.92 @@ -825,18 +827,17 @@
1.93 /// A structure for representing directed path in a digraph.
1.94 /// \tparam GR The digraph type in which the path is.
1.95 ///
1.96 - /// In a sense, the path can be treated as a list of arcs. The
1.97 - /// LEMON path type stores just this list. As a consequence it
1.98 - /// cannot enumerate the nodes in the path and the source node of
1.99 - /// a zero length path is undefined.
1.100 + /// In a sense, a path can be treated as a list of arcs. The
1.101 + /// LEMON path type simply stores this list. As a consequence, it
1.102 + /// cannot enumerate the nodes in the path, and the source node of
1.103 + /// a zero-length path is undefined.
1.104 ///
1.105 /// This implementation is completly static, i.e. it can be copy constucted
1.106 /// or copy assigned from another path, but otherwise it cannot be
1.107 /// modified.
1.108 ///
1.109 - /// Being the the most memory efficient path type in LEMON,
1.110 - /// it is intented to be
1.111 - /// used when you want to store a large number of paths.
1.112 + /// Being the most memory-efficient path type in LEMON, it is
1.113 + /// intented to be used when you want to store a large number of paths.
1.114 template <typename GR>
1.115 class StaticPath {
1.116 public:
1.117 @@ -954,7 +955,8 @@
1.118
1.119 /// \brief The n-th arc.
1.120 ///
1.121 - /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
1.122 + /// Gives back the n-th arc. This function runs in O(1) time.
1.123 + /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
1.124 const Arc& nth(int n) const {
1.125 return _arcs[n];
1.126 }
1.127 @@ -970,7 +972,7 @@
1.128 /// \brief Return true when the path is empty.
1.129 int empty() const { return len == 0; }
1.130
1.131 - /// \brief Erase all arcs in the digraph.
1.132 + /// \brief Reset the path to an empty one.
1.133 void clear() {
1.134 len = 0;
1.135 if (_arcs) delete[] _arcs;
1.136 @@ -1160,15 +1162,17 @@
1.137 return path.empty() ? INVALID : digraph.target(path.back());
1.138 }
1.139
1.140 - /// \brief Class which helps to iterate through the nodes of a path
1.141 + /// \brief Class for iterating through the nodes of a path
1.142 ///
1.143 - /// In a sense, the path can be treated as a list of arcs. The
1.144 - /// LEMON path type stores only this list. As a consequence, it
1.145 - /// cannot enumerate the nodes in the path and the zero length paths
1.146 - /// cannot have a source node.
1.147 + /// Class for iterating through the nodes of a path.
1.148 ///
1.149 - /// This class implements the node iterator of a path structure. To
1.150 - /// provide this feature, the underlying digraph should be passed to
1.151 + /// In a sense, a path can be treated as a list of arcs. The
1.152 + /// LEMON path type simply stores this list. As a consequence, it
1.153 + /// cannot enumerate the nodes in the path, and the source node of
1.154 + /// a zero-length path is undefined.
1.155 + ///
1.156 + /// However, this class implements a node iterator for path structures.
1.157 + /// To provide this feature, the underlying digraph should be passed to
1.158 /// the constructor of the iterator.
1.159 template <typename Path>
1.160 class PathNodeIt {