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