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