COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/digraph_adaptor.h @ 415:4b6112235fad

Last change on this file since 415:4b6112235fad was 415:4b6112235fad, checked in by Balazs Dezso <deba@…>, 12 years ago

Improvements in graph adaptors (#67)

Remove DigraphAdaptor? and GraphAdaptor?
Remove docs of base classes
Move the member documentations to real adaptors
Minor improvements in documentation

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