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