COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 206:47f62d789fe7

Last change on this file since 206:47f62d789fe7 was 199:98b93792541e, checked in by marci, 20 years ago

.

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