COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 998:89969b303727

Last change on this file since 998:89969b303727 was 998:89969b303727, checked in by marci, 16 years ago

ErasingFirstGraphWrapper?

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