src/lemon/graph_wrapper.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1164 80bb73097736
child 1198 6f1604392dc8
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
alpar@906
     1
/* -*- C++ -*-
alpar@921
     2
 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@906
    16
alpar@921
    17
#ifndef LEMON_GRAPH_WRAPPER_H
alpar@921
    18
#define LEMON_GRAPH_WRAPPER_H
marci@556
    19
marci@556
    20
///\ingroup gwrappers
marci@556
    21
///\file
marci@556
    22
///\brief Several graph wrappers.
marci@556
    23
///
marci@556
    24
///This file contains several useful graph wrapper functions.
marci@556
    25
///
marci@556
    26
///\author Marton Makai
marci@556
    27
alpar@921
    28
#include <lemon/invalid.h>
alpar@921
    29
#include <lemon/maps.h>
marci@992
    30
#include <lemon/iterable_graph_extender.h>
alpar@774
    31
#include <iostream>
marci@556
    32
alpar@921
    33
namespace lemon {
marci@556
    34
marci@556
    35
  // Graph wrappers
marci@556
    36
marci@1172
    37
  /*!
marci@1004
    38
    \addtogroup gwrappers
marci@1004
    39
    @{
marci@1172
    40
   */
marci@556
    41
marci@1172
    42
  /*! 
marci@1004
    43
    Base type for the Graph Wrappers
marci@556
    44
marci@1004
    45
    \warning Graph wrappers are in even more experimental state than the other
marci@1004
    46
    parts of the lib. Use them at you own risk.
marci@1004
    47
  
marci@1004
    48
    This is the base type for most of LEMON graph wrappers. 
marci@1004
    49
    This class implements a trivial graph wrapper i.e. it only wraps the 
marci@1004
    50
    functions and types of the graph. The purpose of this class is to 
marci@1004
    51
    make easier implementing graph wrappers. E.g. if a wrapper is 
marci@1004
    52
    considered which differs from the wrapped graph only in some of its 
marci@1004
    53
    functions or types, then it can be derived from GraphWrapper, and only the 
marci@1004
    54
    differences should be implemented.
marci@1004
    55
  
marci@1004
    56
    \author Marton Makai 
marci@1004
    57
  */
marci@970
    58
  template<typename _Graph>
marci@970
    59
  class GraphWrapperBase {
marci@970
    60
  public:
marci@970
    61
    typedef _Graph Graph;
marci@970
    62
    /// \todo Is it needed?
marci@970
    63
    typedef Graph BaseGraph;
marci@970
    64
    typedef Graph ParentGraph;
marci@970
    65
marci@556
    66
  protected:
marci@556
    67
    Graph* graph;
marci@970
    68
    GraphWrapperBase() : graph(0) { }
marci@556
    69
    void setGraph(Graph& _graph) { graph=&_graph; }
marci@556
    70
marci@556
    71
  public:
marci@970
    72
    GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
marci@556
    73
 
alpar@774
    74
    typedef typename Graph::Node Node;
alpar@774
    75
    typedef typename Graph::Edge Edge;
marci@556
    76
   
marci@970
    77
    void first(Node& i) const { graph->first(i); }
marci@970
    78
    void first(Edge& i) const { graph->first(i); }
marci@970
    79
    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970
    80
    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556
    81
marci@970
    82
    void next(Node& i) const { graph->next(i); }
marci@970
    83
    void next(Edge& i) const { graph->next(i); }
marci@970
    84
    void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970
    85
    void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970
    86
alpar@986
    87
    Node source(const Edge& e) const { return graph->source(e); }
alpar@986
    88
    Node target(const Edge& e) const { return graph->target(e); }
marci@556
    89
marci@556
    90
    int nodeNum() const { return graph->nodeNum(); }
marci@556
    91
    int edgeNum() const { return graph->edgeNum(); }
marci@556
    92
  
marci@556
    93
    Node addNode() const { return Node(graph->addNode()); }
alpar@986
    94
    Edge addEdge(const Node& source, const Node& target) const { 
alpar@986
    95
      return Edge(graph->addEdge(source, target)); }
marci@556
    96
marci@556
    97
    void erase(const Node& i) const { graph->erase(i); }
marci@556
    98
    void erase(const Edge& i) const { graph->erase(i); }
marci@556
    99
  
marci@556
   100
    void clear() const { graph->clear(); }
marci@556
   101
    
alpar@736
   102
    bool forward(const Edge& e) const { return graph->forward(e); }
alpar@736
   103
    bool backward(const Edge& e) const { return graph->backward(e); }
marci@739
   104
marci@739
   105
    int id(const Node& v) const { return graph->id(v); }
marci@739
   106
    int id(const Edge& e) const { return graph->id(e); }
marci@650
   107
    
marci@738
   108
    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
marci@650
   109
marci@970
   110
    template <typename _Value>
marci@970
   111
    class NodeMap : public _Graph::template NodeMap<_Value> {
marci@970
   112
    public:
marci@970
   113
      typedef typename _Graph::template NodeMap<_Value> Parent;
marci@970
   114
      NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
marci@970
   115
      NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
marci@970
   116
      : Parent(*gw.graph, value) { }
marci@970
   117
    };
marci@556
   118
marci@970
   119
    template <typename _Value>
marci@970
   120
    class EdgeMap : public _Graph::template EdgeMap<_Value> {
marci@970
   121
    public:
marci@970
   122
      typedef typename _Graph::template EdgeMap<_Value> Parent;
marci@970
   123
      EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
marci@970
   124
      EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
marci@970
   125
      : Parent(*gw.graph, value) { }
marci@970
   126
    };
deba@877
   127
marci@556
   128
  };
marci@556
   129
marci@970
   130
  template <typename _Graph>
marci@970
   131
  class GraphWrapper :
marci@970
   132
    public IterableGraphExtender<GraphWrapperBase<_Graph> > { 
marci@970
   133
  public:
marci@970
   134
    typedef _Graph Graph;
marci@970
   135
    typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
marci@970
   136
  protected:
marci@970
   137
    GraphWrapper() : Parent() { }
marci@569
   138
marci@970
   139
  public:
marci@970
   140
    GraphWrapper(Graph& _graph) { setGraph(_graph); }
marci@970
   141
  };
marci@569
   142
marci@997
   143
  template <typename _Graph>
marci@997
   144
  class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@997
   145
  public:
marci@997
   146
    typedef _Graph Graph;
marci@997
   147
    typedef GraphWrapperBase<_Graph> Parent;
marci@997
   148
  protected:
marci@997
   149
    RevGraphWrapperBase() : Parent() { }
marci@997
   150
  public:
marci@997
   151
    typedef typename Parent::Node Node;
marci@997
   152
    typedef typename Parent::Edge Edge;
marci@997
   153
marci@997
   154
    using Parent::first;
marci@997
   155
    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997
   156
    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997
   157
marci@997
   158
    using Parent::next;
marci@997
   159
    void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997
   160
    void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997
   161
marci@997
   162
    Node source(const Edge& e) const { return Parent::target(e); }
marci@997
   163
    Node target(const Edge& e) const { return Parent::source(e); }
marci@997
   164
  };
marci@997
   165
    
marci@997
   166
marci@556
   167
  /// A graph wrapper which reverses the orientation of the edges.
marci@556
   168
alpar@879
   169
  ///\warning Graph wrappers are in even more experimental state than the other
alpar@879
   170
  ///parts of the lib. Use them at you own risk.
alpar@879
   171
  ///
marci@923
   172
  /// Let \f$G=(V, A)\f$ be a directed graph and 
marci@923
   173
  /// suppose that a graph instange \c g of type 
marci@923
   174
  /// \c ListGraph implements \f$G\f$.
marci@923
   175
  /// \code
marci@923
   176
  /// ListGraph g;
marci@923
   177
  /// \endcode
marci@923
   178
  /// For each directed edge 
marci@923
   179
  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 
marci@923
   180
  /// reversing its orientation. 
marci@923
   181
  /// Then RevGraphWrapper implements the graph structure with node-set 
marci@923
   182
  /// \f$V\f$ and edge-set 
marci@923
   183
  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 
marci@923
   184
  /// reversing the orientation of its edges. The following code shows how 
marci@923
   185
  /// such an instance can be constructed.
marci@923
   186
  /// \code
marci@923
   187
  /// RevGraphWrapper<ListGraph> gw(g);
marci@923
   188
  /// \endcode
marci@556
   189
  ///\author Marton Makai
marci@997
   190
  template<typename _Graph>
marci@997
   191
  class RevGraphWrapper : 
marci@997
   192
    public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
marci@650
   193
  public:
marci@997
   194
    typedef _Graph Graph;
marci@997
   195
    typedef IterableGraphExtender<
marci@997
   196
      RevGraphWrapperBase<_Graph> > Parent;
marci@556
   197
  protected:
marci@997
   198
    RevGraphWrapper() { }
marci@556
   199
  public:
marci@997
   200
    RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
marci@997
   201
  };
marci@556
   202
marci@992
   203
  
marci@992
   204
  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
marci@992
   205
  class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@992
   206
  public:
marci@992
   207
    typedef _Graph Graph;
marci@992
   208
    typedef GraphWrapperBase<_Graph> Parent;
marci@992
   209
  protected:
marci@992
   210
    NodeFilterMap* node_filter_map;
marci@992
   211
    EdgeFilterMap* edge_filter_map;
marci@992
   212
    SubGraphWrapperBase() : Parent(), 
marci@992
   213
			    node_filter_map(0), edge_filter_map(0) { }
marci@775
   214
marci@992
   215
    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992
   216
      node_filter_map=&_node_filter_map;
marci@992
   217
    }
marci@992
   218
    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992
   219
      edge_filter_map=&_edge_filter_map;
marci@992
   220
    }
marci@992
   221
marci@992
   222
  public:
marci@992
   223
//     SubGraphWrapperBase(Graph& _graph, 
marci@992
   224
// 			NodeFilterMap& _node_filter_map, 
marci@992
   225
// 			EdgeFilterMap& _edge_filter_map) : 
marci@992
   226
//       Parent(&_graph), 
marci@992
   227
//       node_filter_map(&node_filter_map), 
marci@992
   228
//       edge_filter_map(&edge_filter_map) { }
marci@992
   229
marci@992
   230
    typedef typename Parent::Node Node;
marci@992
   231
    typedef typename Parent::Edge Edge;
marci@992
   232
marci@992
   233
    void first(Node& i) const { 
marci@992
   234
      Parent::first(i); 
marci@992
   235
      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
marci@992
   236
    }
marci@992
   237
    void first(Edge& i) const { 
marci@992
   238
      Parent::first(i); 
marci@992
   239
      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
marci@992
   240
    }
marci@992
   241
    void firstIn(Edge& i, const Node& n) const { 
marci@992
   242
      Parent::firstIn(i, n); 
marci@992
   243
      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
marci@992
   244
    }
marci@992
   245
    void firstOut(Edge& i, const Node& n) const { 
marci@992
   246
      Parent::firstOut(i, n); 
marci@992
   247
      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
marci@992
   248
    }
marci@992
   249
marci@992
   250
    void next(Node& i) const { 
marci@992
   251
      Parent::next(i); 
marci@992
   252
      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
marci@992
   253
    }
marci@992
   254
    void next(Edge& i) const { 
marci@992
   255
      Parent::next(i); 
marci@992
   256
      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
marci@992
   257
    }
marci@992
   258
    void nextIn(Edge& i) const { 
marci@992
   259
      Parent::nextIn(i); 
marci@992
   260
      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
marci@992
   261
    }
marci@992
   262
    void nextOut(Edge& i) const { 
marci@992
   263
      Parent::nextOut(i); 
marci@992
   264
      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
marci@992
   265
    }
marci@992
   266
marci@992
   267
    /// This function hides \c n in the graph, i.e. the iteration 
marci@992
   268
    /// jumps over it. This is done by simply setting the value of \c n  
marci@992
   269
    /// to be false in the corresponding node-map.
marci@992
   270
    void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992
   271
marci@992
   272
    /// This function hides \c e in the graph, i.e. the iteration 
marci@992
   273
    /// jumps over it. This is done by simply setting the value of \c e  
marci@992
   274
    /// to be false in the corresponding edge-map.
marci@992
   275
    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992
   276
marci@992
   277
    /// The value of \c n is set to be true in the node-map which stores 
marci@992
   278
    /// hide information. If \c n was hidden previuosly, then it is shown 
marci@992
   279
    /// again
marci@992
   280
     void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992
   281
marci@992
   282
    /// The value of \c e is set to be true in the edge-map which stores 
marci@992
   283
    /// hide information. If \c e was hidden previuosly, then it is shown 
marci@992
   284
    /// again
marci@992
   285
    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992
   286
marci@992
   287
    /// Returns true if \c n is hidden.
marci@992
   288
    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992
   289
marci@992
   290
    /// Returns true if \c n is hidden.
marci@992
   291
    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992
   292
marci@992
   293
    /// \warning This is a linear time operation and works only if s
marci@992
   294
    /// \c Graph::NodeIt is defined.
marci@992
   295
    /// \todo assign tags.
marci@992
   296
    int nodeNum() const { 
marci@992
   297
      int i=0;
marci@992
   298
      Node n;
marci@992
   299
      for (first(n); n!=INVALID; next(n)) ++i;
marci@992
   300
      return i; 
marci@992
   301
    }
marci@992
   302
marci@992
   303
    /// \warning This is a linear time operation and works only if 
marci@992
   304
    /// \c Graph::EdgeIt is defined.
marci@992
   305
    /// \todo assign tags.
marci@992
   306
    int edgeNum() const { 
marci@992
   307
      int i=0;
marci@992
   308
      Edge e;
marci@992
   309
      for (first(e); e!=INVALID; next(e)) ++i;
marci@992
   310
      return i; 
marci@992
   311
    }
marci@992
   312
marci@992
   313
marci@992
   314
  };
marci@775
   315
marci@930
   316
  /*! \brief A graph wrapper for hiding nodes and edges from a graph.
marci@556
   317
  
marci@930
   318
  \warning Graph wrappers are in even more experimental state than the other
marci@930
   319
  parts of the lib. Use them at you own risk.
marci@930
   320
  
marci@930
   321
  This wrapper shows a graph with filtered node-set and 
marci@930
   322
  edge-set. 
marci@930
   323
  Given a bool-valued map on the node-set and one on 
marci@930
   324
  the edge-set of the graph, the iterators show only the objects 
marci@930
   325
  having true value. We have to note that this does not mean that an 
marci@930
   326
  induced subgraph is obtained, the node-iterator cares only the filter 
marci@930
   327
  on the node-set, and the edge-iterators care only the filter on the 
marci@930
   328
  edge-set.
marci@930
   329
  \code
marci@930
   330
  typedef SmartGraph Graph;
marci@930
   331
  Graph g;
marci@930
   332
  typedef Graph::Node Node;
marci@930
   333
  typedef Graph::Edge Edge;
marci@930
   334
  Node u=g.addNode(); //node of id 0
marci@930
   335
  Node v=g.addNode(); //node of id 1
marci@930
   336
  Node e=g.addEdge(u, v); //edge of id 0
marci@930
   337
  Node f=g.addEdge(v, u); //edge of id 1
marci@930
   338
  Graph::NodeMap<bool> nm(g, true);
marci@930
   339
  nm.set(u, false);
marci@930
   340
  Graph::EdgeMap<bool> em(g, true);
marci@930
   341
  em.set(e, false);
marci@930
   342
  typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
marci@930
   343
  SubGW gw(g, nm, em);
marci@930
   344
  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
marci@930
   345
  std::cout << ":-)" << std::endl;
marci@930
   346
  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
marci@930
   347
  \endcode
marci@930
   348
  The output of the above code is the following.
marci@930
   349
  \code
marci@930
   350
  1
marci@930
   351
  :-)
marci@930
   352
  1
marci@930
   353
  \endcode
marci@930
   354
  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
marci@930
   355
  \c Graph::Node that is why \c g.id(n) can be applied.
marci@930
   356
marci@933
   357
  For other examples see also the documentation of NodeSubGraphWrapper and 
marci@933
   358
  EdgeSubGraphWrapper.
marci@930
   359
marci@930
   360
  \author Marton Makai
marci@930
   361
  */
marci@992
   362
  template<typename _Graph, typename NodeFilterMap, 
marci@556
   363
	   typename EdgeFilterMap>
marci@992
   364
  class SubGraphWrapper : 
marci@992
   365
    public IterableGraphExtender<
marci@992
   366
    SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
marci@650
   367
  public:
marci@992
   368
    typedef _Graph Graph;
marci@992
   369
    typedef IterableGraphExtender<
marci@992
   370
      SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
marci@556
   371
  protected:
marci@992
   372
    SubGraphWrapper() { }
marci@992
   373
  public:
marci@992
   374
    SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map, 
marci@992
   375
		    EdgeFilterMap& _edge_filter_map) { 
marci@992
   376
      setGraph(_graph);
marci@992
   377
      setNodeFilterMap(_node_filter_map);
marci@992
   378
      setEdgeFilterMap(_edge_filter_map);
marci@992
   379
    }
marci@992
   380
  };
marci@556
   381
marci@556
   382
marci@569
   383
marci@933
   384
  /*! \brief A wrapper for hiding nodes from a graph.
marci@933
   385
marci@933
   386
  \warning Graph wrappers are in even more experimental state than the other
marci@933
   387
  parts of the lib. Use them at you own risk.
marci@933
   388
  
marci@933
   389
  A wrapper for hiding nodes from a graph.
marci@933
   390
  This wrapper specializes SubGraphWrapper in the way that only the node-set 
marci@933
   391
  can be filtered. Note that this does not mean of considering induced 
marci@933
   392
  subgraph, the edge-iterators consider the original edge-set.
marci@933
   393
  \author Marton Makai
marci@933
   394
  */
marci@933
   395
  template<typename Graph, typename NodeFilterMap>
marci@933
   396
  class NodeSubGraphWrapper : 
marci@933
   397
    public SubGraphWrapper<Graph, NodeFilterMap, 
marci@933
   398
			   ConstMap<typename Graph::Edge,bool> > {
marci@933
   399
  public:
marci@933
   400
    typedef SubGraphWrapper<Graph, NodeFilterMap, 
marci@933
   401
			    ConstMap<typename Graph::Edge,bool> > Parent;
marci@933
   402
  protected:
marci@933
   403
    ConstMap<typename Graph::Edge, bool> const_true_map;
marci@933
   404
  public:
marci@933
   405
    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : 
marci@933
   406
      Parent(), const_true_map(true) { 
marci@933
   407
      Parent::setGraph(_graph);
marci@933
   408
      Parent::setNodeFilterMap(_node_filter_map);
marci@933
   409
      Parent::setEdgeFilterMap(const_true_map);
marci@933
   410
    }
marci@933
   411
  };
marci@933
   412
marci@933
   413
marci@932
   414
  /*! \brief A wrapper for hiding edges from a graph.
marci@932
   415
marci@932
   416
  \warning Graph wrappers are in even more experimental state than the other
marci@932
   417
  parts of the lib. Use them at you own risk.
marci@932
   418
  
marci@932
   419
  A wrapper for hiding edges from a graph.
marci@932
   420
  This wrapper specializes SubGraphWrapper in the way that only the edge-set 
marci@933
   421
  can be filtered. The usefulness of this wrapper is demonstrated in the 
marci@933
   422
  problem of searching a maximum number of edge-disjoint shortest paths 
marci@933
   423
  between 
marci@933
   424
  two nodes \c s and \c t. Shortest here means being shortest w.r.t. 
marci@933
   425
  non-negative edge-lengths. Note that 
marci@933
   426
  the comprehension of the presented solution 
marci@933
   427
  need's some knowledge from elementary combinatorial optimization. 
marci@933
   428
marci@933
   429
  If a single shortest path is to be 
marci@933
   430
  searched between two nodes \c s and \c t, then this can be done easily by 
marci@933
   431
  applying the Dijkstra algorithm class. What happens, if a maximum number of 
marci@933
   432
  edge-disjoint shortest paths is to be computed. It can be proved that an 
marci@933
   433
  edge can be in a shortest path if and only if it is tight with respect to 
marci@933
   434
  the potential function computed by Dijkstra. Moreover, any path containing 
marci@933
   435
  only such edges is a shortest one. Thus we have to compute a maximum number 
marci@933
   436
  of edge-disjoint paths between \c s and \c t in the graph which has edge-set 
marci@933
   437
  all the tight edges. The computation will be demonstrated on the following 
marci@933
   438
  graph, which is read from a dimacs file.
marci@933
   439
  
marci@933
   440
  \dot
marci@933
   441
  digraph lemon_dot_example {
marci@933
   442
  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933
   443
  n0 [ label="0 (s)" ];
marci@933
   444
  n1 [ label="1" ];
marci@933
   445
  n2 [ label="2" ];
marci@933
   446
  n3 [ label="3" ];
marci@933
   447
  n4 [ label="4" ];
marci@933
   448
  n5 [ label="5" ];
marci@933
   449
  n6 [ label="6 (t)" ];
marci@933
   450
  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933
   451
  n5 ->  n6 [ label="9, length:4" ];
marci@933
   452
  n4 ->  n6 [ label="8, length:2" ];
marci@933
   453
  n3 ->  n5 [ label="7, length:1" ];
marci@933
   454
  n2 ->  n5 [ label="6, length:3" ];
marci@933
   455
  n2 ->  n6 [ label="5, length:5" ];
marci@933
   456
  n2 ->  n4 [ label="4, length:2" ];
marci@933
   457
  n1 ->  n4 [ label="3, length:3" ];
marci@933
   458
  n0 ->  n3 [ label="2, length:1" ];
marci@933
   459
  n0 ->  n2 [ label="1, length:2" ];
marci@933
   460
  n0 ->  n1 [ label="0, length:3" ];
marci@933
   461
  }
marci@933
   462
  \enddot
marci@933
   463
marci@933
   464
  \code
marci@933
   465
  Graph g;
marci@933
   466
  Node s, t;
marci@933
   467
  LengthMap length(g);
marci@933
   468
marci@933
   469
  readDimacs(std::cin, g, length, s, t);
marci@933
   470
alpar@986
   471
  cout << "edges with lengths (of form id, source--length->target): " << endl;
marci@933
   472
  for(EdgeIt e(g); e!=INVALID; ++e) 
alpar@986
   473
    cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
alpar@986
   474
         << length[e] << "->" << g.id(g.target(e)) << endl;
marci@933
   475
marci@933
   476
  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
marci@933
   477
  \endcode
marci@933
   478
  Next, the potential function is computed with Dijkstra.
marci@933
   479
  \code
marci@933
   480
  typedef Dijkstra<Graph, LengthMap> Dijkstra;
marci@933
   481
  Dijkstra dijkstra(g, length);
marci@933
   482
  dijkstra.run(s);
marci@933
   483
  \endcode
marci@933
   484
  Next, we consrtruct a map which filters the edge-set to the tight edges.
marci@933
   485
  \code
marci@933
   486
  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
marci@933
   487
    TightEdgeFilter;
marci@933
   488
  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
marci@933
   489
  
marci@933
   490
  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
marci@933
   491
  SubGW gw(g, tight_edge_filter);
marci@933
   492
  \endcode
marci@933
   493
  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
marci@933
   494
  with a max flow algorithm Preflow.
marci@933
   495
  \code
marci@933
   496
  ConstMap<Edge, int> const_1_map(1);
marci@933
   497
  Graph::EdgeMap<int> flow(g, 0);
marci@933
   498
marci@933
   499
  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
marci@933
   500
    preflow(gw, s, t, const_1_map, flow);
marci@933
   501
  preflow.run();
marci@933
   502
  \endcode
marci@933
   503
  Last, the output is:
marci@933
   504
  \code  
marci@933
   505
  cout << "maximum number of edge-disjoint shortest path: " 
marci@933
   506
       << preflow.flowValue() << endl;
marci@933
   507
  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
marci@933
   508
       << endl;
marci@933
   509
  for(EdgeIt e(g); e!=INVALID; ++e) 
marci@933
   510
    if (flow[e])
alpar@986
   511
      cout << " " << g.id(g.source(e)) << "--" 
alpar@986
   512
	   << length[e] << "->" << g.id(g.target(e)) << endl;
marci@933
   513
  \endcode
marci@933
   514
  The program has the following (expected :-)) output:
marci@933
   515
  \code
alpar@986
   516
  edges with lengths (of form id, source--length->target):
marci@933
   517
   9, 5--4->6
marci@933
   518
   8, 4--2->6
marci@933
   519
   7, 3--1->5
marci@933
   520
   6, 2--3->5
marci@933
   521
   5, 2--5->6
marci@933
   522
   4, 2--2->4
marci@933
   523
   3, 1--3->4
marci@933
   524
   2, 0--1->3
marci@933
   525
   1, 0--2->2
marci@933
   526
   0, 0--3->1
marci@933
   527
  s: 0 t: 6
marci@933
   528
  maximum number of edge-disjoint shortest path: 2
marci@933
   529
  edges of the maximum number of edge-disjoint shortest s-t paths:
marci@933
   530
   9, 5--4->6
marci@933
   531
   8, 4--2->6
marci@933
   532
   7, 3--1->5
marci@933
   533
   4, 2--2->4
marci@933
   534
   2, 0--1->3
marci@933
   535
   1, 0--2->2
marci@933
   536
  \endcode
marci@933
   537
marci@932
   538
  \author Marton Makai
marci@932
   539
  */
marci@932
   540
  template<typename Graph, typename EdgeFilterMap>
marci@932
   541
  class EdgeSubGraphWrapper : 
marci@932
   542
    public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 
marci@932
   543
			   EdgeFilterMap> {
marci@932
   544
  public:
marci@932
   545
    typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 
marci@932
   546
			    EdgeFilterMap> Parent;
marci@932
   547
  protected:
marci@932
   548
    ConstMap<typename Graph::Node, bool> const_true_map;
marci@932
   549
  public:
marci@932
   550
    EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
marci@932
   551
      Parent(), const_true_map(true) { 
marci@932
   552
      Parent::setGraph(_graph);
marci@932
   553
      Parent::setNodeFilterMap(const_true_map);
marci@932
   554
      Parent::setEdgeFilterMap(_edge_filter_map);
marci@932
   555
    }
marci@932
   556
  };
marci@932
   557
marci@569
   558
marci@556
   559
  template<typename Graph>
marci@556
   560
  class UndirGraphWrapper : public GraphWrapper<Graph> {
marci@650
   561
  public:
marci@650
   562
    typedef GraphWrapper<Graph> Parent; 
marci@556
   563
  protected:
marci@556
   564
    UndirGraphWrapper() : GraphWrapper<Graph>() { }
marci@556
   565
    
marci@556
   566
  public:
marci@556
   567
    typedef typename GraphWrapper<Graph>::Node Node;
marci@556
   568
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@556
   569
    typedef typename GraphWrapper<Graph>::Edge Edge;
marci@556
   570
    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
marci@556
   571
marci@556
   572
    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
marci@556
   573
marci@556
   574
    class OutEdgeIt {
marci@556
   575
      friend class UndirGraphWrapper<Graph>;
marci@556
   576
      bool out_or_in; //true iff out
marci@556
   577
      typename Graph::OutEdgeIt out;
marci@556
   578
      typename Graph::InEdgeIt in;
marci@556
   579
    public:
marci@556
   580
      OutEdgeIt() { }
marci@556
   581
      OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@556
   582
      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
marci@556
   583
	out_or_in=true; _G.graph->first(out, _n);
marci@556
   584
	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
marci@556
   585
      } 
marci@556
   586
      operator Edge() const { 
marci@556
   587
	if (out_or_in) return Edge(out); else return Edge(in); 
marci@556
   588
      }
marci@556
   589
    };
marci@556
   590
marci@556
   591
    typedef OutEdgeIt InEdgeIt; 
marci@556
   592
marci@556
   593
    using GraphWrapper<Graph>::first;
marci@556
   594
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@556
   595
      i=OutEdgeIt(*this, p); return i;
marci@556
   596
    }
marci@556
   597
marci@556
   598
    using GraphWrapper<Graph>::next;
alpar@878
   599
marci@556
   600
    OutEdgeIt& next(OutEdgeIt& e) const {
marci@556
   601
      if (e.out_or_in) {
alpar@986
   602
	typename Graph::Node n=this->graph->source(e.out);
marci@556
   603
	this->graph->next(e.out);
marci@556
   604
	if (!this->graph->valid(e.out)) { 
marci@556
   605
	  e.out_or_in=false; this->graph->first(e.in, n); }
marci@556
   606
      } else {
marci@556
   607
	this->graph->next(e.in);
marci@556
   608
      }
marci@556
   609
      return e;
marci@556
   610
    }
marci@556
   611
marci@556
   612
    Node aNode(const OutEdgeIt& e) const { 
alpar@986
   613
      if (e.out_or_in) return this->graph->source(e); else 
alpar@986
   614
	return this->graph->target(e); }
marci@556
   615
    Node bNode(const OutEdgeIt& e) const { 
alpar@986
   616
      if (e.out_or_in) return this->graph->target(e); else 
alpar@986
   617
	return this->graph->source(e); }
deba@877
   618
deba@891
   619
    //    KEEP_MAPS(Parent, UndirGraphWrapper);
deba@877
   620
marci@556
   621
  };
marci@556
   622
  
marci@910
   623
//   /// \brief An undirected graph template.
marci@910
   624
//   ///
marci@910
   625
//   ///\warning Graph wrappers are in even more experimental state than the other
marci@910
   626
//   ///parts of the lib. Use them at your own risk.
marci@910
   627
//   ///
marci@910
   628
//   /// An undirected graph template.
marci@910
   629
//   /// This class works as an undirected graph and a directed graph of 
marci@910
   630
//   /// class \c Graph is used for the physical storage.
marci@910
   631
//   /// \ingroup graphs
marci@556
   632
  template<typename Graph>
marci@556
   633
  class UndirGraph : public UndirGraphWrapper<Graph> {
marci@556
   634
    typedef UndirGraphWrapper<Graph> Parent;
marci@556
   635
  protected:
marci@556
   636
    Graph gr;
marci@556
   637
  public:
marci@556
   638
    UndirGraph() : UndirGraphWrapper<Graph>() { 
marci@556
   639
      Parent::setGraph(gr); 
marci@556
   640
    }
deba@877
   641
deba@891
   642
    //    KEEP_MAPS(Parent, UndirGraph);
marci@556
   643
  };
marci@556
   644
marci@992
   645
  
marci@992
   646
  template <typename _Graph, 
marci@992
   647
	    typename ForwardFilterMap, typename BackwardFilterMap>
marci@992
   648
  class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@992
   649
  public:
marci@992
   650
    typedef _Graph Graph;
marci@992
   651
    typedef GraphWrapperBase<_Graph> Parent;
marci@992
   652
  protected:
marci@992
   653
    ForwardFilterMap* forward_filter;
marci@992
   654
    BackwardFilterMap* backward_filter;
marci@992
   655
    SubBidirGraphWrapperBase() : Parent(), 
marci@992
   656
				 forward_filter(0), backward_filter(0) { }
marci@992
   657
marci@992
   658
    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
marci@992
   659
      forward_filter=&_forward_filter;
marci@992
   660
    }
marci@992
   661
    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
marci@992
   662
      backward_filter=&_backward_filter;
marci@992
   663
    }
marci@992
   664
marci@992
   665
  public:
marci@992
   666
//     SubGraphWrapperBase(Graph& _graph, 
marci@992
   667
// 			NodeFilterMap& _node_filter_map, 
marci@992
   668
// 			EdgeFilterMap& _edge_filter_map) : 
marci@992
   669
//       Parent(&_graph), 
marci@992
   670
//       node_filter_map(&node_filter_map), 
marci@992
   671
//       edge_filter_map(&edge_filter_map) { }
marci@992
   672
marci@992
   673
    typedef typename Parent::Node Node;
marci@992
   674
    typedef typename _Graph::Edge GraphEdge;
marci@992
   675
    template <typename T> class EdgeMap;
marci@992
   676
    /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from 
marci@992
   677
    /// _Graph::Edge. It contains an extra bool flag which is true 
marci@992
   678
    /// if and only if the 
marci@992
   679
    /// edge is the backward version of the original edge.
marci@992
   680
    class Edge : public _Graph::Edge {
marci@992
   681
      friend class SubBidirGraphWrapperBase<
marci@992
   682
	Graph, ForwardFilterMap, BackwardFilterMap>;
marci@992
   683
      template<typename T> friend class EdgeMap;
marci@992
   684
    protected:
marci@992
   685
      bool backward; //true, iff backward
marci@992
   686
    public:
marci@992
   687
      Edge() { }
marci@992
   688
      /// \todo =false is needed, or causes problems?
marci@992
   689
      /// If \c _backward is false, then we get an edge corresponding to the 
marci@992
   690
      /// original one, otherwise its oppositely directed pair is obtained.
marci@992
   691
      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
marci@992
   692
	_Graph::Edge(e), backward(_backward) { }
marci@992
   693
      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
marci@992
   694
      bool operator==(const Edge& v) const { 
marci@992
   695
	return (this->backward==v.backward && 
marci@992
   696
		static_cast<typename _Graph::Edge>(*this)==
marci@992
   697
		static_cast<typename _Graph::Edge>(v));
marci@992
   698
      } 
marci@992
   699
      bool operator!=(const Edge& v) const { 
marci@992
   700
	return (this->backward!=v.backward || 
marci@992
   701
		static_cast<typename _Graph::Edge>(*this)!=
marci@992
   702
		static_cast<typename _Graph::Edge>(v));
marci@992
   703
      }
marci@992
   704
    };
marci@992
   705
marci@992
   706
    void first(Node& i) const { 
marci@992
   707
      Parent::first(i); 
marci@992
   708
    }
marci@992
   709
marci@992
   710
    void first(Edge& i) const { 
marci@992
   711
      Parent::first(i); 
marci@992
   712
      i.backward=false;
marci@992
   713
      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   714
	     !(*forward_filter)[i]) Parent::next(i);
marci@992
   715
      if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992
   716
	Parent::first(i); 
marci@992
   717
	i.backward=true;
marci@992
   718
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   719
	       !(*backward_filter)[i]) Parent::next(i);
marci@992
   720
      }
marci@992
   721
    }
marci@992
   722
marci@992
   723
    void firstIn(Edge& i, const Node& n) const { 
marci@992
   724
      Parent::firstIn(i, n); 
marci@992
   725
      i.backward=false;
marci@992
   726
      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   727
	     !(*forward_filter)[i]) Parent::nextOut(i);
marci@992
   728
      if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992
   729
	Parent::firstOut(i, n); 
marci@992
   730
	i.backward=true;
marci@992
   731
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   732
	       !(*backward_filter)[i]) Parent::nextOut(i);
marci@992
   733
      }
marci@992
   734
    }
marci@992
   735
marci@992
   736
    void firstOut(Edge& i, const Node& n) const { 
marci@992
   737
      Parent::firstOut(i, n); 
marci@992
   738
      i.backward=false;
marci@992
   739
      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   740
	     !(*forward_filter)[i]) Parent::nextOut(i);
marci@992
   741
      if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992
   742
	Parent::firstIn(i, n); 
marci@992
   743
	i.backward=true;
marci@992
   744
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   745
	       !(*backward_filter)[i]) Parent::nextIn(i);
marci@992
   746
      }
marci@992
   747
    }
marci@992
   748
marci@992
   749
    void next(Node& i) const { 
marci@992
   750
      Parent::next(i); 
marci@992
   751
    }
marci@992
   752
marci@992
   753
    void next(Edge& i) const { 
marci@992
   754
      if (!(i.backward)) {
marci@992
   755
	Parent::next(i);
marci@992
   756
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   757
	       !(*forward_filter)[i]) Parent::next(i);
marci@992
   758
	if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992
   759
	  Parent::first(i); 
marci@992
   760
	  i.backward=true;
marci@992
   761
	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   762
		 !(*backward_filter)[i]) Parent::next(i);
marci@992
   763
	}
marci@992
   764
      } else {
marci@992
   765
	Parent::next(i);
marci@992
   766
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   767
	       !(*backward_filter)[i]) Parent::next(i);
marci@992
   768
      }
marci@992
   769
    }
marci@992
   770
marci@992
   771
    void nextIn(Edge& i) const { 
marci@992
   772
      if (!(i.backward)) {
marci@992
   773
	Node n=Parent::target(i);
marci@992
   774
	Parent::nextIn(i);
marci@992
   775
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   776
	       !(*forward_filter)[i]) Parent::nextIn(i);
marci@992
   777
	if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992
   778
	  Parent::firstOut(i, n); 
marci@992
   779
	  i.backward=true;
marci@992
   780
	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   781
		 !(*backward_filter)[i]) Parent::nextOut(i);
marci@992
   782
	}
marci@992
   783
      } else {
marci@992
   784
	Parent::nextOut(i);
marci@992
   785
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   786
	       !(*backward_filter)[i]) Parent::nextOut(i);
marci@992
   787
      }
marci@992
   788
    }
marci@992
   789
marci@992
   790
    void nextOut(Edge& i) const { 
marci@992
   791
      if (!(i.backward)) {
marci@992
   792
	Node n=Parent::source(i);
marci@992
   793
	Parent::nextOut(i);
marci@992
   794
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   795
	       !(*forward_filter)[i]) Parent::nextOut(i);
marci@992
   796
	if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992
   797
	  Parent::firstIn(i, n); 
marci@992
   798
	  i.backward=true;
marci@992
   799
	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   800
		 !(*backward_filter)[i]) Parent::nextIn(i);
marci@992
   801
	}
marci@992
   802
      } else {
marci@992
   803
	Parent::nextIn(i);
marci@992
   804
	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992
   805
	       !(*backward_filter)[i]) Parent::nextIn(i);
marci@992
   806
      }
marci@992
   807
    }
marci@992
   808
marci@992
   809
    Node source(Edge e) const { 
marci@992
   810
      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
marci@992
   811
    Node target(Edge e) const { 
marci@992
   812
      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
marci@992
   813
marci@992
   814
    /// Gives back the opposite edge.
marci@992
   815
    Edge opposite(const Edge& e) const { 
marci@992
   816
      Edge f=e;
marci@992
   817
      f.backward=!f.backward;
marci@992
   818
      return f;
marci@992
   819
    }
marci@992
   820
marci@992
   821
    /// \warning This is a linear time operation and works only if 
marci@992
   822
    /// \c Graph::EdgeIt is defined.
marci@992
   823
    /// \todo hmm
marci@992
   824
    int edgeNum() const { 
marci@992
   825
      int i=0;
marci@992
   826
      Edge e;
marci@992
   827
      for (first(e); e!=INVALID; next(e)) ++i;
marci@992
   828
      return i; 
marci@992
   829
    }
marci@992
   830
marci@992
   831
    bool forward(const Edge& e) const { return !e.backward; }
marci@992
   832
    bool backward(const Edge& e) const { return e.backward; }
marci@992
   833
marci@992
   834
    template <typename T>
marci@992
   835
    /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two 
marci@992
   836
    /// _Graph::EdgeMap one for the forward edges and 
marci@992
   837
    /// one for the backward edges.
marci@992
   838
    class EdgeMap {
marci@992
   839
      template <typename TT> friend class EdgeMap;
marci@992
   840
      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
marci@992
   841
    public:
marci@992
   842
      typedef T Value;
marci@992
   843
      typedef Edge Key;
marci@992
   844
marci@992
   845
      EdgeMap(const SubBidirGraphWrapperBase<_Graph, 
marci@992
   846
	      ForwardFilterMap, BackwardFilterMap>& g) : 
marci@992
   847
	forward_map(*(g.graph)), backward_map(*(g.graph)) { }
marci@992
   848
marci@992
   849
      EdgeMap(const SubBidirGraphWrapperBase<_Graph, 
marci@992
   850
	      ForwardFilterMap, BackwardFilterMap>& g, T a) : 
marci@992
   851
	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
marci@992
   852
      
marci@992
   853
      void set(Edge e, T a) { 
marci@992
   854
	if (!e.backward) 
marci@992
   855
	  forward_map.set(e, a); 
marci@992
   856
	else 
marci@992
   857
	  backward_map.set(e, a); 
marci@992
   858
      }
marci@992
   859
marci@992
   860
//       typename _Graph::template EdgeMap<T>::ConstReference 
marci@992
   861
//       operator[](Edge e) const { 
marci@992
   862
// 	if (!e.backward) 
marci@992
   863
// 	  return forward_map[e]; 
marci@992
   864
// 	else 
marci@992
   865
// 	  return backward_map[e]; 
marci@992
   866
//       }
marci@992
   867
marci@992
   868
//      typename _Graph::template EdgeMap<T>::Reference 
marci@1016
   869
      T operator[](Edge e) const { 
marci@992
   870
	if (!e.backward) 
marci@992
   871
	  return forward_map[e]; 
marci@992
   872
	else 
marci@992
   873
	  return backward_map[e]; 
marci@992
   874
      }
marci@992
   875
marci@992
   876
      void update() { 
marci@992
   877
	forward_map.update(); 
marci@992
   878
	backward_map.update();
marci@992
   879
      }
marci@992
   880
    };
marci@992
   881
marci@992
   882
  };
marci@569
   883
marci@650
   884
marci@650
   885
  ///\brief A wrapper for composing a subgraph of a 
marci@792
   886
  /// bidirected graph made from a directed one. 
marci@612
   887
  ///
alpar@911
   888
  /// A wrapper for composing a subgraph of a 
alpar@911
   889
  /// bidirected graph made from a directed one. 
alpar@911
   890
  ///
alpar@879
   891
  ///\warning Graph wrappers are in even more experimental state than the other
alpar@879
   892
  ///parts of the lib. Use them at you own risk.
alpar@879
   893
  ///
marci@923
   894
  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 
marci@923
   895
  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
marci@923
   896
  /// reversing its orientation. We are given moreover two bool valued 
marci@923
   897
  /// maps on the edge-set, 
marci@923
   898
  /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 
marci@923
   899
  /// SubBidirGraphWrapper implements the graph structure with node-set 
marci@923
   900
  /// \f$V\f$ and edge-set 
marci@923
   901
  /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. 
marci@792
   902
  /// The purpose of writing + instead of union is because parallel 
marci@923
   903
  /// edges can arise. (Similarly, antiparallel edges also can arise).
marci@792
   904
  /// In other words, a subgraph of the bidirected graph obtained, which 
marci@792
   905
  /// is given by orienting the edges of the original graph in both directions.
marci@923
   906
  /// As the oppositely directed edges are logically different, 
marci@923
   907
  /// the maps are able to attach different values for them. 
marci@923
   908
  ///
marci@923
   909
  /// An example for such a construction is \c RevGraphWrapper where the 
marci@792
   910
  /// forward_filter is everywhere false and the backward_filter is 
marci@792
   911
  /// everywhere true. We note that for sake of efficiency, 
marci@792
   912
  /// \c RevGraphWrapper is implemented in a different way. 
marci@792
   913
  /// But BidirGraphWrapper is obtained from 
marci@792
   914
  /// SubBidirGraphWrapper by considering everywhere true 
marci@910
   915
  /// valued maps both for forward_filter and backward_filter. 
marci@792
   916
  /// Finally, one of the most important applications of SubBidirGraphWrapper 
marci@792
   917
  /// is ResGraphWrapper, which stands for the residual graph in directed 
marci@792
   918
  /// flow and circulation problems. 
marci@792
   919
  /// As wrappers usually, the SubBidirGraphWrapper implements the 
marci@792
   920
  /// above mentioned graph structure without its physical storage, 
marci@923
   921
  /// that is the whole stuff is stored in constant memory. 
marci@992
   922
  template<typename _Graph, 
marci@650
   923
	   typename ForwardFilterMap, typename BackwardFilterMap>
marci@992
   924
  class SubBidirGraphWrapper : 
marci@992
   925
    public IterableGraphExtender<
marci@992
   926
    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
marci@650
   927
  public:
marci@992
   928
    typedef _Graph Graph;
marci@992
   929
    typedef IterableGraphExtender<
marci@992
   930
      SubBidirGraphWrapperBase<
marci@992
   931
      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
marci@569
   932
  protected:
marci@992
   933
    SubBidirGraphWrapper() { }
marci@992
   934
  public:
marci@992
   935
    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter, 
marci@992
   936
			 BackwardFilterMap& _backward_filter) { 
marci@992
   937
      setGraph(_graph);
marci@992
   938
      setForwardFilterMap(_forward_filter);
marci@992
   939
      setBackwardFilterMap(_backward_filter);
marci@992
   940
    }
marci@992
   941
  };
marci@650
   942
marci@569
   943
marci@650
   944
marci@650
   945
  ///\brief A wrapper for composing bidirected graph from a directed one. 
marci@650
   946
  ///
alpar@879
   947
  ///\warning Graph wrappers are in even more experimental state than the other
alpar@879
   948
  ///parts of the lib. Use them at you own risk.
alpar@879
   949
  ///
marci@650
   950
  /// A wrapper for composing bidirected graph from a directed one. 
marci@650
   951
  /// A bidirected graph is composed over the directed one without physical 
marci@650
   952
  /// storage. As the oppositely directed edges are logically different ones 
marci@650
   953
  /// the maps are able to attach different values for them.
marci@650
   954
  template<typename Graph>
marci@650
   955
  class BidirGraphWrapper : 
marci@650
   956
    public SubBidirGraphWrapper<
marci@650
   957
    Graph, 
marci@650
   958
    ConstMap<typename Graph::Edge, bool>, 
marci@650
   959
    ConstMap<typename Graph::Edge, bool> > {
marci@650
   960
  public:
marci@650
   961
    typedef  SubBidirGraphWrapper<
marci@650
   962
      Graph, 
marci@650
   963
      ConstMap<typename Graph::Edge, bool>, 
marci@650
   964
      ConstMap<typename Graph::Edge, bool> > Parent; 
marci@650
   965
  protected:
marci@650
   966
    ConstMap<typename Graph::Edge, bool> cm;
marci@650
   967
marci@655
   968
    BidirGraphWrapper() : Parent(), cm(true) { 
marci@655
   969
      Parent::setForwardFilterMap(cm);
marci@655
   970
      Parent::setBackwardFilterMap(cm);
marci@655
   971
    }
marci@650
   972
  public:
marci@650
   973
    BidirGraphWrapper(Graph& _graph) : Parent() { 
marci@650
   974
      Parent::setGraph(_graph);
marci@650
   975
      Parent::setForwardFilterMap(cm);
marci@650
   976
      Parent::setBackwardFilterMap(cm);
marci@650
   977
    }
marci@738
   978
marci@738
   979
    int edgeNum() const { 
marci@738
   980
      return 2*this->graph->edgeNum();
marci@738
   981
    }
deba@891
   982
    //    KEEP_MAPS(Parent, BidirGraphWrapper);
marci@650
   983
  };
marci@650
   984
marci@650
   985
marci@650
   986
  template<typename Graph, typename Number,
marci@650
   987
	   typename CapacityMap, typename FlowMap>
marci@658
   988
  class ResForwardFilter {
marci@658
   989
    //    const Graph* graph;
marci@650
   990
    const CapacityMap* capacity;
marci@650
   991
    const FlowMap* flow;
marci@650
   992
  public:
marci@658
   993
    ResForwardFilter(/*const Graph& _graph, */
marci@658
   994
		     const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658
   995
      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
marci@658
   996
    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
marci@656
   997
    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656
   998
    void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650
   999
    bool operator[](const typename Graph::Edge& e) const {
marci@738
  1000
      return (Number((*flow)[e]) < Number((*capacity)[e]));
marci@650
  1001
    }
marci@650
  1002
  };
marci@650
  1003
marci@650
  1004
  template<typename Graph, typename Number,
marci@650
  1005
	   typename CapacityMap, typename FlowMap>
marci@658
  1006
  class ResBackwardFilter {
marci@650
  1007
    const CapacityMap* capacity;
marci@650
  1008
    const FlowMap* flow;
marci@650
  1009
  public:
marci@658
  1010
    ResBackwardFilter(/*const Graph& _graph,*/ 
marci@658
  1011
		      const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658
  1012
      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
marci@658
  1013
    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
marci@656
  1014
    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656
  1015
    void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650
  1016
    bool operator[](const typename Graph::Edge& e) const {
marci@738
  1017
      return (Number(0) < Number((*flow)[e]));
marci@650
  1018
    }
marci@650
  1019
  };
marci@650
  1020
marci@653
  1021
  
marci@653
  1022
  /// A wrapper for composing the residual graph for directed flow and circulation problems.
marci@650
  1023
alpar@879
  1024
  ///\warning Graph wrappers are in even more experimental state than the other
alpar@879
  1025
  ///parts of the lib. Use them at you own risk.
alpar@879
  1026
  ///
marci@653
  1027
  /// A wrapper for composing the residual graph for directed flow and circulation problems.
marci@650
  1028
  template<typename Graph, typename Number, 
marci@650
  1029
	   typename CapacityMap, typename FlowMap>
marci@653
  1030
  class ResGraphWrapper : 
marci@650
  1031
    public SubBidirGraphWrapper< 
marci@650
  1032
    Graph, 
marci@658
  1033
    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
marci@658
  1034
    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
marci@650
  1035
  public:
marci@650
  1036
    typedef SubBidirGraphWrapper< 
marci@650
  1037
      Graph, 
marci@658
  1038
      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
marci@658
  1039
      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
marci@650
  1040
  protected:
marci@650
  1041
    const CapacityMap* capacity;
marci@650
  1042
    FlowMap* flow;
marci@658
  1043
    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
marci@658
  1044
    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
marci@658
  1045
    ResGraphWrapper() : Parent(), 
marci@658
  1046
 			capacity(0), flow(0) { }
marci@658
  1047
    void setCapacityMap(const CapacityMap& _capacity) {
marci@658
  1048
      capacity=&_capacity;
marci@658
  1049
      forward_filter.setCapacity(_capacity);
marci@658
  1050
      backward_filter.setCapacity(_capacity);
marci@658
  1051
    }
marci@658
  1052
    void setFlowMap(FlowMap& _flow) {
marci@658
  1053
      flow=&_flow;
marci@658
  1054
      forward_filter.setFlow(_flow);
marci@658
  1055
      backward_filter.setFlow(_flow);
marci@658
  1056
    }
marci@650
  1057
  public:
marci@653
  1058
    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
marci@650
  1059
		       FlowMap& _flow) : 
marci@650
  1060
      Parent(), capacity(&_capacity), flow(&_flow), 
marci@658
  1061
      forward_filter(/*_graph,*/ _capacity, _flow), 
marci@658
  1062
      backward_filter(/*_graph,*/ _capacity, _flow) {
marci@650
  1063
      Parent::setGraph(_graph);
marci@650
  1064
      Parent::setForwardFilterMap(forward_filter);
marci@650
  1065
      Parent::setBackwardFilterMap(backward_filter);
marci@650
  1066
    }
marci@650
  1067
marci@660
  1068
    typedef typename Parent::Edge Edge;
marci@660
  1069
marci@660
  1070
    void augment(const Edge& e, Number a) const {
marci@650
  1071
      if (Parent::forward(e))  
marci@650
  1072
	flow->set(e, (*flow)[e]+a);
marci@650
  1073
      else  
marci@650
  1074
	flow->set(e, (*flow)[e]-a);
marci@650
  1075
    }
marci@650
  1076
marci@660
  1077
    /// \brief Residual capacity map.
marci@660
  1078
    ///
marci@910
  1079
    /// In generic residual graphs the residual capacity can be obtained 
marci@910
  1080
    /// as a map. 
marci@660
  1081
    class ResCap {
marci@660
  1082
    protected:
marci@660
  1083
      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
marci@660
  1084
    public:
alpar@987
  1085
      typedef Number Value;
alpar@987
  1086
      typedef Edge Key;
marci@888
  1087
      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& 
marci@888
  1088
	     _res_graph) : res_graph(&_res_graph) { }
marci@660
  1089
      Number operator[](const Edge& e) const { 
marci@660
  1090
	if (res_graph->forward(e)) 
marci@660
  1091
	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
marci@660
  1092
	else 
marci@660
  1093
	  return (*(res_graph->flow))[e]; 
marci@660
  1094
      }
marci@660
  1095
    };
marci@660
  1096
deba@891
  1097
    //    KEEP_MAPS(Parent, ResGraphWrapper);
marci@650
  1098
  };
marci@650
  1099
marci@650
  1100
marci@998
  1101
marci@998
  1102
  template <typename _Graph, typename FirstOutEdgesMap>
marci@998
  1103
  class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@998
  1104
  public:
marci@998
  1105
    typedef _Graph Graph;
marci@998
  1106
    typedef GraphWrapperBase<_Graph> Parent;
marci@998
  1107
  protected:
marci@998
  1108
    FirstOutEdgesMap* first_out_edges;
marci@998
  1109
    ErasingFirstGraphWrapperBase() : Parent(), 
marci@998
  1110
				     first_out_edges(0) { }
marci@998
  1111
marci@998
  1112
    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998
  1113
      first_out_edges=&_first_out_edges;
marci@998
  1114
    }
marci@998
  1115
marci@998
  1116
  public:
marci@998
  1117
marci@998
  1118
    typedef typename Parent::Node Node;
marci@998
  1119
    typedef typename Parent::Edge Edge;
marci@998
  1120
marci@998
  1121
    void firstOut(Edge& i, const Node& n) const { 
marci@998
  1122
      i=(*first_out_edges)[n];
marci@998
  1123
    }
marci@998
  1124
marci@998
  1125
    void erase(const Edge& e) const {
marci@998
  1126
      Node n=source(e);
marci@998
  1127
      Edge f=e;
marci@998
  1128
      Parent::nextOut(f);
marci@998
  1129
      first_out_edges->set(n, f);
marci@998
  1130
    }    
marci@998
  1131
  };
marci@998
  1132
marci@998
  1133
marci@612
  1134
  /// For blocking flows.
marci@556
  1135
alpar@879
  1136
  ///\warning Graph wrappers are in even more experimental state than the other
alpar@879
  1137
  ///parts of the lib. Use them at you own risk.
alpar@879
  1138
  ///
marci@792
  1139
  /// This graph wrapper is used for on-the-fly 
marci@792
  1140
  /// Dinits blocking flow computations.
marci@612
  1141
  /// For each node, an out-edge is stored which is used when the 
marci@612
  1142
  /// \code 
marci@612
  1143
  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
marci@612
  1144
  /// \endcode
marci@612
  1145
  /// is called. 
marci@556
  1146
  ///
marci@792
  1147
  /// \author Marton Makai
marci@998
  1148
  template <typename _Graph, typename FirstOutEdgesMap>
marci@998
  1149
  class ErasingFirstGraphWrapper : 
marci@998
  1150
    public IterableGraphExtender<
marci@998
  1151
    ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
marci@650
  1152
  public:
marci@998
  1153
    typedef _Graph Graph;
marci@998
  1154
    typedef IterableGraphExtender<
marci@998
  1155
      ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
marci@556
  1156
    ErasingFirstGraphWrapper(Graph& _graph, 
marci@998
  1157
			     FirstOutEdgesMap& _first_out_edges) { 
marci@998
  1158
      setGraph(_graph);
marci@998
  1159
      setFirstOutEdgesMap(_first_out_edges);
marci@998
  1160
    } 
marci@1019
  1161
marci@998
  1162
  };
marci@556
  1163
marci@556
  1164
  ///@}
marci@556
  1165
alpar@921
  1166
} //namespace lemon
marci@556
  1167
alpar@921
  1168
#endif //LEMON_GRAPH_WRAPPER_H
marci@556
  1169