COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_wrapper.h @ 992:10d378f2821c

Last change on this file since 992:10d378f2821c was 992:10d378f2821c, checked in by marci, 16 years ago

GraphWrapper? changes for factory

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