COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 774:4297098d9677

Last change on this file since 774:4297098d9677 was 774:4297098d9677, checked in by Alpar Juttner, 17 years ago

Merge back the whole branches/hugo++ to trunk.

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