Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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 graphs.
30 #include <lemon/path_utils.h>
31 #include <lemon/error.h>
32 #include <lemon/bits/invalid.h>
40 /// \brief A structure for representing directed paths in a graph.
42 /// A structure for representing directed path in a graph.
43 /// \param Graph The graph type in which the path is.
45 /// In a sense, the path can be treated as a list of edges. The
46 /// lemon path type stores just this list. As a consequence it
47 /// cannot enumerate the nodes in the path and the zero length paths
48 /// cannot store the source.
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 erasure is amortized O(1) time. The
53 /// impelementation is based on two opposite organized vectors.
54 template <typename _Graph>
59 typedef typename Graph::Edge Edge;
61 /// \brief Default constructor
63 /// Default constructor
66 /// \brief Template copy constructor
68 /// This path can be initialized with any other path type. It just
69 /// makes a copy of the given path.
70 template <typename CPath>
71 Path(const CPath& cpath) {
72 copyPath(*this, cpath);
75 /// \brief Template copy assignment
77 /// This path can be initialized with any other path type. It just
78 /// makes a copy of the given path.
79 template <typename CPath>
80 Path& operator=(const CPath& cpath) {
81 copyPath(*this, cpath);
85 /// \brief Lemon style iterator for path edges
87 /// This class is used to iterate on the edges of the paths.
91 /// \brief Default constructor
93 /// \brief Invalid constructor
94 EdgeIt(Invalid) : path(0), idx(-1) {}
95 /// \brief Initializate the constructor to the first edge of path
96 EdgeIt(const Path &_path)
97 : path(&_path), idx(_path.empty() ? -1 : 0) {}
101 EdgeIt(const Path &_path, int _idx)
102 : path(&_path), idx(_idx) {}
106 /// \brief Conversion to Edge
107 operator const Edge&() const {
108 return path->nth(idx);
112 EdgeIt& operator++() {
114 if (idx >= path->length()) idx = -1;
118 /// \brief Comparison operator
119 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
120 /// \brief Comparison operator
121 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
122 /// \brief Comparison operator
123 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
130 /// \brief Length of the path.
131 int length() const { return head.size() + tail.size(); }
132 /// \brief Returns whether the path is empty.
133 bool empty() const { return head.empty() && tail.empty(); }
135 /// \brief Resets the path to an empty path.
136 void clear() { head.clear(); tail.clear(); }
138 /// \brief Gives back the nth edge.
140 /// \pre n is in the [0..length() - 1] range
141 const Edge& nth(int n) const {
142 return n < int(head.size()) ? *(head.rbegin() + n) :
143 *(tail.begin() + (n - head.size()));
146 /// \brief Initializes edge iterator to point to the nth edge
148 /// \pre n is in the [0..length() - 1] range
149 EdgeIt nthIt(int n) const {
150 return EdgeIt(*this, n);
153 /// \brief Gives back the first edge of the path
154 const Edge& front() const {
155 return head.empty() ? tail.front() : head.back();
158 /// \brief Add a new edge before the current path
159 void addFront(const Edge& edge) {
160 head.push_back(edge);
163 /// \brief Erase the first edge 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 Gives back the last edge of the path
179 const Edge& back() const {
180 return tail.empty() ? head.front() : tail.back();
183 /// \brief Add a new edge behind the current path
184 void addBack(const Edge& edge) {
185 tail.push_back(edge);
188 /// \brief Erase the last edge 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);
204 typedef True BuildTag;
206 template <typename CPath>
207 void build(const CPath& path) {
208 int len = path.length();
210 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
215 template <typename CPath>
216 void buildRev(const CPath& path) {
217 int len = path.length();
219 for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
225 typedef std::vector<Edge> Container;
226 Container head, tail;
230 /// \brief A structure for representing directed paths in a graph.
232 /// A structure for representing directed path in a graph.
233 /// \param Graph The graph type in which the path is.
235 /// In a sense, the path can be treated as a list of edges. The
236 /// lemon path type stores just this list. As a consequence it
237 /// cannot enumerate the nodes in the path and the zero length paths
238 /// cannot store the source.
240 /// This implementation is a just back insertable and erasable path
241 /// type. It can be indexed in O(1) time. The back insertion and
242 /// erasure is amortized O(1) time. This implementation is faster
243 /// then the \c Path type because it use just one vector for the
245 template <typename _Graph>
249 typedef _Graph Graph;
250 typedef typename Graph::Edge Edge;
252 /// \brief Default constructor
254 /// Default constructor
257 /// \brief Template copy constructor
259 /// This path can be initialized with any other path type. It just
260 /// makes a copy of the given path.
261 template <typename CPath>
262 SimplePath(const CPath& cpath) {
263 copyPath(*this, cpath);
266 /// \brief Template copy assignment
268 /// This path can be initialized with any other path type. It just
269 /// makes a copy of the given path.
270 template <typename CPath>
271 SimplePath& operator=(const CPath& cpath) {
272 copyPath(*this, cpath);
276 /// \brief Iterator class to iterate on the edges of the paths
278 /// This class is used to iterate on the edges of the paths
280 /// Of course it converts to Graph::Edge
282 friend class SimplePath;
284 /// Default constructor
286 /// Invalid constructor
287 EdgeIt(Invalid) : path(0), idx(-1) {}
288 /// \brief Initializate the constructor to the first edge of path
289 EdgeIt(const SimplePath &_path)
290 : path(&_path), idx(_path.empty() ? -1 : 0) {}
294 /// Constructor with starting point
295 EdgeIt(const SimplePath &_path, int _idx)
296 : idx(_idx), path(&_path) {}
300 ///Conversion to Graph::Edge
301 operator const Edge&() const {
302 return path->nth(idx);
306 EdgeIt& operator++() {
308 if (idx >= path->length()) idx = -1;
312 /// Comparison operator
313 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
314 /// Comparison operator
315 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
316 /// Comparison operator
317 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
320 const SimplePath *path;
324 /// \brief Length of the path.
325 int length() const { return data.size(); }
326 /// \brief Returns whether the path is empty.
327 bool empty() const { return data.empty(); }
329 /// \brief Resets the path to an empty path.
330 void clear() { data.clear(); }
332 /// \brief Gives back the nth edge.
334 /// \pre n is in the [0..length() - 1] range
335 const Edge& nth(int n) const {
339 /// \brief Initializes edge iterator to point to the nth edge.
340 EdgeIt nthIt(int n) const {
341 return EdgeIt(*this, n);
344 /// \brief Gives back the first edge of the path.
345 const Edge& front() const {
349 /// \brief Gives back the last edge of the path.
350 const Edge& back() const {
354 /// \brief Add a new edge behind the current path.
355 void addBack(const Edge& edge) {
356 data.push_back(edge);
359 /// \brief Erase the last edge of the path
364 typedef True BuildTag;
366 template <typename CPath>
367 void build(const CPath& path) {
368 int len = path.length();
371 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
377 template <typename CPath>
378 void buildRev(const CPath& path) {
379 int len = path.length();
382 for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
389 typedef std::vector<Edge> Container;
394 /// \brief A structure for representing directed paths in a graph.
396 /// A structure for representing directed path in a graph.
397 /// \param Graph The graph type in which the path is.
399 /// In a sense, the path can be treated as a list of edges. The
400 /// lemon path type stores just this list. As a consequence it
401 /// cannot enumerate the nodes in the path and the zero length paths
402 /// cannot store the source.
404 /// This implementation is a back and front insertable and erasable
405 /// path type. It can be indexed in O(k) time, where k is the rank
406 /// of the edge in the path. The length can be computed in O(n)
407 /// time. The front and back insertion and erasure is O(1) time
408 /// and it can be splited and spliced in O(1) time.
409 template <typename _Graph>
413 typedef _Graph Graph;
414 typedef typename Graph::Edge Edge;
418 // the std::list<> is incompatible
419 // hard to create invalid iterator
427 std::allocator<Node> alloc;
431 /// \brief Default constructor
433 /// Default constructor
434 ListPath() : first(0), last(0) {}
436 /// \brief Template copy constructor
438 /// This path can be initialized with any other path type. It just
439 /// makes a copy of the given path.
440 template <typename CPath>
441 ListPath(const CPath& cpath) : first(0), last(0) {
442 copyPath(*this, cpath);
445 /// \brief Destructor of the path
447 /// Destructor of the path
452 /// \brief Template copy assignment
454 /// This path can be initialized with any other path type. It just
455 /// makes a copy of the given path.
456 template <typename CPath>
457 ListPath& operator=(const CPath& cpath) {
458 copyPath(*this, cpath);
462 /// \brief Iterator class to iterate on the edges of the paths
464 /// This class is used to iterate on the edges of the paths
466 /// Of course it converts to Graph::Edge
468 friend class ListPath;
470 /// Default constructor
472 /// Invalid constructor
473 EdgeIt(Invalid) : path(0), node(0) {}
474 /// \brief Initializate the constructor to the first edge of path
475 EdgeIt(const ListPath &_path)
476 : path(&_path), node(_path.first) {}
480 EdgeIt(const ListPath &_path, Node *_node)
481 : path(&_path), node(_node) {}
486 ///Conversion to Graph::Edge
487 operator const Edge&() const {
492 EdgeIt& operator++() {
497 /// Comparison operator
498 bool operator==(const EdgeIt& e) const { return node==e.node; }
499 /// Comparison operator
500 bool operator!=(const EdgeIt& e) const { return node!=e.node; }
501 /// Comparison operator
502 bool operator<(const EdgeIt& e) const { return node<e.node; }
505 const ListPath *path;
509 /// \brief Gives back the nth edge.
511 /// Gives back the nth edge in O(n) time.
512 /// \pre n is in the [0..length() - 1] range
513 const Edge& nth(int n) const {
515 for (int i = 0; i < n; ++i) {
521 /// \brief Initializes edge iterator to point to the nth edge.
522 EdgeIt nthIt(int n) const {
524 for (int i = 0; i < n; ++i) {
527 return EdgeIt(*this, node);
530 /// \brief Length of the path.
541 /// \brief Returns whether the path is empty.
542 bool empty() const { return first == 0; }
544 /// \brief Resets the path to an empty path.
548 alloc.destroy(first);
549 alloc.deallocate(first, 1);
554 /// \brief Gives back the first edge of the path
555 const Edge& front() const {
559 /// \brief Add a new edge before the current path
560 void addFront(const Edge& edge) {
561 Node *node = alloc.allocate(1);
562 alloc.construct(node, Node());
574 /// \brief Erase the first edge of the path
584 alloc.deallocate(node, 1);
587 /// \brief Gives back the last edge of the path.
588 const Edge& back() const {
592 /// \brief Add a new edge behind the current path.
593 void addBack(const Edge& edge) {
594 Node *node = alloc.allocate(1);
595 alloc.construct(node, Node());
607 /// \brief Erase the last edge of the path
617 alloc.deallocate(node, 1);
620 /// \brief Splicing the given path to the current path.
622 /// It splices the \c tpath to the back of the current path and \c
623 /// tpath becomes empty. The time complexity of this function is
625 void spliceBack(ListPath& tpath) {
628 last->next = tpath.first;
629 tpath.first->prev = last;
636 tpath.first = tpath.last = 0;
639 /// \brief Splicing the given path to the current path.
641 /// It splices the \c tpath before the current path and \c tpath
642 /// becomes empty. The time complexity of this function
644 void spliceFront(ListPath& tpath) {
647 first->prev = tpath.last;
648 tpath.last->next = first;
655 tpath.first = tpath.last = 0;
658 /// \brief Splicing the given path into the current path.
660 /// It splices the \c tpath into the current path before the
661 /// position of \c it iterator and \c tpath becomes empty. The
662 /// time complexity of this function is O(1). If the \c it is \c
663 /// INVALID then it will splice behind the current path.
664 void splice(EdgeIt it, ListPath& tpath) {
667 tpath.first->prev = it.node->prev;
669 it.node->prev->next = tpath.first;
673 it.node->prev = tpath.last;
674 tpath.last->next = it.node;
679 last->next = tpath.first;
680 tpath.first->prev = last;
688 tpath.first = tpath.last = 0;
691 /// \brief Spliting the current path.
693 /// It splits the current path into two parts. The part before \c
694 /// it iterator will remain in the current path and the part from
695 /// the it will put into the \c tpath. If the \c tpath had edges
696 /// before the operation they will be removed first. The time
697 /// complexity of this function is O(1) plus the clearing of \c
698 /// tpath. If the \c it is \c INVALID then it just clears \c
700 void split(EdgeIt it, ListPath& tpath) {
703 tpath.first = it.node;
706 last = it.node->prev;
716 typedef True BuildTag;
718 template <typename CPath>
719 void build(const CPath& path) {
720 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
725 template <typename CPath>
726 void buildRev(const CPath& path) {
727 for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
734 /// \brief A structure for representing directed paths in a graph.
736 /// A structure for representing directed path in a graph.
737 /// \param Graph The graph type in which the path is.
739 /// In a sense, the path can be treated as a list of edges. The
740 /// lemon path type stores just this list. As a consequence it
741 /// cannot enumerate the nodes in the path and the zero length paths
742 /// cannot store the source.
744 /// This implementation is completly static, so it cannot be
745 /// modified exclude the assign an other path. It is intented to be
746 /// used when you want to store a large number of paths because it is
747 /// the most memory efficient path type in the lemon.
748 template <typename _Graph>
752 typedef _Graph Graph;
753 typedef typename Graph::Edge Edge;
755 /// \brief Default constructor
757 /// Default constructor
758 StaticPath() : len(0), edges(0) {}
760 /// \brief Template copy constructor
762 /// This path can be initialized with any other path type. It just
763 /// makes a copy of the given path.
764 template <typename CPath>
765 StaticPath(const CPath& cpath) : edges(0) {
766 copyPath(*this, cpath);
769 /// \brief Destructor of the path
771 /// Destructor of the path
773 if (edges) delete[] edges;
776 /// \brief Template copy assignment
778 /// This path can be initialized with any other path type. It just
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 edges of the paths
788 /// This class is used to iterate on the edges of the paths
790 /// Of course it converts to Graph::Edge
792 friend class StaticPath;
794 /// Default constructor
796 /// Invalid constructor
797 EdgeIt(Invalid) : path(0), idx(-1) {}
798 /// Initializate the constructor to the first edge of path
799 EdgeIt(const StaticPath &_path)
800 : path(&_path), idx(_path.empty() ? -1 : 0) {}
804 /// Constructor with starting point
805 EdgeIt(const StaticPath &_path, int _idx)
806 : idx(_idx), path(&_path) {}
810 ///Conversion to Graph::Edge
811 operator const Edge&() const {
812 return path->nth(idx);
816 EdgeIt& operator++() {
818 if (idx >= path->length()) idx = -1;
822 /// Comparison operator
823 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
824 /// Comparison operator
825 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
826 /// Comparison operator
827 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
830 const StaticPath *path;
834 /// \brief Gives back the nth edge.
836 /// \pre n is in the [0..length() - 1] range
837 const Edge& nth(int n) const {
841 /// \brief Initializes edge iterator to point to the nth edge.
842 EdgeIt nthIt(int n) const {
843 return EdgeIt(*this, n);
846 /// \brief Gives back the length of the path.
847 int length() const { return len; }
849 /// \brief Returns true when the path is empty.
850 int empty() const { return len == 0; }
852 /// \break Erase all edge in the graph.
855 if (edges) delete[] edges;
859 /// \brief Gives back the first edge of the path.
860 const Edge& front() const {
864 /// \brief Gives back the last edge of the path.
865 const Edge& back() const {
866 return edges[len - 1];
870 typedef True BuildTag;
872 template <typename CPath>
873 void build(const CPath& path) {
875 edges = new Edge[len];
877 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
883 template <typename CPath>
884 void buildRev(const CPath& path) {
886 edges = new Edge[len];
888 for (typename CPath::RevEdgeIt it(path); it != INVALID; ++it) {
903 #endif // LEMON_PATH_H