Update INSTALL file.
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
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>
40 /// \brief A structure for representing directed paths in a digraph.
42 /// A structure for representing directed path in a digraph.
43 /// \tparam _Digraph The digraph type in which the path is.
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
47 /// cannot enumerate the nodes of the path and the source node of
48 /// a zero length path is undefined.
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
52 /// insertion and erase is done in O(1) (amortized) time. The
53 /// implementation uses two vectors for storing the front and back
55 template <typename _Digraph>
59 typedef _Digraph Digraph;
60 typedef typename Digraph::Arc Arc;
62 /// \brief Default constructor
64 /// Default constructor
67 /// \brief Template copy constructor
69 /// This constuctor initializes the path from any other path type.
70 /// It simply makes a copy of the given path.
71 template <typename CPath>
72 Path(const CPath& cpath) {
73 copyPath(*this, cpath);
76 /// \brief Template copy assignment
78 /// This operator makes a copy of a path of any other type.
79 template <typename CPath>
80 Path& operator=(const CPath& cpath) {
81 copyPath(*this, cpath);
85 /// \brief LEMON style iterator for path arcs
87 /// This class is used to iterate on the arcs of the paths.
91 /// \brief Default constructor
93 /// \brief Invalid constructor
94 ArcIt(Invalid) : path(0), idx(-1) {}
95 /// \brief Initializate the iterator to the first arc of path
96 ArcIt(const Path &_path)
97 : path(&_path), idx(_path.empty() ? -1 : 0) {}
101 ArcIt(const Path &_path, int _idx)
102 : path(&_path), idx(_idx) {}
106 /// \brief Conversion to Arc
107 operator const Arc&() const {
108 return path->nth(idx);
112 ArcIt& operator++() {
114 if (idx >= path->length()) idx = -1;
118 /// \brief Comparison operator
119 bool operator==(const ArcIt& e) const { return idx==e.idx; }
120 /// \brief Comparison operator
121 bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
122 /// \brief Comparison operator
123 bool operator<(const ArcIt& e) const { return idx<e.idx; }
130 /// \brief Length of the path.
131 int length() const { return head.size() + tail.size(); }
132 /// \brief Return whether the path is empty.
133 bool empty() const { return head.empty() && tail.empty(); }
135 /// \brief Reset the path to an empty one.
136 void clear() { head.clear(); tail.clear(); }
138 /// \brief The nth arc.
140 /// \pre n is in the [0..length() - 1] range
141 const Arc& nth(int n) const {
142 return n < int(head.size()) ? *(head.rbegin() + n) :
143 *(tail.begin() + (n - head.size()));
146 /// \brief Initialize arc iterator to point to the nth arc
148 /// \pre n is in the [0..length() - 1] range
149 ArcIt nthIt(int n) const {
150 return ArcIt(*this, n);
153 /// \brief The first arc of the path
154 const Arc& front() const {
155 return head.empty() ? tail.front() : head.back();
158 /// \brief Add a new arc before the current path
159 void addFront(const Arc& arc) {
163 /// \brief Erase the first arc of the path
169 int halfsize = tail.size() / 2;
170 head.resize(halfsize);
171 std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
173 std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
174 tail.resize(tail.size() - halfsize - 1);
178 /// \brief The last arc of the path
179 const Arc& back() const {
180 return tail.empty() ? head.front() : tail.back();
183 /// \brief Add a new arc behind the current path
184 void addBack(const Arc& arc) {
188 /// \brief Erase the last arc of the path
193 int halfsize = head.size() / 2;
194 tail.resize(halfsize);
195 std::copy(head.begin() + 1, head.begin() + halfsize + 1,
197 std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
198 head.resize(head.size() - halfsize - 1);
202 typedef True BuildTag;
204 template <typename CPath>
205 void build(const CPath& path) {
206 int len = path.length();
208 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
213 template <typename CPath>
214 void buildRev(const CPath& path) {
215 int len = path.length();
217 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
223 typedef std::vector<Arc> Container;
224 Container head, tail;
228 /// \brief A structure for representing directed paths in a digraph.
230 /// A structure for representing directed path in a digraph.
231 /// \tparam _Digraph The digraph type in which the path is.
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
235 /// cannot enumerate the nodes in the path and the zero length paths
236 /// cannot store the source.
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
240 /// erasure is amortized O(1) time. This implementation is faster
241 /// then the \c Path type because it use just one vector for the
243 template <typename _Digraph>
247 typedef _Digraph Digraph;
248 typedef typename Digraph::Arc Arc;
250 /// \brief Default constructor
252 /// Default constructor
255 /// \brief Template copy constructor
257 /// This path can be initialized with any other path type. It just
258 /// makes a copy of the given path.
259 template <typename CPath>
260 SimplePath(const CPath& cpath) {
261 copyPath(*this, cpath);
264 /// \brief Template copy assignment
266 /// This path can be initialized with any other path type. It just
267 /// makes a copy of the given path.
268 template <typename CPath>
269 SimplePath& operator=(const CPath& cpath) {
270 copyPath(*this, cpath);
274 /// \brief Iterator class to iterate on the arcs of the paths
276 /// This class is used to iterate on the arcs of the paths
278 /// Of course it converts to Digraph::Arc
280 friend class SimplePath;
282 /// Default constructor
284 /// Invalid constructor
285 ArcIt(Invalid) : path(0), idx(-1) {}
286 /// \brief Initializate the constructor to the first arc of path
287 ArcIt(const SimplePath &_path)
288 : path(&_path), idx(_path.empty() ? -1 : 0) {}
292 /// Constructor with starting point
293 ArcIt(const SimplePath &_path, int _idx)
294 : idx(_idx), path(&_path) {}
298 ///Conversion to Digraph::Arc
299 operator const Arc&() const {
300 return path->nth(idx);
304 ArcIt& operator++() {
306 if (idx >= path->length()) idx = -1;
310 /// Comparison operator
311 bool operator==(const ArcIt& e) const { return idx==e.idx; }
312 /// Comparison operator
313 bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
314 /// Comparison operator
315 bool operator<(const ArcIt& e) const { return idx<e.idx; }
318 const SimplePath *path;
322 /// \brief Length of the path.
323 int length() const { return data.size(); }
324 /// \brief Return true if the path is empty.
325 bool empty() const { return data.empty(); }
327 /// \brief Reset the path to an empty one.
328 void clear() { data.clear(); }
330 /// \brief The nth arc.
332 /// \pre n is in the [0..length() - 1] range
333 const Arc& nth(int n) const {
337 /// \brief Initializes arc iterator to point to the nth arc.
338 ArcIt nthIt(int n) const {
339 return ArcIt(*this, n);
342 /// \brief The first arc of the path.
343 const Arc& front() const {
347 /// \brief The last arc of the path.
348 const Arc& back() const {
352 /// \brief Add a new arc behind the current path.
353 void addBack(const Arc& arc) {
357 /// \brief Erase the last arc of the path
362 typedef True BuildTag;
364 template <typename CPath>
365 void build(const CPath& path) {
366 int len = path.length();
369 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
375 template <typename CPath>
376 void buildRev(const CPath& path) {
377 int len = path.length();
380 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
387 typedef std::vector<Arc> Container;
392 /// \brief A structure for representing directed paths in a digraph.
394 /// A structure for representing directed path in a digraph.
395 /// \tparam _Digraph The digraph type in which the path is.
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
399 /// cannot enumerate the nodes in the path and the zero length paths
400 /// cannot store the source.
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
404 /// of the arc in the path. The length can be computed in O(n)
405 /// time. The front and back insertion and erasure is O(1) time
406 /// and it can be splited and spliced in O(1) time.
407 template <typename _Digraph>
411 typedef _Digraph Digraph;
412 typedef typename Digraph::Arc Arc;
416 // the std::list<> is incompatible
417 // hard to create invalid iterator
425 std::allocator<Node> alloc;
429 /// \brief Default constructor
431 /// Default constructor
432 ListPath() : first(0), last(0) {}
434 /// \brief Template copy constructor
436 /// This path can be initialized with any other path type. It just
437 /// makes a copy of the given path.
438 template <typename CPath>
439 ListPath(const CPath& cpath) : first(0), last(0) {
440 copyPath(*this, cpath);
443 /// \brief Destructor of the path
445 /// Destructor of the path
450 /// \brief Template copy assignment
452 /// This path can be initialized with any other path type. It just
453 /// makes a copy of the given path.
454 template <typename CPath>
455 ListPath& operator=(const CPath& cpath) {
456 copyPath(*this, cpath);
460 /// \brief Iterator class to iterate on the arcs of the paths
462 /// This class is used to iterate on the arcs of the paths
464 /// Of course it converts to Digraph::Arc
466 friend class ListPath;
468 /// Default constructor
470 /// Invalid constructor
471 ArcIt(Invalid) : path(0), node(0) {}
472 /// \brief Initializate the constructor to the first arc of path
473 ArcIt(const ListPath &_path)
474 : path(&_path), node(_path.first) {}
478 ArcIt(const ListPath &_path, Node *_node)
479 : path(&_path), node(_node) {}
484 ///Conversion to Digraph::Arc
485 operator const Arc&() const {
490 ArcIt& operator++() {
495 /// Comparison operator
496 bool operator==(const ArcIt& e) const { return node==e.node; }
497 /// Comparison operator
498 bool operator!=(const ArcIt& e) const { return node!=e.node; }
499 /// Comparison operator
500 bool operator<(const ArcIt& e) const { return node<e.node; }
503 const ListPath *path;
507 /// \brief The nth arc.
509 /// This function looks for the nth arc in O(n) time.
510 /// \pre n is in the [0..length() - 1] range
511 const Arc& nth(int n) const {
513 for (int i = 0; i < n; ++i) {
519 /// \brief Initializes arc iterator to point to the nth arc.
520 ArcIt nthIt(int n) const {
522 for (int i = 0; i < n; ++i) {
525 return ArcIt(*this, node);
528 /// \brief Length of the path.
539 /// \brief Return true if the path is empty.
540 bool empty() const { return first == 0; }
542 /// \brief Reset the path to an empty one.
546 alloc.destroy(first);
547 alloc.deallocate(first, 1);
552 /// \brief The first arc of the path
553 const Arc& front() const {
557 /// \brief Add a new arc before the current path
558 void addFront(const Arc& arc) {
559 Node *node = alloc.allocate(1);
560 alloc.construct(node, Node());
572 /// \brief Erase the first arc of the path
582 alloc.deallocate(node, 1);
585 /// \brief The last arc of the path.
586 const Arc& back() const {
590 /// \brief Add a new arc behind the current path.
591 void addBack(const Arc& arc) {
592 Node *node = alloc.allocate(1);
593 alloc.construct(node, Node());
605 /// \brief Erase the last arc of the path
615 alloc.deallocate(node, 1);
618 /// \brief Splice a path to the back of the current path.
620 /// It splices \c tpath to the back of the current path and \c
621 /// tpath becomes empty. The time complexity of this function is
623 void spliceBack(ListPath& tpath) {
626 last->next = tpath.first;
627 tpath.first->prev = last;
634 tpath.first = tpath.last = 0;
637 /// \brief Splice a path to the front of the current path.
639 /// It splices \c tpath before the current path and \c tpath
640 /// becomes empty. The time complexity of this function
642 void spliceFront(ListPath& tpath) {
645 first->prev = tpath.last;
646 tpath.last->next = first;
653 tpath.first = tpath.last = 0;
656 /// \brief Splice a path into the current path.
658 /// It splices the \c tpath into the current path before the
659 /// position of \c it iterator and \c tpath becomes empty. The
660 /// time complexity of this function is O(1). If the \c it is
661 /// \c INVALID then it will splice behind the current path.
662 void splice(ArcIt it, ListPath& tpath) {
665 tpath.first->prev = it.node->prev;
667 it.node->prev->next = tpath.first;
671 it.node->prev = tpath.last;
672 tpath.last->next = it.node;
677 last->next = tpath.first;
678 tpath.first->prev = last;
686 tpath.first = tpath.last = 0;
689 /// \brief Split the current path.
691 /// It splits the current path into two parts. The part before
692 /// the iterator \c it will remain in the current path and the part
694 /// \c it will put into \c tpath. If \c tpath have arcs
695 /// before the operation they are removed first. The time
696 /// complexity of this function is O(1) plus the the time of emtying
697 /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
698 void split(ArcIt it, ListPath& tpath) {
701 tpath.first = it.node;
704 last = it.node->prev;
714 typedef True BuildTag;
716 template <typename CPath>
717 void build(const CPath& path) {
718 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
723 template <typename CPath>
724 void buildRev(const CPath& path) {
725 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
732 /// \brief A structure for representing directed paths in a digraph.
734 /// A structure for representing directed path in a digraph.
735 /// \tparam _Digraph The digraph type in which the path is.
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
739 /// cannot enumerate the nodes in the path and the source node of
740 /// a zero length path is undefined.
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
746 /// Being the the most memory efficient path type in LEMON,
747 /// it is intented to be
748 /// used when you want to store a large number of paths.
749 template <typename _Digraph>
753 typedef _Digraph Digraph;
754 typedef typename Digraph::Arc Arc;
756 /// \brief Default constructor
758 /// Default constructor
759 StaticPath() : len(0), arcs(0) {}
761 /// \brief Template copy constructor
763 /// This path can be initialized from any other path type.
764 template <typename CPath>
765 StaticPath(const CPath& cpath) : arcs(0) {
766 copyPath(*this, cpath);
769 /// \brief Destructor of the path
771 /// Destructor of the path
773 if (arcs) delete[] arcs;
776 /// \brief Template copy assignment
778 /// This path can be made equal to any other path type. It simply
779 /// makes a copy of the given path.
780 template <typename CPath>
781 StaticPath& operator=(const CPath& cpath) {
782 copyPath(*this, cpath);
786 /// \brief Iterator class to iterate on the arcs of the paths
788 /// This class is used to iterate on the arcs of the paths
790 /// Of course it converts to Digraph::Arc
792 friend class StaticPath;
794 /// Default constructor
796 /// Invalid constructor
797 ArcIt(Invalid) : path(0), idx(-1) {}
798 /// Initializate the constructor to the first arc of path
799 ArcIt(const StaticPath &_path)
800 : path(&_path), idx(_path.empty() ? -1 : 0) {}
804 /// Constructor with starting point
805 ArcIt(const StaticPath &_path, int _idx)
806 : idx(_idx), path(&_path) {}
810 ///Conversion to Digraph::Arc
811 operator const Arc&() const {
812 return path->nth(idx);
816 ArcIt& operator++() {
818 if (idx >= path->length()) idx = -1;
822 /// Comparison operator
823 bool operator==(const ArcIt& e) const { return idx==e.idx; }
824 /// Comparison operator
825 bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
826 /// Comparison operator
827 bool operator<(const ArcIt& e) const { return idx<e.idx; }
830 const StaticPath *path;
834 /// \brief The nth arc.
836 /// \pre n is in the [0..length() - 1] range
837 const Arc& nth(int n) const {
841 /// \brief The arc iterator pointing to the nth arc.
842 ArcIt nthIt(int n) const {
843 return ArcIt(*this, n);
846 /// \brief The length of the path.
847 int length() const { return len; }
849 /// \brief Return true when the path is empty.
850 int empty() const { return len == 0; }
852 /// \break Erase all arcs in the digraph.
855 if (arcs) delete[] arcs;
859 /// \brief The first arc of the path.
860 const Arc& front() const {
864 /// \brief The last arc of the path.
865 const Arc& back() const {
866 return arcs[len - 1];
870 typedef True BuildTag;
872 template <typename CPath>
873 void build(const CPath& path) {
877 for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
883 template <typename CPath>
884 void buildRev(const CPath& path) {
888 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
899 ///////////////////////////////////////////////////////////////////////
900 // Additional utilities
901 ///////////////////////////////////////////////////////////////////////
903 namespace _path_bits {
905 template <typename Path, typename Enable = void>
906 struct RevPathTagIndicator {
907 static const bool value = false;
910 template <typename Path>
911 struct RevPathTagIndicator<
913 typename enable_if<typename Path::RevPathTag, void>::type
915 static const bool value = true;
918 template <typename Path, typename Enable = void>
919 struct BuildTagIndicator {
920 static const bool value = false;
923 template <typename Path>
924 struct BuildTagIndicator<
926 typename enable_if<typename Path::BuildTag, void>::type
928 static const bool value = true;
931 template <typename Target, typename Source,
932 bool buildEnable = BuildTagIndicator<Target>::value,
933 bool revEnable = RevPathTagIndicator<Source>::value>
934 struct PathCopySelector {
935 static void copy(Target& target, const Source& source) {
937 for (typename Source::ArcIt it(source); it != INVALID; ++it) {
943 template <typename Target, typename Source>
944 struct PathCopySelector<Target, Source, false, true> {
945 static void copy(Target& target, const Source& source) {
947 for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
953 template <typename Target, typename Source>
954 struct PathCopySelector<Target, Source, true, false> {
955 static void copy(Target& target, const Source& source) {
957 target.build(source);
961 template <typename Target, typename Source>
962 struct PathCopySelector<Target, Source, true, true> {
963 static void copy(Target& target, const Source& source) {
965 target.buildRev(source);
972 /// \brief Make a copy of a path.
974 /// This function makes a copy of a path.
975 template <typename Target, typename Source>
976 void copyPath(Target& target, const Source& source) {
977 checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
978 _path_bits::PathCopySelector<Target, Source>::copy(target, source);
981 /// \brief Check the consistency of a path.
983 /// This function checks that the target of each arc is the same
984 /// as the source of the next one.
986 template <typename Digraph, typename Path>
987 bool checkPath(const Digraph& digraph, const Path& path) {
988 typename Path::ArcIt it(path);
989 if (it == INVALID) return true;
990 typename Digraph::Node node = digraph.target(it);
992 while (it != INVALID) {
993 if (digraph.source(it) != node) return false;
994 node = digraph.target(it);
1000 /// \brief The source of a path
1002 /// This function returns the source of the given path.
1003 template <typename Digraph, typename Path>
1004 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1005 return digraph.source(path.front());
1008 /// \brief The target of a path
1010 /// This function returns the target of the given path.
1011 template <typename Digraph, typename Path>
1012 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1013 return digraph.target(path.back());
1016 /// \brief Class which helps to iterate through the nodes of a path
1018 /// In a sense, the path can be treated as a list of arcs. The
1019 /// lemon path type stores only this list. As a consequence, it
1020 /// cannot enumerate the nodes in the path and the zero length paths
1021 /// cannot have a source node.
1023 /// This class implements the node iterator of a path structure. To
1024 /// provide this feature, the underlying digraph should be passed to
1025 /// the constructor of the iterator.
1026 template <typename Path>
1029 const typename Path::Digraph *_digraph;
1030 typename Path::ArcIt _it;
1031 typename Path::Digraph::Node _nd;
1035 typedef typename Path::Digraph Digraph;
1036 typedef typename Digraph::Node Node;
1038 /// Default constructor
1040 /// Invalid constructor
1042 : _digraph(0), _it(INVALID), _nd(INVALID) {}
1044 PathNodeIt(const Digraph& digraph, const Path& path)
1045 : _digraph(&digraph), _it(path) {
1046 _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1049 PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1050 : _digraph(&digraph), _it(path), _nd(src) {}
1052 ///Conversion to Digraph::Node
1053 operator Node() const {
1058 PathNodeIt& operator++() {
1059 if (_it == INVALID) _nd = INVALID;
1061 _nd = _digraph->target(_it);
1067 /// Comparison operator
1068 bool operator==(const PathNodeIt& n) const {
1069 return _it == n._it && _nd == n._nd;
1071 /// Comparison operator
1072 bool operator!=(const PathNodeIt& n) const {
1073 return _it != n._it || _nd != n._nd;
1075 /// Comparison operator
1076 bool operator<(const PathNodeIt& n) const {
1077 return (_it < n._it && _nd != INVALID);
1084 } // namespace lemon
1086 #endif // LEMON_PATH_H