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 @ 169:940b13aba5ff

Last change on this file since 169:940b13aba5ff was 168:27fbd1559fb7, checked in by marci, 20 years ago

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