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 @ 319:98e15ff8dc3b

Last change on this file since 319:98e15ff8dc3b was 318:7bec4e8fb7dd, checked in by marci, 21 years ago

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