equal
deleted
inserted
replaced
41 /// |
41 /// |
42 /// A structure for representing directed path in a digraph. |
42 /// A structure for representing directed path in a digraph. |
43 /// \tparam GR The digraph type in which the path is. |
43 /// \tparam GR The digraph type in which the path is. |
44 /// |
44 /// |
45 /// In a sense, the path can be treated as a list of arcs. The |
45 /// In a sense, the path can be treated as a list of arcs. The |
46 /// lemon path type stores just this list. As a consequence, it |
46 /// LEMON path type stores just this list. As a consequence, it |
47 /// cannot enumerate the nodes of the path and the source node of |
47 /// cannot enumerate the nodes of the path and the source node of |
48 /// a zero length path is undefined. |
48 /// a zero length path is undefined. |
49 /// |
49 /// |
50 /// This implementation is a back and front insertable and erasable |
50 /// This implementation is a back and front insertable and erasable |
51 /// path type. It can be indexed in O(1) time. The front and back |
51 /// path type. It can be indexed in O(1) time. The front and back |
133 bool empty() const { return head.empty() && tail.empty(); } |
133 bool empty() const { return head.empty() && tail.empty(); } |
134 |
134 |
135 /// \brief Reset the path to an empty one. |
135 /// \brief Reset the path to an empty one. |
136 void clear() { head.clear(); tail.clear(); } |
136 void clear() { head.clear(); tail.clear(); } |
137 |
137 |
138 /// \brief The nth arc. |
138 /// \brief The n-th arc. |
139 /// |
139 /// |
140 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
140 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
141 const Arc& nth(int n) const { |
141 const Arc& nth(int n) const { |
142 return n < int(head.size()) ? *(head.rbegin() + n) : |
142 return n < int(head.size()) ? *(head.rbegin() + n) : |
143 *(tail.begin() + (n - head.size())); |
143 *(tail.begin() + (n - head.size())); |
144 } |
144 } |
145 |
145 |
146 /// \brief Initialize arc iterator to point to the nth arc |
146 /// \brief Initialize arc iterator to point to the n-th arc |
147 /// |
147 /// |
148 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
148 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
149 ArcIt nthIt(int n) const { |
149 ArcIt nthIt(int n) const { |
150 return ArcIt(*this, n); |
150 return ArcIt(*this, n); |
151 } |
151 } |
229 /// |
229 /// |
230 /// A structure for representing directed path in a digraph. |
230 /// A structure for representing directed path in a digraph. |
231 /// \tparam GR The digraph type in which the path is. |
231 /// \tparam GR The digraph type in which the path is. |
232 /// |
232 /// |
233 /// In a sense, the path can be treated as a list of arcs. The |
233 /// In a sense, the path can be treated as a list of arcs. The |
234 /// lemon path type stores just this list. As a consequence it |
234 /// LEMON path type stores just this list. As a consequence it |
235 /// cannot enumerate the nodes in the path and the zero length paths |
235 /// cannot enumerate the nodes in the path and the zero length paths |
236 /// cannot store the source. |
236 /// cannot store the source. |
237 /// |
237 /// |
238 /// This implementation is a just back insertable and erasable path |
238 /// This implementation is a just back insertable and erasable path |
239 /// type. It can be indexed in O(1) time. The back insertion and |
239 /// type. It can be indexed in O(1) time. The back insertion and |
325 bool empty() const { return data.empty(); } |
325 bool empty() const { return data.empty(); } |
326 |
326 |
327 /// \brief Reset the path to an empty one. |
327 /// \brief Reset the path to an empty one. |
328 void clear() { data.clear(); } |
328 void clear() { data.clear(); } |
329 |
329 |
330 /// \brief The nth arc. |
330 /// \brief The n-th arc. |
331 /// |
331 /// |
332 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
332 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
333 const Arc& nth(int n) const { |
333 const Arc& nth(int n) const { |
334 return data[n]; |
334 return data[n]; |
335 } |
335 } |
336 |
336 |
337 /// \brief Initializes arc iterator to point to the nth arc. |
337 /// \brief Initializes arc iterator to point to the n-th arc. |
338 ArcIt nthIt(int n) const { |
338 ArcIt nthIt(int n) const { |
339 return ArcIt(*this, n); |
339 return ArcIt(*this, n); |
340 } |
340 } |
341 |
341 |
342 /// \brief The first arc of the path. |
342 /// \brief The first arc of the path. |
393 /// |
393 /// |
394 /// A structure for representing directed path in a digraph. |
394 /// A structure for representing directed path in a digraph. |
395 /// \tparam GR The digraph type in which the path is. |
395 /// \tparam GR The digraph type in which the path is. |
396 /// |
396 /// |
397 /// In a sense, the path can be treated as a list of arcs. The |
397 /// In a sense, the path can be treated as a list of arcs. The |
398 /// lemon path type stores just this list. As a consequence it |
398 /// LEMON path type stores just this list. As a consequence it |
399 /// cannot enumerate the nodes in the path and the zero length paths |
399 /// cannot enumerate the nodes in the path and the zero length paths |
400 /// cannot store the source. |
400 /// cannot store the source. |
401 /// |
401 /// |
402 /// This implementation is a back and front insertable and erasable |
402 /// This implementation is a back and front insertable and erasable |
403 /// path type. It can be indexed in O(k) time, where k is the rank |
403 /// path type. It can be indexed in O(k) time, where k is the rank |
502 private: |
502 private: |
503 const ListPath *path; |
503 const ListPath *path; |
504 Node *node; |
504 Node *node; |
505 }; |
505 }; |
506 |
506 |
507 /// \brief The nth arc. |
507 /// \brief The n-th arc. |
508 /// |
508 /// |
509 /// This function looks for the nth arc in O(n) time. |
509 /// This function looks for the n-th arc in O(n) time. |
510 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
510 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
511 const Arc& nth(int n) const { |
511 const Arc& nth(int n) const { |
512 Node *node = first; |
512 Node *node = first; |
513 for (int i = 0; i < n; ++i) { |
513 for (int i = 0; i < n; ++i) { |
514 node = node->next; |
514 node = node->next; |
515 } |
515 } |
516 return node->arc; |
516 return node->arc; |
517 } |
517 } |
518 |
518 |
519 /// \brief Initializes arc iterator to point to the nth arc. |
519 /// \brief Initializes arc iterator to point to the n-th arc. |
520 ArcIt nthIt(int n) const { |
520 ArcIt nthIt(int n) const { |
521 Node *node = first; |
521 Node *node = first; |
522 for (int i = 0; i < n; ++i) { |
522 for (int i = 0; i < n; ++i) { |
523 node = node->next; |
523 node = node->next; |
524 } |
524 } |
733 /// |
733 /// |
734 /// A structure for representing directed path in a digraph. |
734 /// A structure for representing directed path in a digraph. |
735 /// \tparam GR The digraph type in which the path is. |
735 /// \tparam GR The digraph type in which the path is. |
736 /// |
736 /// |
737 /// In a sense, the path can be treated as a list of arcs. The |
737 /// In a sense, the path can be treated as a list of arcs. The |
738 /// lemon path type stores just this list. As a consequence it |
738 /// LEMON path type stores just this list. As a consequence it |
739 /// cannot enumerate the nodes in the path and the source node of |
739 /// cannot enumerate the nodes in the path and the source node of |
740 /// a zero length path is undefined. |
740 /// a zero length path is undefined. |
741 /// |
741 /// |
742 /// This implementation is completly static, i.e. it can be copy constucted |
742 /// This implementation is completly static, i.e. it can be copy constucted |
743 /// or copy assigned from another path, but otherwise it cannot be |
743 /// or copy assigned from another path, but otherwise it cannot be |
829 private: |
829 private: |
830 const StaticPath *path; |
830 const StaticPath *path; |
831 int idx; |
831 int idx; |
832 }; |
832 }; |
833 |
833 |
834 /// \brief The nth arc. |
834 /// \brief The n-th arc. |
835 /// |
835 /// |
836 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
836 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. |
837 const Arc& nth(int n) const { |
837 const Arc& nth(int n) const { |
838 return arcs[n]; |
838 return arcs[n]; |
839 } |
839 } |
840 |
840 |
841 /// \brief The arc iterator pointing to the nth arc. |
841 /// \brief The arc iterator pointing to the n-th arc. |
842 ArcIt nthIt(int n) const { |
842 ArcIt nthIt(int n) const { |
843 return ArcIt(*this, n); |
843 return ArcIt(*this, n); |
844 } |
844 } |
845 |
845 |
846 /// \brief The length of the path. |
846 /// \brief The length of the path. |
1040 } |
1040 } |
1041 |
1041 |
1042 /// \brief Class which helps to iterate through the nodes of a path |
1042 /// \brief Class which helps to iterate through the nodes of a path |
1043 /// |
1043 /// |
1044 /// In a sense, the path can be treated as a list of arcs. The |
1044 /// In a sense, the path can be treated as a list of arcs. The |
1045 /// lemon path type stores only this list. As a consequence, it |
1045 /// LEMON path type stores only this list. As a consequence, it |
1046 /// cannot enumerate the nodes in the path and the zero length paths |
1046 /// cannot enumerate the nodes in the path and the zero length paths |
1047 /// cannot have a source node. |
1047 /// cannot have a source node. |
1048 /// |
1048 /// |
1049 /// This class implements the node iterator of a path structure. To |
1049 /// This class implements the node iterator of a path structure. To |
1050 /// provide this feature, the underlying digraph should be passed to |
1050 /// provide this feature, the underlying digraph should be passed to |