COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 376:5c12f3515452

Last change on this file since 376:5c12f3515452 was 376:5c12f3515452, checked in by marci, 17 years ago

preflow mods

File size: 39.9 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
4
5#include <invalid.h>
6#include <iter_map.h>
7
8namespace hugo {
9
10  /// Graph wrappers
11
12  /// A main parts of HUGOlib are the different graph structures,
13  /// generic graph algorithms, graph concepts which couple these, and
14  /// graph wrappers. While the previous ones are more or less clear, the
15  /// latter notion needs further explanation.
16  /// Graph wrappers are graph classes which serve for considering graph
17  /// structures in different ways. A short example makes the notion much
18  /// clearer.
19  /// Suppose that we have an instance \c g of a directed graph
20  /// type say \c ListGraph and an algorithm
21  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
22  /// is needed to run on the reversely oriented graph.
23  /// It may be expensive (in time or in memory usage) to copy
24  /// \c g with the reverse orientation.
25  /// Thus, a wrapper class
26  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
27  /// The code looks as follows
28  /// \code
29  /// ListGraph g;
30  /// RevGraphWrapper<ListGraph> rgw(g);
31  /// int result=algorithm(rgw);
32  /// \endcode
33  /// After running the algorithm, the original graph \c g
34  /// remains untouched. Thus the graph wrapper used above is to consider the
35  /// original graph with reverse orientation.
36  /// This techniques gives rise to an elegant code, and
37  /// based on stable graph wrappers, complex algorithms can be
38  /// implemented easily.
39  /// In flow, circulation and bipartite matching problems, the residual
40  /// graph is of particular importance. Combining a wrapper implementing
41  /// this, shortest path algorithms and minimum mean cycle algorithms,
42  /// a range of weighted and cardinality optimization algorithms can be
43  /// obtained. For lack of space, for other examples,
44  /// the interested user is referred to the detailed documentation of graph
45  /// wrappers.
46  /// The behavior of graph wrappers can be very different. Some of them keep
47  /// capabilities of the original graph while in other cases this would be
48  /// meaningless. This means that the concepts that they are a model of depend
49  /// on the graph wrapper, and the wrapped graph(s).
50  /// If an edge of \c rgw is deleted, this is carried out by
51  /// deleting the corresponding edge of \c g. But for a residual
52  /// graph, this operation has no sense.
53  /// Let we stand one more example here to simplify your work.
54  /// wrapper class
55  /// \code template<typename Graph> class RevGraphWrapper; \endcode
56  /// has constructor
57  /// <tt> RevGraphWrapper(Graph& _g)</tt>.
58  /// This means that in a situation,
59  /// when a <tt> const ListGraph& </tt> reference to a graph is given,
60  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
61  /// \code
62  /// int algorithm1(const ListGraph& g) {
63  ///   RevGraphWrapper<const ListGraph> rgw(g);
64  ///   return algorithm2(rgw);
65  /// }
66  /// \endcode
67  template<typename Graph>
68  class GraphWrapper {
69  protected:
70    Graph* graph;
71 
72  public:
73    typedef Graph BaseGraph;
74    typedef Graph ParentGraph;
75
76//     GraphWrapper() : graph(0) { }
77    GraphWrapper(Graph& _graph) : graph(&_graph) { }
78//     void setGraph(Graph& _graph) { graph=&_graph; }
79//     Graph& getGraph() const { return *graph; }
80 
81//    typedef typename Graph::Node Node;
82    class Node : public Graph::Node {
83      friend class GraphWrapper<Graph>;
84    public:
85      Node() { }
86      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
87      Node(const Invalid& i) : Graph::Node(i) { }
88    };
89    class NodeIt {
90      friend class GraphWrapper<Graph>;
91      typename Graph::NodeIt n;
92     public:
93      NodeIt() { }
94      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
95      NodeIt(const Invalid& i) : n(i) { }
96      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
97      operator Node() const { return Node(typename Graph::Node(n)); }
98    };
99//    typedef typename Graph::Edge Edge;
100    class Edge : public Graph::Edge {
101      friend class GraphWrapper<Graph>;
102    public:
103      Edge() { }
104      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
105      Edge(const Invalid& i) : Graph::Edge(i) { }
106    };
107    class OutEdgeIt {
108      friend class GraphWrapper<Graph>;
109      typename Graph::OutEdgeIt e;
110    public:
111      OutEdgeIt() { }
112      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
113      OutEdgeIt(const Invalid& i) : e(i) { }
114      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
115        e(*(_G.graph), typename Graph::Node(_n)) { }
116      operator Edge() const { return Edge(typename Graph::Edge(e)); }
117    };
118    class InEdgeIt {
119      friend class GraphWrapper<Graph>;
120      typename Graph::InEdgeIt e;
121    public:
122      InEdgeIt() { }
123      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
124      InEdgeIt(const Invalid& i) : e(i) { }
125      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
126        e(*(_G.graph), typename Graph::Node(_n)) { }
127      operator Edge() const { return Edge(typename Graph::Edge(e)); }
128    };
129    //typedef typename Graph::SymEdgeIt SymEdgeIt;
130    class EdgeIt {
131      friend class GraphWrapper<Graph>;
132      typename Graph::EdgeIt e;
133    public:
134      EdgeIt() { }
135      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
136      EdgeIt(const Invalid& i) : e(i) { }
137      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
138      operator Edge() const { return Edge(typename Graph::Edge(e)); }
139    };
140   
141    NodeIt& first(NodeIt& i) const {
142      i=NodeIt(*this); return i;
143    }
144    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
145      i=OutEdgeIt(*this, p); return i;
146    }
147    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
148      i=InEdgeIt(*this, p); return i;
149    }
150    EdgeIt& first(EdgeIt& i) const {
151      i=EdgeIt(*this); return i;
152    }
153
154    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
155    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
156    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
157    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
158
159    Node head(const Edge& e) const {
160      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
161    Node tail(const Edge& e) const {
162      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
163
164    bool valid(const Node& n) const {
165      return graph->valid(static_cast<typename Graph::Node>(n)); }
166    bool valid(const Edge& e) const {
167      return graph->valid(static_cast<typename Graph::Edge>(e)); }
168
169    int nodeNum() const { return graph->nodeNum(); }
170    int edgeNum() const { return graph->edgeNum(); }
171 
172    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
173    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
174    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
175    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
176 
177    Node addNode() const { return Node(graph->addNode()); }
178    Edge addEdge(const Node& tail, const Node& head) const {
179      return Edge(graph->addEdge(tail, head)); }
180
181    void erase(const Node& i) const { graph->erase(i); }
182    void erase(const Edge& i) const { graph->erase(i); }
183 
184    void clear() const { graph->clear(); }
185   
186    template<typename T> class NodeMap : public Graph::NodeMap<T> {
187    public:
188      NodeMap(const GraphWrapper<Graph>& _G) : 
189        Graph::NodeMap<T>(*(_G.graph)) { }
190      NodeMap(const GraphWrapper<Graph>& _G, T a) :
191        Graph::NodeMap<T>(*(_G.graph), a) { }
192    };
193
194    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
195    public:
196      EdgeMap(const GraphWrapper<Graph>& _G) : 
197        Graph::EdgeMap<T>(*(_G.graph)) { }
198      EdgeMap(const GraphWrapper<Graph>& _G, T a) :
199        Graph::EdgeMap<T>(*(_G.graph), a) { }
200    };
201  };
202
203  /// A graph wrapper which reverses the orientation of the edges.
204
205  /// A graph wrapper which reverses the orientation of the edges.
206  template<typename Graph>
207  class RevGraphWrapper : public GraphWrapper<Graph> {
208  public:
209
210    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
211
212    typedef typename GraphWrapper<Graph>::Node Node;
213    typedef typename GraphWrapper<Graph>::Edge Edge;
214    //If Graph::OutEdgeIt is not defined
215    //and we do not want to use RevGraphWrapper::InEdgeIt,
216    //the typdef techinque does not work.
217    //Unfortunately all the typedefs are instantiated in templates.
218    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
219    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
220
221    class OutEdgeIt {
222      friend class GraphWrapper<Graph>;
223      friend class RevGraphWrapper<Graph>;
224      typename Graph::OutEdgeIt e;
225    public:
226      OutEdgeIt() { }
227      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
228      OutEdgeIt(const Invalid& i) : e(i) { }
229      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
230        e(*(_G.graph), typename Graph::Node(_n)) { }
231      operator Edge() const { return Edge(typename Graph::Edge(e)); }
232    };
233    class InEdgeIt {
234      friend class GraphWrapper<Graph>;
235      friend class RevGraphWrapper<Graph>;
236      typename Graph::InEdgeIt e;
237    public:
238      InEdgeIt() { }
239      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
240      InEdgeIt(const Invalid& i) : e(i) { }
241      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
242        e(*(_G.graph), typename Graph::Node(_n)) { }
243      operator Edge() const { return Edge(typename Graph::Edge(e)); }
244    };
245
246    using GraphWrapper<Graph>::first;
247    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
248      i=OutEdgeIt(*this, p); return i;
249    }
250    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
251      i=InEdgeIt(*this, p); return i;
252    }
253
254    using GraphWrapper<Graph>::next;
255    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
256    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
257
258    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
259    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
260    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
261    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
262  };
263
264  /// Wrapper for hiding nodes and edges from a graph.
265 
266  /// This wrapper shows a graph with filtered node-set and
267  /// edge-set. The quick brown fox iterator jumps over
268  /// the lazy dog nodes or edges if the values for them are false
269  /// in the bool maps.
270  template<typename Graph, typename NodeFilterMap,
271           typename EdgeFilterMap>
272  class SubGraphWrapper : public GraphWrapper<Graph> {
273  protected:
274    NodeFilterMap* node_filter_map;
275    EdgeFilterMap* edge_filter_map;
276  public:
277
278    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
279                    EdgeFilterMap& _edge_filter_map) :
280      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
281      edge_filter_map(&_edge_filter_map) { } 
282
283    typedef typename GraphWrapper<Graph>::Node Node;
284    class NodeIt {
285      friend class GraphWrapper<Graph>;
286      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
287      typename Graph::NodeIt n;
288     public:
289      NodeIt() { }
290      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
291      NodeIt(const Invalid& i) : n(i) { }
292      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
293        n(*(_G.graph)) {
294        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
295          _G.graph->next(n);
296      }
297      operator Node() const { return Node(typename Graph::Node(n)); }
298    };
299    typedef typename GraphWrapper<Graph>::Edge Edge;
300    class OutEdgeIt {
301      friend class GraphWrapper<Graph>;
302      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
303      typename Graph::OutEdgeIt e;
304    public:
305      OutEdgeIt() { }
306      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
307      OutEdgeIt(const Invalid& i) : e(i) { }
308      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
309                const Node& _n) :
310        e(*(_G.graph), typename Graph::Node(_n)) {
311        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
312          _G.graph->next(e);
313      }
314      operator Edge() const { return Edge(typename Graph::Edge(e)); }
315    };
316    class InEdgeIt {
317      friend class GraphWrapper<Graph>;
318      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
319      typename Graph::InEdgeIt e;
320    public:
321      InEdgeIt() { }
322      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
323      InEdgeIt(const Invalid& i) : e(i) { }
324      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
325               const Node& _n) :
326        e(*(_G.graph), typename Graph::Node(_n)) {
327        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
328          _G.graph->next(e);
329      }
330      operator Edge() const { return Edge(typename Graph::Edge(e)); }
331    };
332    //typedef typename Graph::SymEdgeIt SymEdgeIt;
333    class EdgeIt {
334      friend class GraphWrapper<Graph>;
335      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
336      typename Graph::EdgeIt e;
337    public:
338      EdgeIt() { }
339      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
340      EdgeIt(const Invalid& i) : e(i) { }
341      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
342        e(*(_G.graph)) {
343        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
344          _G.graph->next(e);
345      }
346      operator Edge() const { return Edge(typename Graph::Edge(e)); }
347    };
348
349    NodeIt& first(NodeIt& i) const {
350      i=NodeIt(*this); return i;
351    }
352    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
353      i=OutEdgeIt(*this, p); return i;
354    }
355    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
356      i=InEdgeIt(*this, p); return i;
357    }
358    EdgeIt& first(EdgeIt& i) const {
359      i=EdgeIt(*this); return i;
360    }
361   
362    NodeIt& next(NodeIt& i) const {
363      graph->next(i.n);
364      while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
365      return i;
366    }
367    OutEdgeIt& next(OutEdgeIt& i) const {
368      graph->next(i.e);
369      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
370      return i;
371    }
372    InEdgeIt& next(InEdgeIt& i) const {
373      graph->next(i.e);
374      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
375      return i;
376    }
377    EdgeIt& next(EdgeIt& i) const {
378      graph->next(i.e);
379      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
380      return i;
381    }
382
383    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
384    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
385    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
386    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
387
388    ///\todo
389    ///Some doki, please.
390    void hide(const Node& n) const { node_filter_map->set(n, false); }
391    ///\todo
392    ///Some doki, please.
393    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
394
395    ///\todo
396    ///Some doki, please.
397    void unHide(const Node& n) const { node_filter_map->set(n, true); }
398    ///\todo
399    ///Some doki, please.
400    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
401
402    ///\todo
403    ///Some doki, please.
404    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
405    ///\todo
406    ///Some doki, please.
407    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
408  };
409
410  /// A wrapper for forgetting the orientation of a graph.
411
412  /// A wrapper for getting an undirected graph by forgetting
413  /// the orientation of a directed one.
414  template<typename Graph>
415  class UndirGraphWrapper : public GraphWrapper<Graph> {
416  public:
417    typedef typename GraphWrapper<Graph>::Node Node;
418    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
419    typedef typename GraphWrapper<Graph>::Edge Edge;
420    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
421
422    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
423
424    class OutEdgeIt {
425      friend class UndirGraphWrapper<Graph>;
426      bool out_or_in; //true iff out
427      typename Graph::OutEdgeIt out;
428      typename Graph::InEdgeIt in;
429    public:
430      OutEdgeIt() { }
431      OutEdgeIt(const Invalid& i) : Edge(i) { }
432      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
433        out_or_in=true; _G.graph->first(out, _n);
434        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
435      }
436      operator Edge() const {
437        if (out_or_in) return Edge(out); else return Edge(in);
438      }
439    };
440
441//FIXME InEdgeIt
442    typedef OutEdgeIt InEdgeIt;
443
444    using GraphWrapper<Graph>::first;
445//     NodeIt& first(NodeIt& i) const {
446//       i=NodeIt(*this); return i;
447//     }
448    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
449      i=OutEdgeIt(*this, p); return i;
450    }
451//FIXME
452//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
453//       i=InEdgeIt(*this, p); return i;
454//     }
455//     EdgeIt& first(EdgeIt& i) const {
456//       i=EdgeIt(*this); return i;
457//     }
458
459    using GraphWrapper<Graph>::next;
460//     NodeIt& next(NodeIt& n) const {
461//       GraphWrapper<Graph>::next(n);
462//       return n;
463//     }
464    OutEdgeIt& next(OutEdgeIt& e) const {
465      if (e.out_or_in) {
466        typename Graph::Node n=graph->tail(e.out);
467        graph->next(e.out);
468        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
469      } else {
470        graph->next(e.in);
471      }
472      return e;
473    }
474    //FIXME InEdgeIt
475//     EdgeIt& next(EdgeIt& e) const {
476//       GraphWrapper<Graph>::next(n);
477// //      graph->next(e.e);
478//       return e;
479//     }
480
481    Node aNode(const OutEdgeIt& e) const {
482      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
483    Node bNode(const OutEdgeIt& e) const {
484      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
485  };
486 
487  /// A wrapper for composing the residual graph for directed flow and circulation problems.
488
489  /// A wrapper for composing the residual graph for directed flow and circulation problems.
490  template<typename Graph, typename Number,
491           typename CapacityMap, typename FlowMap>
492  class ResGraphWrapper : public GraphWrapper<Graph> {
493  protected:
494    const CapacityMap* capacity;
495    FlowMap* flow;
496  public:
497
498    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
499                    FlowMap& _flow) :
500      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
501
502    class Edge;
503    class OutEdgeIt;
504    friend class Edge;
505    friend class OutEdgeIt;
506
507    typedef typename GraphWrapper<Graph>::Node Node;
508    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
509    class Edge : public Graph::Edge {
510      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
511    protected:
512      bool forward; //true, iff forward
513//      typename Graph::Edge e;
514    public:
515      Edge() { }
516      Edge(const typename Graph::Edge& _e, bool _forward) :
517        Graph::Edge(_e), forward(_forward) { }
518      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
519//the unique invalid iterator
520      friend bool operator==(const Edge& u, const Edge& v) {
521        return (v.forward==u.forward &&
522                static_cast<typename Graph::Edge>(u)==
523                static_cast<typename Graph::Edge>(v));
524      }
525      friend bool operator!=(const Edge& u, const Edge& v) {
526        return (v.forward!=u.forward ||
527                static_cast<typename Graph::Edge>(u)!=
528                static_cast<typename Graph::Edge>(v));
529      }
530    };
531
532    class OutEdgeIt {
533      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
534    protected:
535      typename Graph::OutEdgeIt out;
536      typename Graph::InEdgeIt in;
537      bool forward;
538    public:
539      OutEdgeIt() { }
540      //FIXME
541//      OutEdgeIt(const Edge& e) : Edge(e) { }
542      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
543//the unique invalid iterator
544      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
545        forward=true;
546        resG.graph->first(out, v);
547        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
548        if (!resG.graph->valid(out)) {
549          forward=false;
550          resG.graph->first(in, v);
551          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
552        }
553      }
554      operator Edge() const {
555//      Edge e;
556//      e.forward=this->forward;
557//      if (this->forward) e=out; else e=in;
558//      return e;
559        if (this->forward)
560          return Edge(out, this->forward);
561        else
562          return Edge(in, this->forward);
563      }
564    };
565
566    class InEdgeIt {
567      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
568    protected:
569      typename Graph::OutEdgeIt out;
570      typename Graph::InEdgeIt in;
571      bool forward;
572    public:
573      InEdgeIt() { }
574      //FIXME
575//      OutEdgeIt(const Edge& e) : Edge(e) { }
576      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
577//the unique invalid iterator
578      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
579        forward=true;
580        resG.graph->first(in, v);
581        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
582        if (!resG.graph->valid(in)) {
583          forward=false;
584          resG.graph->first(out, v);
585          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
586        }
587      }
588      operator Edge() const {
589//      Edge e;
590//      e.forward=this->forward;
591//      if (this->forward) e=out; else e=in;
592//      return e;
593        if (this->forward)
594          return Edge(in, this->forward);
595        else
596          return Edge(out, this->forward);
597      }
598    };
599
600    class EdgeIt {
601      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
602    protected:
603      typename Graph::EdgeIt e;
604      bool forward;
605    public:
606      EdgeIt() { }
607      EdgeIt(const Invalid& i) : e(i), forward(false) { }
608      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
609        forward=true;
610        resG.graph->first(e);
611        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
612        if (!resG.graph->valid(e)) {
613          forward=false;
614          resG.graph->first(e);
615          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
616        }
617      }
618      operator Edge() const {
619        return Edge(e, this->forward);
620      }
621    };
622
623    using GraphWrapper<Graph>::first;
624//     NodeIt& first(NodeIt& i) const {
625//       i=NodeIt(*this); return i;
626//     }
627    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
628      i=OutEdgeIt(*this, p); return i;
629    }
630//    FIXME not tested
631    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
632      i=InEdgeIt(*this, p); return i;
633    }
634    EdgeIt& first(EdgeIt& i) const {
635      i=EdgeIt(*this); return i;
636    }
637 
638    using GraphWrapper<Graph>::next;
639//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
640    OutEdgeIt& next(OutEdgeIt& e) const {
641      if (e.forward) {
642        Node v=graph->aNode(e.out);
643        graph->next(e.out);
644        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
645        if (!graph->valid(e.out)) {
646          e.forward=false;
647          graph->first(e.in, v);
648          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
649        }
650      } else {
651        graph->next(e.in);
652        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
653      }
654      return e;
655    }
656//     FIXME Not tested
657    InEdgeIt& next(InEdgeIt& e) const {
658      if (e.forward) {
659        Node v=graph->aNode(e.in);
660        graph->next(e.in);
661        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
662        if (!graph->valid(e.in)) {
663          e.forward=false;
664          graph->first(e.out, v);
665          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
666        }
667      } else {
668        graph->next(e.out);
669        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
670      }
671      return e;
672    }
673    EdgeIt& next(EdgeIt& e) const {
674      if (e.forward) {
675        graph->next(e.e);
676        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
677        if (!graph->valid(e.e)) {
678          e.forward=false;
679          graph->first(e.e);
680          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
681        }
682      } else {
683        graph->next(e.e);
684        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
685      }
686      return e;
687    }
688
689    Node tail(Edge e) const {
690      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
691    Node head(Edge e) const {
692      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
693
694    Node aNode(OutEdgeIt e) const {
695      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
696    Node bNode(OutEdgeIt e) const {
697      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
698
699    Node aNode(InEdgeIt e) const {
700      return ((e.forward) ? graph->aNode(e.in) : graph->aNode(e.out)); }
701    Node bNode(InEdgeIt e) const {
702      return ((e.forward) ? graph->bNode(e.in) : graph->bNode(e.out)); }
703
704//    int nodeNum() const { return graph->nodeNum(); }
705    //FIXME
706    void edgeNum() const { }
707    //int edgeNum() const { return graph->edgeNum(); }
708
709
710//    int id(Node v) const { return graph->id(v); }
711
712    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
713    bool valid(Edge e) const {
714      return graph->valid(e);
715        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
716    }
717
718    void augment(const Edge& e, Number a) const {
719      if (e.forward) 
720//      flow->set(e.out, flow->get(e.out)+a);
721        flow->set(e, (*flow)[e]+a);
722      else 
723//      flow->set(e.in, flow->get(e.in)-a);
724        flow->set(e, (*flow)[e]-a);
725    }
726
727    Number resCap(const Edge& e) const {
728      if (e.forward)
729//      return (capacity->get(e.out)-flow->get(e.out));
730        return ((*capacity)[e]-(*flow)[e]);
731      else
732//      return (flow->get(e.in));
733        return ((*flow)[e]);
734    }
735
736//     Number resCap(typename Graph::OutEdgeIt out) const {
737// //      return (capacity->get(out)-flow->get(out));
738//       return ((*capacity)[out]-(*flow)[out]);
739//     }
740   
741//     Number resCap(typename Graph::InEdgeIt in) const {
742// //      return (flow->get(in));
743//       return ((*flow)[in]);
744//     }
745
746    template <typename T>
747    class EdgeMap {
748      typename Graph::EdgeMap<T> forward_map, backward_map;
749    public:
750      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
751      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
752      void set(Edge e, T a) {
753        if (e.forward)
754          forward_map.set(e.out, a);
755        else
756          backward_map.set(e.in, a);
757      }
758      T operator[](Edge e) const {
759        if (e.forward)
760          return forward_map[e.out];
761        else
762          return backward_map[e.in];
763      }
764//       T get(Edge e) const {
765//      if (e.out_or_in)
766//        return forward_map.get(e.out);
767//      else
768//        return backward_map.get(e.in);
769//       }
770    };
771  };
772
773  /// ErasingFirstGraphWrapper for blocking flows.
774
775  /// ErasingFirstGraphWrapper for blocking flows.
776  template<typename Graph, typename FirstOutEdgesMap>
777  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
778  protected:
779    FirstOutEdgesMap* first_out_edges;
780  public:
781    ErasingFirstGraphWrapper(Graph& _graph,
782                             FirstOutEdgesMap& _first_out_edges) :
783      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
784
785    typedef typename GraphWrapper<Graph>::Node Node;
786//     class NodeIt {
787//       friend class GraphWrapper<Graph>;
788//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
789//       typename Graph::NodeIt n;
790//      public:
791//       NodeIt() { }
792//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
793//       NodeIt(const Invalid& i) : n(i) { }
794//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
795//      n(*(_G.graph)) { }
796//       operator Node() const { return Node(typename Graph::Node(n)); }
797//     };
798    typedef typename GraphWrapper<Graph>::Edge Edge;
799    class OutEdgeIt {
800      friend class GraphWrapper<Graph>;
801      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
802//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
803      typename Graph::OutEdgeIt e;
804    public:
805      OutEdgeIt() { }
806      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
807      OutEdgeIt(const Invalid& i) : e(i) { }
808      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
809                const Node& _n) :
810        e((*_G.first_out_edges)[_n]) { }
811      operator Edge() const { return Edge(typename Graph::Edge(e)); }
812    };
813    class InEdgeIt {
814      friend class GraphWrapper<Graph>;
815      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
816//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
817      typename Graph::InEdgeIt e;
818    public:
819      InEdgeIt() { }
820      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
821      InEdgeIt(const Invalid& i) : e(i) { }
822      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
823               const Node& _n) :
824        e(*(_G.graph), typename Graph::Node(_n)) { }
825      operator Edge() const { return Edge(typename Graph::Edge(e)); }
826    };
827    //typedef typename Graph::SymEdgeIt SymEdgeIt;
828    class EdgeIt {
829      friend class GraphWrapper<Graph>;
830      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
831//      typedef typename Graph::EdgeIt GraphEdgeIt;
832      typename Graph::EdgeIt e;
833    public:
834      EdgeIt() { }
835      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
836      EdgeIt(const Invalid& i) : e(i) { }
837      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
838        e(*(_G.graph)) { }
839      operator Edge() const { return Edge(typename Graph::Edge(e)); }
840    };
841
842    using GraphWrapper<Graph>::first;
843//     NodeIt& first(NodeIt& i) const {
844//       i=NodeIt(*this); return i;
845//     }
846    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
847      i=OutEdgeIt(*this, p); return i;
848    }
849    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
850      i=InEdgeIt(*this, p); return i;
851    }
852    EdgeIt& first(EdgeIt& i) const {
853      i=EdgeIt(*this); return i;
854    }
855
856    using GraphWrapper<Graph>::next;
857//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
858    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
859    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
860    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
861   
862    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
863    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
864    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
865    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
866
867    void erase(const OutEdgeIt& e) const {
868      OutEdgeIt f=e;
869      this->next(f);
870      first_out_edges->set(this->tail(e), f.e);
871    }
872  };
873
874  /// A wrapper for composing a bipartite graph.
875  /// \c _graph have to be a reference to a graph of type \c Graph
876  /// and \c _s_false_t_true_map is an \c IterableBoolMap
877  /// reference containing the elements for the
878  /// color classes S and T. \c _graph is to be referred to an undirected
879  /// graph or a directed graph with edges oriented from S to T.
880  template<typename Graph>
881  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
882    typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
883    SFalseTTrueMap* s_false_t_true_map;
884   
885  public:
886    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
887      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
888    }
889    typedef typename GraphWrapper<Graph>::Node Node;
890    //using GraphWrapper<Graph>::NodeIt;
891    typedef typename GraphWrapper<Graph>::Edge Edge;
892    //using GraphWrapper<Graph>::EdgeIt;
893    class SNodeIt {
894      Node n;
895    public:
896      SNodeIt() { }
897      SNodeIt(const Invalid& i) : n(i) { }
898      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
899        _G.s_false_t_true_map->first(n, false);
900      }
901      operator Node() const { return n; }
902    };
903    class TNodeIt {
904      Node n;
905    public:
906      TNodeIt() { }
907      TNodeIt(const Invalid& i) : n(i) { }
908      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
909        _G.s_false_t_true_map->first(n, true);
910      }
911      operator Node() const { return n; }
912    };
913    class OutEdgeIt {
914    public:
915      typename Graph::OutEdgeIt e;
916    public:
917      OutEdgeIt() { }
918      OutEdgeIt(const Invalid& i) : e(i) { }
919      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
920        if (!(*(_G.s_false_t_true_map))[_n])
921          e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
922        else
923          e=INVALID;
924      }
925      operator Edge() const { return Edge(typename Graph::Edge(e)); }
926    };
927    class InEdgeIt {
928    public:
929      typename Graph::InEdgeIt e;
930    public:
931      InEdgeIt() { }
932      InEdgeIt(const Invalid& i) : e(i) { }
933      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
934        if ((*(_G.s_false_t_true_map))[_n])
935          e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
936        else
937          e=INVALID;
938      }
939      operator Edge() const { return Edge(typename Graph::Edge(e)); }
940    };
941
942    using GraphWrapper<Graph>::first;
943    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
944    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
945
946    using GraphWrapper<Graph>::next;
947    SNodeIt& next(SNodeIt& n) const {
948      this->s_false_t_true_map->next(n); return n;
949    }
950    TNodeIt& next(TNodeIt& n) const {
951      this->s_false_t_true_map->next(n); return n;
952    }
953
954    Node tail(const Edge& e) {
955      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
956        return Node(this->graph->tail(e));
957      else
958        return Node(this->graph->head(e));     
959    }
960    Node head(const Edge& e) {
961      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
962        return Node(this->graph->head(e));
963      else
964        return Node(this->graph->tail(e));     
965    }
966
967    Node aNode(const OutEdgeIt& e) const {
968      return Node(this->graph->aNode(e.e));
969    }
970    Node aNode(const InEdgeIt& e) const {
971      return Node(this->graph->aNode(e.e));
972    }
973    Node bNode(const OutEdgeIt& e) const {
974      return Node(this->graph->bNode(e.e));
975    }
976    Node bNode(const InEdgeIt& e) const {
977      return Node(this->graph->bNode(e.e));
978    }
979  };
980
981
982
983//   /// experimentral, do not try it.
984//   template<typename Graph>
985//   class stGraphWrapper : public GraphWrapper<Graph> {
986//   public:
987//     class Node;
988//     class NodeIt;
989//     class Edge;
990//     class OutEdgeIt;
991//     class InEdgeIt;
992//     class EdgeIt;
993
994//     const Node s;
995//     const Node t;
996
997//     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),
998//                                  s(INVALID, 1), t(INVALID, 2) { }
999
1000//     class Node : public Graph::Node {
1001//       friend class GraphWrapper<Graph>;
1002//       friend class stGraphWrapper<Graph>;
1003//     protected:
1004//       int spec; //0 if real node, 1 iff s, 2 iff t
1005//     public:
1006//       Node() { }
1007//       Node(const typename Graph::Node& _n, int _spec=0) :
1008//      Graph::Node(_n), spec(_spec) { }
1009//       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
1010//       //invalid: (invalid, 2);
1011//     };
1012
1013//     class NodeIt {
1014//       friend class GraphWrapper<Graph>;
1015//       friend class stGraphWrapper<Graph>;
1016//       typename Graph::NodeIt n;
1017//       int spec;
1018//      public:
1019//       NodeIt() { }
1020//       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :
1021//      n(_n), spec(_spec) { }
1022//       NodeIt(const Invalid& i) : n(i), spec(2) { }
1023//       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1024//      if (!_G->valid(n)) spec=1;
1025//       }
1026//       operator Node() const { return Node(n, spec); }
1027//     };
1028// //    typedef typename Graph::Edge Edge;
1029//     class Edge : public Graph::Edge {
1030//       friend class GraphWrapper<Graph>;
1031//       friend class stGraphWrapper<Graph>;
1032//       Node tail_spec;
1033//       Node head_spec;
1034//     public:
1035//       Edge() { }
1036//       Edge(const typename Graph::Edge& _e) :
1037//      Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {
1038//      //a tail-t es a head-et real node-ra csinaljuk
1039//       }
1040//       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
1041//     };
1042//     class OutEdgeIt {
1043//       friend class GraphWrapper<Graph>;
1044//       friend class stGraphWrapper<Graph>;
1045//       typename Graph::OutEdgeIt e;
1046//       Node tail_spec;
1047//       Node head_spec;
1048//     public:
1049//       OutEdgeIt() { }
1050//       OutEdgeIt(const typename Graph::OutEdgeIt& _e) :
1051//      e(_e), tail_spec(i, 0), head_spec(i, 0) {
1052//      //a tail-t es a head-et real node-ra csinaljuk
1053//       }
1054//       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
1055//       //invalid: (barmi, 0, 2)
1056//       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
1057//      switch (_n.spec) {
1058//      case 0 :
1059//        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
1060//        _tail.spec=0;
1061//        _head.spec=0;
1062//        if (!_G.graph->valid(e)) spec=1;
1063//        break;
1064//      case 1:
1065//        e=INVALID;
1066//        _tail.spec=1;
1067//        _head(_G.graph->first(typename Graph::NodeIt()));
1068//        if _head.spec==1
1069//        break;
1070//      };
1071       
1072//        }
1073//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1074//     };
1075//     class InEdgeIt {
1076//       friend class GraphWrapper<Graph>;
1077//       typename Graph::InEdgeIt e;
1078//     public:
1079//       InEdgeIt() { }
1080//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1081//       InEdgeIt(const Invalid& i) : e(i) { }
1082//       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1083//      e(*(_G.graph), typename Graph::Node(_n)) { }
1084//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1085//     };
1086//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1087//     class EdgeIt {
1088//       friend class GraphWrapper<Graph>;
1089//       typename Graph::EdgeIt e;
1090//     public:
1091//       EdgeIt() { }
1092//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1093//       EdgeIt(const Invalid& i) : e(i) { }
1094//       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
1095//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1096//     };
1097   
1098//     NodeIt& first(NodeIt& i) const {
1099//       i=NodeIt(*this); return i;
1100//     }
1101//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1102//       i=OutEdgeIt(*this, p); return i;
1103//     }
1104//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1105//       i=InEdgeIt(*this, p); return i;
1106//     }
1107//     EdgeIt& first(EdgeIt& i) const {
1108//       i=EdgeIt(*this); return i;
1109//     }
1110
1111//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1112//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1113//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1114//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
1115
1116//     Node head(const Edge& e) const {
1117//       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1118//     Node tail(const Edge& e) const {
1119//       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1120
1121//     bool valid(const Node& n) const {
1122//       return graph->valid(static_cast<typename Graph::Node>(n)); }
1123//     bool valid(const Edge& e) const {
1124//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
1125
1126//     int nodeNum() const { return graph->nodeNum(); }
1127//     int edgeNum() const { return graph->edgeNum(); }
1128 
1129//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1130//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1131//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1132//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1133 
1134//     Node addNode() const { return Node(graph->addNode()); }
1135//     Edge addEdge(const Node& tail, const Node& head) const {
1136//       return Edge(graph->addEdge(tail, head)); }
1137
1138//     void erase(const Node& i) const { graph->erase(i); }
1139//     void erase(const Edge& i) const { graph->erase(i); }
1140 
1141//     void clear() const { graph->clear(); }
1142   
1143//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1144//     public:
1145//       NodeMap(const GraphWrapper<Graph>& _G) : 
1146//      Graph::NodeMap<T>(*(_G.graph)) { }
1147//       NodeMap(const GraphWrapper<Graph>& _G, T a) :
1148//      Graph::NodeMap<T>(*(_G.graph), a) { }
1149//     };
1150
1151//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1152//     public:
1153//       EdgeMap(const GraphWrapper<Graph>& _G) : 
1154//      Graph::EdgeMap<T>(*(_G.graph)) { }
1155//       EdgeMap(const GraphWrapper<Graph>& _G, T a) :
1156//      Graph::EdgeMap<T>(*(_G.graph), a) { }
1157//     };
1158//   };
1159
1160} //namespace hugo
1161
1162#endif //HUGO_GRAPH_WRAPPER_H
1163
Note: See TracBrowser for help on using the repository browser.