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