COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/adaptors.h @ 448:9d9990909fc8

Last change on this file since 448:9d9990909fc8 was 448:9d9990909fc8, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Add missing const keywords (+ remove misleading ones) (#67)

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