1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 ///\brief Classes for representing paths in digraphs.
30 #include <lemon/error.h>
31 #include <lemon/core.h>
32 #include <lemon/concepts/path.h>
33 #include <lemon/bits/stl_iterators.h>
41 /// \brief A structure for representing directed paths in a digraph.
43 /// A structure for representing directed path in a digraph.
44 /// \tparam GR The digraph type in which the path is.
46 /// In a sense, a path can be treated as a list of arcs. The
47 /// LEMON path type simply stores this list. As a consequence, it
48 /// cannot enumerate the nodes in the path, and the source node of
49 /// a zero-length path is undefined.
51 /// This implementation is a back and front insertable and erasable
52 /// path type. It can be indexed in O(1) time. The front and back
53 /// insertion and erase is done in O(1) (amortized) time. The
54 /// implementation uses two vectors for storing the front and back
56 template <typename GR>
61 typedef typename Digraph::Arc Arc;
63 /// \brief Default constructor
65 /// Default constructor
68 /// \brief Copy constructor
70 Path(const Path& cpath) {
71 pathCopy(cpath, *this);
74 /// \brief Template copy constructor
76 /// This constuctor initializes the path from any other path type.
77 /// It simply makes a copy of the given path.
78 template <typename CPath>
79 Path(const CPath& cpath) {
80 pathCopy(cpath, *this);
83 /// \brief Copy assignment
85 Path& operator=(const Path& cpath) {
86 pathCopy(cpath, *this);
90 /// \brief Template copy assignment
92 /// This operator makes a copy of a path of any other type.
93 template <typename CPath>
94 Path& operator=(const CPath& cpath) {
95 pathCopy(cpath, *this);
99 /// \brief LEMON style iterator for path arcs
101 /// This class is used to iterate on the arcs of the paths.
105 /// \brief Default constructor
107 /// \brief Invalid constructor
108 ArcIt(Invalid) : path(0), idx(-1) {}
109 /// \brief Initializate the iterator to the first arc of path
110 ArcIt(const Path &_path)
111 : path(&_path), idx(_path.empty() ? -1 : 0) {}
115 ArcIt(const Path &_path, int _idx)
116 : path(&_path), idx(_idx) {}
120 /// \brief Conversion to Arc
121 operator const Arc&() const {
122 return path->nth(idx);
126 ArcIt& operator++() {
128 if (idx >= path->length()) idx = -1;
132 /// \brief Comparison operator
133 bool operator==(const ArcIt& e) const { return idx==e.idx; }
134 /// \brief Comparison operator
135 bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
136 /// \brief Comparison operator
137 bool operator<(const ArcIt& e) const { return idx<e.idx; }
144 /// \brief Gets the collection of the arcs of the path.
146 /// This function can be used for iterating on the
147 /// arcs of the path. It returns a wrapped
148 /// ArcIt, which looks like an STL container
149 /// (by having begin() and end()) which you can use in range-based
150 /// for loops, STL algorithms, etc.
151 /// For example you can write:
153 /// for(auto a: p.arcs())
156 LemonRangeWrapper1<ArcIt, Path> arcs() const {
157 return LemonRangeWrapper1<ArcIt, Path>(*this);
161 /// \brief Length of the path.
162 int length() const { return head.size() + tail.size(); }
163 /// \brief Return whether the path is empty.
164 bool empty() const { return head.empty() && tail.empty(); }
166 /// \brief Reset the path to an empty one.
167 void clear() { head.clear(); tail.clear(); }
169 /// \brief The n-th arc.
171 /// Gives back the n-th arc. This function runs in O(1) time.
172 /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
173 const Arc& nth(int n) const {
174 return n < int(head.size()) ? *(head.rbegin() + n) :
175 *(tail.begin() + (n - head.size()));
178 /// \brief Initialize arc iterator to point to the n-th arc
180 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
181 ArcIt nthIt(int n) const {
182 return ArcIt(*this, n);
185 /// \brief The first arc of the path
186 const Arc& front() const {
187 return head.empty() ? tail.front() : head.back();
190 /// \brief Add a new arc before the current path
191 void addFront(const Arc& arc) {
195 /// \brief Erase the first arc of the path
201 int halfsize = tail.size() / 2;
202 head.resize(halfsize);
203 std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
205 std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
206 tail.resize(tail.size() - halfsize - 1);
210 /// \brief The last arc of the path
211 const Arc& back() const {
212 return tail.empty() ? head.front() : tail.back();
215 /// \brief Add a new arc behind the current path
216 void addBack(const Arc& arc) {
220 /// \brief Erase the last arc of the path
225 int halfsize = head.size() / 2;
226 tail.resize(halfsize);
227 std::copy(head.begin() + 1, head.begin() + halfsize + 1,
229 std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
230 head.resize(head.size() - halfsize - 1);
234 typedef True BuildTag;
236 template <typename CPath>
237 void build(const CPath& path) {
238 int len = path.length();
240 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
245 template <typename CPath>
246 void buildRev(const CPath& path) {
247 int len = path.length();
249 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
255 typedef std::vector<Arc> Container;
256 Container head, tail;
260 /// \brief A structure for representing directed paths in a digraph.
262 /// A structure for representing directed path in a digraph.
263 /// \tparam GR The digraph type in which the path is.
265 /// In a sense, a path can be treated as a list of arcs. The
266 /// LEMON path type simply stores this list. As a consequence, it
267 /// cannot enumerate the nodes in the path, and the source node of
268 /// a zero-length path is undefined.
270 /// This implementation is a just back insertable and erasable path
271 /// type. It can be indexed in O(1) time. The back insertion and
272 /// erasure is amortized O(1) time. This implementation is faster
273 /// than the \c Path type because it use just one vector for the
275 template <typename GR>
280 typedef typename Digraph::Arc Arc;
282 /// \brief Default constructor
284 /// Default constructor
287 /// \brief Copy constructor
289 SimplePath(const SimplePath& cpath) {
290 pathCopy(cpath, *this);
293 /// \brief Template copy constructor
295 /// This path can be initialized with any other path type. It just
296 /// makes a copy of the given path.
297 template <typename CPath>
298 SimplePath(const CPath& cpath) {
299 pathCopy(cpath, *this);
302 /// \brief Copy assignment
304 SimplePath& operator=(const SimplePath& cpath) {
305 pathCopy(cpath, *this);
309 /// \brief Template copy assignment
311 /// This path can be initialized with any other path type. It just
312 /// makes a copy of the given path.
313 template <typename CPath>
314 SimplePath& operator=(const CPath& cpath) {
315 pathCopy(cpath, *this);
319 /// \brief Iterator class to iterate on the arcs of the paths
321 /// This class is used to iterate on the arcs of the paths
323 /// Of course it converts to Digraph::Arc
325 friend class SimplePath;
327 /// Default constructor
329 /// Invalid constructor
330 ArcIt(Invalid) : path(0), idx(-1) {}
331 /// \brief Initializate the constructor to the first arc of path
332 ArcIt(const SimplePath &_path)
333 : path(&_path), idx(_path.empty() ? -1 : 0) {}
337 /// Constructor with starting point
338 ArcIt(const SimplePath &_path, int _idx)
339 : path(&_path), idx(_idx) {}
343 ///Conversion to Digraph::Arc
344 operator const Arc&() const {
345 return path->nth(idx);
349 ArcIt& operator++() {
351 if (idx >= path->length()) idx = -1;
355 /// Comparison operator
356 bool operator==(const ArcIt& e) const { return idx==e.idx; }
357 /// Comparison operator
358 bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
359 /// Comparison operator
360 bool operator<(const ArcIt& e) const { return idx<e.idx; }
363 const SimplePath *path;
367 /// \brief Gets the collection of the arcs of the path.
369 /// This function can be used for iterating on the
370 /// arcs of the path. It returns a wrapped
371 /// ArcIt, which looks like an STL container
372 /// (by having begin() and end()) which you can use in range-based
373 /// for loops, STL algorithms, etc.
374 /// For example you can write:
376 /// for(auto a: p.arcs())
379 LemonRangeWrapper1<ArcIt, SimplePath> arcs() const {
380 return LemonRangeWrapper1<ArcIt, SimplePath>(*this);
384 /// \brief Length of the path.
385 int length() const { return data.size(); }
386 /// \brief Return true if the path is empty.
387 bool empty() const { return data.empty(); }
389 /// \brief Reset the path to an empty one.
390 void clear() { data.clear(); }
392 /// \brief The n-th arc.
394 /// Gives back the n-th arc. This function runs in O(1) time.
395 /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
396 const Arc& nth(int n) const {
400 /// \brief Initializes arc iterator to point to the n-th arc.
401 ArcIt nthIt(int n) const {
402 return ArcIt(*this, n);
405 /// \brief The first arc of the path.
406 const Arc& front() const {
410 /// \brief The last arc of the path.
411 const Arc& back() const {
415 /// \brief Add a new arc behind the current path.
416 void addBack(const Arc& arc) {
420 /// \brief Erase the last arc of the path
425 typedef True BuildTag;
427 template <typename CPath>
428 void build(const CPath& path) {
429 int len = path.length();
432 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
438 template <typename CPath>
439 void buildRev(const CPath& path) {
440 int len = path.length();
443 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
450 typedef std::vector<Arc> Container;
455 /// \brief A structure for representing directed paths in a digraph.
457 /// A structure for representing directed path in a digraph.
458 /// \tparam GR The digraph type in which the path is.
460 /// In a sense, a path can be treated as a list of arcs. The
461 /// LEMON path type simply stores this list. As a consequence, it
462 /// cannot enumerate the nodes in the path, and the source node of
463 /// a zero-length path is undefined.
465 /// This implementation is a back and front insertable and erasable
466 /// path type. It can be indexed in O(k) time, where k is the rank
467 /// of the arc in the path. The length can be computed in O(n)
468 /// time. The front and back insertion and erasure is O(1) time
469 /// and it can be splited and spliced in O(1) time.
470 template <typename GR>
475 typedef typename Digraph::Arc Arc;
479 // the std::list<> is incompatible
480 // hard to create invalid iterator
488 std::allocator<Node> alloc;
492 /// \brief Default constructor
494 /// Default constructor
495 ListPath() : first(0), last(0) {}
497 /// \brief Copy constructor
499 ListPath(const ListPath& cpath) : first(0), last(0) {
500 pathCopy(cpath, *this);
503 /// \brief Template copy constructor
505 /// This path can be initialized with any other path type. It just
506 /// makes a copy of the given path.
507 template <typename CPath>
508 ListPath(const CPath& cpath) : first(0), last(0) {
509 pathCopy(cpath, *this);
512 /// \brief Destructor of the path
514 /// Destructor of the path
519 /// \brief Copy assignment
521 ListPath& operator=(const ListPath& cpath) {
522 pathCopy(cpath, *this);
526 /// \brief Template copy assignment
528 /// This path can be initialized with any other path type. It just
529 /// makes a copy of the given path.
530 template <typename CPath>
531 ListPath& operator=(const CPath& cpath) {
532 pathCopy(cpath, *this);
536 /// \brief Iterator class to iterate on the arcs of the paths
538 /// This class is used to iterate on the arcs of the paths
540 /// Of course it converts to Digraph::Arc
542 friend class ListPath;
544 /// Default constructor
546 /// Invalid constructor
547 ArcIt(Invalid) : path(0), node(0) {}
548 /// \brief Initializate the constructor to the first arc of path
549 ArcIt(const ListPath &_path)
550 : path(&_path), node(_path.first) {}
554 ArcIt(const ListPath &_path, Node *_node)
555 : path(&_path), node(_node) {}
560 ///Conversion to Digraph::Arc
561 operator const Arc&() const {
566 ArcIt& operator++() {
571 /// Comparison operator
572 bool operator==(const ArcIt& e) const { return node==e.node; }
573 /// Comparison operator
574 bool operator!=(const ArcIt& e) const { return node!=e.node; }
575 /// Comparison operator
576 bool operator<(const ArcIt& e) const { return node<e.node; }
579 const ListPath *path;
583 /// \brief Gets the collection of the arcs of the path.
585 /// This function can be used for iterating on the
586 /// arcs of the path. It returns a wrapped
587 /// ArcIt, which looks like an STL container
588 /// (by having begin() and end()) which you can use in range-based
589 /// for loops, STL algorithms, etc.
590 /// For example you can write:
592 /// for(auto a: p.arcs())
595 LemonRangeWrapper1<ArcIt, ListPath> arcs() const {
596 return LemonRangeWrapper1<ArcIt, ListPath>(*this);
600 /// \brief The n-th arc.
602 /// This function looks for the n-th arc in O(n) time.
603 /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
604 const Arc& nth(int n) const {
606 for (int i = 0; i < n; ++i) {
612 /// \brief Initializes arc iterator to point to the n-th arc.
613 ArcIt nthIt(int n) const {
615 for (int i = 0; i < n; ++i) {
618 return ArcIt(*this, node);
621 /// \brief Length of the path.
632 /// \brief Return true if the path is empty.
633 bool empty() const { return first == 0; }
635 /// \brief Reset the path to an empty one.
639 alloc.destroy(first);
640 alloc.deallocate(first, 1);
645 /// \brief The first arc of the path
646 const Arc& front() const {
650 /// \brief Add a new arc before the current path
651 void addFront(const Arc& arc) {
652 Node *node = alloc.allocate(1);
653 alloc.construct(node, Node());
665 /// \brief Erase the first arc of the path
675 alloc.deallocate(node, 1);
678 /// \brief The last arc of the path.
679 const Arc& back() const {
683 /// \brief Add a new arc behind the current path.
684 void addBack(const Arc& arc) {
685 Node *node = alloc.allocate(1);
686 alloc.construct(node, Node());
698 /// \brief Erase the last arc of the path
708 alloc.deallocate(node, 1);
711 /// \brief Splice a path to the back of the current path.
713 /// It splices \c tpath to the back of the current path and \c
714 /// tpath becomes empty. The time complexity of this function is
716 void spliceBack(ListPath& tpath) {
719 last->next = tpath.first;
720 tpath.first->prev = last;
727 tpath.first = tpath.last = 0;
730 /// \brief Splice a path to the front of the current path.
732 /// It splices \c tpath before the current path and \c tpath
733 /// becomes empty. The time complexity of this function
735 void spliceFront(ListPath& tpath) {
738 first->prev = tpath.last;
739 tpath.last->next = first;
746 tpath.first = tpath.last = 0;
749 /// \brief Splice a path into the current path.
751 /// It splices the \c tpath into the current path before the
752 /// position of \c it iterator and \c tpath becomes empty. The
753 /// time complexity of this function is O(1). If the \c it is
754 /// \c INVALID then it will splice behind the current path.
755 void splice(ArcIt it, ListPath& tpath) {
758 tpath.first->prev = it.node->prev;
760 it.node->prev->next = tpath.first;
764 it.node->prev = tpath.last;
765 tpath.last->next = it.node;
770 last->next = tpath.first;
771 tpath.first->prev = last;
779 tpath.first = tpath.last = 0;
782 /// \brief Split the current path.
784 /// It splits the current path into two parts. The part before
785 /// the iterator \c it will remain in the current path and the part
787 /// \c it will put into \c tpath. If \c tpath have arcs
788 /// before the operation they are removed first. The time
789 /// complexity of this function is O(1) plus the time of emtying
790 /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
791 void split(ArcIt it, ListPath& tpath) {
794 tpath.first = it.node;
797 last = it.node->prev;
807 typedef True BuildTag;
809 template <typename CPath>
810 void build(const CPath& path) {
811 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
816 template <typename CPath>
817 void buildRev(const CPath& path) {
818 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
825 /// \brief A structure for representing directed paths in a digraph.
827 /// A structure for representing directed path in a digraph.
828 /// \tparam GR The digraph type in which the path is.
830 /// In a sense, a path can be treated as a list of arcs. The
831 /// LEMON path type simply stores this list. As a consequence, it
832 /// cannot enumerate the nodes in the path, and the source node of
833 /// a zero-length path is undefined.
835 /// This implementation is completly static, i.e. it can be copy constucted
836 /// or copy assigned from another path, but otherwise it cannot be
839 /// Being the most memory-efficient path type in LEMON, it is
840 /// intented to be used when you want to store a large number of paths.
841 template <typename GR>
846 typedef typename Digraph::Arc Arc;
848 /// \brief Default constructor
850 /// Default constructor
851 StaticPath() : len(0), _arcs(0) {}
853 /// \brief Copy constructor
855 StaticPath(const StaticPath& cpath) : _arcs(0) {
856 pathCopy(cpath, *this);
859 /// \brief Template copy constructor
861 /// This path can be initialized from any other path type.
862 template <typename CPath>
863 StaticPath(const CPath& cpath) : _arcs(0) {
864 pathCopy(cpath, *this);
867 /// \brief Destructor of the path
869 /// Destructor of the path
871 if (_arcs) delete[] _arcs;
874 /// \brief Copy assignment
876 StaticPath& operator=(const StaticPath& cpath) {
877 pathCopy(cpath, *this);
881 /// \brief Template copy assignment
883 /// This path can be made equal to any other path type. It simply
884 /// makes a copy of the given path.
885 template <typename CPath>
886 StaticPath& operator=(const CPath& cpath) {
887 pathCopy(cpath, *this);
891 /// \brief Iterator class to iterate on the arcs of the paths
893 /// This class is used to iterate on the arcs of the paths
895 /// Of course it converts to Digraph::Arc
897 friend class StaticPath;
899 /// Default constructor
901 /// Invalid constructor
902 ArcIt(Invalid) : path(0), idx(-1) {}
903 /// Initializate the constructor to the first arc of path
904 ArcIt(const StaticPath &_path)
905 : path(&_path), idx(_path.empty() ? -1 : 0) {}
909 /// Constructor with starting point
910 ArcIt(const StaticPath &_path, int _idx)
911 : idx(_idx), path(&_path) {}
915 ///Conversion to Digraph::Arc
916 operator const Arc&() const {
917 return path->nth(idx);
921 ArcIt& operator++() {
923 if (idx >= path->length()) idx = -1;
927 /// Comparison operator
928 bool operator==(const ArcIt& e) const { return idx==e.idx; }
929 /// Comparison operator
930 bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
931 /// Comparison operator
932 bool operator<(const ArcIt& e) const { return idx<e.idx; }
935 const StaticPath *path;
939 /// \brief Gets the collection of the arcs of the path.
941 /// This function can be used for iterating on the
942 /// arcs of the path. It returns a wrapped
943 /// ArcIt, which looks like an STL container
944 /// (by having begin() and end()) which you can use in range-based
945 /// for loops, STL algorithms, etc.
946 /// For example you can write:
948 /// for(auto a: p.arcs())
951 LemonRangeWrapper1<ArcIt, StaticPath> arcs() const {
952 return LemonRangeWrapper1<ArcIt, StaticPath>(*this);
956 /// \brief The n-th arc.
958 /// Gives back the n-th arc. This function runs in O(1) time.
959 /// \pre \c n is in the range <tt>[0..length() - 1]</tt>.
960 const Arc& nth(int n) const {
964 /// \brief The arc iterator pointing to the n-th arc.
965 ArcIt nthIt(int n) const {
966 return ArcIt(*this, n);
969 /// \brief The length of the path.
970 int length() const { return len; }
972 /// \brief Return true when the path is empty.
973 int empty() const { return len == 0; }
975 /// \brief Reset the path to an empty one.
978 if (_arcs) delete[] _arcs;
982 /// \brief The first arc of the path.
983 const Arc& front() const {
987 /// \brief The last arc of the path.
988 const Arc& back() const {
989 return _arcs[len - 1];
993 typedef True BuildTag;
995 template <typename CPath>
996 void build(const CPath& path) {
998 _arcs = new Arc[len];
1000 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1006 template <typename CPath>
1007 void buildRev(const CPath& path) {
1008 len = path.length();
1009 _arcs = new Arc[len];
1011 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1022 ///////////////////////////////////////////////////////////////////////
1023 // Additional utilities
1024 ///////////////////////////////////////////////////////////////////////
1026 namespace _path_bits {
1028 template <typename Path, typename Enable = void>
1029 struct RevPathTagIndicator {
1030 static const bool value = false;
1033 template <typename Path>
1034 struct RevPathTagIndicator<
1036 typename enable_if<typename Path::RevPathTag, void>::type
1038 static const bool value = true;
1041 template <typename Path, typename Enable = void>
1042 struct BuildTagIndicator {
1043 static const bool value = false;
1046 template <typename Path>
1047 struct BuildTagIndicator<
1049 typename enable_if<typename Path::BuildTag, void>::type
1051 static const bool value = true;
1054 template <typename From, typename To,
1055 bool buildEnable = BuildTagIndicator<To>::value>
1056 struct PathCopySelectorForward {
1057 static void copy(const From& from, To& to) {
1059 for (typename From::ArcIt it(from); it != INVALID; ++it) {
1065 template <typename From, typename To>
1066 struct PathCopySelectorForward<From, To, true> {
1067 static void copy(const From& from, To& to) {
1073 template <typename From, typename To,
1074 bool buildEnable = BuildTagIndicator<To>::value>
1075 struct PathCopySelectorBackward {
1076 static void copy(const From& from, To& to) {
1078 for (typename From::RevArcIt it(from); it != INVALID; ++it) {
1084 template <typename From, typename To>
1085 struct PathCopySelectorBackward<From, To, true> {
1086 static void copy(const From& from, To& to) {
1093 template <typename From, typename To,
1094 bool revEnable = RevPathTagIndicator<From>::value>
1095 struct PathCopySelector {
1096 static void copy(const From& from, To& to) {
1097 PathCopySelectorForward<From, To>::copy(from, to);
1101 template <typename From, typename To>
1102 struct PathCopySelector<From, To, true> {
1103 static void copy(const From& from, To& to) {
1104 PathCopySelectorBackward<From, To>::copy(from, to);
1111 /// \brief Make a copy of a path.
1113 /// This function makes a copy of a path.
1114 template <typename From, typename To>
1115 void pathCopy(const From& from, To& to) {
1116 checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
1117 _path_bits::PathCopySelector<From, To>::copy(from, to);
1120 /// \brief Deprecated version of \ref pathCopy().
1122 /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
1123 template <typename To, typename From>
1124 void copyPath(To& to, const From& from) {
1128 /// \brief Check the consistency of a path.
1130 /// This function checks that the target of each arc is the same
1131 /// as the source of the next one.
1133 template <typename Digraph, typename Path>
1134 bool checkPath(const Digraph& digraph, const Path& path) {
1135 typename Path::ArcIt it(path);
1136 if (it == INVALID) return true;
1137 typename Digraph::Node node = digraph.target(it);
1139 while (it != INVALID) {
1140 if (digraph.source(it) != node) return false;
1141 node = digraph.target(it);
1147 /// \brief The source of a path
1149 /// This function returns the source node of the given path.
1150 /// If the path is empty, then it returns \c INVALID.
1151 template <typename Digraph, typename Path>
1152 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1153 return path.empty() ? INVALID : digraph.source(path.front());
1156 /// \brief The target of a path
1158 /// This function returns the target node of the given path.
1159 /// If the path is empty, then it returns \c INVALID.
1160 template <typename Digraph, typename Path>
1161 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1162 return path.empty() ? INVALID : digraph.target(path.back());
1165 /// \brief Class for iterating through the nodes of a path
1167 /// Class for iterating through the nodes of a path.
1169 /// In a sense, a path can be treated as a list of arcs. The
1170 /// LEMON path type simply stores this list. As a consequence, it
1171 /// cannot enumerate the nodes in the path, and the source node of
1172 /// a zero-length path is undefined.
1174 /// However, this class implements a node iterator for path structures.
1175 /// To provide this feature, the underlying digraph should be passed to
1176 /// the constructor of the iterator.
1177 template <typename Path>
1180 const typename Path::Digraph *_digraph;
1181 typename Path::ArcIt _it;
1182 typename Path::Digraph::Node _nd;
1186 typedef typename Path::Digraph Digraph;
1187 typedef typename Digraph::Node Node;
1189 /// Default constructor
1191 /// Invalid constructor
1193 : _digraph(0), _it(INVALID), _nd(INVALID) {}
1195 PathNodeIt(const Digraph& digraph, const Path& path)
1196 : _digraph(&digraph), _it(path) {
1197 _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1200 PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1201 : _digraph(&digraph), _it(path), _nd(src) {}
1203 ///Conversion to Digraph::Node
1204 operator Node() const {
1209 PathNodeIt& operator++() {
1210 if (_it == INVALID) _nd = INVALID;
1212 _nd = _digraph->target(_it);
1218 /// Comparison operator
1219 bool operator==(const PathNodeIt& n) const {
1220 return _it == n._it && _nd == n._nd;
1222 /// Comparison operator
1223 bool operator!=(const PathNodeIt& n) const {
1224 return _it != n._it || _nd != n._nd;
1226 /// Comparison operator
1227 bool operator<(const PathNodeIt& n) const {
1228 return (_it < n._it && _nd != INVALID);
1233 /// \brief Gets the collection of the nodes of the path.
1235 /// This function can be used for iterating on the
1236 /// nodes of the path. It returns a wrapped
1237 /// PathNodeIt, which looks like an STL container
1238 /// (by having begin() and end()) which you can use in range-based
1239 /// for loops, STL algorithms, etc.
1240 /// For example you can write:
1242 /// for(auto u: pathNodes(g,p))
1245 template<typename Path>
1246 LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>
1247 pathNodes(const typename Path::Digraph &g, const Path &p) {
1249 LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>(g,p);
1254 } // namespace lemon
1256 #endif // LEMON_PATH_H