|
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 of copy of a path. |
|
94 /// |
|
95 /// Make of 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 Checks the path's consistency. |
|
103 /// |
|
104 /// Checks that each arc's target is the next's source. |
|
105 /// |
|
106 template <typename Digraph, typename Path> |
|
107 bool checkPath(const Digraph& digraph, const Path& path) { |
|
108 typename Path::ArcIt it(path); |
|
109 if (it == INVALID) return true; |
|
110 typename Digraph::Node node = digraph.target(it); |
|
111 ++it; |
|
112 while (it != INVALID) { |
|
113 if (digraph.source(it) != node) return false; |
|
114 node = digraph.target(it); |
|
115 ++it; |
|
116 } |
|
117 return true; |
|
118 } |
|
119 |
|
120 /// \brief Gives back the source of the path |
|
121 /// |
|
122 /// Gives back the source of the path. |
|
123 template <typename Digraph, typename Path> |
|
124 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { |
|
125 return digraph.source(path.front()); |
|
126 } |
|
127 |
|
128 /// \brief Gives back the target of the path |
|
129 /// |
|
130 /// Gives back the target of the path. |
|
131 template <typename Digraph, typename Path> |
|
132 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { |
|
133 return digraph.target(path.back()); |
|
134 } |
|
135 |
|
136 /// \brief Class which helps to iterate the nodes of a path |
|
137 /// |
|
138 /// In a sense, the path can be treated as a list of arcs. The |
|
139 /// lemon path type stores just this list. As a consequence it |
|
140 /// cannot enumerate the nodes in the path and the zero length paths |
|
141 /// cannot store the node. |
|
142 /// |
|
143 /// This class implements the node iterator of a path structure. To |
|
144 /// provide this feature, the underlying digraph should be given to |
|
145 /// the constructor of the iterator. |
|
146 template <typename Path> |
|
147 class PathNodeIt { |
|
148 private: |
|
149 const typename Path::Digraph *_digraph; |
|
150 typename Path::ArcIt _it; |
|
151 typename Path::Digraph::Node _nd; |
|
152 |
|
153 public: |
|
154 |
|
155 typedef typename Path::Digraph Digraph; |
|
156 typedef typename Digraph::Node Node; |
|
157 |
|
158 /// Default constructor |
|
159 PathNodeIt() {} |
|
160 /// Invalid constructor |
|
161 PathNodeIt(Invalid) |
|
162 : _digraph(0), _it(INVALID), _nd(INVALID) {} |
|
163 /// Constructor |
|
164 PathNodeIt(const Digraph& digraph, const Path& path) |
|
165 : _digraph(&digraph), _it(path) { |
|
166 _nd = (_it != INVALID ? _digraph->source(_it) : INVALID); |
|
167 } |
|
168 /// Constructor |
|
169 PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) |
|
170 : _digraph(&digraph), _it(path), _nd(src) {} |
|
171 |
|
172 ///Conversion to Digraph::Node |
|
173 operator Node() const { |
|
174 return _nd; |
|
175 } |
|
176 |
|
177 /// Next node |
|
178 PathNodeIt& operator++() { |
|
179 if (_it == INVALID) _nd = INVALID; |
|
180 else { |
|
181 _nd = _digraph->target(_it); |
|
182 ++_it; |
|
183 } |
|
184 return *this; |
|
185 } |
|
186 |
|
187 /// Comparison operator |
|
188 bool operator==(const PathNodeIt& n) const { |
|
189 return _it == n._it && _nd == n._nd; |
|
190 } |
|
191 /// Comparison operator |
|
192 bool operator!=(const PathNodeIt& n) const { |
|
193 return _it != n._it || _nd != n._nd; |
|
194 } |
|
195 /// Comparison operator |
|
196 bool operator<(const PathNodeIt& n) const { |
|
197 return (_it < n._it && _nd != INVALID); |
|
198 } |
|
199 |
|
200 }; |
|
201 |
|
202 } |
|
203 |
|
204 #endif |