# source:lemon-0.x/src/hugo/graph_wrapper.h@792:147eb3a58706

Last change on this file since 792:147eb3a58706 was 792:147eb3a58706, checked in by marci, 19 years ago

Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.

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