COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 786:d7b3b13b9df6

Last change on this file since 786:d7b3b13b9df6 was 777:a82713ed19f3, checked in by marci, 17 years ago

graph_wrapper.h is ready for hugo 0.2

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