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 @ 237:7fb8b67d2c5e

Last change on this file since 237:7fb8b67d2c5e was 237:7fb8b67d2c5e, checked in by marci, 20 years ago

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