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 @ 323:58bc28afea63

Last change on this file since 323:58bc28afea63 was 323:58bc28afea63, checked in by marci, 20 years ago

gw, kiszedtem ami nem kell
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, typename FlowMap, typename CapacityMap>
900  class ResGraphWrapper : public GraphWrapper<Graph> {
901  protected:
902//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
903//    typedef typename Graph::InEdgeIt GraphInEdgeIt;
904//    typedef typename Graph::Edge GraphEdge;
905    FlowMap* flow;
906    const CapacityMap* capacity;
907  public:
908
909    ResGraphWrapper(Graph& _graph, FlowMap& _flow,
910                    const CapacityMap& _capacity) :
911      GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
912
913    class Edge;
914    class OutEdgeIt;
915    friend class Edge;
916    friend class OutEdgeIt;
917
918    typedef typename GraphWrapper<Graph>::Node Node;
919    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
920    class Edge : public Graph::Edge {
921      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
922    protected:
923      bool forward; //true, iff forward
924//      typename Graph::Edge e;
925    public:
926      Edge() { }
927      Edge(const typename Graph::Edge& _e, bool _forward) :
928        Graph::Edge(_e), forward(_forward) { }
929      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
930//the unique invalid iterator
931      friend bool operator==(const Edge& u, const Edge& v) {
932        return (v.forward==u.forward &&
933                static_cast<typename Graph::Edge>(u)==
934                static_cast<typename Graph::Edge>(v));
935      }
936      friend bool operator!=(const Edge& u, const Edge& v) {
937        return (v.forward!=u.forward ||
938                static_cast<typename Graph::Edge>(u)!=
939                static_cast<typename Graph::Edge>(v));
940      }
941    };
942//     class Edge {
943//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
944//     protected:
945//       bool out_or_in; //true, iff out
946//       GraphOutEdgeIt out;
947//       GraphInEdgeIt in;
948//     public:
949//       Edge() : out_or_in(true) { }
950//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
951// //       bool valid() const {
952// //   return out_or_in && out.valid() || in.valid(); }
953//       friend bool operator==(const Edge& u, const Edge& v) {
954//      if (v.out_or_in)
955//        return (u.out_or_in && u.out==v.out);
956//      else
957//        return (!u.out_or_in && u.in==v.in);
958//       }
959//       friend bool operator!=(const Edge& u, const Edge& v) {
960//      if (v.out_or_in)
961//        return (!u.out_or_in || u.out!=v.out);
962//      else
963//        return (u.out_or_in || u.in!=v.in);
964//       }
965//       operator GraphEdge() const {
966//      if (out_or_in) return(out); else return(in);
967//       }
968//     };
969    class OutEdgeIt {
970      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
971    protected:
972      typename Graph::OutEdgeIt out;
973      typename Graph::InEdgeIt in;
974      bool forward;
975    public:
976      OutEdgeIt() { }
977      //FIXME
978//      OutEdgeIt(const Edge& e) : Edge(e) { }
979      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
980//the unique invalid iterator
981      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
982        forward=true;
983        resG.graph->first(out, v);
984        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
985        if (!resG.graph->valid(out)) {
986          forward=false;
987          resG.graph->first(in, v);
988          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
989        }
990      }
991      operator Edge() const {
992//      Edge e;
993//      e.forward=this->forward;
994//      if (this->forward) e=out; else e=in;
995//      return e;
996        if (this->forward)
997          return Edge(out, this->forward);
998        else
999          return Edge(in, this->forward);
1000      }
1001    };
1002//     class OutEdgeIt : public Edge {
1003//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1004//     public:
1005//       OutEdgeIt() { }
1006//       //FIXME
1007//       OutEdgeIt(const Edge& e) : Edge(e) { }
1008//       OutEdgeIt(const Invalid& i) : Edge(i) { }
1009//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1010//      resG.graph->first(out, v);
1011//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1012//      if (!resG.graph->valid(out)) {
1013//        out_or_in=0;
1014//        resG.graph->first(in, v);
1015//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1016//      }
1017//       }
1018//     public:
1019//       OutEdgeIt& operator++() {
1020//      if (out_or_in) {
1021//        Node v=/*resG->*/G->aNode(out);
1022//        ++out;
1023//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1024//        if (!out.valid()) {
1025//          out_or_in=0;
1026//          G->first(in, v);
1027//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1028//        }
1029//      } else {
1030//        ++in;
1031//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1032//      }
1033//      return *this;
1034//       }
1035//    };
1036
1037    //FIXME This is just for having InEdgeIt
1038//    class InEdgeIt : public Edge { };
1039
1040    class InEdgeIt {
1041      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1042    protected:
1043      typename Graph::OutEdgeIt out;
1044      typename Graph::InEdgeIt in;
1045      bool forward;
1046    public:
1047      InEdgeIt() { }
1048      //FIXME
1049//      OutEdgeIt(const Edge& e) : Edge(e) { }
1050      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1051//the unique invalid iterator
1052      InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
1053        forward=true;
1054        resG.graph->first(in, v);
1055        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1056        if (!resG.graph->valid(in)) {
1057          forward=false;
1058          resG.graph->first(out, v);
1059          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1060        }
1061      }
1062      operator Edge() const {
1063//      Edge e;
1064//      e.forward=this->forward;
1065//      if (this->forward) e=out; else e=in;
1066//      return e;
1067        if (this->forward)
1068          return Edge(in, this->forward);
1069        else
1070          return Edge(out, this->forward);
1071      }
1072    };
1073
1074    class EdgeIt {
1075      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1076    protected:
1077      typename Graph::EdgeIt e;
1078      bool forward;
1079    public:
1080      EdgeIt() { }
1081      EdgeIt(const Invalid& i) : e(i), forward(false) { }
1082      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
1083        forward=true;
1084        resG.graph->first(e);
1085        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1086        if (!resG.graph->valid(e)) {
1087          forward=false;
1088          resG.graph->first(e);
1089          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1090        }
1091      }
1092      operator Edge() const {
1093        return Edge(e, this->forward);
1094      }
1095    };
1096//     class EdgeIt : public Edge {
1097//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1098//       NodeIt v;
1099//     public:
1100//       EdgeIt() { }
1101//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1102//       EdgeIt(const Invalid& i) : Edge(i) { }
1103//       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1104//      resG.graph->first(v);
1105//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1106//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1107//      while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1108//        resG.graph->next(v);
1109//        if (resG.graph->valid(v)) resG.graph->first(out, v);
1110//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1111//      }
1112//      if (!resG.graph->valid(out)) {
1113//        out_or_in=0;
1114//        resG.graph->first(v);
1115//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1116//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1117//        while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1118//          resG.graph->next(v);
1119//          if (resG.graph->valid(v)) resG.graph->first(in, v);
1120//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1121//        }
1122//      }
1123//       }
1124//       EdgeIt& operator++() {
1125//      if (out_or_in) {
1126//        ++out;
1127//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1128//        while (v.valid() && !out.valid()) {
1129//          ++v;
1130//          if (v.valid()) G->first(out, v);
1131//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1132//        }
1133//        if (!out.valid()) {
1134//          out_or_in=0;
1135//          G->first(v);
1136//          if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
1137//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1138//          while (v.valid() && !in.valid()) {
1139//            ++v;
1140//            if (v.valid()) G->first(in, v);
1141//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1142//          } 
1143//        }
1144//      } else {
1145//        ++in;
1146//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1147//        while (v.valid() && !in.valid()) {
1148//          ++v;
1149//          if (v.valid()) G->first(in, v);
1150//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1151//        }
1152//      }
1153//      return *this;
1154//       }
1155//    };
1156
1157    NodeIt& first(NodeIt& i) const {
1158      i=NodeIt(*this); return i;
1159    }
1160    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1161      i=OutEdgeIt(*this, p); return i;
1162    }
1163//    FIXME not tested
1164    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1165      i=InEdgeIt(*this, p); return i;
1166    }
1167    EdgeIt& first(EdgeIt& i) const {
1168      i=EdgeIt(*this); return i;
1169    }
1170   
1171    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1172    OutEdgeIt& next(OutEdgeIt& e) const {
1173      if (e.forward) {
1174        Node v=graph->aNode(e.out);
1175        graph->next(e.out);
1176        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1177        if (!graph->valid(e.out)) {
1178          e.forward=false;
1179          graph->first(e.in, v);
1180          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1181        }
1182      } else {
1183        graph->next(e.in);
1184        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1185      }
1186      return e;
1187    }
1188//     FIXME Not tested
1189    InEdgeIt& next(InEdgeIt& e) const {
1190      if (e.forward) {
1191        Node v=graph->aNode(e.in);
1192        graph->next(e.in);
1193        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1194        if (!graph->valid(e.in)) {
1195          e.forward=false;
1196          graph->first(e.out, v);
1197          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1198        }
1199      } else {
1200        graph->next(e.out);
1201        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1202      }
1203      return e;
1204    }
1205    EdgeIt& next(EdgeIt& e) const {
1206      if (e.forward) {
1207        graph->next(e.e);
1208        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1209        if (!graph->valid(e.e)) {
1210          e.forward=false;
1211          graph->first(e.e);
1212          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1213        }
1214      } else {
1215        graph->next(e.e);
1216        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1217      }
1218      return e;
1219    }
1220//     EdgeIt& next(EdgeIt& e) const {
1221//       if (e.out_or_in) {
1222//      graph->next(e.out);
1223//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1224//        while (graph->valid(e.v) && !graph->valid(e.out)) {
1225//          graph->next(e.v);
1226//          if (graph->valid(e.v)) graph->first(e.out, e.v);
1227//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1228//        }
1229//        if (!graph->valid(e.out)) {
1230//          e.out_or_in=0;
1231//          graph->first(e.v);
1232//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1233//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1234//          while (graph->valid(e.v) && !graph->valid(e.in)) {
1235//            graph->next(e.v);
1236//            if (graph->valid(e.v)) graph->first(e.in, e.v);
1237//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1238//          } 
1239//        }
1240//      } else {
1241//        graph->next(e.in);
1242//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1243//        while (graph->valid(e.v) && !graph->valid(e.in)) {
1244//          graph->next(e.v);
1245//          if (graph->valid(e.v)) graph->first(e.in, e.v);
1246//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1247//        }
1248//      }
1249//      return e;
1250//       }
1251   
1252
1253    template< typename It >
1254    It first() const {
1255      It e;
1256      first(e);
1257      return e;
1258    }
1259
1260    template< typename It >
1261    It first(Node v) const {
1262      It e;
1263      first(e, v);
1264      return e;
1265    }
1266
1267    Node tail(Edge e) const {
1268      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
1269    Node head(Edge e) const {
1270      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
1271
1272    Node aNode(OutEdgeIt e) const {
1273      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1274    Node bNode(OutEdgeIt e) const {
1275      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1276
1277    int nodeNum() const { return graph->nodeNum(); }
1278    //FIXME
1279    //int edgeNum() const { return graph->edgeNum(); }
1280
1281
1282//    int id(Node v) const { return graph->id(v); }
1283
1284    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1285    bool valid(Edge e) const {
1286      return graph->valid(e);
1287        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1288    }
1289
1290    void augment(const Edge& e, Number a) const {
1291      if (e.forward) 
1292//      flow->set(e.out, flow->get(e.out)+a);
1293        flow->set(e, (*flow)[e]+a);
1294      else 
1295//      flow->set(e.in, flow->get(e.in)-a);
1296        flow->set(e, (*flow)[e]-a);
1297    }
1298
1299    Number resCap(const Edge& e) const {
1300      if (e.forward)
1301//      return (capacity->get(e.out)-flow->get(e.out));
1302        return ((*capacity)[e]-(*flow)[e]);
1303      else
1304//      return (flow->get(e.in));
1305        return ((*flow)[e]);
1306    }
1307
1308//     Number resCap(typename Graph::OutEdgeIt out) const {
1309// //      return (capacity->get(out)-flow->get(out));
1310//       return ((*capacity)[out]-(*flow)[out]);
1311//     }
1312   
1313//     Number resCap(typename Graph::InEdgeIt in) const {
1314// //      return (flow->get(in));
1315//       return ((*flow)[in]);
1316//     }
1317
1318//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1319//     public:
1320//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1321//      : Graph::NodeMap<T>(_G.gw) { }
1322//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1323//            T a) : Graph::NodeMap<T>(_G.gw, a) { }
1324//     };
1325
1326//     template <typename T>
1327//     class NodeMap {
1328//       typename Graph::NodeMap<T> node_map;
1329//     public:
1330//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1331//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1332//       void set(Node nit, T a) { node_map.set(nit, a); }
1333//       T get(Node nit) const { return node_map.get(nit); }
1334//     };
1335
1336    template <typename T>
1337    class EdgeMap {
1338      typename Graph::EdgeMap<T> forward_map, backward_map;
1339    public:
1340      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1341      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1342      void set(Edge e, T a) {
1343        if (e.forward)
1344          forward_map.set(e.out, a);
1345        else
1346          backward_map.set(e.in, a);
1347      }
1348      T operator[](Edge e) const {
1349        if (e.forward)
1350          return forward_map[e.out];
1351        else
1352          return backward_map[e.in];
1353      }
1354//       T get(Edge e) const {
1355//      if (e.out_or_in)
1356//        return forward_map.get(e.out);
1357//      else
1358//        return backward_map.get(e.in);
1359//       }
1360    };
1361  };
1362
1363 
1364
1365//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1366//   class ResGraphWrapper : public GraphWrapper<Graph> {
1367//   protected:
1368//     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1369//     typedef typename Graph::InEdgeIt GraphInEdgeIt;
1370//     typedef typename Graph::Edge GraphEdge;
1371//     FlowMap* flow;
1372//     const CapacityMap* capacity;
1373//   public:
1374
1375//     ResGraphWrapper(Graph& _graph, FlowMap& _flow,
1376//                  const CapacityMap& _capacity) :
1377//       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
1378
1379//     class Edge;
1380//     class OutEdgeIt;
1381//     friend class Edge;
1382//     friend class OutEdgeIt;
1383
1384//     typedef typename GraphWrapper<Graph>::Node Node;
1385//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1386//     class Edge {
1387//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1388//     protected:
1389//       bool out_or_in; //true, iff out
1390//       GraphOutEdgeIt out;
1391//       GraphInEdgeIt in;
1392//     public:
1393//       Edge() : out_or_in(true) { }
1394//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1395// //       bool valid() const {
1396// //   return out_or_in && out.valid() || in.valid(); }
1397//       friend bool operator==(const Edge& u, const Edge& v) {
1398//      if (v.out_or_in)
1399//        return (u.out_or_in && u.out==v.out);
1400//      else
1401//        return (!u.out_or_in && u.in==v.in);
1402//       }
1403//       friend bool operator!=(const Edge& u, const Edge& v) {
1404//      if (v.out_or_in)
1405//        return (!u.out_or_in || u.out!=v.out);
1406//      else
1407//        return (u.out_or_in || u.in!=v.in);
1408//       }
1409//       operator GraphEdge() const {
1410//      if (out_or_in) return(out); else return(in);
1411//       }
1412//     };
1413//     class OutEdgeIt : public Edge {
1414//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1415//     public:
1416//       OutEdgeIt() { }
1417//       //FIXME
1418//       OutEdgeIt(const Edge& e) : Edge(e) { }
1419//       OutEdgeIt(const Invalid& i) : Edge(i) { }
1420//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1421//      resG.graph->first(out, v);
1422//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1423//      if (!resG.graph->valid(out)) {
1424//        out_or_in=0;
1425//        resG.graph->first(in, v);
1426//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1427//      }
1428//       }
1429// //     public:
1430// //       OutEdgeIt& operator++() {
1431// //   if (out_or_in) {
1432// //     Node v=/*resG->*/G->aNode(out);
1433// //     ++out;
1434// //     while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1435// //     if (!out.valid()) {
1436// //       out_or_in=0;
1437// //       G->first(in, v);
1438// //       while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1439// //     }
1440// //   } else {
1441// //     ++in;
1442// //     while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1443// //   }
1444// //   return *this;
1445// //       }
1446//     };
1447
1448//     //FIXME This is just for having InEdgeIt
1449// //    class InEdgeIt : public Edge { };
1450
1451//     class EdgeIt : public Edge {
1452//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1453//       NodeIt v;
1454//     public:
1455//       EdgeIt() { }
1456//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1457//       EdgeIt(const Invalid& i) : Edge(i) { }
1458//       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1459//      resG.graph->first(v);
1460//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1461//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1462//      while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1463//        resG.graph->next(v);
1464//        if (resG.graph->valid(v)) resG.graph->first(out, v);
1465//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1466//      }
1467//      if (!resG.graph->valid(out)) {
1468//        out_or_in=0;
1469//        resG.graph->first(v);
1470//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1471//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1472//        while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1473//          resG.graph->next(v);
1474//          if (resG.graph->valid(v)) resG.graph->first(in, v);
1475//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1476//        }
1477//      }
1478//       }
1479// //       EdgeIt& operator++() {
1480// //   if (out_or_in) {
1481// //     ++out;
1482// //     while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1483// //     while (v.valid() && !out.valid()) {
1484// //       ++v;
1485// //       if (v.valid()) G->first(out, v);
1486// //       while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1487// //     }
1488// //     if (!out.valid()) {
1489// //       out_or_in=0;
1490// //       G->first(v);
1491// //       if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
1492// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1493// //       while (v.valid() && !in.valid()) {
1494// //         ++v;
1495// //         if (v.valid()) G->first(in, v);
1496// //         while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1497// //       } 
1498// //     }
1499// //   } else {
1500// //     ++in;
1501// //     while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1502// //     while (v.valid() && !in.valid()) {
1503// //       ++v;
1504// //       if (v.valid()) G->first(in, v);
1505// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1506// //     }
1507// //   }
1508// //   return *this;
1509// //       }
1510//     };
1511
1512//     NodeIt& first(NodeIt& i) const {
1513//       i=NodeIt(*this);
1514//       return i;
1515//     }
1516//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1517//       i=OutEdgeIt(*this, p);
1518//       return i;
1519//     }
1520//     //FIXME Not yet implemented
1521//     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1522//     //i=InEdgeIt(*this, p);
1523//     //  return i;
1524//     //}
1525//     EdgeIt& first(EdgeIt& e) const {
1526//       e=EdgeIt(*this);
1527//       return e;
1528//     }
1529   
1530//     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
1531//     OutEdgeIt& next(OutEdgeIt& e) const {
1532//       if (e.out_or_in) {
1533//      Node v=graph->aNode(e.out);
1534//      graph->next(e.out);
1535//      while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1536//      if (!graph->valid(e.out)) {
1537//        e.out_or_in=0;
1538//        graph->first(e.in, v);
1539//        while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1540//      }
1541//       } else {
1542//      graph->next(e.in);
1543//      while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1544//       }
1545//       return e;
1546//     }
1547//     //FIXME Not yet implemented
1548//     //InEdgeIt& next(InEdgeIt& e) const {
1549//     //  return e;
1550//     //}
1551//     EdgeIt& next(EdgeIt& e) const {
1552//       if (e.out_or_in) {
1553//      graph->next(e.out);
1554//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1555//        while (graph->valid(e.v) && !graph->valid(e.out)) {
1556//          graph->next(e.v);
1557//          if (graph->valid(e.v)) graph->first(e.out, e.v);
1558//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1559//        }
1560//        if (!graph->valid(e.out)) {
1561//          e.out_or_in=0;
1562//          graph->first(e.v);
1563//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1564//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1565//          while (graph->valid(e.v) && !graph->valid(e.in)) {
1566//            graph->next(e.v);
1567//            if (graph->valid(e.v)) graph->first(e.in, e.v);
1568//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1569//          } 
1570//        }
1571//      } else {
1572//        graph->next(e.in);
1573//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1574//        while (graph->valid(e.v) && !graph->valid(e.in)) {
1575//          graph->next(e.v);
1576//          if (graph->valid(e.v)) graph->first(e.in, e.v);
1577//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1578//        }
1579//      }
1580//      return e;
1581//       }
1582   
1583
1584//     template< typename It >
1585//     It first() const {
1586//       It e;
1587//       first(e);
1588//       return e;
1589//     }
1590
1591//     template< typename It >
1592//     It first(Node v) const {
1593//       It e;
1594//       first(e, v);
1595//       return e;
1596//     }
1597
1598//     Node tail(Edge e) const {
1599//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1600//     Node head(Edge e) const {
1601//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1602
1603//     Node aNode(OutEdgeIt e) const {
1604//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1605//     Node bNode(OutEdgeIt e) const {
1606//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1607
1608//     int nodeNum() const { return graph->nodeNum(); }
1609//     //FIXME
1610//     //int edgeNum() const { return graph->edgeNum(); }
1611
1612
1613//     int id(Node v) const { return graph->id(v); }
1614
1615//     bool valid(Node n) const { return graph->valid(n); }
1616//     bool valid(Edge e) const {
1617//       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1618
1619//     void augment(const Edge& e, Number a) const {
1620//       if (e.out_or_in) 
1621// //   flow->set(e.out, flow->get(e.out)+a);
1622//      flow->set(e.out, (*flow)[e.out]+a);
1623//       else 
1624// //   flow->set(e.in, flow->get(e.in)-a);
1625//      flow->set(e.in, (*flow)[e.in]-a);
1626//     }
1627
1628//     Number resCap(const Edge& e) const {
1629//       if (e.out_or_in)
1630// //   return (capacity->get(e.out)-flow->get(e.out));
1631//      return ((*capacity)[e.out]-(*flow)[e.out]);
1632//       else
1633// //   return (flow->get(e.in));
1634//      return ((*flow)[e.in]);
1635//     }
1636
1637//     Number resCap(GraphOutEdgeIt out) const {
1638// //      return (capacity->get(out)-flow->get(out));
1639//       return ((*capacity)[out]-(*flow)[out]);
1640//     }
1641   
1642//     Number resCap(GraphInEdgeIt in) const {
1643// //      return (flow->get(in));
1644//       return ((*flow)[in]);
1645//     }
1646
1647// //     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1648// //     public:
1649// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1650// //   : Graph::NodeMap<T>(_G.gw) { }
1651// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1652// //         T a) : Graph::NodeMap<T>(_G.gw, a) { }
1653// //     };
1654
1655// //     template <typename T>
1656// //     class NodeMap {
1657// //       typename Graph::NodeMap<T> node_map;
1658// //     public:
1659// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1660// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1661// //       void set(Node nit, T a) { node_map.set(nit, a); }
1662// //       T get(Node nit) const { return node_map.get(nit); }
1663// //     };
1664
1665//     template <typename T>
1666//     class EdgeMap {
1667//       typename Graph::EdgeMap<T> forward_map, backward_map;
1668//     public:
1669//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1670//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1671//       void set(Edge e, T a) {
1672//      if (e.out_or_in)
1673//        forward_map.set(e.out, a);
1674//      else
1675//        backward_map.set(e.in, a);
1676//       }
1677//       T operator[](Edge e) const {
1678//      if (e.out_or_in)
1679//        return forward_map[e.out];
1680//      else
1681//        return backward_map[e.in];
1682//       }
1683// //       T get(Edge e) const {
1684// //   if (e.out_or_in)
1685// //     return forward_map.get(e.out);
1686// //   else
1687// //     return backward_map.get(e.in);
1688// //       }
1689//     };
1690//   };
1691
1692
1693  //ErasingFirstGraphWrapper for blocking flows
1694  template<typename Graph, typename FirstOutEdgesMap>
1695  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1696  protected:
1697    FirstOutEdgesMap* first_out_edges;
1698  public:
1699    ErasingFirstGraphWrapper(Graph& _graph,
1700                             FirstOutEdgesMap& _first_out_edges) :
1701      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1702
1703    typedef typename GraphWrapper<Graph>::Node Node;
1704    class NodeIt {
1705      friend class GraphWrapper<Graph>;
1706      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1707      typename Graph::NodeIt n;
1708     public:
1709      NodeIt() { }
1710      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1711      NodeIt(const Invalid& i) : n(i) { }
1712      NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1713        n(*(_G.graph)) { }
1714      operator Node() const { return Node(typename Graph::Node(n)); }
1715    };
1716    typedef typename GraphWrapper<Graph>::Edge Edge;
1717    class OutEdgeIt {
1718      friend class GraphWrapper<Graph>;
1719      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1720//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1721      typename Graph::OutEdgeIt e;
1722    public:
1723      OutEdgeIt() { }
1724      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1725      OutEdgeIt(const Invalid& i) : e(i) { }
1726      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1727                const Node& _n) :
1728        e((*_G.first_out_edges)[_n]) { }
1729      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1730    };
1731    class InEdgeIt {
1732      friend class GraphWrapper<Graph>;
1733      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1734//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
1735      typename Graph::InEdgeIt e;
1736    public:
1737      InEdgeIt() { }
1738      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1739      InEdgeIt(const Invalid& i) : e(i) { }
1740      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1741               const Node& _n) :
1742        e(*(_G.graph), typename Graph::Node(_n)) { }
1743      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1744    };
1745    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1746    class EdgeIt {
1747      friend class GraphWrapper<Graph>;
1748      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1749//      typedef typename Graph::EdgeIt GraphEdgeIt;
1750      typename Graph::EdgeIt e;
1751    public:
1752      EdgeIt() { }
1753      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1754      EdgeIt(const Invalid& i) : e(i) { }
1755      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1756        e(*(_G.graph)) { }
1757      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1758    };
1759
1760    NodeIt& first(NodeIt& i) const {
1761      i=NodeIt(*this); return i;
1762    }
1763    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1764      i=OutEdgeIt(*this, p); return i;
1765    }
1766    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1767      i=InEdgeIt(*this, p); return i;
1768    }
1769    EdgeIt& first(EdgeIt& i) const {
1770      i=EdgeIt(*this); return i;
1771    }
1772
1773//     template<typename I> I& first(I& i) const {
1774//       graph->first(i);
1775//       return i;
1776//     }
1777//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1778// //      e=first_out_edges->get(n);
1779//       e=(*first_out_edges)[n];
1780//       return e;
1781//     }
1782//     template<typename I, typename P> I& first(I& i, const P& p) const {
1783//       graph->first(i, p);
1784//       return i;
1785//     }
1786   
1787    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1788    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1789    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1790    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
1791   
1792    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1793    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1794    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1795    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1796
1797//     template<typename I> I& next(I &i) const {
1798//       graph->next(i);
1799//       return i;
1800//     }
1801   
1802    template< typename It > It first() const {
1803      It e; this->first(e); return e; }
1804   
1805    template< typename It > It first(const Node& v) const {
1806      It e; this->first(e, v); return e; }
1807
1808    void erase(const OutEdgeIt& e) const {
1809      OutEdgeIt f=e;
1810      this->next(f);
1811      first_out_edges->set(this->tail(e), f.e);
1812    }
1813  };
1814
1815//   //ErasingFirstGraphWrapper for blocking flows
1816//   template<typename Graph, typename FirstOutEdgesMap>
1817//   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1818//   protected:
1819//     FirstOutEdgesMap* first_out_edges;
1820//   public:
1821//     ErasingFirstGraphWrapper(Graph& _graph,
1822//                           FirstOutEdgesMap& _first_out_edges) :
1823//       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1824
1825//     typedef typename Graph::Node Node;
1826//     class NodeIt : public Graph::NodeIt {
1827//     public:
1828//       NodeIt() { }
1829//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1830//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1831//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1832//      Graph::NodeIt(*(_G.graph)) { }
1833//     };
1834//     typedef typename Graph::Edge Edge;
1835//     class OutEdgeIt : public Graph::OutEdgeIt {
1836//     public:
1837//       OutEdgeIt() { }
1838//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1839//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1840//       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1841//              const Node& n) :
1842//      Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
1843//     };
1844//     class InEdgeIt : public Graph::InEdgeIt {
1845//     public:
1846//       InEdgeIt() { }
1847//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1848//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1849//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1850//             const Node& n) :
1851//      Graph::InEdgeIt(*(_G.graph), n) { }
1852//     };
1853//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1854//     class EdgeIt : public Graph::EdgeIt {
1855//     public:
1856//       EdgeIt() { }
1857//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1858//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1859//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1860//      Graph::EdgeIt(*(_G.graph)) { }
1861//     };
1862
1863//     NodeIt& first(NodeIt& i) const {
1864//       i=NodeIt(*this);
1865//       return i;
1866//     }
1867//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1868//       i=OutEdgeIt(*this, n);
1869// //      i=(*first_out_edges)[n];
1870//       return i;
1871//     }
1872//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1873//       i=InEdgeIt(*this, n);
1874//       return i;
1875//     }
1876//     EdgeIt& first(EdgeIt& i) const {
1877//       i=EdgeIt(*this);
1878//       return i;
1879//     }
1880
1881// //     template<typename I> I& first(I& i) const {
1882// //       graph->first(i);
1883// //       return i;
1884// //     }
1885// //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1886// // //      e=first_out_edges->get(n);
1887// //       e=(*first_out_edges)[n];
1888// //       return e;
1889// //     }
1890// //     template<typename I, typename P> I& first(I& i, const P& p) const {
1891// //       graph->first(i, p);
1892// //       return i;
1893// //     }
1894   
1895//     NodeIt& next(NodeIt& i) const {
1896//       graph->next(i);
1897//       return i;
1898//     }
1899//     OutEdgeIt& next(OutEdgeIt& i) const {
1900//       graph->next(i);
1901//       return i;
1902//     }
1903//     InEdgeIt& next(InEdgeIt& i) const {
1904//       graph->next(i);
1905//       return i;
1906//     }
1907//     EdgeIt& next(EdgeIt& i) const {
1908//       graph->next(i);
1909//       return i;
1910//     }
1911
1912// //     template<typename I> I& next(I &i) const {
1913// //       graph->next(i);
1914// //       return i;
1915// //     }
1916   
1917//     template< typename It > It first() const {
1918//       It e; this->first(e); return e; }
1919   
1920//     template< typename It > It first(const Node& v) const {
1921//       It e; this->first(e, v); return e; }
1922
1923//     void erase(const OutEdgeIt& e) const {
1924//       OutEdgeIt f=e;
1925//       this->next(f);
1926//       first_out_edges->set(this->tail(e), f);
1927//     }
1928//   };
1929
1930
1931// // FIXME: comparison should be made better!!!
1932//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1933//   class ResGraphWrapper
1934//   {
1935//     Graph* graph;
1936 
1937//   public:
1938//     typedef Graph ParentGraph;
1939
1940//     typedef typename Graph::Node Node;
1941//     typedef typename Graph::Edge Edge;
1942 
1943//     typedef typename Graph::NodeIt NodeIt;
1944   
1945//     class OutEdgeIt {
1946//     public:
1947//       //Graph::Node n;
1948//       bool out_or_in;
1949//       typename Graph::OutEdgeIt o;
1950//       typename Graph::InEdgeIt i;   
1951//     };
1952//     class InEdgeIt {
1953//     public:
1954//       //Graph::Node n;
1955//       bool out_or_in;
1956//       typename Graph::OutEdgeIt o;
1957//       typename Graph::InEdgeIt i;   
1958//     };
1959//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1960//     typedef typename Graph::EdgeIt EdgeIt;
1961
1962//     int nodeNum() const { return gw.nodeNum(); }
1963//     int edgeNum() const { return gw.edgeNum(); }
1964
1965//     Node& first(Node& n) const { return gw.first(n); }
1966
1967//     // Edge and SymEdge  is missing!!!!
1968//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1969
1970//     //FIXME
1971//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1972//       {
1973//      e.n=n;
1974//      gw.first(e.o,n);
1975//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1976//        gw.goNext(e.o);
1977//      if(!gw.valid(e.o)) {
1978//        gw.first(e.i,n);
1979//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1980//          gw.goNext(e.i);
1981//      }
1982//      return e;
1983//       }
1984// /*
1985//   OutEdgeIt &goNext(OutEdgeIt &e)
1986//   {
1987//   if(gw.valid(e.o)) {
1988//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1989//   gw.goNext(e.o);
1990//   if(gw.valid(e.o)) return e;
1991//   else gw.first(e.i,e.n);
1992//   }
1993//   else {
1994//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1995//   gw.goNext(e.i);
1996//   return e;
1997//   }
1998//   }
1999//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
2000// */
2001//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
2002
2003//     //FIXME
2004//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
2005//       {
2006//      e.n=n;
2007//      gw.first(e.i,n);
2008//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
2009//        gw.goNext(e.i);
2010//      if(!gw.valid(e.i)) {
2011//        gw.first(e.o,n);
2012//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
2013//          gw.goNext(e.o);
2014//      }
2015//      return e;
2016//       }
2017// /*
2018//   InEdgeIt &goNext(InEdgeIt &e)
2019//   {
2020//   if(gw.valid(e.i)) {
2021//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
2022//   gw.goNext(e.i);
2023//   if(gw.valid(e.i)) return e;
2024//   else gw.first(e.o,e.n);
2025//   }
2026//   else {
2027//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
2028//   gw.goNext(e.o);
2029//   return e;
2030//   }
2031//   }
2032//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
2033// */
2034//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
2035
2036//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
2037//     //template<typename I> I next(const I i); { return gw.goNext(i); }
2038
2039//     template< typename It > It first() const {
2040//       It e; first(e); return e; }
2041
2042//     template< typename It > It first(Node v) const {
2043//       It e; first(e, v); return e; }
2044
2045//     Node head(const Edge& e) const { return gw.head(e); }
2046//     Node tail(const Edge& e) const { return gw.tail(e); }
2047 
2048//     template<typename I> Node aNode(const I& e) const {
2049//       return gw.aNode(e); }
2050//     template<typename I> Node bNode(const I& e) const {
2051//       return gw.bNode(e); }
2052 
2053//     //template<typename I> bool valid(const I i);
2054//     //{ return gw.valid(i); }
2055 
2056//     //template<typename I> void setInvalid(const I &i);
2057//     //{ return gw.setInvalid(i); }
2058 
2059//     Node addNode() { return gw.addNode(); }
2060//     Edge addEdge(const Node& tail, const Node& head) {
2061//       return gw.addEdge(tail, head); }
2062 
2063//     template<typename I> void erase(const I& i) { gw.erase(i); }
2064 
2065//     void clear() { gw.clear(); }
2066 
2067//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
2068//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
2069 
2070//     void setGraph(Graph& _graph) { graph = &_graph; }
2071//     Graph& getGraph() { return (*graph); }
2072
2073//     //ResGraphWrapper() : graph(0) { }
2074//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
2075//   };
2076
2077} //namespace hugo
2078
2079#endif //HUGO_GRAPH_WRAPPER_H
2080
Note: See TracBrowser for help on using the repository browser.