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 @ 236:ea3de9530ee8

Last change on this file since 236:ea3de9530ee8 was 236:ea3de9530ee8, checked in by marci, 20 years ago

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