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 @ 259:509ba9f136d2

Last change on this file since 259:509ba9f136d2 was 259:509ba9f136d2, checked in by marci, 20 years ago

ResGraphWrapper? partial improvement
File size: 49.2 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
4
5#include <invalid.h>
6
7namespace hugo {
8
9  template<typename Graph>
10  class 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    typedef TrivGraphWrapper<const Graph> GraphWrapper;
782    GraphWrapper gw;
783    FlowMap* flow;
784    const CapacityMap* capacity;
785  public:
786
787    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
788             const CapacityMap& _capacity) :
789      gw(_G), flow(&_flow), capacity(&_capacity) { }
790
791    //void setGraph(const Graph& _graph) { graph = &_graph; }
792    //const Graph& getGraph() const { return (*graph); }
793
794    class Edge;
795    class OutEdgeIt;
796    friend class Edge;
797    friend class OutEdgeIt;
798
799    class Edge {
800      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
801    protected:
802      bool out_or_in; //true, iff out
803      OldOutEdgeIt out;
804      OldInEdgeIt in;
805    public:
806      Edge() : out_or_in(true) { }
807      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
808//       bool valid() const {
809//      return out_or_in && out.valid() || in.valid(); }
810      friend bool operator==(const Edge& u, const Edge& v) {
811        if (v.out_or_in)
812          return (u.out_or_in && u.out==v.out);
813        else
814          return (!u.out_or_in && u.in==v.in);
815      }
816      friend bool operator!=(const Edge& u, const Edge& v) {
817        if (v.out_or_in)
818          return (!u.out_or_in || u.out!=v.out);
819        else
820          return (u.out_or_in || u.in!=v.in);
821      }
822    };
823
824
825    class OutEdgeIt : public Edge {
826      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
827    public:
828      OutEdgeIt() { }
829      //FIXME
830      OutEdgeIt(const Edge& e) : Edge(e) { }
831      OutEdgeIt(const Invalid& i) : Edge(i) { }
832    private:
833      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
834        resG.gw.first(out, v);
835        while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
836        if (!resG.gw.valid(out)) {
837          out_or_in=0;
838          resG.gw.first(in, v);
839          while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
840        }
841      }
842//     public:
843//       OutEdgeIt& operator++() {
844//      if (out_or_in) {
845//        Node v=/*resG->*/G->aNode(out);
846//        ++out;
847//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
848//        if (!out.valid()) {
849//          out_or_in=0;
850//          G->first(in, v);
851//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
852//        }
853//      } else {
854//        ++in;
855//        while( in.valid() && !(Edge::free()>0) ) { ++in; }
856//      }
857//      return *this;
858//       }
859    };
860
861    class EdgeIt : public Edge {
862      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
863      typename Graph::NodeIt v;
864    public:
865      EdgeIt() { }
866      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
867      EdgeIt(const Invalid& i) : Edge(i) { }
868      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
869        resG.gw.first(v);
870        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
871        while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
872        while (resG.gw.valid(v) && !resG.gw.valid(out)) {
873          resG.gw.next(v);
874          if (resG.gw.valid(v)) resG.gw.first(out, v);
875          while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
876        }
877        if (!resG.gw.valid(out)) {
878          out_or_in=0;
879          resG.gw.first(v);
880          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
881          while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
882          while (resG.gw.valid(v) && !resG.gw.valid(in)) {
883            resG.gw.next(v);
884            if (resG.gw.valid(v)) resG.gw.first(in, v);
885            while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
886          }
887        }
888      }
889//       EdgeIt& operator++() {
890//      if (out_or_in) {
891//        ++out;
892//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
893//        while (v.valid() && !out.valid()) {
894//          ++v;
895//          if (v.valid()) G->first(out, v);
896//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
897//        }
898//        if (!out.valid()) {
899//          out_or_in=0;
900//          G->first(v);
901//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
902//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
903//          while (v.valid() && !in.valid()) {
904//            ++v;
905//            if (v.valid()) G->first(in, v);
906//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
907//          } 
908//        }
909//      } else {
910//        ++in;
911//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
912//        while (v.valid() && !in.valid()) {
913//          ++v;
914//          if (v.valid()) G->first(in, v);
915//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
916//        }
917//      }
918//      return *this;
919//       }
920    };
921
922    NodeIt& first(NodeIt& v) const { return gw.first(v); }
923    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
924      e=OutEdgeIt(*this, v);
925      return e;
926    }
927    EdgeIt& first(EdgeIt& e) const {
928      e=EdgeIt(*this);
929      return e;
930    }
931   
932    NodeIt& next(NodeIt& n) const { return gw.next(n); }
933
934    OutEdgeIt& next(OutEdgeIt& e) const {
935      if (e.out_or_in) {
936        Node v=gw.aNode(e.out);
937        gw.next(e.out);
938        while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
939        if (!gw.valid(e.out)) {
940          e.out_or_in=0;
941          gw.first(e.in, v);
942          while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
943        }
944      } else {
945        gw.next(e.in);
946        while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
947      }
948      return e;
949    }
950
951    EdgeIt& next(EdgeIt& e) const {
952      if (e.out_or_in) {
953        gw.next(e.out);
954        while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
955          while (gw.valid(e.v) && !gw.valid(e.out)) {
956            gw.next(e.v);
957            if (gw.valid(e.v)) gw.first(e.out, e.v);
958            while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
959          }
960          if (!gw.valid(e.out)) {
961            e.out_or_in=0;
962            gw.first(e.v);
963            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
964            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
965            while (gw.valid(e.v) && !gw.valid(e.in)) {
966              gw.next(e.v);
967              if (gw.valid(e.v)) gw.first(e.in, e.v);
968              while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
969            } 
970          }
971        } else {
972          gw.next(e.in);
973          while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
974          while (gw.valid(e.v) && !gw.valid(e.in)) {
975            gw.next(e.v);
976            if (gw.valid(e.v)) gw.first(e.in, e.v);
977            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
978          }
979        }
980        return e;
981      }
982   
983
984    template< typename It >
985    It first() const {
986      It e;
987      first(e);
988      return e;
989    }
990
991    template< typename It >
992    It first(Node v) const {
993      It e;
994      first(e, v);
995      return e;
996    }
997
998    Node tail(Edge e) const {
999      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1000    Node head(Edge e) const {
1001      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1002
1003    Node aNode(OutEdgeIt e) const {
1004      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1005    Node bNode(OutEdgeIt e) const {
1006      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1007
1008    int id(Node v) const { return gw.id(v); }
1009
1010    bool valid(Node n) const { return gw.valid(n); }
1011    bool valid(Edge e) const {
1012      return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
1013
1014    void augment(const Edge& e, Number a) const {
1015      if (e.out_or_in) 
1016        flow->set(e.out, flow->get(e.out)+a);
1017      else 
1018        flow->set(e.in, flow->get(e.in)-a);
1019    }
1020
1021    Number free(const Edge& e) const {
1022      if (e.out_or_in)
1023        return (capacity->get(e.out)-flow->get(e.out));
1024      else
1025        return (flow->get(e.in));
1026    }
1027
1028    Number free(OldOutEdgeIt out) const {
1029      return (capacity->get(out)-flow->get(out));
1030    }
1031   
1032    Number free(OldInEdgeIt in) const {
1033      return (flow->get(in));
1034    }
1035
1036    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1037    public:
1038      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1039        : GraphWrapper::NodeMap<T>(_G.gw) { }
1040      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1041              T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1042    };
1043
1044//     template <typename T>
1045//     class NodeMap {
1046//       typename Graph::NodeMap<T> node_map;
1047//     public:
1048//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1049//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1050//       void set(Node nit, T a) { node_map.set(nit, a); }
1051//       T get(Node nit) const { return node_map.get(nit); }
1052//     };
1053
1054    template <typename T>
1055    class EdgeMap {
1056      typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1057    public:
1058      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1059      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1060      void set(Edge e, T a) {
1061        if (e.out_or_in)
1062          forward_map.set(e.out, a);
1063        else
1064          backward_map.set(e.in, a);
1065      }
1066      T get(Edge e) {
1067        if (e.out_or_in)
1068          return forward_map.get(e.out);
1069        else
1070          return backward_map.get(e.in);
1071      }
1072    };
1073  };
1074
1075  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1076  class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1077  protected:
1078    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1079    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1080  public:
1081    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1082                           const CapacityMap& _capacity) :
1083      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1084      first_out_edges(*this) /*, dist(*this)*/ {
1085      for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1086        OutEdgeIt e;
1087        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1088        first_out_edges.set(n, e);
1089      }
1090    }
1091
1092    //void setGraph(Graph& _graph) { graph = &_graph; }
1093    //Graph& getGraph() const { return (*graph); }
1094 
1095    //TrivGraphWrapper() : graph(0) { }
1096    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1097
1098    //typedef Graph BaseGraph;
1099
1100    //typedef typename Graph::Node Node;
1101    //typedef typename Graph::NodeIt NodeIt;
1102
1103    //typedef typename Graph::Edge Edge;
1104    //typedef typename Graph::OutEdgeIt OutEdgeIt;
1105    //typedef typename Graph::InEdgeIt InEdgeIt;
1106    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1107    //typedef typename Graph::EdgeIt EdgeIt;
1108
1109    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1110    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1111
1112    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1113    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1114    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1115    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1116    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1117
1118    NodeIt& first(NodeIt& n) const {
1119      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1120    }
1121
1122    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1123      e=first_out_edges.get(n);
1124      return e;
1125    }
1126   
1127    //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1128    //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1129    //  return first(i, p); }
1130   
1131    //template<typename I> I getNext(const I& i) const {
1132    //  return gw.getNext(i); }
1133    //template<typename I> I& next(I &i) const { return gw.next(i); }   
1134
1135    template< typename It > It first() const {
1136      It e; first(e); return e; }
1137
1138    template< typename It > It first(const Node& v) const {
1139      It e; first(e, v); return e; }
1140
1141    //Node head(const Edge& e) const { return gw.head(e); }
1142    //Node tail(const Edge& e) const { return gw.tail(e); }
1143
1144    //template<typename I> bool valid(const I& i) const
1145    //  { return gw.valid(i); }
1146 
1147    //int nodeNum() const { return gw.nodeNum(); }
1148    //int edgeNum() const { return gw.edgeNum(); }
1149 
1150    //template<typename I> Node aNode(const I& e) const {
1151    //  return gw.aNode(e); }
1152    //template<typename I> Node bNode(const I& e) const {
1153    //  return gw.bNode(e); }
1154 
1155    //Node addNode() const { return gw.addNode(); }
1156    //Edge addEdge(const Node& tail, const Node& head) const {
1157    //  return gw.addEdge(tail, head); }
1158 
1159    //void erase(const OutEdgeIt& e) {
1160    //  first_out_edge(this->tail(e))=e;
1161    //}
1162    void erase(const Edge& e) {
1163      OutEdgeIt f(e);
1164      next(f);
1165      first_out_edges.set(this->tail(e), f);
1166    }
1167    //template<typename I> void erase(const I& i) const { gw.erase(i); }
1168 
1169    //void clear() const { gw.clear(); }
1170   
1171    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1172    public:
1173      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1174        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1175      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1176        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1177    };
1178
1179    template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1180    public:
1181      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1182        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1183      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1184        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1185    };
1186  };
1187
1188  template<typename GraphWrapper>
1189  class FilterGraphWrapper {
1190  };
1191
1192  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1193  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1194
1195    //Graph* graph;
1196 
1197  public:
1198    //typedef Graph BaseGraph;
1199
1200    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1201    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1202
1203    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1204    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1205    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1206    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1207    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1208
1209    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1210   
1211  public:
1212    FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1213                           const CapacityMap& _capacity) :
1214      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1215    }
1216
1217    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1218      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1219      while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1220        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1221      return e;
1222    }
1223
1224    NodeIt& next(NodeIt& e) const {
1225      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1226    }
1227
1228    OutEdgeIt& next(OutEdgeIt& e) const {
1229      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1230      while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1231        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1232      return e;
1233    }
1234
1235    NodeIt& first(NodeIt& n) const {
1236      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1237    }
1238
1239    void erase(const Edge& e) {
1240      OutEdgeIt f(e);
1241      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1242      while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1243        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1244      first_out_edges.set(this->tail(e), f);
1245    }
1246
1247    //TrivGraphWrapper() : graph(0) { }
1248    //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1249
1250    //void setGraph(Graph& _graph) { graph = &_graph; }
1251    //Graph& getGraph() const { return (*graph); }
1252   
1253    //template<typename I> I& first(I& i) const { return gw.first(i); }
1254    //template<typename I, typename P> I& first(I& i, const P& p) const {
1255    //  return gw.first(i, p); }
1256   
1257    //template<typename I> I getNext(const I& i) const {
1258    //  return gw.getNext(i); }
1259    //template<typename I> I& next(I &i) const { return gw.next(i); }   
1260
1261    template< typename It > It first() const {
1262      It e; first(e); return e; }
1263
1264    template< typename It > It first(const Node& v) const {
1265      It e; first(e, v); return e; }
1266
1267    //Node head(const Edge& e) const { return gw.head(e); }
1268    //Node tail(const Edge& e) const { return gw.tail(e); }
1269
1270    //template<typename I> bool valid(const I& i) const
1271    //  { return gw.valid(i); }
1272 
1273    //template<typename I> void setInvalid(const I &i);
1274    //{ return gw.setInvalid(i); }
1275
1276    //int nodeNum() const { return gw.nodeNum(); }
1277    //int edgeNum() const { return gw.edgeNum(); }
1278 
1279    //template<typename I> Node aNode(const I& e) const {
1280    //  return gw.aNode(e); }
1281    //template<typename I> Node bNode(const I& e) const {
1282    //  return gw.bNode(e); }
1283 
1284    //Node addNode() const { return gw.addNode(); }
1285    //Edge addEdge(const Node& tail, const Node& head) const {
1286    //  return gw.addEdge(tail, head); }
1287 
1288    //template<typename I> void erase(const I& i) const { gw.erase(i); }
1289 
1290    //void clear() const { gw.clear(); }
1291   
1292    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1293    public:
1294      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1295        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1296      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1297        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1298    };
1299
1300    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1301    public:
1302      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1303        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1304      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1305        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1306    };
1307
1308  public:
1309    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1310
1311  };
1312
1313
1314
1315// // FIXME: comparison should be made better!!!
1316//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1317//   class ResGraphWrapper
1318//   {
1319//     Graph* graph;
1320 
1321//   public:
1322//     typedef Graph BaseGraph;
1323
1324//     typedef typename Graph::Node Node;
1325//     typedef typename Graph::Edge Edge;
1326 
1327//     typedef typename Graph::NodeIt NodeIt;
1328   
1329//     class OutEdgeIt {
1330//     public:
1331//       //Graph::Node n;
1332//       bool out_or_in;
1333//       typename Graph::OutEdgeIt o;
1334//       typename Graph::InEdgeIt i;   
1335//     };
1336//     class InEdgeIt {
1337//     public:
1338//       //Graph::Node n;
1339//       bool out_or_in;
1340//       typename Graph::OutEdgeIt o;
1341//       typename Graph::InEdgeIt i;   
1342//     };
1343//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1344//     typedef typename Graph::EdgeIt EdgeIt;
1345
1346//     int nodeNum() const { return gw.nodeNum(); }
1347//     int edgeNum() const { return gw.edgeNum(); }
1348
1349//     Node& first(Node& n) const { return gw.first(n); }
1350
1351//     // Edge and SymEdge  is missing!!!!
1352//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1353
1354//     //FIXME
1355//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1356//       {
1357//      e.n=n;
1358//      gw.first(e.o,n);
1359//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1360//        gw.goNext(e.o);
1361//      if(!gw.valid(e.o)) {
1362//        gw.first(e.i,n);
1363//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1364//          gw.goNext(e.i);
1365//      }
1366//      return e;
1367//       }
1368// /*
1369//   OutEdgeIt &goNext(OutEdgeIt &e)
1370//   {
1371//   if(gw.valid(e.o)) {
1372//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1373//   gw.goNext(e.o);
1374//   if(gw.valid(e.o)) return e;
1375//   else gw.first(e.i,e.n);
1376//   }
1377//   else {
1378//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1379//   gw.goNext(e.i);
1380//   return e;
1381//   }
1382//   }
1383//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1384// */
1385//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1386
1387//     //FIXME
1388//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1389//       {
1390//      e.n=n;
1391//      gw.first(e.i,n);
1392//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1393//        gw.goNext(e.i);
1394//      if(!gw.valid(e.i)) {
1395//        gw.first(e.o,n);
1396//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1397//          gw.goNext(e.o);
1398//      }
1399//      return e;
1400//       }
1401// /*
1402//   InEdgeIt &goNext(InEdgeIt &e)
1403//   {
1404//   if(gw.valid(e.i)) {
1405//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1406//   gw.goNext(e.i);
1407//   if(gw.valid(e.i)) return e;
1408//   else gw.first(e.o,e.n);
1409//   }
1410//   else {
1411//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1412//   gw.goNext(e.o);
1413//   return e;
1414//   }
1415//   }
1416//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1417// */
1418//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1419
1420//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1421//     //template<typename I> I next(const I i); { return gw.goNext(i); }
1422
1423//     template< typename It > It first() const {
1424//       It e; first(e); return e; }
1425
1426//     template< typename It > It first(Node v) const {
1427//       It e; first(e, v); return e; }
1428
1429//     Node head(const Edge& e) const { return gw.head(e); }
1430//     Node tail(const Edge& e) const { return gw.tail(e); }
1431 
1432//     template<typename I> Node aNode(const I& e) const {
1433//       return gw.aNode(e); }
1434//     template<typename I> Node bNode(const I& e) const {
1435//       return gw.bNode(e); }
1436 
1437//     //template<typename I> bool valid(const I i);
1438//     //{ return gw.valid(i); }
1439 
1440//     //template<typename I> void setInvalid(const I &i);
1441//     //{ return gw.setInvalid(i); }
1442 
1443//     Node addNode() { return gw.addNode(); }
1444//     Edge addEdge(const Node& tail, const Node& head) {
1445//       return gw.addEdge(tail, head); }
1446 
1447//     template<typename I> void erase(const I& i) { gw.erase(i); }
1448 
1449//     void clear() { gw.clear(); }
1450 
1451//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1452//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1453 
1454//     void setGraph(Graph& _graph) { graph = &_graph; }
1455//     Graph& getGraph() { return (*graph); }
1456
1457//     //ResGraphWrapper() : graph(0) { }
1458//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1459//   };
1460
1461} //namespace hugo
1462
1463#endif //HUGO_GRAPH_WRAPPER_H
1464
Note: See TracBrowser for help on using the repository browser.