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 @ 253:f45703336699

Last change on this file since 253:f45703336699 was 239:3f76d1aa9d37, checked in by marci, 21 years ago

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