COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 263:f24f276e0b6b

Last change on this file since 263:f24f276e0b6b was 263:f24f276e0b6b, checked in by marci, 17 years ago

ResGraphWrapper? ...

File size: 51.0 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  //Subgraph on the same node-set and partial edge-set
346  template<typename GraphWrapper, typename EdgeFilterMap>
347  class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
348  protected:
349    EdgeFilterMap* filter_map;
350  public:
351    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
352    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
353    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
354    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
355    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
356    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
357
358    SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
359      GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { } 
360
361    template<typename I> I& first(I& i) const {
362      gw.first(i);
363      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
364      return i;
365    }
366    template<typename I, typename P> I& first(I& i, const P& p) const {
367      gw.first(i, p);
368      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
369      return i;
370    }
371   
372    //template<typename I> I getNext(const I& i) const {
373    //  return gw.getNext(i);
374    //}
375    template<typename I> I& next(I &i) const {
376      gw.next(i);
377      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
378      return i;
379    }
380   
381    template< typename It > It first() const {
382      It e; this->first(e); return e; }
383   
384    template< typename It > It first(const Node& v) const {
385      It e; this->first(e, v); return e; }
386  };
387
388//   template<typename GraphWrapper>
389//   class UndirGraphWrapper {
390//   protected:
391//     //Graph* graph;
392//     GraphWrapper gw;
393
394//   public:
395//     typedef GraphWrapper BaseGraph;
396
397//     typedef typename GraphWrapper::Node Node;
398//     typedef typename GraphWrapper::NodeIt NodeIt;
399
400//     //typedef typename Graph::Edge Edge;
401//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
402//     //typedef typename Graph::InEdgeIt InEdgeIt;
403//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
404//     //typedef typename Graph::EdgeIt EdgeIt;
405
406//     //private:
407//     typedef typename GraphWrapper::Edge GraphEdge;
408//     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
409//     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
410//     //public:
411
412//     //UndirGraphWrapper() : graph(0) { }
413//     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
414
415//     //void setGraph(Graph& _graph) { graph = &_graph; }
416//     //Graph& getGraph() const { return (*graph); }
417 
418//     class Edge {
419//       friend class UndirGraphWrapper<GraphWrapper>;
420//       bool out_or_in; //true iff out
421//       GraphOutEdgeIt out;
422//       GraphInEdgeIt in;
423//     public:
424//       Edge() : out_or_in(), out(), in() { }
425//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
426//       operator GraphEdge() const {
427//      if (out_or_in) return(out); else return(in);
428//       }
429//       friend bool operator==(const Edge& u, const Edge& v) {
430//      if (v.out_or_in)
431//        return (u.out_or_in && u.out==v.out);
432//      else
433//        return (!u.out_or_in && u.in==v.in);
434//       }
435//       friend bool operator!=(const Edge& u, const Edge& v) {
436//      if (v.out_or_in)
437//        return (!u.out_or_in || u.out!=v.out);
438//      else
439//        return (u.out_or_in || u.in!=v.in);
440//       }
441//     };
442
443//     class OutEdgeIt : public Edge {
444//       friend class UndirGraphWrapper<GraphWrapper>;
445//     public:
446//       OutEdgeIt() : Edge() { }
447//       OutEdgeIt(const Invalid& i) : Edge(i) { }
448//       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
449//      : Edge() {
450//      out_or_in=true;
451//      _G.gw.first(out, n);
452//      if (!(_G.gw.valid(out))) {
453//        out_or_in=false;
454//        _G.gw.first(in, n);
455//      }
456//       }
457//     };
458
459//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
460//       e.out_or_in=true;
461//       gw.first(e.out, n);
462//       if (!(gw.valid(e.out))) {
463//      e.out_or_in=false;
464//      gw.first(e.in, n);
465//       }
466//       return e;
467//     }
468
469//     OutEdgeIt& next(OutEdgeIt& e) const {
470//       if (e.out_or_in) {
471//      Node n=gw.tail(e.out);
472//      gw.next(e.out);
473//      if (!gw.valid(e.out)) {
474//        e.out_or_in=false;
475//        gw.first(e.in, n);
476//      }
477//       } else {
478//      gw.next(e.in);
479//       }
480//       return e;
481//     }
482
483//     Node aNode(const OutEdgeIt& e) const {
484//       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
485//     Node bNode(const OutEdgeIt& e) const {
486//       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
487
488//     typedef OutEdgeIt InEdgeIt;
489
490//     template<typename I> I& first(I& i) const { return gw.first(i); }
491// //     template<typename I, typename P> I& first(I& i, const P& p) const {
492// //       return graph->first(i, p); }
493   
494//     template<typename I> I getNext(const I& i) const {
495//       return gw.getNext(i); }
496//     template<typename I> I& next(I &i) const { return gw.next(i); }   
497
498//     template< typename It > It first() const {
499//       It e; first(e); return e; }
500
501//     template< typename It > It first(const Node& v) const {
502//       It e; first(e, v); return e; }
503
504//     Node head(const Edge& e) const { return gw.head(e); }
505//     Node tail(const Edge& e) const { return gw.tail(e); }
506
507//     template<typename I> bool valid(const I& i) const
508//       { return gw.valid(i); }
509 
510//     //template<typename I> void setInvalid(const I &i);
511//     //{ return graph->setInvalid(i); }
512
513//     int nodeNum() const { return gw.nodeNum(); }
514//     int edgeNum() const { return gw.edgeNum(); }
515 
516// //     template<typename I> Node aNode(const I& e) const {
517// //       return graph->aNode(e); }
518// //     template<typename I> Node bNode(const I& e) const {
519// //       return graph->bNode(e); }
520 
521//     Node addNode() const { return gw.addNode(); }
522// // FIXME: ez igy nem jo, mert nem
523// //    Edge addEdge(const Node& tail, const Node& head) const {
524// //      return graph->addEdge(tail, head); }
525 
526//     template<typename I> void erase(const I& i) const { gw.erase(i); }
527 
528//     void clear() const { gw.clear(); }
529   
530//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
531//     public:
532//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
533//      GraphWrapper::NodeMap<T>(_G.gw) { }
534//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
535//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
536//     };
537
538//     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
539//     public:
540//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
541//      GraphWrapper::EdgeMap<T>(_G.gw) { }
542//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
543//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
544//     };
545//   };
546
547
548  template<typename GraphWrapper>
549  class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
550  protected:
551//    GraphWrapper gw;
552
553  public:
554    //typedef GraphWrapper BaseGraph;
555
556    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
557    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
558
559    //private:
560    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge GraphEdge;
561    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt GraphOutEdgeIt;
562    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt GraphInEdgeIt;
563    //public:
564
565    //UndirGraphWrapper() : graph(0) { }
566    UndirGraphWrapper(GraphWrapper _gw) :
567      GraphWrapperSkeleton<GraphWrapper>(_gw) { } 
568
569    //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
570
571    //void setGraph(Graph& _graph) { graph = &_graph; }
572    //Graph& getGraph() const { return (*graph); }
573 
574    class Edge {
575      friend class UndirGraphWrapper<GraphWrapper>;
576      bool out_or_in; //true iff out
577      GraphOutEdgeIt out;
578      GraphInEdgeIt in;
579    public:
580      Edge() : out_or_in(), out(), in() { }
581      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
582      operator GraphEdge() const {
583        if (out_or_in) return(out); else return(in);
584      }
585//FIXME
586//2 edges are equal if they "refer" to the same physical edge
587//is it good?
588      friend bool operator==(const Edge& u, const Edge& v) {
589        if (v.out_or_in)
590          if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
591        //return (u.out_or_in && u.out==v.out);
592        else
593          if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
594        //return (!u.out_or_in && u.in==v.in);
595      }
596      friend bool operator!=(const Edge& u, const Edge& v) {
597        if (v.out_or_in)
598          if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
599        //return (!u.out_or_in || u.out!=v.out);
600        else
601          if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
602        //return (u.out_or_in || u.in!=v.in);
603      }
604    };
605
606    class OutEdgeIt : public Edge {
607      friend class UndirGraphWrapper<GraphWrapper>;
608    public:
609      OutEdgeIt() : Edge() { }
610      OutEdgeIt(const Invalid& i) : Edge(i) { }
611      OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
612        : Edge() {
613        out_or_in=true; _G.gw.first(out, n);
614        if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
615      }
616    };
617
618    typedef OutEdgeIt InEdgeIt;
619
620    class EdgeIt : public Edge {
621      friend class UndirGraphWrapper<GraphWrapper>;
622    protected:
623      NodeIt v;
624    public:
625      EdgeIt() : Edge() { }
626      EdgeIt(const Invalid& i) : Edge(i) { }
627      EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
628        : Edge() {
629        out_or_in=true;
630        //Node v;
631        _G.first(v);
632        if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
633        while (_G.valid(v) && !_G.gw.valid(out)) {
634          _G.gw.next(v);
635          if (_G.valid(v)) _G.gw.first(out);
636        }
637      }
638    };
639
640    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
641      e.out_or_in=true; gw.first(e.out, n);
642      if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
643      return e;
644    }
645
646    EdgeIt& first(EdgeIt& e) const {
647      e.out_or_in=true;
648      //NodeIt v;
649      first(e.v);
650      if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
651      while (valid(e.v) && !gw.valid(e.out)) {
652        gw.next(e.v);
653        if (valid(e.v)) gw.first(e.out, e.v);
654      }
655      return e;
656    }
657
658    template<typename I> I& first(I& i) const { return gw.first(i); }
659    template<typename I, typename P> I& first(I& i, const P& p) const {
660      return graph->first(i, p); }
661
662    OutEdgeIt& next(OutEdgeIt& e) const {
663      if (e.out_or_in) {
664        Node n=gw.tail(e.out);
665        gw.next(e.out);
666        if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
667      } else {
668        gw.next(e.in);
669      }
670      return e;
671    }
672
673    EdgeIt& next(EdgeIt& e) const {
674      //NodeIt v=tail(e);
675      gw.next(e.out);
676      while (valid(e.v) && !gw.valid(e.out)) {
677        next(e.v);
678        if (valid(e.v)) gw.first(e.out, e.v);
679      }
680      return e;
681    }
682
683    template<typename I> I& next(I &i) const { return gw.next(i); }   
684    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
685
686    template< typename It > It first() const {
687      It e; first(e); return e; }
688
689    template< typename It > It first(const Node& v) const {
690      It e; first(e, v); return e; }
691
692//    Node head(const Edge& e) const { return gw.head(e); }
693//    Node tail(const Edge& e) const { return gw.tail(e); }
694
695//    template<typename I> bool valid(const I& i) const
696//      { return gw.valid(i); }
697 
698//    int nodeNum() const { return gw.nodeNum(); }
699//    int edgeNum() const { return gw.edgeNum(); }
700 
701//     template<typename I> Node aNode(const I& e) const {
702//       return graph->aNode(e); }
703//     template<typename I> Node bNode(const I& e) const {
704//       return graph->bNode(e); }
705
706    Node aNode(const OutEdgeIt& e) const {
707      if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
708    Node bNode(const OutEdgeIt& e) const {
709      if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
710 
711//    Node addNode() const { return gw.addNode(); }
712
713// FIXME: ez igy nem jo, mert nem
714//    Edge addEdge(const Node& tail, const Node& head) const {
715//      return graph->addEdge(tail, head); }
716 
717//    template<typename I> void erase(const I& i) const { gw.erase(i); }
718 
719//    void clear() const { gw.clear(); }
720   
721//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
722//     public:
723//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
724//      GraphWrapper::NodeMap<T>(_G.gw) { }
725//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
726//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
727//     };
728
729//     template<typename T> class EdgeMap :
730//       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
731//     public:
732//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
733//      GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
734//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
735//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
736//     };
737   };
738
739
740
741
742
743//   template<typename Graph>
744//   class SymGraphWrapper
745//   {
746//     Graph* graph;
747 
748//   public:
749//     typedef Graph BaseGraph;
750
751//     typedef typename Graph::Node Node;
752//     typedef typename Graph::Edge Edge;
753 
754//     typedef typename Graph::NodeIt NodeIt;
755   
756//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
757//     //iranyitatlant, ami van
758//     //mert csak 1 dolgot lehet be typedef-elni
759//     typedef typename Graph::OutEdgeIt SymEdgeIt;
760//     //typedef typename Graph::InEdgeIt SymEdgeIt;
761//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
762//     typedef typename Graph::EdgeIt EdgeIt;
763
764//     int nodeNum() const { return graph->nodeNum(); }
765//     int edgeNum() const { return graph->edgeNum(); }
766   
767//     template<typename I> I& first(I& i) const { return graph->first(i); }
768//     template<typename I, typename P> I& first(I& i, const P& p) const {
769//       return graph->first(i, p); }
770//     //template<typename I> I next(const I i); { return graph->goNext(i); }
771//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
772
773//     template< typename It > It first() const {
774//       It e; first(e); return e; }
775
776//     template< typename It > It first(Node v) const {
777//       It e; first(e, v); return e; }
778
779//     Node head(const Edge& e) const { return graph->head(e); }
780//     Node tail(const Edge& e) const { return graph->tail(e); }
781 
782//     template<typename I> Node aNode(const I& e) const {
783//       return graph->aNode(e); }
784//     template<typename I> Node bNode(const I& e) const {
785//       return graph->bNode(e); }
786 
787//     //template<typename I> bool valid(const I i);
788//     //{ return graph->valid(i); }
789 
790//     //template<typename I> void setInvalid(const I &i);
791//     //{ return graph->setInvalid(i); }
792 
793//     Node addNode() { return graph->addNode(); }
794//     Edge addEdge(const Node& tail, const Node& head) {
795//       return graph->addEdge(tail, head); }
796 
797//     template<typename I> void erase(const I& i) { graph->erase(i); }
798 
799//     void clear() { graph->clear(); }
800 
801//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
802//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
803 
804//     void setGraph(Graph& _graph) { graph = &_graph; }
805//     Graph& getGraph() { return (*graph); }
806
807//     //SymGraphWrapper() : graph(0) { }
808//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
809//   };
810
811
812  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
813  class ResGraphWrapper {
814  public:
815    //typedef Graph BaseGraph;
816    typedef typename Graph::Node Node;
817    typedef typename Graph::NodeIt NodeIt;
818  private:
819    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
820    typedef typename Graph::InEdgeIt OldInEdgeIt;
821  protected:
822    //const Graph* graph;
823    typedef TrivGraphWrapper<const Graph> GraphWrapper;
824    GraphWrapper gw;
825    FlowMap* flow;
826    const CapacityMap* capacity;
827  public:
828
829    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
830             const CapacityMap& _capacity) :
831      gw(_G), flow(&_flow), capacity(&_capacity) { }
832
833    //void setGraph(const Graph& _graph) { graph = &_graph; }
834    //const Graph& getGraph() const { return (*graph); }
835
836    class Edge;
837    class OutEdgeIt;
838    friend class Edge;
839    friend class OutEdgeIt;
840
841    class Edge {
842      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
843    protected:
844      bool out_or_in; //true, iff out
845      OldOutEdgeIt out;
846      OldInEdgeIt in;
847    public:
848      Edge() : out_or_in(true) { }
849      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
850//       bool valid() const {
851//      return out_or_in && out.valid() || in.valid(); }
852      friend bool operator==(const Edge& u, const Edge& v) {
853        if (v.out_or_in)
854          return (u.out_or_in && u.out==v.out);
855        else
856          return (!u.out_or_in && u.in==v.in);
857      }
858      friend bool operator!=(const Edge& u, const Edge& v) {
859        if (v.out_or_in)
860          return (!u.out_or_in || u.out!=v.out);
861        else
862          return (u.out_or_in || u.in!=v.in);
863      }
864    };
865
866
867    class OutEdgeIt : public Edge {
868      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
869    public:
870      OutEdgeIt() { }
871      //FIXME
872      OutEdgeIt(const Edge& e) : Edge(e) { }
873      OutEdgeIt(const Invalid& i) : Edge(i) { }
874    private:
875      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
876        resG.gw.first(out, v);
877        while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
878        if (!resG.gw.valid(out)) {
879          out_or_in=0;
880          resG.gw.first(in, v);
881          while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
882        }
883      }
884//     public:
885//       OutEdgeIt& operator++() {
886//      if (out_or_in) {
887//        Node v=/*resG->*/G->aNode(out);
888//        ++out;
889//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
890//        if (!out.valid()) {
891//          out_or_in=0;
892//          G->first(in, v);
893//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
894//        }
895//      } else {
896//        ++in;
897//        while( in.valid() && !(Edge::free()>0) ) { ++in; }
898//      }
899//      return *this;
900//       }
901    };
902
903    //FIXME This is just for having InEdgeIt
904    typedef void InEdgeIt;
905
906    class EdgeIt : public Edge {
907      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
908      typename Graph::NodeIt v;
909    public:
910      EdgeIt() { }
911      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
912      EdgeIt(const Invalid& i) : Edge(i) { }
913      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
914        resG.gw.first(v);
915        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
916        while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
917        while (resG.gw.valid(v) && !resG.gw.valid(out)) {
918          resG.gw.next(v);
919          if (resG.gw.valid(v)) resG.gw.first(out, v);
920          while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
921        }
922        if (!resG.gw.valid(out)) {
923          out_or_in=0;
924          resG.gw.first(v);
925          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
926          while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
927          while (resG.gw.valid(v) && !resG.gw.valid(in)) {
928            resG.gw.next(v);
929            if (resG.gw.valid(v)) resG.gw.first(in, v);
930            while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
931          }
932        }
933      }
934//       EdgeIt& operator++() {
935//      if (out_or_in) {
936//        ++out;
937//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
938//        while (v.valid() && !out.valid()) {
939//          ++v;
940//          if (v.valid()) G->first(out, v);
941//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
942//        }
943//        if (!out.valid()) {
944//          out_or_in=0;
945//          G->first(v);
946//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
947//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
948//          while (v.valid() && !in.valid()) {
949//            ++v;
950//            if (v.valid()) G->first(in, v);
951//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
952//          } 
953//        }
954//      } else {
955//        ++in;
956//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
957//        while (v.valid() && !in.valid()) {
958//          ++v;
959//          if (v.valid()) G->first(in, v);
960//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
961//        }
962//      }
963//      return *this;
964//       }
965    };
966
967    NodeIt& first(NodeIt& v) const { return gw.first(v); }
968    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
969      e=OutEdgeIt(*this, v);
970      return e;
971    }
972    EdgeIt& first(EdgeIt& e) const {
973      e=EdgeIt(*this);
974      return e;
975    }
976   
977    NodeIt& next(NodeIt& n) const { return gw.next(n); }
978
979    OutEdgeIt& next(OutEdgeIt& e) const {
980      if (e.out_or_in) {
981        Node v=gw.aNode(e.out);
982        gw.next(e.out);
983        while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
984        if (!gw.valid(e.out)) {
985          e.out_or_in=0;
986          gw.first(e.in, v);
987          while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
988        }
989      } else {
990        gw.next(e.in);
991        while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
992      }
993      return e;
994    }
995
996    EdgeIt& next(EdgeIt& e) const {
997      if (e.out_or_in) {
998        gw.next(e.out);
999        while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1000          while (gw.valid(e.v) && !gw.valid(e.out)) {
1001            gw.next(e.v);
1002            if (gw.valid(e.v)) gw.first(e.out, e.v);
1003            while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1004          }
1005          if (!gw.valid(e.out)) {
1006            e.out_or_in=0;
1007            gw.first(e.v);
1008            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
1009            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1010            while (gw.valid(e.v) && !gw.valid(e.in)) {
1011              gw.next(e.v);
1012              if (gw.valid(e.v)) gw.first(e.in, e.v);
1013              while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1014            } 
1015          }
1016        } else {
1017          gw.next(e.in);
1018          while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1019          while (gw.valid(e.v) && !gw.valid(e.in)) {
1020            gw.next(e.v);
1021            if (gw.valid(e.v)) gw.first(e.in, e.v);
1022            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1023          }
1024        }
1025        return e;
1026      }
1027   
1028
1029    template< typename It >
1030    It first() const {
1031      It e;
1032      first(e);
1033      return e;
1034    }
1035
1036    template< typename It >
1037    It first(Node v) const {
1038      It e;
1039      first(e, v);
1040      return e;
1041    }
1042
1043    Node tail(Edge e) const {
1044      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1045    Node head(Edge e) const {
1046      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1047
1048    Node aNode(OutEdgeIt e) const {
1049      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1050    Node bNode(OutEdgeIt e) const {
1051      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1052
1053    int nodeNum() const { return gw.nodeNum(); }
1054    //FIXME
1055    //int edgeNum() const { return gw.edgeNum(); }
1056
1057
1058    int id(Node v) const { return gw.id(v); }
1059
1060    bool valid(Node n) const { return gw.valid(n); }
1061    bool valid(Edge e) const {
1062      return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
1063
1064    void augment(const Edge& e, Number a) const {
1065      if (e.out_or_in) 
1066        flow->set(e.out, flow->get(e.out)+a);
1067      else 
1068        flow->set(e.in, flow->get(e.in)-a);
1069    }
1070
1071    Number free(const Edge& e) const {
1072      if (e.out_or_in)
1073        return (capacity->get(e.out)-flow->get(e.out));
1074      else
1075        return (flow->get(e.in));
1076    }
1077
1078    Number free(OldOutEdgeIt out) const {
1079      return (capacity->get(out)-flow->get(out));
1080    }
1081   
1082    Number free(OldInEdgeIt in) const {
1083      return (flow->get(in));
1084    }
1085
1086    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1087    public:
1088      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1089        : GraphWrapper::NodeMap<T>(_G.gw) { }
1090      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1091              T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1092    };
1093
1094//     template <typename T>
1095//     class NodeMap {
1096//       typename Graph::NodeMap<T> node_map;
1097//     public:
1098//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1099//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1100//       void set(Node nit, T a) { node_map.set(nit, a); }
1101//       T get(Node nit) const { return node_map.get(nit); }
1102//     };
1103
1104    template <typename T>
1105    class EdgeMap {
1106      typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1107    public:
1108      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1109      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1110      void set(Edge e, T a) {
1111        if (e.out_or_in)
1112          forward_map.set(e.out, a);
1113        else
1114          backward_map.set(e.in, a);
1115      }
1116      T get(Edge e) {
1117        if (e.out_or_in)
1118          return forward_map.get(e.out);
1119        else
1120          return backward_map.get(e.in);
1121      }
1122    };
1123  };
1124
1125  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1126  class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1127  protected:
1128    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1129    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1130  public:
1131    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1132                           const CapacityMap& _capacity) :
1133      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1134      first_out_edges(*this) /*, dist(*this)*/ {
1135      for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1136        OutEdgeIt e;
1137        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1138        first_out_edges.set(n, e);
1139      }
1140    }
1141
1142    //void setGraph(Graph& _graph) { graph = &_graph; }
1143    //Graph& getGraph() const { return (*graph); }
1144 
1145    //TrivGraphWrapper() : graph(0) { }
1146    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1147
1148    //typedef Graph BaseGraph;
1149
1150    //typedef typename Graph::Node Node;
1151    //typedef typename Graph::NodeIt NodeIt;
1152
1153    //typedef typename Graph::Edge Edge;
1154    //typedef typename Graph::OutEdgeIt OutEdgeIt;
1155    //typedef typename Graph::InEdgeIt InEdgeIt;
1156    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1157    //typedef typename Graph::EdgeIt EdgeIt;
1158
1159    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1160    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1161
1162    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1163    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1164    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1165    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1166    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1167
1168    NodeIt& first(NodeIt& n) const {
1169      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1170    }
1171
1172    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1173      e=first_out_edges.get(n);
1174      return e;
1175    }
1176   
1177    //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1178    //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1179    //  return first(i, p); }
1180   
1181    //template<typename I> I getNext(const I& i) const {
1182    //  return gw.getNext(i); }
1183    //template<typename I> I& next(I &i) const { return gw.next(i); }   
1184
1185    template< typename It > It first() const {
1186      It e; first(e); return e; }
1187
1188    template< typename It > It first(const Node& v) const {
1189      It e; first(e, v); return e; }
1190
1191    //Node head(const Edge& e) const { return gw.head(e); }
1192    //Node tail(const Edge& e) const { return gw.tail(e); }
1193
1194    //template<typename I> bool valid(const I& i) const
1195    //  { return gw.valid(i); }
1196 
1197    //int nodeNum() const { return gw.nodeNum(); }
1198    //int edgeNum() const { return gw.edgeNum(); }
1199 
1200    //template<typename I> Node aNode(const I& e) const {
1201    //  return gw.aNode(e); }
1202    //template<typename I> Node bNode(const I& e) const {
1203    //  return gw.bNode(e); }
1204 
1205    //Node addNode() const { return gw.addNode(); }
1206    //Edge addEdge(const Node& tail, const Node& head) const {
1207    //  return gw.addEdge(tail, head); }
1208 
1209    //void erase(const OutEdgeIt& e) {
1210    //  first_out_edge(this->tail(e))=e;
1211    //}
1212    void erase(const Edge& e) {
1213      OutEdgeIt f(e);
1214      next(f);
1215      first_out_edges.set(this->tail(e), f);
1216    }
1217    //template<typename I> void erase(const I& i) const { gw.erase(i); }
1218 
1219    //void clear() const { gw.clear(); }
1220   
1221    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1222    public:
1223      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1224        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1225      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1226        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1227    };
1228
1229    template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1230    public:
1231      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1232        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1233      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1234        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1235    };
1236  };
1237
1238  template<typename GraphWrapper>
1239  class FilterGraphWrapper {
1240  };
1241
1242  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1243  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1244
1245    //Graph* graph;
1246 
1247  public:
1248    //typedef Graph BaseGraph;
1249
1250    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1251    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1252
1253    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1254    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1255    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1256    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1257    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1258
1259    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1260   
1261  public:
1262    FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1263                           const CapacityMap& _capacity) :
1264      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1265    }
1266
1267    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1268      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1269      while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1270        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1271      return e;
1272    }
1273
1274    NodeIt& next(NodeIt& e) const {
1275      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1276    }
1277
1278    OutEdgeIt& next(OutEdgeIt& e) const {
1279      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1280      while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1281        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1282      return e;
1283    }
1284
1285    NodeIt& first(NodeIt& n) const {
1286      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1287    }
1288
1289    void erase(const Edge& e) {
1290      OutEdgeIt f(e);
1291      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1292      while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1293        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1294      first_out_edges.set(this->tail(e), f);
1295    }
1296
1297    //TrivGraphWrapper() : graph(0) { }
1298    //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1299
1300    //void setGraph(Graph& _graph) { graph = &_graph; }
1301    //Graph& getGraph() const { return (*graph); }
1302   
1303    //template<typename I> I& first(I& i) const { return gw.first(i); }
1304    //template<typename I, typename P> I& first(I& i, const P& p) const {
1305    //  return gw.first(i, p); }
1306   
1307    //template<typename I> I getNext(const I& i) const {
1308    //  return gw.getNext(i); }
1309    //template<typename I> I& next(I &i) const { return gw.next(i); }   
1310
1311    template< typename It > It first() const {
1312      It e; first(e); return e; }
1313
1314    template< typename It > It first(const Node& v) const {
1315      It e; first(e, v); return e; }
1316
1317    //Node head(const Edge& e) const { return gw.head(e); }
1318    //Node tail(const Edge& e) const { return gw.tail(e); }
1319
1320    //template<typename I> bool valid(const I& i) const
1321    //  { return gw.valid(i); }
1322 
1323    //template<typename I> void setInvalid(const I &i);
1324    //{ return gw.setInvalid(i); }
1325
1326    //int nodeNum() const { return gw.nodeNum(); }
1327    //int edgeNum() const { return gw.edgeNum(); }
1328 
1329    //template<typename I> Node aNode(const I& e) const {
1330    //  return gw.aNode(e); }
1331    //template<typename I> Node bNode(const I& e) const {
1332    //  return gw.bNode(e); }
1333 
1334    //Node addNode() const { return gw.addNode(); }
1335    //Edge addEdge(const Node& tail, const Node& head) const {
1336    //  return gw.addEdge(tail, head); }
1337 
1338    //template<typename I> void erase(const I& i) const { gw.erase(i); }
1339 
1340    //void clear() const { gw.clear(); }
1341   
1342    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1343    public:
1344      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1345        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1346      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1347        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1348    };
1349
1350    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1351    public:
1352      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1353        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1354      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1355        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1356    };
1357
1358  public:
1359    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1360
1361  };
1362
1363
1364
1365// // FIXME: comparison should be made better!!!
1366//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1367//   class ResGraphWrapper
1368//   {
1369//     Graph* graph;
1370 
1371//   public:
1372//     typedef Graph BaseGraph;
1373
1374//     typedef typename Graph::Node Node;
1375//     typedef typename Graph::Edge Edge;
1376 
1377//     typedef typename Graph::NodeIt NodeIt;
1378   
1379//     class OutEdgeIt {
1380//     public:
1381//       //Graph::Node n;
1382//       bool out_or_in;
1383//       typename Graph::OutEdgeIt o;
1384//       typename Graph::InEdgeIt i;   
1385//     };
1386//     class InEdgeIt {
1387//     public:
1388//       //Graph::Node n;
1389//       bool out_or_in;
1390//       typename Graph::OutEdgeIt o;
1391//       typename Graph::InEdgeIt i;   
1392//     };
1393//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1394//     typedef typename Graph::EdgeIt EdgeIt;
1395
1396//     int nodeNum() const { return gw.nodeNum(); }
1397//     int edgeNum() const { return gw.edgeNum(); }
1398
1399//     Node& first(Node& n) const { return gw.first(n); }
1400
1401//     // Edge and SymEdge  is missing!!!!
1402//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1403
1404//     //FIXME
1405//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1406//       {
1407//      e.n=n;
1408//      gw.first(e.o,n);
1409//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1410//        gw.goNext(e.o);
1411//      if(!gw.valid(e.o)) {
1412//        gw.first(e.i,n);
1413//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1414//          gw.goNext(e.i);
1415//      }
1416//      return e;
1417//       }
1418// /*
1419//   OutEdgeIt &goNext(OutEdgeIt &e)
1420//   {
1421//   if(gw.valid(e.o)) {
1422//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1423//   gw.goNext(e.o);
1424//   if(gw.valid(e.o)) return e;
1425//   else gw.first(e.i,e.n);
1426//   }
1427//   else {
1428//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1429//   gw.goNext(e.i);
1430//   return e;
1431//   }
1432//   }
1433//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1434// */
1435//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1436
1437//     //FIXME
1438//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1439//       {
1440//      e.n=n;
1441//      gw.first(e.i,n);
1442//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1443//        gw.goNext(e.i);
1444//      if(!gw.valid(e.i)) {
1445//        gw.first(e.o,n);
1446//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1447//          gw.goNext(e.o);
1448//      }
1449//      return e;
1450//       }
1451// /*
1452//   InEdgeIt &goNext(InEdgeIt &e)
1453//   {
1454//   if(gw.valid(e.i)) {
1455//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1456//   gw.goNext(e.i);
1457//   if(gw.valid(e.i)) return e;
1458//   else gw.first(e.o,e.n);
1459//   }
1460//   else {
1461//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1462//   gw.goNext(e.o);
1463//   return e;
1464//   }
1465//   }
1466//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1467// */
1468//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1469
1470//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1471//     //template<typename I> I next(const I i); { return gw.goNext(i); }
1472
1473//     template< typename It > It first() const {
1474//       It e; first(e); return e; }
1475
1476//     template< typename It > It first(Node v) const {
1477//       It e; first(e, v); return e; }
1478
1479//     Node head(const Edge& e) const { return gw.head(e); }
1480//     Node tail(const Edge& e) const { return gw.tail(e); }
1481 
1482//     template<typename I> Node aNode(const I& e) const {
1483//       return gw.aNode(e); }
1484//     template<typename I> Node bNode(const I& e) const {
1485//       return gw.bNode(e); }
1486 
1487//     //template<typename I> bool valid(const I i);
1488//     //{ return gw.valid(i); }
1489 
1490//     //template<typename I> void setInvalid(const I &i);
1491//     //{ return gw.setInvalid(i); }
1492 
1493//     Node addNode() { return gw.addNode(); }
1494//     Edge addEdge(const Node& tail, const Node& head) {
1495//       return gw.addEdge(tail, head); }
1496 
1497//     template<typename I> void erase(const I& i) { gw.erase(i); }
1498 
1499//     void clear() { gw.clear(); }
1500 
1501//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1502//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1503 
1504//     void setGraph(Graph& _graph) { graph = &_graph; }
1505//     Graph& getGraph() { return (*graph); }
1506
1507//     //ResGraphWrapper() : graph(0) { }
1508//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1509//   };
1510
1511} //namespace hugo
1512
1513#endif //HUGO_GRAPH_WRAPPER_H
1514
Note: See TracBrowser for help on using the repository browser.