deba@430
|
1 |
/* -*- C++ -*-
|
deba@430
|
2 |
*
|
deba@430
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
deba@430
|
4 |
*
|
deba@430
|
5 |
* Copyright (C) 2003-2008
|
deba@430
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@430
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@430
|
8 |
*
|
deba@430
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@430
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@430
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@430
|
12 |
*
|
deba@430
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@430
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@430
|
15 |
* purpose.
|
deba@430
|
16 |
*
|
deba@430
|
17 |
*/
|
deba@430
|
18 |
|
deba@430
|
19 |
#ifndef LEMON_DIGRAPH_ADAPTOR_H
|
deba@430
|
20 |
#define LEMON_DIGRAPH_ADAPTOR_H
|
deba@430
|
21 |
|
deba@430
|
22 |
///\ingroup graph_adaptors
|
deba@430
|
23 |
///\file
|
deba@430
|
24 |
///\brief Several digraph adaptors.
|
deba@430
|
25 |
///
|
deba@430
|
26 |
///This file contains several useful digraph adaptor functions.
|
deba@430
|
27 |
|
deba@430
|
28 |
#include <lemon/core.h>
|
deba@430
|
29 |
#include <lemon/maps.h>
|
deba@430
|
30 |
#include <lemon/bits/variant.h>
|
deba@430
|
31 |
|
deba@430
|
32 |
#include <lemon/bits/base_extender.h>
|
deba@430
|
33 |
#include <lemon/bits/graph_adaptor_extender.h>
|
deba@430
|
34 |
#include <lemon/bits/graph_extender.h>
|
deba@430
|
35 |
#include <lemon/tolerance.h>
|
deba@430
|
36 |
|
deba@430
|
37 |
#include <algorithm>
|
deba@430
|
38 |
|
deba@430
|
39 |
namespace lemon {
|
deba@430
|
40 |
|
deba@430
|
41 |
///\brief Base type for the Digraph Adaptors
|
deba@430
|
42 |
///
|
deba@430
|
43 |
///Base type for the Digraph Adaptors
|
deba@430
|
44 |
///
|
deba@430
|
45 |
///This is the base type for most of LEMON digraph adaptors. This
|
deba@430
|
46 |
///class implements a trivial digraph adaptor i.e. it only wraps the
|
deba@430
|
47 |
///functions and types of the digraph. The purpose of this class is
|
deba@430
|
48 |
///to make easier implementing digraph adaptors. E.g. if an adaptor
|
deba@430
|
49 |
///is considered which differs from the wrapped digraph only in some
|
deba@430
|
50 |
///of its functions or types, then it can be derived from
|
deba@430
|
51 |
///DigraphAdaptor, and only the differences should be implemented.
|
deba@430
|
52 |
template<typename _Digraph>
|
deba@430
|
53 |
class DigraphAdaptorBase {
|
deba@430
|
54 |
public:
|
deba@430
|
55 |
typedef _Digraph Digraph;
|
deba@430
|
56 |
typedef DigraphAdaptorBase Adaptor;
|
deba@430
|
57 |
typedef Digraph ParentDigraph;
|
deba@430
|
58 |
|
deba@430
|
59 |
protected:
|
deba@430
|
60 |
Digraph* _digraph;
|
deba@430
|
61 |
DigraphAdaptorBase() : _digraph(0) { }
|
deba@430
|
62 |
void setDigraph(Digraph& digraph) { _digraph = &digraph; }
|
deba@430
|
63 |
|
deba@430
|
64 |
public:
|
deba@430
|
65 |
DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
|
deba@430
|
66 |
|
deba@430
|
67 |
typedef typename Digraph::Node Node;
|
deba@430
|
68 |
typedef typename Digraph::Arc Arc;
|
deba@430
|
69 |
|
deba@430
|
70 |
void first(Node& i) const { _digraph->first(i); }
|
deba@430
|
71 |
void first(Arc& i) const { _digraph->first(i); }
|
deba@430
|
72 |
void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
|
deba@430
|
73 |
void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
|
deba@430
|
74 |
|
deba@430
|
75 |
void next(Node& i) const { _digraph->next(i); }
|
deba@430
|
76 |
void next(Arc& i) const { _digraph->next(i); }
|
deba@430
|
77 |
void nextIn(Arc& i) const { _digraph->nextIn(i); }
|
deba@430
|
78 |
void nextOut(Arc& i) const { _digraph->nextOut(i); }
|
deba@430
|
79 |
|
deba@430
|
80 |
Node source(const Arc& a) const { return _digraph->source(a); }
|
deba@430
|
81 |
Node target(const Arc& a) const { return _digraph->target(a); }
|
deba@430
|
82 |
|
deba@430
|
83 |
typedef NodeNumTagIndicator<Digraph> NodeNumTag;
|
deba@430
|
84 |
int nodeNum() const { return _digraph->nodeNum(); }
|
deba@430
|
85 |
|
deba@430
|
86 |
typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
|
deba@430
|
87 |
int arcNum() const { return _digraph->arcNum(); }
|
deba@430
|
88 |
|
deba@430
|
89 |
typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
|
deba@430
|
90 |
Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
|
deba@430
|
91 |
return _digraph->findArc(u, v, prev);
|
deba@430
|
92 |
}
|
deba@430
|
93 |
|
deba@430
|
94 |
Node addNode() { return _digraph->addNode(); }
|
deba@430
|
95 |
Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
|
deba@430
|
96 |
|
deba@430
|
97 |
void erase(const Node& n) const { _digraph->erase(n); }
|
deba@430
|
98 |
void erase(const Arc& a) const { _digraph->erase(a); }
|
deba@430
|
99 |
|
deba@430
|
100 |
void clear() const { _digraph->clear(); }
|
deba@430
|
101 |
|
deba@430
|
102 |
int id(const Node& n) const { return _digraph->id(n); }
|
deba@430
|
103 |
int id(const Arc& a) const { return _digraph->id(a); }
|
deba@430
|
104 |
|
deba@430
|
105 |
Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
|
deba@430
|
106 |
Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
|
deba@430
|
107 |
|
deba@430
|
108 |
int maxNodeId() const { return _digraph->maxNodeId(); }
|
deba@430
|
109 |
int maxArcId() const { return _digraph->maxArcId(); }
|
deba@430
|
110 |
|
deba@430
|
111 |
typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
|
deba@430
|
112 |
NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
|
deba@430
|
113 |
|
deba@430
|
114 |
typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
|
deba@430
|
115 |
ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
|
deba@430
|
116 |
|
deba@430
|
117 |
template <typename _Value>
|
deba@430
|
118 |
class NodeMap : public Digraph::template NodeMap<_Value> {
|
deba@430
|
119 |
public:
|
deba@430
|
120 |
|
deba@430
|
121 |
typedef typename Digraph::template NodeMap<_Value> Parent;
|
deba@430
|
122 |
|
deba@430
|
123 |
explicit NodeMap(const Adaptor& adaptor)
|
deba@430
|
124 |
: Parent(*adaptor._digraph) {}
|
deba@430
|
125 |
|
deba@430
|
126 |
NodeMap(const Adaptor& adaptor, const _Value& value)
|
deba@430
|
127 |
: Parent(*adaptor._digraph, value) { }
|
deba@430
|
128 |
|
deba@430
|
129 |
private:
|
deba@430
|
130 |
NodeMap& operator=(const NodeMap& cmap) {
|
deba@430
|
131 |
return operator=<NodeMap>(cmap);
|
deba@430
|
132 |
}
|
deba@430
|
133 |
|
deba@430
|
134 |
template <typename CMap>
|
deba@430
|
135 |
NodeMap& operator=(const CMap& cmap) {
|
deba@430
|
136 |
Parent::operator=(cmap);
|
deba@430
|
137 |
return *this;
|
deba@430
|
138 |
}
|
deba@430
|
139 |
|
deba@430
|
140 |
};
|
deba@430
|
141 |
|
deba@430
|
142 |
template <typename _Value>
|
deba@430
|
143 |
class ArcMap : public Digraph::template ArcMap<_Value> {
|
deba@430
|
144 |
public:
|
deba@430
|
145 |
|
deba@430
|
146 |
typedef typename Digraph::template ArcMap<_Value> Parent;
|
deba@430
|
147 |
|
deba@430
|
148 |
explicit ArcMap(const Adaptor& adaptor)
|
deba@430
|
149 |
: Parent(*adaptor._digraph) {}
|
deba@430
|
150 |
|
deba@430
|
151 |
ArcMap(const Adaptor& adaptor, const _Value& value)
|
deba@430
|
152 |
: Parent(*adaptor._digraph, value) {}
|
deba@430
|
153 |
|
deba@430
|
154 |
private:
|
deba@430
|
155 |
ArcMap& operator=(const ArcMap& cmap) {
|
deba@430
|
156 |
return operator=<ArcMap>(cmap);
|
deba@430
|
157 |
}
|
deba@430
|
158 |
|
deba@430
|
159 |
template <typename CMap>
|
deba@430
|
160 |
ArcMap& operator=(const CMap& cmap) {
|
deba@430
|
161 |
Parent::operator=(cmap);
|
deba@430
|
162 |
return *this;
|
deba@430
|
163 |
}
|
deba@430
|
164 |
|
deba@430
|
165 |
};
|
deba@430
|
166 |
|
deba@430
|
167 |
};
|
deba@430
|
168 |
|
deba@430
|
169 |
///\ingroup graph_adaptors
|
deba@430
|
170 |
///
|
deba@430
|
171 |
///\brief Trivial Digraph Adaptor
|
deba@430
|
172 |
///
|
deba@430
|
173 |
/// This class is an adaptor which does not change the adapted
|
deba@430
|
174 |
/// digraph. It can be used only to test the digraph adaptors.
|
deba@430
|
175 |
template <typename _Digraph>
|
deba@430
|
176 |
class DigraphAdaptor :
|
deba@430
|
177 |
public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
|
deba@430
|
178 |
public:
|
deba@430
|
179 |
typedef _Digraph Digraph;
|
deba@430
|
180 |
typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
|
deba@430
|
181 |
protected:
|
deba@430
|
182 |
DigraphAdaptor() : Parent() { }
|
deba@430
|
183 |
|
deba@430
|
184 |
public:
|
deba@430
|
185 |
explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
|
deba@430
|
186 |
};
|
deba@430
|
187 |
|
deba@430
|
188 |
/// \brief Just gives back a digraph adaptor
|
deba@430
|
189 |
///
|
deba@430
|
190 |
/// Just gives back a digraph adaptor which
|
deba@430
|
191 |
/// should be provide original digraph
|
deba@430
|
192 |
template<typename Digraph>
|
deba@430
|
193 |
DigraphAdaptor<const Digraph>
|
deba@430
|
194 |
digraphAdaptor(const Digraph& digraph) {
|
deba@430
|
195 |
return DigraphAdaptor<const Digraph>(digraph);
|
deba@430
|
196 |
}
|
deba@430
|
197 |
|
deba@430
|
198 |
|
deba@430
|
199 |
template <typename _Digraph>
|
deba@430
|
200 |
class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
|
deba@430
|
201 |
public:
|
deba@430
|
202 |
typedef _Digraph Digraph;
|
deba@430
|
203 |
typedef DigraphAdaptorBase<_Digraph> Parent;
|
deba@430
|
204 |
protected:
|
deba@430
|
205 |
RevDigraphAdaptorBase() : Parent() { }
|
deba@430
|
206 |
public:
|
deba@430
|
207 |
typedef typename Parent::Node Node;
|
deba@430
|
208 |
typedef typename Parent::Arc Arc;
|
deba@430
|
209 |
|
deba@430
|
210 |
void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
|
deba@430
|
211 |
void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
|
deba@430
|
212 |
|
deba@430
|
213 |
void nextIn(Arc& a) const { Parent::nextOut(a); }
|
deba@430
|
214 |
void nextOut(Arc& a) const { Parent::nextIn(a); }
|
deba@430
|
215 |
|
deba@430
|
216 |
Node source(const Arc& a) const { return Parent::target(a); }
|
deba@430
|
217 |
Node target(const Arc& a) const { return Parent::source(a); }
|
deba@430
|
218 |
|
deba@430
|
219 |
typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
|
deba@430
|
220 |
Arc findArc(const Node& u, const Node& v,
|
deba@430
|
221 |
const Arc& prev = INVALID) {
|
deba@430
|
222 |
return Parent::findArc(v, u, prev);
|
deba@430
|
223 |
}
|
deba@430
|
224 |
|
deba@430
|
225 |
};
|
deba@430
|
226 |
|
deba@430
|
227 |
|
deba@430
|
228 |
///\ingroup graph_adaptors
|
deba@430
|
229 |
///
|
deba@430
|
230 |
///\brief A digraph adaptor which reverses the orientation of the arcs.
|
deba@430
|
231 |
///
|
deba@430
|
232 |
/// If \c g is defined as
|
deba@430
|
233 |
///\code
|
deba@430
|
234 |
/// ListDigraph g;
|
deba@430
|
235 |
///\endcode
|
deba@430
|
236 |
/// then
|
deba@430
|
237 |
///\code
|
deba@430
|
238 |
/// RevDigraphAdaptor<ListDigraph> ga(g);
|
deba@430
|
239 |
///\endcode
|
deba@430
|
240 |
/// implements the digraph obtained from \c g by
|
deba@430
|
241 |
/// reversing the orientation of its arcs.
|
deba@430
|
242 |
///
|
deba@430
|
243 |
/// A good example of using RevDigraphAdaptor is to decide that the
|
deba@430
|
244 |
/// directed graph is wheter strongly connected or not. If from one
|
deba@430
|
245 |
/// node each node is reachable and from each node is reachable this
|
deba@430
|
246 |
/// node then and just then the digraph is strongly
|
deba@430
|
247 |
/// connected. Instead of this condition we use a little bit
|
deba@430
|
248 |
/// different. From one node each node ahould be reachable in the
|
deba@430
|
249 |
/// digraph and in the reversed digraph. Now this condition can be
|
deba@430
|
250 |
/// checked with the Dfs algorithm class and the RevDigraphAdaptor
|
deba@430
|
251 |
/// algorithm class.
|
deba@430
|
252 |
///
|
deba@430
|
253 |
/// And look at the code:
|
deba@430
|
254 |
///
|
deba@430
|
255 |
///\code
|
deba@430
|
256 |
/// bool stronglyConnected(const Digraph& digraph) {
|
deba@430
|
257 |
/// if (NodeIt(digraph) == INVALID) return true;
|
deba@430
|
258 |
/// Dfs<Digraph> dfs(digraph);
|
deba@430
|
259 |
/// dfs.run(NodeIt(digraph));
|
deba@430
|
260 |
/// for (NodeIt it(digraph); it != INVALID; ++it) {
|
deba@430
|
261 |
/// if (!dfs.reached(it)) {
|
deba@430
|
262 |
/// return false;
|
deba@430
|
263 |
/// }
|
deba@430
|
264 |
/// }
|
deba@430
|
265 |
/// typedef RevDigraphAdaptor<const Digraph> RDigraph;
|
deba@430
|
266 |
/// RDigraph rdigraph(digraph);
|
deba@430
|
267 |
/// DfsVisit<RDigraph> rdfs(rdigraph);
|
deba@430
|
268 |
/// rdfs.run(NodeIt(digraph));
|
deba@430
|
269 |
/// for (NodeIt it(digraph); it != INVALID; ++it) {
|
deba@430
|
270 |
/// if (!rdfs.reached(it)) {
|
deba@430
|
271 |
/// return false;
|
deba@430
|
272 |
/// }
|
deba@430
|
273 |
/// }
|
deba@430
|
274 |
/// return true;
|
deba@430
|
275 |
/// }
|
deba@430
|
276 |
///\endcode
|
deba@430
|
277 |
template<typename _Digraph>
|
deba@430
|
278 |
class RevDigraphAdaptor :
|
deba@430
|
279 |
public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
|
deba@430
|
280 |
public:
|
deba@430
|
281 |
typedef _Digraph Digraph;
|
deba@430
|
282 |
typedef DigraphAdaptorExtender<
|
deba@430
|
283 |
RevDigraphAdaptorBase<_Digraph> > Parent;
|
deba@430
|
284 |
protected:
|
deba@430
|
285 |
RevDigraphAdaptor() { }
|
deba@430
|
286 |
public:
|
deba@430
|
287 |
explicit RevDigraphAdaptor(Digraph& digraph) {
|
deba@430
|
288 |
Parent::setDigraph(digraph);
|
deba@430
|
289 |
}
|
deba@430
|
290 |
};
|
deba@430
|
291 |
|
deba@430
|
292 |
/// \brief Just gives back a reverse digraph adaptor
|
deba@430
|
293 |
///
|
deba@430
|
294 |
/// Just gives back a reverse digraph adaptor
|
deba@430
|
295 |
template<typename Digraph>
|
deba@430
|
296 |
RevDigraphAdaptor<const Digraph>
|
deba@430
|
297 |
revDigraphAdaptor(const Digraph& digraph) {
|
deba@430
|
298 |
return RevDigraphAdaptor<const Digraph>(digraph);
|
deba@430
|
299 |
}
|
deba@430
|
300 |
|
deba@430
|
301 |
template <typename _Digraph, typename _NodeFilterMap,
|
deba@430
|
302 |
typename _ArcFilterMap, bool checked = true>
|
deba@430
|
303 |
class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
|
deba@430
|
304 |
public:
|
deba@430
|
305 |
typedef _Digraph Digraph;
|
deba@430
|
306 |
typedef _NodeFilterMap NodeFilterMap;
|
deba@430
|
307 |
typedef _ArcFilterMap ArcFilterMap;
|
deba@430
|
308 |
|
deba@430
|
309 |
typedef SubDigraphAdaptorBase Adaptor;
|
deba@430
|
310 |
typedef DigraphAdaptorBase<_Digraph> Parent;
|
deba@430
|
311 |
protected:
|
deba@430
|
312 |
NodeFilterMap* _node_filter;
|
deba@430
|
313 |
ArcFilterMap* _arc_filter;
|
deba@430
|
314 |
SubDigraphAdaptorBase()
|
deba@430
|
315 |
: Parent(), _node_filter(0), _arc_filter(0) { }
|
deba@430
|
316 |
|
deba@430
|
317 |
void setNodeFilterMap(NodeFilterMap& node_filter) {
|
deba@430
|
318 |
_node_filter = &node_filter;
|
deba@430
|
319 |
}
|
deba@430
|
320 |
void setArcFilterMap(ArcFilterMap& arc_filter) {
|
deba@430
|
321 |
_arc_filter = &arc_filter;
|
deba@430
|
322 |
}
|
deba@430
|
323 |
|
deba@430
|
324 |
public:
|
deba@430
|
325 |
|
deba@430
|
326 |
typedef typename Parent::Node Node;
|
deba@430
|
327 |
typedef typename Parent::Arc Arc;
|
deba@430
|
328 |
|
deba@430
|
329 |
void first(Node& i) const {
|
deba@430
|
330 |
Parent::first(i);
|
deba@430
|
331 |
while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
|
deba@430
|
332 |
}
|
deba@430
|
333 |
|
deba@430
|
334 |
void first(Arc& i) const {
|
deba@430
|
335 |
Parent::first(i);
|
deba@430
|
336 |
while (i != INVALID && (!(*_arc_filter)[i]
|
deba@430
|
337 |
|| !(*_node_filter)[Parent::source(i)]
|
deba@430
|
338 |
|| !(*_node_filter)[Parent::target(i)])) Parent::next(i);
|
deba@430
|
339 |
}
|
deba@430
|
340 |
|
deba@430
|
341 |
void firstIn(Arc& i, const Node& n) const {
|
deba@430
|
342 |
Parent::firstIn(i, n);
|
deba@430
|
343 |
while (i != INVALID && (!(*_arc_filter)[i]
|
deba@430
|
344 |
|| !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
|
deba@430
|
345 |
}
|
deba@430
|
346 |
|
deba@430
|
347 |
void firstOut(Arc& i, const Node& n) const {
|
deba@430
|
348 |
Parent::firstOut(i, n);
|
deba@430
|
349 |
while (i != INVALID && (!(*_arc_filter)[i]
|
deba@430
|
350 |
|| !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
|
deba@430
|
351 |
}
|
deba@430
|
352 |
|
deba@430
|
353 |
void next(Node& i) const {
|
deba@430
|
354 |
Parent::next(i);
|
deba@430
|
355 |
while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
|
deba@430
|
356 |
}
|
deba@430
|
357 |
|
deba@430
|
358 |
void next(Arc& i) const {
|
deba@430
|
359 |
Parent::next(i);
|
deba@430
|
360 |
while (i != INVALID && (!(*_arc_filter)[i]
|
deba@430
|
361 |
|| !(*_node_filter)[Parent::source(i)]
|
deba@430
|
362 |
|| !(*_node_filter)[Parent::target(i)])) Parent::next(i);
|
deba@430
|
363 |
}
|
deba@430
|
364 |
|
deba@430
|
365 |
void nextIn(Arc& i) const {
|
deba@430
|
366 |
Parent::nextIn(i);
|
deba@430
|
367 |
while (i != INVALID && (!(*_arc_filter)[i]
|
deba@430
|
368 |
|| !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
|
deba@430
|
369 |
}
|
deba@430
|
370 |
|
deba@430
|
371 |
void nextOut(Arc& i) const {
|
deba@430
|
372 |
Parent::nextOut(i);
|
deba@430
|
373 |
while (i != INVALID && (!(*_arc_filter)[i]
|
deba@430
|
374 |
|| !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
|
deba@430
|
375 |
}
|
deba@430
|
376 |
|
deba@430
|
377 |
///\e
|
deba@430
|
378 |
|
deba@430
|
379 |
/// This function hides \c n in the digraph, i.e. the iteration
|
deba@430
|
380 |
/// jumps over it. This is done by simply setting the value of \c n
|
deba@430
|
381 |
/// to be false in the corresponding node-map.
|
deba@430
|
382 |
void hide(const Node& n) const { _node_filter->set(n, false); }
|
deba@430
|
383 |
|
deba@430
|
384 |
///\e
|
deba@430
|
385 |
|
deba@430
|
386 |
/// This function hides \c a in the digraph, i.e. the iteration
|
deba@430
|
387 |
/// jumps over it. This is done by simply setting the value of \c a
|
deba@430
|
388 |
/// to be false in the corresponding arc-map.
|
deba@430
|
389 |
void hide(const Arc& a) const { _arc_filter->set(a, false); }
|
deba@430
|
390 |
|
deba@430
|
391 |
///\e
|
deba@430
|
392 |
|
deba@430
|
393 |
/// The value of \c n is set to be true in the node-map which stores
|
deba@430
|
394 |
/// hide information. If \c n was hidden previuosly, then it is shown
|
deba@430
|
395 |
/// again
|
deba@430
|
396 |
void unHide(const Node& n) const { _node_filter->set(n, true); }
|
deba@430
|
397 |
|
deba@430
|
398 |
///\e
|
deba@430
|
399 |
|
deba@430
|
400 |
/// The value of \c a is set to be true in the arc-map which stores
|
deba@430
|
401 |
/// hide information. If \c a was hidden previuosly, then it is shown
|
deba@430
|
402 |
/// again
|
deba@430
|
403 |
void unHide(const Arc& a) const { _arc_filter->set(a, true); }
|
deba@430
|
404 |
|
deba@430
|
405 |
/// Returns true if \c n is hidden.
|
deba@430
|
406 |
|
deba@430
|
407 |
///\e
|
deba@430
|
408 |
///
|
deba@430
|
409 |
bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
|
deba@430
|
410 |
|
deba@430
|
411 |
/// Returns true if \c a is hidden.
|
deba@430
|
412 |
|
deba@430
|
413 |
///\e
|
deba@430
|
414 |
///
|
deba@430
|
415 |
bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
|
deba@430
|
416 |
|
deba@430
|
417 |
typedef False NodeNumTag;
|
deba@430
|
418 |
typedef False EdgeNumTag;
|
deba@430
|
419 |
|
deba@430
|
420 |
typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
|
deba@430
|
421 |
Arc findArc(const Node& source, const Node& target,
|
deba@430
|
422 |
const Arc& prev = INVALID) {
|
deba@430
|
423 |
if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
|
deba@430
|
424 |
return INVALID;
|
deba@430
|
425 |
}
|
deba@430
|
426 |
Arc arc = Parent::findArc(source, target, prev);
|
deba@430
|
427 |
while (arc != INVALID && !(*_arc_filter)[arc]) {
|
deba@430
|
428 |
arc = Parent::findArc(source, target, arc);
|
deba@430
|
429 |
}
|
deba@430
|
430 |
return arc;
|
deba@430
|
431 |
}
|
deba@430
|
432 |
|
deba@430
|
433 |
template <typename _Value>
|
deba@430
|
434 |
class NodeMap : public SubMapExtender<Adaptor,
|
deba@430
|
435 |
typename Parent::template NodeMap<_Value> > {
|
deba@430
|
436 |
public:
|
deba@430
|
437 |
typedef _Value Value;
|
deba@430
|
438 |
typedef SubMapExtender<Adaptor, typename Parent::
|
deba@430
|
439 |
template NodeMap<Value> > MapParent;
|
deba@430
|
440 |
|
deba@430
|
441 |
NodeMap(const Adaptor& adaptor)
|
deba@430
|
442 |
: MapParent(adaptor) {}
|
deba@430
|
443 |
NodeMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
444 |
: MapParent(adaptor, value) {}
|
deba@430
|
445 |
|
deba@430
|
446 |
private:
|
deba@430
|
447 |
NodeMap& operator=(const NodeMap& cmap) {
|
deba@430
|
448 |
return operator=<NodeMap>(cmap);
|
deba@430
|
449 |
}
|
deba@430
|
450 |
|
deba@430
|
451 |
template <typename CMap>
|
deba@430
|
452 |
NodeMap& operator=(const CMap& cmap) {
|
deba@430
|
453 |
MapParent::operator=(cmap);
|
deba@430
|
454 |
return *this;
|
deba@430
|
455 |
}
|
deba@430
|
456 |
};
|
deba@430
|
457 |
|
deba@430
|
458 |
template <typename _Value>
|
deba@430
|
459 |
class ArcMap : public SubMapExtender<Adaptor,
|
deba@430
|
460 |
typename Parent::template ArcMap<_Value> > {
|
deba@430
|
461 |
public:
|
deba@430
|
462 |
typedef _Value Value;
|
deba@430
|
463 |
typedef SubMapExtender<Adaptor, typename Parent::
|
deba@430
|
464 |
template ArcMap<Value> > MapParent;
|
deba@430
|
465 |
|
deba@430
|
466 |
ArcMap(const Adaptor& adaptor)
|
deba@430
|
467 |
: MapParent(adaptor) {}
|
deba@430
|
468 |
ArcMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
469 |
: MapParent(adaptor, value) {}
|
deba@430
|
470 |
|
deba@430
|
471 |
private:
|
deba@430
|
472 |
ArcMap& operator=(const ArcMap& cmap) {
|
deba@430
|
473 |
return operator=<ArcMap>(cmap);
|
deba@430
|
474 |
}
|
deba@430
|
475 |
|
deba@430
|
476 |
template <typename CMap>
|
deba@430
|
477 |
ArcMap& operator=(const CMap& cmap) {
|
deba@430
|
478 |
MapParent::operator=(cmap);
|
deba@430
|
479 |
return *this;
|
deba@430
|
480 |
}
|
deba@430
|
481 |
};
|
deba@430
|
482 |
|
deba@430
|
483 |
};
|
deba@430
|
484 |
|
deba@430
|
485 |
template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
|
deba@430
|
486 |
class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
|
deba@430
|
487 |
: public DigraphAdaptorBase<_Digraph> {
|
deba@430
|
488 |
public:
|
deba@430
|
489 |
typedef _Digraph Digraph;
|
deba@430
|
490 |
typedef _NodeFilterMap NodeFilterMap;
|
deba@430
|
491 |
typedef _ArcFilterMap ArcFilterMap;
|
deba@430
|
492 |
|
deba@430
|
493 |
typedef SubDigraphAdaptorBase Adaptor;
|
deba@430
|
494 |
typedef DigraphAdaptorBase<Digraph> Parent;
|
deba@430
|
495 |
protected:
|
deba@430
|
496 |
NodeFilterMap* _node_filter;
|
deba@430
|
497 |
ArcFilterMap* _arc_filter;
|
deba@430
|
498 |
SubDigraphAdaptorBase()
|
deba@430
|
499 |
: Parent(), _node_filter(0), _arc_filter(0) { }
|
deba@430
|
500 |
|
deba@430
|
501 |
void setNodeFilterMap(NodeFilterMap& node_filter) {
|
deba@430
|
502 |
_node_filter = &node_filter;
|
deba@430
|
503 |
}
|
deba@430
|
504 |
void setArcFilterMap(ArcFilterMap& arc_filter) {
|
deba@430
|
505 |
_arc_filter = &arc_filter;
|
deba@430
|
506 |
}
|
deba@430
|
507 |
|
deba@430
|
508 |
public:
|
deba@430
|
509 |
|
deba@430
|
510 |
typedef typename Parent::Node Node;
|
deba@430
|
511 |
typedef typename Parent::Arc Arc;
|
deba@430
|
512 |
|
deba@430
|
513 |
void first(Node& i) const {
|
deba@430
|
514 |
Parent::first(i);
|
deba@430
|
515 |
while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
|
deba@430
|
516 |
}
|
deba@430
|
517 |
|
deba@430
|
518 |
void first(Arc& i) const {
|
deba@430
|
519 |
Parent::first(i);
|
deba@430
|
520 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
|
deba@430
|
521 |
}
|
deba@430
|
522 |
|
deba@430
|
523 |
void firstIn(Arc& i, const Node& n) const {
|
deba@430
|
524 |
Parent::firstIn(i, n);
|
deba@430
|
525 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
|
deba@430
|
526 |
}
|
deba@430
|
527 |
|
deba@430
|
528 |
void firstOut(Arc& i, const Node& n) const {
|
deba@430
|
529 |
Parent::firstOut(i, n);
|
deba@430
|
530 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
|
deba@430
|
531 |
}
|
deba@430
|
532 |
|
deba@430
|
533 |
void next(Node& i) const {
|
deba@430
|
534 |
Parent::next(i);
|
deba@430
|
535 |
while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
|
deba@430
|
536 |
}
|
deba@430
|
537 |
void next(Arc& i) const {
|
deba@430
|
538 |
Parent::next(i);
|
deba@430
|
539 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
|
deba@430
|
540 |
}
|
deba@430
|
541 |
void nextIn(Arc& i) const {
|
deba@430
|
542 |
Parent::nextIn(i);
|
deba@430
|
543 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
|
deba@430
|
544 |
}
|
deba@430
|
545 |
|
deba@430
|
546 |
void nextOut(Arc& i) const {
|
deba@430
|
547 |
Parent::nextOut(i);
|
deba@430
|
548 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
|
deba@430
|
549 |
}
|
deba@430
|
550 |
|
deba@430
|
551 |
///\e
|
deba@430
|
552 |
|
deba@430
|
553 |
/// This function hides \c n in the digraph, i.e. the iteration
|
deba@430
|
554 |
/// jumps over it. This is done by simply setting the value of \c n
|
deba@430
|
555 |
/// to be false in the corresponding node-map.
|
deba@430
|
556 |
void hide(const Node& n) const { _node_filter->set(n, false); }
|
deba@430
|
557 |
|
deba@430
|
558 |
///\e
|
deba@430
|
559 |
|
deba@430
|
560 |
/// This function hides \c e in the digraph, i.e. the iteration
|
deba@430
|
561 |
/// jumps over it. This is done by simply setting the value of \c e
|
deba@430
|
562 |
/// to be false in the corresponding arc-map.
|
deba@430
|
563 |
void hide(const Arc& e) const { _arc_filter->set(e, false); }
|
deba@430
|
564 |
|
deba@430
|
565 |
///\e
|
deba@430
|
566 |
|
deba@430
|
567 |
/// The value of \c n is set to be true in the node-map which stores
|
deba@430
|
568 |
/// hide information. If \c n was hidden previuosly, then it is shown
|
deba@430
|
569 |
/// again
|
deba@430
|
570 |
void unHide(const Node& n) const { _node_filter->set(n, true); }
|
deba@430
|
571 |
|
deba@430
|
572 |
///\e
|
deba@430
|
573 |
|
deba@430
|
574 |
/// The value of \c e is set to be true in the arc-map which stores
|
deba@430
|
575 |
/// hide information. If \c e was hidden previuosly, then it is shown
|
deba@430
|
576 |
/// again
|
deba@430
|
577 |
void unHide(const Arc& e) const { _arc_filter->set(e, true); }
|
deba@430
|
578 |
|
deba@430
|
579 |
/// Returns true if \c n is hidden.
|
deba@430
|
580 |
|
deba@430
|
581 |
///\e
|
deba@430
|
582 |
///
|
deba@430
|
583 |
bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
|
deba@430
|
584 |
|
deba@430
|
585 |
/// Returns true if \c n is hidden.
|
deba@430
|
586 |
|
deba@430
|
587 |
///\e
|
deba@430
|
588 |
///
|
deba@430
|
589 |
bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
|
deba@430
|
590 |
|
deba@430
|
591 |
typedef False NodeNumTag;
|
deba@430
|
592 |
typedef False EdgeNumTag;
|
deba@430
|
593 |
|
deba@430
|
594 |
typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
|
deba@430
|
595 |
Arc findArc(const Node& source, const Node& target,
|
deba@430
|
596 |
const Arc& prev = INVALID) {
|
deba@430
|
597 |
if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
|
deba@430
|
598 |
return INVALID;
|
deba@430
|
599 |
}
|
deba@430
|
600 |
Arc arc = Parent::findArc(source, target, prev);
|
deba@430
|
601 |
while (arc != INVALID && !(*_arc_filter)[arc]) {
|
deba@430
|
602 |
arc = Parent::findArc(source, target, arc);
|
deba@430
|
603 |
}
|
deba@430
|
604 |
return arc;
|
deba@430
|
605 |
}
|
deba@430
|
606 |
|
deba@430
|
607 |
template <typename _Value>
|
deba@430
|
608 |
class NodeMap : public SubMapExtender<Adaptor,
|
deba@430
|
609 |
typename Parent::template NodeMap<_Value> > {
|
deba@430
|
610 |
public:
|
deba@430
|
611 |
typedef _Value Value;
|
deba@430
|
612 |
typedef SubMapExtender<Adaptor, typename Parent::
|
deba@430
|
613 |
template NodeMap<Value> > MapParent;
|
deba@430
|
614 |
|
deba@430
|
615 |
NodeMap(const Adaptor& adaptor)
|
deba@430
|
616 |
: MapParent(adaptor) {}
|
deba@430
|
617 |
NodeMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
618 |
: MapParent(adaptor, value) {}
|
deba@430
|
619 |
|
deba@430
|
620 |
private:
|
deba@430
|
621 |
NodeMap& operator=(const NodeMap& cmap) {
|
deba@430
|
622 |
return operator=<NodeMap>(cmap);
|
deba@430
|
623 |
}
|
deba@430
|
624 |
|
deba@430
|
625 |
template <typename CMap>
|
deba@430
|
626 |
NodeMap& operator=(const CMap& cmap) {
|
deba@430
|
627 |
MapParent::operator=(cmap);
|
deba@430
|
628 |
return *this;
|
deba@430
|
629 |
}
|
deba@430
|
630 |
};
|
deba@430
|
631 |
|
deba@430
|
632 |
template <typename _Value>
|
deba@430
|
633 |
class ArcMap : public SubMapExtender<Adaptor,
|
deba@430
|
634 |
typename Parent::template ArcMap<_Value> > {
|
deba@430
|
635 |
public:
|
deba@430
|
636 |
typedef _Value Value;
|
deba@430
|
637 |
typedef SubMapExtender<Adaptor, typename Parent::
|
deba@430
|
638 |
template ArcMap<Value> > MapParent;
|
deba@430
|
639 |
|
deba@430
|
640 |
ArcMap(const Adaptor& adaptor)
|
deba@430
|
641 |
: MapParent(adaptor) {}
|
deba@430
|
642 |
ArcMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
643 |
: MapParent(adaptor, value) {}
|
deba@430
|
644 |
|
deba@430
|
645 |
private:
|
deba@430
|
646 |
ArcMap& operator=(const ArcMap& cmap) {
|
deba@430
|
647 |
return operator=<ArcMap>(cmap);
|
deba@430
|
648 |
}
|
deba@430
|
649 |
|
deba@430
|
650 |
template <typename CMap>
|
deba@430
|
651 |
ArcMap& operator=(const CMap& cmap) {
|
deba@430
|
652 |
MapParent::operator=(cmap);
|
deba@430
|
653 |
return *this;
|
deba@430
|
654 |
}
|
deba@430
|
655 |
};
|
deba@430
|
656 |
|
deba@430
|
657 |
};
|
deba@430
|
658 |
|
deba@430
|
659 |
/// \ingroup graph_adaptors
|
deba@430
|
660 |
///
|
deba@430
|
661 |
/// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
|
deba@430
|
662 |
///
|
deba@430
|
663 |
/// SubDigraphAdaptor shows the digraph with filtered node-set and
|
deba@430
|
664 |
/// arc-set. If the \c checked parameter is true then it filters the arcset
|
deba@430
|
665 |
/// to do not get invalid arcs without source or target.
|
deba@430
|
666 |
/// Let \f$ G=(V, A) \f$ be a directed digraph
|
deba@430
|
667 |
/// and suppose that the digraph instance \c g of type ListDigraph
|
deba@430
|
668 |
/// implements \f$ G \f$.
|
deba@430
|
669 |
/// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
|
deba@430
|
670 |
/// on the node-set and arc-set.
|
deba@430
|
671 |
/// SubDigraphAdaptor<...>::NodeIt iterates
|
deba@430
|
672 |
/// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
|
deba@430
|
673 |
/// SubDigraphAdaptor<...>::ArcIt iterates
|
deba@430
|
674 |
/// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
|
deba@430
|
675 |
/// SubDigraphAdaptor<...>::OutArcIt and
|
deba@430
|
676 |
/// SubDigraphAdaptor<...>::InArcIt iterates
|
deba@430
|
677 |
/// only on arcs leaving and entering a specific node which have true value.
|
deba@430
|
678 |
///
|
deba@430
|
679 |
/// If the \c checked template parameter is false then we have to
|
deba@430
|
680 |
/// note that the node-iterator cares only the filter on the
|
deba@430
|
681 |
/// node-set, and the arc-iterator cares only the filter on the
|
deba@430
|
682 |
/// arc-set. This way the arc-map should filter all arcs which's
|
deba@430
|
683 |
/// source or target is filtered by the node-filter.
|
deba@430
|
684 |
///\code
|
deba@430
|
685 |
/// typedef ListDigraph Digraph;
|
deba@430
|
686 |
/// DIGRAPH_TYPEDEFS(Digraph);
|
deba@430
|
687 |
/// Digraph g;
|
deba@430
|
688 |
/// Node u=g.addNode(); //node of id 0
|
deba@430
|
689 |
/// Node v=g.addNode(); //node of id 1
|
deba@430
|
690 |
/// Arc a=g.addArc(u, v); //arc of id 0
|
deba@430
|
691 |
/// Arc f=g.addArc(v, u); //arc of id 1
|
deba@430
|
692 |
/// BoolNodeMap nm(g, true);
|
deba@430
|
693 |
/// nm.set(u, false);
|
deba@430
|
694 |
/// BoolArcMap am(g, true);
|
deba@430
|
695 |
/// am.set(a, false);
|
deba@430
|
696 |
/// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;
|
deba@430
|
697 |
/// SubGA ga(g, nm, am);
|
deba@430
|
698 |
/// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
|
deba@430
|
699 |
/// std::cout << g.id(n) << std::endl;
|
deba@430
|
700 |
/// std::cout << ":-)" << std::endl;
|
deba@430
|
701 |
/// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
|
deba@430
|
702 |
/// std::cout << g.id(a) << std::endl;
|
deba@430
|
703 |
///\endcode
|
deba@430
|
704 |
/// The output of the above code is the following.
|
deba@430
|
705 |
///\code
|
deba@430
|
706 |
/// 1
|
deba@430
|
707 |
/// :-)
|
deba@430
|
708 |
/// 1
|
deba@430
|
709 |
///\endcode
|
deba@430
|
710 |
/// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
|
deba@430
|
711 |
/// \c Digraph::Node that is why \c g.id(n) can be applied.
|
deba@430
|
712 |
///
|
deba@430
|
713 |
/// For other examples see also the documentation of
|
deba@430
|
714 |
/// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
|
deba@430
|
715 |
template<typename _Digraph,
|
deba@430
|
716 |
typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
|
deba@430
|
717 |
typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
|
deba@430
|
718 |
bool checked = true>
|
deba@430
|
719 |
class SubDigraphAdaptor :
|
deba@430
|
720 |
public DigraphAdaptorExtender<
|
deba@430
|
721 |
SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
|
deba@430
|
722 |
public:
|
deba@430
|
723 |
typedef _Digraph Digraph;
|
deba@430
|
724 |
typedef _NodeFilterMap NodeFilterMap;
|
deba@430
|
725 |
typedef _ArcFilterMap ArcFilterMap;
|
deba@430
|
726 |
|
deba@430
|
727 |
typedef DigraphAdaptorExtender<
|
deba@430
|
728 |
SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
|
deba@430
|
729 |
Parent;
|
deba@430
|
730 |
|
deba@430
|
731 |
protected:
|
deba@430
|
732 |
SubDigraphAdaptor() { }
|
deba@430
|
733 |
public:
|
deba@430
|
734 |
|
deba@430
|
735 |
SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
|
deba@430
|
736 |
ArcFilterMap& arc_filter) {
|
deba@430
|
737 |
setDigraph(digraph);
|
deba@430
|
738 |
setNodeFilterMap(node_filter);
|
deba@430
|
739 |
setArcFilterMap(arc_filter);
|
deba@430
|
740 |
}
|
deba@430
|
741 |
|
deba@430
|
742 |
};
|
deba@430
|
743 |
|
deba@430
|
744 |
/// \brief Just gives back a sub digraph adaptor
|
deba@430
|
745 |
///
|
deba@430
|
746 |
/// Just gives back a sub digraph adaptor
|
deba@430
|
747 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
|
deba@430
|
748 |
SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
|
deba@430
|
749 |
subDigraphAdaptor(const Digraph& digraph,
|
deba@430
|
750 |
NodeFilterMap& nfm, ArcFilterMap& afm) {
|
deba@430
|
751 |
return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
|
deba@430
|
752 |
(digraph, nfm, afm);
|
deba@430
|
753 |
}
|
deba@430
|
754 |
|
deba@430
|
755 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
|
deba@430
|
756 |
SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
|
deba@430
|
757 |
subDigraphAdaptor(const Digraph& digraph,
|
deba@430
|
758 |
NodeFilterMap& nfm, ArcFilterMap& afm) {
|
deba@430
|
759 |
return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
|
deba@430
|
760 |
(digraph, nfm, afm);
|
deba@430
|
761 |
}
|
deba@430
|
762 |
|
deba@430
|
763 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
|
deba@430
|
764 |
SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
|
deba@430
|
765 |
subDigraphAdaptor(const Digraph& digraph,
|
deba@430
|
766 |
NodeFilterMap& nfm, ArcFilterMap& afm) {
|
deba@430
|
767 |
return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
|
deba@430
|
768 |
(digraph, nfm, afm);
|
deba@430
|
769 |
}
|
deba@430
|
770 |
|
deba@430
|
771 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
|
deba@430
|
772 |
SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
|
deba@430
|
773 |
subDigraphAdaptor(const Digraph& digraph,
|
deba@430
|
774 |
NodeFilterMap& nfm, ArcFilterMap& afm) {
|
deba@430
|
775 |
return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
|
deba@430
|
776 |
const ArcFilterMap>(digraph, nfm, afm);
|
deba@430
|
777 |
}
|
deba@430
|
778 |
|
deba@430
|
779 |
|
deba@430
|
780 |
|
deba@430
|
781 |
///\ingroup graph_adaptors
|
deba@430
|
782 |
///
|
deba@430
|
783 |
///\brief An adaptor for hiding nodes from a digraph.
|
deba@430
|
784 |
///
|
deba@430
|
785 |
///An adaptor for hiding nodes from a digraph. This adaptor
|
deba@430
|
786 |
///specializes SubDigraphAdaptor in the way that only the node-set
|
deba@430
|
787 |
///can be filtered. In usual case the checked parameter is true, we
|
deba@430
|
788 |
///get the induced subgraph. But if the checked parameter is false
|
deba@430
|
789 |
///then we can filter only isolated nodes.
|
deba@430
|
790 |
template<typename _Digraph,
|
deba@430
|
791 |
typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
|
deba@430
|
792 |
bool checked = true>
|
deba@430
|
793 |
class NodeSubDigraphAdaptor :
|
deba@430
|
794 |
public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
|
deba@430
|
795 |
ConstMap<typename _Digraph::Arc, bool>, checked> {
|
deba@430
|
796 |
public:
|
deba@430
|
797 |
|
deba@430
|
798 |
typedef _Digraph Digraph;
|
deba@430
|
799 |
typedef _NodeFilterMap NodeFilterMap;
|
deba@430
|
800 |
|
deba@430
|
801 |
typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
|
deba@430
|
802 |
ConstMap<typename Digraph::Arc, bool>, checked>
|
deba@430
|
803 |
Parent;
|
deba@430
|
804 |
|
deba@430
|
805 |
protected:
|
deba@430
|
806 |
ConstMap<typename Digraph::Arc, bool> const_true_map;
|
deba@430
|
807 |
|
deba@430
|
808 |
NodeSubDigraphAdaptor() : const_true_map(true) {
|
deba@430
|
809 |
Parent::setArcFilterMap(const_true_map);
|
deba@430
|
810 |
}
|
deba@430
|
811 |
|
deba@430
|
812 |
public:
|
deba@430
|
813 |
|
deba@430
|
814 |
NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
|
deba@430
|
815 |
Parent(), const_true_map(true) {
|
deba@430
|
816 |
Parent::setDigraph(_digraph);
|
deba@430
|
817 |
Parent::setNodeFilterMap(node_filter);
|
deba@430
|
818 |
Parent::setArcFilterMap(const_true_map);
|
deba@430
|
819 |
}
|
deba@430
|
820 |
|
deba@430
|
821 |
};
|
deba@430
|
822 |
|
deba@430
|
823 |
|
deba@430
|
824 |
/// \brief Just gives back a \c NodeSubDigraphAdaptor
|
deba@430
|
825 |
///
|
deba@430
|
826 |
/// Just gives back a \c NodeSubDigraphAdaptor
|
deba@430
|
827 |
template<typename Digraph, typename NodeFilterMap>
|
deba@430
|
828 |
NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
|
deba@430
|
829 |
nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
|
deba@430
|
830 |
return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
|
deba@430
|
831 |
}
|
deba@430
|
832 |
|
deba@430
|
833 |
template<typename Digraph, typename NodeFilterMap>
|
deba@430
|
834 |
NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
|
deba@430
|
835 |
nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
|
deba@430
|
836 |
return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
|
deba@430
|
837 |
(digraph, nfm);
|
deba@430
|
838 |
}
|
deba@430
|
839 |
|
deba@430
|
840 |
///\ingroup graph_adaptors
|
deba@430
|
841 |
///
|
deba@430
|
842 |
///\brief An adaptor for hiding arcs from a digraph.
|
deba@430
|
843 |
///
|
deba@430
|
844 |
///An adaptor for hiding arcs from a digraph. This adaptor
|
deba@430
|
845 |
///specializes SubDigraphAdaptor in the way that only the arc-set
|
deba@430
|
846 |
///can be filtered. The usefulness of this adaptor is demonstrated
|
deba@430
|
847 |
///in the problem of searching a maximum number of arc-disjoint
|
deba@430
|
848 |
///shortest paths between two nodes \c s and \c t. Shortest here
|
deba@430
|
849 |
///means being shortest w.r.t. non-negative arc-lengths. Note that
|
deba@430
|
850 |
///the comprehension of the presented solution need's some
|
deba@430
|
851 |
///elementary knowlarc from combinatorial optimization.
|
deba@430
|
852 |
///
|
deba@430
|
853 |
///If a single shortest path is to be searched between \c s and \c
|
deba@430
|
854 |
///t, then this can be done easily by applying the Dijkstra
|
deba@430
|
855 |
///algorithm. What happens, if a maximum number of arc-disjoint
|
deba@430
|
856 |
///shortest paths is to be computed. It can be proved that an arc
|
deba@430
|
857 |
///can be in a shortest path if and only if it is tight with respect
|
deba@430
|
858 |
///to the potential function computed by Dijkstra. Moreover, any
|
deba@430
|
859 |
///path containing only such arcs is a shortest one. Thus we have
|
deba@430
|
860 |
///to compute a maximum number of arc-disjoint paths between \c s
|
deba@430
|
861 |
///and \c t in the digraph which has arc-set all the tight arcs. The
|
deba@430
|
862 |
///computation will be demonstrated on the following digraph, which
|
deba@430
|
863 |
///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
|
deba@430
|
864 |
///The full source code is available in \ref
|
deba@430
|
865 |
///sub_digraph_adaptor_demo.cc. If you are interested in more demo
|
deba@430
|
866 |
///programs, you can use \ref dim_to_dot.cc to generate .dot files
|
deba@430
|
867 |
///from dimacs files. The .dot file of the following figure was
|
deba@430
|
868 |
///generated by the demo program \ref dim_to_dot.cc.
|
deba@430
|
869 |
///
|
deba@430
|
870 |
///\dot
|
deba@430
|
871 |
///didigraph lemon_dot_example {
|
deba@430
|
872 |
///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
|
deba@430
|
873 |
///n0 [ label="0 (s)" ];
|
deba@430
|
874 |
///n1 [ label="1" ];
|
deba@430
|
875 |
///n2 [ label="2" ];
|
deba@430
|
876 |
///n3 [ label="3" ];
|
deba@430
|
877 |
///n4 [ label="4" ];
|
deba@430
|
878 |
///n5 [ label="5" ];
|
deba@430
|
879 |
///n6 [ label="6 (t)" ];
|
deba@430
|
880 |
///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
|
deba@430
|
881 |
///n5 -> n6 [ label="9, length:4" ];
|
deba@430
|
882 |
///n4 -> n6 [ label="8, length:2" ];
|
deba@430
|
883 |
///n3 -> n5 [ label="7, length:1" ];
|
deba@430
|
884 |
///n2 -> n5 [ label="6, length:3" ];
|
deba@430
|
885 |
///n2 -> n6 [ label="5, length:5" ];
|
deba@430
|
886 |
///n2 -> n4 [ label="4, length:2" ];
|
deba@430
|
887 |
///n1 -> n4 [ label="3, length:3" ];
|
deba@430
|
888 |
///n0 -> n3 [ label="2, length:1" ];
|
deba@430
|
889 |
///n0 -> n2 [ label="1, length:2" ];
|
deba@430
|
890 |
///n0 -> n1 [ label="0, length:3" ];
|
deba@430
|
891 |
///}
|
deba@430
|
892 |
///\enddot
|
deba@430
|
893 |
///
|
deba@430
|
894 |
///\code
|
deba@430
|
895 |
///Digraph g;
|
deba@430
|
896 |
///Node s, t;
|
deba@430
|
897 |
///LengthMap length(g);
|
deba@430
|
898 |
///
|
deba@430
|
899 |
///readDimacs(std::cin, g, length, s, t);
|
deba@430
|
900 |
///
|
deba@430
|
901 |
///cout << "arcs with lengths (of form id, source--length->target): " << endl;
|
deba@430
|
902 |
///for(ArcIt e(g); e!=INVALID; ++e)
|
deba@430
|
903 |
/// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
|
deba@430
|
904 |
/// << length[e] << "->" << g.id(g.target(e)) << endl;
|
deba@430
|
905 |
///
|
deba@430
|
906 |
///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
|
deba@430
|
907 |
///\endcode
|
deba@430
|
908 |
///Next, the potential function is computed with Dijkstra.
|
deba@430
|
909 |
///\code
|
deba@430
|
910 |
///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
|
deba@430
|
911 |
///Dijkstra dijkstra(g, length);
|
deba@430
|
912 |
///dijkstra.run(s);
|
deba@430
|
913 |
///\endcode
|
deba@430
|
914 |
///Next, we consrtruct a map which filters the arc-set to the tight arcs.
|
deba@430
|
915 |
///\code
|
deba@430
|
916 |
///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap>
|
deba@430
|
917 |
/// TightArcFilter;
|
deba@430
|
918 |
///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
|
deba@430
|
919 |
///
|
deba@430
|
920 |
///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
|
deba@430
|
921 |
///SubGA ga(g, tight_arc_filter);
|
deba@430
|
922 |
///\endcode
|
deba@430
|
923 |
///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed
|
deba@430
|
924 |
///with a max flow algorithm Preflow.
|
deba@430
|
925 |
///\code
|
deba@430
|
926 |
///ConstMap<Arc, int> const_1_map(1);
|
deba@430
|
927 |
///Digraph::ArcMap<int> flow(g, 0);
|
deba@430
|
928 |
///
|
deba@430
|
929 |
///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> >
|
deba@430
|
930 |
/// preflow(ga, const_1_map, s, t);
|
deba@430
|
931 |
///preflow.run();
|
deba@430
|
932 |
///\endcode
|
deba@430
|
933 |
///Last, the output is:
|
deba@430
|
934 |
///\code
|
deba@430
|
935 |
///cout << "maximum number of arc-disjoint shortest path: "
|
deba@430
|
936 |
/// << preflow.flowValue() << endl;
|
deba@430
|
937 |
///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: "
|
deba@430
|
938 |
/// << endl;
|
deba@430
|
939 |
///for(ArcIt e(g); e!=INVALID; ++e)
|
deba@430
|
940 |
/// if (preflow.flow(e))
|
deba@430
|
941 |
/// cout << " " << g.id(g.source(e)) << "--"
|
deba@430
|
942 |
/// << length[e] << "->" << g.id(g.target(e)) << endl;
|
deba@430
|
943 |
///\endcode
|
deba@430
|
944 |
///The program has the following (expected :-)) output:
|
deba@430
|
945 |
///\code
|
deba@430
|
946 |
///arcs with lengths (of form id, source--length->target):
|
deba@430
|
947 |
/// 9, 5--4->6
|
deba@430
|
948 |
/// 8, 4--2->6
|
deba@430
|
949 |
/// 7, 3--1->5
|
deba@430
|
950 |
/// 6, 2--3->5
|
deba@430
|
951 |
/// 5, 2--5->6
|
deba@430
|
952 |
/// 4, 2--2->4
|
deba@430
|
953 |
/// 3, 1--3->4
|
deba@430
|
954 |
/// 2, 0--1->3
|
deba@430
|
955 |
/// 1, 0--2->2
|
deba@430
|
956 |
/// 0, 0--3->1
|
deba@430
|
957 |
///s: 0 t: 6
|
deba@430
|
958 |
///maximum number of arc-disjoint shortest path: 2
|
deba@430
|
959 |
///arcs of the maximum number of arc-disjoint shortest s-t paths:
|
deba@430
|
960 |
/// 9, 5--4->6
|
deba@430
|
961 |
/// 8, 4--2->6
|
deba@430
|
962 |
/// 7, 3--1->5
|
deba@430
|
963 |
/// 4, 2--2->4
|
deba@430
|
964 |
/// 2, 0--1->3
|
deba@430
|
965 |
/// 1, 0--2->2
|
deba@430
|
966 |
///\endcode
|
deba@430
|
967 |
template<typename _Digraph, typename _ArcFilterMap>
|
deba@430
|
968 |
class ArcSubDigraphAdaptor :
|
deba@430
|
969 |
public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
|
deba@430
|
970 |
_ArcFilterMap, false> {
|
deba@430
|
971 |
public:
|
deba@430
|
972 |
typedef _Digraph Digraph;
|
deba@430
|
973 |
typedef _ArcFilterMap ArcFilterMap;
|
deba@430
|
974 |
|
deba@430
|
975 |
typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
|
deba@430
|
976 |
ArcFilterMap, false> Parent;
|
deba@430
|
977 |
protected:
|
deba@430
|
978 |
ConstMap<typename Digraph::Node, bool> const_true_map;
|
deba@430
|
979 |
|
deba@430
|
980 |
ArcSubDigraphAdaptor() : const_true_map(true) {
|
deba@430
|
981 |
Parent::setNodeFilterMap(const_true_map);
|
deba@430
|
982 |
}
|
deba@430
|
983 |
|
deba@430
|
984 |
public:
|
deba@430
|
985 |
|
deba@430
|
986 |
ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
|
deba@430
|
987 |
: Parent(), const_true_map(true) {
|
deba@430
|
988 |
Parent::setDigraph(digraph);
|
deba@430
|
989 |
Parent::setNodeFilterMap(const_true_map);
|
deba@430
|
990 |
Parent::setArcFilterMap(arc_filter);
|
deba@430
|
991 |
}
|
deba@430
|
992 |
|
deba@430
|
993 |
};
|
deba@430
|
994 |
|
deba@430
|
995 |
/// \brief Just gives back an arc sub digraph adaptor
|
deba@430
|
996 |
///
|
deba@430
|
997 |
/// Just gives back an arc sub digraph adaptor
|
deba@430
|
998 |
template<typename Digraph, typename ArcFilterMap>
|
deba@430
|
999 |
ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
|
deba@430
|
1000 |
arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
|
deba@430
|
1001 |
return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
|
deba@430
|
1002 |
}
|
deba@430
|
1003 |
|
deba@430
|
1004 |
template<typename Digraph, typename ArcFilterMap>
|
deba@430
|
1005 |
ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
|
deba@430
|
1006 |
arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
|
deba@430
|
1007 |
return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
|
deba@430
|
1008 |
(digraph, afm);
|
deba@430
|
1009 |
}
|
deba@430
|
1010 |
|
deba@430
|
1011 |
template <typename _Digraph>
|
deba@430
|
1012 |
class UndirDigraphAdaptorBase {
|
deba@430
|
1013 |
public:
|
deba@430
|
1014 |
typedef _Digraph Digraph;
|
deba@430
|
1015 |
typedef UndirDigraphAdaptorBase Adaptor;
|
deba@430
|
1016 |
|
deba@430
|
1017 |
typedef True UndirectedTag;
|
deba@430
|
1018 |
|
deba@430
|
1019 |
typedef typename Digraph::Arc Edge;
|
deba@430
|
1020 |
typedef typename Digraph::Node Node;
|
deba@430
|
1021 |
|
deba@430
|
1022 |
class Arc : public Edge {
|
deba@430
|
1023 |
friend class UndirDigraphAdaptorBase;
|
deba@430
|
1024 |
protected:
|
deba@430
|
1025 |
bool _forward;
|
deba@430
|
1026 |
|
deba@430
|
1027 |
Arc(const Edge& edge, bool forward) :
|
deba@430
|
1028 |
Edge(edge), _forward(forward) {}
|
deba@430
|
1029 |
|
deba@430
|
1030 |
public:
|
deba@430
|
1031 |
Arc() {}
|
deba@430
|
1032 |
|
deba@430
|
1033 |
Arc(Invalid) : Edge(INVALID), _forward(true) {}
|
deba@430
|
1034 |
|
deba@430
|
1035 |
bool operator==(const Arc &other) const {
|
deba@430
|
1036 |
return _forward == other._forward &&
|
deba@430
|
1037 |
static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
|
deba@430
|
1038 |
}
|
deba@430
|
1039 |
bool operator!=(const Arc &other) const {
|
deba@430
|
1040 |
return _forward != other._forward ||
|
deba@430
|
1041 |
static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
|
deba@430
|
1042 |
}
|
deba@430
|
1043 |
bool operator<(const Arc &other) const {
|
deba@430
|
1044 |
return _forward < other._forward ||
|
deba@430
|
1045 |
(_forward == other._forward &&
|
deba@430
|
1046 |
static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
|
deba@430
|
1047 |
}
|
deba@430
|
1048 |
};
|
deba@430
|
1049 |
|
deba@430
|
1050 |
|
deba@430
|
1051 |
|
deba@430
|
1052 |
void first(Node& n) const {
|
deba@430
|
1053 |
_digraph->first(n);
|
deba@430
|
1054 |
}
|
deba@430
|
1055 |
|
deba@430
|
1056 |
void next(Node& n) const {
|
deba@430
|
1057 |
_digraph->next(n);
|
deba@430
|
1058 |
}
|
deba@430
|
1059 |
|
deba@430
|
1060 |
void first(Arc& a) const {
|
deba@430
|
1061 |
_digraph->first(a);
|
deba@430
|
1062 |
a._forward = true;
|
deba@430
|
1063 |
}
|
deba@430
|
1064 |
|
deba@430
|
1065 |
void next(Arc& a) const {
|
deba@430
|
1066 |
if (a._forward) {
|
deba@430
|
1067 |
a._forward = false;
|
deba@430
|
1068 |
} else {
|
deba@430
|
1069 |
_digraph->next(a);
|
deba@430
|
1070 |
a._forward = true;
|
deba@430
|
1071 |
}
|
deba@430
|
1072 |
}
|
deba@430
|
1073 |
|
deba@430
|
1074 |
void first(Edge& e) const {
|
deba@430
|
1075 |
_digraph->first(e);
|
deba@430
|
1076 |
}
|
deba@430
|
1077 |
|
deba@430
|
1078 |
void next(Edge& e) const {
|
deba@430
|
1079 |
_digraph->next(e);
|
deba@430
|
1080 |
}
|
deba@430
|
1081 |
|
deba@430
|
1082 |
void firstOut(Arc& a, const Node& n) const {
|
deba@430
|
1083 |
_digraph->firstIn(a, n);
|
deba@430
|
1084 |
if( static_cast<const Edge&>(a) != INVALID ) {
|
deba@430
|
1085 |
a._forward = false;
|
deba@430
|
1086 |
} else {
|
deba@430
|
1087 |
_digraph->firstOut(a, n);
|
deba@430
|
1088 |
a._forward = true;
|
deba@430
|
1089 |
}
|
deba@430
|
1090 |
}
|
deba@430
|
1091 |
void nextOut(Arc &a) const {
|
deba@430
|
1092 |
if (!a._forward) {
|
deba@430
|
1093 |
Node n = _digraph->target(a);
|
deba@430
|
1094 |
_digraph->nextIn(a);
|
deba@430
|
1095 |
if (static_cast<const Edge&>(a) == INVALID ) {
|
deba@430
|
1096 |
_digraph->firstOut(a, n);
|
deba@430
|
1097 |
a._forward = true;
|
deba@430
|
1098 |
}
|
deba@430
|
1099 |
}
|
deba@430
|
1100 |
else {
|
deba@430
|
1101 |
_digraph->nextOut(a);
|
deba@430
|
1102 |
}
|
deba@430
|
1103 |
}
|
deba@430
|
1104 |
|
deba@430
|
1105 |
void firstIn(Arc &a, const Node &n) const {
|
deba@430
|
1106 |
_digraph->firstOut(a, n);
|
deba@430
|
1107 |
if (static_cast<const Edge&>(a) != INVALID ) {
|
deba@430
|
1108 |
a._forward = false;
|
deba@430
|
1109 |
} else {
|
deba@430
|
1110 |
_digraph->firstIn(a, n);
|
deba@430
|
1111 |
a._forward = true;
|
deba@430
|
1112 |
}
|
deba@430
|
1113 |
}
|
deba@430
|
1114 |
void nextIn(Arc &a) const {
|
deba@430
|
1115 |
if (!a._forward) {
|
deba@430
|
1116 |
Node n = _digraph->source(a);
|
deba@430
|
1117 |
_digraph->nextOut(a);
|
deba@430
|
1118 |
if( static_cast<const Edge&>(a) == INVALID ) {
|
deba@430
|
1119 |
_digraph->firstIn(a, n);
|
deba@430
|
1120 |
a._forward = true;
|
deba@430
|
1121 |
}
|
deba@430
|
1122 |
}
|
deba@430
|
1123 |
else {
|
deba@430
|
1124 |
_digraph->nextIn(a);
|
deba@430
|
1125 |
}
|
deba@430
|
1126 |
}
|
deba@430
|
1127 |
|
deba@430
|
1128 |
void firstInc(Edge &e, bool &d, const Node &n) const {
|
deba@430
|
1129 |
d = true;
|
deba@430
|
1130 |
_digraph->firstOut(e, n);
|
deba@430
|
1131 |
if (e != INVALID) return;
|
deba@430
|
1132 |
d = false;
|
deba@430
|
1133 |
_digraph->firstIn(e, n);
|
deba@430
|
1134 |
}
|
deba@430
|
1135 |
|
deba@430
|
1136 |
void nextInc(Edge &e, bool &d) const {
|
deba@430
|
1137 |
if (d) {
|
deba@430
|
1138 |
Node s = _digraph->source(e);
|
deba@430
|
1139 |
_digraph->nextOut(e);
|
deba@430
|
1140 |
if (e != INVALID) return;
|
deba@430
|
1141 |
d = false;
|
deba@430
|
1142 |
_digraph->firstIn(e, s);
|
deba@430
|
1143 |
} else {
|
deba@430
|
1144 |
_digraph->nextIn(e);
|
deba@430
|
1145 |
}
|
deba@430
|
1146 |
}
|
deba@430
|
1147 |
|
deba@430
|
1148 |
Node u(const Edge& e) const {
|
deba@430
|
1149 |
return _digraph->source(e);
|
deba@430
|
1150 |
}
|
deba@430
|
1151 |
|
deba@430
|
1152 |
Node v(const Edge& e) const {
|
deba@430
|
1153 |
return _digraph->target(e);
|
deba@430
|
1154 |
}
|
deba@430
|
1155 |
|
deba@430
|
1156 |
Node source(const Arc &a) const {
|
deba@430
|
1157 |
return a._forward ? _digraph->source(a) : _digraph->target(a);
|
deba@430
|
1158 |
}
|
deba@430
|
1159 |
|
deba@430
|
1160 |
Node target(const Arc &a) const {
|
deba@430
|
1161 |
return a._forward ? _digraph->target(a) : _digraph->source(a);
|
deba@430
|
1162 |
}
|
deba@430
|
1163 |
|
deba@430
|
1164 |
static Arc direct(const Edge &e, bool d) {
|
deba@430
|
1165 |
return Arc(e, d);
|
deba@430
|
1166 |
}
|
deba@430
|
1167 |
Arc direct(const Edge &e, const Node& n) const {
|
deba@430
|
1168 |
return Arc(e, _digraph->source(e) == n);
|
deba@430
|
1169 |
}
|
deba@430
|
1170 |
|
deba@430
|
1171 |
static bool direction(const Arc &a) { return a._forward; }
|
deba@430
|
1172 |
|
deba@430
|
1173 |
Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
|
deba@430
|
1174 |
Arc arcFromId(int ix) const {
|
deba@430
|
1175 |
return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
|
deba@430
|
1176 |
}
|
deba@430
|
1177 |
Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
|
deba@430
|
1178 |
|
deba@430
|
1179 |
int id(const Node &n) const { return _digraph->id(n); }
|
deba@430
|
1180 |
int id(const Arc &a) const {
|
deba@430
|
1181 |
return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
|
deba@430
|
1182 |
}
|
deba@430
|
1183 |
int id(const Edge &e) const { return _digraph->id(e); }
|
deba@430
|
1184 |
|
deba@430
|
1185 |
int maxNodeId() const { return _digraph->maxNodeId(); }
|
deba@430
|
1186 |
int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
|
deba@430
|
1187 |
int maxEdgeId() const { return _digraph->maxArcId(); }
|
deba@430
|
1188 |
|
deba@430
|
1189 |
Node addNode() { return _digraph->addNode(); }
|
deba@430
|
1190 |
Edge addEdge(const Node& u, const Node& v) {
|
deba@430
|
1191 |
return _digraph->addArc(u, v);
|
deba@430
|
1192 |
}
|
deba@430
|
1193 |
|
deba@430
|
1194 |
void erase(const Node& i) { _digraph->erase(i); }
|
deba@430
|
1195 |
void erase(const Edge& i) { _digraph->erase(i); }
|
deba@430
|
1196 |
|
deba@430
|
1197 |
void clear() { _digraph->clear(); }
|
deba@430
|
1198 |
|
deba@430
|
1199 |
typedef NodeNumTagIndicator<Digraph> NodeNumTag;
|
deba@430
|
1200 |
int nodeNum() const { return 2 * _digraph->arcNum(); }
|
deba@430
|
1201 |
typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
|
deba@430
|
1202 |
int arcNum() const { return 2 * _digraph->arcNum(); }
|
deba@430
|
1203 |
int edgeNum() const { return _digraph->arcNum(); }
|
deba@430
|
1204 |
|
deba@430
|
1205 |
typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
|
deba@430
|
1206 |
Arc findArc(Node s, Node t, Arc p = INVALID) const {
|
deba@430
|
1207 |
if (p == INVALID) {
|
deba@430
|
1208 |
Edge arc = _digraph->findArc(s, t);
|
deba@430
|
1209 |
if (arc != INVALID) return direct(arc, true);
|
deba@430
|
1210 |
arc = _digraph->findArc(t, s);
|
deba@430
|
1211 |
if (arc != INVALID) return direct(arc, false);
|
deba@430
|
1212 |
} else if (direction(p)) {
|
deba@430
|
1213 |
Edge arc = _digraph->findArc(s, t, p);
|
deba@430
|
1214 |
if (arc != INVALID) return direct(arc, true);
|
deba@430
|
1215 |
arc = _digraph->findArc(t, s);
|
deba@430
|
1216 |
if (arc != INVALID) return direct(arc, false);
|
deba@430
|
1217 |
} else {
|
deba@430
|
1218 |
Edge arc = _digraph->findArc(t, s, p);
|
deba@430
|
1219 |
if (arc != INVALID) return direct(arc, false);
|
deba@430
|
1220 |
}
|
deba@430
|
1221 |
return INVALID;
|
deba@430
|
1222 |
}
|
deba@430
|
1223 |
|
deba@430
|
1224 |
Edge findEdge(Node s, Node t, Edge p = INVALID) const {
|
deba@430
|
1225 |
if (s != t) {
|
deba@430
|
1226 |
if (p == INVALID) {
|
deba@430
|
1227 |
Edge arc = _digraph->findArc(s, t);
|
deba@430
|
1228 |
if (arc != INVALID) return arc;
|
deba@430
|
1229 |
arc = _digraph->findArc(t, s);
|
deba@430
|
1230 |
if (arc != INVALID) return arc;
|
deba@430
|
1231 |
} else if (_digraph->s(p) == s) {
|
deba@430
|
1232 |
Edge arc = _digraph->findArc(s, t, p);
|
deba@430
|
1233 |
if (arc != INVALID) return arc;
|
deba@430
|
1234 |
arc = _digraph->findArc(t, s);
|
deba@430
|
1235 |
if (arc != INVALID) return arc;
|
deba@430
|
1236 |
} else {
|
deba@430
|
1237 |
Edge arc = _digraph->findArc(t, s, p);
|
deba@430
|
1238 |
if (arc != INVALID) return arc;
|
deba@430
|
1239 |
}
|
deba@430
|
1240 |
} else {
|
deba@430
|
1241 |
return _digraph->findArc(s, t, p);
|
deba@430
|
1242 |
}
|
deba@430
|
1243 |
return INVALID;
|
deba@430
|
1244 |
}
|
deba@430
|
1245 |
|
deba@430
|
1246 |
private:
|
deba@430
|
1247 |
|
deba@430
|
1248 |
template <typename _Value>
|
deba@430
|
1249 |
class ArcMapBase {
|
deba@430
|
1250 |
private:
|
deba@430
|
1251 |
|
deba@430
|
1252 |
typedef typename Digraph::template ArcMap<_Value> MapImpl;
|
deba@430
|
1253 |
|
deba@430
|
1254 |
public:
|
deba@430
|
1255 |
|
deba@430
|
1256 |
typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
|
deba@430
|
1257 |
|
deba@430
|
1258 |
typedef _Value Value;
|
deba@430
|
1259 |
typedef Arc Key;
|
deba@430
|
1260 |
|
deba@430
|
1261 |
ArcMapBase(const Adaptor& adaptor) :
|
deba@430
|
1262 |
_forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
|
deba@430
|
1263 |
|
deba@430
|
1264 |
ArcMapBase(const Adaptor& adaptor, const Value& v)
|
deba@430
|
1265 |
: _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
|
deba@430
|
1266 |
|
deba@430
|
1267 |
void set(const Arc& a, const Value& v) {
|
deba@430
|
1268 |
if (direction(a)) {
|
deba@430
|
1269 |
_forward.set(a, v);
|
deba@430
|
1270 |
} else {
|
deba@430
|
1271 |
_backward.set(a, v);
|
deba@430
|
1272 |
}
|
deba@430
|
1273 |
}
|
deba@430
|
1274 |
|
deba@430
|
1275 |
typename MapTraits<MapImpl>::ConstReturnValue
|
deba@430
|
1276 |
operator[](const Arc& a) const {
|
deba@430
|
1277 |
if (direction(a)) {
|
deba@430
|
1278 |
return _forward[a];
|
deba@430
|
1279 |
} else {
|
deba@430
|
1280 |
return _backward[a];
|
deba@430
|
1281 |
}
|
deba@430
|
1282 |
}
|
deba@430
|
1283 |
|
deba@430
|
1284 |
typename MapTraits<MapImpl>::ReturnValue
|
deba@430
|
1285 |
operator[](const Arc& a) {
|
deba@430
|
1286 |
if (direction(a)) {
|
deba@430
|
1287 |
return _forward[a];
|
deba@430
|
1288 |
} else {
|
deba@430
|
1289 |
return _backward[a];
|
deba@430
|
1290 |
}
|
deba@430
|
1291 |
}
|
deba@430
|
1292 |
|
deba@430
|
1293 |
protected:
|
deba@430
|
1294 |
|
deba@430
|
1295 |
MapImpl _forward, _backward;
|
deba@430
|
1296 |
|
deba@430
|
1297 |
};
|
deba@430
|
1298 |
|
deba@430
|
1299 |
public:
|
deba@430
|
1300 |
|
deba@430
|
1301 |
template <typename _Value>
|
deba@430
|
1302 |
class NodeMap : public Digraph::template NodeMap<_Value> {
|
deba@430
|
1303 |
public:
|
deba@430
|
1304 |
|
deba@430
|
1305 |
typedef _Value Value;
|
deba@430
|
1306 |
typedef typename Digraph::template NodeMap<Value> Parent;
|
deba@430
|
1307 |
|
deba@430
|
1308 |
explicit NodeMap(const Adaptor& adaptor)
|
deba@430
|
1309 |
: Parent(*adaptor._digraph) {}
|
deba@430
|
1310 |
|
deba@430
|
1311 |
NodeMap(const Adaptor& adaptor, const _Value& value)
|
deba@430
|
1312 |
: Parent(*adaptor._digraph, value) { }
|
deba@430
|
1313 |
|
deba@430
|
1314 |
private:
|
deba@430
|
1315 |
NodeMap& operator=(const NodeMap& cmap) {
|
deba@430
|
1316 |
return operator=<NodeMap>(cmap);
|
deba@430
|
1317 |
}
|
deba@430
|
1318 |
|
deba@430
|
1319 |
template <typename CMap>
|
deba@430
|
1320 |
NodeMap& operator=(const CMap& cmap) {
|
deba@430
|
1321 |
Parent::operator=(cmap);
|
deba@430
|
1322 |
return *this;
|
deba@430
|
1323 |
}
|
deba@430
|
1324 |
|
deba@430
|
1325 |
};
|
deba@430
|
1326 |
|
deba@430
|
1327 |
template <typename _Value>
|
deba@430
|
1328 |
class ArcMap
|
deba@430
|
1329 |
: public SubMapExtender<Adaptor, ArcMapBase<_Value> >
|
deba@430
|
1330 |
{
|
deba@430
|
1331 |
public:
|
deba@430
|
1332 |
typedef _Value Value;
|
deba@430
|
1333 |
typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
|
deba@430
|
1334 |
|
deba@430
|
1335 |
ArcMap(const Adaptor& adaptor)
|
deba@430
|
1336 |
: Parent(adaptor) {}
|
deba@430
|
1337 |
|
deba@430
|
1338 |
ArcMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
1339 |
: Parent(adaptor, value) {}
|
deba@430
|
1340 |
|
deba@430
|
1341 |
private:
|
deba@430
|
1342 |
ArcMap& operator=(const ArcMap& cmap) {
|
deba@430
|
1343 |
return operator=<ArcMap>(cmap);
|
deba@430
|
1344 |
}
|
deba@430
|
1345 |
|
deba@430
|
1346 |
template <typename CMap>
|
deba@430
|
1347 |
ArcMap& operator=(const CMap& cmap) {
|
deba@430
|
1348 |
Parent::operator=(cmap);
|
deba@430
|
1349 |
return *this;
|
deba@430
|
1350 |
}
|
deba@430
|
1351 |
};
|
deba@430
|
1352 |
|
deba@430
|
1353 |
template <typename _Value>
|
deba@430
|
1354 |
class EdgeMap : public Digraph::template ArcMap<_Value> {
|
deba@430
|
1355 |
public:
|
deba@430
|
1356 |
|
deba@430
|
1357 |
typedef _Value Value;
|
deba@430
|
1358 |
typedef typename Digraph::template ArcMap<Value> Parent;
|
deba@430
|
1359 |
|
deba@430
|
1360 |
explicit EdgeMap(const Adaptor& adaptor)
|
deba@430
|
1361 |
: Parent(*adaptor._digraph) {}
|
deba@430
|
1362 |
|
deba@430
|
1363 |
EdgeMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
1364 |
: Parent(*adaptor._digraph, value) {}
|
deba@430
|
1365 |
|
deba@430
|
1366 |
private:
|
deba@430
|
1367 |
EdgeMap& operator=(const EdgeMap& cmap) {
|
deba@430
|
1368 |
return operator=<EdgeMap>(cmap);
|
deba@430
|
1369 |
}
|
deba@430
|
1370 |
|
deba@430
|
1371 |
template <typename CMap>
|
deba@430
|
1372 |
EdgeMap& operator=(const CMap& cmap) {
|
deba@430
|
1373 |
Parent::operator=(cmap);
|
deba@430
|
1374 |
return *this;
|
deba@430
|
1375 |
}
|
deba@430
|
1376 |
|
deba@430
|
1377 |
};
|
deba@430
|
1378 |
|
deba@430
|
1379 |
typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
|
deba@430
|
1380 |
NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
|
deba@430
|
1381 |
|
deba@430
|
1382 |
protected:
|
deba@430
|
1383 |
|
deba@430
|
1384 |
UndirDigraphAdaptorBase() : _digraph(0) {}
|
deba@430
|
1385 |
|
deba@430
|
1386 |
Digraph* _digraph;
|
deba@430
|
1387 |
|
deba@430
|
1388 |
void setDigraph(Digraph& digraph) {
|
deba@430
|
1389 |
_digraph = &digraph;
|
deba@430
|
1390 |
}
|
deba@430
|
1391 |
|
deba@430
|
1392 |
};
|
deba@430
|
1393 |
|
deba@430
|
1394 |
///\ingroup graph_adaptors
|
deba@430
|
1395 |
///
|
deba@430
|
1396 |
/// \brief An graph is made from a directed digraph by an adaptor
|
deba@430
|
1397 |
///
|
deba@430
|
1398 |
/// This adaptor makes an undirected graph from a directed
|
deba@430
|
1399 |
/// digraph. All arc of the underlying will be showed in the adaptor
|
deba@430
|
1400 |
/// as an edge. Let's see an informal example about using
|
deba@430
|
1401 |
/// this adaptor:
|
deba@430
|
1402 |
///
|
deba@430
|
1403 |
/// There is a network of the streets of a town. Of course there are
|
deba@430
|
1404 |
/// some one-way street in the town hence the network is a directed
|
deba@430
|
1405 |
/// one. There is a crazy driver who go oppositely in the one-way
|
deba@430
|
1406 |
/// street without moral sense. Of course he can pass this streets
|
deba@430
|
1407 |
/// slower than the regular way, in fact his speed is half of the
|
deba@430
|
1408 |
/// normal speed. How long should he drive to get from a source
|
deba@430
|
1409 |
/// point to the target? Let see the example code which calculate it:
|
deba@430
|
1410 |
///
|
deba@430
|
1411 |
/// \todo BadCode, SimpleMap does no exists
|
deba@430
|
1412 |
///\code
|
deba@430
|
1413 |
/// typedef UndirDigraphAdaptor<Digraph> Graph;
|
deba@430
|
1414 |
/// Graph graph(digraph);
|
deba@430
|
1415 |
///
|
deba@430
|
1416 |
/// typedef SimpleMap<LengthMap> FLengthMap;
|
deba@430
|
1417 |
/// FLengthMap flength(length);
|
deba@430
|
1418 |
///
|
deba@430
|
1419 |
/// typedef ScaleMap<LengthMap> RLengthMap;
|
deba@430
|
1420 |
/// RLengthMap rlength(length, 2.0);
|
deba@430
|
1421 |
///
|
deba@430
|
1422 |
/// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
|
deba@430
|
1423 |
/// ULengthMap ulength(flength, rlength);
|
deba@430
|
1424 |
///
|
deba@430
|
1425 |
/// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
|
deba@430
|
1426 |
/// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
|
deba@430
|
1427 |
///\endcode
|
deba@430
|
1428 |
///
|
deba@430
|
1429 |
/// The combined arc map makes the length map for the undirected
|
deba@430
|
1430 |
/// graph. It is created from a forward and reverse map. The forward
|
deba@430
|
1431 |
/// map is created from the original length map with a SimpleMap
|
deba@430
|
1432 |
/// adaptor which just makes a read-write map from the reference map
|
deba@430
|
1433 |
/// i.e. it forgets that it can be return reference to values. The
|
deba@430
|
1434 |
/// reverse map is just the scaled original map with the ScaleMap
|
deba@430
|
1435 |
/// adaptor. The combination solves that passing the reverse way
|
deba@430
|
1436 |
/// takes double time than the original. To get the driving time we
|
deba@430
|
1437 |
/// run the dijkstra algorithm on the graph.
|
deba@430
|
1438 |
template<typename _Digraph>
|
deba@430
|
1439 |
class UndirDigraphAdaptor
|
deba@430
|
1440 |
: public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
|
deba@430
|
1441 |
public:
|
deba@430
|
1442 |
typedef _Digraph Digraph;
|
deba@430
|
1443 |
typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
|
deba@430
|
1444 |
protected:
|
deba@430
|
1445 |
UndirDigraphAdaptor() { }
|
deba@430
|
1446 |
public:
|
deba@430
|
1447 |
|
deba@430
|
1448 |
/// \brief Constructor
|
deba@430
|
1449 |
///
|
deba@430
|
1450 |
/// Constructor
|
deba@430
|
1451 |
UndirDigraphAdaptor(_Digraph& _digraph) {
|
deba@430
|
1452 |
setDigraph(_digraph);
|
deba@430
|
1453 |
}
|
deba@430
|
1454 |
|
deba@430
|
1455 |
/// \brief ArcMap combined from two original ArcMap
|
deba@430
|
1456 |
///
|
deba@430
|
1457 |
/// This class adapts two original digraph ArcMap to
|
deba@430
|
1458 |
/// get an arc map on the adaptor.
|
deba@430
|
1459 |
template <typename _ForwardMap, typename _BackwardMap>
|
deba@430
|
1460 |
class CombinedArcMap {
|
deba@430
|
1461 |
public:
|
deba@430
|
1462 |
|
deba@430
|
1463 |
typedef _ForwardMap ForwardMap;
|
deba@430
|
1464 |
typedef _BackwardMap BackwardMap;
|
deba@430
|
1465 |
|
deba@430
|
1466 |
typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
|
deba@430
|
1467 |
|
deba@430
|
1468 |
typedef typename ForwardMap::Value Value;
|
deba@430
|
1469 |
typedef typename Parent::Arc Key;
|
deba@430
|
1470 |
|
deba@430
|
1471 |
/// \brief Constructor
|
deba@430
|
1472 |
///
|
deba@430
|
1473 |
/// Constructor
|
deba@430
|
1474 |
CombinedArcMap() : _forward(0), _backward(0) {}
|
deba@430
|
1475 |
|
deba@430
|
1476 |
/// \brief Constructor
|
deba@430
|
1477 |
///
|
deba@430
|
1478 |
/// Constructor
|
deba@430
|
1479 |
CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
|
deba@430
|
1480 |
: _forward(&forward), _backward(&backward) {}
|
deba@430
|
1481 |
|
deba@430
|
1482 |
|
deba@430
|
1483 |
/// \brief Sets the value associated with a key.
|
deba@430
|
1484 |
///
|
deba@430
|
1485 |
/// Sets the value associated with a key.
|
deba@430
|
1486 |
void set(const Key& e, const Value& a) {
|
deba@430
|
1487 |
if (Parent::direction(e)) {
|
deba@430
|
1488 |
_forward->set(e, a);
|
deba@430
|
1489 |
} else {
|
deba@430
|
1490 |
_backward->set(e, a);
|
deba@430
|
1491 |
}
|
deba@430
|
1492 |
}
|
deba@430
|
1493 |
|
deba@430
|
1494 |
/// \brief Returns the value associated with a key.
|
deba@430
|
1495 |
///
|
deba@430
|
1496 |
/// Returns the value associated with a key.
|
deba@430
|
1497 |
typename MapTraits<ForwardMap>::ConstReturnValue
|
deba@430
|
1498 |
operator[](const Key& e) const {
|
deba@430
|
1499 |
if (Parent::direction(e)) {
|
deba@430
|
1500 |
return (*_forward)[e];
|
deba@430
|
1501 |
} else {
|
deba@430
|
1502 |
return (*_backward)[e];
|
deba@430
|
1503 |
}
|
deba@430
|
1504 |
}
|
deba@430
|
1505 |
|
deba@430
|
1506 |
/// \brief Returns the value associated with a key.
|
deba@430
|
1507 |
///
|
deba@430
|
1508 |
/// Returns the value associated with a key.
|
deba@430
|
1509 |
typename MapTraits<ForwardMap>::ReturnValue
|
deba@430
|
1510 |
operator[](const Key& e) {
|
deba@430
|
1511 |
if (Parent::direction(e)) {
|
deba@430
|
1512 |
return (*_forward)[e];
|
deba@430
|
1513 |
} else {
|
deba@430
|
1514 |
return (*_backward)[e];
|
deba@430
|
1515 |
}
|
deba@430
|
1516 |
}
|
deba@430
|
1517 |
|
deba@430
|
1518 |
/// \brief Sets the forward map
|
deba@430
|
1519 |
///
|
deba@430
|
1520 |
/// Sets the forward map
|
deba@430
|
1521 |
void setForwardMap(ForwardMap& forward) {
|
deba@430
|
1522 |
_forward = &forward;
|
deba@430
|
1523 |
}
|
deba@430
|
1524 |
|
deba@430
|
1525 |
/// \brief Sets the backward map
|
deba@430
|
1526 |
///
|
deba@430
|
1527 |
/// Sets the backward map
|
deba@430
|
1528 |
void setBackwardMap(BackwardMap& backward) {
|
deba@430
|
1529 |
_backward = &backward;
|
deba@430
|
1530 |
}
|
deba@430
|
1531 |
|
deba@430
|
1532 |
protected:
|
deba@430
|
1533 |
|
deba@430
|
1534 |
ForwardMap* _forward;
|
deba@430
|
1535 |
BackwardMap* _backward;
|
deba@430
|
1536 |
|
deba@430
|
1537 |
};
|
deba@430
|
1538 |
|
deba@430
|
1539 |
};
|
deba@430
|
1540 |
|
deba@430
|
1541 |
/// \brief Just gives back an undir digraph adaptor
|
deba@430
|
1542 |
///
|
deba@430
|
1543 |
/// Just gives back an undir digraph adaptor
|
deba@430
|
1544 |
template<typename Digraph>
|
deba@430
|
1545 |
UndirDigraphAdaptor<const Digraph>
|
deba@430
|
1546 |
undirDigraphAdaptor(const Digraph& digraph) {
|
deba@430
|
1547 |
return UndirDigraphAdaptor<const Digraph>(digraph);
|
deba@430
|
1548 |
}
|
deba@430
|
1549 |
|
deba@430
|
1550 |
template<typename _Digraph,
|
deba@430
|
1551 |
typename _CapacityMap = typename _Digraph::template ArcMap<int>,
|
deba@430
|
1552 |
typename _FlowMap = _CapacityMap,
|
deba@430
|
1553 |
typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
|
deba@430
|
1554 |
class ResForwardFilter {
|
deba@430
|
1555 |
public:
|
deba@430
|
1556 |
|
deba@430
|
1557 |
typedef _Digraph Digraph;
|
deba@430
|
1558 |
typedef _CapacityMap CapacityMap;
|
deba@430
|
1559 |
typedef _FlowMap FlowMap;
|
deba@430
|
1560 |
typedef _Tolerance Tolerance;
|
deba@430
|
1561 |
|
deba@430
|
1562 |
typedef typename Digraph::Arc Key;
|
deba@430
|
1563 |
typedef bool Value;
|
deba@430
|
1564 |
|
deba@430
|
1565 |
private:
|
deba@430
|
1566 |
|
deba@430
|
1567 |
const CapacityMap* _capacity;
|
deba@430
|
1568 |
const FlowMap* _flow;
|
deba@430
|
1569 |
Tolerance _tolerance;
|
deba@430
|
1570 |
public:
|
deba@430
|
1571 |
|
deba@430
|
1572 |
ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
|
deba@430
|
1573 |
const Tolerance& tolerance = Tolerance())
|
deba@430
|
1574 |
: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
|
deba@430
|
1575 |
|
deba@430
|
1576 |
ResForwardFilter(const Tolerance& tolerance = Tolerance())
|
deba@430
|
1577 |
: _capacity(0), _flow(0), _tolerance(tolerance) { }
|
deba@430
|
1578 |
|
deba@430
|
1579 |
void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
|
deba@430
|
1580 |
void setFlow(const FlowMap& flow) { _flow = &flow; }
|
deba@430
|
1581 |
|
deba@430
|
1582 |
bool operator[](const typename Digraph::Arc& a) const {
|
deba@430
|
1583 |
return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
|
deba@430
|
1584 |
}
|
deba@430
|
1585 |
};
|
deba@430
|
1586 |
|
deba@430
|
1587 |
template<typename _Digraph,
|
deba@430
|
1588 |
typename _CapacityMap = typename _Digraph::template ArcMap<int>,
|
deba@430
|
1589 |
typename _FlowMap = _CapacityMap,
|
deba@430
|
1590 |
typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
|
deba@430
|
1591 |
class ResBackwardFilter {
|
deba@430
|
1592 |
public:
|
deba@430
|
1593 |
|
deba@430
|
1594 |
typedef _Digraph Digraph;
|
deba@430
|
1595 |
typedef _CapacityMap CapacityMap;
|
deba@430
|
1596 |
typedef _FlowMap FlowMap;
|
deba@430
|
1597 |
typedef _Tolerance Tolerance;
|
deba@430
|
1598 |
|
deba@430
|
1599 |
typedef typename Digraph::Arc Key;
|
deba@430
|
1600 |
typedef bool Value;
|
deba@430
|
1601 |
|
deba@430
|
1602 |
private:
|
deba@430
|
1603 |
|
deba@430
|
1604 |
const CapacityMap* _capacity;
|
deba@430
|
1605 |
const FlowMap* _flow;
|
deba@430
|
1606 |
Tolerance _tolerance;
|
deba@430
|
1607 |
|
deba@430
|
1608 |
public:
|
deba@430
|
1609 |
|
deba@430
|
1610 |
ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
|
deba@430
|
1611 |
const Tolerance& tolerance = Tolerance())
|
deba@430
|
1612 |
: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
|
deba@430
|
1613 |
ResBackwardFilter(const Tolerance& tolerance = Tolerance())
|
deba@430
|
1614 |
: _capacity(0), _flow(0), _tolerance(tolerance) { }
|
deba@430
|
1615 |
|
deba@430
|
1616 |
void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
|
deba@430
|
1617 |
void setFlow(const FlowMap& flow) { _flow = &flow; }
|
deba@430
|
1618 |
|
deba@430
|
1619 |
bool operator[](const typename Digraph::Arc& a) const {
|
deba@430
|
1620 |
return _tolerance.positive((*_flow)[a]);
|
deba@430
|
1621 |
}
|
deba@430
|
1622 |
};
|
deba@430
|
1623 |
|
deba@430
|
1624 |
|
deba@430
|
1625 |
///\ingroup graph_adaptors
|
deba@430
|
1626 |
///
|
deba@430
|
1627 |
///\brief An adaptor for composing the residual graph for directed
|
deba@430
|
1628 |
///flow and circulation problems.
|
deba@430
|
1629 |
///
|
deba@430
|
1630 |
///An adaptor for composing the residual graph for directed flow and
|
deba@430
|
1631 |
///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph
|
deba@430
|
1632 |
///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
|
deba@430
|
1633 |
///\f$, be functions on the arc-set.
|
deba@430
|
1634 |
///
|
deba@430
|
1635 |
///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
|
deba@430
|
1636 |
///for a flow and \f$ c \f$ for a capacity function. Suppose that a
|
deba@430
|
1637 |
///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
|
deba@430
|
1638 |
///
|
deba@430
|
1639 |
///\code
|
deba@430
|
1640 |
/// ListDigraph g;
|
deba@430
|
1641 |
///\endcode
|
deba@430
|
1642 |
///
|
deba@430
|
1643 |
///Then ResDigraphAdaptor implements the digraph structure with
|
deba@430
|
1644 |
/// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}
|
deba@430
|
1645 |
/// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
|
deba@430
|
1646 |
/// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
|
deba@430
|
1647 |
/// called residual graph. When we take the union \f$
|
deba@430
|
1648 |
/// A_{forward}\cup A_{backward} \f$, multilicities are counted,
|
deba@430
|
1649 |
/// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$
|
deba@430
|
1650 |
/// A_{backward} \f$, then in the adaptor it appears twice. The
|
deba@430
|
1651 |
/// following code shows how such an instance can be constructed.
|
deba@430
|
1652 |
///
|
deba@430
|
1653 |
///\code
|
deba@430
|
1654 |
/// typedef ListDigraph Digraph;
|
deba@430
|
1655 |
/// IntArcMap f(g), c(g);
|
deba@430
|
1656 |
/// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);
|
deba@430
|
1657 |
///\endcode
|
deba@430
|
1658 |
template<typename _Digraph,
|
deba@430
|
1659 |
typename _CapacityMap = typename _Digraph::template ArcMap<int>,
|
deba@430
|
1660 |
typename _FlowMap = _CapacityMap,
|
deba@430
|
1661 |
typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
|
deba@430
|
1662 |
class ResDigraphAdaptor :
|
deba@430
|
1663 |
public ArcSubDigraphAdaptor<
|
deba@430
|
1664 |
UndirDigraphAdaptor<const _Digraph>,
|
deba@430
|
1665 |
typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
|
deba@430
|
1666 |
ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,
|
deba@430
|
1667 |
ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
|
deba@430
|
1668 |
public:
|
deba@430
|
1669 |
|
deba@430
|
1670 |
typedef _Digraph Digraph;
|
deba@430
|
1671 |
typedef _CapacityMap CapacityMap;
|
deba@430
|
1672 |
typedef _FlowMap FlowMap;
|
deba@430
|
1673 |
typedef _Tolerance Tolerance;
|
deba@430
|
1674 |
|
deba@430
|
1675 |
typedef typename CapacityMap::Value Value;
|
deba@430
|
1676 |
typedef ResDigraphAdaptor Adaptor;
|
deba@430
|
1677 |
|
deba@430
|
1678 |
protected:
|
deba@430
|
1679 |
|
deba@430
|
1680 |
typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
|
deba@430
|
1681 |
|
deba@430
|
1682 |
typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
|
deba@430
|
1683 |
ForwardFilter;
|
deba@430
|
1684 |
|
deba@430
|
1685 |
typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
|
deba@430
|
1686 |
BackwardFilter;
|
deba@430
|
1687 |
|
deba@430
|
1688 |
typedef typename UndirDigraph::
|
deba@430
|
1689 |
template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
|
deba@430
|
1690 |
|
deba@430
|
1691 |
typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
|
deba@430
|
1692 |
|
deba@430
|
1693 |
const CapacityMap* _capacity;
|
deba@430
|
1694 |
FlowMap* _flow;
|
deba@430
|
1695 |
|
deba@430
|
1696 |
UndirDigraph _graph;
|
deba@430
|
1697 |
ForwardFilter _forward_filter;
|
deba@430
|
1698 |
BackwardFilter _backward_filter;
|
deba@430
|
1699 |
ArcFilter _arc_filter;
|
deba@430
|
1700 |
|
deba@430
|
1701 |
void setCapacityMap(const CapacityMap& capacity) {
|
deba@430
|
1702 |
_capacity = &capacity;
|
deba@430
|
1703 |
_forward_filter.setCapacity(capacity);
|
deba@430
|
1704 |
_backward_filter.setCapacity(capacity);
|
deba@430
|
1705 |
}
|
deba@430
|
1706 |
|
deba@430
|
1707 |
void setFlowMap(FlowMap& flow) {
|
deba@430
|
1708 |
_flow = &flow;
|
deba@430
|
1709 |
_forward_filter.setFlow(flow);
|
deba@430
|
1710 |
_backward_filter.setFlow(flow);
|
deba@430
|
1711 |
}
|
deba@430
|
1712 |
|
deba@430
|
1713 |
public:
|
deba@430
|
1714 |
|
deba@430
|
1715 |
/// \brief Constructor of the residual digraph.
|
deba@430
|
1716 |
///
|
deba@430
|
1717 |
/// Constructor of the residual graph. The parameters are the digraph type,
|
deba@430
|
1718 |
/// the flow map, the capacity map and a tolerance object.
|
deba@430
|
1719 |
ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
|
deba@430
|
1720 |
FlowMap& flow, const Tolerance& tolerance = Tolerance())
|
deba@430
|
1721 |
: Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
|
deba@430
|
1722 |
_forward_filter(capacity, flow, tolerance),
|
deba@430
|
1723 |
_backward_filter(capacity, flow, tolerance),
|
deba@430
|
1724 |
_arc_filter(_forward_filter, _backward_filter)
|
deba@430
|
1725 |
{
|
deba@430
|
1726 |
Parent::setDigraph(_graph);
|
deba@430
|
1727 |
Parent::setArcFilterMap(_arc_filter);
|
deba@430
|
1728 |
}
|
deba@430
|
1729 |
|
deba@430
|
1730 |
typedef typename Parent::Arc Arc;
|
deba@430
|
1731 |
|
deba@430
|
1732 |
/// \brief Gives back the residual capacity of the arc.
|
deba@430
|
1733 |
///
|
deba@430
|
1734 |
/// Gives back the residual capacity of the arc.
|
deba@430
|
1735 |
Value rescap(const Arc& arc) const {
|
deba@430
|
1736 |
if (UndirDigraph::direction(arc)) {
|
deba@430
|
1737 |
return (*_capacity)[arc] - (*_flow)[arc];
|
deba@430
|
1738 |
} else {
|
deba@430
|
1739 |
return (*_flow)[arc];
|
deba@430
|
1740 |
}
|
deba@430
|
1741 |
}
|
deba@430
|
1742 |
|
deba@430
|
1743 |
/// \brief Augment on the given arc in the residual digraph.
|
deba@430
|
1744 |
///
|
deba@430
|
1745 |
/// Augment on the given arc in the residual digraph. It increase
|
deba@430
|
1746 |
/// or decrease the flow on the original arc depend on the direction
|
deba@430
|
1747 |
/// of the residual arc.
|
deba@430
|
1748 |
void augment(const Arc& e, const Value& a) const {
|
deba@430
|
1749 |
if (UndirDigraph::direction(e)) {
|
deba@430
|
1750 |
_flow->set(e, (*_flow)[e] + a);
|
deba@430
|
1751 |
} else {
|
deba@430
|
1752 |
_flow->set(e, (*_flow)[e] - a);
|
deba@430
|
1753 |
}
|
deba@430
|
1754 |
}
|
deba@430
|
1755 |
|
deba@430
|
1756 |
/// \brief Returns the direction of the arc.
|
deba@430
|
1757 |
///
|
deba@430
|
1758 |
/// Returns true when the arc is same oriented as the original arc.
|
deba@430
|
1759 |
static bool forward(const Arc& e) {
|
deba@430
|
1760 |
return UndirDigraph::direction(e);
|
deba@430
|
1761 |
}
|
deba@430
|
1762 |
|
deba@430
|
1763 |
/// \brief Returns the direction of the arc.
|
deba@430
|
1764 |
///
|
deba@430
|
1765 |
/// Returns true when the arc is opposite oriented as the original arc.
|
deba@430
|
1766 |
static bool backward(const Arc& e) {
|
deba@430
|
1767 |
return !UndirDigraph::direction(e);
|
deba@430
|
1768 |
}
|
deba@430
|
1769 |
|
deba@430
|
1770 |
/// \brief Gives back the forward oriented residual arc.
|
deba@430
|
1771 |
///
|
deba@430
|
1772 |
/// Gives back the forward oriented residual arc.
|
deba@430
|
1773 |
static Arc forward(const typename Digraph::Arc& e) {
|
deba@430
|
1774 |
return UndirDigraph::direct(e, true);
|
deba@430
|
1775 |
}
|
deba@430
|
1776 |
|
deba@430
|
1777 |
/// \brief Gives back the backward oriented residual arc.
|
deba@430
|
1778 |
///
|
deba@430
|
1779 |
/// Gives back the backward oriented residual arc.
|
deba@430
|
1780 |
static Arc backward(const typename Digraph::Arc& e) {
|
deba@430
|
1781 |
return UndirDigraph::direct(e, false);
|
deba@430
|
1782 |
}
|
deba@430
|
1783 |
|
deba@430
|
1784 |
/// \brief Residual capacity map.
|
deba@430
|
1785 |
///
|
deba@430
|
1786 |
/// In generic residual digraphs the residual capacity can be obtained
|
deba@430
|
1787 |
/// as a map.
|
deba@430
|
1788 |
class ResCap {
|
deba@430
|
1789 |
protected:
|
deba@430
|
1790 |
const Adaptor* _adaptor;
|
deba@430
|
1791 |
public:
|
deba@430
|
1792 |
typedef Arc Key;
|
deba@430
|
1793 |
typedef typename _CapacityMap::Value Value;
|
deba@430
|
1794 |
|
deba@430
|
1795 |
ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
|
deba@430
|
1796 |
|
deba@430
|
1797 |
Value operator[](const Arc& e) const {
|
deba@430
|
1798 |
return _adaptor->rescap(e);
|
deba@430
|
1799 |
}
|
deba@430
|
1800 |
|
deba@430
|
1801 |
};
|
deba@430
|
1802 |
|
deba@430
|
1803 |
};
|
deba@430
|
1804 |
|
deba@430
|
1805 |
/// \brief Base class for split digraph adaptor
|
deba@430
|
1806 |
///
|
deba@430
|
1807 |
/// Base class of split digraph adaptor. In most case you do not need to
|
deba@430
|
1808 |
/// use it directly but the documented member functions of this class can
|
deba@430
|
1809 |
/// be used with the SplitDigraphAdaptor class.
|
deba@430
|
1810 |
/// \sa SplitDigraphAdaptor
|
deba@430
|
1811 |
template <typename _Digraph>
|
deba@430
|
1812 |
class SplitDigraphAdaptorBase {
|
deba@430
|
1813 |
public:
|
deba@430
|
1814 |
|
deba@430
|
1815 |
typedef _Digraph Digraph;
|
deba@430
|
1816 |
typedef DigraphAdaptorBase<const _Digraph> Parent;
|
deba@430
|
1817 |
typedef SplitDigraphAdaptorBase Adaptor;
|
deba@430
|
1818 |
|
deba@430
|
1819 |
typedef typename Digraph::Node DigraphNode;
|
deba@430
|
1820 |
typedef typename Digraph::Arc DigraphArc;
|
deba@430
|
1821 |
|
deba@430
|
1822 |
class Node;
|
deba@430
|
1823 |
class Arc;
|
deba@430
|
1824 |
|
deba@430
|
1825 |
private:
|
deba@430
|
1826 |
|
deba@430
|
1827 |
template <typename T> class NodeMapBase;
|
deba@430
|
1828 |
template <typename T> class ArcMapBase;
|
deba@430
|
1829 |
|
deba@430
|
1830 |
public:
|
deba@430
|
1831 |
|
deba@430
|
1832 |
class Node : public DigraphNode {
|
deba@430
|
1833 |
friend class SplitDigraphAdaptorBase;
|
deba@430
|
1834 |
template <typename T> friend class NodeMapBase;
|
deba@430
|
1835 |
private:
|
deba@430
|
1836 |
|
deba@430
|
1837 |
bool _in;
|
deba@430
|
1838 |
Node(DigraphNode node, bool in)
|
deba@430
|
1839 |
: DigraphNode(node), _in(in) {}
|
deba@430
|
1840 |
|
deba@430
|
1841 |
public:
|
deba@430
|
1842 |
|
deba@430
|
1843 |
Node() {}
|
deba@430
|
1844 |
Node(Invalid) : DigraphNode(INVALID), _in(true) {}
|
deba@430
|
1845 |
|
deba@430
|
1846 |
bool operator==(const Node& node) const {
|
deba@430
|
1847 |
return DigraphNode::operator==(node) && _in == node._in;
|
deba@430
|
1848 |
}
|
deba@430
|
1849 |
|
deba@430
|
1850 |
bool operator!=(const Node& node) const {
|
deba@430
|
1851 |
return !(*this == node);
|
deba@430
|
1852 |
}
|
deba@430
|
1853 |
|
deba@430
|
1854 |
bool operator<(const Node& node) const {
|
deba@430
|
1855 |
return DigraphNode::operator<(node) ||
|
deba@430
|
1856 |
(DigraphNode::operator==(node) && _in < node._in);
|
deba@430
|
1857 |
}
|
deba@430
|
1858 |
};
|
deba@430
|
1859 |
|
deba@430
|
1860 |
class Arc {
|
deba@430
|
1861 |
friend class SplitDigraphAdaptorBase;
|
deba@430
|
1862 |
template <typename T> friend class ArcMapBase;
|
deba@430
|
1863 |
private:
|
deba@430
|
1864 |
typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
|
deba@430
|
1865 |
|
deba@430
|
1866 |
explicit Arc(const DigraphArc& arc) : _item(arc) {}
|
deba@430
|
1867 |
explicit Arc(const DigraphNode& node) : _item(node) {}
|
deba@430
|
1868 |
|
deba@430
|
1869 |
ArcImpl _item;
|
deba@430
|
1870 |
|
deba@430
|
1871 |
public:
|
deba@430
|
1872 |
Arc() {}
|
deba@430
|
1873 |
Arc(Invalid) : _item(DigraphArc(INVALID)) {}
|
deba@430
|
1874 |
|
deba@430
|
1875 |
bool operator==(const Arc& arc) const {
|
deba@430
|
1876 |
if (_item.firstState()) {
|
deba@430
|
1877 |
if (arc._item.firstState()) {
|
deba@430
|
1878 |
return _item.first() == arc._item.first();
|
deba@430
|
1879 |
}
|
deba@430
|
1880 |
} else {
|
deba@430
|
1881 |
if (arc._item.secondState()) {
|
deba@430
|
1882 |
return _item.second() == arc._item.second();
|
deba@430
|
1883 |
}
|
deba@430
|
1884 |
}
|
deba@430
|
1885 |
return false;
|
deba@430
|
1886 |
}
|
deba@430
|
1887 |
|
deba@430
|
1888 |
bool operator!=(const Arc& arc) const {
|
deba@430
|
1889 |
return !(*this == arc);
|
deba@430
|
1890 |
}
|
deba@430
|
1891 |
|
deba@430
|
1892 |
bool operator<(const Arc& arc) const {
|
deba@430
|
1893 |
if (_item.firstState()) {
|
deba@430
|
1894 |
if (arc._item.firstState()) {
|
deba@430
|
1895 |
return _item.first() < arc._item.first();
|
deba@430
|
1896 |
}
|
deba@430
|
1897 |
return false;
|
deba@430
|
1898 |
} else {
|
deba@430
|
1899 |
if (arc._item.secondState()) {
|
deba@430
|
1900 |
return _item.second() < arc._item.second();
|
deba@430
|
1901 |
}
|
deba@430
|
1902 |
return true;
|
deba@430
|
1903 |
}
|
deba@430
|
1904 |
}
|
deba@430
|
1905 |
|
deba@430
|
1906 |
operator DigraphArc() const { return _item.first(); }
|
deba@430
|
1907 |
operator DigraphNode() const { return _item.second(); }
|
deba@430
|
1908 |
|
deba@430
|
1909 |
};
|
deba@430
|
1910 |
|
deba@430
|
1911 |
void first(Node& n) const {
|
deba@430
|
1912 |
_digraph->first(n);
|
deba@430
|
1913 |
n._in = true;
|
deba@430
|
1914 |
}
|
deba@430
|
1915 |
|
deba@430
|
1916 |
void next(Node& n) const {
|
deba@430
|
1917 |
if (n._in) {
|
deba@430
|
1918 |
n._in = false;
|
deba@430
|
1919 |
} else {
|
deba@430
|
1920 |
n._in = true;
|
deba@430
|
1921 |
_digraph->next(n);
|
deba@430
|
1922 |
}
|
deba@430
|
1923 |
}
|
deba@430
|
1924 |
|
deba@430
|
1925 |
void first(Arc& e) const {
|
deba@430
|
1926 |
e._item.setSecond();
|
deba@430
|
1927 |
_digraph->first(e._item.second());
|
deba@430
|
1928 |
if (e._item.second() == INVALID) {
|
deba@430
|
1929 |
e._item.setFirst();
|
deba@430
|
1930 |
_digraph->first(e._item.first());
|
deba@430
|
1931 |
}
|
deba@430
|
1932 |
}
|
deba@430
|
1933 |
|
deba@430
|
1934 |
void next(Arc& e) const {
|
deba@430
|
1935 |
if (e._item.secondState()) {
|
deba@430
|
1936 |
_digraph->next(e._item.second());
|
deba@430
|
1937 |
if (e._item.second() == INVALID) {
|
deba@430
|
1938 |
e._item.setFirst();
|
deba@430
|
1939 |
_digraph->first(e._item.first());
|
deba@430
|
1940 |
}
|
deba@430
|
1941 |
} else {
|
deba@430
|
1942 |
_digraph->next(e._item.first());
|
deba@430
|
1943 |
}
|
deba@430
|
1944 |
}
|
deba@430
|
1945 |
|
deba@430
|
1946 |
void firstOut(Arc& e, const Node& n) const {
|
deba@430
|
1947 |
if (n._in) {
|
deba@430
|
1948 |
e._item.setSecond(n);
|
deba@430
|
1949 |
} else {
|
deba@430
|
1950 |
e._item.setFirst();
|
deba@430
|
1951 |
_digraph->firstOut(e._item.first(), n);
|
deba@430
|
1952 |
}
|
deba@430
|
1953 |
}
|
deba@430
|
1954 |
|
deba@430
|
1955 |
void nextOut(Arc& e) const {
|
deba@430
|
1956 |
if (!e._item.firstState()) {
|
deba@430
|
1957 |
e._item.setFirst(INVALID);
|
deba@430
|
1958 |
} else {
|
deba@430
|
1959 |
_digraph->nextOut(e._item.first());
|
deba@430
|
1960 |
}
|
deba@430
|
1961 |
}
|
deba@430
|
1962 |
|
deba@430
|
1963 |
void firstIn(Arc& e, const Node& n) const {
|
deba@430
|
1964 |
if (!n._in) {
|
deba@430
|
1965 |
e._item.setSecond(n);
|
deba@430
|
1966 |
} else {
|
deba@430
|
1967 |
e._item.setFirst();
|
deba@430
|
1968 |
_digraph->firstIn(e._item.first(), n);
|
deba@430
|
1969 |
}
|
deba@430
|
1970 |
}
|
deba@430
|
1971 |
|
deba@430
|
1972 |
void nextIn(Arc& e) const {
|
deba@430
|
1973 |
if (!e._item.firstState()) {
|
deba@430
|
1974 |
e._item.setFirst(INVALID);
|
deba@430
|
1975 |
} else {
|
deba@430
|
1976 |
_digraph->nextIn(e._item.first());
|
deba@430
|
1977 |
}
|
deba@430
|
1978 |
}
|
deba@430
|
1979 |
|
deba@430
|
1980 |
Node source(const Arc& e) const {
|
deba@430
|
1981 |
if (e._item.firstState()) {
|
deba@430
|
1982 |
return Node(_digraph->source(e._item.first()), false);
|
deba@430
|
1983 |
} else {
|
deba@430
|
1984 |
return Node(e._item.second(), true);
|
deba@430
|
1985 |
}
|
deba@430
|
1986 |
}
|
deba@430
|
1987 |
|
deba@430
|
1988 |
Node target(const Arc& e) const {
|
deba@430
|
1989 |
if (e._item.firstState()) {
|
deba@430
|
1990 |
return Node(_digraph->target(e._item.first()), true);
|
deba@430
|
1991 |
} else {
|
deba@430
|
1992 |
return Node(e._item.second(), false);
|
deba@430
|
1993 |
}
|
deba@430
|
1994 |
}
|
deba@430
|
1995 |
|
deba@430
|
1996 |
int id(const Node& n) const {
|
deba@430
|
1997 |
return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
|
deba@430
|
1998 |
}
|
deba@430
|
1999 |
Node nodeFromId(int ix) const {
|
deba@430
|
2000 |
return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
|
deba@430
|
2001 |
}
|
deba@430
|
2002 |
int maxNodeId() const {
|
deba@430
|
2003 |
return 2 * _digraph->maxNodeId() + 1;
|
deba@430
|
2004 |
}
|
deba@430
|
2005 |
|
deba@430
|
2006 |
int id(const Arc& e) const {
|
deba@430
|
2007 |
if (e._item.firstState()) {
|
deba@430
|
2008 |
return _digraph->id(e._item.first()) << 1;
|
deba@430
|
2009 |
} else {
|
deba@430
|
2010 |
return (_digraph->id(e._item.second()) << 1) | 1;
|
deba@430
|
2011 |
}
|
deba@430
|
2012 |
}
|
deba@430
|
2013 |
Arc arcFromId(int ix) const {
|
deba@430
|
2014 |
if ((ix & 1) == 0) {
|
deba@430
|
2015 |
return Arc(_digraph->arcFromId(ix >> 1));
|
deba@430
|
2016 |
} else {
|
deba@430
|
2017 |
return Arc(_digraph->nodeFromId(ix >> 1));
|
deba@430
|
2018 |
}
|
deba@430
|
2019 |
}
|
deba@430
|
2020 |
int maxArcId() const {
|
deba@430
|
2021 |
return std::max(_digraph->maxNodeId() << 1,
|
deba@430
|
2022 |
(_digraph->maxArcId() << 1) | 1);
|
deba@430
|
2023 |
}
|
deba@430
|
2024 |
|
deba@430
|
2025 |
/// \brief Returns true when the node is in-node.
|
deba@430
|
2026 |
///
|
deba@430
|
2027 |
/// Returns true when the node is in-node.
|
deba@430
|
2028 |
static bool inNode(const Node& n) {
|
deba@430
|
2029 |
return n._in;
|
deba@430
|
2030 |
}
|
deba@430
|
2031 |
|
deba@430
|
2032 |
/// \brief Returns true when the node is out-node.
|
deba@430
|
2033 |
///
|
deba@430
|
2034 |
/// Returns true when the node is out-node.
|
deba@430
|
2035 |
static bool outNode(const Node& n) {
|
deba@430
|
2036 |
return !n._in;
|
deba@430
|
2037 |
}
|
deba@430
|
2038 |
|
deba@430
|
2039 |
/// \brief Returns true when the arc is arc in the original digraph.
|
deba@430
|
2040 |
///
|
deba@430
|
2041 |
/// Returns true when the arc is arc in the original digraph.
|
deba@430
|
2042 |
static bool origArc(const Arc& e) {
|
deba@430
|
2043 |
return e._item.firstState();
|
deba@430
|
2044 |
}
|
deba@430
|
2045 |
|
deba@430
|
2046 |
/// \brief Returns true when the arc binds an in-node and an out-node.
|
deba@430
|
2047 |
///
|
deba@430
|
2048 |
/// Returns true when the arc binds an in-node and an out-node.
|
deba@430
|
2049 |
static bool bindArc(const Arc& e) {
|
deba@430
|
2050 |
return e._item.secondState();
|
deba@430
|
2051 |
}
|
deba@430
|
2052 |
|
deba@430
|
2053 |
/// \brief Gives back the in-node created from the \c node.
|
deba@430
|
2054 |
///
|
deba@430
|
2055 |
/// Gives back the in-node created from the \c node.
|
deba@430
|
2056 |
static Node inNode(const DigraphNode& n) {
|
deba@430
|
2057 |
return Node(n, true);
|
deba@430
|
2058 |
}
|
deba@430
|
2059 |
|
deba@430
|
2060 |
/// \brief Gives back the out-node created from the \c node.
|
deba@430
|
2061 |
///
|
deba@430
|
2062 |
/// Gives back the out-node created from the \c node.
|
deba@430
|
2063 |
static Node outNode(const DigraphNode& n) {
|
deba@430
|
2064 |
return Node(n, false);
|
deba@430
|
2065 |
}
|
deba@430
|
2066 |
|
deba@430
|
2067 |
/// \brief Gives back the arc binds the two part of the node.
|
deba@430
|
2068 |
///
|
deba@430
|
2069 |
/// Gives back the arc binds the two part of the node.
|
deba@430
|
2070 |
static Arc arc(const DigraphNode& n) {
|
deba@430
|
2071 |
return Arc(n);
|
deba@430
|
2072 |
}
|
deba@430
|
2073 |
|
deba@430
|
2074 |
/// \brief Gives back the arc of the original arc.
|
deba@430
|
2075 |
///
|
deba@430
|
2076 |
/// Gives back the arc of the original arc.
|
deba@430
|
2077 |
static Arc arc(const DigraphArc& e) {
|
deba@430
|
2078 |
return Arc(e);
|
deba@430
|
2079 |
}
|
deba@430
|
2080 |
|
deba@430
|
2081 |
typedef True NodeNumTag;
|
deba@430
|
2082 |
|
deba@430
|
2083 |
int nodeNum() const {
|
deba@430
|
2084 |
return 2 * countNodes(*_digraph);
|
deba@430
|
2085 |
}
|
deba@430
|
2086 |
|
deba@430
|
2087 |
typedef True EdgeNumTag;
|
deba@430
|
2088 |
int arcNum() const {
|
deba@430
|
2089 |
return countArcs(*_digraph) + countNodes(*_digraph);
|
deba@430
|
2090 |
}
|
deba@430
|
2091 |
|
deba@430
|
2092 |
typedef True FindEdgeTag;
|
deba@430
|
2093 |
Arc findArc(const Node& u, const Node& v,
|
deba@430
|
2094 |
const Arc& prev = INVALID) const {
|
deba@430
|
2095 |
if (inNode(u)) {
|
deba@430
|
2096 |
if (outNode(v)) {
|
deba@430
|
2097 |
if (static_cast<const DigraphNode&>(u) ==
|
deba@430
|
2098 |
static_cast<const DigraphNode&>(v) && prev == INVALID) {
|
deba@430
|
2099 |
return Arc(u);
|
deba@430
|
2100 |
}
|
deba@430
|
2101 |
}
|
deba@430
|
2102 |
} else {
|
deba@430
|
2103 |
if (inNode(v)) {
|
deba@430
|
2104 |
return Arc(::lemon::findArc(*_digraph, u, v, prev));
|
deba@430
|
2105 |
}
|
deba@430
|
2106 |
}
|
deba@430
|
2107 |
return INVALID;
|
deba@430
|
2108 |
}
|
deba@430
|
2109 |
|
deba@430
|
2110 |
private:
|
deba@430
|
2111 |
|
deba@430
|
2112 |
template <typename _Value>
|
deba@430
|
2113 |
class NodeMapBase
|
deba@430
|
2114 |
: public MapTraits<typename Parent::template NodeMap<_Value> > {
|
deba@430
|
2115 |
typedef typename Parent::template NodeMap<_Value> NodeImpl;
|
deba@430
|
2116 |
public:
|
deba@430
|
2117 |
typedef Node Key;
|
deba@430
|
2118 |
typedef _Value Value;
|
deba@430
|
2119 |
|
deba@430
|
2120 |
NodeMapBase(const Adaptor& adaptor)
|
deba@430
|
2121 |
: _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
|
deba@430
|
2122 |
NodeMapBase(const Adaptor& adaptor, const Value& value)
|
deba@430
|
2123 |
: _in_map(*adaptor._digraph, value),
|
deba@430
|
2124 |
_out_map(*adaptor._digraph, value) {}
|
deba@430
|
2125 |
|
deba@430
|
2126 |
void set(const Node& key, const Value& val) {
|
deba@430
|
2127 |
if (Adaptor::inNode(key)) { _in_map.set(key, val); }
|
deba@430
|
2128 |
else {_out_map.set(key, val); }
|
deba@430
|
2129 |
}
|
deba@430
|
2130 |
|
deba@430
|
2131 |
typename MapTraits<NodeImpl>::ReturnValue
|
deba@430
|
2132 |
operator[](const Node& key) {
|
deba@430
|
2133 |
if (Adaptor::inNode(key)) { return _in_map[key]; }
|
deba@430
|
2134 |
else { return _out_map[key]; }
|
deba@430
|
2135 |
}
|
deba@430
|
2136 |
|
deba@430
|
2137 |
typename MapTraits<NodeImpl>::ConstReturnValue
|
deba@430
|
2138 |
operator[](const Node& key) const {
|
deba@430
|
2139 |
if (Adaptor::inNode(key)) { return _in_map[key]; }
|
deba@430
|
2140 |
else { return _out_map[key]; }
|
deba@430
|
2141 |
}
|
deba@430
|
2142 |
|
deba@430
|
2143 |
private:
|
deba@430
|
2144 |
NodeImpl _in_map, _out_map;
|
deba@430
|
2145 |
};
|
deba@430
|
2146 |
|
deba@430
|
2147 |
template <typename _Value>
|
deba@430
|
2148 |
class ArcMapBase
|
deba@430
|
2149 |
: public MapTraits<typename Parent::template ArcMap<_Value> > {
|
deba@430
|
2150 |
typedef typename Parent::template ArcMap<_Value> ArcImpl;
|
deba@430
|
2151 |
typedef typename Parent::template NodeMap<_Value> NodeImpl;
|
deba@430
|
2152 |
public:
|
deba@430
|
2153 |
typedef Arc Key;
|
deba@430
|
2154 |
typedef _Value Value;
|
deba@430
|
2155 |
|
deba@430
|
2156 |
ArcMapBase(const Adaptor& adaptor)
|
deba@430
|
2157 |
: _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
|
deba@430
|
2158 |
ArcMapBase(const Adaptor& adaptor, const Value& value)
|
deba@430
|
2159 |
: _arc_map(*adaptor._digraph, value),
|
deba@430
|
2160 |
_node_map(*adaptor._digraph, value) {}
|
deba@430
|
2161 |
|
deba@430
|
2162 |
void set(const Arc& key, const Value& val) {
|
deba@430
|
2163 |
if (Adaptor::origArc(key)) {
|
deba@430
|
2164 |
_arc_map.set(key._item.first(), val);
|
deba@430
|
2165 |
} else {
|
deba@430
|
2166 |
_node_map.set(key._item.second(), val);
|
deba@430
|
2167 |
}
|
deba@430
|
2168 |
}
|
deba@430
|
2169 |
|
deba@430
|
2170 |
typename MapTraits<ArcImpl>::ReturnValue
|
deba@430
|
2171 |
operator[](const Arc& key) {
|
deba@430
|
2172 |
if (Adaptor::origArc(key)) {
|
deba@430
|
2173 |
return _arc_map[key._item.first()];
|
deba@430
|
2174 |
} else {
|
deba@430
|
2175 |
return _node_map[key._item.second()];
|
deba@430
|
2176 |
}
|
deba@430
|
2177 |
}
|
deba@430
|
2178 |
|
deba@430
|
2179 |
typename MapTraits<ArcImpl>::ConstReturnValue
|
deba@430
|
2180 |
operator[](const Arc& key) const {
|
deba@430
|
2181 |
if (Adaptor::origArc(key)) {
|
deba@430
|
2182 |
return _arc_map[key._item.first()];
|
deba@430
|
2183 |
} else {
|
deba@430
|
2184 |
return _node_map[key._item.second()];
|
deba@430
|
2185 |
}
|
deba@430
|
2186 |
}
|
deba@430
|
2187 |
|
deba@430
|
2188 |
private:
|
deba@430
|
2189 |
ArcImpl _arc_map;
|
deba@430
|
2190 |
NodeImpl _node_map;
|
deba@430
|
2191 |
};
|
deba@430
|
2192 |
|
deba@430
|
2193 |
public:
|
deba@430
|
2194 |
|
deba@430
|
2195 |
template <typename _Value>
|
deba@430
|
2196 |
class NodeMap
|
deba@430
|
2197 |
: public SubMapExtender<Adaptor, NodeMapBase<_Value> >
|
deba@430
|
2198 |
{
|
deba@430
|
2199 |
public:
|
deba@430
|
2200 |
typedef _Value Value;
|
deba@430
|
2201 |
typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
|
deba@430
|
2202 |
|
deba@430
|
2203 |
NodeMap(const Adaptor& adaptor)
|
deba@430
|
2204 |
: Parent(adaptor) {}
|
deba@430
|
2205 |
|
deba@430
|
2206 |
NodeMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
2207 |
: Parent(adaptor, value) {}
|
deba@430
|
2208 |
|
deba@430
|
2209 |
private:
|
deba@430
|
2210 |
NodeMap& operator=(const NodeMap& cmap) {
|
deba@430
|
2211 |
return operator=<NodeMap>(cmap);
|
deba@430
|
2212 |
}
|
deba@430
|
2213 |
|
deba@430
|
2214 |
template <typename CMap>
|
deba@430
|
2215 |
NodeMap& operator=(const CMap& cmap) {
|
deba@430
|
2216 |
Parent::operator=(cmap);
|
deba@430
|
2217 |
return *this;
|
deba@430
|
2218 |
}
|
deba@430
|
2219 |
};
|
deba@430
|
2220 |
|
deba@430
|
2221 |
template <typename _Value>
|
deba@430
|
2222 |
class ArcMap
|
deba@430
|
2223 |
: public SubMapExtender<Adaptor, ArcMapBase<_Value> >
|
deba@430
|
2224 |
{
|
deba@430
|
2225 |
public:
|
deba@430
|
2226 |
typedef _Value Value;
|
deba@430
|
2227 |
typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
|
deba@430
|
2228 |
|
deba@430
|
2229 |
ArcMap(const Adaptor& adaptor)
|
deba@430
|
2230 |
: Parent(adaptor) {}
|
deba@430
|
2231 |
|
deba@430
|
2232 |
ArcMap(const Adaptor& adaptor, const Value& value)
|
deba@430
|
2233 |
: Parent(adaptor, value) {}
|
deba@430
|
2234 |
|
deba@430
|
2235 |
private:
|
deba@430
|
2236 |
ArcMap& operator=(const ArcMap& cmap) {
|
deba@430
|
2237 |
return operator=<ArcMap>(cmap);
|
deba@430
|
2238 |
}
|
deba@430
|
2239 |
|
deba@430
|
2240 |
template <typename CMap>
|
deba@430
|
2241 |
ArcMap& operator=(const CMap& cmap) {
|
deba@430
|
2242 |
Parent::operator=(cmap);
|
deba@430
|
2243 |
return *this;
|
deba@430
|
2244 |
}
|
deba@430
|
2245 |
};
|
deba@430
|
2246 |
|
deba@430
|
2247 |
protected:
|
deba@430
|
2248 |
|
deba@430
|
2249 |
SplitDigraphAdaptorBase() : _digraph(0) {}
|
deba@430
|
2250 |
|
deba@430
|
2251 |
Digraph* _digraph;
|
deba@430
|
2252 |
|
deba@430
|
2253 |
void setDigraph(Digraph& digraph) {
|
deba@430
|
2254 |
_digraph = &digraph;
|
deba@430
|
2255 |
}
|
deba@430
|
2256 |
|
deba@430
|
2257 |
};
|
deba@430
|
2258 |
|
deba@430
|
2259 |
/// \ingroup graph_adaptors
|
deba@430
|
2260 |
///
|
deba@430
|
2261 |
/// \brief Split digraph adaptor class
|
deba@430
|
2262 |
///
|
deba@430
|
2263 |
/// This is an digraph adaptor which splits all node into an in-node
|
deba@430
|
2264 |
/// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
|
deba@430
|
2265 |
/// node in the digraph with two node, \f$ u_{in} \f$ node and
|
deba@430
|
2266 |
/// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
|
deba@430
|
2267 |
/// original digraph the new target of the arc will be \f$ u_{in} \f$ and
|
deba@430
|
2268 |
/// similarly the source of the original \f$ (u, v) \f$ arc will be
|
deba@430
|
2269 |
/// \f$ u_{out} \f$. The adaptor will add for each node in the
|
deba@430
|
2270 |
/// original digraph an additional arc which will connect
|
deba@430
|
2271 |
/// \f$ (u_{in}, u_{out}) \f$.
|
deba@430
|
2272 |
///
|
deba@430
|
2273 |
/// The aim of this class is to run algorithm with node costs if the
|
deba@430
|
2274 |
/// algorithm can use directly just arc costs. In this case we should use
|
deba@430
|
2275 |
/// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
|
deba@430
|
2276 |
/// bind arc in the adapted digraph.
|
deba@430
|
2277 |
///
|
deba@430
|
2278 |
/// By example a maximum flow algoritm can compute how many arc
|
deba@430
|
2279 |
/// disjoint paths are in the digraph. But we would like to know how
|
deba@430
|
2280 |
/// many node disjoint paths are in the digraph. First we have to
|
deba@430
|
2281 |
/// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
|
deba@430
|
2282 |
/// algorithm on the adapted digraph. The bottleneck of the flow will
|
deba@430
|
2283 |
/// be the bind arcs which bounds the flow with the count of the
|
deba@430
|
2284 |
/// node disjoint paths.
|
deba@430
|
2285 |
///
|
deba@430
|
2286 |
///\code
|
deba@430
|
2287 |
///
|
deba@430
|
2288 |
/// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
|
deba@430
|
2289 |
///
|
deba@430
|
2290 |
/// SDigraph sdigraph(digraph);
|
deba@430
|
2291 |
///
|
deba@430
|
2292 |
/// typedef ConstMap<SDigraph::Arc, int> SCapacity;
|
deba@430
|
2293 |
/// SCapacity scapacity(1);
|
deba@430
|
2294 |
///
|
deba@430
|
2295 |
/// SDigraph::ArcMap<int> sflow(sdigraph);
|
deba@430
|
2296 |
///
|
deba@430
|
2297 |
/// Preflow<SDigraph, SCapacity>
|
deba@430
|
2298 |
/// spreflow(sdigraph, scapacity,
|
deba@430
|
2299 |
/// SDigraph::outNode(source), SDigraph::inNode(target));
|
deba@430
|
2300 |
///
|
deba@430
|
2301 |
/// spreflow.run();
|
deba@430
|
2302 |
///
|
deba@430
|
2303 |
///\endcode
|
deba@430
|
2304 |
///
|
deba@430
|
2305 |
/// The result of the mamixum flow on the original digraph
|
deba@430
|
2306 |
/// shows the next figure:
|
deba@430
|
2307 |
///
|
deba@430
|
2308 |
/// \image html arc_disjoint.png
|
deba@430
|
2309 |
/// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
|
deba@430
|
2310 |
///
|
deba@430
|
2311 |
/// And the maximum flow on the adapted digraph:
|
deba@430
|
2312 |
///
|
deba@430
|
2313 |
/// \image html node_disjoint.png
|
deba@430
|
2314 |
/// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
|
deba@430
|
2315 |
///
|
deba@430
|
2316 |
/// The second solution contains just 3 disjoint paths while the first 4.
|
deba@430
|
2317 |
/// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
|
deba@430
|
2318 |
///
|
deba@430
|
2319 |
/// This digraph adaptor is fully conform to the
|
deba@430
|
2320 |
/// \ref concepts::Digraph "Digraph" concept and
|
deba@430
|
2321 |
/// contains some additional member functions and types. The
|
deba@430
|
2322 |
/// documentation of some member functions may be found just in the
|
deba@430
|
2323 |
/// SplitDigraphAdaptorBase class.
|
deba@430
|
2324 |
///
|
deba@430
|
2325 |
/// \sa SplitDigraphAdaptorBase
|
deba@430
|
2326 |
template <typename _Digraph>
|
deba@430
|
2327 |
class SplitDigraphAdaptor
|
deba@430
|
2328 |
: public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
|
deba@430
|
2329 |
public:
|
deba@430
|
2330 |
typedef _Digraph Digraph;
|
deba@430
|
2331 |
typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
|
deba@430
|
2332 |
|
deba@430
|
2333 |
typedef typename Parent::Node Node;
|
deba@430
|
2334 |
typedef typename Parent::Arc Arc;
|
deba@430
|
2335 |
|
deba@430
|
2336 |
/// \brief Constructor of the adaptor.
|
deba@430
|
2337 |
///
|
deba@430
|
2338 |
/// Constructor of the adaptor.
|
deba@430
|
2339 |
SplitDigraphAdaptor(Digraph& g) {
|
deba@430
|
2340 |
Parent::setDigraph(g);
|
deba@430
|
2341 |
}
|
deba@430
|
2342 |
|
deba@430
|
2343 |
/// \brief NodeMap combined from two original NodeMap
|
deba@430
|
2344 |
///
|
deba@430
|
2345 |
/// This class adapt two of the original digraph NodeMap to
|
deba@430
|
2346 |
/// get a node map on the adapted digraph.
|
deba@430
|
2347 |
template <typename InNodeMap, typename OutNodeMap>
|
deba@430
|
2348 |
class CombinedNodeMap {
|
deba@430
|
2349 |
public:
|
deba@430
|
2350 |
|
deba@430
|
2351 |
typedef Node Key;
|
deba@430
|
2352 |
typedef typename InNodeMap::Value Value;
|
deba@430
|
2353 |
|
deba@430
|
2354 |
/// \brief Constructor
|
deba@430
|
2355 |
///
|
deba@430
|
2356 |
/// Constructor.
|
deba@430
|
2357 |
CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
|
deba@430
|
2358 |
: _in_map(in_map), _out_map(out_map) {}
|
deba@430
|
2359 |
|
deba@430
|
2360 |
/// \brief The subscript operator.
|
deba@430
|
2361 |
///
|
deba@430
|
2362 |
/// The subscript operator.
|
deba@430
|
2363 |
Value& operator[](const Key& key) {
|
deba@430
|
2364 |
if (Parent::inNode(key)) {
|
deba@430
|
2365 |
return _in_map[key];
|
deba@430
|
2366 |
} else {
|
deba@430
|
2367 |
return _out_map[key];
|
deba@430
|
2368 |
}
|
deba@430
|
2369 |
}
|
deba@430
|
2370 |
|
deba@430
|
2371 |
/// \brief The const subscript operator.
|
deba@430
|
2372 |
///
|
deba@430
|
2373 |
/// The const subscript operator.
|
deba@430
|
2374 |
Value operator[](const Key& key) const {
|
deba@430
|
2375 |
if (Parent::inNode(key)) {
|
deba@430
|
2376 |
return _in_map[key];
|
deba@430
|
2377 |
} else {
|
deba@430
|
2378 |
return _out_map[key];
|
deba@430
|
2379 |
}
|
deba@430
|
2380 |
}
|
deba@430
|
2381 |
|
deba@430
|
2382 |
/// \brief The setter function of the map.
|
deba@430
|
2383 |
///
|
deba@430
|
2384 |
/// The setter function of the map.
|
deba@430
|
2385 |
void set(const Key& key, const Value& value) {
|
deba@430
|
2386 |
if (Parent::inNode(key)) {
|
deba@430
|
2387 |
_in_map.set(key, value);
|
deba@430
|
2388 |
} else {
|
deba@430
|
2389 |
_out_map.set(key, value);
|
deba@430
|
2390 |
}
|
deba@430
|
2391 |
}
|
deba@430
|
2392 |
|
deba@430
|
2393 |
private:
|
deba@430
|
2394 |
|
deba@430
|
2395 |
InNodeMap& _in_map;
|
deba@430
|
2396 |
OutNodeMap& _out_map;
|
deba@430
|
2397 |
|
deba@430
|
2398 |
};
|
deba@430
|
2399 |
|
deba@430
|
2400 |
|
deba@430
|
2401 |
/// \brief Just gives back a combined node map.
|
deba@430
|
2402 |
///
|
deba@430
|
2403 |
/// Just gives back a combined node map.
|
deba@430
|
2404 |
template <typename InNodeMap, typename OutNodeMap>
|
deba@430
|
2405 |
static CombinedNodeMap<InNodeMap, OutNodeMap>
|
deba@430
|
2406 |
combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
|
deba@430
|
2407 |
return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
|
deba@430
|
2408 |
}
|
deba@430
|
2409 |
|
deba@430
|
2410 |
template <typename InNodeMap, typename OutNodeMap>
|
deba@430
|
2411 |
static CombinedNodeMap<const InNodeMap, OutNodeMap>
|
deba@430
|
2412 |
combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
|
deba@430
|
2413 |
return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
|
deba@430
|
2414 |
}
|
deba@430
|
2415 |
|
deba@430
|
2416 |
template <typename InNodeMap, typename OutNodeMap>
|
deba@430
|
2417 |
static CombinedNodeMap<InNodeMap, const OutNodeMap>
|
deba@430
|
2418 |
combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
|
deba@430
|
2419 |
return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
|
deba@430
|
2420 |
}
|
deba@430
|
2421 |
|
deba@430
|
2422 |
template <typename InNodeMap, typename OutNodeMap>
|
deba@430
|
2423 |
static CombinedNodeMap<const InNodeMap, const OutNodeMap>
|
deba@430
|
2424 |
combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
|
deba@430
|
2425 |
return CombinedNodeMap<const InNodeMap,
|
deba@430
|
2426 |
const OutNodeMap>(in_map, out_map);
|
deba@430
|
2427 |
}
|
deba@430
|
2428 |
|
deba@430
|
2429 |
/// \brief ArcMap combined from an original ArcMap and NodeMap
|
deba@430
|
2430 |
///
|
deba@430
|
2431 |
/// This class adapt an original digraph ArcMap and NodeMap to
|
deba@430
|
2432 |
/// get an arc map on the adapted digraph.
|
deba@430
|
2433 |
template <typename DigraphArcMap, typename DigraphNodeMap>
|
deba@430
|
2434 |
class CombinedArcMap {
|
deba@430
|
2435 |
public:
|
deba@430
|
2436 |
|
deba@430
|
2437 |
typedef Arc Key;
|
deba@430
|
2438 |
typedef typename DigraphArcMap::Value Value;
|
deba@430
|
2439 |
|
deba@430
|
2440 |
/// \brief Constructor
|
deba@430
|
2441 |
///
|
deba@430
|
2442 |
/// Constructor.
|
deba@430
|
2443 |
CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
|
deba@430
|
2444 |
: _arc_map(arc_map), _node_map(node_map) {}
|
deba@430
|
2445 |
|
deba@430
|
2446 |
/// \brief The subscript operator.
|
deba@430
|
2447 |
///
|
deba@430
|
2448 |
/// The subscript operator.
|
deba@430
|
2449 |
void set(const Arc& arc, const Value& val) {
|
deba@430
|
2450 |
if (Parent::origArc(arc)) {
|
deba@430
|
2451 |
_arc_map.set(arc, val);
|
deba@430
|
2452 |
} else {
|
deba@430
|
2453 |
_node_map.set(arc, val);
|
deba@430
|
2454 |
}
|
deba@430
|
2455 |
}
|
deba@430
|
2456 |
|
deba@430
|
2457 |
/// \brief The const subscript operator.
|
deba@430
|
2458 |
///
|
deba@430
|
2459 |
/// The const subscript operator.
|
deba@430
|
2460 |
Value operator[](const Key& arc) const {
|
deba@430
|
2461 |
if (Parent::origArc(arc)) {
|
deba@430
|
2462 |
return _arc_map[arc];
|
deba@430
|
2463 |
} else {
|
deba@430
|
2464 |
return _node_map[arc];
|
deba@430
|
2465 |
}
|
deba@430
|
2466 |
}
|
deba@430
|
2467 |
|
deba@430
|
2468 |
/// \brief The const subscript operator.
|
deba@430
|
2469 |
///
|
deba@430
|
2470 |
/// The const subscript operator.
|
deba@430
|
2471 |
Value& operator[](const Key& arc) {
|
deba@430
|
2472 |
if (Parent::origArc(arc)) {
|
deba@430
|
2473 |
return _arc_map[arc];
|
deba@430
|
2474 |
} else {
|
deba@430
|
2475 |
return _node_map[arc];
|
deba@430
|
2476 |
}
|
deba@430
|
2477 |
}
|
deba@430
|
2478 |
|
deba@430
|
2479 |
private:
|
deba@430
|
2480 |
DigraphArcMap& _arc_map;
|
deba@430
|
2481 |
DigraphNodeMap& _node_map;
|
deba@430
|
2482 |
};
|
deba@430
|
2483 |
|
deba@430
|
2484 |
/// \brief Just gives back a combined arc map.
|
deba@430
|
2485 |
///
|
deba@430
|
2486 |
/// Just gives back a combined arc map.
|
deba@430
|
2487 |
template <typename DigraphArcMap, typename DigraphNodeMap>
|
deba@430
|
2488 |
static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
|
deba@430
|
2489 |
combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
|
deba@430
|
2490 |
return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
|
deba@430
|
2491 |
}
|
deba@430
|
2492 |
|
deba@430
|
2493 |
template <typename DigraphArcMap, typename DigraphNodeMap>
|
deba@430
|
2494 |
static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
|
deba@430
|
2495 |
combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
|
deba@430
|
2496 |
return CombinedArcMap<const DigraphArcMap,
|
deba@430
|
2497 |
DigraphNodeMap>(arc_map, node_map);
|
deba@430
|
2498 |
}
|
deba@430
|
2499 |
|
deba@430
|
2500 |
template <typename DigraphArcMap, typename DigraphNodeMap>
|
deba@430
|
2501 |
static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
|
deba@430
|
2502 |
combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
|
deba@430
|
2503 |
return CombinedArcMap<DigraphArcMap,
|
deba@430
|
2504 |
const DigraphNodeMap>(arc_map, node_map);
|
deba@430
|
2505 |
}
|
deba@430
|
2506 |
|
deba@430
|
2507 |
template <typename DigraphArcMap, typename DigraphNodeMap>
|
deba@430
|
2508 |
static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
|
deba@430
|
2509 |
combinedArcMap(const DigraphArcMap& arc_map,
|
deba@430
|
2510 |
const DigraphNodeMap& node_map) {
|
deba@430
|
2511 |
return CombinedArcMap<const DigraphArcMap,
|
deba@430
|
2512 |
const DigraphNodeMap>(arc_map, node_map);
|
deba@430
|
2513 |
}
|
deba@430
|
2514 |
|
deba@430
|
2515 |
};
|
deba@430
|
2516 |
|
deba@430
|
2517 |
/// \brief Just gives back a split digraph adaptor
|
deba@430
|
2518 |
///
|
deba@430
|
2519 |
/// Just gives back a split digraph adaptor
|
deba@430
|
2520 |
template<typename Digraph>
|
deba@430
|
2521 |
SplitDigraphAdaptor<Digraph>
|
deba@430
|
2522 |
splitDigraphAdaptor(const Digraph& digraph) {
|
deba@430
|
2523 |
return SplitDigraphAdaptor<Digraph>(digraph);
|
deba@430
|
2524 |
}
|
deba@430
|
2525 |
|
deba@430
|
2526 |
|
deba@430
|
2527 |
} //namespace lemon
|
deba@430
|
2528 |
|
deba@430
|
2529 |
#endif //LEMON_DIGRAPH_ADAPTOR_H
|
deba@430
|
2530 |
|