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 @ 238:ad3bdd78f4f6

Last change on this file since 238:ad3bdd78f4f6 was 238:ad3bdd78f4f6, checked in by marci, 21 years ago

.
File size: 49.4 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      friend bool operator==(const Edge& u, const Edge& v) {
544        if (v.out_or_in)
545          return (u.out_or_in && u.out==v.out);
546        else
547          return (!u.out_or_in && u.in==v.in);
548      }
549      friend bool operator!=(const Edge& u, const Edge& v) {
550        if (v.out_or_in)
551          return (!u.out_or_in || u.out!=v.out);
552        else
553          return (u.out_or_in || u.in!=v.in);
554      }
555    };
556
557    class OutEdgeIt : public Edge {
558      friend class UndirGraphWrapper<GraphWrapper>;
559    public:
560      OutEdgeIt() : Edge() { }
561      OutEdgeIt(const Invalid& i) : Edge(i) { }
562      OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
563        : Edge() {
564        out_or_in=true;
565        _G.gw.first(out, n);
566        if (!(_G.gw.valid(out))) {
567          out_or_in=false;
568          _G.gw.first(in, n);
569        }
570      }
571    };
572
573    typedef OutEdgeIt InEdgeIt;
574
575    class EdgeIt : public Edge {
576      friend class UndirGraphWrapper<GraphWrapper>;
577    protected:
578      NodeIt v;
579    public:
580      EdgeIt() : Edge() { }
581      EdgeIt(const Invalid& i) : Edge(i) { }
582      EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
583        : Edge() {
584        out_or_in=true;
585        //Node v;
586        _G.first(v);
587        if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
588        while (_G.valid(v) && !_G.gw.valid(out)) {
589          _G.gw.next(v);
590          if (_G.valid(v)) _G.gw.first(out);
591        }
592      }
593    };
594
595    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
596      e.out_or_in=true;
597      gw.first(e.out, n);
598      if (!(gw.valid(e.out))) {
599        e.out_or_in=false;
600        gw.first(e.in, n);
601      }
602      return e;
603    }
604
605    EdgeIt& first(EdgeIt& e) const {
606      e.out_or_in=true;
607      //NodeIt v;
608      first(e.v);
609      if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
610      while (valid(e.v) && !gw.valid(e.out)) {
611        gw.next(e.v);
612        if (valid(e.v)) gw.first(e.out, e.v);
613      }
614      return e;
615    }
616
617    template<typename I> I& first(I& i) const { return gw.first(i); }
618    template<typename I, typename P> I& first(I& i, const P& p) const {
619      return graph->first(i, p); }
620
621    OutEdgeIt& next(OutEdgeIt& e) const {
622      if (e.out_or_in) {
623        Node n=gw.tail(e.out);
624        gw.next(e.out);
625        if (!gw.valid(e.out)) {
626          e.out_or_in=false;
627          gw.first(e.in, n);
628        }
629      } else {
630        gw.next(e.in);
631      }
632      return e;
633    }
634
635    EdgeIt& next(EdgeIt& e) const {
636      //NodeIt v=tail(e);
637      gw.next(e.out);
638      while (valid(e.v) && !gw.valid(e.out)) {
639        next(e.v);
640        if (valid(e.v)) gw.first(e.out, e.v);
641      }
642      return e;
643    }
644
645    template<typename I> I& next(I &i) const { return gw.next(i); }   
646   
647    template<typename I> I getNext(const I& i) const {
648      return gw.getNext(i); }
649
650    template< typename It > It first() const {
651      It e; first(e); return e; }
652
653    template< typename It > It first(const Node& v) const {
654      It e; first(e, v); return e; }
655
656//    Node head(const Edge& e) const { return gw.head(e); }
657//    Node tail(const Edge& e) const { return gw.tail(e); }
658
659//    template<typename I> bool valid(const I& i) const
660//      { return gw.valid(i); }
661 
662//    int nodeNum() const { return gw.nodeNum(); }
663//    int edgeNum() const { return gw.edgeNum(); }
664 
665//     template<typename I> Node aNode(const I& e) const {
666//       return graph->aNode(e); }
667//     template<typename I> Node bNode(const I& e) const {
668//       return graph->bNode(e); }
669
670    Node aNode(const OutEdgeIt& e) const {
671      if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
672    Node bNode(const OutEdgeIt& e) const {
673      if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
674 
675//    Node addNode() const { return gw.addNode(); }
676
677// FIXME: ez igy nem jo, mert nem
678//    Edge addEdge(const Node& tail, const Node& head) const {
679//      return graph->addEdge(tail, head); }
680 
681//    template<typename I> void erase(const I& i) const { gw.erase(i); }
682 
683//    void clear() const { gw.clear(); }
684   
685//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
686//     public:
687//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
688//      GraphWrapper::NodeMap<T>(_G.gw) { }
689//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
690//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
691//     };
692
693//     template<typename T> class EdgeMap :
694//       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
695//     public:
696//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
697//      GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
698//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
699//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
700//     };
701   };
702
703
704
705
706
707//   template<typename Graph>
708//   class SymGraphWrapper
709//   {
710//     Graph* graph;
711 
712//   public:
713//     typedef Graph BaseGraph;
714
715//     typedef typename Graph::Node Node;
716//     typedef typename Graph::Edge Edge;
717 
718//     typedef typename Graph::NodeIt NodeIt;
719   
720//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
721//     //iranyitatlant, ami van
722//     //mert csak 1 dolgot lehet be typedef-elni
723//     typedef typename Graph::OutEdgeIt SymEdgeIt;
724//     //typedef typename Graph::InEdgeIt SymEdgeIt;
725//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
726//     typedef typename Graph::EdgeIt EdgeIt;
727
728//     int nodeNum() const { return graph->nodeNum(); }
729//     int edgeNum() const { return graph->edgeNum(); }
730   
731//     template<typename I> I& first(I& i) const { return graph->first(i); }
732//     template<typename I, typename P> I& first(I& i, const P& p) const {
733//       return graph->first(i, p); }
734//     //template<typename I> I next(const I i); { return graph->goNext(i); }
735//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
736
737//     template< typename It > It first() const {
738//       It e; first(e); return e; }
739
740//     template< typename It > It first(Node v) const {
741//       It e; first(e, v); return e; }
742
743//     Node head(const Edge& e) const { return graph->head(e); }
744//     Node tail(const Edge& e) const { return graph->tail(e); }
745 
746//     template<typename I> Node aNode(const I& e) const {
747//       return graph->aNode(e); }
748//     template<typename I> Node bNode(const I& e) const {
749//       return graph->bNode(e); }
750 
751//     //template<typename I> bool valid(const I i);
752//     //{ return graph->valid(i); }
753 
754//     //template<typename I> void setInvalid(const I &i);
755//     //{ return graph->setInvalid(i); }
756 
757//     Node addNode() { return graph->addNode(); }
758//     Edge addEdge(const Node& tail, const Node& head) {
759//       return graph->addEdge(tail, head); }
760 
761//     template<typename I> void erase(const I& i) { graph->erase(i); }
762 
763//     void clear() { graph->clear(); }
764 
765//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
766//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
767 
768//     void setGraph(Graph& _graph) { graph = &_graph; }
769//     Graph& getGraph() { return (*graph); }
770
771//     //SymGraphWrapper() : graph(0) { }
772//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
773//   };
774
775
776  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
777  class ResGraphWrapper {
778  public:
779    typedef Graph BaseGraph;
780    typedef typename Graph::Node Node;
781    typedef typename Graph::NodeIt NodeIt;
782  private:
783    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
784    typedef typename Graph::InEdgeIt OldInEdgeIt;
785  protected:
786    const Graph* graph;
787    FlowMap* flow;
788    const CapacityMap* capacity;
789  public:
790
791    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
792             const CapacityMap& _capacity) :
793      graph(&_G), flow(&_flow), capacity(&_capacity) { }
794
795    void setGraph(const Graph& _graph) { graph = &_graph; }
796    const Graph& getGraph() const { return (*graph); }
797
798    class Edge;
799    class OutEdgeIt;
800    friend class Edge;
801    friend class OutEdgeIt;
802
803    class Edge {
804      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
805    protected:
806      bool out_or_in; //true, iff out
807      OldOutEdgeIt out;
808      OldInEdgeIt in;
809    public:
810      Edge() : out_or_in(true) { }
811      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
812//       bool valid() const {
813//      return out_or_in && out.valid() || in.valid(); }
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      friend bool operator!=(const Edge& u, const Edge& v) {
821        if (v.out_or_in)
822          return (!u.out_or_in || u.out!=v.out);
823        else
824          return (u.out_or_in || u.in!=v.in);
825      }
826    };
827
828
829    class OutEdgeIt : public Edge {
830      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
831    public:
832      OutEdgeIt() { }
833      //FIXME
834      OutEdgeIt(const Edge& e) : Edge(e) { }
835      OutEdgeIt(const Invalid& i) : Edge(i) { }
836    private:
837      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
838        resG.graph->first(out, v);
839        while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
840        if (!resG.graph->valid(out)) {
841          out_or_in=0;
842          resG.graph->first(in, v);
843          while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
844        }
845      }
846//     public:
847//       OutEdgeIt& operator++() {
848//      if (out_or_in) {
849//        Node v=/*resG->*/G->aNode(out);
850//        ++out;
851//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
852//        if (!out.valid()) {
853//          out_or_in=0;
854//          G->first(in, v);
855//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
856//        }
857//      } else {
858//        ++in;
859//        while( in.valid() && !(Edge::free()>0) ) { ++in; }
860//      }
861//      return *this;
862//       }
863    };
864
865    class EdgeIt : public Edge {
866      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
867      typename Graph::NodeIt v;
868    public:
869      EdgeIt() { }
870      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
871      EdgeIt(const Invalid& i) : Edge(i) { }
872      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
873        resG.graph->first(v);
874        if (resG.graph->valid(v)) resG.graph->first(out, v); else out=OldOutEdgeIt(INVALID);
875        while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
876        while (resG.graph->valid(v) && !resG.graph->valid(out)) {
877          resG.graph->next(v);
878          if (resG.graph->valid(v)) resG.graph->first(out, v);
879          while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
880        }
881        if (!resG.graph->valid(out)) {
882          out_or_in=0;
883          resG.graph->first(v);
884          if (resG.graph->valid(v)) resG.graph->first(in, v); else in=OldInEdgeIt(INVALID);
885          while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
886          while (resG.graph->valid(v) && !resG.graph->valid(in)) {
887            resG.graph->next(v);
888            if (resG.graph->valid(v)) resG.graph->first(in, v);
889            while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
890          }
891        }
892      }
893//       EdgeIt& operator++() {
894//      if (out_or_in) {
895//        ++out;
896//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
897//        while (v.valid() && !out.valid()) {
898//          ++v;
899//          if (v.valid()) G->first(out, v);
900//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
901//        }
902//        if (!out.valid()) {
903//          out_or_in=0;
904//          G->first(v);
905//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
906//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
907//          while (v.valid() && !in.valid()) {
908//            ++v;
909//            if (v.valid()) G->first(in, v);
910//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
911//          } 
912//        }
913//      } else {
914//        ++in;
915//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
916//        while (v.valid() && !in.valid()) {
917//          ++v;
918//          if (v.valid()) G->first(in, v);
919//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
920//        }
921//      }
922//      return *this;
923//       }
924    };
925
926    NodeIt& first(NodeIt& v) const { return graph->first(v); }
927    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
928      e=OutEdgeIt(*this, v);
929      return e;
930    }
931    EdgeIt& first(EdgeIt& e) const {
932      e=EdgeIt(*this);
933      return e;
934    }
935   
936    NodeIt& next(NodeIt& n) const { return graph->next(n); }
937
938    OutEdgeIt& next(OutEdgeIt& e) const {
939      if (e.out_or_in) {
940        Node v=graph->aNode(e.out);
941        graph->next(e.out);
942        while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
943        if (!graph->valid(e.out)) {
944          e.out_or_in=0;
945          graph->first(e.in, v);
946          while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
947        }
948      } else {
949        graph->next(e.in);
950        while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
951      }
952      return e;
953    }
954
955    EdgeIt& next(EdgeIt& e) const {
956      if (e.out_or_in) {
957        graph->next(e.out);
958        while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
959          while (graph->valid(e.v) && !graph->valid(e.out)) {
960            graph->next(e.v);
961            if (graph->valid(e.v)) graph->first(e.out, e.v);
962            while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
963          }
964          if (!graph->valid(e.out)) {
965            e.out_or_in=0;
966            graph->first(e.v);
967            if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
968            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
969            while (graph->valid(e.v) && !graph->valid(e.in)) {
970              graph->next(e.v);
971              if (graph->valid(e.v)) graph->first(e.in, e.v);
972              while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
973            } 
974          }
975        } else {
976          graph->next(e.in);
977          while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
978          while (graph->valid(e.v) && !graph->valid(e.in)) {
979            graph->next(e.v);
980            if (graph->valid(e.v)) graph->first(e.in, e.v);
981            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
982          }
983        }
984        return e;
985      }
986   
987
988    template< typename It >
989    It first() const {
990      It e;
991      first(e);
992      return e;
993    }
994
995    template< typename It >
996    It first(Node v) const {
997      It e;
998      first(e, v);
999      return e;
1000    }
1001
1002    Node tail(Edge e) const {
1003      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1004    Node head(Edge e) const {
1005      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1006
1007    Node aNode(OutEdgeIt e) const {
1008      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1009    Node bNode(OutEdgeIt e) const {
1010      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1011
1012    int id(Node v) const { return graph->id(v); }
1013
1014    bool valid(Node n) const { return graph->valid(n); }
1015    bool valid(Edge e) const {
1016      return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1017
1018    void augment(const Edge& e, Number a) const {
1019      if (e.out_or_in) 
1020        flow->set(e.out, flow->get(e.out)+a);
1021      else 
1022        flow->set(e.in, flow->get(e.in)-a);
1023    }
1024
1025    Number free(const Edge& e) const {
1026      if (e.out_or_in)
1027        return (capacity->get(e.out)-flow->get(e.out));
1028      else
1029        return (flow->get(e.in));
1030    }
1031
1032    Number free(OldOutEdgeIt out) const {
1033      return (capacity->get(out)-flow->get(out));
1034    }
1035   
1036    Number free(OldInEdgeIt in) const {
1037      return (flow->get(in));
1038    }
1039
1040    template<typename T> class NodeMap : public Graph::NodeMap<T> {
1041    public:
1042      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1043        : Graph::NodeMap<T>(_G.getGraph()) { }
1044      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1045              T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
1046    };
1047
1048//     template <typename T>
1049//     class NodeMap {
1050//       typename Graph::NodeMap<T> node_map;
1051//     public:
1052//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1053//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1054//       void set(Node nit, T a) { node_map.set(nit, a); }
1055//       T get(Node nit) const { return node_map.get(nit); }
1056//     };
1057
1058    template <typename T>
1059    class EdgeMap {
1060      typename Graph::EdgeMap<T> forward_map, backward_map;
1061    public:
1062      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
1063      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
1064      void set(Edge e, T a) {
1065        if (e.out_or_in)
1066          forward_map.set(e.out, a);
1067        else
1068          backward_map.set(e.in, a);
1069      }
1070      T get(Edge e) {
1071        if (e.out_or_in)
1072          return forward_map.get(e.out);
1073        else
1074          return backward_map.get(e.in);
1075      }
1076    };
1077  };
1078
1079  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1080  class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1081  protected:
1082    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1083    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1084  public:
1085    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1086                           const CapacityMap& _capacity) :
1087      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1088      first_out_edges(*this) /*, dist(*this)*/ {
1089      for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1090        OutEdgeIt e;
1091        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1092        first_out_edges.set(n, e);
1093      }
1094    }
1095
1096    //void setGraph(Graph& _graph) { graph = &_graph; }
1097    //Graph& getGraph() const { return (*graph); }
1098 
1099    //TrivGraphWrapper() : graph(0) { }
1100    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1101
1102    //typedef Graph BaseGraph;
1103
1104    //typedef typename Graph::Node Node;
1105    //typedef typename Graph::NodeIt NodeIt;
1106
1107    //typedef typename Graph::Edge Edge;
1108    //typedef typename Graph::OutEdgeIt OutEdgeIt;
1109    //typedef typename Graph::InEdgeIt InEdgeIt;
1110    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1111    //typedef typename Graph::EdgeIt EdgeIt;
1112
1113    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1114    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1115
1116    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1117    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1118    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1119    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1120    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1121
1122    NodeIt& first(NodeIt& n) const {
1123      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1124    }
1125
1126    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1127      e=first_out_edges.get(n);
1128      return e;
1129    }
1130   
1131    //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1132    //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1133    //  return first(i, p); }
1134   
1135    //template<typename I> I getNext(const I& i) const {
1136    //  return graph->getNext(i); }
1137    //template<typename I> I& next(I &i) const { return graph->next(i); }   
1138
1139    template< typename It > It first() const {
1140      It e; first(e); return e; }
1141
1142    template< typename It > It first(const Node& v) const {
1143      It e; first(e, v); return e; }
1144
1145    //Node head(const Edge& e) const { return graph->head(e); }
1146    //Node tail(const Edge& e) const { return graph->tail(e); }
1147
1148    //template<typename I> bool valid(const I& i) const
1149    //  { return graph->valid(i); }
1150 
1151    //int nodeNum() const { return graph->nodeNum(); }
1152    //int edgeNum() const { return graph->edgeNum(); }
1153 
1154    //template<typename I> Node aNode(const I& e) const {
1155    //  return graph->aNode(e); }
1156    //template<typename I> Node bNode(const I& e) const {
1157    //  return graph->bNode(e); }
1158 
1159    //Node addNode() const { return graph->addNode(); }
1160    //Edge addEdge(const Node& tail, const Node& head) const {
1161    //  return graph->addEdge(tail, head); }
1162 
1163    //void erase(const OutEdgeIt& e) {
1164    //  first_out_edge(this->tail(e))=e;
1165    //}
1166    void erase(const Edge& e) {
1167      OutEdgeIt f(e);
1168      next(f);
1169      first_out_edges.set(this->tail(e), f);
1170    }
1171    //template<typename I> void erase(const I& i) const { graph->erase(i); }
1172 
1173    //void clear() const { graph->clear(); }
1174   
1175    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1176    public:
1177      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1178        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1179      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1180        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1181    };
1182
1183    template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1184    public:
1185      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1186        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1187      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1188        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1189    };
1190  };
1191
1192  template<typename GraphWrapper>
1193  class FilterGraphWrapper {
1194  };
1195
1196  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1197  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1198
1199    //Graph* graph;
1200 
1201  public:
1202    //typedef Graph BaseGraph;
1203
1204    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1205    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1206
1207    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1208    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1209    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1210    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1211    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1212
1213    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1214   
1215  public:
1216    FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1217                           const CapacityMap& _capacity) :
1218      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, graph->nodeNum()) {
1219    }
1220
1221    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1222      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1223      while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1224        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1225      return e;
1226    }
1227
1228    NodeIt& next(NodeIt& e) const {
1229      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1230    }
1231
1232    OutEdgeIt& next(OutEdgeIt& e) const {
1233      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1234      while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1235        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1236      return e;
1237    }
1238
1239    NodeIt& first(NodeIt& n) const {
1240      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1241    }
1242
1243    void erase(const Edge& e) {
1244      OutEdgeIt f(e);
1245      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1246      while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1247        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1248      first_out_edges.set(this->tail(e), f);
1249    }
1250
1251    //TrivGraphWrapper() : graph(0) { }
1252    //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1253
1254    //void setGraph(Graph& _graph) { graph = &_graph; }
1255    //Graph& getGraph() const { return (*graph); }
1256   
1257    //template<typename I> I& first(I& i) const { return graph->first(i); }
1258    //template<typename I, typename P> I& first(I& i, const P& p) const {
1259    //  return graph->first(i, p); }
1260   
1261    //template<typename I> I getNext(const I& i) const {
1262    //  return graph->getNext(i); }
1263    //template<typename I> I& next(I &i) const { return graph->next(i); }   
1264
1265    template< typename It > It first() const {
1266      It e; first(e); return e; }
1267
1268    template< typename It > It first(const Node& v) const {
1269      It e; first(e, v); return e; }
1270
1271    //Node head(const Edge& e) const { return graph->head(e); }
1272    //Node tail(const Edge& e) const { return graph->tail(e); }
1273
1274    //template<typename I> bool valid(const I& i) const
1275    //  { return graph->valid(i); }
1276 
1277    //template<typename I> void setInvalid(const I &i);
1278    //{ return graph->setInvalid(i); }
1279
1280    //int nodeNum() const { return graph->nodeNum(); }
1281    //int edgeNum() const { return graph->edgeNum(); }
1282 
1283    //template<typename I> Node aNode(const I& e) const {
1284    //  return graph->aNode(e); }
1285    //template<typename I> Node bNode(const I& e) const {
1286    //  return graph->bNode(e); }
1287 
1288    //Node addNode() const { return graph->addNode(); }
1289    //Edge addEdge(const Node& tail, const Node& head) const {
1290    //  return graph->addEdge(tail, head); }
1291 
1292    //template<typename I> void erase(const I& i) const { graph->erase(i); }
1293 
1294    //void clear() const { graph->clear(); }
1295   
1296    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1297    public:
1298      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1299        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1300      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1301        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1302    };
1303
1304    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1305    public:
1306      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1307        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1308      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1309        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1310    };
1311
1312  public:
1313    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1314
1315  };
1316
1317
1318
1319// // FIXME: comparison should be made better!!!
1320//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1321//   class ResGraphWrapper
1322//   {
1323//     Graph* graph;
1324 
1325//   public:
1326//     typedef Graph BaseGraph;
1327
1328//     typedef typename Graph::Node Node;
1329//     typedef typename Graph::Edge Edge;
1330 
1331//     typedef typename Graph::NodeIt NodeIt;
1332   
1333//     class OutEdgeIt {
1334//     public:
1335//       //Graph::Node n;
1336//       bool out_or_in;
1337//       typename Graph::OutEdgeIt o;
1338//       typename Graph::InEdgeIt i;   
1339//     };
1340//     class InEdgeIt {
1341//     public:
1342//       //Graph::Node n;
1343//       bool out_or_in;
1344//       typename Graph::OutEdgeIt o;
1345//       typename Graph::InEdgeIt i;   
1346//     };
1347//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1348//     typedef typename Graph::EdgeIt EdgeIt;
1349
1350//     int nodeNum() const { return graph->nodeNum(); }
1351//     int edgeNum() const { return graph->edgeNum(); }
1352
1353//     Node& first(Node& n) const { return graph->first(n); }
1354
1355//     // Edge and SymEdge  is missing!!!!
1356//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1357
1358//     //FIXME
1359//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1360//       {
1361//      e.n=n;
1362//      graph->first(e.o,n);
1363//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1364//        graph->goNext(e.o);
1365//      if(!graph->valid(e.o)) {
1366//        graph->first(e.i,n);
1367//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1368//          graph->goNext(e.i);
1369//      }
1370//      return e;
1371//       }
1372// /*
1373//   OutEdgeIt &goNext(OutEdgeIt &e)
1374//   {
1375//   if(graph->valid(e.o)) {
1376//   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1377//   graph->goNext(e.o);
1378//   if(graph->valid(e.o)) return e;
1379//   else graph->first(e.i,e.n);
1380//   }
1381//   else {
1382//   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1383//   graph->goNext(e.i);
1384//   return e;
1385//   }
1386//   }
1387//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1388// */
1389//     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
1390
1391//     //FIXME
1392//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1393//       {
1394//      e.n=n;
1395//      graph->first(e.i,n);
1396//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1397//        graph->goNext(e.i);
1398//      if(!graph->valid(e.i)) {
1399//        graph->first(e.o,n);
1400//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1401//          graph->goNext(e.o);
1402//      }
1403//      return e;
1404//       }
1405// /*
1406//   InEdgeIt &goNext(InEdgeIt &e)
1407//   {
1408//   if(graph->valid(e.i)) {
1409//   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1410//   graph->goNext(e.i);
1411//   if(graph->valid(e.i)) return e;
1412//   else graph->first(e.o,e.n);
1413//   }
1414//   else {
1415//   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1416//   graph->goNext(e.o);
1417//   return e;
1418//   }
1419//   }
1420//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1421// */
1422//     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
1423
1424//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1425//     //template<typename I> I next(const I i); { return graph->goNext(i); }
1426
1427//     template< typename It > It first() const {
1428//       It e; first(e); return e; }
1429
1430//     template< typename It > It first(Node v) const {
1431//       It e; first(e, v); return e; }
1432
1433//     Node head(const Edge& e) const { return graph->head(e); }
1434//     Node tail(const Edge& e) const { return graph->tail(e); }
1435 
1436//     template<typename I> Node aNode(const I& e) const {
1437//       return graph->aNode(e); }
1438//     template<typename I> Node bNode(const I& e) const {
1439//       return graph->bNode(e); }
1440 
1441//     //template<typename I> bool valid(const I i);
1442//     //{ return graph->valid(i); }
1443 
1444//     //template<typename I> void setInvalid(const I &i);
1445//     //{ return graph->setInvalid(i); }
1446 
1447//     Node addNode() { return graph->addNode(); }
1448//     Edge addEdge(const Node& tail, const Node& head) {
1449//       return graph->addEdge(tail, head); }
1450 
1451//     template<typename I> void erase(const I& i) { graph->erase(i); }
1452 
1453//     void clear() { graph->clear(); }
1454 
1455//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1456//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1457 
1458//     void setGraph(Graph& _graph) { graph = &_graph; }
1459//     Graph& getGraph() { return (*graph); }
1460
1461//     //ResGraphWrapper() : graph(0) { }
1462//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1463//   };
1464
1465} //namespace hugo
1466
1467#endif //GRAPH_WRAPPER_H
1468
Note: See TracBrowser for help on using the repository browser.