1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
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. |
|
12 * |
|
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 |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 ///\ingroup paths |
|
20 ///\file |
|
21 ///\brief Classes for representing paths in digraphs. |
|
22 /// |
|
23 |
|
24 #ifndef LEMON_PATH_UTILS_H |
|
25 #define LEMON_PATH_UTILS_H |
|
26 |
|
27 #include <lemon/concepts/path.h> |
|
28 |
|
29 namespace lemon { |
|
30 |
|
31 namespace _path_bits { |
|
32 |
|
33 template <typename Path, typename Enable = void> |
|
34 struct RevTagIndicator { |
|
35 static const bool value = false; |
|
36 }; |
|
37 |
|
38 template <typename Digraph> |
|
39 struct RevTagIndicator< |
|
40 Digraph, |
|
41 typename enable_if<typename Digraph::RevTag, void>::type |
|
42 > { |
|
43 static const bool value = true; |
|
44 }; |
|
45 |
|
46 template <typename Target, typename Source, |
|
47 typename BuildEnable = void, typename RevEnable = void> |
|
48 struct PathCopySelector { |
|
49 static void copy(Target& target, const Source& source) { |
|
50 target.clear(); |
|
51 for (typename Source::ArcIt it(source); it != INVALID; ++it) { |
|
52 target.addBack(it); |
|
53 } |
|
54 } |
|
55 }; |
|
56 |
|
57 template <typename Target, typename Source, typename BuildEnable> |
|
58 struct PathCopySelector< |
|
59 Target, Source, BuildEnable, |
|
60 typename enable_if<typename Source::RevPathTag, void>::type> { |
|
61 static void copy(Target& target, const Source& source) { |
|
62 target.clear(); |
|
63 for (typename Source::RevArcIt it(source); it != INVALID; ++it) { |
|
64 target.addFront(it); |
|
65 } |
|
66 } |
|
67 }; |
|
68 |
|
69 template <typename Target, typename Source, typename RevEnable> |
|
70 struct PathCopySelector< |
|
71 Target, Source, |
|
72 typename enable_if<typename Target::BuildTag, void>::type, RevEnable> { |
|
73 static void copy(Target& target, const Source& source) { |
|
74 target.clear(); |
|
75 target.build(source); |
|
76 } |
|
77 }; |
|
78 |
|
79 template <typename Target, typename Source> |
|
80 struct PathCopySelector< |
|
81 Target, Source, |
|
82 typename enable_if<typename Target::BuildTag, void>::type, |
|
83 typename enable_if<typename Source::RevPathTag, void>::type> { |
|
84 static void copy(Target& target, const Source& source) { |
|
85 target.clear(); |
|
86 target.buildRev(source); |
|
87 } |
|
88 }; |
|
89 |
|
90 } |
|
91 |
|
92 |
|
93 /// \brief Make a copy of a path. |
|
94 /// |
|
95 /// This function makes a copy of a path. |
|
96 template <typename Target, typename Source> |
|
97 void copyPath(Target& target, const Source& source) { |
|
98 checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>(); |
|
99 _path_bits::PathCopySelector<Target, Source>::copy(target, source); |
|
100 } |
|
101 |
|
102 /// \brief Check the consistency of a path. |
|
103 /// |
|
104 /// This function checks that the target of each arc is the same |
|
105 /// as the source of the next one. |
|
106 /// |
|
107 template <typename Digraph, typename Path> |
|
108 bool checkPath(const Digraph& digraph, const Path& path) { |
|
109 typename Path::ArcIt it(path); |
|
110 if (it == INVALID) return true; |
|
111 typename Digraph::Node node = digraph.target(it); |
|
112 ++it; |
|
113 while (it != INVALID) { |
|
114 if (digraph.source(it) != node) return false; |
|
115 node = digraph.target(it); |
|
116 ++it; |
|
117 } |
|
118 return true; |
|
119 } |
|
120 |
|
121 /// \brief The source of a path |
|
122 /// |
|
123 /// This function returns the source of the given path. |
|
124 template <typename Digraph, typename Path> |
|
125 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { |
|
126 return digraph.source(path.front()); |
|
127 } |
|
128 |
|
129 /// \brief The target of a path |
|
130 /// |
|
131 /// This function returns the target of the given path. |
|
132 template <typename Digraph, typename Path> |
|
133 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { |
|
134 return digraph.target(path.back()); |
|
135 } |
|
136 |
|
137 /// \brief Class which helps to iterate through the nodes of a path |
|
138 /// |
|
139 /// In a sense, the path can be treated as a list of arcs. The |
|
140 /// lemon path type stores only this list. As a consequence, it |
|
141 /// cannot enumerate the nodes in the path and the zero length paths |
|
142 /// cannot have a source node. |
|
143 /// |
|
144 /// This class implements the node iterator of a path structure. To |
|
145 /// provide this feature, the underlying digraph should be passed to |
|
146 /// the constructor of the iterator. |
|
147 template <typename Path> |
|
148 class PathNodeIt { |
|
149 private: |
|
150 const typename Path::Digraph *_digraph; |
|
151 typename Path::ArcIt _it; |
|
152 typename Path::Digraph::Node _nd; |
|
153 |
|
154 public: |
|
155 |
|
156 typedef typename Path::Digraph Digraph; |
|
157 typedef typename Digraph::Node Node; |
|
158 |
|
159 /// Default constructor |
|
160 PathNodeIt() {} |
|
161 /// Invalid constructor |
|
162 PathNodeIt(Invalid) |
|
163 : _digraph(0), _it(INVALID), _nd(INVALID) {} |
|
164 /// Constructor |
|
165 PathNodeIt(const Digraph& digraph, const Path& path) |
|
166 : _digraph(&digraph), _it(path) { |
|
167 _nd = (_it != INVALID ? _digraph->source(_it) : INVALID); |
|
168 } |
|
169 /// Constructor |
|
170 PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) |
|
171 : _digraph(&digraph), _it(path), _nd(src) {} |
|
172 |
|
173 ///Conversion to Digraph::Node |
|
174 operator Node() const { |
|
175 return _nd; |
|
176 } |
|
177 |
|
178 /// Next node |
|
179 PathNodeIt& operator++() { |
|
180 if (_it == INVALID) _nd = INVALID; |
|
181 else { |
|
182 _nd = _digraph->target(_it); |
|
183 ++_it; |
|
184 } |
|
185 return *this; |
|
186 } |
|
187 |
|
188 /// Comparison operator |
|
189 bool operator==(const PathNodeIt& n) const { |
|
190 return _it == n._it && _nd == n._nd; |
|
191 } |
|
192 /// Comparison operator |
|
193 bool operator!=(const PathNodeIt& n) const { |
|
194 return _it != n._it || _nd != n._nd; |
|
195 } |
|
196 /// Comparison operator |
|
197 bool operator<(const PathNodeIt& n) const { |
|
198 return (_it < n._it && _nd != INVALID); |
|
199 } |
|
200 |
|
201 }; |
|
202 |
|
203 } |
|
204 |
|
205 #endif |
|