COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 739:3bb5553ec41b

Last change on this file since 739:3bb5553ec41b was 739:3bb5553ec41b, checked in by marci, 20 years ago

GraphWrapper::id(const Node&), GraphWrapper::id(const Edge&) function,
'cause I need it.

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