COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 331:f5461f8bc59b

Last change on this file since 331:f5461f8bc59b was 330:7ac0d4e8a31c, checked in by marci, 22 years ago

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