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