COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 1016:18d009b23e42

Last change on this file since 1016:18d009b23e42 was 1016:18d009b23e42, checked in by marci, 16 years ago

bug fix in SubBidirGraphWrapper?, roadmap to MergeGraphWrapper?

File size: 67.3 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_GRAPH_WRAPPER_H
18#define LEMON_GRAPH_WRAPPER_H
19
20///\ingroup gwrappers
21///\file
22///\brief Several graph wrappers.
23///
24///This file contains several useful graph wrapper functions.
25///
26///\author Marton Makai
27
28#include <lemon/invalid.h>
29#include <lemon/maps.h>
30#include <lemon/iterable_graph_extender.h>
31#include <lemon/map_defines.h>
32#include <iostream>
33
34namespace lemon {
35
36  // Graph wrappers
37
38  /*! \addtogroup gwrappers
39    The main parts of LEMON are the different graph structures,
40    generic graph algorithms, graph concepts which couple these, and
41    graph wrappers. While the previous ones are more or less clear, the
42    latter notion needs further explanation.
43    Graph wrappers are graph classes which serve for considering graph
44    structures in different ways. A short example makes the notion much
45    clearer.
46    Suppose that we have an instance \c g of a directed graph
47    type say \c ListGraph and an algorithm
48    \code template<typename Graph> int algorithm(const Graph&); \endcode
49    is needed to run on the reversely oriented graph.
50    It may be expensive (in time or in memory usage) to copy
51    \c g with the reverse orientation.
52    Thus, a wrapper class
53    \code template<typename Graph> class RevGraphWrapper; \endcode is used.
54    The code looks as follows
55    \code
56    ListGraph g;
57    RevGraphWrapper<ListGraph> rgw(g);
58    int result=algorithm(rgw);
59    \endcode
60    After running the algorithm, the original graph \c g
61    remains untouched. Thus the graph wrapper used above is to consider the
62    original graph with reverse orientation.
63    This techniques gives rise to an elegant code, and
64    based on stable graph wrappers, complex algorithms can be
65    implemented easily.
66    In flow, circulation and bipartite matching problems, the residual
67    graph is of particular importance. Combining a wrapper implementing
68    this, shortest path algorithms and minimum mean cycle algorithms,
69    a range of weighted and cardinality optimization algorithms can be
70    obtained. For lack of space, for other examples,
71    the interested user is referred to the detailed documentation of graph
72    wrappers.
73    The behavior of graph wrappers can be very different. Some of them keep
74    capabilities of the original graph while in other cases this would be
75    meaningless. This means that the concepts that they are a model of depend
76    on the graph wrapper, and the wrapped graph(s).
77    If an edge of \c rgw is deleted, this is carried out by
78    deleting the corresponding edge of \c g. But for a residual
79    graph, this operation has no sense.
80    Let we stand one more example here to simplify your work.
81    wrapper class
82    \code template<typename Graph> class RevGraphWrapper; \endcode
83    has constructor
84    <tt> RevGraphWrapper(Graph& _g)</tt>.
85    This means that in a situation,
86    when a <tt> const ListGraph& </tt> reference to a graph is given,
87    then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
88    \code
89    int algorithm1(const ListGraph& g) {
90    RevGraphWrapper<const ListGraph> rgw(g);
91    return algorithm2(rgw);
92    }
93    \endcode
94
95    \addtogroup gwrappers
96    @{
97
98    Base type for the Graph Wrappers
99
100    \warning Graph wrappers are in even more experimental state than the other
101    parts of the lib. Use them at you own risk.
102 
103    This is the base type for most of LEMON graph wrappers.
104    This class implements a trivial graph wrapper i.e. it only wraps the
105    functions and types of the graph. The purpose of this class is to
106    make easier implementing graph wrappers. E.g. if a wrapper is
107    considered which differs from the wrapped graph only in some of its
108    functions or types, then it can be derived from GraphWrapper, and only the
109    differences should be implemented.
110 
111    \author Marton Makai
112  */
113  template<typename _Graph>
114  class GraphWrapperBase {
115  public:
116    typedef _Graph Graph;
117    /// \todo Is it needed?
118    typedef Graph BaseGraph;
119    typedef Graph ParentGraph;
120
121  protected:
122    Graph* graph;
123    GraphWrapperBase() : graph(0) { }
124    void setGraph(Graph& _graph) { graph=&_graph; }
125
126  public:
127    GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
128//     GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }
129 
130    typedef typename Graph::Node Node;
131    typedef typename Graph::Edge Edge;
132   
133    void first(Node& i) const { graph->first(i); }
134    void first(Edge& i) const { graph->first(i); }
135    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
136    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
137//     NodeIt& first(NodeIt& i) const {
138//       i=NodeIt(*this); return i;
139//     }
140//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
141//       i=OutEdgeIt(*this, p); return i;
142//     }
143//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
144//       i=InEdgeIt(*this, p); return i;
145//     }
146//     EdgeIt& first(EdgeIt& i) const {
147//       i=EdgeIt(*this); return i;
148//     }
149
150    void next(Node& i) const { graph->next(i); }
151    void next(Edge& i) const { graph->next(i); }
152    void nextIn(Edge& i) const { graph->nextIn(i); }
153    void nextOut(Edge& i) const { graph->nextOut(i); }
154
155    Node source(const Edge& e) const { return graph->source(e); }
156    Node target(const Edge& e) const { return graph->target(e); }
157//     Node source(const Edge& e) const {
158//       return Node(graph->source(static_cast<typename Graph::Edge>(e))); }
159//     Node target(const Edge& e) const {
160//       return Node(graph->target(static_cast<typename Graph::Edge>(e))); }
161
162    int nodeNum() const { return graph->nodeNum(); }
163    int edgeNum() const { return graph->edgeNum(); }
164 
165    Node addNode() const { return Node(graph->addNode()); }
166    Edge addEdge(const Node& source, const Node& target) const {
167      return Edge(graph->addEdge(source, target)); }
168
169    void erase(const Node& i) const { graph->erase(i); }
170    void erase(const Edge& i) const { graph->erase(i); }
171 
172    void clear() const { graph->clear(); }
173   
174    bool forward(const Edge& e) const { return graph->forward(e); }
175    bool backward(const Edge& e) const { return graph->backward(e); }
176
177    int id(const Node& v) const { return graph->id(v); }
178    int id(const Edge& e) const { return graph->id(e); }
179   
180    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
181
182    template <typename _Value>
183    class NodeMap : public _Graph::template NodeMap<_Value> {
184    public:
185      typedef typename _Graph::template NodeMap<_Value> Parent;
186      NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
187      NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
188      : Parent(*gw.graph, value) { }
189    };
190
191    template <typename _Value>
192    class EdgeMap : public _Graph::template EdgeMap<_Value> {
193    public:
194      typedef typename _Graph::template EdgeMap<_Value> Parent;
195      EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
196      EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
197      : Parent(*gw.graph, value) { }
198    };
199
200  };
201
202  template <typename _Graph>
203  class GraphWrapper :
204    public IterableGraphExtender<GraphWrapperBase<_Graph> > {
205  public:
206    typedef _Graph Graph;
207    typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
208  protected:
209    GraphWrapper() : Parent() { }
210
211  public:
212    GraphWrapper(Graph& _graph) { setGraph(_graph); }
213  };
214
215  template <typename _Graph>
216  class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
217  public:
218    typedef _Graph Graph;
219    typedef GraphWrapperBase<_Graph> Parent;
220  protected:
221    RevGraphWrapperBase() : Parent() { }
222  public:
223    typedef typename Parent::Node Node;
224    typedef typename Parent::Edge Edge;
225
226    using Parent::first;
227    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
228    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
229
230    using Parent::next;
231    void nextIn(Edge& i) const { Parent::nextOut(i); }
232    void nextOut(Edge& i) const { Parent::nextIn(i); }
233
234    Node source(const Edge& e) const { return Parent::target(e); }
235    Node target(const Edge& e) const { return Parent::source(e); }
236  };
237   
238
239  /// A graph wrapper which reverses the orientation of the edges.
240
241  ///\warning Graph wrappers are in even more experimental state than the other
242  ///parts of the lib. Use them at you own risk.
243  ///
244  /// Let \f$G=(V, A)\f$ be a directed graph and
245  /// suppose that a graph instange \c g of type
246  /// \c ListGraph implements \f$G\f$.
247  /// \code
248  /// ListGraph g;
249  /// \endcode
250  /// For each directed edge
251  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
252  /// reversing its orientation.
253  /// Then RevGraphWrapper implements the graph structure with node-set
254  /// \f$V\f$ and edge-set
255  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
256  /// reversing the orientation of its edges. The following code shows how
257  /// such an instance can be constructed.
258  /// \code
259  /// RevGraphWrapper<ListGraph> gw(g);
260  /// \endcode
261  ///\author Marton Makai
262  template<typename _Graph>
263  class RevGraphWrapper :
264    public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
265  public:
266    typedef _Graph Graph;
267    typedef IterableGraphExtender<
268      RevGraphWrapperBase<_Graph> > Parent;
269  protected:
270    RevGraphWrapper() { }
271  public:
272    RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
273  };
274//   template<typename Graph>
275//   class RevGraphWrapper : public GraphWrapper<Graph> {
276//   public:
277//     typedef GraphWrapper<Graph> Parent;
278//   protected:
279//     RevGraphWrapper() : GraphWrapper<Graph>() { }
280//   public:
281//     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
282//     RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
283
284//     typedef typename GraphWrapper<Graph>::Node Node;
285//     typedef typename GraphWrapper<Graph>::Edge Edge;
286//     //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
287//     //because this does not work is some of them are not defined in the
288//     //original graph. The problem with this is that typedef-ed stuff
289//     //are instantiated in c++.
290//     class OutEdgeIt : public Edge {
291//       const RevGraphWrapper<Graph>* gw;
292//       friend class GraphWrapper<Graph>;
293//      public:
294//       OutEdgeIt() { }
295//       OutEdgeIt(Invalid i) : Edge(i) { }
296//       OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
297//      Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
298//       OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
299//      Edge(e), gw(&_gw) { }
300//       OutEdgeIt& operator++() {
301//      *(static_cast<Edge*>(this))=
302//        ++(typename Graph::InEdgeIt(*(gw->graph), *this));
303//      return *this;
304//       }
305//     };
306//     class InEdgeIt : public Edge {
307//       const RevGraphWrapper<Graph>* gw;
308//       friend class GraphWrapper<Graph>;
309//      public:
310//       InEdgeIt() { }
311//       InEdgeIt(Invalid i) : Edge(i) { }
312//       InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
313//      Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
314//       InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
315//      Edge(e), gw(&_gw) { }
316//       InEdgeIt& operator++() {
317//      *(static_cast<Edge*>(this))=
318//        ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
319//      return *this;
320//       }
321//     };
322
323//     using GraphWrapper<Graph>::first;
324//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
325//       i=OutEdgeIt(*this, p); return i;
326//     }
327//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
328//       i=InEdgeIt(*this, p); return i;
329//     }
330
331//     Node source(const Edge& e) const {
332//       return GraphWrapper<Graph>::target(e); }
333//     Node target(const Edge& e) const {
334//       return GraphWrapper<Graph>::source(e); }
335
336//     //    KEEP_MAPS(Parent, RevGraphWrapper);
337
338//   };
339
340 
341  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
342  class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
343  public:
344    typedef _Graph Graph;
345    typedef GraphWrapperBase<_Graph> Parent;
346  protected:
347    NodeFilterMap* node_filter_map;
348    EdgeFilterMap* edge_filter_map;
349    SubGraphWrapperBase() : Parent(),
350                            node_filter_map(0), edge_filter_map(0) { }
351
352    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
353      node_filter_map=&_node_filter_map;
354    }
355    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
356      edge_filter_map=&_edge_filter_map;
357    }
358
359  public:
360//     SubGraphWrapperBase(Graph& _graph,
361//                      NodeFilterMap& _node_filter_map,
362//                      EdgeFilterMap& _edge_filter_map) :
363//       Parent(&_graph),
364//       node_filter_map(&node_filter_map),
365//       edge_filter_map(&edge_filter_map) { }
366
367    typedef typename Parent::Node Node;
368    typedef typename Parent::Edge Edge;
369
370    void first(Node& i) const {
371      Parent::first(i);
372      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
373    }
374    void first(Edge& i) const {
375      Parent::first(i);
376      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
377    }
378    void firstIn(Edge& i, const Node& n) const {
379      Parent::firstIn(i, n);
380      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
381    }
382    void firstOut(Edge& i, const Node& n) const {
383      Parent::firstOut(i, n);
384      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
385    }
386
387    void next(Node& i) const {
388      Parent::next(i);
389      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
390    }
391    void next(Edge& i) const {
392      Parent::next(i);
393      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
394    }
395    void nextIn(Edge& i) const {
396      Parent::nextIn(i);
397      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
398    }
399    void nextOut(Edge& i) const {
400      Parent::nextOut(i);
401      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
402    }
403
404    /// This function hides \c n in the graph, i.e. the iteration
405    /// jumps over it. This is done by simply setting the value of \c n 
406    /// to be false in the corresponding node-map.
407    void hide(const Node& n) const { node_filter_map->set(n, false); }
408
409    /// This function hides \c e in the graph, i.e. the iteration
410    /// jumps over it. This is done by simply setting the value of \c e 
411    /// to be false in the corresponding edge-map.
412    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
413
414    /// The value of \c n is set to be true in the node-map which stores
415    /// hide information. If \c n was hidden previuosly, then it is shown
416    /// again
417     void unHide(const Node& n) const { node_filter_map->set(n, true); }
418
419    /// The value of \c e is set to be true in the edge-map which stores
420    /// hide information. If \c e was hidden previuosly, then it is shown
421    /// again
422    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
423
424    /// Returns true if \c n is hidden.
425    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
426
427    /// Returns true if \c n is hidden.
428    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
429
430    /// \warning This is a linear time operation and works only if s
431    /// \c Graph::NodeIt is defined.
432    /// \todo assign tags.
433    int nodeNum() const {
434      int i=0;
435      Node n;
436      for (first(n); n!=INVALID; next(n)) ++i;
437      return i;
438    }
439
440    /// \warning This is a linear time operation and works only if
441    /// \c Graph::EdgeIt is defined.
442    /// \todo assign tags.
443    int edgeNum() const {
444      int i=0;
445      Edge e;
446      for (first(e); e!=INVALID; next(e)) ++i;
447      return i;
448    }
449
450
451  };
452
453  /*! \brief A graph wrapper for hiding nodes and edges from a graph.
454 
455  \warning Graph wrappers are in even more experimental state than the other
456  parts of the lib. Use them at you own risk.
457 
458  This wrapper shows a graph with filtered node-set and
459  edge-set.
460  Given a bool-valued map on the node-set and one on
461  the edge-set of the graph, the iterators show only the objects
462  having true value. We have to note that this does not mean that an
463  induced subgraph is obtained, the node-iterator cares only the filter
464  on the node-set, and the edge-iterators care only the filter on the
465  edge-set.
466  \code
467  typedef SmartGraph Graph;
468  Graph g;
469  typedef Graph::Node Node;
470  typedef Graph::Edge Edge;
471  Node u=g.addNode(); //node of id 0
472  Node v=g.addNode(); //node of id 1
473  Node e=g.addEdge(u, v); //edge of id 0
474  Node f=g.addEdge(v, u); //edge of id 1
475  Graph::NodeMap<bool> nm(g, true);
476  nm.set(u, false);
477  Graph::EdgeMap<bool> em(g, true);
478  em.set(e, false);
479  typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
480  SubGW gw(g, nm, em);
481  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
482  std::cout << ":-)" << std::endl;
483  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
484  \endcode
485  The output of the above code is the following.
486  \code
487  1
488  :-)
489  1
490  \endcode
491  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
492  \c Graph::Node that is why \c g.id(n) can be applied.
493
494  For other examples see also the documentation of NodeSubGraphWrapper and
495  EdgeSubGraphWrapper.
496
497  \author Marton Makai
498  */
499  template<typename _Graph, typename NodeFilterMap,
500           typename EdgeFilterMap>
501  class SubGraphWrapper :
502    public IterableGraphExtender<
503    SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
504  public:
505    typedef _Graph Graph;
506    typedef IterableGraphExtender<
507      SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
508  protected:
509    SubGraphWrapper() { }
510  public:
511    SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
512                    EdgeFilterMap& _edge_filter_map) {
513      setGraph(_graph);
514      setNodeFilterMap(_node_filter_map);
515      setEdgeFilterMap(_edge_filter_map);
516    }
517  };
518
519//   template<typename Graph, typename NodeFilterMap,
520//         typename EdgeFilterMap>
521//   class SubGraphWrapper : public GraphWrapper<Graph> {
522//   public:
523//     typedef GraphWrapper<Graph> Parent;
524//   protected:
525//     NodeFilterMap* node_filter_map;
526//     EdgeFilterMap* edge_filter_map;
527
528//     SubGraphWrapper() : GraphWrapper<Graph>(),
529//                      node_filter_map(0), edge_filter_map(0) { }
530//     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
531//       node_filter_map=&_node_filter_map;
532//     }
533//     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
534//       edge_filter_map=&_edge_filter_map;
535//     }
536   
537//   public:
538//     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
539//                  EdgeFilterMap& _edge_filter_map) :
540//       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
541//       edge_filter_map(&_edge_filter_map) { } 
542
543//     typedef typename GraphWrapper<Graph>::Node Node;
544//     class NodeIt : public Node {
545//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
546//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
547//     public:
548//       NodeIt() { }
549//       NodeIt(Invalid i) : Node(i) { }
550//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
551//      Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
552//      while (*static_cast<Node*>(this)!=INVALID &&
553//             !(*(gw->node_filter_map))[*this])
554//        *(static_cast<Node*>(this))=
555//          ++(typename Graph::NodeIt(*(gw->graph), *this));
556//       }
557//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
558//           const Node& n) :
559//      Node(n), gw(&_gw) { }
560//       NodeIt& operator++() {
561//      *(static_cast<Node*>(this))=
562//        ++(typename Graph::NodeIt(*(gw->graph), *this));
563//      while (*static_cast<Node*>(this)!=INVALID &&
564//             !(*(gw->node_filter_map))[*this])
565//        *(static_cast<Node*>(this))=
566//          ++(typename Graph::NodeIt(*(gw->graph), *this));
567//      return *this;
568//       }
569//     };
570//     typedef typename GraphWrapper<Graph>::Edge Edge;
571//     class OutEdgeIt : public Edge {
572//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
573//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
574//     public:
575//       OutEdgeIt() { }
576//       OutEdgeIt(Invalid i) : Edge(i) { }
577//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
578//      Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
579//      while (*static_cast<Edge*>(this)!=INVALID &&
580//             !(*(gw->edge_filter_map))[*this])
581//        *(static_cast<Edge*>(this))=
582//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
583//       }
584//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
585//           const Edge& e) :
586//      Edge(e), gw(&_gw) { }
587//       OutEdgeIt& operator++() {
588//      *(static_cast<Edge*>(this))=
589//        ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
590//      while (*static_cast<Edge*>(this)!=INVALID &&
591//             !(*(gw->edge_filter_map))[*this])
592//        *(static_cast<Edge*>(this))=
593//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
594//      return *this;
595//       }
596//     };
597//     class InEdgeIt : public Edge {
598//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
599//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
600//     public:
601//       InEdgeIt() { }
602//       //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
603//       InEdgeIt(Invalid i) : Edge(i) { }
604//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
605//      Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
606//      while (*static_cast<Edge*>(this)!=INVALID &&
607//             !(*(gw->edge_filter_map))[*this])
608//        *(static_cast<Edge*>(this))=
609//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
610//       }
611//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
612//           const Edge& e) :
613//      Edge(e), gw(&_gw) { }
614//       InEdgeIt& operator++() {
615//      *(static_cast<Edge*>(this))=
616//        ++(typename Graph::InEdgeIt(*(gw->graph), *this));
617//      while (*static_cast<Edge*>(this)!=INVALID &&
618//             !(*(gw->edge_filter_map))[*this])
619//        *(static_cast<Edge*>(this))=
620//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
621//      return *this;
622//       }
623//     };
624//     class EdgeIt : public Edge {
625//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
626//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
627//     public:
628//       EdgeIt() { }
629//       EdgeIt(Invalid i) : Edge(i) { }
630//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
631//      Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
632//      while (*static_cast<Edge*>(this)!=INVALID &&
633//             !(*(gw->edge_filter_map))[*this])
634//        *(static_cast<Edge*>(this))=
635//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
636//       }
637//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
638//           const Edge& e) :
639//      Edge(e), gw(&_gw) { }
640//       EdgeIt& operator++() {
641//      *(static_cast<Edge*>(this))=
642//        ++(typename Graph::EdgeIt(*(gw->graph), *this));
643//      while (*static_cast<Edge*>(this)!=INVALID &&
644//             !(*(gw->edge_filter_map))[*this])
645//        *(static_cast<Edge*>(this))=
646//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
647//      return *this;
648//       }
649//     };
650
651//     NodeIt& first(NodeIt& i) const {
652//       i=NodeIt(*this); return i;
653//     }
654//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
655//       i=OutEdgeIt(*this, p); return i;
656//     }
657//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
658//       i=InEdgeIt(*this, p); return i;
659//     }
660//     EdgeIt& first(EdgeIt& i) const {
661//       i=EdgeIt(*this); return i;
662//     }
663   
664//     /// This function hides \c n in the graph, i.e. the iteration
665//     /// jumps over it. This is done by simply setting the value of \c n 
666//     /// to be false in the corresponding node-map.
667//     void hide(const Node& n) const { node_filter_map->set(n, false); }
668
669//     /// This function hides \c e in the graph, i.e. the iteration
670//     /// jumps over it. This is done by simply setting the value of \c e 
671//     /// to be false in the corresponding edge-map.
672//     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
673
674//     /// The value of \c n is set to be true in the node-map which stores
675//     /// hide information. If \c n was hidden previuosly, then it is shown
676//     /// again
677//      void unHide(const Node& n) const { node_filter_map->set(n, true); }
678
679//     /// The value of \c e is set to be true in the edge-map which stores
680//     /// hide information. If \c e was hidden previuosly, then it is shown
681//     /// again
682//     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
683
684//     /// Returns true if \c n is hidden.
685//     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
686
687//     /// Returns true if \c n is hidden.
688//     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
689
690//     /// \warning This is a linear time operation and works only if
691//     /// \c Graph::NodeIt is defined.
692//     int nodeNum() const {
693//       int i=0;
694//       for (NodeIt n(*this); n!=INVALID; ++n) ++i;
695//       return i;
696//     }
697
698//     /// \warning This is a linear time operation and works only if
699//     /// \c Graph::EdgeIt is defined.
700//     int edgeNum() const {
701//       int i=0;
702//       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
703//       return i;
704//     }
705
706//     //    KEEP_MAPS(Parent, SubGraphWrapper);
707//   };
708
709
710  /*! \brief A wrapper for hiding nodes from a graph.
711
712  \warning Graph wrappers are in even more experimental state than the other
713  parts of the lib. Use them at you own risk.
714 
715  A wrapper for hiding nodes from a graph.
716  This wrapper specializes SubGraphWrapper in the way that only the node-set
717  can be filtered. Note that this does not mean of considering induced
718  subgraph, the edge-iterators consider the original edge-set.
719  \author Marton Makai
720  */
721  template<typename Graph, typename NodeFilterMap>
722  class NodeSubGraphWrapper :
723    public SubGraphWrapper<Graph, NodeFilterMap,
724                           ConstMap<typename Graph::Edge,bool> > {
725  public:
726    typedef SubGraphWrapper<Graph, NodeFilterMap,
727                            ConstMap<typename Graph::Edge,bool> > Parent;
728  protected:
729    ConstMap<typename Graph::Edge, bool> const_true_map;
730  public:
731    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
732      Parent(), const_true_map(true) {
733      Parent::setGraph(_graph);
734      Parent::setNodeFilterMap(_node_filter_map);
735      Parent::setEdgeFilterMap(const_true_map);
736    }
737  };
738
739
740  /*! \brief A wrapper for hiding edges from a graph.
741
742  \warning Graph wrappers are in even more experimental state than the other
743  parts of the lib. Use them at you own risk.
744 
745  A wrapper for hiding edges from a graph.
746  This wrapper specializes SubGraphWrapper in the way that only the edge-set
747  can be filtered. The usefulness of this wrapper is demonstrated in the
748  problem of searching a maximum number of edge-disjoint shortest paths
749  between
750  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
751  non-negative edge-lengths. Note that
752  the comprehension of the presented solution
753  need's some knowledge from elementary combinatorial optimization.
754
755  If a single shortest path is to be
756  searched between two nodes \c s and \c t, then this can be done easily by
757  applying the Dijkstra algorithm class. What happens, if a maximum number of
758  edge-disjoint shortest paths is to be computed. It can be proved that an
759  edge can be in a shortest path if and only if it is tight with respect to
760  the potential function computed by Dijkstra. Moreover, any path containing
761  only such edges is a shortest one. Thus we have to compute a maximum number
762  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
763  all the tight edges. The computation will be demonstrated on the following
764  graph, which is read from a dimacs file.
765 
766  \dot
767  digraph lemon_dot_example {
768  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
769  n0 [ label="0 (s)" ];
770  n1 [ label="1" ];
771  n2 [ label="2" ];
772  n3 [ label="3" ];
773  n4 [ label="4" ];
774  n5 [ label="5" ];
775  n6 [ label="6 (t)" ];
776  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
777  n5 ->  n6 [ label="9, length:4" ];
778  n4 ->  n6 [ label="8, length:2" ];
779  n3 ->  n5 [ label="7, length:1" ];
780  n2 ->  n5 [ label="6, length:3" ];
781  n2 ->  n6 [ label="5, length:5" ];
782  n2 ->  n4 [ label="4, length:2" ];
783  n1 ->  n4 [ label="3, length:3" ];
784  n0 ->  n3 [ label="2, length:1" ];
785  n0 ->  n2 [ label="1, length:2" ];
786  n0 ->  n1 [ label="0, length:3" ];
787  }
788  \enddot
789
790  \code
791  Graph g;
792  Node s, t;
793  LengthMap length(g);
794
795  readDimacs(std::cin, g, length, s, t);
796
797  cout << "edges with lengths (of form id, source--length->target): " << endl;
798  for(EdgeIt e(g); e!=INVALID; ++e)
799    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
800         << length[e] << "->" << g.id(g.target(e)) << endl;
801
802  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
803  \endcode
804  Next, the potential function is computed with Dijkstra.
805  \code
806  typedef Dijkstra<Graph, LengthMap> Dijkstra;
807  Dijkstra dijkstra(g, length);
808  dijkstra.run(s);
809  \endcode
810  Next, we consrtruct a map which filters the edge-set to the tight edges.
811  \code
812  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
813    TightEdgeFilter;
814  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
815 
816  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
817  SubGW gw(g, tight_edge_filter);
818  \endcode
819  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
820  with a max flow algorithm Preflow.
821  \code
822  ConstMap<Edge, int> const_1_map(1);
823  Graph::EdgeMap<int> flow(g, 0);
824
825  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
826    preflow(gw, s, t, const_1_map, flow);
827  preflow.run();
828  \endcode
829  Last, the output is:
830  \code 
831  cout << "maximum number of edge-disjoint shortest path: "
832       << preflow.flowValue() << endl;
833  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
834       << endl;
835  for(EdgeIt e(g); e!=INVALID; ++e)
836    if (flow[e])
837      cout << " " << g.id(g.source(e)) << "--"
838           << length[e] << "->" << g.id(g.target(e)) << endl;
839  \endcode
840  The program has the following (expected :-)) output:
841  \code
842  edges with lengths (of form id, source--length->target):
843   9, 5--4->6
844   8, 4--2->6
845   7, 3--1->5
846   6, 2--3->5
847   5, 2--5->6
848   4, 2--2->4
849   3, 1--3->4
850   2, 0--1->3
851   1, 0--2->2
852   0, 0--3->1
853  s: 0 t: 6
854  maximum number of edge-disjoint shortest path: 2
855  edges of the maximum number of edge-disjoint shortest s-t paths:
856   9, 5--4->6
857   8, 4--2->6
858   7, 3--1->5
859   4, 2--2->4
860   2, 0--1->3
861   1, 0--2->2
862  \endcode
863
864  \author Marton Makai
865  */
866  template<typename Graph, typename EdgeFilterMap>
867  class EdgeSubGraphWrapper :
868    public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
869                           EdgeFilterMap> {
870  public:
871    typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
872                            EdgeFilterMap> Parent;
873  protected:
874    ConstMap<typename Graph::Node, bool> const_true_map;
875  public:
876    EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
877      Parent(), const_true_map(true) {
878      Parent::setGraph(_graph);
879      Parent::setNodeFilterMap(const_true_map);
880      Parent::setEdgeFilterMap(_edge_filter_map);
881    }
882  };
883
884
885  template<typename Graph>
886  class UndirGraphWrapper : public GraphWrapper<Graph> {
887  public:
888    typedef GraphWrapper<Graph> Parent;
889  protected:
890    UndirGraphWrapper() : GraphWrapper<Graph>() { }
891   
892  public:
893    typedef typename GraphWrapper<Graph>::Node Node;
894    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
895    typedef typename GraphWrapper<Graph>::Edge Edge;
896    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
897
898    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
899
900    class OutEdgeIt {
901      friend class UndirGraphWrapper<Graph>;
902      bool out_or_in; //true iff out
903      typename Graph::OutEdgeIt out;
904      typename Graph::InEdgeIt in;
905    public:
906      OutEdgeIt() { }
907      OutEdgeIt(const Invalid& i) : Edge(i) { }
908      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
909        out_or_in=true; _G.graph->first(out, _n);
910        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
911      }
912      operator Edge() const {
913        if (out_or_in) return Edge(out); else return Edge(in);
914      }
915    };
916
917    typedef OutEdgeIt InEdgeIt;
918
919    using GraphWrapper<Graph>::first;
920    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
921      i=OutEdgeIt(*this, p); return i;
922    }
923
924    using GraphWrapper<Graph>::next;
925
926    OutEdgeIt& next(OutEdgeIt& e) const {
927      if (e.out_or_in) {
928        typename Graph::Node n=this->graph->source(e.out);
929        this->graph->next(e.out);
930        if (!this->graph->valid(e.out)) {
931          e.out_or_in=false; this->graph->first(e.in, n); }
932      } else {
933        this->graph->next(e.in);
934      }
935      return e;
936    }
937
938    Node aNode(const OutEdgeIt& e) const {
939      if (e.out_or_in) return this->graph->source(e); else
940        return this->graph->target(e); }
941    Node bNode(const OutEdgeIt& e) const {
942      if (e.out_or_in) return this->graph->target(e); else
943        return this->graph->source(e); }
944
945    //    KEEP_MAPS(Parent, UndirGraphWrapper);
946
947  };
948 
949//   /// \brief An undirected graph template.
950//   ///
951//   ///\warning Graph wrappers are in even more experimental state than the other
952//   ///parts of the lib. Use them at your own risk.
953//   ///
954//   /// An undirected graph template.
955//   /// This class works as an undirected graph and a directed graph of
956//   /// class \c Graph is used for the physical storage.
957//   /// \ingroup graphs
958  template<typename Graph>
959  class UndirGraph : public UndirGraphWrapper<Graph> {
960    typedef UndirGraphWrapper<Graph> Parent;
961  protected:
962    Graph gr;
963  public:
964    UndirGraph() : UndirGraphWrapper<Graph>() {
965      Parent::setGraph(gr);
966    }
967
968    //    KEEP_MAPS(Parent, UndirGraph);
969  };
970
971 
972  template <typename _Graph,
973            typename ForwardFilterMap, typename BackwardFilterMap>
974  class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
975  public:
976    typedef _Graph Graph;
977    typedef GraphWrapperBase<_Graph> Parent;
978  protected:
979    ForwardFilterMap* forward_filter;
980    BackwardFilterMap* backward_filter;
981    SubBidirGraphWrapperBase() : Parent(),
982                                 forward_filter(0), backward_filter(0) { }
983
984    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
985      forward_filter=&_forward_filter;
986    }
987    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
988      backward_filter=&_backward_filter;
989    }
990
991  public:
992//     SubGraphWrapperBase(Graph& _graph,
993//                      NodeFilterMap& _node_filter_map,
994//                      EdgeFilterMap& _edge_filter_map) :
995//       Parent(&_graph),
996//       node_filter_map(&node_filter_map),
997//       edge_filter_map(&edge_filter_map) { }
998
999    typedef typename Parent::Node Node;
1000    typedef typename _Graph::Edge GraphEdge;
1001    template <typename T> class EdgeMap;
1002    /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
1003    /// _Graph::Edge. It contains an extra bool flag which is true
1004    /// if and only if the
1005    /// edge is the backward version of the original edge.
1006    class Edge : public _Graph::Edge {
1007      friend class SubBidirGraphWrapperBase<
1008        Graph, ForwardFilterMap, BackwardFilterMap>;
1009      template<typename T> friend class EdgeMap;
1010    protected:
1011      bool backward; //true, iff backward
1012    public:
1013      Edge() { }
1014      /// \todo =false is needed, or causes problems?
1015      /// If \c _backward is false, then we get an edge corresponding to the
1016      /// original one, otherwise its oppositely directed pair is obtained.
1017      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
1018        _Graph::Edge(e), backward(_backward) { }
1019      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
1020      bool operator==(const Edge& v) const {
1021        return (this->backward==v.backward &&
1022                static_cast<typename _Graph::Edge>(*this)==
1023                static_cast<typename _Graph::Edge>(v));
1024      }
1025      bool operator!=(const Edge& v) const {
1026        return (this->backward!=v.backward ||
1027                static_cast<typename _Graph::Edge>(*this)!=
1028                static_cast<typename _Graph::Edge>(v));
1029      }
1030    };
1031
1032    void first(Node& i) const {
1033      Parent::first(i);
1034    }
1035
1036    void first(Edge& i) const {
1037      Parent::first(i);
1038      i.backward=false;
1039      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1040             !(*forward_filter)[i]) Parent::next(i);
1041      if (*static_cast<GraphEdge*>(&i)==INVALID) {
1042        Parent::first(i);
1043        i.backward=true;
1044        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1045               !(*backward_filter)[i]) Parent::next(i);
1046      }
1047    }
1048
1049    void firstIn(Edge& i, const Node& n) const {
1050      Parent::firstIn(i, n);
1051      i.backward=false;
1052      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1053             !(*forward_filter)[i]) Parent::nextOut(i);
1054      if (*static_cast<GraphEdge*>(&i)==INVALID) {
1055        Parent::firstOut(i, n);
1056        i.backward=true;
1057        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1058               !(*backward_filter)[i]) Parent::nextOut(i);
1059      }
1060    }
1061
1062    void firstOut(Edge& i, const Node& n) const {
1063      Parent::firstOut(i, n);
1064      i.backward=false;
1065      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1066             !(*forward_filter)[i]) Parent::nextOut(i);
1067      if (*static_cast<GraphEdge*>(&i)==INVALID) {
1068        Parent::firstIn(i, n);
1069        i.backward=true;
1070        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1071               !(*backward_filter)[i]) Parent::nextIn(i);
1072      }
1073    }
1074
1075    void next(Node& i) const {
1076      Parent::next(i);
1077    }
1078
1079    void next(Edge& i) const {
1080      if (!(i.backward)) {
1081        Parent::next(i);
1082        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1083               !(*forward_filter)[i]) Parent::next(i);
1084        if (*static_cast<GraphEdge*>(&i)==INVALID) {
1085          Parent::first(i);
1086          i.backward=true;
1087          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1088                 !(*backward_filter)[i]) Parent::next(i);
1089        }
1090      } else {
1091        Parent::next(i);
1092        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1093               !(*backward_filter)[i]) Parent::next(i);
1094      }
1095    }
1096
1097    void nextIn(Edge& i) const {
1098      if (!(i.backward)) {
1099        Node n=Parent::target(i);
1100        Parent::nextIn(i);
1101        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1102               !(*forward_filter)[i]) Parent::nextIn(i);
1103        if (*static_cast<GraphEdge*>(&i)==INVALID) {
1104          Parent::firstOut(i, n);
1105          i.backward=true;
1106          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1107                 !(*backward_filter)[i]) Parent::nextOut(i);
1108        }
1109      } else {
1110        Parent::nextOut(i);
1111        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1112               !(*backward_filter)[i]) Parent::nextOut(i);
1113      }
1114    }
1115
1116    void nextOut(Edge& i) const {
1117      if (!(i.backward)) {
1118        Node n=Parent::source(i);
1119        Parent::nextOut(i);
1120        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1121               !(*forward_filter)[i]) Parent::nextOut(i);
1122        if (*static_cast<GraphEdge*>(&i)==INVALID) {
1123          Parent::firstIn(i, n);
1124          i.backward=true;
1125          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1126                 !(*backward_filter)[i]) Parent::nextIn(i);
1127        }
1128      } else {
1129        Parent::nextIn(i);
1130        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1131               !(*backward_filter)[i]) Parent::nextIn(i);
1132      }
1133    }
1134
1135    Node source(Edge e) const {
1136      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
1137    Node target(Edge e) const {
1138      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
1139
1140    /// Gives back the opposite edge.
1141    Edge opposite(const Edge& e) const {
1142      Edge f=e;
1143      f.backward=!f.backward;
1144      return f;
1145    }
1146
1147    /// \warning This is a linear time operation and works only if
1148    /// \c Graph::EdgeIt is defined.
1149    /// \todo hmm
1150    int edgeNum() const {
1151      int i=0;
1152      Edge e;
1153      for (first(e); e!=INVALID; next(e)) ++i;
1154      return i;
1155    }
1156
1157    bool forward(const Edge& e) const { return !e.backward; }
1158    bool backward(const Edge& e) const { return e.backward; }
1159
1160    template <typename T>
1161    /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
1162    /// _Graph::EdgeMap one for the forward edges and
1163    /// one for the backward edges.
1164    class EdgeMap {
1165      template <typename TT> friend class EdgeMap;
1166      typename _Graph::template EdgeMap<T> forward_map, backward_map;
1167    public:
1168      typedef T Value;
1169      typedef Edge Key;
1170
1171      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
1172              ForwardFilterMap, BackwardFilterMap>& g) :
1173        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1174
1175      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
1176              ForwardFilterMap, BackwardFilterMap>& g, T a) :
1177        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1178     
1179      void set(Edge e, T a) {
1180        if (!e.backward)
1181          forward_map.set(e, a);
1182        else
1183          backward_map.set(e, a);
1184      }
1185
1186//       typename _Graph::template EdgeMap<T>::ConstReference
1187//       operator[](Edge e) const {
1188//      if (!e.backward)
1189//        return forward_map[e];
1190//      else
1191//        return backward_map[e];
1192//       }
1193
1194//      typename _Graph::template EdgeMap<T>::Reference
1195      T operator[](Edge e) const {
1196        if (!e.backward)
1197          return forward_map[e];
1198        else
1199          return backward_map[e];
1200      }
1201
1202      void update() {
1203        forward_map.update();
1204        backward_map.update();
1205      }
1206    };
1207
1208  };
1209
1210
1211  ///\brief A wrapper for composing a subgraph of a
1212  /// bidirected graph made from a directed one.
1213  ///
1214  /// A wrapper for composing a subgraph of a
1215  /// bidirected graph made from a directed one.
1216  ///
1217  ///\warning Graph wrappers are in even more experimental state than the other
1218  ///parts of the lib. Use them at you own risk.
1219  ///
1220  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1221  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1222  /// reversing its orientation. We are given moreover two bool valued
1223  /// maps on the edge-set,
1224  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1225  /// SubBidirGraphWrapper implements the graph structure with node-set
1226  /// \f$V\f$ and edge-set
1227  /// \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$.
1228  /// The purpose of writing + instead of union is because parallel
1229  /// edges can arise. (Similarly, antiparallel edges also can arise).
1230  /// In other words, a subgraph of the bidirected graph obtained, which
1231  /// is given by orienting the edges of the original graph in both directions.
1232  /// As the oppositely directed edges are logically different,
1233  /// the maps are able to attach different values for them.
1234  ///
1235  /// An example for such a construction is \c RevGraphWrapper where the
1236  /// forward_filter is everywhere false and the backward_filter is
1237  /// everywhere true. We note that for sake of efficiency,
1238  /// \c RevGraphWrapper is implemented in a different way.
1239  /// But BidirGraphWrapper is obtained from
1240  /// SubBidirGraphWrapper by considering everywhere true
1241  /// valued maps both for forward_filter and backward_filter.
1242  /// Finally, one of the most important applications of SubBidirGraphWrapper
1243  /// is ResGraphWrapper, which stands for the residual graph in directed
1244  /// flow and circulation problems.
1245  /// As wrappers usually, the SubBidirGraphWrapper implements the
1246  /// above mentioned graph structure without its physical storage,
1247  /// that is the whole stuff is stored in constant memory.
1248  template<typename _Graph,
1249           typename ForwardFilterMap, typename BackwardFilterMap>
1250  class SubBidirGraphWrapper :
1251    public IterableGraphExtender<
1252    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1253  public:
1254    typedef _Graph Graph;
1255    typedef IterableGraphExtender<
1256      SubBidirGraphWrapperBase<
1257      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1258  protected:
1259    SubBidirGraphWrapper() { }
1260  public:
1261    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
1262                         BackwardFilterMap& _backward_filter) {
1263      setGraph(_graph);
1264      setForwardFilterMap(_forward_filter);
1265      setBackwardFilterMap(_backward_filter);
1266    }
1267  };
1268
1269//   template<typename Graph,
1270//         typename ForwardFilterMap, typename BackwardFilterMap>
1271//   class SubBidirGraphWrapper : public GraphWrapper<Graph> {
1272//   public:
1273//     typedef GraphWrapper<Graph> Parent;
1274//   protected:
1275//     ForwardFilterMap* forward_filter;
1276//     BackwardFilterMap* backward_filter;
1277
1278//     SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
1279//     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
1280//       forward_filter=&_forward_filter;
1281//     }
1282//     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
1283//       backward_filter=&_backward_filter;
1284//     }
1285
1286//   public:
1287
1288//     SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
1289//                       BackwardFilterMap& _backward_filter) :
1290//       GraphWrapper<Graph>(_graph),
1291//       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
1292//     SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
1293//                       ForwardFilterMap, BackwardFilterMap>& gw) :
1294//       Parent(gw),
1295//       forward_filter(gw.forward_filter),
1296//       backward_filter(gw.backward_filter) { }
1297
1298//     class Edge;
1299//     class OutEdgeIt;
1300//     friend class Edge;
1301//     friend class OutEdgeIt;
1302
1303//     template<typename T> class EdgeMap;
1304
1305//     typedef typename GraphWrapper<Graph>::Node Node;
1306
1307//     typedef typename Graph::Edge GraphEdge;
1308//     /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
1309//     /// Graph::Edge. It contains an extra bool flag which is true
1310//     /// if and only if the
1311//     /// edge is the backward version of the original edge.
1312//     class Edge : public Graph::Edge {
1313//       friend class SubBidirGraphWrapper<Graph,
1314//                                      ForwardFilterMap, BackwardFilterMap>;
1315//       template<typename T> friend class EdgeMap;
1316//     protected:
1317//       bool backward; //true, iff backward
1318//     public:
1319//       Edge() { }
1320//       /// \todo =false is needed, or causes problems?
1321//       /// If \c _backward is false, then we get an edge corresponding to the
1322//       /// original one, otherwise its oppositely directed pair is obtained.
1323//       Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
1324//      Graph::Edge(e), backward(_backward) { }
1325//       Edge(Invalid i) : Graph::Edge(i), backward(true) { }
1326//       bool operator==(const Edge& v) const {
1327//      return (this->backward==v.backward &&
1328//              static_cast<typename Graph::Edge>(*this)==
1329//              static_cast<typename Graph::Edge>(v));
1330//       }
1331//       bool operator!=(const Edge& v) const {
1332//      return (this->backward!=v.backward ||
1333//              static_cast<typename Graph::Edge>(*this)!=
1334//              static_cast<typename Graph::Edge>(v));
1335//       }
1336//     };
1337
1338//     class OutEdgeIt : public Edge {
1339//       friend class SubBidirGraphWrapper<Graph,
1340//                                      ForwardFilterMap, BackwardFilterMap>;
1341//     protected:
1342//       const SubBidirGraphWrapper<Graph,
1343//                               ForwardFilterMap, BackwardFilterMap>* gw;
1344//     public:
1345//       OutEdgeIt() { }
1346//       OutEdgeIt(Invalid i) : Edge(i) { }
1347//       OutEdgeIt(const SubBidirGraphWrapper<Graph,
1348//              ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
1349//      Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
1350//      while (*static_cast<GraphEdge*>(this)!=INVALID &&
1351//             !(*(gw->forward_filter))[*this])
1352//        *(static_cast<GraphEdge*>(this))=
1353//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1354//      if (*static_cast<GraphEdge*>(this)==INVALID) {
1355//        *static_cast<Edge*>(this)=
1356//          Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
1357//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1358//               !(*(gw->backward_filter))[*this])
1359//          *(static_cast<GraphEdge*>(this))=
1360//            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1361//      }
1362//       }
1363//       OutEdgeIt(const SubBidirGraphWrapper<Graph,
1364//              ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1365//      Edge(e), gw(&_gw) { }
1366//       OutEdgeIt& operator++() {
1367//      if (!this->backward) {
1368//        Node n=gw->source(*this);
1369//        *(static_cast<GraphEdge*>(this))=
1370//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1371//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1372//               !(*(gw->forward_filter))[*this])
1373//          *(static_cast<GraphEdge*>(this))=
1374//            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1375//        if (*static_cast<GraphEdge*>(this)==INVALID) {
1376//          *static_cast<Edge*>(this)=
1377//            Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
1378//          while (*static_cast<GraphEdge*>(this)!=INVALID &&
1379//                 !(*(gw->backward_filter))[*this])
1380//            *(static_cast<GraphEdge*>(this))=
1381//              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1382//        }
1383//      } else {
1384//        *(static_cast<GraphEdge*>(this))=
1385//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1386//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1387//               !(*(gw->backward_filter))[*this])
1388//          *(static_cast<GraphEdge*>(this))=
1389//            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1390//      }
1391//      return *this;
1392//       }
1393//     };
1394
1395//     class InEdgeIt : public Edge {
1396//       friend class SubBidirGraphWrapper<Graph,
1397//                                      ForwardFilterMap, BackwardFilterMap>;
1398//     protected:
1399//       const SubBidirGraphWrapper<Graph,
1400//                               ForwardFilterMap, BackwardFilterMap>* gw;
1401//     public:
1402//       InEdgeIt() { }
1403//       InEdgeIt(Invalid i) : Edge(i) { }
1404//       InEdgeIt(const SubBidirGraphWrapper<Graph,
1405//             ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
1406//      Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
1407//      while (*static_cast<GraphEdge*>(this)!=INVALID &&
1408//             !(*(gw->forward_filter))[*this])
1409//        *(static_cast<GraphEdge*>(this))=
1410//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1411//      if (*static_cast<GraphEdge*>(this)==INVALID) {
1412//        *static_cast<Edge*>(this)=
1413//          Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
1414//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1415//               !(*(gw->backward_filter))[*this])
1416//          *(static_cast<GraphEdge*>(this))=
1417//            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1418//      }
1419//       }
1420//       InEdgeIt(const SubBidirGraphWrapper<Graph,
1421//             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1422//      Edge(e), gw(&_gw) { }
1423//       InEdgeIt& operator++() {
1424//      if (!this->backward) {
1425//        Node n=gw->source(*this);
1426//        *(static_cast<GraphEdge*>(this))=
1427//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1428//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1429//               !(*(gw->forward_filter))[*this])
1430//          *(static_cast<GraphEdge*>(this))=
1431//            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1432//        if (*static_cast<GraphEdge*>(this)==INVALID) {
1433//          *static_cast<Edge*>(this)=
1434//            Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
1435//          while (*static_cast<GraphEdge*>(this)!=INVALID &&
1436//                 !(*(gw->backward_filter))[*this])
1437//            *(static_cast<GraphEdge*>(this))=
1438//              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1439//        }
1440//      } else {
1441//        *(static_cast<GraphEdge*>(this))=
1442//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1443//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1444//               !(*(gw->backward_filter))[*this])
1445//          *(static_cast<GraphEdge*>(this))=
1446//            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1447//      }
1448//      return *this;
1449//       }
1450//     };
1451
1452//     class EdgeIt : public Edge {
1453//       friend class SubBidirGraphWrapper<Graph,
1454//                                      ForwardFilterMap, BackwardFilterMap>;
1455//     protected:
1456//       const SubBidirGraphWrapper<Graph,
1457//                               ForwardFilterMap, BackwardFilterMap>* gw;
1458//     public:
1459//       EdgeIt() { }
1460//       EdgeIt(Invalid i) : Edge(i) { }
1461//       EdgeIt(const SubBidirGraphWrapper<Graph,
1462//           ForwardFilterMap, BackwardFilterMap>& _gw) :
1463//      Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
1464//      while (*static_cast<GraphEdge*>(this)!=INVALID &&
1465//             !(*(gw->forward_filter))[*this])
1466//        *(static_cast<GraphEdge*>(this))=
1467//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
1468//      if (*static_cast<GraphEdge*>(this)==INVALID) {
1469//        *static_cast<Edge*>(this)=
1470//          Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1471//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1472//               !(*(gw->backward_filter))[*this])
1473//          *(static_cast<GraphEdge*>(this))=
1474//            ++(typename Graph::EdgeIt(*(gw->graph), *this));
1475//      }
1476//       }
1477//       EdgeIt(const SubBidirGraphWrapper<Graph,
1478//           ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1479//      Edge(e), gw(&_gw) { }
1480//       EdgeIt& operator++() {
1481//      if (!this->backward) {
1482//        *(static_cast<GraphEdge*>(this))=
1483//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
1484//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1485//               !(*(gw->forward_filter))[*this])
1486//          *(static_cast<GraphEdge*>(this))=
1487//            ++(typename Graph::EdgeIt(*(gw->graph), *this));
1488//        if (*static_cast<GraphEdge*>(this)==INVALID) {
1489//          *static_cast<Edge*>(this)=
1490//            Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1491//          while (*static_cast<GraphEdge*>(this)!=INVALID &&
1492//                 !(*(gw->backward_filter))[*this])
1493//            *(static_cast<GraphEdge*>(this))=
1494//              ++(typename Graph::EdgeIt(*(gw->graph), *this));
1495//        }
1496//      } else {
1497//        *(static_cast<GraphEdge*>(this))=
1498//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
1499//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
1500//               !(*(gw->backward_filter))[*this])
1501//          *(static_cast<GraphEdge*>(this))=
1502//            ++(typename Graph::EdgeIt(*(gw->graph), *this));
1503//      }
1504//      return *this;
1505//       }
1506//     };
1507
1508// //     using GraphWrapper<Graph>::first;
1509// //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1510// //       i=OutEdgeIt(*this, p); return i;
1511// //     }
1512// //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1513// //       i=InEdgeIt(*this, p); return i;
1514// //     }
1515// //     EdgeIt& first(EdgeIt& i) const {
1516// //       i=EdgeIt(*this); return i;
1517// //     }
1518 
1519
1520//     Node source(Edge e) const {
1521//       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
1522//     Node target(Edge e) const {
1523//       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
1524
1525//     /// Gives back the opposite edge.
1526//     Edge opposite(const Edge& e) const {
1527//       Edge f=e;
1528//       f.backward=!f.backward;
1529//       return f;
1530//     }
1531
1532//     /// \warning This is a linear time operation and works only if
1533//     /// \c Graph::EdgeIt is defined.
1534//     int edgeNum() const {
1535//       int i=0;
1536//       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1537//       return i;
1538//     }
1539
1540//     bool forward(const Edge& e) const { return !e.backward; }
1541//     bool backward(const Edge& e) const { return e.backward; }
1542
1543
1544//     template <typename T>
1545//     /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1546//     /// Graph::EdgeMap one for the forward edges and
1547//     /// one for the backward edges.
1548//     class EdgeMap {
1549//       template <typename TT> friend class EdgeMap;
1550//       typename Graph::template EdgeMap<T> forward_map, backward_map;
1551//     public:
1552//       typedef T Value;
1553//       typedef Edge Key;
1554
1555//       EdgeMap(const SubBidirGraphWrapper<Graph,
1556//            ForwardFilterMap, BackwardFilterMap>& g) :
1557//      forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1558
1559//       EdgeMap(const SubBidirGraphWrapper<Graph,
1560//            ForwardFilterMap, BackwardFilterMap>& g, T a) :
1561//      forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1562
1563//       template <typename TT>
1564//       EdgeMap(const EdgeMap<TT>& copy)
1565//      : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
1566
1567//       template <typename TT>
1568//       EdgeMap& operator=(const EdgeMap<TT>& copy) {
1569//      forward_map = copy.forward_map;
1570//      backward_map = copy.backward_map;
1571//      return *this;
1572//       }
1573     
1574//       void set(Edge e, T a) {
1575//      if (!e.backward)
1576//        forward_map.set(e, a);
1577//      else
1578//        backward_map.set(e, a);
1579//       }
1580
1581//       typename Graph::template EdgeMap<T>::ConstReference
1582//       operator[](Edge e) const {
1583//      if (!e.backward)
1584//        return forward_map[e];
1585//      else
1586//        return backward_map[e];
1587//       }
1588
1589//       typename Graph::template EdgeMap<T>::Reference
1590//       operator[](Edge e) {
1591//      if (!e.backward)
1592//        return forward_map[e];
1593//      else
1594//        return backward_map[e];
1595//       }
1596
1597//       void update() {
1598//      forward_map.update();
1599//      backward_map.update();
1600//       }
1601//     };
1602
1603
1604//     //    KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
1605
1606//   };
1607
1608
1609  ///\brief A wrapper for composing bidirected graph from a directed one.
1610  ///
1611  ///\warning Graph wrappers are in even more experimental state than the other
1612  ///parts of the lib. Use them at you own risk.
1613  ///
1614  /// A wrapper for composing bidirected graph from a directed one.
1615  /// A bidirected graph is composed over the directed one without physical
1616  /// storage. As the oppositely directed edges are logically different ones
1617  /// the maps are able to attach different values for them.
1618  template<typename Graph>
1619  class BidirGraphWrapper :
1620    public SubBidirGraphWrapper<
1621    Graph,
1622    ConstMap<typename Graph::Edge, bool>,
1623    ConstMap<typename Graph::Edge, bool> > {
1624  public:
1625    typedef  SubBidirGraphWrapper<
1626      Graph,
1627      ConstMap<typename Graph::Edge, bool>,
1628      ConstMap<typename Graph::Edge, bool> > Parent;
1629  protected:
1630    ConstMap<typename Graph::Edge, bool> cm;
1631
1632    BidirGraphWrapper() : Parent(), cm(true) {
1633      Parent::setForwardFilterMap(cm);
1634      Parent::setBackwardFilterMap(cm);
1635    }
1636  public:
1637    BidirGraphWrapper(Graph& _graph) : Parent() {
1638      Parent::setGraph(_graph);
1639      Parent::setForwardFilterMap(cm);
1640      Parent::setBackwardFilterMap(cm);
1641    }
1642
1643    int edgeNum() const {
1644      return 2*this->graph->edgeNum();
1645    }
1646    //    KEEP_MAPS(Parent, BidirGraphWrapper);
1647  };
1648
1649
1650  /// \brief A bidirected graph template.
1651  ///
1652  ///\warning Graph wrappers are in even more experimental state than the other
1653  ///parts of the lib. Use them at you own risk.
1654  ///
1655  /// A bidirected graph template.
1656  /// Such a bidirected graph stores each pair of oppositely directed edges
1657  /// ones in the memory, i.e. a directed graph of type
1658  /// \c Graph is used for that.
1659  /// As the oppositely directed edges are logically different ones
1660  /// the maps are able to attach different values for them.
1661  /// \ingroup graphs
1662  template<typename Graph>
1663  class BidirGraph : public BidirGraphWrapper<Graph> {
1664  public:
1665    typedef UndirGraphWrapper<Graph> Parent;
1666  protected:
1667    Graph gr;
1668  public:
1669    BidirGraph() : BidirGraphWrapper<Graph>() {
1670      Parent::setGraph(gr);
1671    }
1672    //    KEEP_MAPS(Parent, BidirGraph);
1673  };
1674
1675
1676
1677  template<typename Graph, typename Number,
1678           typename CapacityMap, typename FlowMap>
1679  class ResForwardFilter {
1680    //    const Graph* graph;
1681    const CapacityMap* capacity;
1682    const FlowMap* flow;
1683  public:
1684    ResForwardFilter(/*const Graph& _graph, */
1685                     const CapacityMap& _capacity, const FlowMap& _flow) :
1686      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1687    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1688    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1689    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1690    bool operator[](const typename Graph::Edge& e) const {
1691      return (Number((*flow)[e]) < Number((*capacity)[e]));
1692    }
1693  };
1694
1695  template<typename Graph, typename Number,
1696           typename CapacityMap, typename FlowMap>
1697  class ResBackwardFilter {
1698    const CapacityMap* capacity;
1699    const FlowMap* flow;
1700  public:
1701    ResBackwardFilter(/*const Graph& _graph,*/
1702                      const CapacityMap& _capacity, const FlowMap& _flow) :
1703      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1704    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1705    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1706    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1707    bool operator[](const typename Graph::Edge& e) const {
1708      return (Number(0) < Number((*flow)[e]));
1709    }
1710  };
1711
1712 
1713  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1714
1715  ///\warning Graph wrappers are in even more experimental state than the other
1716  ///parts of the lib. Use them at you own risk.
1717  ///
1718  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1719  template<typename Graph, typename Number,
1720           typename CapacityMap, typename FlowMap>
1721  class ResGraphWrapper :
1722    public SubBidirGraphWrapper<
1723    Graph,
1724    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1725    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1726  public:
1727    typedef SubBidirGraphWrapper<
1728      Graph,
1729      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1730      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1731  protected:
1732    const CapacityMap* capacity;
1733    FlowMap* flow;
1734    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1735    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1736    ResGraphWrapper() : Parent(),
1737                        capacity(0), flow(0) { }
1738    void setCapacityMap(const CapacityMap& _capacity) {
1739      capacity=&_capacity;
1740      forward_filter.setCapacity(_capacity);
1741      backward_filter.setCapacity(_capacity);
1742    }
1743    void setFlowMap(FlowMap& _flow) {
1744      flow=&_flow;
1745      forward_filter.setFlow(_flow);
1746      backward_filter.setFlow(_flow);
1747    }
1748  public:
1749    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1750                       FlowMap& _flow) :
1751      Parent(), capacity(&_capacity), flow(&_flow),
1752      forward_filter(/*_graph,*/ _capacity, _flow),
1753      backward_filter(/*_graph,*/ _capacity, _flow) {
1754      Parent::setGraph(_graph);
1755      Parent::setForwardFilterMap(forward_filter);
1756      Parent::setBackwardFilterMap(backward_filter);
1757    }
1758
1759    typedef typename Parent::Edge Edge;
1760
1761    void augment(const Edge& e, Number a) const {
1762      if (Parent::forward(e)) 
1763        flow->set(e, (*flow)[e]+a);
1764      else 
1765        flow->set(e, (*flow)[e]-a);
1766    }
1767
1768    /// \brief Residual capacity map.
1769    ///
1770    /// In generic residual graphs the residual capacity can be obtained
1771    /// as a map.
1772    class ResCap {
1773    protected:
1774      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1775    public:
1776      typedef Number Value;
1777      typedef Edge Key;
1778      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1779             _res_graph) : res_graph(&_res_graph) { }
1780      Number operator[](const Edge& e) const {
1781        if (res_graph->forward(e))
1782          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1783        else
1784          return (*(res_graph->flow))[e];
1785      }
1786    };
1787
1788    //    KEEP_MAPS(Parent, ResGraphWrapper);
1789  };
1790
1791
1792
1793  template <typename _Graph, typename FirstOutEdgesMap>
1794  class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1795  public:
1796    typedef _Graph Graph;
1797    typedef GraphWrapperBase<_Graph> Parent;
1798  protected:
1799    FirstOutEdgesMap* first_out_edges;
1800    ErasingFirstGraphWrapperBase() : Parent(),
1801                                     first_out_edges(0) { }
1802
1803    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1804      first_out_edges=&_first_out_edges;
1805    }
1806
1807  public:
1808
1809    typedef typename Parent::Node Node;
1810    typedef typename Parent::Edge Edge;
1811
1812//     using Parent::first;
1813//     void first(Node& i) const {
1814//       Parent::first(i);
1815//       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1816//     }
1817//     void first(Edge& i) const {
1818//       Parent::first(i);
1819//       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
1820//     }
1821//     void firstIn(Edge& i, const Node& n) const {
1822//       Parent::firstIn(i, n);
1823//       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
1824//     }
1825    void firstOut(Edge& i, const Node& n) const {
1826      i=(*first_out_edges)[n];
1827    }
1828
1829    void erase(const Edge& e) const {
1830      Node n=source(e);
1831      Edge f=e;
1832      Parent::nextOut(f);
1833      first_out_edges->set(n, f);
1834    }   
1835//     void next(Node& i) const {
1836//       Parent::next(i);
1837//       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1838//     }
1839//     void next(Edge& i) const {
1840//       Parent::next(i);
1841//       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
1842//     }
1843//     void nextIn(Edge& i) const {
1844//       Parent::nextIn(i);
1845//       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
1846//     }
1847//     void nextOut(Edge& i) const {
1848//       Parent::nextOut(i);
1849//       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
1850//     }
1851  };
1852
1853
1854  /// For blocking flows.
1855
1856  ///\warning Graph wrappers are in even more experimental state than the other
1857  ///parts of the lib. Use them at you own risk.
1858  ///
1859  /// This graph wrapper is used for on-the-fly
1860  /// Dinits blocking flow computations.
1861  /// For each node, an out-edge is stored which is used when the
1862  /// \code
1863  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1864  /// \endcode
1865  /// is called.
1866  ///
1867  /// \author Marton Makai
1868  template <typename _Graph, typename FirstOutEdgesMap>
1869  class ErasingFirstGraphWrapper :
1870    public IterableGraphExtender<
1871    ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1872  public:
1873    typedef _Graph Graph;
1874    typedef IterableGraphExtender<
1875      ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1876    ErasingFirstGraphWrapper(Graph& _graph,
1877                             FirstOutEdgesMap& _first_out_edges) {
1878      setGraph(_graph);
1879      setFirstOutEdgesMap(_first_out_edges);
1880    }
1881//     using GraphWrapper<Graph>::first;
1882//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1883//       i=OutEdgeIt(*this, p); return i;
1884//     }
1885  };
1886//   template<typename Graph, typename FirstOutEdgesMap>
1887//   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1888//   public:
1889//     typedef GraphWrapper<Graph> Parent;
1890//   protected:
1891//     FirstOutEdgesMap* first_out_edges;
1892//   public:
1893//     ErasingFirstGraphWrapper(Graph& _graph,
1894//                           FirstOutEdgesMap& _first_out_edges) :
1895//       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1896
1897//     typedef typename GraphWrapper<Graph>::Node Node;
1898//     typedef typename GraphWrapper<Graph>::Edge Edge;
1899//     class OutEdgeIt : public Edge {
1900//       friend class GraphWrapper<Graph>;
1901//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1902//       const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1903//     public:
1904//       OutEdgeIt() { }
1905//       OutEdgeIt(Invalid i) : Edge(i) { }
1906//       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1907//              const Node& n) :
1908//      Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1909//       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1910//              const Edge& e) :
1911//      Edge(e), gw(&_gw) { }
1912//       OutEdgeIt& operator++() {
1913//      *(static_cast<Edge*>(this))=
1914//        ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1915//      return *this;
1916//       }
1917//     };
1918
1919// //     using GraphWrapper<Graph>::first;
1920// //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1921// //       i=OutEdgeIt(*this, p); return i;
1922// //     }
1923//     void erase(const Edge& e) const {
1924//       Node n=source(e);
1925//       typename Graph::OutEdgeIt f(*Parent::graph, n);
1926//       ++f;
1927//       first_out_edges->set(n, f);
1928//     }
1929
1930//     //    KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1931//   };
1932
1933  ///@}
1934
1935} //namespace lemon
1936
1937#endif //LEMON_GRAPH_WRAPPER_H
1938
Note: See TracBrowser for help on using the repository browser.