Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2010
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_ADAPTORS_H
20 : : #define LEMON_ADAPTORS_H
21 : :
22 : : /// \ingroup graph_adaptors
23 : : /// \file
24 : : /// \brief Adaptor classes for digraphs and graphs
25 : : ///
26 : : /// This file contains several useful adaptors for digraphs and graphs.
27 : :
28 : : #include <lemon/core.h>
29 : : #include <lemon/maps.h>
30 : : #include <lemon/bits/variant.h>
31 : :
32 : : #include <lemon/bits/graph_adaptor_extender.h>
33 : : #include <lemon/bits/map_extender.h>
34 : : #include <lemon/tolerance.h>
35 : :
36 : : #include <algorithm>
37 : :
38 : : namespace lemon {
39 : :
40 : : #ifdef _MSC_VER
41 : : #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
42 : : #else
43 : : #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
44 : : #endif
45 : :
46 : : template<typename DGR>
47 : : class DigraphAdaptorBase {
48 : : public:
49 : : typedef DGR Digraph;
50 : : typedef DigraphAdaptorBase Adaptor;
51 : :
52 : : protected:
53 : : DGR* _digraph;
54 : 80 : DigraphAdaptorBase() : _digraph(0) { }
55 : 80 : void initialize(DGR& digraph) { _digraph = &digraph; }
56 : :
57 : : public:
58 : : DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
59 : :
60 : : typedef typename DGR::Node Node;
61 : : typedef typename DGR::Arc Arc;
62 : :
63 : 1004 : void first(Node& i) const { _digraph->first(i); }
64 : : void first(Arc& i) const { _digraph->first(i); }
65 : 2146 : void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
66 : : void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
67 : :
68 : 5056 : void next(Node& i) const { _digraph->next(i); }
69 : : void next(Arc& i) const { _digraph->next(i); }
70 : 2060 : void nextIn(Arc& i) const { _digraph->nextIn(i); }
71 : : void nextOut(Arc& i) const { _digraph->nextOut(i); }
72 : :
73 : 2060 : Node source(const Arc& a) const { return _digraph->source(a); }
74 : : Node target(const Arc& a) const { return _digraph->target(a); }
75 : :
76 : : typedef NodeNumTagIndicator<DGR> NodeNumTag;
77 : : int nodeNum() const { return _digraph->nodeNum(); }
78 : :
79 : : typedef ArcNumTagIndicator<DGR> ArcNumTag;
80 : : int arcNum() const { return _digraph->arcNum(); }
81 : :
82 : : typedef FindArcTagIndicator<DGR> FindArcTag;
83 : : Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
84 : : return _digraph->findArc(u, v, prev);
85 : : }
86 : :
87 : : Node addNode() { return _digraph->addNode(); }
88 : : Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
89 : :
90 : : void erase(const Node& n) { _digraph->erase(n); }
91 : : void erase(const Arc& a) { _digraph->erase(a); }
92 : :
93 : : void clear() { _digraph->clear(); }
94 : :
95 : : int id(const Node& n) const { return _digraph->id(n); }
96 : : int id(const Arc& a) const { return _digraph->id(a); }
97 : :
98 : : Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
99 : : Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
100 : :
101 : : int maxNodeId() const { return _digraph->maxNodeId(); }
102 : : int maxArcId() const { return _digraph->maxArcId(); }
103 : :
104 : : typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
105 : : NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
106 : :
107 : : typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
108 : : ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
109 : :
110 : : template <typename V>
111 [ - + ][ - + ]: 3012 : class NodeMap : public DGR::template NodeMap<V> {
[ - + ]
112 : : typedef typename DGR::template NodeMap<V> Parent;
113 : :
114 : : public:
115 : 753 : explicit NodeMap(const Adaptor& adaptor)
116 : 753 : : Parent(*adaptor._digraph) {}
117 : : NodeMap(const Adaptor& adaptor, const V& value)
118 : : : Parent(*adaptor._digraph, value) { }
119 : :
120 : : private:
121 : : NodeMap& operator=(const NodeMap& cmap) {
122 : : return operator=<NodeMap>(cmap);
123 : : }
124 : :
125 : : template <typename CMap>
126 : : NodeMap& operator=(const CMap& cmap) {
127 : : Parent::operator=(cmap);
128 : : return *this;
129 : : }
130 : :
131 : : };
132 : :
133 : : template <typename V>
134 : : class ArcMap : public DGR::template ArcMap<V> {
135 : : typedef typename DGR::template ArcMap<V> Parent;
136 : :
137 : : public:
138 : : explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
139 : : : Parent(*adaptor._digraph) {}
140 : : ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
141 : : : Parent(*adaptor._digraph, value) {}
142 : :
143 : : private:
144 : : ArcMap& operator=(const ArcMap& cmap) {
145 : : return operator=<ArcMap>(cmap);
146 : : }
147 : :
148 : : template <typename CMap>
149 : : ArcMap& operator=(const CMap& cmap) {
150 : : Parent::operator=(cmap);
151 : : return *this;
152 : : }
153 : :
154 : : };
155 : :
156 : : };
157 : :
158 : : template<typename GR>
159 : : class GraphAdaptorBase {
160 : : public:
161 : : typedef GR Graph;
162 : :
163 : : protected:
164 : : GR* _graph;
165 : :
166 : : GraphAdaptorBase() : _graph(0) {}
167 : :
168 : : void initialize(GR& graph) { _graph = &graph; }
169 : :
170 : : public:
171 : : GraphAdaptorBase(GR& graph) : _graph(&graph) {}
172 : :
173 : : typedef typename GR::Node Node;
174 : : typedef typename GR::Arc Arc;
175 : : typedef typename GR::Edge Edge;
176 : :
177 : : void first(Node& i) const { _graph->first(i); }
178 : : void first(Arc& i) const { _graph->first(i); }
179 : : void first(Edge& i) const { _graph->first(i); }
180 : : void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
181 : : void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
182 : : void firstInc(Edge &i, bool &d, const Node &n) const {
183 : : _graph->firstInc(i, d, n);
184 : : }
185 : :
186 : : void next(Node& i) const { _graph->next(i); }
187 : : void next(Arc& i) const { _graph->next(i); }
188 : : void next(Edge& i) const { _graph->next(i); }
189 : : void nextIn(Arc& i) const { _graph->nextIn(i); }
190 : : void nextOut(Arc& i) const { _graph->nextOut(i); }
191 : : void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
192 : :
193 : : Node u(const Edge& e) const { return _graph->u(e); }
194 : : Node v(const Edge& e) const { return _graph->v(e); }
195 : :
196 : : Node source(const Arc& a) const { return _graph->source(a); }
197 : : Node target(const Arc& a) const { return _graph->target(a); }
198 : :
199 : : typedef NodeNumTagIndicator<Graph> NodeNumTag;
200 : : int nodeNum() const { return _graph->nodeNum(); }
201 : :
202 : : typedef ArcNumTagIndicator<Graph> ArcNumTag;
203 : : int arcNum() const { return _graph->arcNum(); }
204 : :
205 : : typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
206 : : int edgeNum() const { return _graph->edgeNum(); }
207 : :
208 : : typedef FindArcTagIndicator<Graph> FindArcTag;
209 : : Arc findArc(const Node& u, const Node& v,
210 : : const Arc& prev = INVALID) const {
211 : : return _graph->findArc(u, v, prev);
212 : : }
213 : :
214 : : typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
215 : : Edge findEdge(const Node& u, const Node& v,
216 : : const Edge& prev = INVALID) const {
217 : : return _graph->findEdge(u, v, prev);
218 : : }
219 : :
220 : : Node addNode() { return _graph->addNode(); }
221 : : Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
222 : :
223 : : void erase(const Node& i) { _graph->erase(i); }
224 : : void erase(const Edge& i) { _graph->erase(i); }
225 : :
226 : : void clear() { _graph->clear(); }
227 : :
228 : : bool direction(const Arc& a) const { return _graph->direction(a); }
229 : : Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
230 : :
231 : : int id(const Node& v) const { return _graph->id(v); }
232 : : int id(const Arc& a) const { return _graph->id(a); }
233 : : int id(const Edge& e) const { return _graph->id(e); }
234 : :
235 : : Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
236 : : Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
237 : : Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
238 : :
239 : : int maxNodeId() const { return _graph->maxNodeId(); }
240 : : int maxArcId() const { return _graph->maxArcId(); }
241 : : int maxEdgeId() const { return _graph->maxEdgeId(); }
242 : :
243 : : typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
244 : : NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
245 : :
246 : : typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
247 : : ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
248 : :
249 : : typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
250 : : EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
251 : :
252 : : template <typename V>
253 : : class NodeMap : public GR::template NodeMap<V> {
254 : : typedef typename GR::template NodeMap<V> Parent;
255 : :
256 : : public:
257 : : explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
258 : : : Parent(*adapter._graph) {}
259 : : NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
260 : : : Parent(*adapter._graph, value) {}
261 : :
262 : : private:
263 : : NodeMap& operator=(const NodeMap& cmap) {
264 : : return operator=<NodeMap>(cmap);
265 : : }
266 : :
267 : : template <typename CMap>
268 : : NodeMap& operator=(const CMap& cmap) {
269 : : Parent::operator=(cmap);
270 : : return *this;
271 : : }
272 : :
273 : : };
274 : :
275 : : template <typename V>
276 : : class ArcMap : public GR::template ArcMap<V> {
277 : : typedef typename GR::template ArcMap<V> Parent;
278 : :
279 : : public:
280 : : explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
281 : : : Parent(*adapter._graph) {}
282 : : ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
283 : : : Parent(*adapter._graph, value) {}
284 : :
285 : : private:
286 : : ArcMap& operator=(const ArcMap& cmap) {
287 : : return operator=<ArcMap>(cmap);
288 : : }
289 : :
290 : : template <typename CMap>
291 : : ArcMap& operator=(const CMap& cmap) {
292 : : Parent::operator=(cmap);
293 : : return *this;
294 : : }
295 : : };
296 : :
297 : : template <typename V>
298 : : class EdgeMap : public GR::template EdgeMap<V> {
299 : : typedef typename GR::template EdgeMap<V> Parent;
300 : :
301 : : public:
302 : : explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
303 : : : Parent(*adapter._graph) {}
304 : : EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
305 : : : Parent(*adapter._graph, value) {}
306 : :
307 : : private:
308 : : EdgeMap& operator=(const EdgeMap& cmap) {
309 : : return operator=<EdgeMap>(cmap);
310 : : }
311 : :
312 : : template <typename CMap>
313 : : EdgeMap& operator=(const CMap& cmap) {
314 : : Parent::operator=(cmap);
315 : : return *this;
316 : : }
317 : : };
318 : :
319 : : };
320 : :
321 : : template <typename DGR>
322 : : class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
323 : : typedef DigraphAdaptorBase<DGR> Parent;
324 : : public:
325 : : typedef DGR Digraph;
326 : : protected:
327 : 160 : ReverseDigraphBase() : Parent() { }
328 : : public:
329 : : typedef typename Parent::Node Node;
330 : : typedef typename Parent::Arc Arc;
331 : :
332 : : void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
333 : 2146 : void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
334 : :
335 : : void nextIn(Arc& a) const { Parent::nextOut(a); }
336 : 2060 : void nextOut(Arc& a) const { Parent::nextIn(a); }
337 : :
338 : : Node source(const Arc& a) const { return Parent::target(a); }
339 : 2060 : Node target(const Arc& a) const { return Parent::source(a); }
340 : :
341 : : Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
342 : :
343 : : typedef FindArcTagIndicator<DGR> FindArcTag;
344 : : Arc findArc(const Node& u, const Node& v,
345 : : const Arc& prev = INVALID) const {
346 : : return Parent::findArc(v, u, prev);
347 : : }
348 : :
349 : : };
350 : :
351 : : /// \ingroup graph_adaptors
352 : : ///
353 : : /// \brief Adaptor class for reversing the orientation of the arcs in
354 : : /// a digraph.
355 : : ///
356 : : /// ReverseDigraph can be used for reversing the arcs in a digraph.
357 : : /// It conforms to the \ref concepts::Digraph "Digraph" concept.
358 : : ///
359 : : /// The adapted digraph can also be modified through this adaptor
360 : : /// by adding or removing nodes or arcs, unless the \c GR template
361 : : /// parameter is set to be \c const.
362 : : ///
363 : : /// This class provides item counting in the same time as the adapted
364 : : /// digraph structure.
365 : : ///
366 : : /// \tparam DGR The type of the adapted digraph.
367 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept.
368 : : /// It can also be specified to be \c const.
369 : : ///
370 : : /// \note The \c Node and \c Arc types of this adaptor and the adapted
371 : : /// digraph are convertible to each other.
372 : : template<typename DGR>
373 : : #ifdef DOXYGEN
374 : : class ReverseDigraph {
375 : : #else
376 : : class ReverseDigraph :
377 : : public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
378 : : #endif
379 : : typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
380 : : public:
381 : : /// The type of the adapted digraph.
382 : : typedef DGR Digraph;
383 : : protected:
384 : : ReverseDigraph() { }
385 : : public:
386 : :
387 : : /// \brief Constructor
388 : : ///
389 : : /// Creates a reverse digraph adaptor for the given digraph.
390 : 160 : explicit ReverseDigraph(DGR& digraph) {
391 : 80 : Parent::initialize(digraph);
392 : 80 : }
393 : : };
394 : :
395 : : /// \brief Returns a read-only ReverseDigraph adaptor
396 : : ///
397 : : /// This function just returns a read-only \ref ReverseDigraph adaptor.
398 : : /// \ingroup graph_adaptors
399 : : /// \relates ReverseDigraph
400 : : template<typename DGR>
401 : : ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
402 : : return ReverseDigraph<const DGR>(digraph);
403 : : }
404 : :
405 : :
406 : : template <typename DGR, typename NF, typename AF, bool ch = true>
407 : : class SubDigraphBase : public DigraphAdaptorBase<DGR> {
408 : : typedef DigraphAdaptorBase<DGR> Parent;
409 : : public:
410 : : typedef DGR Digraph;
411 : : typedef NF NodeFilterMap;
412 : : typedef AF ArcFilterMap;
413 : :
414 : : typedef SubDigraphBase Adaptor;
415 : : protected:
416 : : NF* _node_filter;
417 : : AF* _arc_filter;
418 : : SubDigraphBase()
419 : : : Parent(), _node_filter(0), _arc_filter(0) { }
420 : :
421 : : void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
422 : : Parent::initialize(digraph);
423 : : _node_filter = &node_filter;
424 : : _arc_filter = &arc_filter;
425 : : }
426 : :
427 : : public:
428 : :
429 : : typedef typename Parent::Node Node;
430 : : typedef typename Parent::Arc Arc;
431 : :
432 : : void first(Node& i) const {
433 : : Parent::first(i);
434 : : while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
435 : : }
436 : :
437 : : void first(Arc& i) const {
438 : : Parent::first(i);
439 : : while (i != INVALID && (!(*_arc_filter)[i]
440 : : || !(*_node_filter)[Parent::source(i)]
441 : : || !(*_node_filter)[Parent::target(i)]))
442 : : Parent::next(i);
443 : : }
444 : :
445 : : void firstIn(Arc& i, const Node& n) const {
446 : : Parent::firstIn(i, n);
447 : : while (i != INVALID && (!(*_arc_filter)[i]
448 : : || !(*_node_filter)[Parent::source(i)]))
449 : : Parent::nextIn(i);
450 : : }
451 : :
452 : : void firstOut(Arc& i, const Node& n) const {
453 : : Parent::firstOut(i, n);
454 : : while (i != INVALID && (!(*_arc_filter)[i]
455 : : || !(*_node_filter)[Parent::target(i)]))
456 : : Parent::nextOut(i);
457 : : }
458 : :
459 : : void next(Node& i) const {
460 : : Parent::next(i);
461 : : while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
462 : : }
463 : :
464 : : void next(Arc& i) const {
465 : : Parent::next(i);
466 : : while (i != INVALID && (!(*_arc_filter)[i]
467 : : || !(*_node_filter)[Parent::source(i)]
468 : : || !(*_node_filter)[Parent::target(i)]))
469 : : Parent::next(i);
470 : : }
471 : :
472 : : void nextIn(Arc& i) const {
473 : : Parent::nextIn(i);
474 : : while (i != INVALID && (!(*_arc_filter)[i]
475 : : || !(*_node_filter)[Parent::source(i)]))
476 : : Parent::nextIn(i);
477 : : }
478 : :
479 : : void nextOut(Arc& i) const {
480 : : Parent::nextOut(i);
481 : : while (i != INVALID && (!(*_arc_filter)[i]
482 : : || !(*_node_filter)[Parent::target(i)]))
483 : : Parent::nextOut(i);
484 : : }
485 : :
486 : : void status(const Node& n, bool v) const { _node_filter->set(n, v); }
487 : : void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
488 : :
489 : : bool status(const Node& n) const { return (*_node_filter)[n]; }
490 : : bool status(const Arc& a) const { return (*_arc_filter)[a]; }
491 : :
492 : : typedef False NodeNumTag;
493 : : typedef False ArcNumTag;
494 : :
495 : : typedef FindArcTagIndicator<DGR> FindArcTag;
496 : : Arc findArc(const Node& source, const Node& target,
497 : : const Arc& prev = INVALID) const {
498 : : if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
499 : : return INVALID;
500 : : }
501 : : Arc arc = Parent::findArc(source, target, prev);
502 : : while (arc != INVALID && !(*_arc_filter)[arc]) {
503 : : arc = Parent::findArc(source, target, arc);
504 : : }
505 : : return arc;
506 : : }
507 : :
508 : : public:
509 : :
510 : : template <typename V>
511 : : class NodeMap
512 : : : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
513 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
514 : : typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
515 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
516 : :
517 : : public:
518 : : typedef V Value;
519 : :
520 : : NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
521 : : : Parent(adaptor) {}
522 : : NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
523 : : : Parent(adaptor, value) {}
524 : :
525 : : private:
526 : : NodeMap& operator=(const NodeMap& cmap) {
527 : : return operator=<NodeMap>(cmap);
528 : : }
529 : :
530 : : template <typename CMap>
531 : : NodeMap& operator=(const CMap& cmap) {
532 : : Parent::operator=(cmap);
533 : : return *this;
534 : : }
535 : : };
536 : :
537 : : template <typename V>
538 : : class ArcMap
539 : : : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
540 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
541 : : typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
542 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
543 : :
544 : : public:
545 : : typedef V Value;
546 : :
547 : : ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
548 : : : Parent(adaptor) {}
549 : : ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
550 : : : Parent(adaptor, value) {}
551 : :
552 : : private:
553 : : ArcMap& operator=(const ArcMap& cmap) {
554 : : return operator=<ArcMap>(cmap);
555 : : }
556 : :
557 : : template <typename CMap>
558 : : ArcMap& operator=(const CMap& cmap) {
559 : : Parent::operator=(cmap);
560 : : return *this;
561 : : }
562 : : };
563 : :
564 : : };
565 : :
566 : : template <typename DGR, typename NF, typename AF>
567 : : class SubDigraphBase<DGR, NF, AF, false>
568 : : : public DigraphAdaptorBase<DGR> {
569 : : typedef DigraphAdaptorBase<DGR> Parent;
570 : : public:
571 : : typedef DGR Digraph;
572 : : typedef NF NodeFilterMap;
573 : : typedef AF ArcFilterMap;
574 : :
575 : : typedef SubDigraphBase Adaptor;
576 : : protected:
577 : : NF* _node_filter;
578 : : AF* _arc_filter;
579 : : SubDigraphBase()
580 : : : Parent(), _node_filter(0), _arc_filter(0) { }
581 : :
582 : : void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
583 : : Parent::initialize(digraph);
584 : : _node_filter = &node_filter;
585 : : _arc_filter = &arc_filter;
586 : : }
587 : :
588 : : public:
589 : :
590 : : typedef typename Parent::Node Node;
591 : : typedef typename Parent::Arc Arc;
592 : :
593 : : void first(Node& i) const {
594 : : Parent::first(i);
595 : : while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
596 : : }
597 : :
598 : : void first(Arc& i) const {
599 : : Parent::first(i);
600 : : while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
601 : : }
602 : :
603 : : void firstIn(Arc& i, const Node& n) const {
604 : : Parent::firstIn(i, n);
605 : : while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
606 : : }
607 : :
608 : : void firstOut(Arc& i, const Node& n) const {
609 : : Parent::firstOut(i, n);
610 : : while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
611 : : }
612 : :
613 : : void next(Node& i) const {
614 : : Parent::next(i);
615 : : while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
616 : : }
617 : : void next(Arc& i) const {
618 : : Parent::next(i);
619 : : while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
620 : : }
621 : : void nextIn(Arc& i) const {
622 : : Parent::nextIn(i);
623 : : while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
624 : : }
625 : :
626 : : void nextOut(Arc& i) const {
627 : : Parent::nextOut(i);
628 : : while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
629 : : }
630 : :
631 : : void status(const Node& n, bool v) const { _node_filter->set(n, v); }
632 : : void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
633 : :
634 : : bool status(const Node& n) const { return (*_node_filter)[n]; }
635 : : bool status(const Arc& a) const { return (*_arc_filter)[a]; }
636 : :
637 : : typedef False NodeNumTag;
638 : : typedef False ArcNumTag;
639 : :
640 : : typedef FindArcTagIndicator<DGR> FindArcTag;
641 : : Arc findArc(const Node& source, const Node& target,
642 : : const Arc& prev = INVALID) const {
643 : : if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
644 : : return INVALID;
645 : : }
646 : : Arc arc = Parent::findArc(source, target, prev);
647 : : while (arc != INVALID && !(*_arc_filter)[arc]) {
648 : : arc = Parent::findArc(source, target, arc);
649 : : }
650 : : return arc;
651 : : }
652 : :
653 : : template <typename V>
654 : : class NodeMap
655 : : : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
656 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
657 : : typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
658 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
659 : :
660 : : public:
661 : : typedef V Value;
662 : :
663 : : NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
664 : : : Parent(adaptor) {}
665 : : NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
666 : : : Parent(adaptor, value) {}
667 : :
668 : : private:
669 : : NodeMap& operator=(const NodeMap& cmap) {
670 : : return operator=<NodeMap>(cmap);
671 : : }
672 : :
673 : : template <typename CMap>
674 : : NodeMap& operator=(const CMap& cmap) {
675 : : Parent::operator=(cmap);
676 : : return *this;
677 : : }
678 : : };
679 : :
680 : : template <typename V>
681 : : class ArcMap
682 : : : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
683 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
684 : : typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
685 : : LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
686 : :
687 : : public:
688 : : typedef V Value;
689 : :
690 : : ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
691 : : : Parent(adaptor) {}
692 : : ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
693 : : : Parent(adaptor, value) {}
694 : :
695 : : private:
696 : : ArcMap& operator=(const ArcMap& cmap) {
697 : : return operator=<ArcMap>(cmap);
698 : : }
699 : :
700 : : template <typename CMap>
701 : : ArcMap& operator=(const CMap& cmap) {
702 : : Parent::operator=(cmap);
703 : : return *this;
704 : : }
705 : : };
706 : :
707 : : };
708 : :
709 : : /// \ingroup graph_adaptors
710 : : ///
711 : : /// \brief Adaptor class for hiding nodes and arcs in a digraph
712 : : ///
713 : : /// SubDigraph can be used for hiding nodes and arcs in a digraph.
714 : : /// A \c bool node map and a \c bool arc map must be specified, which
715 : : /// define the filters for nodes and arcs.
716 : : /// Only the nodes and arcs with \c true filter value are
717 : : /// shown in the subdigraph. The arcs that are incident to hidden
718 : : /// nodes are also filtered out.
719 : : /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
720 : : ///
721 : : /// The adapted digraph can also be modified through this adaptor
722 : : /// by adding or removing nodes or arcs, unless the \c GR template
723 : : /// parameter is set to be \c const.
724 : : ///
725 : : /// This class provides only linear time counting for nodes and arcs.
726 : : ///
727 : : /// \tparam DGR The type of the adapted digraph.
728 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept.
729 : : /// It can also be specified to be \c const.
730 : : /// \tparam NF The type of the node filter map.
731 : : /// It must be a \c bool (or convertible) node map of the
732 : : /// adapted digraph. The default type is
733 : : /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
734 : : /// \tparam AF The type of the arc filter map.
735 : : /// It must be \c bool (or convertible) arc map of the
736 : : /// adapted digraph. The default type is
737 : : /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
738 : : ///
739 : : /// \note The \c Node and \c Arc types of this adaptor and the adapted
740 : : /// digraph are convertible to each other.
741 : : ///
742 : : /// \see FilterNodes
743 : : /// \see FilterArcs
744 : : #ifdef DOXYGEN
745 : : template<typename DGR, typename NF, typename AF>
746 : : class SubDigraph {
747 : : #else
748 : : template<typename DGR,
749 : : typename NF = typename DGR::template NodeMap<bool>,
750 : : typename AF = typename DGR::template ArcMap<bool> >
751 : : class SubDigraph :
752 : : public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
753 : : #endif
754 : : public:
755 : : /// The type of the adapted digraph.
756 : : typedef DGR Digraph;
757 : : /// The type of the node filter map.
758 : : typedef NF NodeFilterMap;
759 : : /// The type of the arc filter map.
760 : : typedef AF ArcFilterMap;
761 : :
762 : : typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
763 : : Parent;
764 : :
765 : : typedef typename Parent::Node Node;
766 : : typedef typename Parent::Arc Arc;
767 : :
768 : : protected:
769 : : SubDigraph() { }
770 : : public:
771 : :
772 : : /// \brief Constructor
773 : : ///
774 : : /// Creates a subdigraph for the given digraph with the
775 : : /// given node and arc filter maps.
776 : : SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
777 : : Parent::initialize(digraph, node_filter, arc_filter);
778 : : }
779 : :
780 : : /// \brief Sets the status of the given node
781 : : ///
782 : : /// This function sets the status of the given node.
783 : : /// It is done by simply setting the assigned value of \c n
784 : : /// to \c v in the node filter map.
785 : : void status(const Node& n, bool v) const { Parent::status(n, v); }
786 : :
787 : : /// \brief Sets the status of the given arc
788 : : ///
789 : : /// This function sets the status of the given arc.
790 : : /// It is done by simply setting the assigned value of \c a
791 : : /// to \c v in the arc filter map.
792 : : void status(const Arc& a, bool v) const { Parent::status(a, v); }
793 : :
794 : : /// \brief Returns the status of the given node
795 : : ///
796 : : /// This function returns the status of the given node.
797 : : /// It is \c true if the given node is enabled (i.e. not hidden).
798 : : bool status(const Node& n) const { return Parent::status(n); }
799 : :
800 : : /// \brief Returns the status of the given arc
801 : : ///
802 : : /// This function returns the status of the given arc.
803 : : /// It is \c true if the given arc is enabled (i.e. not hidden).
804 : : bool status(const Arc& a) const { return Parent::status(a); }
805 : :
806 : : /// \brief Disables the given node
807 : : ///
808 : : /// This function disables the given node in the subdigraph,
809 : : /// so the iteration jumps over it.
810 : : /// It is the same as \ref status() "status(n, false)".
811 : : void disable(const Node& n) const { Parent::status(n, false); }
812 : :
813 : : /// \brief Disables the given arc
814 : : ///
815 : : /// This function disables the given arc in the subdigraph,
816 : : /// so the iteration jumps over it.
817 : : /// It is the same as \ref status() "status(a, false)".
818 : : void disable(const Arc& a) const { Parent::status(a, false); }
819 : :
820 : : /// \brief Enables the given node
821 : : ///
822 : : /// This function enables the given node in the subdigraph.
823 : : /// It is the same as \ref status() "status(n, true)".
824 : : void enable(const Node& n) const { Parent::status(n, true); }
825 : :
826 : : /// \brief Enables the given arc
827 : : ///
828 : : /// This function enables the given arc in the subdigraph.
829 : : /// It is the same as \ref status() "status(a, true)".
830 : : void enable(const Arc& a) const { Parent::status(a, true); }
831 : :
832 : : };
833 : :
834 : : /// \brief Returns a read-only SubDigraph adaptor
835 : : ///
836 : : /// This function just returns a read-only \ref SubDigraph adaptor.
837 : : /// \ingroup graph_adaptors
838 : : /// \relates SubDigraph
839 : : template<typename DGR, typename NF, typename AF>
840 : : SubDigraph<const DGR, NF, AF>
841 : : subDigraph(const DGR& digraph,
842 : : NF& node_filter, AF& arc_filter) {
843 : : return SubDigraph<const DGR, NF, AF>
844 : : (digraph, node_filter, arc_filter);
845 : : }
846 : :
847 : : template<typename DGR, typename NF, typename AF>
848 : : SubDigraph<const DGR, const NF, AF>
849 : : subDigraph(const DGR& digraph,
850 : : const NF& node_filter, AF& arc_filter) {
851 : : return SubDigraph<const DGR, const NF, AF>
852 : : (digraph, node_filter, arc_filter);
853 : : }
854 : :
855 : : template<typename DGR, typename NF, typename AF>
856 : : SubDigraph<const DGR, NF, const AF>
857 : : subDigraph(const DGR& digraph,
858 : : NF& node_filter, const AF& arc_filter) {
859 : : return SubDigraph<const DGR, NF, const AF>
860 : : (digraph, node_filter, arc_filter);
861 : : }
862 : :
863 : : template<typename DGR, typename NF, typename AF>
864 : : SubDigraph<const DGR, const NF, const AF>
865 : : subDigraph(const DGR& digraph,
866 : : const NF& node_filter, const AF& arc_filter) {
867 : : return SubDigraph<const DGR, const NF, const AF>
868 : : (digraph, node_filter, arc_filter);
869 : : }
870 : :
871 : :
872 : : template <typename GR, typename NF, typename EF, bool ch = true>
873 : : class SubGraphBase : public GraphAdaptorBase<GR> {
874 : : typedef GraphAdaptorBase<GR> Parent;
875 : : public:
876 : : typedef GR Graph;
877 : : typedef NF NodeFilterMap;
878 : : typedef EF EdgeFilterMap;
879 : :
880 : : typedef SubGraphBase Adaptor;
881 : : protected:
882 : :
883 : : NF* _node_filter;
884 : : EF* _edge_filter;
885 : :
886 : : SubGraphBase()
887 : : : Parent(), _node_filter(0), _edge_filter(0) { }
888 : :
889 : : void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
890 : : Parent::initialize(graph);
891 : : _node_filter = &node_filter;
892 : : _edge_filter = &edge_filter;
893 : : }
894 : :
895 : : public:
896 : :
897 : : typedef typename Parent::Node Node;
898 : : typedef typename Parent::Arc Arc;
899 : : typedef typename Parent::Edge Edge;
900 : :
901 : : void first(Node& i) const {
902 : : Parent::first(i);
903 : : while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
904 : : }
905 : :
906 : : void first(Arc& i) const {
907 : : Parent::first(i);
908 : : while (i!=INVALID && (!(*_edge_filter)[i]
909 : : || !(*_node_filter)[Parent::source(i)]
910 : : || !(*_node_filter)[Parent::target(i)]))
911 : : Parent::next(i);
912 : : }
913 : :
914 : : void first(Edge& i) const {
915 : : Parent::first(i);
916 : : while (i!=INVALID && (!(*_edge_filter)[i]
917 : : || !(*_node_filter)[Parent::u(i)]
918 : : || !(*_node_filter)[Parent::v(i)]))
919 : : Parent::next(i);
920 : : }
921 : :
922 : : void firstIn(Arc& i, const Node& n) const {
923 : : Parent::firstIn(i, n);
924 : : while (i!=INVALID && (!(*_edge_filter)[i]
925 : : || !(*_node_filter)[Parent::source(i)]))
926 : : Parent::nextIn(i);
927 : : }
928 : :
929 : : void firstOut(Arc& i, const Node& n) const {
930 : : Parent::firstOut(i, n);
931 : : while (i!=INVALID && (!(*_edge_filter)[i]
932 : : || !(*_node_filter)[Parent::target(i)]))
933 : : Parent::nextOut(i);
934 : : }
935 : :
936 : : void firstInc(Edge& i, bool& d, const Node& n) const {
937 : : Parent::firstInc(i, d, n);
938 : : while (i!=INVALID && (!(*_edge_filter)[i]
939 : : || !(*_node_filter)[Parent::u(i)]
940 : : || !(*_node_filter)[Parent::v(i)]))
941 : : Parent::nextInc(i, d);
942 : : }
943 : :
944 : : void next(Node& i) const {
945 : : Parent::next(i);
946 : : while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
947 : : }
948 : :
949 : : void next(Arc& i) const {
950 : : Parent::next(i);
951 : : while (i!=INVALID && (!(*_edge_filter)[i]
952 : : || !(*_node_filter)[Parent::source(i)]
953 : : || !(*_node_filter)[Parent::target(i)]))
954 : : Parent::next(i);
955 : : }
956 : :
957 : : void next(Edge& i) const {
958 : : Parent::next(i);
959 : : while (i!=INVALID && (!(*_edge_filter)[i]
960 : : || !(*_node_filter)[Parent::u(i)]
961 : : || !(*_node_filter)[Parent::v(i)]))
962 : : Parent::next(i);
963 : : }
964 : :
965 : : void nextIn(Arc& i) const {
966 : : Parent::nextIn(i);
967 : : while (i!=INVALID && (!(*_edge_filter)[i]
968 : : || !(*_node_filter)[Parent::source(i)]))
969 : : Parent::nextIn(i);
970 : : }
971 : :
972 : : void nextOut(Arc& i) const {
973 : : Parent::nextOut(i);
974 : : while (i!=INVALID && (!(*_edge_filter)[i]
975 : : || !(*_node_filter)[Parent::target(i)]))
976 : : Parent::nextOut(i);
977 : : }
978 : :
979 : : void nextInc(Edge& i, bool& d) const {
980 : : Parent::nextInc(i, d);
981 : : while (i!=INVALID && (!(*_edge_filter)[i]
982 : : || !(*_node_filter)[Parent::u(i)]
983 : : || !(*_node_filter)[Parent::v(i)]))
984 : : Parent::nextInc(i, d);
985 : : }
986 : :
987 : : void status(const Node& n, bool v) const { _node_filter->set(n, v); }
988 : : void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
989 : :
990 : : bool status(const Node& n) const { return (*_node_filter)[n]; }
991 : : bool status(const Edge& e) const { return (*_edge_filter)[e]; }
992 : :
993 : : typedef False NodeNumTag;
994 : : typedef False ArcNumTag;
995 : : typedef False EdgeNumTag;
996 : :
997 : : typedef FindArcTagIndicator<Graph> FindArcTag;
998 : : Arc findArc(const Node& u, const Node& v,
999 : : const Arc& prev = INVALID) const {
1000 : : if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
1001 : : return INVALID;
1002 : : }
1003 : : Arc arc = Parent::findArc(u, v, prev);
1004 : : while (arc != INVALID && !(*_edge_filter)[arc]) {
1005 : : arc = Parent::findArc(u, v, arc);
1006 : : }
1007 : : return arc;
1008 : : }
1009 : :
1010 : : typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1011 : : Edge findEdge(const Node& u, const Node& v,
1012 : : const Edge& prev = INVALID) const {
1013 : : if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
1014 : : return INVALID;
1015 : : }
1016 : : Edge edge = Parent::findEdge(u, v, prev);
1017 : : while (edge != INVALID && !(*_edge_filter)[edge]) {
1018 : : edge = Parent::findEdge(u, v, edge);
1019 : : }
1020 : : return edge;
1021 : : }
1022 : :
1023 : : template <typename V>
1024 : : class NodeMap
1025 : : : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1026 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1027 : : typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1028 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1029 : :
1030 : : public:
1031 : : typedef V Value;
1032 : :
1033 : : NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1034 : : : Parent(adaptor) {}
1035 : : NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1036 : : : Parent(adaptor, value) {}
1037 : :
1038 : : private:
1039 : : NodeMap& operator=(const NodeMap& cmap) {
1040 : : return operator=<NodeMap>(cmap);
1041 : : }
1042 : :
1043 : : template <typename CMap>
1044 : : NodeMap& operator=(const CMap& cmap) {
1045 : : Parent::operator=(cmap);
1046 : : return *this;
1047 : : }
1048 : : };
1049 : :
1050 : : template <typename V>
1051 : : class ArcMap
1052 : : : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1053 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1054 : : typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1055 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1056 : :
1057 : : public:
1058 : : typedef V Value;
1059 : :
1060 : : ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1061 : : : Parent(adaptor) {}
1062 : : ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1063 : : : Parent(adaptor, value) {}
1064 : :
1065 : : private:
1066 : : ArcMap& operator=(const ArcMap& cmap) {
1067 : : return operator=<ArcMap>(cmap);
1068 : : }
1069 : :
1070 : : template <typename CMap>
1071 : : ArcMap& operator=(const CMap& cmap) {
1072 : : Parent::operator=(cmap);
1073 : : return *this;
1074 : : }
1075 : : };
1076 : :
1077 : : template <typename V>
1078 : : class EdgeMap
1079 : : : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1080 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1081 : : typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1082 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1083 : :
1084 : : public:
1085 : : typedef V Value;
1086 : :
1087 : : EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1088 : : : Parent(adaptor) {}
1089 : :
1090 : : EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1091 : : : Parent(adaptor, value) {}
1092 : :
1093 : : private:
1094 : : EdgeMap& operator=(const EdgeMap& cmap) {
1095 : : return operator=<EdgeMap>(cmap);
1096 : : }
1097 : :
1098 : : template <typename CMap>
1099 : : EdgeMap& operator=(const CMap& cmap) {
1100 : : Parent::operator=(cmap);
1101 : : return *this;
1102 : : }
1103 : : };
1104 : :
1105 : : };
1106 : :
1107 : : template <typename GR, typename NF, typename EF>
1108 : : class SubGraphBase<GR, NF, EF, false>
1109 : : : public GraphAdaptorBase<GR> {
1110 : : typedef GraphAdaptorBase<GR> Parent;
1111 : : public:
1112 : : typedef GR Graph;
1113 : : typedef NF NodeFilterMap;
1114 : : typedef EF EdgeFilterMap;
1115 : :
1116 : : typedef SubGraphBase Adaptor;
1117 : : protected:
1118 : : NF* _node_filter;
1119 : : EF* _edge_filter;
1120 : : SubGraphBase()
1121 : : : Parent(), _node_filter(0), _edge_filter(0) { }
1122 : :
1123 : : void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
1124 : : Parent::initialize(graph);
1125 : : _node_filter = &node_filter;
1126 : : _edge_filter = &edge_filter;
1127 : : }
1128 : :
1129 : : public:
1130 : :
1131 : : typedef typename Parent::Node Node;
1132 : : typedef typename Parent::Arc Arc;
1133 : : typedef typename Parent::Edge Edge;
1134 : :
1135 : : void first(Node& i) const {
1136 : : Parent::first(i);
1137 : : while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1138 : : }
1139 : :
1140 : : void first(Arc& i) const {
1141 : : Parent::first(i);
1142 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1143 : : }
1144 : :
1145 : : void first(Edge& i) const {
1146 : : Parent::first(i);
1147 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1148 : : }
1149 : :
1150 : : void firstIn(Arc& i, const Node& n) const {
1151 : : Parent::firstIn(i, n);
1152 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
1153 : : }
1154 : :
1155 : : void firstOut(Arc& i, const Node& n) const {
1156 : : Parent::firstOut(i, n);
1157 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
1158 : : }
1159 : :
1160 : : void firstInc(Edge& i, bool& d, const Node& n) const {
1161 : : Parent::firstInc(i, d, n);
1162 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
1163 : : }
1164 : :
1165 : : void next(Node& i) const {
1166 : : Parent::next(i);
1167 : : while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1168 : : }
1169 : : void next(Arc& i) const {
1170 : : Parent::next(i);
1171 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1172 : : }
1173 : : void next(Edge& i) const {
1174 : : Parent::next(i);
1175 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1176 : : }
1177 : : void nextIn(Arc& i) const {
1178 : : Parent::nextIn(i);
1179 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
1180 : : }
1181 : :
1182 : : void nextOut(Arc& i) const {
1183 : : Parent::nextOut(i);
1184 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
1185 : : }
1186 : : void nextInc(Edge& i, bool& d) const {
1187 : : Parent::nextInc(i, d);
1188 : : while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
1189 : : }
1190 : :
1191 : : void status(const Node& n, bool v) const { _node_filter->set(n, v); }
1192 : : void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
1193 : :
1194 : : bool status(const Node& n) const { return (*_node_filter)[n]; }
1195 : : bool status(const Edge& e) const { return (*_edge_filter)[e]; }
1196 : :
1197 : : typedef False NodeNumTag;
1198 : : typedef False ArcNumTag;
1199 : : typedef False EdgeNumTag;
1200 : :
1201 : : typedef FindArcTagIndicator<Graph> FindArcTag;
1202 : : Arc findArc(const Node& u, const Node& v,
1203 : : const Arc& prev = INVALID) const {
1204 : : Arc arc = Parent::findArc(u, v, prev);
1205 : : while (arc != INVALID && !(*_edge_filter)[arc]) {
1206 : : arc = Parent::findArc(u, v, arc);
1207 : : }
1208 : : return arc;
1209 : : }
1210 : :
1211 : : typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1212 : : Edge findEdge(const Node& u, const Node& v,
1213 : : const Edge& prev = INVALID) const {
1214 : : Edge edge = Parent::findEdge(u, v, prev);
1215 : : while (edge != INVALID && !(*_edge_filter)[edge]) {
1216 : : edge = Parent::findEdge(u, v, edge);
1217 : : }
1218 : : return edge;
1219 : : }
1220 : :
1221 : : template <typename V>
1222 : : class NodeMap
1223 : : : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1224 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1225 : : typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1226 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1227 : :
1228 : : public:
1229 : : typedef V Value;
1230 : :
1231 : : NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1232 : : : Parent(adaptor) {}
1233 : : NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1234 : : : Parent(adaptor, value) {}
1235 : :
1236 : : private:
1237 : : NodeMap& operator=(const NodeMap& cmap) {
1238 : : return operator=<NodeMap>(cmap);
1239 : : }
1240 : :
1241 : : template <typename CMap>
1242 : : NodeMap& operator=(const CMap& cmap) {
1243 : : Parent::operator=(cmap);
1244 : : return *this;
1245 : : }
1246 : : };
1247 : :
1248 : : template <typename V>
1249 : : class ArcMap
1250 : : : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1251 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1252 : : typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1253 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1254 : :
1255 : : public:
1256 : : typedef V Value;
1257 : :
1258 : : ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1259 : : : Parent(adaptor) {}
1260 : : ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1261 : : : Parent(adaptor, value) {}
1262 : :
1263 : : private:
1264 : : ArcMap& operator=(const ArcMap& cmap) {
1265 : : return operator=<ArcMap>(cmap);
1266 : : }
1267 : :
1268 : : template <typename CMap>
1269 : : ArcMap& operator=(const CMap& cmap) {
1270 : : Parent::operator=(cmap);
1271 : : return *this;
1272 : : }
1273 : : };
1274 : :
1275 : : template <typename V>
1276 : : class EdgeMap
1277 : : : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1278 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1279 : : typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1280 : : LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1281 : :
1282 : : public:
1283 : : typedef V Value;
1284 : :
1285 : : EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1286 : : : Parent(adaptor) {}
1287 : :
1288 : : EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1289 : : : Parent(adaptor, value) {}
1290 : :
1291 : : private:
1292 : : EdgeMap& operator=(const EdgeMap& cmap) {
1293 : : return operator=<EdgeMap>(cmap);
1294 : : }
1295 : :
1296 : : template <typename CMap>
1297 : : EdgeMap& operator=(const CMap& cmap) {
1298 : : Parent::operator=(cmap);
1299 : : return *this;
1300 : : }
1301 : : };
1302 : :
1303 : : };
1304 : :
1305 : : /// \ingroup graph_adaptors
1306 : : ///
1307 : : /// \brief Adaptor class for hiding nodes and edges in an undirected
1308 : : /// graph.
1309 : : ///
1310 : : /// SubGraph can be used for hiding nodes and edges in a graph.
1311 : : /// A \c bool node map and a \c bool edge map must be specified, which
1312 : : /// define the filters for nodes and edges.
1313 : : /// Only the nodes and edges with \c true filter value are
1314 : : /// shown in the subgraph. The edges that are incident to hidden
1315 : : /// nodes are also filtered out.
1316 : : /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
1317 : : ///
1318 : : /// The adapted graph can also be modified through this adaptor
1319 : : /// by adding or removing nodes or edges, unless the \c GR template
1320 : : /// parameter is set to be \c const.
1321 : : ///
1322 : : /// This class provides only linear time counting for nodes, edges and arcs.
1323 : : ///
1324 : : /// \tparam GR The type of the adapted graph.
1325 : : /// It must conform to the \ref concepts::Graph "Graph" concept.
1326 : : /// It can also be specified to be \c const.
1327 : : /// \tparam NF The type of the node filter map.
1328 : : /// It must be a \c bool (or convertible) node map of the
1329 : : /// adapted graph. The default type is
1330 : : /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1331 : : /// \tparam EF The type of the edge filter map.
1332 : : /// It must be a \c bool (or convertible) edge map of the
1333 : : /// adapted graph. The default type is
1334 : : /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1335 : : ///
1336 : : /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1337 : : /// adapted graph are convertible to each other.
1338 : : ///
1339 : : /// \see FilterNodes
1340 : : /// \see FilterEdges
1341 : : #ifdef DOXYGEN
1342 : : template<typename GR, typename NF, typename EF>
1343 : : class SubGraph {
1344 : : #else
1345 : : template<typename GR,
1346 : : typename NF = typename GR::template NodeMap<bool>,
1347 : : typename EF = typename GR::template EdgeMap<bool> >
1348 : : class SubGraph :
1349 : : public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
1350 : : #endif
1351 : : public:
1352 : : /// The type of the adapted graph.
1353 : : typedef GR Graph;
1354 : : /// The type of the node filter map.
1355 : : typedef NF NodeFilterMap;
1356 : : /// The type of the edge filter map.
1357 : : typedef EF EdgeFilterMap;
1358 : :
1359 : : typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
1360 : : Parent;
1361 : :
1362 : : typedef typename Parent::Node Node;
1363 : : typedef typename Parent::Edge Edge;
1364 : :
1365 : : protected:
1366 : : SubGraph() { }
1367 : : public:
1368 : :
1369 : : /// \brief Constructor
1370 : : ///
1371 : : /// Creates a subgraph for the given graph with the given node
1372 : : /// and edge filter maps.
1373 : : SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
1374 : : initialize(graph, node_filter, edge_filter);
1375 : : }
1376 : :
1377 : : /// \brief Sets the status of the given node
1378 : : ///
1379 : : /// This function sets the status of the given node.
1380 : : /// It is done by simply setting the assigned value of \c n
1381 : : /// to \c v in the node filter map.
1382 : : void status(const Node& n, bool v) const { Parent::status(n, v); }
1383 : :
1384 : : /// \brief Sets the status of the given edge
1385 : : ///
1386 : : /// This function sets the status of the given edge.
1387 : : /// It is done by simply setting the assigned value of \c e
1388 : : /// to \c v in the edge filter map.
1389 : : void status(const Edge& e, bool v) const { Parent::status(e, v); }
1390 : :
1391 : : /// \brief Returns the status of the given node
1392 : : ///
1393 : : /// This function returns the status of the given node.
1394 : : /// It is \c true if the given node is enabled (i.e. not hidden).
1395 : : bool status(const Node& n) const { return Parent::status(n); }
1396 : :
1397 : : /// \brief Returns the status of the given edge
1398 : : ///
1399 : : /// This function returns the status of the given edge.
1400 : : /// It is \c true if the given edge is enabled (i.e. not hidden).
1401 : : bool status(const Edge& e) const { return Parent::status(e); }
1402 : :
1403 : : /// \brief Disables the given node
1404 : : ///
1405 : : /// This function disables the given node in the subdigraph,
1406 : : /// so the iteration jumps over it.
1407 : : /// It is the same as \ref status() "status(n, false)".
1408 : : void disable(const Node& n) const { Parent::status(n, false); }
1409 : :
1410 : : /// \brief Disables the given edge
1411 : : ///
1412 : : /// This function disables the given edge in the subgraph,
1413 : : /// so the iteration jumps over it.
1414 : : /// It is the same as \ref status() "status(e, false)".
1415 : : void disable(const Edge& e) const { Parent::status(e, false); }
1416 : :
1417 : : /// \brief Enables the given node
1418 : : ///
1419 : : /// This function enables the given node in the subdigraph.
1420 : : /// It is the same as \ref status() "status(n, true)".
1421 : : void enable(const Node& n) const { Parent::status(n, true); }
1422 : :
1423 : : /// \brief Enables the given edge
1424 : : ///
1425 : : /// This function enables the given edge in the subgraph.
1426 : : /// It is the same as \ref status() "status(e, true)".
1427 : : void enable(const Edge& e) const { Parent::status(e, true); }
1428 : :
1429 : : };
1430 : :
1431 : : /// \brief Returns a read-only SubGraph adaptor
1432 : : ///
1433 : : /// This function just returns a read-only \ref SubGraph adaptor.
1434 : : /// \ingroup graph_adaptors
1435 : : /// \relates SubGraph
1436 : : template<typename GR, typename NF, typename EF>
1437 : : SubGraph<const GR, NF, EF>
1438 : : subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
1439 : : return SubGraph<const GR, NF, EF>
1440 : : (graph, node_filter, edge_filter);
1441 : : }
1442 : :
1443 : : template<typename GR, typename NF, typename EF>
1444 : : SubGraph<const GR, const NF, EF>
1445 : : subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
1446 : : return SubGraph<const GR, const NF, EF>
1447 : : (graph, node_filter, edge_filter);
1448 : : }
1449 : :
1450 : : template<typename GR, typename NF, typename EF>
1451 : : SubGraph<const GR, NF, const EF>
1452 : : subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
1453 : : return SubGraph<const GR, NF, const EF>
1454 : : (graph, node_filter, edge_filter);
1455 : : }
1456 : :
1457 : : template<typename GR, typename NF, typename EF>
1458 : : SubGraph<const GR, const NF, const EF>
1459 : : subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
1460 : : return SubGraph<const GR, const NF, const EF>
1461 : : (graph, node_filter, edge_filter);
1462 : : }
1463 : :
1464 : :
1465 : : /// \ingroup graph_adaptors
1466 : : ///
1467 : : /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1468 : : ///
1469 : : /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
1470 : : /// graph. A \c bool node map must be specified, which defines the filter
1471 : : /// for the nodes. Only the nodes with \c true filter value and the
1472 : : /// arcs/edges incident to nodes both with \c true filter value are shown
1473 : : /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
1474 : : /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
1475 : : /// depending on the \c GR template parameter.
1476 : : ///
1477 : : /// The adapted (di)graph can also be modified through this adaptor
1478 : : /// by adding or removing nodes or arcs/edges, unless the \c GR template
1479 : : /// parameter is set to be \c const.
1480 : : ///
1481 : : /// This class provides only linear time item counting.
1482 : : ///
1483 : : /// \tparam GR The type of the adapted digraph or graph.
1484 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept
1485 : : /// or the \ref concepts::Graph "Graph" concept.
1486 : : /// It can also be specified to be \c const.
1487 : : /// \tparam NF The type of the node filter map.
1488 : : /// It must be a \c bool (or convertible) node map of the
1489 : : /// adapted (di)graph. The default type is
1490 : : /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1491 : : ///
1492 : : /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
1493 : : /// adapted (di)graph are convertible to each other.
1494 : : #ifdef DOXYGEN
1495 : : template<typename GR, typename NF>
1496 : : class FilterNodes {
1497 : : #else
1498 : : template<typename GR,
1499 : : typename NF = typename GR::template NodeMap<bool>,
1500 : : typename Enable = void>
1501 : : class FilterNodes :
1502 : : public DigraphAdaptorExtender<
1503 : : SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1504 : : true> > {
1505 : : #endif
1506 : : typedef DigraphAdaptorExtender<
1507 : : SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1508 : : true> > Parent;
1509 : :
1510 : : public:
1511 : :
1512 : : typedef GR Digraph;
1513 : : typedef NF NodeFilterMap;
1514 : :
1515 : : typedef typename Parent::Node Node;
1516 : :
1517 : : protected:
1518 : : ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
1519 : :
1520 : : FilterNodes() : const_true_map() {}
1521 : :
1522 : : public:
1523 : :
1524 : : /// \brief Constructor
1525 : : ///
1526 : : /// Creates a subgraph for the given digraph or graph with the
1527 : : /// given node filter map.
1528 : : FilterNodes(GR& graph, NF& node_filter)
1529 : : : Parent(), const_true_map()
1530 : : {
1531 : : Parent::initialize(graph, node_filter, const_true_map);
1532 : : }
1533 : :
1534 : : /// \brief Sets the status of the given node
1535 : : ///
1536 : : /// This function sets the status of the given node.
1537 : : /// It is done by simply setting the assigned value of \c n
1538 : : /// to \c v in the node filter map.
1539 : : void status(const Node& n, bool v) const { Parent::status(n, v); }
1540 : :
1541 : : /// \brief Returns the status of the given node
1542 : : ///
1543 : : /// This function returns the status of the given node.
1544 : : /// It is \c true if the given node is enabled (i.e. not hidden).
1545 : : bool status(const Node& n) const { return Parent::status(n); }
1546 : :
1547 : : /// \brief Disables the given node
1548 : : ///
1549 : : /// This function disables the given node, so the iteration
1550 : : /// jumps over it.
1551 : : /// It is the same as \ref status() "status(n, false)".
1552 : : void disable(const Node& n) const { Parent::status(n, false); }
1553 : :
1554 : : /// \brief Enables the given node
1555 : : ///
1556 : : /// This function enables the given node.
1557 : : /// It is the same as \ref status() "status(n, true)".
1558 : : void enable(const Node& n) const { Parent::status(n, true); }
1559 : :
1560 : : };
1561 : :
1562 : : template<typename GR, typename NF>
1563 : : class FilterNodes<GR, NF,
1564 : : typename enable_if<UndirectedTagIndicator<GR> >::type> :
1565 : : public GraphAdaptorExtender<
1566 : : SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1567 : : true> > {
1568 : :
1569 : : typedef GraphAdaptorExtender<
1570 : : SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1571 : : true> > Parent;
1572 : :
1573 : : public:
1574 : :
1575 : : typedef GR Graph;
1576 : : typedef NF NodeFilterMap;
1577 : :
1578 : : typedef typename Parent::Node Node;
1579 : :
1580 : : protected:
1581 : : ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
1582 : :
1583 : : FilterNodes() : const_true_map() {}
1584 : :
1585 : : public:
1586 : :
1587 : : FilterNodes(GR& graph, NodeFilterMap& node_filter) :
1588 : : Parent(), const_true_map() {
1589 : : Parent::initialize(graph, node_filter, const_true_map);
1590 : : }
1591 : :
1592 : : void status(const Node& n, bool v) const { Parent::status(n, v); }
1593 : : bool status(const Node& n) const { return Parent::status(n); }
1594 : : void disable(const Node& n) const { Parent::status(n, false); }
1595 : : void enable(const Node& n) const { Parent::status(n, true); }
1596 : :
1597 : : };
1598 : :
1599 : :
1600 : : /// \brief Returns a read-only FilterNodes adaptor
1601 : : ///
1602 : : /// This function just returns a read-only \ref FilterNodes adaptor.
1603 : : /// \ingroup graph_adaptors
1604 : : /// \relates FilterNodes
1605 : : template<typename GR, typename NF>
1606 : : FilterNodes<const GR, NF>
1607 : : filterNodes(const GR& graph, NF& node_filter) {
1608 : : return FilterNodes<const GR, NF>(graph, node_filter);
1609 : : }
1610 : :
1611 : : template<typename GR, typename NF>
1612 : : FilterNodes<const GR, const NF>
1613 : : filterNodes(const GR& graph, const NF& node_filter) {
1614 : : return FilterNodes<const GR, const NF>(graph, node_filter);
1615 : : }
1616 : :
1617 : : /// \ingroup graph_adaptors
1618 : : ///
1619 : : /// \brief Adaptor class for hiding arcs in a digraph.
1620 : : ///
1621 : : /// FilterArcs adaptor can be used for hiding arcs in a digraph.
1622 : : /// A \c bool arc map must be specified, which defines the filter for
1623 : : /// the arcs. Only the arcs with \c true filter value are shown in the
1624 : : /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
1625 : : /// "Digraph" concept.
1626 : : ///
1627 : : /// The adapted digraph can also be modified through this adaptor
1628 : : /// by adding or removing nodes or arcs, unless the \c GR template
1629 : : /// parameter is set to be \c const.
1630 : : ///
1631 : : /// This class provides only linear time counting for nodes and arcs.
1632 : : ///
1633 : : /// \tparam DGR The type of the adapted digraph.
1634 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1635 : : /// It can also be specified to be \c const.
1636 : : /// \tparam AF The type of the arc filter map.
1637 : : /// It must be a \c bool (or convertible) arc map of the
1638 : : /// adapted digraph. The default type is
1639 : : /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
1640 : : ///
1641 : : /// \note The \c Node and \c Arc types of this adaptor and the adapted
1642 : : /// digraph are convertible to each other.
1643 : : #ifdef DOXYGEN
1644 : : template<typename DGR,
1645 : : typename AF>
1646 : : class FilterArcs {
1647 : : #else
1648 : : template<typename DGR,
1649 : : typename AF = typename DGR::template ArcMap<bool> >
1650 : : class FilterArcs :
1651 : : public DigraphAdaptorExtender<
1652 : : SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1653 : : AF, false> > {
1654 : : #endif
1655 : : typedef DigraphAdaptorExtender<
1656 : : SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1657 : : AF, false> > Parent;
1658 : :
1659 : : public:
1660 : :
1661 : : /// The type of the adapted digraph.
1662 : : typedef DGR Digraph;
1663 : : /// The type of the arc filter map.
1664 : : typedef AF ArcFilterMap;
1665 : :
1666 : : typedef typename Parent::Arc Arc;
1667 : :
1668 : : protected:
1669 : : ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
1670 : :
1671 : : FilterArcs() : const_true_map() {}
1672 : :
1673 : : public:
1674 : :
1675 : : /// \brief Constructor
1676 : : ///
1677 : : /// Creates a subdigraph for the given digraph with the given arc
1678 : : /// filter map.
1679 : : FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
1680 : : : Parent(), const_true_map() {
1681 : : Parent::initialize(digraph, const_true_map, arc_filter);
1682 : : }
1683 : :
1684 : : /// \brief Sets the status of the given arc
1685 : : ///
1686 : : /// This function sets the status of the given arc.
1687 : : /// It is done by simply setting the assigned value of \c a
1688 : : /// to \c v in the arc filter map.
1689 : : void status(const Arc& a, bool v) const { Parent::status(a, v); }
1690 : :
1691 : : /// \brief Returns the status of the given arc
1692 : : ///
1693 : : /// This function returns the status of the given arc.
1694 : : /// It is \c true if the given arc is enabled (i.e. not hidden).
1695 : : bool status(const Arc& a) const { return Parent::status(a); }
1696 : :
1697 : : /// \brief Disables the given arc
1698 : : ///
1699 : : /// This function disables the given arc in the subdigraph,
1700 : : /// so the iteration jumps over it.
1701 : : /// It is the same as \ref status() "status(a, false)".
1702 : : void disable(const Arc& a) const { Parent::status(a, false); }
1703 : :
1704 : : /// \brief Enables the given arc
1705 : : ///
1706 : : /// This function enables the given arc in the subdigraph.
1707 : : /// It is the same as \ref status() "status(a, true)".
1708 : : void enable(const Arc& a) const { Parent::status(a, true); }
1709 : :
1710 : : };
1711 : :
1712 : : /// \brief Returns a read-only FilterArcs adaptor
1713 : : ///
1714 : : /// This function just returns a read-only \ref FilterArcs adaptor.
1715 : : /// \ingroup graph_adaptors
1716 : : /// \relates FilterArcs
1717 : : template<typename DGR, typename AF>
1718 : : FilterArcs<const DGR, AF>
1719 : : filterArcs(const DGR& digraph, AF& arc_filter) {
1720 : : return FilterArcs<const DGR, AF>(digraph, arc_filter);
1721 : : }
1722 : :
1723 : : template<typename DGR, typename AF>
1724 : : FilterArcs<const DGR, const AF>
1725 : : filterArcs(const DGR& digraph, const AF& arc_filter) {
1726 : : return FilterArcs<const DGR, const AF>(digraph, arc_filter);
1727 : : }
1728 : :
1729 : : /// \ingroup graph_adaptors
1730 : : ///
1731 : : /// \brief Adaptor class for hiding edges in a graph.
1732 : : ///
1733 : : /// FilterEdges adaptor can be used for hiding edges in a graph.
1734 : : /// A \c bool edge map must be specified, which defines the filter for
1735 : : /// the edges. Only the edges with \c true filter value are shown in the
1736 : : /// subgraph. This adaptor conforms to the \ref concepts::Graph
1737 : : /// "Graph" concept.
1738 : : ///
1739 : : /// The adapted graph can also be modified through this adaptor
1740 : : /// by adding or removing nodes or edges, unless the \c GR template
1741 : : /// parameter is set to be \c const.
1742 : : ///
1743 : : /// This class provides only linear time counting for nodes, edges and arcs.
1744 : : ///
1745 : : /// \tparam GR The type of the adapted graph.
1746 : : /// It must conform to the \ref concepts::Graph "Graph" concept.
1747 : : /// It can also be specified to be \c const.
1748 : : /// \tparam EF The type of the edge filter map.
1749 : : /// It must be a \c bool (or convertible) edge map of the
1750 : : /// adapted graph. The default type is
1751 : : /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1752 : : ///
1753 : : /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1754 : : /// adapted graph are convertible to each other.
1755 : : #ifdef DOXYGEN
1756 : : template<typename GR,
1757 : : typename EF>
1758 : : class FilterEdges {
1759 : : #else
1760 : : template<typename GR,
1761 : : typename EF = typename GR::template EdgeMap<bool> >
1762 : : class FilterEdges :
1763 : : public GraphAdaptorExtender<
1764 : : SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
1765 : : EF, false> > {
1766 : : #endif
1767 : : typedef GraphAdaptorExtender<
1768 : : SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
1769 : : EF, false> > Parent;
1770 : :
1771 : : public:
1772 : :
1773 : : /// The type of the adapted graph.
1774 : : typedef GR Graph;
1775 : : /// The type of the edge filter map.
1776 : : typedef EF EdgeFilterMap;
1777 : :
1778 : : typedef typename Parent::Edge Edge;
1779 : :
1780 : : protected:
1781 : : ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
1782 : :
1783 : : FilterEdges() : const_true_map(true) {
1784 : : Parent::setNodeFilterMap(const_true_map);
1785 : : }
1786 : :
1787 : : public:
1788 : :
1789 : : /// \brief Constructor
1790 : : ///
1791 : : /// Creates a subgraph for the given graph with the given edge
1792 : : /// filter map.
1793 : : FilterEdges(GR& graph, EF& edge_filter)
1794 : : : Parent(), const_true_map() {
1795 : : Parent::initialize(graph, const_true_map, edge_filter);
1796 : : }
1797 : :
1798 : : /// \brief Sets the status of the given edge
1799 : : ///
1800 : : /// This function sets the status of the given edge.
1801 : : /// It is done by simply setting the assigned value of \c e
1802 : : /// to \c v in the edge filter map.
1803 : : void status(const Edge& e, bool v) const { Parent::status(e, v); }
1804 : :
1805 : : /// \brief Returns the status of the given edge
1806 : : ///
1807 : : /// This function returns the status of the given edge.
1808 : : /// It is \c true if the given edge is enabled (i.e. not hidden).
1809 : : bool status(const Edge& e) const { return Parent::status(e); }
1810 : :
1811 : : /// \brief Disables the given edge
1812 : : ///
1813 : : /// This function disables the given edge in the subgraph,
1814 : : /// so the iteration jumps over it.
1815 : : /// It is the same as \ref status() "status(e, false)".
1816 : : void disable(const Edge& e) const { Parent::status(e, false); }
1817 : :
1818 : : /// \brief Enables the given edge
1819 : : ///
1820 : : /// This function enables the given edge in the subgraph.
1821 : : /// It is the same as \ref status() "status(e, true)".
1822 : : void enable(const Edge& e) const { Parent::status(e, true); }
1823 : :
1824 : : };
1825 : :
1826 : : /// \brief Returns a read-only FilterEdges adaptor
1827 : : ///
1828 : : /// This function just returns a read-only \ref FilterEdges adaptor.
1829 : : /// \ingroup graph_adaptors
1830 : : /// \relates FilterEdges
1831 : : template<typename GR, typename EF>
1832 : : FilterEdges<const GR, EF>
1833 : : filterEdges(const GR& graph, EF& edge_filter) {
1834 : : return FilterEdges<const GR, EF>(graph, edge_filter);
1835 : : }
1836 : :
1837 : : template<typename GR, typename EF>
1838 : : FilterEdges<const GR, const EF>
1839 : : filterEdges(const GR& graph, const EF& edge_filter) {
1840 : : return FilterEdges<const GR, const EF>(graph, edge_filter);
1841 : : }
1842 : :
1843 : :
1844 : : template <typename DGR>
1845 : : class UndirectorBase {
1846 : : public:
1847 : : typedef DGR Digraph;
1848 : : typedef UndirectorBase Adaptor;
1849 : :
1850 : : typedef True UndirectedTag;
1851 : :
1852 : : typedef typename Digraph::Arc Edge;
1853 : : typedef typename Digraph::Node Node;
1854 : :
1855 : : class Arc {
1856 : : friend class UndirectorBase;
1857 : : protected:
1858 : : Edge _edge;
1859 : : bool _forward;
1860 : :
1861 : : Arc(const Edge& edge, bool forward)
1862 : : : _edge(edge), _forward(forward) {}
1863 : :
1864 : : public:
1865 : : Arc() {}
1866 : :
1867 : : Arc(Invalid) : _edge(INVALID), _forward(true) {}
1868 : :
1869 : : operator const Edge&() const { return _edge; }
1870 : :
1871 : : bool operator==(const Arc &other) const {
1872 : : return _forward == other._forward && _edge == other._edge;
1873 : : }
1874 : : bool operator!=(const Arc &other) const {
1875 : : return _forward != other._forward || _edge != other._edge;
1876 : : }
1877 : : bool operator<(const Arc &other) const {
1878 : : return _forward < other._forward ||
1879 : : (_forward == other._forward && _edge < other._edge);
1880 : : }
1881 : : };
1882 : :
1883 : : void first(Node& n) const {
1884 : : _digraph->first(n);
1885 : : }
1886 : :
1887 : : void next(Node& n) const {
1888 : : _digraph->next(n);
1889 : : }
1890 : :
1891 : : void first(Arc& a) const {
1892 : : _digraph->first(a._edge);
1893 : : a._forward = true;
1894 : : }
1895 : :
1896 : : void next(Arc& a) const {
1897 : : if (a._forward) {
1898 : : a._forward = false;
1899 : : } else {
1900 : : _digraph->next(a._edge);
1901 : : a._forward = true;
1902 : : }
1903 : : }
1904 : :
1905 : : void first(Edge& e) const {
1906 : : _digraph->first(e);
1907 : : }
1908 : :
1909 : : void next(Edge& e) const {
1910 : : _digraph->next(e);
1911 : : }
1912 : :
1913 : : void firstOut(Arc& a, const Node& n) const {
1914 : : _digraph->firstIn(a._edge, n);
1915 : : if (a._edge != INVALID ) {
1916 : : a._forward = false;
1917 : : } else {
1918 : : _digraph->firstOut(a._edge, n);
1919 : : a._forward = true;
1920 : : }
1921 : : }
1922 : : void nextOut(Arc &a) const {
1923 : : if (!a._forward) {
1924 : : Node n = _digraph->target(a._edge);
1925 : : _digraph->nextIn(a._edge);
1926 : : if (a._edge == INVALID) {
1927 : : _digraph->firstOut(a._edge, n);
1928 : : a._forward = true;
1929 : : }
1930 : : }
1931 : : else {
1932 : : _digraph->nextOut(a._edge);
1933 : : }
1934 : : }
1935 : :
1936 : : void firstIn(Arc &a, const Node &n) const {
1937 : : _digraph->firstOut(a._edge, n);
1938 : : if (a._edge != INVALID ) {
1939 : : a._forward = false;
1940 : : } else {
1941 : : _digraph->firstIn(a._edge, n);
1942 : : a._forward = true;
1943 : : }
1944 : : }
1945 : : void nextIn(Arc &a) const {
1946 : : if (!a._forward) {
1947 : : Node n = _digraph->source(a._edge);
1948 : : _digraph->nextOut(a._edge);
1949 : : if (a._edge == INVALID ) {
1950 : : _digraph->firstIn(a._edge, n);
1951 : : a._forward = true;
1952 : : }
1953 : : }
1954 : : else {
1955 : : _digraph->nextIn(a._edge);
1956 : : }
1957 : : }
1958 : :
1959 : : void firstInc(Edge &e, bool &d, const Node &n) const {
1960 : : d = true;
1961 : : _digraph->firstOut(e, n);
1962 : : if (e != INVALID) return;
1963 : : d = false;
1964 : : _digraph->firstIn(e, n);
1965 : : }
1966 : :
1967 : : void nextInc(Edge &e, bool &d) const {
1968 : : if (d) {
1969 : : Node s = _digraph->source(e);
1970 : : _digraph->nextOut(e);
1971 : : if (e != INVALID) return;
1972 : : d = false;
1973 : : _digraph->firstIn(e, s);
1974 : : } else {
1975 : : _digraph->nextIn(e);
1976 : : }
1977 : : }
1978 : :
1979 : : Node u(const Edge& e) const {
1980 : : return _digraph->source(e);
1981 : : }
1982 : :
1983 : : Node v(const Edge& e) const {
1984 : : return _digraph->target(e);
1985 : : }
1986 : :
1987 : : Node source(const Arc &a) const {
1988 : : return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
1989 : : }
1990 : :
1991 : : Node target(const Arc &a) const {
1992 : : return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
1993 : : }
1994 : :
1995 : : static Arc direct(const Edge &e, bool d) {
1996 : : return Arc(e, d);
1997 : : }
1998 : :
1999 : : static bool direction(const Arc &a) { return a._forward; }
2000 : :
2001 : : Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
2002 : : Arc arcFromId(int ix) const {
2003 : : return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
2004 : : }
2005 : : Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
2006 : :
2007 : : int id(const Node &n) const { return _digraph->id(n); }
2008 : : int id(const Arc &a) const {
2009 : : return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
2010 : : }
2011 : : int id(const Edge &e) const { return _digraph->id(e); }
2012 : :
2013 : : int maxNodeId() const { return _digraph->maxNodeId(); }
2014 : : int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
2015 : : int maxEdgeId() const { return _digraph->maxArcId(); }
2016 : :
2017 : : Node addNode() { return _digraph->addNode(); }
2018 : : Edge addEdge(const Node& u, const Node& v) {
2019 : : return _digraph->addArc(u, v);
2020 : : }
2021 : :
2022 : : void erase(const Node& i) { _digraph->erase(i); }
2023 : : void erase(const Edge& i) { _digraph->erase(i); }
2024 : :
2025 : : void clear() { _digraph->clear(); }
2026 : :
2027 : : typedef NodeNumTagIndicator<Digraph> NodeNumTag;
2028 : : int nodeNum() const { return _digraph->nodeNum(); }
2029 : :
2030 : : typedef ArcNumTagIndicator<Digraph> ArcNumTag;
2031 : : int arcNum() const { return 2 * _digraph->arcNum(); }
2032 : :
2033 : : typedef ArcNumTag EdgeNumTag;
2034 : : int edgeNum() const { return _digraph->arcNum(); }
2035 : :
2036 : : typedef FindArcTagIndicator<Digraph> FindArcTag;
2037 : : Arc findArc(Node s, Node t, Arc p = INVALID) const {
2038 : : if (p == INVALID) {
2039 : : Edge arc = _digraph->findArc(s, t);
2040 : : if (arc != INVALID) return direct(arc, true);
2041 : : arc = _digraph->findArc(t, s);
2042 : : if (arc != INVALID) return direct(arc, false);
2043 : : } else if (direction(p)) {
2044 : : Edge arc = _digraph->findArc(s, t, p);
2045 : : if (arc != INVALID) return direct(arc, true);
2046 : : arc = _digraph->findArc(t, s);
2047 : : if (arc != INVALID) return direct(arc, false);
2048 : : } else {
2049 : : Edge arc = _digraph->findArc(t, s, p);
2050 : : if (arc != INVALID) return direct(arc, false);
2051 : : }
2052 : : return INVALID;
2053 : : }
2054 : :
2055 : : typedef FindArcTag FindEdgeTag;
2056 : : Edge findEdge(Node s, Node t, Edge p = INVALID) const {
2057 : : if (s != t) {
2058 : : if (p == INVALID) {
2059 : : Edge arc = _digraph->findArc(s, t);
2060 : : if (arc != INVALID) return arc;
2061 : : arc = _digraph->findArc(t, s);
2062 : : if (arc != INVALID) return arc;
2063 : : } else if (_digraph->source(p) == s) {
2064 : : Edge arc = _digraph->findArc(s, t, p);
2065 : : if (arc != INVALID) return arc;
2066 : : arc = _digraph->findArc(t, s);
2067 : : if (arc != INVALID) return arc;
2068 : : } else {
2069 : : Edge arc = _digraph->findArc(t, s, p);
2070 : : if (arc != INVALID) return arc;
2071 : : }
2072 : : } else {
2073 : : return _digraph->findArc(s, t, p);
2074 : : }
2075 : : return INVALID;
2076 : : }
2077 : :
2078 : : private:
2079 : :
2080 : : template <typename V>
2081 : : class ArcMapBase {
2082 : : private:
2083 : :
2084 : : typedef typename DGR::template ArcMap<V> MapImpl;
2085 : :
2086 : : public:
2087 : :
2088 : : typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
2089 : :
2090 : : typedef V Value;
2091 : : typedef Arc Key;
2092 : : typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
2093 : : typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
2094 : : typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
2095 : : typedef typename MapTraits<MapImpl>::ReturnValue Reference;
2096 : :
2097 : : ArcMapBase(const UndirectorBase<DGR>& adaptor) :
2098 : : _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
2099 : :
2100 : : ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
2101 : : : _forward(*adaptor._digraph, value),
2102 : : _backward(*adaptor._digraph, value) {}
2103 : :
2104 : : void set(const Arc& a, const V& value) {
2105 : : if (direction(a)) {
2106 : : _forward.set(a, value);
2107 : : } else {
2108 : : _backward.set(a, value);
2109 : : }
2110 : : }
2111 : :
2112 : : ConstReturnValue operator[](const Arc& a) const {
2113 : : if (direction(a)) {
2114 : : return _forward[a];
2115 : : } else {
2116 : : return _backward[a];
2117 : : }
2118 : : }
2119 : :
2120 : : ReturnValue operator[](const Arc& a) {
2121 : : if (direction(a)) {
2122 : : return _forward[a];
2123 : : } else {
2124 : : return _backward[a];
2125 : : }
2126 : : }
2127 : :
2128 : : protected:
2129 : :
2130 : : MapImpl _forward, _backward;
2131 : :
2132 : : };
2133 : :
2134 : : public:
2135 : :
2136 : : template <typename V>
2137 : : class NodeMap : public DGR::template NodeMap<V> {
2138 : : typedef typename DGR::template NodeMap<V> Parent;
2139 : :
2140 : : public:
2141 : : typedef V Value;
2142 : :
2143 : : explicit NodeMap(const UndirectorBase<DGR>& adaptor)
2144 : : : Parent(*adaptor._digraph) {}
2145 : :
2146 : : NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
2147 : : : Parent(*adaptor._digraph, value) { }
2148 : :
2149 : : private:
2150 : : NodeMap& operator=(const NodeMap& cmap) {
2151 : : return operator=<NodeMap>(cmap);
2152 : : }
2153 : :
2154 : : template <typename CMap>
2155 : : NodeMap& operator=(const CMap& cmap) {
2156 : : Parent::operator=(cmap);
2157 : : return *this;
2158 : : }
2159 : :
2160 : : };
2161 : :
2162 : : template <typename V>
2163 : : class ArcMap
2164 : : : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
2165 : : typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
2166 : :
2167 : : public:
2168 : : typedef V Value;
2169 : :
2170 : : explicit ArcMap(const UndirectorBase<DGR>& adaptor)
2171 : : : Parent(adaptor) {}
2172 : :
2173 : : ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
2174 : : : Parent(adaptor, value) {}
2175 : :
2176 : : private:
2177 : : ArcMap& operator=(const ArcMap& cmap) {
2178 : : return operator=<ArcMap>(cmap);
2179 : : }
2180 : :
2181 : : template <typename CMap>
2182 : : ArcMap& operator=(const CMap& cmap) {
2183 : : Parent::operator=(cmap);
2184 : : return *this;
2185 : : }
2186 : : };
2187 : :
2188 : : template <typename V>
2189 : : class EdgeMap : public Digraph::template ArcMap<V> {
2190 : : typedef typename Digraph::template ArcMap<V> Parent;
2191 : :
2192 : : public:
2193 : : typedef V Value;
2194 : :
2195 : : explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
2196 : : : Parent(*adaptor._digraph) {}
2197 : :
2198 : : EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
2199 : : : Parent(*adaptor._digraph, value) {}
2200 : :
2201 : : private:
2202 : : EdgeMap& operator=(const EdgeMap& cmap) {
2203 : : return operator=<EdgeMap>(cmap);
2204 : : }
2205 : :
2206 : : template <typename CMap>
2207 : : EdgeMap& operator=(const CMap& cmap) {
2208 : : Parent::operator=(cmap);
2209 : : return *this;
2210 : : }
2211 : :
2212 : : };
2213 : :
2214 : : typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
2215 : : NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2216 : :
2217 : : typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
2218 : : EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
2219 : :
2220 : : typedef EdgeNotifier ArcNotifier;
2221 : : ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
2222 : :
2223 : : protected:
2224 : :
2225 : : UndirectorBase() : _digraph(0) {}
2226 : :
2227 : : DGR* _digraph;
2228 : :
2229 : : void initialize(DGR& digraph) {
2230 : : _digraph = &digraph;
2231 : : }
2232 : :
2233 : : };
2234 : :
2235 : : /// \ingroup graph_adaptors
2236 : : ///
2237 : : /// \brief Adaptor class for viewing a digraph as an undirected graph.
2238 : : ///
2239 : : /// Undirector adaptor can be used for viewing a digraph as an undirected
2240 : : /// graph. All arcs of the underlying digraph are showed in the
2241 : : /// adaptor as an edge (and also as a pair of arcs, of course).
2242 : : /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
2243 : : ///
2244 : : /// The adapted digraph can also be modified through this adaptor
2245 : : /// by adding or removing nodes or edges, unless the \c GR template
2246 : : /// parameter is set to be \c const.
2247 : : ///
2248 : : /// This class provides item counting in the same time as the adapted
2249 : : /// digraph structure.
2250 : : ///
2251 : : /// \tparam DGR The type of the adapted digraph.
2252 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2253 : : /// It can also be specified to be \c const.
2254 : : ///
2255 : : /// \note The \c Node type of this adaptor and the adapted digraph are
2256 : : /// convertible to each other, moreover the \c Edge type of the adaptor
2257 : : /// and the \c Arc type of the adapted digraph are also convertible to
2258 : : /// each other.
2259 : : /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
2260 : : /// of the adapted digraph.)
2261 : : template<typename DGR>
2262 : : #ifdef DOXYGEN
2263 : : class Undirector {
2264 : : #else
2265 : : class Undirector :
2266 : : public GraphAdaptorExtender<UndirectorBase<DGR> > {
2267 : : #endif
2268 : : typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
2269 : : public:
2270 : : /// The type of the adapted digraph.
2271 : : typedef DGR Digraph;
2272 : : protected:
2273 : : Undirector() { }
2274 : : public:
2275 : :
2276 : : /// \brief Constructor
2277 : : ///
2278 : : /// Creates an undirected graph from the given digraph.
2279 : : Undirector(DGR& digraph) {
2280 : : initialize(digraph);
2281 : : }
2282 : :
2283 : : /// \brief Arc map combined from two original arc maps
2284 : : ///
2285 : : /// This map adaptor class adapts two arc maps of the underlying
2286 : : /// digraph to get an arc map of the undirected graph.
2287 : : /// Its value type is inherited from the first arc map type (\c FW).
2288 : : /// \tparam FW The type of the "foward" arc map.
2289 : : /// \tparam BK The type of the "backward" arc map.
2290 : : template <typename FW, typename BK>
2291 : : class CombinedArcMap {
2292 : : public:
2293 : :
2294 : : /// The key type of the map
2295 : : typedef typename Parent::Arc Key;
2296 : : /// The value type of the map
2297 : : typedef typename FW::Value Value;
2298 : :
2299 : : typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
2300 : :
2301 : : typedef typename MapTraits<FW>::ReturnValue ReturnValue;
2302 : : typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
2303 : : typedef typename MapTraits<FW>::ReturnValue Reference;
2304 : : typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
2305 : :
2306 : : /// Constructor
2307 : : CombinedArcMap(FW& forward, BK& backward)
2308 : : : _forward(&forward), _backward(&backward) {}
2309 : :
2310 : : /// Sets the value associated with the given key.
2311 : : void set(const Key& e, const Value& a) {
2312 : : if (Parent::direction(e)) {
2313 : : _forward->set(e, a);
2314 : : } else {
2315 : : _backward->set(e, a);
2316 : : }
2317 : : }
2318 : :
2319 : : /// Returns the value associated with the given key.
2320 : : ConstReturnValue operator[](const Key& e) const {
2321 : : if (Parent::direction(e)) {
2322 : : return (*_forward)[e];
2323 : : } else {
2324 : : return (*_backward)[e];
2325 : : }
2326 : : }
2327 : :
2328 : : /// Returns a reference to the value associated with the given key.
2329 : : ReturnValue operator[](const Key& e) {
2330 : : if (Parent::direction(e)) {
2331 : : return (*_forward)[e];
2332 : : } else {
2333 : : return (*_backward)[e];
2334 : : }
2335 : : }
2336 : :
2337 : : protected:
2338 : :
2339 : : FW* _forward;
2340 : : BK* _backward;
2341 : :
2342 : : };
2343 : :
2344 : : /// \brief Returns a combined arc map
2345 : : ///
2346 : : /// This function just returns a combined arc map.
2347 : : template <typename FW, typename BK>
2348 : : static CombinedArcMap<FW, BK>
2349 : : combinedArcMap(FW& forward, BK& backward) {
2350 : : return CombinedArcMap<FW, BK>(forward, backward);
2351 : : }
2352 : :
2353 : : template <typename FW, typename BK>
2354 : : static CombinedArcMap<const FW, BK>
2355 : : combinedArcMap(const FW& forward, BK& backward) {
2356 : : return CombinedArcMap<const FW, BK>(forward, backward);
2357 : : }
2358 : :
2359 : : template <typename FW, typename BK>
2360 : : static CombinedArcMap<FW, const BK>
2361 : : combinedArcMap(FW& forward, const BK& backward) {
2362 : : return CombinedArcMap<FW, const BK>(forward, backward);
2363 : : }
2364 : :
2365 : : template <typename FW, typename BK>
2366 : : static CombinedArcMap<const FW, const BK>
2367 : : combinedArcMap(const FW& forward, const BK& backward) {
2368 : : return CombinedArcMap<const FW, const BK>(forward, backward);
2369 : : }
2370 : :
2371 : : };
2372 : :
2373 : : /// \brief Returns a read-only Undirector adaptor
2374 : : ///
2375 : : /// This function just returns a read-only \ref Undirector adaptor.
2376 : : /// \ingroup graph_adaptors
2377 : : /// \relates Undirector
2378 : : template<typename DGR>
2379 : : Undirector<const DGR> undirector(const DGR& digraph) {
2380 : : return Undirector<const DGR>(digraph);
2381 : : }
2382 : :
2383 : :
2384 : : template <typename GR, typename DM>
2385 : : class OrienterBase {
2386 : : public:
2387 : :
2388 : : typedef GR Graph;
2389 : : typedef DM DirectionMap;
2390 : :
2391 : : typedef typename GR::Node Node;
2392 : : typedef typename GR::Edge Arc;
2393 : :
2394 : : void reverseArc(const Arc& arc) {
2395 : : _direction->set(arc, !(*_direction)[arc]);
2396 : : }
2397 : :
2398 : : void first(Node& i) const { _graph->first(i); }
2399 : : void first(Arc& i) const { _graph->first(i); }
2400 : : void firstIn(Arc& i, const Node& n) const {
2401 : : bool d = true;
2402 : : _graph->firstInc(i, d, n);
2403 : : while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2404 : : }
2405 : : void firstOut(Arc& i, const Node& n ) const {
2406 : : bool d = true;
2407 : : _graph->firstInc(i, d, n);
2408 : : while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2409 : : }
2410 : :
2411 : : void next(Node& i) const { _graph->next(i); }
2412 : : void next(Arc& i) const { _graph->next(i); }
2413 : : void nextIn(Arc& i) const {
2414 : : bool d = !(*_direction)[i];
2415 : : _graph->nextInc(i, d);
2416 : : while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2417 : : }
2418 : : void nextOut(Arc& i) const {
2419 : : bool d = (*_direction)[i];
2420 : : _graph->nextInc(i, d);
2421 : : while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2422 : : }
2423 : :
2424 : : Node source(const Arc& e) const {
2425 : : return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2426 : : }
2427 : : Node target(const Arc& e) const {
2428 : : return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2429 : : }
2430 : :
2431 : : typedef NodeNumTagIndicator<Graph> NodeNumTag;
2432 : : int nodeNum() const { return _graph->nodeNum(); }
2433 : :
2434 : : typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2435 : : int arcNum() const { return _graph->edgeNum(); }
2436 : :
2437 : : typedef FindEdgeTagIndicator<Graph> FindArcTag;
2438 : : Arc findArc(const Node& u, const Node& v,
2439 : : const Arc& prev = INVALID) const {
2440 : : Arc arc = _graph->findEdge(u, v, prev);
2441 : : while (arc != INVALID && source(arc) != u) {
2442 : : arc = _graph->findEdge(u, v, arc);
2443 : : }
2444 : : return arc;
2445 : : }
2446 : :
2447 : : Node addNode() {
2448 : : return Node(_graph->addNode());
2449 : : }
2450 : :
2451 : : Arc addArc(const Node& u, const Node& v) {
2452 : : Arc arc = _graph->addEdge(u, v);
2453 : : _direction->set(arc, _graph->u(arc) == u);
2454 : : return arc;
2455 : : }
2456 : :
2457 : : void erase(const Node& i) { _graph->erase(i); }
2458 : : void erase(const Arc& i) { _graph->erase(i); }
2459 : :
2460 : : void clear() { _graph->clear(); }
2461 : :
2462 : : int id(const Node& v) const { return _graph->id(v); }
2463 : : int id(const Arc& e) const { return _graph->id(e); }
2464 : :
2465 : : Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2466 : : Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2467 : :
2468 : : int maxNodeId() const { return _graph->maxNodeId(); }
2469 : : int maxArcId() const { return _graph->maxEdgeId(); }
2470 : :
2471 : : typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
2472 : : NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2473 : :
2474 : : typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
2475 : : ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2476 : :
2477 : : template <typename V>
2478 : : class NodeMap : public GR::template NodeMap<V> {
2479 : : typedef typename GR::template NodeMap<V> Parent;
2480 : :
2481 : : public:
2482 : :
2483 : : explicit NodeMap(const OrienterBase<GR, DM>& adapter)
2484 : : : Parent(*adapter._graph) {}
2485 : :
2486 : : NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
2487 : : : Parent(*adapter._graph, value) {}
2488 : :
2489 : : private:
2490 : : NodeMap& operator=(const NodeMap& cmap) {
2491 : : return operator=<NodeMap>(cmap);
2492 : : }
2493 : :
2494 : : template <typename CMap>
2495 : : NodeMap& operator=(const CMap& cmap) {
2496 : : Parent::operator=(cmap);
2497 : : return *this;
2498 : : }
2499 : :
2500 : : };
2501 : :
2502 : : template <typename V>
2503 : : class ArcMap : public GR::template EdgeMap<V> {
2504 : : typedef typename Graph::template EdgeMap<V> Parent;
2505 : :
2506 : : public:
2507 : :
2508 : : explicit ArcMap(const OrienterBase<GR, DM>& adapter)
2509 : : : Parent(*adapter._graph) { }
2510 : :
2511 : : ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
2512 : : : Parent(*adapter._graph, value) { }
2513 : :
2514 : : private:
2515 : : ArcMap& operator=(const ArcMap& cmap) {
2516 : : return operator=<ArcMap>(cmap);
2517 : : }
2518 : :
2519 : : template <typename CMap>
2520 : : ArcMap& operator=(const CMap& cmap) {
2521 : : Parent::operator=(cmap);
2522 : : return *this;
2523 : : }
2524 : : };
2525 : :
2526 : :
2527 : :
2528 : : protected:
2529 : : Graph* _graph;
2530 : : DM* _direction;
2531 : :
2532 : : void initialize(GR& graph, DM& direction) {
2533 : : _graph = &graph;
2534 : : _direction = &direction;
2535 : : }
2536 : :
2537 : : };
2538 : :
2539 : : /// \ingroup graph_adaptors
2540 : : ///
2541 : : /// \brief Adaptor class for orienting the edges of a graph to get a digraph
2542 : : ///
2543 : : /// Orienter adaptor can be used for orienting the edges of a graph to
2544 : : /// get a digraph. A \c bool edge map of the underlying graph must be
2545 : : /// specified, which define the direction of the arcs in the adaptor.
2546 : : /// The arcs can be easily reversed by the \c reverseArc() member function
2547 : : /// of the adaptor.
2548 : : /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2549 : : ///
2550 : : /// The adapted graph can also be modified through this adaptor
2551 : : /// by adding or removing nodes or arcs, unless the \c GR template
2552 : : /// parameter is set to be \c const.
2553 : : ///
2554 : : /// This class provides item counting in the same time as the adapted
2555 : : /// graph structure.
2556 : : ///
2557 : : /// \tparam GR The type of the adapted graph.
2558 : : /// It must conform to the \ref concepts::Graph "Graph" concept.
2559 : : /// It can also be specified to be \c const.
2560 : : /// \tparam DM The type of the direction map.
2561 : : /// It must be a \c bool (or convertible) edge map of the
2562 : : /// adapted graph. The default type is
2563 : : /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
2564 : : ///
2565 : : /// \note The \c Node type of this adaptor and the adapted graph are
2566 : : /// convertible to each other, moreover the \c Arc type of the adaptor
2567 : : /// and the \c Edge type of the adapted graph are also convertible to
2568 : : /// each other.
2569 : : #ifdef DOXYGEN
2570 : : template<typename GR,
2571 : : typename DM>
2572 : : class Orienter {
2573 : : #else
2574 : : template<typename GR,
2575 : : typename DM = typename GR::template EdgeMap<bool> >
2576 : : class Orienter :
2577 : : public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
2578 : : #endif
2579 : : typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
2580 : : public:
2581 : :
2582 : : /// The type of the adapted graph.
2583 : : typedef GR Graph;
2584 : : /// The type of the direction edge map.
2585 : : typedef DM DirectionMap;
2586 : :
2587 : : typedef typename Parent::Arc Arc;
2588 : :
2589 : : protected:
2590 : : Orienter() { }
2591 : :
2592 : : public:
2593 : :
2594 : : /// \brief Constructor
2595 : : ///
2596 : : /// Constructor of the adaptor.
2597 : : Orienter(GR& graph, DM& direction) {
2598 : : Parent::initialize(graph, direction);
2599 : : }
2600 : :
2601 : : /// \brief Reverses the given arc
2602 : : ///
2603 : : /// This function reverses the given arc.
2604 : : /// It is done by simply negate the assigned value of \c a
2605 : : /// in the direction map.
2606 : : void reverseArc(const Arc& a) {
2607 : : Parent::reverseArc(a);
2608 : : }
2609 : : };
2610 : :
2611 : : /// \brief Returns a read-only Orienter adaptor
2612 : : ///
2613 : : /// This function just returns a read-only \ref Orienter adaptor.
2614 : : /// \ingroup graph_adaptors
2615 : : /// \relates Orienter
2616 : : template<typename GR, typename DM>
2617 : : Orienter<const GR, DM>
2618 : : orienter(const GR& graph, DM& direction) {
2619 : : return Orienter<const GR, DM>(graph, direction);
2620 : : }
2621 : :
2622 : : template<typename GR, typename DM>
2623 : : Orienter<const GR, const DM>
2624 : : orienter(const GR& graph, const DM& direction) {
2625 : : return Orienter<const GR, const DM>(graph, direction);
2626 : : }
2627 : :
2628 : : namespace _adaptor_bits {
2629 : :
2630 : : template <typename DGR, typename CM, typename FM, typename TL>
2631 : : class ResForwardFilter {
2632 : : public:
2633 : :
2634 : : typedef typename DGR::Arc Key;
2635 : : typedef bool Value;
2636 : :
2637 : : private:
2638 : :
2639 : : const CM* _capacity;
2640 : : const FM* _flow;
2641 : : TL _tolerance;
2642 : :
2643 : : public:
2644 : :
2645 : : ResForwardFilter(const CM& capacity, const FM& flow,
2646 : : const TL& tolerance = TL())
2647 : : : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2648 : :
2649 : : bool operator[](const typename DGR::Arc& a) const {
2650 : : return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2651 : : }
2652 : : };
2653 : :
2654 : : template<typename DGR,typename CM, typename FM, typename TL>
2655 : : class ResBackwardFilter {
2656 : : public:
2657 : :
2658 : : typedef typename DGR::Arc Key;
2659 : : typedef bool Value;
2660 : :
2661 : : private:
2662 : :
2663 : : const CM* _capacity;
2664 : : const FM* _flow;
2665 : : TL _tolerance;
2666 : :
2667 : : public:
2668 : :
2669 : : ResBackwardFilter(const CM& capacity, const FM& flow,
2670 : : const TL& tolerance = TL())
2671 : : : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2672 : :
2673 : : bool operator[](const typename DGR::Arc& a) const {
2674 : : return _tolerance.positive((*_flow)[a]);
2675 : : }
2676 : : };
2677 : :
2678 : : }
2679 : :
2680 : : /// \ingroup graph_adaptors
2681 : : ///
2682 : : /// \brief Adaptor class for composing the residual digraph for directed
2683 : : /// flow and circulation problems.
2684 : : ///
2685 : : /// ResidualDigraph can be used for composing the \e residual digraph
2686 : : /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
2687 : : /// be a directed graph and let \f$ F \f$ be a number type.
2688 : : /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
2689 : : /// This adaptor implements a digraph structure with node set \f$ V \f$
2690 : : /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
2691 : : /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
2692 : : /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
2693 : : /// called residual digraph.
2694 : : /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
2695 : : /// multiplicities are counted, i.e. the adaptor has exactly
2696 : : /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
2697 : : /// arcs).
2698 : : /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2699 : : ///
2700 : : /// This class provides only linear time counting for nodes and arcs.
2701 : : ///
2702 : : /// \tparam DGR The type of the adapted digraph.
2703 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2704 : : /// It is implicitly \c const.
2705 : : /// \tparam CM The type of the capacity map.
2706 : : /// It must be an arc map of some numerical type, which defines
2707 : : /// the capacities in the flow problem. It is implicitly \c const.
2708 : : /// The default type is
2709 : : /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
2710 : : /// \tparam FM The type of the flow map.
2711 : : /// It must be an arc map of some numerical type, which defines
2712 : : /// the flow values in the flow problem. The default type is \c CM.
2713 : : /// \tparam TL The tolerance type for handling inexact computation.
2714 : : /// The default tolerance type depends on the value type of the
2715 : : /// capacity map.
2716 : : ///
2717 : : /// \note This adaptor is implemented using Undirector and FilterArcs
2718 : : /// adaptors.
2719 : : ///
2720 : : /// \note The \c Node type of this adaptor and the adapted digraph are
2721 : : /// convertible to each other, moreover the \c Arc type of the adaptor
2722 : : /// is convertible to the \c Arc type of the adapted digraph.
2723 : : #ifdef DOXYGEN
2724 : : template<typename DGR, typename CM, typename FM, typename TL>
2725 : : class ResidualDigraph
2726 : : #else
2727 : : template<typename DGR,
2728 : : typename CM = typename DGR::template ArcMap<int>,
2729 : : typename FM = CM,
2730 : : typename TL = Tolerance<typename CM::Value> >
2731 : : class ResidualDigraph
2732 : : : public SubDigraph<
2733 : : Undirector<const DGR>,
2734 : : ConstMap<typename DGR::Node, Const<bool, true> >,
2735 : : typename Undirector<const DGR>::template CombinedArcMap<
2736 : : _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
2737 : : _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
2738 : : #endif
2739 : : {
2740 : : public:
2741 : :
2742 : : /// The type of the underlying digraph.
2743 : : typedef DGR Digraph;
2744 : : /// The type of the capacity map.
2745 : : typedef CM CapacityMap;
2746 : : /// The type of the flow map.
2747 : : typedef FM FlowMap;
2748 : : /// The tolerance type.
2749 : : typedef TL Tolerance;
2750 : :
2751 : : typedef typename CapacityMap::Value Value;
2752 : : typedef ResidualDigraph Adaptor;
2753 : :
2754 : : protected:
2755 : :
2756 : : typedef Undirector<const Digraph> Undirected;
2757 : :
2758 : : typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
2759 : :
2760 : : typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
2761 : : FM, TL> ForwardFilter;
2762 : :
2763 : : typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
2764 : : FM, TL> BackwardFilter;
2765 : :
2766 : : typedef typename Undirected::
2767 : : template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2768 : :
2769 : : typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
2770 : :
2771 : : const CapacityMap* _capacity;
2772 : : FlowMap* _flow;
2773 : :
2774 : : Undirected _graph;
2775 : : NodeFilter _node_filter;
2776 : : ForwardFilter _forward_filter;
2777 : : BackwardFilter _backward_filter;
2778 : : ArcFilter _arc_filter;
2779 : :
2780 : : public:
2781 : :
2782 : : /// \brief Constructor
2783 : : ///
2784 : : /// Constructor of the residual digraph adaptor. The parameters are the
2785 : : /// digraph, the capacity map, the flow map, and a tolerance object.
2786 : : ResidualDigraph(const DGR& digraph, const CM& capacity,
2787 : : FM& flow, const TL& tolerance = Tolerance())
2788 : : : Parent(), _capacity(&capacity), _flow(&flow),
2789 : : _graph(digraph), _node_filter(),
2790 : : _forward_filter(capacity, flow, tolerance),
2791 : : _backward_filter(capacity, flow, tolerance),
2792 : : _arc_filter(_forward_filter, _backward_filter)
2793 : : {
2794 : : Parent::initialize(_graph, _node_filter, _arc_filter);
2795 : : }
2796 : :
2797 : : typedef typename Parent::Arc Arc;
2798 : :
2799 : : /// \brief Returns the residual capacity of the given arc.
2800 : : ///
2801 : : /// Returns the residual capacity of the given arc.
2802 : : Value residualCapacity(const Arc& a) const {
2803 : : if (Undirected::direction(a)) {
2804 : : return (*_capacity)[a] - (*_flow)[a];
2805 : : } else {
2806 : : return (*_flow)[a];
2807 : : }
2808 : : }
2809 : :
2810 : : /// \brief Augments on the given arc in the residual digraph.
2811 : : ///
2812 : : /// Augments on the given arc in the residual digraph. It increases
2813 : : /// or decreases the flow value on the original arc according to the
2814 : : /// direction of the residual arc.
2815 : : void augment(const Arc& a, const Value& v) const {
2816 : : if (Undirected::direction(a)) {
2817 : : _flow->set(a, (*_flow)[a] + v);
2818 : : } else {
2819 : : _flow->set(a, (*_flow)[a] - v);
2820 : : }
2821 : : }
2822 : :
2823 : : /// \brief Returns \c true if the given residual arc is a forward arc.
2824 : : ///
2825 : : /// Returns \c true if the given residual arc has the same orientation
2826 : : /// as the original arc, i.e. it is a so called forward arc.
2827 : : static bool forward(const Arc& a) {
2828 : : return Undirected::direction(a);
2829 : : }
2830 : :
2831 : : /// \brief Returns \c true if the given residual arc is a backward arc.
2832 : : ///
2833 : : /// Returns \c true if the given residual arc has the opposite orientation
2834 : : /// than the original arc, i.e. it is a so called backward arc.
2835 : : static bool backward(const Arc& a) {
2836 : : return !Undirected::direction(a);
2837 : : }
2838 : :
2839 : : /// \brief Returns the forward oriented residual arc.
2840 : : ///
2841 : : /// Returns the forward oriented residual arc related to the given
2842 : : /// arc of the underlying digraph.
2843 : : static Arc forward(const typename Digraph::Arc& a) {
2844 : : return Undirected::direct(a, true);
2845 : : }
2846 : :
2847 : : /// \brief Returns the backward oriented residual arc.
2848 : : ///
2849 : : /// Returns the backward oriented residual arc related to the given
2850 : : /// arc of the underlying digraph.
2851 : : static Arc backward(const typename Digraph::Arc& a) {
2852 : : return Undirected::direct(a, false);
2853 : : }
2854 : :
2855 : : /// \brief Residual capacity map.
2856 : : ///
2857 : : /// This map adaptor class can be used for obtaining the residual
2858 : : /// capacities as an arc map of the residual digraph.
2859 : : /// Its value type is inherited from the capacity map.
2860 : : class ResidualCapacity {
2861 : : protected:
2862 : : const Adaptor* _adaptor;
2863 : : public:
2864 : : /// The key type of the map
2865 : : typedef Arc Key;
2866 : : /// The value type of the map
2867 : : typedef typename CapacityMap::Value Value;
2868 : :
2869 : : /// Constructor
2870 : : ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
2871 : : : _adaptor(&adaptor) {}
2872 : :
2873 : : /// Returns the value associated with the given residual arc
2874 : : Value operator[](const Arc& a) const {
2875 : : return _adaptor->residualCapacity(a);
2876 : : }
2877 : :
2878 : : };
2879 : :
2880 : : /// \brief Returns a residual capacity map
2881 : : ///
2882 : : /// This function just returns a residual capacity map.
2883 : : ResidualCapacity residualCapacity() const {
2884 : : return ResidualCapacity(*this);
2885 : : }
2886 : :
2887 : : };
2888 : :
2889 : : /// \brief Returns a (read-only) Residual adaptor
2890 : : ///
2891 : : /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
2892 : : /// \ingroup graph_adaptors
2893 : : /// \relates ResidualDigraph
2894 : : template<typename DGR, typename CM, typename FM>
2895 : : ResidualDigraph<DGR, CM, FM>
2896 : : residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
2897 : : return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
2898 : : }
2899 : :
2900 : :
2901 : : template <typename DGR>
2902 : : class SplitNodesBase {
2903 : : typedef DigraphAdaptorBase<const DGR> Parent;
2904 : :
2905 : : public:
2906 : :
2907 : : typedef DGR Digraph;
2908 : : typedef SplitNodesBase Adaptor;
2909 : :
2910 : : typedef typename DGR::Node DigraphNode;
2911 : : typedef typename DGR::Arc DigraphArc;
2912 : :
2913 : : class Node;
2914 : : class Arc;
2915 : :
2916 : : private:
2917 : :
2918 : : template <typename T> class NodeMapBase;
2919 : : template <typename T> class ArcMapBase;
2920 : :
2921 : : public:
2922 : :
2923 : : class Node : public DigraphNode {
2924 : : friend class SplitNodesBase;
2925 : : template <typename T> friend class NodeMapBase;
2926 : : private:
2927 : :
2928 : : bool _in;
2929 : : Node(DigraphNode node, bool in)
2930 : : : DigraphNode(node), _in(in) {}
2931 : :
2932 : : public:
2933 : :
2934 : : Node() {}
2935 : : Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2936 : :
2937 : : bool operator==(const Node& node) const {
2938 : : return DigraphNode::operator==(node) && _in == node._in;
2939 : : }
2940 : :
2941 : : bool operator!=(const Node& node) const {
2942 : : return !(*this == node);
2943 : : }
2944 : :
2945 : : bool operator<(const Node& node) const {
2946 : : return DigraphNode::operator<(node) ||
2947 : : (DigraphNode::operator==(node) && _in < node._in);
2948 : : }
2949 : : };
2950 : :
2951 : : class Arc {
2952 : : friend class SplitNodesBase;
2953 : : template <typename T> friend class ArcMapBase;
2954 : : private:
2955 : : typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2956 : :
2957 : : explicit Arc(const DigraphArc& arc) : _item(arc) {}
2958 : : explicit Arc(const DigraphNode& node) : _item(node) {}
2959 : :
2960 : : ArcImpl _item;
2961 : :
2962 : : public:
2963 : : Arc() {}
2964 : : Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2965 : :
2966 : : bool operator==(const Arc& arc) const {
2967 : : if (_item.firstState()) {
2968 : : if (arc._item.firstState()) {
2969 : : return _item.first() == arc._item.first();
2970 : : }
2971 : : } else {
2972 : : if (arc._item.secondState()) {
2973 : : return _item.second() == arc._item.second();
2974 : : }
2975 : : }
2976 : : return false;
2977 : : }
2978 : :
2979 : : bool operator!=(const Arc& arc) const {
2980 : : return !(*this == arc);
2981 : : }
2982 : :
2983 : : bool operator<(const Arc& arc) const {
2984 : : if (_item.firstState()) {
2985 : : if (arc._item.firstState()) {
2986 : : return _item.first() < arc._item.first();
2987 : : }
2988 : : return false;
2989 : : } else {
2990 : : if (arc._item.secondState()) {
2991 : : return _item.second() < arc._item.second();
2992 : : }
2993 : : return true;
2994 : : }
2995 : : }
2996 : :
2997 : : operator DigraphArc() const { return _item.first(); }
2998 : : operator DigraphNode() const { return _item.second(); }
2999 : :
3000 : : };
3001 : :
3002 : : void first(Node& n) const {
3003 : : _digraph->first(n);
3004 : : n._in = true;
3005 : : }
3006 : :
3007 : : void next(Node& n) const {
3008 : : if (n._in) {
3009 : : n._in = false;
3010 : : } else {
3011 : : n._in = true;
3012 : : _digraph->next(n);
3013 : : }
3014 : : }
3015 : :
3016 : : void first(Arc& e) const {
3017 : : e._item.setSecond();
3018 : : _digraph->first(e._item.second());
3019 : : if (e._item.second() == INVALID) {
3020 : : e._item.setFirst();
3021 : : _digraph->first(e._item.first());
3022 : : }
3023 : : }
3024 : :
3025 : : void next(Arc& e) const {
3026 : : if (e._item.secondState()) {
3027 : : _digraph->next(e._item.second());
3028 : : if (e._item.second() == INVALID) {
3029 : : e._item.setFirst();
3030 : : _digraph->first(e._item.first());
3031 : : }
3032 : : } else {
3033 : : _digraph->next(e._item.first());
3034 : : }
3035 : : }
3036 : :
3037 : : void firstOut(Arc& e, const Node& n) const {
3038 : : if (n._in) {
3039 : : e._item.setSecond(n);
3040 : : } else {
3041 : : e._item.setFirst();
3042 : : _digraph->firstOut(e._item.first(), n);
3043 : : }
3044 : : }
3045 : :
3046 : : void nextOut(Arc& e) const {
3047 : : if (!e._item.firstState()) {
3048 : : e._item.setFirst(INVALID);
3049 : : } else {
3050 : : _digraph->nextOut(e._item.first());
3051 : : }
3052 : : }
3053 : :
3054 : : void firstIn(Arc& e, const Node& n) const {
3055 : : if (!n._in) {
3056 : : e._item.setSecond(n);
3057 : : } else {
3058 : : e._item.setFirst();
3059 : : _digraph->firstIn(e._item.first(), n);
3060 : : }
3061 : : }
3062 : :
3063 : : void nextIn(Arc& e) const {
3064 : : if (!e._item.firstState()) {
3065 : : e._item.setFirst(INVALID);
3066 : : } else {
3067 : : _digraph->nextIn(e._item.first());
3068 : : }
3069 : : }
3070 : :
3071 : : Node source(const Arc& e) const {
3072 : : if (e._item.firstState()) {
3073 : : return Node(_digraph->source(e._item.first()), false);
3074 : : } else {
3075 : : return Node(e._item.second(), true);
3076 : : }
3077 : : }
3078 : :
3079 : : Node target(const Arc& e) const {
3080 : : if (e._item.firstState()) {
3081 : : return Node(_digraph->target(e._item.first()), true);
3082 : : } else {
3083 : : return Node(e._item.second(), false);
3084 : : }
3085 : : }
3086 : :
3087 : : int id(const Node& n) const {
3088 : : return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
3089 : : }
3090 : : Node nodeFromId(int ix) const {
3091 : : return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
3092 : : }
3093 : : int maxNodeId() const {
3094 : : return 2 * _digraph->maxNodeId() + 1;
3095 : : }
3096 : :
3097 : : int id(const Arc& e) const {
3098 : : if (e._item.firstState()) {
3099 : : return _digraph->id(e._item.first()) << 1;
3100 : : } else {
3101 : : return (_digraph->id(e._item.second()) << 1) | 1;
3102 : : }
3103 : : }
3104 : : Arc arcFromId(int ix) const {
3105 : : if ((ix & 1) == 0) {
3106 : : return Arc(_digraph->arcFromId(ix >> 1));
3107 : : } else {
3108 : : return Arc(_digraph->nodeFromId(ix >> 1));
3109 : : }
3110 : : }
3111 : : int maxArcId() const {
3112 : : return std::max(_digraph->maxNodeId() << 1,
3113 : : (_digraph->maxArcId() << 1) | 1);
3114 : : }
3115 : :
3116 : : static bool inNode(const Node& n) {
3117 : : return n._in;
3118 : : }
3119 : :
3120 : : static bool outNode(const Node& n) {
3121 : : return !n._in;
3122 : : }
3123 : :
3124 : : static bool origArc(const Arc& e) {
3125 : : return e._item.firstState();
3126 : : }
3127 : :
3128 : : static bool bindArc(const Arc& e) {
3129 : : return e._item.secondState();
3130 : : }
3131 : :
3132 : : static Node inNode(const DigraphNode& n) {
3133 : : return Node(n, true);
3134 : : }
3135 : :
3136 : : static Node outNode(const DigraphNode& n) {
3137 : : return Node(n, false);
3138 : : }
3139 : :
3140 : : static Arc arc(const DigraphNode& n) {
3141 : : return Arc(n);
3142 : : }
3143 : :
3144 : : static Arc arc(const DigraphArc& e) {
3145 : : return Arc(e);
3146 : : }
3147 : :
3148 : : typedef True NodeNumTag;
3149 : : int nodeNum() const {
3150 : : return 2 * countNodes(*_digraph);
3151 : : }
3152 : :
3153 : : typedef True ArcNumTag;
3154 : : int arcNum() const {
3155 : : return countArcs(*_digraph) + countNodes(*_digraph);
3156 : : }
3157 : :
3158 : : typedef True FindArcTag;
3159 : : Arc findArc(const Node& u, const Node& v,
3160 : : const Arc& prev = INVALID) const {
3161 : : if (inNode(u) && outNode(v)) {
3162 : : if (static_cast<const DigraphNode&>(u) ==
3163 : : static_cast<const DigraphNode&>(v) && prev == INVALID) {
3164 : : return Arc(u);
3165 : : }
3166 : : }
3167 : : else if (outNode(u) && inNode(v)) {
3168 : : return Arc(::lemon::findArc(*_digraph, u, v, prev));
3169 : : }
3170 : : return INVALID;
3171 : : }
3172 : :
3173 : : private:
3174 : :
3175 : : template <typename V>
3176 : : class NodeMapBase
3177 : : : public MapTraits<typename Parent::template NodeMap<V> > {
3178 : : typedef typename Parent::template NodeMap<V> NodeImpl;
3179 : : public:
3180 : : typedef Node Key;
3181 : : typedef V Value;
3182 : : typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
3183 : : typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
3184 : : typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
3185 : : typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
3186 : : typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
3187 : :
3188 : : NodeMapBase(const SplitNodesBase<DGR>& adaptor)
3189 : : : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
3190 : : NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
3191 : : : _in_map(*adaptor._digraph, value),
3192 : : _out_map(*adaptor._digraph, value) {}
3193 : :
3194 : : void set(const Node& key, const V& val) {
3195 : : if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
3196 : : else {_out_map.set(key, val); }
3197 : : }
3198 : :
3199 : : ReturnValue operator[](const Node& key) {
3200 : : if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
3201 : : else { return _out_map[key]; }
3202 : : }
3203 : :
3204 : : ConstReturnValue operator[](const Node& key) const {
3205 : : if (Adaptor::inNode(key)) { return _in_map[key]; }
3206 : : else { return _out_map[key]; }
3207 : : }
3208 : :
3209 : : private:
3210 : : NodeImpl _in_map, _out_map;
3211 : : };
3212 : :
3213 : : template <typename V>
3214 : : class ArcMapBase
3215 : : : public MapTraits<typename Parent::template ArcMap<V> > {
3216 : : typedef typename Parent::template ArcMap<V> ArcImpl;
3217 : : typedef typename Parent::template NodeMap<V> NodeImpl;
3218 : : public:
3219 : : typedef Arc Key;
3220 : : typedef V Value;
3221 : : typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
3222 : : typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
3223 : : typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
3224 : : typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
3225 : : typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
3226 : :
3227 : : ArcMapBase(const SplitNodesBase<DGR>& adaptor)
3228 : : : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
3229 : : ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
3230 : : : _arc_map(*adaptor._digraph, value),
3231 : : _node_map(*adaptor._digraph, value) {}
3232 : :
3233 : : void set(const Arc& key, const V& val) {
3234 : : if (SplitNodesBase<DGR>::origArc(key)) {
3235 : : _arc_map.set(static_cast<const DigraphArc&>(key), val);
3236 : : } else {
3237 : : _node_map.set(static_cast<const DigraphNode&>(key), val);
3238 : : }
3239 : : }
3240 : :
3241 : : ReturnValue operator[](const Arc& key) {
3242 : : if (SplitNodesBase<DGR>::origArc(key)) {
3243 : : return _arc_map[static_cast<const DigraphArc&>(key)];
3244 : : } else {
3245 : : return _node_map[static_cast<const DigraphNode&>(key)];
3246 : : }
3247 : : }
3248 : :
3249 : : ConstReturnValue operator[](const Arc& key) const {
3250 : : if (SplitNodesBase<DGR>::origArc(key)) {
3251 : : return _arc_map[static_cast<const DigraphArc&>(key)];
3252 : : } else {
3253 : : return _node_map[static_cast<const DigraphNode&>(key)];
3254 : : }
3255 : : }
3256 : :
3257 : : private:
3258 : : ArcImpl _arc_map;
3259 : : NodeImpl _node_map;
3260 : : };
3261 : :
3262 : : public:
3263 : :
3264 : : template <typename V>
3265 : : class NodeMap
3266 : : : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
3267 : : typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
3268 : :
3269 : : public:
3270 : : typedef V Value;
3271 : :
3272 : : NodeMap(const SplitNodesBase<DGR>& adaptor)
3273 : : : Parent(adaptor) {}
3274 : :
3275 : : NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
3276 : : : Parent(adaptor, value) {}
3277 : :
3278 : : private:
3279 : : NodeMap& operator=(const NodeMap& cmap) {
3280 : : return operator=<NodeMap>(cmap);
3281 : : }
3282 : :
3283 : : template <typename CMap>
3284 : : NodeMap& operator=(const CMap& cmap) {
3285 : : Parent::operator=(cmap);
3286 : : return *this;
3287 : : }
3288 : : };
3289 : :
3290 : : template <typename V>
3291 : : class ArcMap
3292 : : : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
3293 : : typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
3294 : :
3295 : : public:
3296 : : typedef V Value;
3297 : :
3298 : : ArcMap(const SplitNodesBase<DGR>& adaptor)
3299 : : : Parent(adaptor) {}
3300 : :
3301 : : ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
3302 : : : Parent(adaptor, value) {}
3303 : :
3304 : : private:
3305 : : ArcMap& operator=(const ArcMap& cmap) {
3306 : : return operator=<ArcMap>(cmap);
3307 : : }
3308 : :
3309 : : template <typename CMap>
3310 : : ArcMap& operator=(const CMap& cmap) {
3311 : : Parent::operator=(cmap);
3312 : : return *this;
3313 : : }
3314 : : };
3315 : :
3316 : : protected:
3317 : :
3318 : : SplitNodesBase() : _digraph(0) {}
3319 : :
3320 : : DGR* _digraph;
3321 : :
3322 : : void initialize(Digraph& digraph) {
3323 : : _digraph = &digraph;
3324 : : }
3325 : :
3326 : : };
3327 : :
3328 : : /// \ingroup graph_adaptors
3329 : : ///
3330 : : /// \brief Adaptor class for splitting the nodes of a digraph.
3331 : : ///
3332 : : /// SplitNodes adaptor can be used for splitting each node into an
3333 : : /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
3334 : : /// replaces each node \f$ u \f$ in the digraph with two nodes,
3335 : : /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
3336 : : /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
3337 : : /// new target of the arc will be \f$ u_{in} \f$ and similarly the
3338 : : /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
3339 : : /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
3340 : : /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
3341 : : ///
3342 : : /// The aim of this class is running an algorithm with respect to node
3343 : : /// costs or capacities if the algorithm considers only arc costs or
3344 : : /// capacities directly.
3345 : : /// In this case you can use \c SplitNodes adaptor, and set the node
3346 : : /// costs/capacities of the original digraph to the \e bind \e arcs
3347 : : /// in the adaptor.
3348 : : ///
3349 : : /// This class provides item counting in the same time as the adapted
3350 : : /// digraph structure.
3351 : : ///
3352 : : /// \tparam DGR The type of the adapted digraph.
3353 : : /// It must conform to the \ref concepts::Digraph "Digraph" concept.
3354 : : /// It is implicitly \c const.
3355 : : ///
3356 : : /// \note The \c Node type of this adaptor is converible to the \c Node
3357 : : /// type of the adapted digraph.
3358 : : template <typename DGR>
3359 : : #ifdef DOXYGEN
3360 : : class SplitNodes {
3361 : : #else
3362 : : class SplitNodes
3363 : : : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
3364 : : #endif
3365 : : typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
3366 : :
3367 : : public:
3368 : : typedef DGR Digraph;
3369 : :
3370 : : typedef typename DGR::Node DigraphNode;
3371 : : typedef typename DGR::Arc DigraphArc;
3372 : :
3373 : : typedef typename Parent::Node Node;
3374 : : typedef typename Parent::Arc Arc;
3375 : :
3376 : : /// \brief Constructor
3377 : : ///
3378 : : /// Constructor of the adaptor.
3379 : : SplitNodes(const DGR& g) {
3380 : : Parent::initialize(g);
3381 : : }
3382 : :
3383 : : /// \brief Returns \c true if the given node is an in-node.
3384 : : ///
3385 : : /// Returns \c true if the given node is an in-node.
3386 : : static bool inNode(const Node& n) {
3387 : : return Parent::inNode(n);
3388 : : }
3389 : :
3390 : : /// \brief Returns \c true if the given node is an out-node.
3391 : : ///
3392 : : /// Returns \c true if the given node is an out-node.
3393 : : static bool outNode(const Node& n) {
3394 : : return Parent::outNode(n);
3395 : : }
3396 : :
3397 : : /// \brief Returns \c true if the given arc is an original arc.
3398 : : ///
3399 : : /// Returns \c true if the given arc is one of the arcs in the
3400 : : /// original digraph.
3401 : : static bool origArc(const Arc& a) {
3402 : : return Parent::origArc(a);
3403 : : }
3404 : :
3405 : : /// \brief Returns \c true if the given arc is a bind arc.
3406 : : ///
3407 : : /// Returns \c true if the given arc is a bind arc, i.e. it connects
3408 : : /// an in-node and an out-node.
3409 : : static bool bindArc(const Arc& a) {
3410 : : return Parent::bindArc(a);
3411 : : }
3412 : :
3413 : : /// \brief Returns the in-node created from the given original node.
3414 : : ///
3415 : : /// Returns the in-node created from the given original node.
3416 : : static Node inNode(const DigraphNode& n) {
3417 : : return Parent::inNode(n);
3418 : : }
3419 : :
3420 : : /// \brief Returns the out-node created from the given original node.
3421 : : ///
3422 : : /// Returns the out-node created from the given original node.
3423 : : static Node outNode(const DigraphNode& n) {
3424 : : return Parent::outNode(n);
3425 : : }
3426 : :
3427 : : /// \brief Returns the bind arc that corresponds to the given
3428 : : /// original node.
3429 : : ///
3430 : : /// Returns the bind arc in the adaptor that corresponds to the given
3431 : : /// original node, i.e. the arc connecting the in-node and out-node
3432 : : /// of \c n.
3433 : : static Arc arc(const DigraphNode& n) {
3434 : : return Parent::arc(n);
3435 : : }
3436 : :
3437 : : /// \brief Returns the arc that corresponds to the given original arc.
3438 : : ///
3439 : : /// Returns the arc in the adaptor that corresponds to the given
3440 : : /// original arc.
3441 : : static Arc arc(const DigraphArc& a) {
3442 : : return Parent::arc(a);
3443 : : }
3444 : :
3445 : : /// \brief Node map combined from two original node maps
3446 : : ///
3447 : : /// This map adaptor class adapts two node maps of the original digraph
3448 : : /// to get a node map of the split digraph.
3449 : : /// Its value type is inherited from the first node map type (\c IN).
3450 : : /// \tparam IN The type of the node map for the in-nodes.
3451 : : /// \tparam OUT The type of the node map for the out-nodes.
3452 : : template <typename IN, typename OUT>
3453 : : class CombinedNodeMap {
3454 : : public:
3455 : :
3456 : : /// The key type of the map
3457 : : typedef Node Key;
3458 : : /// The value type of the map
3459 : : typedef typename IN::Value Value;
3460 : :
3461 : : typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
3462 : : typedef typename MapTraits<IN>::ReturnValue ReturnValue;
3463 : : typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
3464 : : typedef typename MapTraits<IN>::ReturnValue Reference;
3465 : : typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
3466 : :
3467 : : /// Constructor
3468 : : CombinedNodeMap(IN& in_map, OUT& out_map)
3469 : : : _in_map(in_map), _out_map(out_map) {}
3470 : :
3471 : : /// Returns the value associated with the given key.
3472 : : Value operator[](const Key& key) const {
3473 : : if (SplitNodesBase<const DGR>::inNode(key)) {
3474 : : return _in_map[key];
3475 : : } else {
3476 : : return _out_map[key];
3477 : : }
3478 : : }
3479 : :
3480 : : /// Returns a reference to the value associated with the given key.
3481 : : Value& operator[](const Key& key) {
3482 : : if (SplitNodesBase<const DGR>::inNode(key)) {
3483 : : return _in_map[key];
3484 : : } else {
3485 : : return _out_map[key];
3486 : : }
3487 : : }
3488 : :
3489 : : /// Sets the value associated with the given key.
3490 : : void set(const Key& key, const Value& value) {
3491 : : if (SplitNodesBase<const DGR>::inNode(key)) {
3492 : : _in_map.set(key, value);
3493 : : } else {
3494 : : _out_map.set(key, value);
3495 : : }
3496 : : }
3497 : :
3498 : : private:
3499 : :
3500 : : IN& _in_map;
3501 : : OUT& _out_map;
3502 : :
3503 : : };
3504 : :
3505 : :
3506 : : /// \brief Returns a combined node map
3507 : : ///
3508 : : /// This function just returns a combined node map.
3509 : : template <typename IN, typename OUT>
3510 : : static CombinedNodeMap<IN, OUT>
3511 : : combinedNodeMap(IN& in_map, OUT& out_map) {
3512 : : return CombinedNodeMap<IN, OUT>(in_map, out_map);
3513 : : }
3514 : :
3515 : : template <typename IN, typename OUT>
3516 : : static CombinedNodeMap<const IN, OUT>
3517 : : combinedNodeMap(const IN& in_map, OUT& out_map) {
3518 : : return CombinedNodeMap<const IN, OUT>(in_map, out_map);
3519 : : }
3520 : :
3521 : : template <typename IN, typename OUT>
3522 : : static CombinedNodeMap<IN, const OUT>
3523 : : combinedNodeMap(IN& in_map, const OUT& out_map) {
3524 : : return CombinedNodeMap<IN, const OUT>(in_map, out_map);
3525 : : }
3526 : :
3527 : : template <typename IN, typename OUT>
3528 : : static CombinedNodeMap<const IN, const OUT>
3529 : : combinedNodeMap(const IN& in_map, const OUT& out_map) {
3530 : : return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
3531 : : }
3532 : :
3533 : : /// \brief Arc map combined from an arc map and a node map of the
3534 : : /// original digraph.
3535 : : ///
3536 : : /// This map adaptor class adapts an arc map and a node map of the
3537 : : /// original digraph to get an arc map of the split digraph.
3538 : : /// Its value type is inherited from the original arc map type (\c AM).
3539 : : /// \tparam AM The type of the arc map.
3540 : : /// \tparam NM the type of the node map.
3541 : : template <typename AM, typename NM>
3542 : : class CombinedArcMap {
3543 : : public:
3544 : :
3545 : : /// The key type of the map
3546 : : typedef Arc Key;
3547 : : /// The value type of the map
3548 : : typedef typename AM::Value Value;
3549 : :
3550 : : typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
3551 : : typedef typename MapTraits<AM>::ReturnValue ReturnValue;
3552 : : typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
3553 : : typedef typename MapTraits<AM>::ReturnValue Reference;
3554 : : typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
3555 : :
3556 : : /// Constructor
3557 : : CombinedArcMap(AM& arc_map, NM& node_map)
3558 : : : _arc_map(arc_map), _node_map(node_map) {}
3559 : :
3560 : : /// Returns the value associated with the given key.
3561 : : Value operator[](const Key& arc) const {
3562 : : if (SplitNodesBase<const DGR>::origArc(arc)) {
3563 : : return _arc_map[arc];
3564 : : } else {
3565 : : return _node_map[arc];
3566 : : }
3567 : : }
3568 : :
3569 : : /// Returns a reference to the value associated with the given key.
3570 : : Value& operator[](const Key& arc) {
3571 : : if (SplitNodesBase<const DGR>::origArc(arc)) {
3572 : : return _arc_map[arc];
3573 : : } else {
3574 : : return _node_map[arc];
3575 : : }
3576 : : }
3577 : :
3578 : : /// Sets the value associated with the given key.
3579 : : void set(const Arc& arc, const Value& val) {
3580 : : if (SplitNodesBase<const DGR>::origArc(arc)) {
3581 : : _arc_map.set(arc, val);
3582 : : } else {
3583 : : _node_map.set(arc, val);
3584 : : }
3585 : : }
3586 : :
3587 : : private:
3588 : :
3589 : : AM& _arc_map;
3590 : : NM& _node_map;
3591 : :
3592 : : };
3593 : :
3594 : : /// \brief Returns a combined arc map
3595 : : ///
3596 : : /// This function just returns a combined arc map.
3597 : : template <typename ArcMap, typename NodeMap>
3598 : : static CombinedArcMap<ArcMap, NodeMap>
3599 : : combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
3600 : : return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
3601 : : }
3602 : :
3603 : : template <typename ArcMap, typename NodeMap>
3604 : : static CombinedArcMap<const ArcMap, NodeMap>
3605 : : combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
3606 : : return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
3607 : : }
3608 : :
3609 : : template <typename ArcMap, typename NodeMap>
3610 : : static CombinedArcMap<ArcMap, const NodeMap>
3611 : : combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
3612 : : return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
3613 : : }
3614 : :
3615 : : template <typename ArcMap, typename NodeMap>
3616 : : static CombinedArcMap<const ArcMap, const NodeMap>
3617 : : combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
3618 : : return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
3619 : : }
3620 : :
3621 : : };
3622 : :
3623 : : /// \brief Returns a (read-only) SplitNodes adaptor
3624 : : ///
3625 : : /// This function just returns a (read-only) \ref SplitNodes adaptor.
3626 : : /// \ingroup graph_adaptors
3627 : : /// \relates SplitNodes
3628 : : template<typename DGR>
3629 : : SplitNodes<DGR>
3630 : : splitNodes(const DGR& digraph) {
3631 : : return SplitNodes<DGR>(digraph);
3632 : : }
3633 : :
3634 : : #undef LEMON_SCOPE_FIX
3635 : :
3636 : : } //namespace lemon
3637 : :
3638 : : #endif //LEMON_ADAPTORS_H
|
