COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 174:44700ed9ffaa

Last change on this file since 174:44700ed9ffaa was 174:44700ed9ffaa, checked in by marci, 20 years ago

towards on ListGraph?, SmartGraph? compatibility

File size: 36.9 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    Graph* graph;
12 
13  public:
14    typedef Graph BaseGraph;
15
16    typedef typename Graph::Node Node;
17    typedef typename Graph::NodeIt NodeIt;
18
19    typedef typename Graph::Edge Edge;
20    typedef typename Graph::OutEdgeIt OutEdgeIt;
21    typedef typename Graph::InEdgeIt InEdgeIt;
22    //typedef typename Graph::SymEdgeIt SymEdgeIt;
23    typedef typename Graph::EdgeIt EdgeIt;
24
25    //TrivGraphWrapper() : graph(0) { }
26    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
27
28    void setGraph(Graph& _graph) { graph = &_graph; }
29    Graph& getGraph() const { return (*graph); }
30   
31    template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
32    template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
33      return graph->/*getF*/first(i, p); }
34   
35    template<typename I> I getNext(const I& i) const {
36      return graph->getNext(i); }
37    template<typename I> I& next(I &i) const { return graph->next(i); }   
38
39    template< typename It > It first() const {
40      It e; /*getF*/first(e); return e; }
41
42    template< typename It > It first(const Node& v) const {
43      It e; /*getF*/first(e, v); return e; }
44
45    Node head(const Edge& e) const { return graph->head(e); }
46    Node tail(const Edge& e) const { return graph->tail(e); }
47
48    template<typename I> bool valid(const I& i) const
49      { return graph->valid(i); }
50 
51    //template<typename I> void setInvalid(const I &i);
52    //{ return graph->setInvalid(i); }
53
54    int nodeNum() const { return graph->nodeNum(); }
55    int edgeNum() const { return graph->edgeNum(); }
56 
57    template<typename I> Node aNode(const I& e) const {
58      return graph->aNode(e); }
59    template<typename I> Node bNode(const I& e) const {
60      return graph->bNode(e); }
61 
62    Node addNode() const { return graph->addNode(); }
63    Edge addEdge(const Node& tail, const Node& head) const {
64      return graph->addEdge(tail, head); }
65 
66    template<typename I> void erase(const I& i) const { graph->erase(i); }
67 
68    void clear() const { graph->clear(); }
69   
70    template<typename T> class NodeMap : public Graph::NodeMap<T> {
71    public:
72      NodeMap(const TrivGraphWrapper<Graph>& _G) :
73        Graph::NodeMap<T>(_G.getGraph()) { }
74      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
75        Graph::NodeMap<T>(_G.getGraph(), a) { }
76    };
77
78    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
79    public:
80      EdgeMap(const TrivGraphWrapper<Graph>& _G) :
81        Graph::EdgeMap<T>(_G.getGraph()) { }
82      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
83        Graph::EdgeMap<T>(_G.getGraph(), a) { }
84    };
85  };
86
87  template<typename Graph>
88  class RevGraphWrapper
89  {
90    Graph* graph;
91 
92  public:
93    typedef Graph BaseGraph;
94
95    typedef typename Graph::Node Node;   
96    typedef typename Graph::NodeIt NodeIt;
97 
98    typedef typename Graph::Edge Edge;
99    typedef typename Graph::OutEdgeIt InEdgeIt;
100    typedef typename Graph::InEdgeIt OutEdgeIt;
101    //typedef typename Graph::SymEdgeIt SymEdgeIt;
102    typedef typename Graph::EdgeIt EdgeIt;
103
104    //RevGraphWrapper() : graph(0) { }
105    RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
106
107    void setGraph(Graph& _graph) { graph = &_graph; }
108    Graph& getGraph() const { return (*graph); }
109   
110    template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
111    template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
112      return graph->/*getF*/first(i, p); }
113
114    template<typename I> I getNext(const I& i) const {
115      return graph->getNext(i); }
116    template<typename I> I& next(I &i) const { return graph->next(i); }   
117
118    template< typename It > It first() const {
119      It e; /*getF*/first(e); return e; }
120
121    template< typename It > It first(const Node& v) const {
122      It e; /*getF*/first(e, v); return e; }
123
124    Node head(const Edge& e) const { return graph->tail(e); }
125    Node tail(const Edge& e) const { return graph->head(e); }
126 
127    template<typename I> bool valid(const I& i) const
128      { return graph->valid(i); }
129 
130    //template<typename I> void setInvalid(const I &i);
131    //{ return graph->setInvalid(i); }
132 
133    template<typename I> Node aNode(const I& e) const {
134      return graph->aNode(e); }
135    template<typename I> Node bNode(const I& e) const {
136      return graph->bNode(e); }
137
138    Node addNode() const { return graph->addNode(); }
139    Edge addEdge(const Node& tail, const Node& head) const {
140      return graph->addEdge(tail, head); }
141 
142    int nodeNum() const { return graph->nodeNum(); }
143    int edgeNum() const { return graph->edgeNum(); }
144 
145    template<typename I> void erase(const I& i) const { graph->erase(i); }
146 
147    void clear() const { graph->clear(); }
148
149    template<typename T> class NodeMap : public Graph::NodeMap<T> {
150    public:
151      NodeMap(const RevGraphWrapper<Graph>& _G) :
152        Graph::NodeMap<T>(_G.getGraph()) { }
153      NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
154        Graph::NodeMap<T>(_G.getGraph(), a) { }
155    };
156
157    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
158    public:
159      EdgeMap(const RevGraphWrapper<Graph>& _G) :
160        Graph::EdgeMap<T>(_G.getGraph()) { }
161      EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
162        Graph::EdgeMap<T>(_G.getGraph(), a) { }
163    };
164  };
165
166
167  template<typename Graph>
168  class UndirGraphWrapper {
169    Graph* graph;
170 
171  public:
172    typedef Graph BaseGraph;
173
174    typedef typename Graph::Node Node;
175    typedef typename Graph::NodeIt NodeIt;
176
177    //typedef typename Graph::Edge Edge;
178    //typedef typename Graph::OutEdgeIt OutEdgeIt;
179    //typedef typename Graph::InEdgeIt InEdgeIt;
180    //typedef typename Graph::SymEdgeIt SymEdgeIt;
181    //typedef typename Graph::EdgeIt EdgeIt;
182
183    //private:
184    typedef typename Graph::Edge GraphEdge;
185    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
186    typedef typename Graph::InEdgeIt GraphInEdgeIt;
187    //public:
188
189    //UndirGraphWrapper() : graph(0) { }
190    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
191
192    void setGraph(Graph& _graph) { graph = &_graph; }
193    Graph& getGraph() const { return (*graph); }
194 
195    class Edge {
196      friend class UndirGraphWrapper<Graph>;
197      bool out_or_in; //true iff out
198      GraphOutEdgeIt out;
199      GraphInEdgeIt in;
200    public:
201      Edge() : out_or_in(), out(), in() { }
202      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
203      operator GraphEdge() const {
204        if (out_or_in) return(out); else return(in);
205      }
206      friend bool operator==(const Edge& u, const Edge& v) {
207        if (v.out_or_in)
208          return (u.out_or_in && u.out==v.out);
209        else
210          return (!u.out_or_in && u.in==v.in);
211      }
212      friend bool operator!=(const Edge& u, const Edge& v) {
213        if (v.out_or_in)
214          return (!u.out_or_in || u.out!=v.out);
215        else
216          return (u.out_or_in || u.in!=v.in);
217      }
218    };
219
220    class OutEdgeIt : public Edge {
221      friend class UndirGraphWrapper<Graph>;
222    public:
223      OutEdgeIt() : Edge() { }
224      OutEdgeIt(const Invalid& i) : Edge(i) { }
225      OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
226        out_or_in=true;
227        _G.graph->/*getF*/first(out, n);
228        if (!(_G.graph->valid(out))) {
229          out_or_in=false;
230          _G.graph->/*getF*/first(in, n);
231        }
232      }
233    };
234
235    OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
236      e.out_or_in=true;
237      graph->/*getF*/first(e.out, n);
238      if (!(graph->valid(e.out))) {
239        e.out_or_in=false;
240        graph->/*getF*/first(e.in, n);
241      }
242      return e;
243    }
244
245    OutEdgeIt& next(OutEdgeIt& e) const {
246      if (e.out_or_in) {
247        Node n=graph->tail(e.out);
248        graph->next(e.out);
249        if (!graph->valid(e.out)) {
250          e.out_or_in=false;
251          graph->/*getF*/first(e.in, n);
252        }
253      } else {
254        graph->next(e.in);
255      }
256      return e;
257    }
258
259    Node aNode(const OutEdgeIt& e) const {
260      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
261    Node bNode(const OutEdgeIt& e) const {
262      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
263
264    typedef OutEdgeIt InEdgeIt;
265
266    template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
267//     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
268//       return graph->/*getF*/first(i, p); }
269   
270    template<typename I> I getNext(const I& i) const {
271      return graph->getNext(i); }
272    template<typename I> I& next(I &i) const { return graph->next(i); }   
273
274    template< typename It > It first() const {
275      It e; /*getF*/first(e); return e; }
276
277    template< typename It > It first(const Node& v) const {
278      It e; /*getF*/first(e, v); return e; }
279
280    Node head(const Edge& e) const { return graph->head(e); }
281    Node tail(const Edge& e) const { return graph->tail(e); }
282
283    template<typename I> bool valid(const I& i) const
284      { return graph->valid(i); }
285 
286    //template<typename I> void setInvalid(const I &i);
287    //{ return graph->setInvalid(i); }
288
289    int nodeNum() const { return graph->nodeNum(); }
290    int edgeNum() const { return graph->edgeNum(); }
291 
292//     template<typename I> Node aNode(const I& e) const {
293//       return graph->aNode(e); }
294//     template<typename I> Node bNode(const I& e) const {
295//       return graph->bNode(e); }
296 
297    Node addNode() const { return graph->addNode(); }
298    Edge addEdge(const Node& tail, const Node& head) const {
299      return graph->addEdge(tail, head); }
300 
301    template<typename I> void erase(const I& i) const { graph->erase(i); }
302 
303    void clear() const { graph->clear(); }
304   
305    template<typename T> class NodeMap : public Graph::NodeMap<T> {
306    public:
307      NodeMap(const UndirGraphWrapper<Graph>& _G) :
308        Graph::NodeMap<T>(_G.getGraph()) { }
309      NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
310        Graph::NodeMap<T>(_G.getGraph(), a) { }
311    };
312
313    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
314    public:
315      EdgeMap(const UndirGraphWrapper<Graph>& _G) :
316        Graph::EdgeMap<T>(_G.getGraph()) { }
317      EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
318        Graph::EdgeMap<T>(_G.getGraph(), a) { }
319    };
320  };
321
322
323
324//   template<typename Graph>
325//   class SymGraphWrapper
326//   {
327//     Graph* graph;
328 
329//   public:
330//     typedef Graph BaseGraph;
331
332//     typedef typename Graph::Node Node;
333//     typedef typename Graph::Edge Edge;
334 
335//     typedef typename Graph::NodeIt NodeIt;
336   
337//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
338//     //iranyitatlant, ami van
339//     //mert csak 1 dolgot lehet be typedef-elni
340//     typedef typename Graph::OutEdgeIt SymEdgeIt;
341//     //typedef typename Graph::InEdgeIt SymEdgeIt;
342//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
343//     typedef typename Graph::EdgeIt EdgeIt;
344
345//     int nodeNum() const { return graph->nodeNum(); }
346//     int edgeNum() const { return graph->edgeNum(); }
347   
348//     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
349//     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
350//       return graph->/*getF*/first(i, p); }
351//     //template<typename I> I next(const I i); { return graph->goNext(i); }
352//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
353
354//     template< typename It > It first() const {
355//       It e; /*getF*/first(e); return e; }
356
357//     template< typename It > It first(Node v) const {
358//       It e; /*getF*/first(e, v); return e; }
359
360//     Node head(const Edge& e) const { return graph->head(e); }
361//     Node tail(const Edge& e) const { return graph->tail(e); }
362 
363//     template<typename I> Node aNode(const I& e) const {
364//       return graph->aNode(e); }
365//     template<typename I> Node bNode(const I& e) const {
366//       return graph->bNode(e); }
367 
368//     //template<typename I> bool valid(const I i);
369//     //{ return graph->valid(i); }
370 
371//     //template<typename I> void setInvalid(const I &i);
372//     //{ return graph->setInvalid(i); }
373 
374//     Node addNode() { return graph->addNode(); }
375//     Edge addEdge(const Node& tail, const Node& head) {
376//       return graph->addEdge(tail, head); }
377 
378//     template<typename I> void erase(const I& i) { graph->erase(i); }
379 
380//     void clear() { graph->clear(); }
381 
382//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
383//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
384 
385//     void setGraph(Graph& _graph) { graph = &_graph; }
386//     Graph& getGraph() { return (*graph); }
387
388//     //SymGraphWrapper() : graph(0) { }
389//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
390//   };
391
392
393  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
394  class ResGraphWrapper {
395  public:
396    typedef Graph BaseGraph;
397    typedef typename Graph::Node Node;
398    typedef typename Graph::NodeIt NodeIt;
399  private:
400    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
401    typedef typename Graph::InEdgeIt OldInEdgeIt;
402    const Graph* graph;
403    FlowMap* flow;
404    const CapacityMap* capacity;
405  public:
406
407    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
408             const CapacityMap& _capacity) :
409      graph(&_G), flow(&_flow), capacity(&_capacity) { }
410
411    void setGraph(const Graph& _graph) { graph = &_graph; }
412    const Graph& getGraph() const { return (*graph); }
413
414    class Edge;
415    class OutEdgeIt;
416    friend class Edge;
417    friend class OutEdgeIt;
418
419    class Edge {
420      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
421    protected:
422      bool out_or_in; //true, iff out
423      OldOutEdgeIt out;
424      OldInEdgeIt in;
425    public:
426      Edge() : out_or_in(true) { }
427      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
428//       bool valid() const {
429//      return out_or_in && out.valid() || in.valid(); }
430      friend bool operator==(const Edge& u, const Edge& v) {
431        if (v.out_or_in)
432          return (u.out_or_in && u.out==v.out);
433        else
434          return (!u.out_or_in && u.in==v.in);
435      }
436      friend bool operator!=(const Edge& u, const Edge& v) {
437        if (v.out_or_in)
438          return (!u.out_or_in || u.out!=v.out);
439        else
440          return (u.out_or_in || u.in!=v.in);
441      }
442    };
443
444
445    class OutEdgeIt : public Edge {
446      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
447    public:
448      OutEdgeIt() { }
449      //FIXME
450      OutEdgeIt(const Edge& e) : Edge(e) { }
451      OutEdgeIt(const Invalid& i) : Edge(i) { }
452    private:
453      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
454        resG.graph->/*getF*/first(out, v);
455        while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
456        if (!resG.graph->valid(out)) {
457          out_or_in=0;
458          resG.graph->/*getF*/first(in, v);
459          while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
460        }
461      }
462//     public:
463//       OutEdgeIt& operator++() {
464//      if (out_or_in) {
465//        Node v=/*resG->*/G->aNode(out);
466//        ++out;
467//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
468//        if (!out.valid()) {
469//          out_or_in=0;
470//          G->/*getF*/first(in, v);
471//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
472//        }
473//      } else {
474//        ++in;
475//        while( in.valid() && !(Edge::free()>0) ) { ++in; }
476//      }
477//      return *this;
478//       }
479    };
480
481    class EdgeIt : public Edge {
482      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
483      typename Graph::NodeIt v;
484    public:
485      EdgeIt() { }
486      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
487      EdgeIt(const Invalid& i) : Edge(i) { }
488      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
489        resG.graph->/*getF*/first(v);
490        if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID);
491        while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
492        while (resG.graph->valid(v) && !resG.graph->valid(out)) {
493          resG.graph->next(v);
494          if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v);
495          while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
496        }
497        if (!resG.graph->valid(out)) {
498          out_or_in=0;
499          resG.graph->/*getF*/first(v);
500          if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID);
501          while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
502          while (resG.graph->valid(v) && !resG.graph->valid(in)) {
503            resG.graph->next(v);
504            if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v);
505            while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
506          }
507        }
508      }
509//       EdgeIt& operator++() {
510//      if (out_or_in) {
511//        ++out;
512//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
513//        while (v.valid() && !out.valid()) {
514//          ++v;
515//          if (v.valid()) G->/*getF*/first(out, v);
516//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
517//        }
518//        if (!out.valid()) {
519//          out_or_in=0;
520//          G->/*getF*/first(v);
521//          if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt();
522//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
523//          while (v.valid() && !in.valid()) {
524//            ++v;
525//            if (v.valid()) G->/*getF*/first(in, v);
526//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
527//          } 
528//        }
529//      } else {
530//        ++in;
531//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
532//        while (v.valid() && !in.valid()) {
533//          ++v;
534//          if (v.valid()) G->/*getF*/first(in, v);
535//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
536//        }
537//      }
538//      return *this;
539//       }
540    };
541
542    NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); }
543    OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
544      e=OutEdgeIt(*this, v);
545      return e;
546    }
547    EdgeIt& /*getF*/first(EdgeIt& e) const {
548      e=EdgeIt(*this);
549      return e;
550    }
551   
552    NodeIt& next(NodeIt& n) const { return graph->next(n); }
553
554    OutEdgeIt& next(OutEdgeIt& e) const {
555      if (e.out_or_in) {
556        Node v=graph->aNode(e.out);
557        graph->next(e.out);
558        while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
559        if (!graph->valid(e.out)) {
560          e.out_or_in=0;
561          graph->/*getF*/first(e.in, v);
562          while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
563        }
564      } else {
565        graph->next(e.in);
566        while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
567      }
568      return e;
569    }
570
571    EdgeIt& next(EdgeIt& e) const {
572      if (e.out_or_in) {
573        graph->next(e.out);
574        while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
575          while (graph->valid(e.v) && !graph->valid(e.out)) {
576            graph->next(e.v);
577            if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v);
578            while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
579          }
580          if (!graph->valid(e.out)) {
581            e.out_or_in=0;
582            graph->/*getF*/first(e.v);
583            if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
584            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
585            while (graph->valid(e.v) && !graph->valid(e.in)) {
586              graph->next(e.v);
587              if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
588              while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
589            } 
590          }
591        } else {
592          graph->next(e.in);
593          while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
594          while (graph->valid(e.v) && !graph->valid(e.in)) {
595            graph->next(e.v);
596            if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
597            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
598          }
599        }
600        return e;
601      }
602   
603
604    template< typename It >
605    It first() const {
606      It e;
607      /*getF*/first(e);
608      return e;
609    }
610
611    template< typename It >
612    It first(Node v) const {
613      It e;
614      /*getF*/first(e, v);
615      return e;
616    }
617
618    Node tail(Edge e) const {
619      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
620    Node head(Edge e) const {
621      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
622
623    Node aNode(OutEdgeIt e) const {
624      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
625    Node bNode(OutEdgeIt e) const {
626      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
627
628    int id(Node v) const { return graph->id(v); }
629
630    bool valid(Node n) const { return graph->valid(n); }
631    bool valid(Edge e) const {
632      return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
633
634    void augment(const Edge& e, Number a) const {
635      if (e.out_or_in) 
636        flow->set(e.out, flow->get(e.out)+a);
637      else 
638        flow->set(e.in, flow->get(e.in)-a);
639    }
640
641    Number free(const Edge& e) const {
642      if (e.out_or_in)
643        return (capacity->get(e.out)-flow->get(e.out));
644      else
645        return (flow->get(e.in));
646    }
647
648    Number free(OldOutEdgeIt out) const {
649      return (capacity->get(out)-flow->get(out));
650    }
651   
652    Number free(OldInEdgeIt in) const {
653      return (flow->get(in));
654    }
655
656    template<typename T> class NodeMap : public Graph::NodeMap<T> {
657    public:
658      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
659        : Graph::NodeMap<T>(_G.getGraph()) { }
660      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
661              T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
662    };
663
664//     template <typename T>
665//     class NodeMap {
666//       typename Graph::NodeMap<T> node_map;
667//     public:
668//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
669//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
670//       void set(Node nit, T a) { node_map.set(nit, a); }
671//       T get(Node nit) const { return node_map.get(nit); }
672//     };
673
674    template <typename T>
675    class EdgeMap {
676      typename Graph::EdgeMap<T> forward_map, backward_map;
677    public:
678      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
679      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
680      void set(Edge e, T a) {
681        if (e.out_or_in)
682          forward_map.set(e.out, a);
683        else
684          backward_map.set(e.in, a);
685      }
686      T get(Edge e) {
687        if (e.out_or_in)
688          return forward_map.get(e.out);
689        else
690          return backward_map.get(e.in);
691      }
692    };
693  };
694
695  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
696  class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
697  protected:
698    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
699    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
700  public:
701    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
702                           const CapacityMap& _capacity) :
703      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
704      first_out_edges(*this) /*, dist(*this)*/ {
705      for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
706        OutEdgeIt e;
707        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
708        first_out_edges.set(n, e);
709      }
710    }
711
712    //void setGraph(Graph& _graph) { graph = &_graph; }
713    //Graph& getGraph() const { return (*graph); }
714 
715    //TrivGraphWrapper() : graph(0) { }
716    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
717
718    //typedef Graph BaseGraph;
719
720    //typedef typename Graph::Node Node;
721    //typedef typename Graph::NodeIt NodeIt;
722
723    //typedef typename Graph::Edge Edge;
724    //typedef typename Graph::OutEdgeIt OutEdgeIt;
725    //typedef typename Graph::InEdgeIt InEdgeIt;
726    //typedef typename Graph::SymEdgeIt SymEdgeIt;
727    //typedef typename Graph::EdgeIt EdgeIt;
728
729    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
730    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
731
732    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
733    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
734    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
735    //typedef typename Graph::SymEdgeIt SymEdgeIt;
736    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
737
738    NodeIt& /*getF*/first(NodeIt& n) const {
739      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
740    }
741
742    OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
743      e=first_out_edges.get(n);
744      return e;
745    }
746   
747    //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); }
748    //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
749    //  return /*getF*/first(i, p); }
750   
751    //template<typename I> I getNext(const I& i) const {
752    //  return graph->getNext(i); }
753    //template<typename I> I& next(I &i) const { return graph->next(i); }   
754
755    template< typename It > It first() const {
756      It e; /*getF*/first(e); return e; }
757
758    template< typename It > It first(const Node& v) const {
759      It e; /*getF*/first(e, v); return e; }
760
761    //Node head(const Edge& e) const { return graph->head(e); }
762    //Node tail(const Edge& e) const { return graph->tail(e); }
763
764    //template<typename I> bool valid(const I& i) const
765    //  { return graph->valid(i); }
766 
767    //int nodeNum() const { return graph->nodeNum(); }
768    //int edgeNum() const { return graph->edgeNum(); }
769 
770    //template<typename I> Node aNode(const I& e) const {
771    //  return graph->aNode(e); }
772    //template<typename I> Node bNode(const I& e) const {
773    //  return graph->bNode(e); }
774 
775    //Node addNode() const { return graph->addNode(); }
776    //Edge addEdge(const Node& tail, const Node& head) const {
777    //  return graph->addEdge(tail, head); }
778 
779    //void erase(const OutEdgeIt& e) {
780    //  first_out_edge(this->tail(e))=e;
781    //}
782    void erase(const Edge& e) {
783      OutEdgeIt f(e);
784      next(f);
785      first_out_edges.set(this->tail(e), f);
786    }
787    //template<typename I> void erase(const I& i) const { graph->erase(i); }
788 
789    //void clear() const { graph->clear(); }
790   
791    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
792    public:
793      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
794        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
795      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
796        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
797    };
798
799    template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
800    public:
801      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
802        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
803      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
804        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
805    };
806  };
807
808  template<typename GraphWrapper>
809  class FilterGraphWrapper {
810  };
811
812  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
813  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
814
815    //Graph* graph;
816 
817  public:
818    //typedef Graph BaseGraph;
819
820    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
821    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
822
823    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
824    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
825    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
826    //typedef typename Graph::SymEdgeIt SymEdgeIt;
827    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
828
829    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
830   
831  public:
832    FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
833                           const CapacityMap& _capacity) :
834      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {
835    }
836
837    OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
838      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
839      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
840        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
841      return e;
842    }
843
844    NodeIt& next(NodeIt& e) const {
845      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
846    }
847
848    OutEdgeIt& next(OutEdgeIt& e) const {
849      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
850      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
851        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
852      return e;
853    }
854
855    NodeIt& /*getF*/first(NodeIt& n) const {
856      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
857    }
858
859    void erase(const Edge& e) {
860      OutEdgeIt f(e);
861      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
862      while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))
863        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
864      first_out_edges.set(this->tail(e), f);
865    }
866
867    //TrivGraphWrapper() : graph(0) { }
868    //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
869
870    //void setGraph(Graph& _graph) { graph = &_graph; }
871    //Graph& getGraph() const { return (*graph); }
872   
873    //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
874    //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
875    //  return graph->/*getF*/first(i, p); }
876   
877    //template<typename I> I getNext(const I& i) const {
878    //  return graph->getNext(i); }
879    //template<typename I> I& next(I &i) const { return graph->next(i); }   
880
881    template< typename It > It first() const {
882      It e; /*getF*/first(e); return e; }
883
884    template< typename It > It first(const Node& v) const {
885      It e; /*getF*/first(e, v); return e; }
886
887    //Node head(const Edge& e) const { return graph->head(e); }
888    //Node tail(const Edge& e) const { return graph->tail(e); }
889
890    //template<typename I> bool valid(const I& i) const
891    //  { return graph->valid(i); }
892 
893    //template<typename I> void setInvalid(const I &i);
894    //{ return graph->setInvalid(i); }
895
896    //int nodeNum() const { return graph->nodeNum(); }
897    //int edgeNum() const { return graph->edgeNum(); }
898 
899    //template<typename I> Node aNode(const I& e) const {
900    //  return graph->aNode(e); }
901    //template<typename I> Node bNode(const I& e) const {
902    //  return graph->bNode(e); }
903 
904    //Node addNode() const { return graph->addNode(); }
905    //Edge addEdge(const Node& tail, const Node& head) const {
906    //  return graph->addEdge(tail, head); }
907 
908    //template<typename I> void erase(const I& i) const { graph->erase(i); }
909 
910    //void clear() const { graph->clear(); }
911   
912    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
913    public:
914      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
915        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
916      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
917        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
918    };
919
920    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
921    public:
922      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
923        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
924      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
925        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
926    };
927
928  public:
929    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
930
931  };
932
933
934
935// // FIXME: comparison should be made better!!!
936//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
937//   class ResGraphWrapper
938//   {
939//     Graph* graph;
940 
941//   public:
942//     typedef Graph BaseGraph;
943
944//     typedef typename Graph::Node Node;
945//     typedef typename Graph::Edge Edge;
946 
947//     typedef typename Graph::NodeIt NodeIt;
948   
949//     class OutEdgeIt {
950//     public:
951//       //Graph::Node n;
952//       bool out_or_in;
953//       typename Graph::OutEdgeIt o;
954//       typename Graph::InEdgeIt i;   
955//     };
956//     class InEdgeIt {
957//     public:
958//       //Graph::Node n;
959//       bool out_or_in;
960//       typename Graph::OutEdgeIt o;
961//       typename Graph::InEdgeIt i;   
962//     };
963//     typedef typename Graph::SymEdgeIt SymEdgeIt;
964//     typedef typename Graph::EdgeIt EdgeIt;
965
966//     int nodeNum() const { return graph->nodeNum(); }
967//     int edgeNum() const { return graph->edgeNum(); }
968
969//     Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); }
970
971//     // Edge and SymEdge  is missing!!!!
972//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
973
974//     //FIXME
975//     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const
976//       {
977//      e.n=n;
978//      graph->/*getF*/first(e.o,n);
979//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
980//        graph->goNext(e.o);
981//      if(!graph->valid(e.o)) {
982//        graph->/*getF*/first(e.i,n);
983//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
984//          graph->goNext(e.i);
985//      }
986//      return e;
987//       }
988// /*
989//   OutEdgeIt &goNext(OutEdgeIt &e)
990//   {
991//   if(graph->valid(e.o)) {
992//   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
993//   graph->goNext(e.o);
994//   if(graph->valid(e.o)) return e;
995//   else graph->/*getF*/first(e.i,e.n);
996//   }
997//   else {
998//   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
999//   graph->goNext(e.i);
1000//   return e;
1001//   }
1002//   }
1003//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1004// */
1005//     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
1006
1007//     //FIXME
1008//     InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const
1009//       {
1010//      e.n=n;
1011//      graph->/*getF*/first(e.i,n);
1012//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1013//        graph->goNext(e.i);
1014//      if(!graph->valid(e.i)) {
1015//        graph->/*getF*/first(e.o,n);
1016//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1017//          graph->goNext(e.o);
1018//      }
1019//      return e;
1020//       }
1021// /*
1022//   InEdgeIt &goNext(InEdgeIt &e)
1023//   {
1024//   if(graph->valid(e.i)) {
1025//   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1026//   graph->goNext(e.i);
1027//   if(graph->valid(e.i)) return e;
1028//   else graph->/*getF*/first(e.o,e.n);
1029//   }
1030//   else {
1031//   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1032//   graph->goNext(e.o);
1033//   return e;
1034//   }
1035//   }
1036//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1037// */
1038//     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
1039
1040//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1041//     //template<typename I> I next(const I i); { return graph->goNext(i); }
1042
1043//     template< typename It > It first() const {
1044//       It e; /*getF*/first(e); return e; }
1045
1046//     template< typename It > It first(Node v) const {
1047//       It e; /*getF*/first(e, v); return e; }
1048
1049//     Node head(const Edge& e) const { return graph->head(e); }
1050//     Node tail(const Edge& e) const { return graph->tail(e); }
1051 
1052//     template<typename I> Node aNode(const I& e) const {
1053//       return graph->aNode(e); }
1054//     template<typename I> Node bNode(const I& e) const {
1055//       return graph->bNode(e); }
1056 
1057//     //template<typename I> bool valid(const I i);
1058//     //{ return graph->valid(i); }
1059 
1060//     //template<typename I> void setInvalid(const I &i);
1061//     //{ return graph->setInvalid(i); }
1062 
1063//     Node addNode() { return graph->addNode(); }
1064//     Edge addEdge(const Node& tail, const Node& head) {
1065//       return graph->addEdge(tail, head); }
1066 
1067//     template<typename I> void erase(const I& i) { graph->erase(i); }
1068 
1069//     void clear() { graph->clear(); }
1070 
1071//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1072//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1073 
1074//     void setGraph(Graph& _graph) { graph = &_graph; }
1075//     Graph& getGraph() { return (*graph); }
1076
1077//     //ResGraphWrapper() : graph(0) { }
1078//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1079//   };
1080
1081} //namespace hugo
1082
1083#endif //GRAPH_WRAPPER_H
1084
Note: See TracBrowser for help on using the repository browser.