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 @ 268:f4eb1ae59b50

Last change on this file since 268:f4eb1ae59b50 was 266:4cec4981dfd1, checked in by marci, 20 years ago

GraphWrappers?, MapWrappers?
File size: 55.8 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 TrivGraphWrapper {
11  protected:
12    Graph* graph;
13 
14  public:
15    typedef Graph BaseGraph;
16
17    typedef typename Graph::Node Node;
18    class NodeIt : public Graph::NodeIt {
19    public:
20      NodeIt() { }
21      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
22      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
23      NodeIt(const TrivGraphWrapper<Graph>& _G) :
24        Graph::NodeIt(*(_G.graph)) { }
25    };
26    typedef typename Graph::Edge Edge;
27    //typedef typename Graph::OutEdgeIt OutEdgeIt;
28    class OutEdgeIt : public Graph::OutEdgeIt {
29    public:
30      OutEdgeIt() { }
31      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
32      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
33      OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
34        Graph::OutEdgeIt(*(_G.graph), n) { }
35    };
36    //typedef typename Graph::InEdgeIt InEdgeIt;
37    class InEdgeIt : public Graph::InEdgeIt {
38    public:
39      InEdgeIt() { }
40      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
41      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
42      InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
43        Graph::InEdgeIt(*(_G.graph), n) { }
44    };
45    //typedef typename Graph::SymEdgeIt SymEdgeIt;
46    //typedef typename Graph::EdgeIt EdgeIt;
47    class EdgeIt : public Graph::EdgeIt {
48    public:
49      EdgeIt() { }
50      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
51      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
52      EdgeIt(const TrivGraphWrapper<Graph>& _G) :
53        Graph::EdgeIt(*(_G.graph)) { }
54    };
55
56    //TrivGraphWrapper() : graph(0) { }
57    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
58
59//    void setGraph(Graph& _graph) { graph = &_graph; }
60//    Graph& getGraph() const { return (*graph); }
61
62    NodeIt& first(NodeIt& i) const {
63      i=NodeIt(*this);
64      return i;
65    }
66    EdgeIt& first(EdgeIt& i) const {
67      i=EdgeIt(*this);
68      return i;
69    }
70//     template<typename I> I& first(I& i) const {
71//       //return graph->first(i);
72//       i=I(*this);
73//       return i;
74//     }
75    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
76      i=OutEdgeIt(*this, p);
77      return i;
78    }
79    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
80      i=InEdgeIt(*this, p);
81      return i;
82    }
83//     template<typename I, typename P> I& first(I& i, const P& p) const {
84//       //return graph->first(i, p);
85//       i=I(*this, p);
86//       return i;
87//     }
88   
89//    template<typename I> I getNext(const I& i) const {
90//      return graph->getNext(i); }
91    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
92
93    template< typename It > It first() const {
94      It e; first(e); return e; }
95
96    template< typename It > It first(const Node& v) const {
97      It e; first(e, v); return e; }
98
99    Node head(const Edge& e) const { return graph->head(e); }
100    Node tail(const Edge& e) const { return graph->tail(e); }
101
102    template<typename I> bool valid(const I& i) const
103      { return graph->valid(i); }
104 
105    //template<typename I> void setInvalid(const I &i);
106    //{ return graph->setInvalid(i); }
107
108    int nodeNum() const { return graph->nodeNum(); }
109    int edgeNum() const { return graph->edgeNum(); }
110 
111    template<typename I> Node aNode(const I& e) const {
112      return graph->aNode(e); }
113    template<typename I> Node bNode(const I& e) const {
114      return graph->bNode(e); }
115 
116    Node addNode() const { return graph->addNode(); }
117    Edge addEdge(const Node& tail, const Node& head) const {
118      return graph->addEdge(tail, head); }
119 
120    template<typename I> void erase(const I& i) const { graph->erase(i); }
121 
122    void clear() const { graph->clear(); }
123   
124    template<typename T> class NodeMap : public Graph::NodeMap<T> {
125    public:
126      NodeMap(const TrivGraphWrapper<Graph>& _G) : 
127        Graph::NodeMap<T>(*(_G.graph)) { }
128      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
129        Graph::NodeMap<T>(*(_G.graph), a) { }
130    };
131
132    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
133    public:
134      EdgeMap(const TrivGraphWrapper<Graph>& _G) : 
135        Graph::EdgeMap<T>(*(_G.graph)) { }
136      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
137        Graph::EdgeMap<T>(*(_G.graph), a) { }
138    };
139
140    template<typename Map, typename T> class NodeMapWrapper {
141    protected:
142      Map* map;
143    public:
144      NodeMapWrapper(Map& _map) : map(&_map) { }
145      //template<typename T>
146      void set(Node n, T a) { map->set(n, a); }
147      //template<typename T>
148      T get(Node n) const { return map->get(n); }
149    };
150
151    template<typename Map, typename T> class EdgeMapWrapper {
152    protected:
153      Map* map;
154    public:
155      EdgeMapWrapper(Map& _map) : map(&_map) { }
156      //template<typename T>
157      void set(Edge n, T a) { map->set(n, a); }
158      //template<typename T>
159      T get(Edge n) const { return map->get(n); }
160    };
161  };
162
163  template<typename GraphWrapper>
164  class GraphWrapperSkeleton {
165  protected:
166    GraphWrapper gw;
167 
168  public:
169    //typedef typename GraphWrapper::BaseGraph BaseGraph;
170
171//     typedef typename GraphWrapper::Node Node;
172//     typedef typename GraphWrapper::NodeIt NodeIt;
173
174//     typedef typename GraphWrapper::Edge Edge;
175//     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
176//     typedef typename GraphWrapper::InEdgeIt InEdgeIt;
177//     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
178//     typedef typename GraphWrapper::EdgeIt EdgeIt;
179
180    typedef typename GraphWrapper::Node Node;
181    class NodeIt : public GraphWrapper::NodeIt {
182    public:
183      NodeIt() { }
184      NodeIt(const typename GraphWrapper::NodeIt& n) :
185        GraphWrapper::NodeIt(n) { }
186      NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
187      NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
188        GraphWrapper::NodeIt(_G.gw) { }
189    };
190    typedef typename GraphWrapper::Edge Edge;
191    //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
192    class OutEdgeIt : public GraphWrapper::OutEdgeIt {
193    public:
194      OutEdgeIt() { }
195      OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
196        GraphWrapper::OutEdgeIt(e) { }
197      OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
198      OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
199        GraphWrapper::OutEdgeIt(_G.gw, n) { }
200    };
201    //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
202    class InEdgeIt : public GraphWrapper::InEdgeIt {
203    public:
204      InEdgeIt() { }
205      InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
206        GraphWrapper::InEdgeIt(e) { }
207      InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
208      InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
209        GraphWrapper::InEdgeIt(_G.gw, n) { }
210    };
211    //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
212    //typedef typename GraphWrapper::EdgeIt EdgeIt;
213    class EdgeIt : public GraphWrapper::EdgeIt {
214    public:
215      EdgeIt() { }
216      EdgeIt(const typename GraphWrapper::EdgeIt& e) :
217        GraphWrapper::EdgeIt(e) { }
218      EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
219      EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
220        GraphWrapper::EdgeIt(_G.gw) { }
221    };
222
223
224    //GraphWrapperSkeleton() : gw() { }
225    GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
226
227    //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
228    //BaseGraph& getGraph() const { return gw.getGraph(); }
229   
230    template<typename I> I& first(I& i) const {       
231      i=I(*this);
232      return i;
233    }
234    template<typename I, typename P> I& first(I& i, const P& p) const {
235      i=I(*this, p);
236      return i;
237    }
238   
239//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
240    template<typename I> I& next(I &i) const { gw.next(i); return i; }   
241
242    template< typename It > It first() const {
243      It e; this->first(e); return e; }
244
245    template< typename It > It first(const Node& v) const {
246      It e; this->first(e, v); return e; }
247
248    Node head(const Edge& e) const { return gw.head(e); }
249    Node tail(const Edge& e) const { return gw.tail(e); }
250
251    template<typename I> bool valid(const I& i) const { return gw.valid(i); }
252 
253    //template<typename I> void setInvalid(const I &i);
254    //{ return graph->setInvalid(i); }
255
256    int nodeNum() const { return gw.nodeNum(); }
257    int edgeNum() const { return gw.edgeNum(); }
258 
259    template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
260    template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
261 
262    Node addNode() const { return gw.addNode(); }
263    Edge addEdge(const Node& tail, const Node& head) const {
264      return gw.addEdge(tail, head); }
265 
266    template<typename I> void erase(const I& i) const { gw.erase(i); }
267 
268    void clear() const { gw.clear(); }
269   
270    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
271    public:
272      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 
273        GraphWrapper::NodeMap<T>(_G.gw) { }
274      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
275        GraphWrapper::NodeMap<T>(_G.gw, a) { }
276    };
277
278    template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
279    public:
280      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 
281        GraphWrapper::EdgeMap<T>(_G.gw) { }
282      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
283        GraphWrapper::EdgeMap<T>(_G.gw, a) { }
284    };
285  };
286
287//   template<typename Graph>
288//   class RevGraphWrapper
289//   {
290//   protected:
291//     Graph* graph;
292 
293//   public:
294//     typedef Graph BaseGraph;
295
296//     typedef typename Graph::Node Node;   
297//     typedef typename Graph::NodeIt NodeIt;
298 
299//     typedef typename Graph::Edge Edge;
300//     typedef typename Graph::OutEdgeIt InEdgeIt;
301//     typedef typename Graph::InEdgeIt OutEdgeIt;
302//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
303//     typedef typename Graph::EdgeIt EdgeIt;
304
305//     //RevGraphWrapper() : graph(0) { }
306//     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
307
308//     void setGraph(Graph& _graph) { graph = &_graph; }
309//     Graph& getGraph() const { return (*graph); }
310   
311//     template<typename I> I& first(I& i) const { return graph->first(i); }
312//     template<typename I, typename P> I& first(I& i, const P& p) const {
313//       return graph->first(i, p); }
314
315//     template<typename I> I getNext(const I& i) const {
316//       return graph->getNext(i); }
317//     template<typename I> I& next(I &i) const { return graph->next(i); }   
318
319//     template< typename It > It first() const {
320//       It e; first(e); return e; }
321
322//     template< typename It > It first(const Node& v) const {
323//       It e; first(e, v); return e; }
324
325//     Node head(const Edge& e) const { return graph->tail(e); }
326//     Node tail(const Edge& e) const { return graph->head(e); }
327 
328//     template<typename I> bool valid(const I& i) const
329//       { return graph->valid(i); }
330 
331//     //template<typename I> void setInvalid(const I &i);
332//     //{ return graph->setInvalid(i); }
333 
334//     template<typename I> Node aNode(const I& e) const {
335//       return graph->aNode(e); }
336//     template<typename I> Node bNode(const I& e) const {
337//       return graph->bNode(e); }
338
339//     Node addNode() const { return graph->addNode(); }
340//     Edge addEdge(const Node& tail, const Node& head) const {
341//       return graph->addEdge(tail, head); }
342 
343//     int nodeNum() const { return graph->nodeNum(); }
344//     int edgeNum() const { return graph->edgeNum(); }
345 
346//     template<typename I> void erase(const I& i) const { graph->erase(i); }
347 
348//     void clear() const { graph->clear(); }
349
350//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
351//     public:
352//       NodeMap(const RevGraphWrapper<Graph>& _G) :
353//      Graph::NodeMap<T>(_G.getGraph()) { }
354//       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
355//      Graph::NodeMap<T>(_G.getGraph(), a) { }
356//     };
357
358//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
359//     public:
360//       EdgeMap(const RevGraphWrapper<Graph>& _G) :
361//      Graph::EdgeMap<T>(_G.getGraph()) { }
362//       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
363//      Graph::EdgeMap<T>(_G.getGraph(), a) { }
364//     };
365//   };
366
367//   template<typename /*Graph*/GraphWrapper
368//   /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
369//   class RevGraphWrapper :
370//     public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
371//   protected:
372//     //Graph* graph;
373   
374//   public:
375//     //typedef Graph BaseGraph;
376
377//     //typedef typename Graph::Node Node;   
378//     //typedef typename Graph::NodeIt NodeIt;
379 
380//     //typedef typename Graph::Edge Edge;
381//     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
382//     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
383//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
384//     //typedef typename Graph::EdgeIt EdgeIt;
385
386//     //RevGraphWrapper() : graph(0) { }
387//     RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
388   
389//     //void setGraph(Graph& _graph) { graph = &_graph; }
390//     //Graph& getGraph() const { return (*graph); }
391   
392//     //template<typename I> I& first(I& i) const { return graph->first(i); }
393//     //template<typename I, typename P> I& first(I& i, const P& p) const {
394//     //  return graph->first(i, p); }
395
396//     //template<typename I> I getNext(const I& i) const {
397//     //  return graph->getNext(i); }
398//     //template<typename I> I& next(I &i) const { return graph->next(i); }   
399
400//     //template< typename It > It first() const {
401//     //  It e; first(e); return e; }
402
403//     //template< typename It > It first(const Node& v) const {
404//     //  It e; first(e, v); return e; }
405
406//     //Node head(const Edge& e) const { return graph->tail(e); }
407//     //Node tail(const Edge& e) const { return graph->head(e); }
408 
409//     //template<typename I> bool valid(const I& i) const
410//     //  { return graph->valid(i); }
411 
412//     //template<typename I> void setInvalid(const I &i);
413//     //{ return graph->setInvalid(i); }
414 
415//     //template<typename I> Node aNode(const I& e) const {
416//     //  return graph->aNode(e); }
417//     //template<typename I> Node bNode(const I& e) const {
418//     //  return graph->bNode(e); }
419
420//     //Node addNode() const { return graph->addNode(); }
421//     //Edge addEdge(const Node& tail, const Node& head) const {
422//     //  return graph->addEdge(tail, head); }
423 
424//     //int nodeNum() const { return graph->nodeNum(); }
425//     //int edgeNum() const { return graph->edgeNum(); }
426 
427//     //template<typename I> void erase(const I& i) const { graph->erase(i); }
428 
429//     //void clear() const { graph->clear(); }
430
431//     template<typename T> class NodeMap :
432//       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
433//     {
434//     public:
435//       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
436//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
437//       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
438//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
439//     };
440   
441//     template<typename T> class EdgeMap :
442//       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
443//     public:
444//       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
445//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
446//       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
447//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
448//     };
449//   };
450
451
452  template<typename GraphWrapper>
453  class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
454  public:
455    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
456    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
457    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
458    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
459
460    RevGraphWrapper(GraphWrapper _gw) :
461      GraphWrapperSkeleton<GraphWrapper>(_gw) { } 
462
463    Node head(const Edge& e) const
464      { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
465    Node tail(const Edge& e) const
466      { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
467  };
468
469  //Subgraph on the same node-set and partial edge-set
470  template<typename GraphWrapper, typename EdgeFilterMap>
471  class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
472  protected:
473    EdgeFilterMap* filter_map;
474  public:
475    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
476    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
477    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
478    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
479    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
480    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
481
482    SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
483      GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { } 
484
485    template<typename I> I& first(I& i) const {
486      gw.first(i);
487      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
488      return i;
489    }
490    template<typename I, typename P> I& first(I& i, const P& p) const {
491      gw.first(i, p);
492      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
493      return i;
494    }
495   
496    //template<typename I> I getNext(const I& i) const {
497    //  return gw.getNext(i);
498    //}
499    template<typename I> I& next(I &i) const {
500      gw.next(i);
501      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
502      return i;
503    }
504   
505    template< typename It > It first() const {
506      It e; this->first(e); return e; }
507   
508    template< typename It > It first(const Node& v) const {
509      It e; this->first(e, v); return e; }
510  };
511
512//   template<typename GraphWrapper>
513//   class UndirGraphWrapper {
514//   protected:
515//     //Graph* graph;
516//     GraphWrapper gw;
517
518//   public:
519//     typedef GraphWrapper BaseGraph;
520
521//     typedef typename GraphWrapper::Node Node;
522//     typedef typename GraphWrapper::NodeIt NodeIt;
523
524//     //typedef typename Graph::Edge Edge;
525//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
526//     //typedef typename Graph::InEdgeIt InEdgeIt;
527//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
528//     //typedef typename Graph::EdgeIt EdgeIt;
529
530//     //private:
531//     typedef typename GraphWrapper::Edge GraphEdge;
532//     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
533//     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
534//     //public:
535
536//     //UndirGraphWrapper() : graph(0) { }
537//     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
538
539//     //void setGraph(Graph& _graph) { graph = &_graph; }
540//     //Graph& getGraph() const { return (*graph); }
541 
542//     class Edge {
543//       friend class UndirGraphWrapper<GraphWrapper>;
544//       bool out_or_in; //true iff out
545//       GraphOutEdgeIt out;
546//       GraphInEdgeIt in;
547//     public:
548//       Edge() : out_or_in(), out(), in() { }
549//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
550//       operator GraphEdge() const {
551//      if (out_or_in) return(out); else return(in);
552//       }
553//       friend bool operator==(const Edge& u, const Edge& v) {
554//      if (v.out_or_in)
555//        return (u.out_or_in && u.out==v.out);
556//      else
557//        return (!u.out_or_in && u.in==v.in);
558//       }
559//       friend bool operator!=(const Edge& u, const Edge& v) {
560//      if (v.out_or_in)
561//        return (!u.out_or_in || u.out!=v.out);
562//      else
563//        return (u.out_or_in || u.in!=v.in);
564//       }
565//     };
566
567//     class OutEdgeIt : public Edge {
568//       friend class UndirGraphWrapper<GraphWrapper>;
569//     public:
570//       OutEdgeIt() : Edge() { }
571//       OutEdgeIt(const Invalid& i) : Edge(i) { }
572//       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
573//      : Edge() {
574//      out_or_in=true;
575//      _G.gw.first(out, n);
576//      if (!(_G.gw.valid(out))) {
577//        out_or_in=false;
578//        _G.gw.first(in, n);
579//      }
580//       }
581//     };
582
583//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
584//       e.out_or_in=true;
585//       gw.first(e.out, n);
586//       if (!(gw.valid(e.out))) {
587//      e.out_or_in=false;
588//      gw.first(e.in, n);
589//       }
590//       return e;
591//     }
592
593//     OutEdgeIt& next(OutEdgeIt& e) const {
594//       if (e.out_or_in) {
595//      Node n=gw.tail(e.out);
596//      gw.next(e.out);
597//      if (!gw.valid(e.out)) {
598//        e.out_or_in=false;
599//        gw.first(e.in, n);
600//      }
601//       } else {
602//      gw.next(e.in);
603//       }
604//       return e;
605//     }
606
607//     Node aNode(const OutEdgeIt& e) const {
608//       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
609//     Node bNode(const OutEdgeIt& e) const {
610//       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
611
612//     typedef OutEdgeIt InEdgeIt;
613
614//     template<typename I> I& first(I& i) const { return gw.first(i); }
615// //     template<typename I, typename P> I& first(I& i, const P& p) const {
616// //       return graph->first(i, p); }
617   
618//     template<typename I> I getNext(const I& i) const {
619//       return gw.getNext(i); }
620//     template<typename I> I& next(I &i) const { return gw.next(i); }   
621
622//     template< typename It > It first() const {
623//       It e; first(e); return e; }
624
625//     template< typename It > It first(const Node& v) const {
626//       It e; first(e, v); return e; }
627
628//     Node head(const Edge& e) const { return gw.head(e); }
629//     Node tail(const Edge& e) const { return gw.tail(e); }
630
631//     template<typename I> bool valid(const I& i) const
632//       { return gw.valid(i); }
633 
634//     //template<typename I> void setInvalid(const I &i);
635//     //{ return graph->setInvalid(i); }
636
637//     int nodeNum() const { return gw.nodeNum(); }
638//     int edgeNum() const { return gw.edgeNum(); }
639 
640// //     template<typename I> Node aNode(const I& e) const {
641// //       return graph->aNode(e); }
642// //     template<typename I> Node bNode(const I& e) const {
643// //       return graph->bNode(e); }
644 
645//     Node addNode() const { return gw.addNode(); }
646// // FIXME: ez igy nem jo, mert nem
647// //    Edge addEdge(const Node& tail, const Node& head) const {
648// //      return graph->addEdge(tail, head); }
649 
650//     template<typename I> void erase(const I& i) const { gw.erase(i); }
651 
652//     void clear() const { gw.clear(); }
653   
654//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
655//     public:
656//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
657//      GraphWrapper::NodeMap<T>(_G.gw) { }
658//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
659//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
660//     };
661
662//     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
663//     public:
664//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
665//      GraphWrapper::EdgeMap<T>(_G.gw) { }
666//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
667//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
668//     };
669//   };
670
671
672  template<typename GraphWrapper>
673  class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
674  protected:
675//    GraphWrapper gw;
676
677  public:
678    //typedef GraphWrapper BaseGraph;
679
680    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
681    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
682
683    //private:
684    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge GraphEdge;
685    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt GraphOutEdgeIt;
686    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt GraphInEdgeIt;
687    //public:
688
689    //UndirGraphWrapper() : graph(0) { }
690    UndirGraphWrapper(GraphWrapper _gw) :
691      GraphWrapperSkeleton<GraphWrapper>(_gw) { } 
692
693    //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
694
695    //void setGraph(Graph& _graph) { graph = &_graph; }
696    //Graph& getGraph() const { return (*graph); }
697 
698    class Edge {
699      friend class UndirGraphWrapper<GraphWrapper>;
700      bool out_or_in; //true iff out
701      GraphOutEdgeIt out;
702      GraphInEdgeIt in;
703    public:
704      Edge() : out_or_in(), out(), in() { }
705      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
706      operator GraphEdge() const {
707        if (out_or_in) return(out); else return(in);
708      }
709//FIXME
710//2 edges are equal if they "refer" to the same physical edge
711//is it good?
712      friend bool operator==(const Edge& u, const Edge& v) {
713        if (v.out_or_in)
714          if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
715        //return (u.out_or_in && u.out==v.out);
716        else
717          if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
718        //return (!u.out_or_in && u.in==v.in);
719      }
720      friend bool operator!=(const Edge& u, const Edge& v) {
721        if (v.out_or_in)
722          if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
723        //return (!u.out_or_in || u.out!=v.out);
724        else
725          if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
726        //return (u.out_or_in || u.in!=v.in);
727      }
728    };
729
730    class OutEdgeIt : public Edge {
731      friend class UndirGraphWrapper<GraphWrapper>;
732    public:
733      OutEdgeIt() : Edge() { }
734      OutEdgeIt(const Invalid& i) : Edge(i) { }
735      OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
736        : Edge() {
737        out_or_in=true; _G.gw.first(out, n);
738        if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
739      }
740    };
741
742    typedef OutEdgeIt InEdgeIt;
743
744    class EdgeIt : public Edge {
745      friend class UndirGraphWrapper<GraphWrapper>;
746    protected:
747      NodeIt v;
748    public:
749      EdgeIt() : Edge() { }
750      EdgeIt(const Invalid& i) : Edge(i) { }
751      EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
752        : Edge() {
753        out_or_in=true;
754        //Node v;
755        _G.first(v);
756        if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
757        while (_G.valid(v) && !_G.gw.valid(out)) {
758          _G.gw.next(v);
759          if (_G.valid(v)) _G.gw.first(out);
760        }
761      }
762    };
763
764    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
765      e.out_or_in=true; gw.first(e.out, n);
766      if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
767      return e;
768    }
769
770    EdgeIt& first(EdgeIt& e) const {
771      e.out_or_in=true;
772      //NodeIt v;
773      first(e.v);
774      if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
775      while (valid(e.v) && !gw.valid(e.out)) {
776        gw.next(e.v);
777        if (valid(e.v)) gw.first(e.out, e.v);
778      }
779      return e;
780    }
781
782    template<typename I> I& first(I& i) const { gw.first(i); return i; }
783    template<typename I, typename P> I& first(I& i, const P& p) const {
784      gw.first(i, p); return i; }
785
786    OutEdgeIt& next(OutEdgeIt& e) const {
787      if (e.out_or_in) {
788        Node n=gw.tail(e.out);
789        gw.next(e.out);
790        if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
791      } else {
792        gw.next(e.in);
793      }
794      return e;
795    }
796
797    EdgeIt& next(EdgeIt& e) const {
798      //NodeIt v=tail(e);
799      gw.next(e.out);
800      while (valid(e.v) && !gw.valid(e.out)) {
801        next(e.v);
802        if (valid(e.v)) gw.first(e.out, e.v);
803      }
804      return e;
805    }
806
807    template<typename I> I& next(I &i) const { return gw.next(i); }   
808//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
809
810    template< typename It > It first() const {
811      It e; first(e); return e; }
812
813    template< typename It > It first(const Node& v) const {
814      It e; first(e, v); return e; }
815
816//    Node head(const Edge& e) const { return gw.head(e); }
817//    Node tail(const Edge& e) const { return gw.tail(e); }
818
819//    template<typename I> bool valid(const I& i) const
820//      { return gw.valid(i); }
821 
822//    int nodeNum() const { return gw.nodeNum(); }
823//    int edgeNum() const { return gw.edgeNum(); }
824 
825//     template<typename I> Node aNode(const I& e) const {
826//       return graph->aNode(e); }
827//     template<typename I> Node bNode(const I& e) const {
828//       return graph->bNode(e); }
829
830    Node aNode(const OutEdgeIt& e) const {
831      if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
832    Node bNode(const OutEdgeIt& e) const {
833      if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
834 
835//    Node addNode() const { return gw.addNode(); }
836
837// FIXME: ez igy nem jo, mert nem
838//    Edge addEdge(const Node& tail, const Node& head) const {
839//      return graph->addEdge(tail, head); }
840 
841//    template<typename I> void erase(const I& i) const { gw.erase(i); }
842 
843//    void clear() const { gw.clear(); }
844   
845//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
846//     public:
847//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
848//      GraphWrapper::NodeMap<T>(_G.gw) { }
849//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
850//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
851//     };
852
853//     template<typename T> class EdgeMap :
854//       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
855//     public:
856//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
857//      GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
858//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
859//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
860//     };
861   };
862
863
864
865
866
867//   template<typename Graph>
868//   class SymGraphWrapper
869//   {
870//     Graph* graph;
871 
872//   public:
873//     typedef Graph BaseGraph;
874
875//     typedef typename Graph::Node Node;
876//     typedef typename Graph::Edge Edge;
877 
878//     typedef typename Graph::NodeIt NodeIt;
879   
880//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
881//     //iranyitatlant, ami van
882//     //mert csak 1 dolgot lehet be typedef-elni
883//     typedef typename Graph::OutEdgeIt SymEdgeIt;
884//     //typedef typename Graph::InEdgeIt SymEdgeIt;
885//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
886//     typedef typename Graph::EdgeIt EdgeIt;
887
888//     int nodeNum() const { return graph->nodeNum(); }
889//     int edgeNum() const { return graph->edgeNum(); }
890   
891//     template<typename I> I& first(I& i) const { return graph->first(i); }
892//     template<typename I, typename P> I& first(I& i, const P& p) const {
893//       return graph->first(i, p); }
894//     //template<typename I> I next(const I i); { return graph->goNext(i); }
895//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
896
897//     template< typename It > It first() const {
898//       It e; first(e); return e; }
899
900//     template< typename It > It first(Node v) const {
901//       It e; first(e, v); return e; }
902
903//     Node head(const Edge& e) const { return graph->head(e); }
904//     Node tail(const Edge& e) const { return graph->tail(e); }
905 
906//     template<typename I> Node aNode(const I& e) const {
907//       return graph->aNode(e); }
908//     template<typename I> Node bNode(const I& e) const {
909//       return graph->bNode(e); }
910 
911//     //template<typename I> bool valid(const I i);
912//     //{ return graph->valid(i); }
913 
914//     //template<typename I> void setInvalid(const I &i);
915//     //{ return graph->setInvalid(i); }
916 
917//     Node addNode() { return graph->addNode(); }
918//     Edge addEdge(const Node& tail, const Node& head) {
919//       return graph->addEdge(tail, head); }
920 
921//     template<typename I> void erase(const I& i) { graph->erase(i); }
922 
923//     void clear() { graph->clear(); }
924 
925//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
926//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
927 
928//     void setGraph(Graph& _graph) { graph = &_graph; }
929//     Graph& getGraph() { return (*graph); }
930
931//     //SymGraphWrapper() : graph(0) { }
932//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
933//   };
934
935
936  template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
937  class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
938  public:
939    //typedef Graph BaseGraph;
940    //typedef TrivGraphWrapper<const Graph> GraphWrapper;
941    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
942    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
943  private:
944    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OldOutEdgeIt;
945    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OldInEdgeIt;
946  protected:
947    //const Graph* graph;
948    //GraphWrapper gw;
949    FlowMap* flow;
950    const CapacityMap* capacity;
951  public:
952
953    ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
954                    const CapacityMap& _capacity) :
955      GraphWrapperSkeleton<GraphWrapper>(_gw),
956      flow(&_flow), capacity(&_capacity) { }
957
958    //void setGraph(const Graph& _graph) { graph = &_graph; }
959    //const Graph& getGraph() const { return (*graph); }
960
961    class Edge;
962    class OutEdgeIt;
963    friend class Edge;
964    friend class OutEdgeIt;
965
966    class Edge {
967      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
968    protected:
969      bool out_or_in; //true, iff out
970      OldOutEdgeIt out;
971      OldInEdgeIt in;
972    public:
973      Edge() : out_or_in(true) { }
974      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
975//       bool valid() const {
976//      return out_or_in && out.valid() || in.valid(); }
977      friend bool operator==(const Edge& u, const Edge& v) {
978        if (v.out_or_in)
979          return (u.out_or_in && u.out==v.out);
980        else
981          return (!u.out_or_in && u.in==v.in);
982      }
983      friend bool operator!=(const Edge& u, const Edge& v) {
984        if (v.out_or_in)
985          return (!u.out_or_in || u.out!=v.out);
986        else
987          return (u.out_or_in || u.in!=v.in);
988      }
989    };
990
991
992    class OutEdgeIt : public Edge {
993      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
994    public:
995      OutEdgeIt() { }
996      //FIXME
997      OutEdgeIt(const Edge& e) : Edge(e) { }
998      OutEdgeIt(const Invalid& i) : Edge(i) { }
999    protected:
1000      OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1001        resG.gw.first(out, v);
1002        while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
1003        if (!resG.gw.valid(out)) {
1004          out_or_in=0;
1005          resG.gw.first(in, v);
1006          while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
1007        }
1008      }
1009//     public:
1010//       OutEdgeIt& operator++() {
1011//      if (out_or_in) {
1012//        Node v=/*resG->*/G->aNode(out);
1013//        ++out;
1014//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
1015//        if (!out.valid()) {
1016//          out_or_in=0;
1017//          G->first(in, v);
1018//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
1019//        }
1020//      } else {
1021//        ++in;
1022//        while( in.valid() && !(Edge::free()>0) ) { ++in; }
1023//      }
1024//      return *this;
1025//       }
1026    };
1027
1028    //FIXME This is just for having InEdgeIt
1029    typedef void InEdgeIt;
1030
1031    class EdgeIt : public Edge {
1032      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1033      NodeIt v;
1034    public:
1035      EdgeIt() { }
1036      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1037      EdgeIt(const Invalid& i) : Edge(i) { }
1038      EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
1039        resG.gw.first(v);
1040        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
1041        while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
1042        while (resG.gw.valid(v) && !resG.gw.valid(out)) {
1043          resG.gw.next(v);
1044          if (resG.gw.valid(v)) resG.gw.first(out, v);
1045          while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
1046        }
1047        if (!resG.gw.valid(out)) {
1048          out_or_in=0;
1049          resG.gw.first(v);
1050          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
1051          while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
1052          while (resG.gw.valid(v) && !resG.gw.valid(in)) {
1053            resG.gw.next(v);
1054            if (resG.gw.valid(v)) resG.gw.first(in, v);
1055            while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
1056          }
1057        }
1058      }
1059//       EdgeIt& operator++() {
1060//      if (out_or_in) {
1061//        ++out;
1062//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
1063//        while (v.valid() && !out.valid()) {
1064//          ++v;
1065//          if (v.valid()) G->first(out, v);
1066//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
1067//        }
1068//        if (!out.valid()) {
1069//          out_or_in=0;
1070//          G->first(v);
1071//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1072//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
1073//          while (v.valid() && !in.valid()) {
1074//            ++v;
1075//            if (v.valid()) G->first(in, v);
1076//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
1077//          } 
1078//        }
1079//      } else {
1080//        ++in;
1081//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
1082//        while (v.valid() && !in.valid()) {
1083//          ++v;
1084//          if (v.valid()) G->first(in, v);
1085//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
1086//        }
1087//      }
1088//      return *this;
1089//       }
1090    };
1091
1092    NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
1093    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1094      e=OutEdgeIt(*this, v);
1095      return e;
1096    }
1097    EdgeIt& first(EdgeIt& e) const {
1098      e=EdgeIt(*this);
1099      return e;
1100    }
1101   
1102    NodeIt& next(NodeIt& n) const { return gw.next(n); }
1103
1104    OutEdgeIt& next(OutEdgeIt& e) const {
1105      if (e.out_or_in) {
1106        Node v=gw.aNode(e.out);
1107        gw.next(e.out);
1108        while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1109        if (!gw.valid(e.out)) {
1110          e.out_or_in=0;
1111          gw.first(e.in, v);
1112          while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1113        }
1114      } else {
1115        gw.next(e.in);
1116        while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1117      }
1118      return e;
1119    }
1120
1121    EdgeIt& next(EdgeIt& e) const {
1122      if (e.out_or_in) {
1123        gw.next(e.out);
1124        while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1125          while (gw.valid(e.v) && !gw.valid(e.out)) {
1126            gw.next(e.v);
1127            if (gw.valid(e.v)) gw.first(e.out, e.v);
1128            while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1129          }
1130          if (!gw.valid(e.out)) {
1131            e.out_or_in=0;
1132            gw.first(e.v);
1133            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
1134            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1135            while (gw.valid(e.v) && !gw.valid(e.in)) {
1136              gw.next(e.v);
1137              if (gw.valid(e.v)) gw.first(e.in, e.v);
1138              while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1139            } 
1140          }
1141        } else {
1142          gw.next(e.in);
1143          while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1144          while (gw.valid(e.v) && !gw.valid(e.in)) {
1145            gw.next(e.v);
1146            if (gw.valid(e.v)) gw.first(e.in, e.v);
1147            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1148          }
1149        }
1150        return e;
1151      }
1152   
1153
1154    template< typename It >
1155    It first() const {
1156      It e;
1157      first(e);
1158      return e;
1159    }
1160
1161    template< typename It >
1162    It first(Node v) const {
1163      It e;
1164      first(e, v);
1165      return e;
1166    }
1167
1168    Node tail(Edge e) const {
1169      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1170    Node head(Edge e) const {
1171      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1172
1173    Node aNode(OutEdgeIt e) const {
1174      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1175    Node bNode(OutEdgeIt e) const {
1176      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1177
1178    int nodeNum() const { return gw.nodeNum(); }
1179    //FIXME
1180    //int edgeNum() const { return gw.edgeNum(); }
1181
1182
1183    int id(Node v) const { return gw.id(v); }
1184
1185    bool valid(Node n) const { return gw.valid(n); }
1186    bool valid(Edge e) const {
1187      return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
1188
1189    void augment(const Edge& e, Number a) const {
1190      if (e.out_or_in) 
1191        flow->set(e.out, flow->get(e.out)+a);
1192      else 
1193        flow->set(e.in, flow->get(e.in)-a);
1194    }
1195
1196    Number free(const Edge& e) const {
1197      if (e.out_or_in)
1198        return (capacity->get(e.out)-flow->get(e.out));
1199      else
1200        return (flow->get(e.in));
1201    }
1202
1203    Number free(OldOutEdgeIt out) const {
1204      return (capacity->get(out)-flow->get(out));
1205    }
1206   
1207    Number free(OldInEdgeIt in) const {
1208      return (flow->get(in));
1209    }
1210
1211//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1212//     public:
1213//       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
1214//      : GraphWrapper::NodeMap<T>(_G.gw) { }
1215//       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
1216//            T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1217//     };
1218
1219//     template <typename T>
1220//     class NodeMap {
1221//       typename Graph::NodeMap<T> node_map;
1222//     public:
1223//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1224//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1225//       void set(Node nit, T a) { node_map.set(nit, a); }
1226//       T get(Node nit) const { return node_map.get(nit); }
1227//     };
1228
1229    template <typename T>
1230    class EdgeMap {
1231      typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1232    public:
1233      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1234      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1235      void set(Edge e, T a) {
1236        if (e.out_or_in)
1237          forward_map.set(e.out, a);
1238        else
1239          backward_map.set(e.in, a);
1240      }
1241      T get(Edge e) {
1242        if (e.out_or_in)
1243          return forward_map.get(e.out);
1244        else
1245          return backward_map.get(e.in);
1246      }
1247    };
1248  };
1249
1250//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1251//   class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1252//   protected:
1253//     ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1254//     //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1255//   public:
1256//     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1257//                         const CapacityMap& _capacity) :
1258//       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1259//       first_out_edges(*this) /*, dist(*this)*/ {
1260//       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1261//      OutEdgeIt e;
1262//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1263//      first_out_edges.set(n, e);
1264//       }
1265//     }
1266
1267//     //void setGraph(Graph& _graph) { graph = &_graph; }
1268//     //Graph& getGraph() const { return (*graph); }
1269 
1270//     //TrivGraphWrapper() : graph(0) { }
1271//     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1272
1273//     //typedef Graph BaseGraph;
1274
1275//     //typedef typename Graph::Node Node;
1276//     //typedef typename Graph::NodeIt NodeIt;
1277
1278//     //typedef typename Graph::Edge Edge;
1279//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
1280//     //typedef typename Graph::InEdgeIt InEdgeIt;
1281//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1282//     //typedef typename Graph::EdgeIt EdgeIt;
1283
1284//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1285//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1286
1287//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1288//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1289//     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1290//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1291//     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1292
1293//     NodeIt& first(NodeIt& n) const {
1294//       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1295//     }
1296
1297//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1298//       e=first_out_edges.get(n);
1299//       return e;
1300//     }
1301   
1302//     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1303//     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1304//     //  return first(i, p); }
1305   
1306//     //template<typename I> I getNext(const I& i) const {
1307//     //  return gw.getNext(i); }
1308//     //template<typename I> I& next(I &i) const { return gw.next(i); }   
1309
1310//     template< typename It > It first() const {
1311//       It e; first(e); return e; }
1312
1313//     template< typename It > It first(const Node& v) const {
1314//       It e; first(e, v); return e; }
1315
1316//     //Node head(const Edge& e) const { return gw.head(e); }
1317//     //Node tail(const Edge& e) const { return gw.tail(e); }
1318
1319//     //template<typename I> bool valid(const I& i) const
1320//     //  { return gw.valid(i); }
1321 
1322//     //int nodeNum() const { return gw.nodeNum(); }
1323//     //int edgeNum() const { return gw.edgeNum(); }
1324 
1325//     //template<typename I> Node aNode(const I& e) const {
1326//     //  return gw.aNode(e); }
1327//     //template<typename I> Node bNode(const I& e) const {
1328//     //  return gw.bNode(e); }
1329 
1330//     //Node addNode() const { return gw.addNode(); }
1331//     //Edge addEdge(const Node& tail, const Node& head) const {
1332//     //  return gw.addEdge(tail, head); }
1333 
1334//     //void erase(const OutEdgeIt& e) {
1335//     //  first_out_edge(this->tail(e))=e;
1336//     //}
1337//     void erase(const Edge& e) {
1338//       OutEdgeIt f(e);
1339//       next(f);
1340//       first_out_edges.set(this->tail(e), f);
1341//     }
1342//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
1343 
1344//     //void clear() const { gw.clear(); }
1345   
1346//     template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1347//     public:
1348//       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1349//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1350//       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1351//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1352//     };
1353
1354//     template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1355//     public:
1356//       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1357//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1358//       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1359//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1360//     };
1361//   };
1362
1363//   template<typename GraphWrapper>
1364//   class FilterGraphWrapper {
1365//   };
1366
1367//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1368//   class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1369
1370//     //Graph* graph;
1371 
1372//   public:
1373//     //typedef Graph BaseGraph;
1374
1375//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1376//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1377
1378//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1379//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1380//     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1381//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1382//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1383
1384//     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1385   
1386//   public:
1387//     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1388//                         const CapacityMap& _capacity) :
1389//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1390//     }
1391
1392//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1393//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1394//       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1395//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1396//       return e;
1397//     }
1398
1399//     NodeIt& next(NodeIt& e) const {
1400//       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1401//     }
1402
1403//     OutEdgeIt& next(OutEdgeIt& e) const {
1404//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1405//       while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1406//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1407//       return e;
1408//     }
1409
1410//     NodeIt& first(NodeIt& n) const {
1411//       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1412//     }
1413
1414//     void erase(const Edge& e) {
1415//       OutEdgeIt f(e);
1416//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1417//       while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1418//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1419//       first_out_edges.set(this->tail(e), f);
1420//     }
1421
1422//     //TrivGraphWrapper() : graph(0) { }
1423//     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1424
1425//     //void setGraph(Graph& _graph) { graph = &_graph; }
1426//     //Graph& getGraph() const { return (*graph); }
1427   
1428//     //template<typename I> I& first(I& i) const { return gw.first(i); }
1429//     //template<typename I, typename P> I& first(I& i, const P& p) const {
1430//     //  return gw.first(i, p); }
1431   
1432//     //template<typename I> I getNext(const I& i) const {
1433//     //  return gw.getNext(i); }
1434//     //template<typename I> I& next(I &i) const { return gw.next(i); }   
1435
1436//     template< typename It > It first() const {
1437//       It e; first(e); return e; }
1438
1439//     template< typename It > It first(const Node& v) const {
1440//       It e; first(e, v); return e; }
1441
1442//     //Node head(const Edge& e) const { return gw.head(e); }
1443//     //Node tail(const Edge& e) const { return gw.tail(e); }
1444
1445//     //template<typename I> bool valid(const I& i) const
1446//     //  { return gw.valid(i); }
1447 
1448//     //template<typename I> void setInvalid(const I &i);
1449//     //{ return gw.setInvalid(i); }
1450
1451//     //int nodeNum() const { return gw.nodeNum(); }
1452//     //int edgeNum() const { return gw.edgeNum(); }
1453 
1454//     //template<typename I> Node aNode(const I& e) const {
1455//     //  return gw.aNode(e); }
1456//     //template<typename I> Node bNode(const I& e) const {
1457//     //  return gw.bNode(e); }
1458 
1459//     //Node addNode() const { return gw.addNode(); }
1460//     //Edge addEdge(const Node& tail, const Node& head) const {
1461//     //  return gw.addEdge(tail, head); }
1462 
1463//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
1464 
1465//     //void clear() const { gw.clear(); }
1466   
1467//     template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1468//     public:
1469//       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1470//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1471//       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1472//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1473//     };
1474
1475//     template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1476//     public:
1477//       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1478//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1479//       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1480//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1481//     };
1482
1483//   public:
1484//     ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1485
1486//   };
1487
1488
1489
1490// // FIXME: comparison should be made better!!!
1491//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1492//   class ResGraphWrapper
1493//   {
1494//     Graph* graph;
1495 
1496//   public:
1497//     typedef Graph BaseGraph;
1498
1499//     typedef typename Graph::Node Node;
1500//     typedef typename Graph::Edge Edge;
1501 
1502//     typedef typename Graph::NodeIt NodeIt;
1503   
1504//     class OutEdgeIt {
1505//     public:
1506//       //Graph::Node n;
1507//       bool out_or_in;
1508//       typename Graph::OutEdgeIt o;
1509//       typename Graph::InEdgeIt i;   
1510//     };
1511//     class InEdgeIt {
1512//     public:
1513//       //Graph::Node n;
1514//       bool out_or_in;
1515//       typename Graph::OutEdgeIt o;
1516//       typename Graph::InEdgeIt i;   
1517//     };
1518//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1519//     typedef typename Graph::EdgeIt EdgeIt;
1520
1521//     int nodeNum() const { return gw.nodeNum(); }
1522//     int edgeNum() const { return gw.edgeNum(); }
1523
1524//     Node& first(Node& n) const { return gw.first(n); }
1525
1526//     // Edge and SymEdge  is missing!!!!
1527//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1528
1529//     //FIXME
1530//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1531//       {
1532//      e.n=n;
1533//      gw.first(e.o,n);
1534//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1535//        gw.goNext(e.o);
1536//      if(!gw.valid(e.o)) {
1537//        gw.first(e.i,n);
1538//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1539//          gw.goNext(e.i);
1540//      }
1541//      return e;
1542//       }
1543// /*
1544//   OutEdgeIt &goNext(OutEdgeIt &e)
1545//   {
1546//   if(gw.valid(e.o)) {
1547//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1548//   gw.goNext(e.o);
1549//   if(gw.valid(e.o)) return e;
1550//   else gw.first(e.i,e.n);
1551//   }
1552//   else {
1553//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1554//   gw.goNext(e.i);
1555//   return e;
1556//   }
1557//   }
1558//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1559// */
1560//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1561
1562//     //FIXME
1563//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1564//       {
1565//      e.n=n;
1566//      gw.first(e.i,n);
1567//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1568//        gw.goNext(e.i);
1569//      if(!gw.valid(e.i)) {
1570//        gw.first(e.o,n);
1571//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1572//          gw.goNext(e.o);
1573//      }
1574//      return e;
1575//       }
1576// /*
1577//   InEdgeIt &goNext(InEdgeIt &e)
1578//   {
1579//   if(gw.valid(e.i)) {
1580//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1581//   gw.goNext(e.i);
1582//   if(gw.valid(e.i)) return e;
1583//   else gw.first(e.o,e.n);
1584//   }
1585//   else {
1586//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1587//   gw.goNext(e.o);
1588//   return e;
1589//   }
1590//   }
1591//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1592// */
1593//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1594
1595//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1596//     //template<typename I> I next(const I i); { return gw.goNext(i); }
1597
1598//     template< typename It > It first() const {
1599//       It e; first(e); return e; }
1600
1601//     template< typename It > It first(Node v) const {
1602//       It e; first(e, v); return e; }
1603
1604//     Node head(const Edge& e) const { return gw.head(e); }
1605//     Node tail(const Edge& e) const { return gw.tail(e); }
1606 
1607//     template<typename I> Node aNode(const I& e) const {
1608//       return gw.aNode(e); }
1609//     template<typename I> Node bNode(const I& e) const {
1610//       return gw.bNode(e); }
1611 
1612//     //template<typename I> bool valid(const I i);
1613//     //{ return gw.valid(i); }
1614 
1615//     //template<typename I> void setInvalid(const I &i);
1616//     //{ return gw.setInvalid(i); }
1617 
1618//     Node addNode() { return gw.addNode(); }
1619//     Edge addEdge(const Node& tail, const Node& head) {
1620//       return gw.addEdge(tail, head); }
1621 
1622//     template<typename I> void erase(const I& i) { gw.erase(i); }
1623 
1624//     void clear() { gw.clear(); }
1625 
1626//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1627//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1628 
1629//     void setGraph(Graph& _graph) { graph = &_graph; }
1630//     Graph& getGraph() { return (*graph); }
1631
1632//     //ResGraphWrapper() : graph(0) { }
1633//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1634//   };
1635
1636} //namespace hugo
1637
1638#endif //HUGO_GRAPH_WRAPPER_H
1639
Note: See TracBrowser for help on using the repository browser.