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 @ 158:4f54d89fa9d2

Last change on this file since 158:4f54d89fa9d2 was 158:4f54d89fa9d2, checked in by marci, 21 years ago

a lot of interesting and very useful wrapper graphs
File size: 26.2 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    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
24    template<typename I, typename P> I& getFirst(I& i, const P& p) const {
25      return graph->getFirst(i, p); }
26   
27    template<typename I> I getNext(const I& i) const {
28      return graph->getNext(i); }
29    template<typename I> I& next(I &i) const { return graph->next(i); }   
30
31    template< typename It > It first() const {
32      It e; getFirst(e); return e; }
33
34    template< typename It > It first(const NodeIt& v) const {
35      It e; getFirst(e, v); return e; }
36
37    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
38    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
39
40    template<typename I> bool valid(const I& i) const
41      { return graph->valid(i); }
42 
43    //template<typename I> void setInvalid(const I &i);
44    //{ return graph->setInvalid(i); }
45
46    int nodeNum() const { return graph->nodeNum(); }
47    int edgeNum() const { return graph->edgeNum(); }
48 
49    template<typename I> NodeIt aNode(const I& e) const {
50      return graph->aNode(e); }
51    template<typename I> NodeIt bNode(const I& e) const {
52      return graph->bNode(e); }
53 
54    NodeIt addNode() const { return graph->addNode(); }
55    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
56      return graph->addEdge(tail, head); }
57 
58    template<typename I> void erase(const I& i) const { graph->erase(i); }
59 
60    void clear() const { graph->clear(); }
61   
62    template<typename T> class NodeMap : public Graph::NodeMap<T> {
63    public:
64      NodeMap(const TrivGraphWrapper<Graph>& _G) :
65        Graph::NodeMap<T>(_G.getGraph()) { }
66      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
67        Graph::NodeMap<T>(_G.getGraph(), a) { }
68    };
69    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
70    public:
71      EdgeMap(const TrivGraphWrapper<Graph>& _G) :
72        Graph::EdgeMap<T>(_G.getGraph()) { }
73      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
74        Graph::EdgeMap<T>(_G.getGraph(), a) { }
75    };
76   
77    void setGraph(Graph& _graph) { graph = &_graph; }
78    Graph& getGraph() const { return (*graph); }
79 
80    //TrivGraphWrapper() : graph(0) { }
81    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
82  };
83
84  template<typename Graph>
85  class RevGraphWrapper
86  {
87    Graph* graph;
88 
89  public:
90    typedef Graph BaseGraph;
91
92    typedef typename Graph::NodeIt NodeIt;   
93    typedef typename Graph::EachNodeIt EachNodeIt;
94 
95    typedef typename Graph::EdgeIt EdgeIt;
96    typedef typename Graph::OutEdgeIt InEdgeIt;
97    typedef typename Graph::InEdgeIt OutEdgeIt;
98    //typedef typename Graph::SymEdgeIt SymEdgeIt;
99    typedef typename Graph::EachEdgeIt EachEdgeIt;
100   
101    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
102    template<typename I, typename P> I& getFirst(I& i, const P& p) const {
103      return graph->getFirst(i, p); }
104
105    template<typename I> I getNext(const I& i) const {
106      return graph->getNext(i); }
107    template<typename I> I& next(I &i) const { return graph->next(i); }   
108
109    template< typename It > It first() const {
110      It e; getFirst(e); return e; }
111
112    template< typename It > It first(const NodeIt& v) const {
113      It e; getFirst(e, v); return e; }
114
115    NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
116    NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
117 
118    template<typename I> bool valid(const I& i) const
119      { return graph->valid(i); }
120 
121    //template<typename I> void setInvalid(const I &i);
122    //{ return graph->setInvalid(i); }
123 
124    template<typename I> NodeIt aNode(const I& e) const {
125      return graph->aNode(e); }
126    template<typename I> NodeIt bNode(const I& e) const {
127      return graph->bNode(e); }
128
129    NodeIt addNode() const { return graph->addNode(); }
130    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
131      return graph->addEdge(tail, head); }
132 
133    int nodeNum() const { return graph->nodeNum(); }
134    int edgeNum() const { return graph->edgeNum(); }
135 
136    template<typename I> void erase(const I& i) const { graph->erase(i); }
137 
138    void clear() const { graph->clear(); }
139
140    template<typename T> class NodeMap : public Graph::NodeMap<T> {
141    public:
142      NodeMap(const RevGraphWrapper<Graph>& _G) :
143        Graph::NodeMap<T>(_G.getGraph()) { }
144      NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
145        Graph::NodeMap<T>(_G.getGraph(), a) { }
146    };
147    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
148    public:
149      EdgeMap(const RevGraphWrapper<Graph>& _G) :
150        Graph::EdgeMap<T>(_G.getGraph()) { }
151      EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
152        Graph::EdgeMap<T>(_G.getGraph(), a) { }
153    };
154
155    void setGraph(Graph& _graph) { graph = &_graph; }
156    Graph& getGraph() const { return (*graph); }
157
158    //RevGraphWrapper() : graph(0) { }
159    RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
160  };
161
162
163  template<typename Graph>
164  class UndirGraphWrapper {
165    Graph* graph;
166 
167  public:
168    typedef Graph BaseGraph;
169
170    typedef typename Graph::NodeIt NodeIt;
171    typedef typename Graph::EachNodeIt EachNodeIt;
172
173    //typedef typename Graph::EdgeIt EdgeIt;
174    //typedef typename Graph::OutEdgeIt OutEdgeIt;
175    //typedef typename Graph::InEdgeIt InEdgeIt;
176    //typedef typename Graph::SymEdgeIt SymEdgeIt;
177    //typedef typename Graph::EachEdgeIt EachEdgeIt;
178
179    //private:
180    typedef typename Graph::EdgeIt GraphEdgeIt;
181    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
182    typedef typename Graph::InEdgeIt GraphInEdgeIt;
183    //public:
184
185    class EdgeIt {
186      friend class UndirGraphWrapper<Graph>;
187      bool out_or_in; //true iff out
188      GraphOutEdgeIt out;
189      GraphInEdgeIt in;
190    public:
191      EdgeIt() : out_or_in(true), out(), in() { }
192      operator GraphEdgeIt() const {
193        if (out_or_in) return(out); else return(in);
194      }
195    };
196
197    class OutEdgeIt : public EdgeIt {
198      friend class UndirGraphWrapper<Graph>;
199      //bool out_or_in; //true iff out
200      //GraphOutEdgeIt out;
201      //GraphInEdgeIt in;
202    public:
203      OutEdgeIt() : EdgeIt() { }
204      OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
205        _G.graph->getFirst(out, n);
206        if (!(_G.graph->valid(out))) {
207          out_or_in=false;
208          _G.graph->getFirst(in, n);
209        }
210      }
211    };
212
213    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
214      e.out_or_in=true;
215      graph->getFirst(e.out, n);
216      if (!(graph->valid(e.out))) {
217        e.out_or_in=false;
218        graph->getFirst(e.in, n);
219      }
220      return e;
221    }
222
223    OutEdgeIt& next(OutEdgeIt& e) const {
224      if (e.out_or_in) {
225        NodeIt n=graph->tail(e.out);
226        graph->next(e.out);
227        if (!graph->valid(e.out)) {
228          e.out_or_in=false;
229          graph->getFirst(e.in, n);
230        }
231      } else {
232        graph->next(e.in);
233      }
234      return e;
235    }
236
237    NodeIt aNode(const OutEdgeIt& e) const {
238      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
239    NodeIt bNode(const OutEdgeIt& e) const {
240      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
241
242    typedef OutEdgeIt InEdgeIt;
243
244    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
245//     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
246//       return graph->getFirst(i, p); }
247   
248    template<typename I> I getNext(const I& i) const {
249      return graph->getNext(i); }
250    template<typename I> I& next(I &i) const { return graph->next(i); }   
251
252    template< typename It > It first() const {
253      It e; getFirst(e); return e; }
254
255    template< typename It > It first(const NodeIt& v) const {
256      It e; getFirst(e, v); return e; }
257
258    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
259    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
260
261    template<typename I> bool valid(const I& i) const
262      { return graph->valid(i); }
263 
264    //template<typename I> void setInvalid(const I &i);
265    //{ return graph->setInvalid(i); }
266
267    int nodeNum() const { return graph->nodeNum(); }
268    int edgeNum() const { return graph->edgeNum(); }
269 
270//     template<typename I> NodeIt aNode(const I& e) const {
271//       return graph->aNode(e); }
272//     template<typename I> NodeIt bNode(const I& e) const {
273//       return graph->bNode(e); }
274 
275    NodeIt addNode() const { return graph->addNode(); }
276    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
277      return graph->addEdge(tail, head); }
278 
279    template<typename I> void erase(const I& i) const { graph->erase(i); }
280 
281    void clear() const { graph->clear(); }
282   
283    template<typename T> class NodeMap : public Graph::NodeMap<T> {
284    public:
285      NodeMap(const UndirGraphWrapper<Graph>& _G) :
286        Graph::NodeMap<T>(_G.getGraph()) { }
287      NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
288        Graph::NodeMap<T>(_G.getGraph(), a) { }
289    };
290    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
291    public:
292      EdgeMap(const UndirGraphWrapper<Graph>& _G) :
293        Graph::EdgeMap<T>(_G.getGraph()) { }
294      EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
295        Graph::EdgeMap<T>(_G.getGraph(), a) { }
296    };
297   
298    void setGraph(Graph& _graph) { graph = &_graph; }
299    Graph& getGraph() const { return (*graph); }
300 
301    //TrivGraphWrapper() : graph(0) { }
302    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
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    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
390             const CapacityMap& _capacity) :
391      G(&_G), flow(&_flow), capacity(&_capacity) { }
392//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
393//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
394    void setGraph(Graph& _graph) { graph = &_graph; }
395    Graph& getGraph() const { return (*graph); }
396    class EdgeIt;
397    class OutEdgeIt;
398    friend class EdgeIt;
399    friend class OutEdgeIt;
400
401    class EdgeIt {
402      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
403    protected:
404      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
405      const Graph* G;
406      FlowMap* flow;
407      const CapacityMap* capacity;
408      //OldSymEdgeIt sym;
409      OldOutEdgeIt out;
410      OldInEdgeIt in;
411      bool out_or_in; //true, iff out
412    public:
413      EdgeIt() : out_or_in(true) { }
414      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
415        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
416      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
417      Number free() const {
418        if (out_or_in) {
419          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
420        } else {
421          return (/*resG->*/flow->get(in));
422        }
423      }
424      bool valid() const {
425        return out_or_in && out.valid() || in.valid(); }
426      void augment(Number a) const {
427        if (out_or_in) {
428          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
429        } else {
430          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
431        }
432      }
433      void print() {
434        if (out_or_in) {
435          std::cout << "out ";
436          if (out.valid())
437            std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
438          else
439            std::cout << "invalid";
440        }
441        else {
442          std::cout << "in ";
443          if (in.valid())
444            std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
445          else
446            std::cout << "invalid";
447        }
448        std::cout << std::endl;
449      }
450    };
451
452    Number free(OldOutEdgeIt out) const {
453      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
454    }
455    Number free(OldInEdgeIt in) const {
456      return (/*resG->*/flow->get(in));
457    }
458
459    class OutEdgeIt : public EdgeIt {
460      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
461    public:
462      OutEdgeIt() { }
463    private:
464      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
465        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
466        G->getFirst(out, v);
467        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
468        if (!out.valid()) {
469          out_or_in=0;
470          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
471          G->getFirst(in, v);
472          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
473        }
474      }
475    public:
476      OutEdgeIt& operator++() {
477        if (out_or_in) {
478          NodeIt v=/*resG->*/G->aNode(out);
479          ++out;
480          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
481          if (!out.valid()) {
482            out_or_in=0;
483            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
484            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
485          }
486        } else {
487          ++in;
488          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
489        }
490        return *this;
491      }
492    };
493
494    class EachEdgeIt : public EdgeIt {
495      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
496      typename Graph::EachNodeIt v;
497    public:
498      EachEdgeIt() { }
499      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
500      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
501        out_or_in=true;
502        G->getFirst(v);
503        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
504        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
505        while (v.valid() && !out.valid()) {
506          ++v;
507          if (v.valid()) G->getFirst(out, v);
508          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
509        }
510        if (!out.valid()) {
511          out_or_in=0;
512          G->getFirst(v);
513          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
514          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
515          while (v.valid() && !in.valid()) {
516            ++v;
517            if (v.valid()) G->getFirst(in, v);
518            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
519          }
520        }
521      }
522      EachEdgeIt& operator++() {
523        if (out_or_in) {
524          ++out;
525          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
526          while (v.valid() && !out.valid()) {
527            ++v;
528            if (v.valid()) G->getFirst(out, v);
529            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
530          }
531          if (!out.valid()) {
532            out_or_in=0;
533            G->getFirst(v);
534            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
535            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
536            while (v.valid() && !in.valid()) {
537              ++v;
538              if (v.valid()) G->getFirst(in, v);
539              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
540            } 
541          }
542        } else {
543          ++in;
544          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
545          while (v.valid() && !in.valid()) {
546            ++v;
547            if (v.valid()) G->getFirst(in, v);
548            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
549          }
550        }
551        return *this;
552      }
553    };
554
555    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
556    void getFirst(OutEdgeIt& e, NodeIt v) const {
557      e=OutEdgeIt(*G, v, *flow, *capacity);
558    }
559    void getFirst(EachEdgeIt& e) const {
560      e=EachEdgeIt(*G, *flow, *capacity);
561    }
562   
563    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
564
565    OutEdgeIt& next(OutEdgeIt& e) const {
566      if (e.out_or_in) {
567        NodeIt v=G->aNode(e.out);
568        ++(e.out);
569        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
570        if (!G->valid(e.out)) {
571          e.out_or_in=0;
572          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
573          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
574        }
575      } else {
576        ++(e.in);
577        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
578      }
579      return e;
580    }
581
582    EachEdgeIt& next(EachEdgeIt& e) const {
583      if (e.out_or_in) {
584        ++(e.out);
585        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
586          while (G->valid(e.v) && !G->valid(e.out)) {
587            ++(e.v);
588            if (G->valid(e.v)) G->getFirst(e.out, e.v);
589            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
590          }
591          if (!G->valid(e.out)) {
592            e.out_or_in=0;
593            G->getFirst(e.v);
594            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
595            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
596            while (G->valid(e.v) && !G->valid(e.in)) {
597              ++(e.v);
598              if (G->valid(e.v)) G->getFirst(e.in, e.v);
599              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
600            } 
601          }
602        } else {
603          ++(e.in);
604          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
605          while (G->valid(e.v) && !G->valid(e.in)) {
606            ++(e.v);
607            if (G->valid(e.v)) G->getFirst(e.in, e.v);
608            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
609          }
610        }
611        return e;
612      }
613   
614
615    template< typename It >
616    It first() const {
617      It e;
618      getFirst(e);
619      return e;
620    }
621
622    template< typename It >
623    It first(NodeIt v) const {
624      It e;
625      getFirst(e, v);
626      return e;
627    }
628
629    NodeIt tail(EdgeIt e) const {
630      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
631    NodeIt head(EdgeIt e) const {
632      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
633
634    NodeIt aNode(OutEdgeIt e) const {
635      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
636    NodeIt bNode(OutEdgeIt e) const {
637      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
638
639    int id(NodeIt v) const { return G->id(v); }
640
641    bool valid(NodeIt n) const { return G->valid(n); }
642    bool valid(EdgeIt e) const {
643      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
644
645    template<typename T> class NodeMap : public Graph::NodeMap<T> {
646    public:
647      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
648        : Graph::NodeMap<T>(_G.getGraph()) { }
649      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
650              T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
651    };
652
653//     template <typename T>
654//     class NodeMap {
655//       typename Graph::NodeMap<T> node_map;
656//     public:
657//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
658//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
659//       void set(NodeIt nit, T a) { node_map.set(nit, a); }
660//       T get(NodeIt nit) const { return node_map.get(nit); }
661//     };
662
663    template <typename T>
664    class EdgeMap {
665      typename Graph::EdgeMap<T> forward_map, backward_map;
666    public:
667      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
668      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
669      void set(EdgeIt e, T a) {
670        if (e.out_or_in)
671          forward_map.set(e.out, a);
672        else
673          backward_map.set(e.in, a);
674      }
675      T get(EdgeIt e) {
676        if (e.out_or_in)
677          return forward_map.get(e.out);
678        else
679          return backward_map.get(e.in);
680      }
681    };
682
683  };
684
685
686
687// // FIXME: comparison should be made better!!!
688//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
689//   class ResGraphWrapper
690//   {
691//     Graph* graph;
692 
693//   public:
694//     typedef Graph BaseGraph;
695
696//     typedef typename Graph::NodeIt NodeIt;
697//     typedef typename Graph::EdgeIt EdgeIt;
698 
699//     typedef typename Graph::EachNodeIt EachNodeIt;
700   
701//     class OutEdgeIt {
702//     public:
703//       //Graph::NodeIt n;
704//       bool out_or_in;
705//       typename Graph::OutEdgeIt o;
706//       typename Graph::InEdgeIt i;   
707//     };
708//     class InEdgeIt {
709//     public:
710//       //Graph::NodeIt n;
711//       bool out_or_in;
712//       typename Graph::OutEdgeIt o;
713//       typename Graph::InEdgeIt i;   
714//     };
715//     typedef typename Graph::SymEdgeIt SymEdgeIt;
716//     typedef typename Graph::EachEdgeIt EachEdgeIt;
717
718//     int nodeNum() const { return graph->nodeNum(); }
719//     int edgeNum() const { return graph->edgeNum(); }
720
721//     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
722
723//     // EachEdge and SymEdge  is missing!!!!
724//     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
725
726//     //FIXME
727//     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
728//       {
729//      e.n=n;
730//      graph->getFirst(e.o,n);
731//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
732//        graph->goNext(e.o);
733//      if(!graph->valid(e.o)) {
734//        graph->getFirst(e.i,n);
735//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
736//          graph->goNext(e.i);
737//      }
738//      return e;
739//       }
740// /*
741//   OutEdgeIt &goNext(OutEdgeIt &e)
742//   {
743//   if(graph->valid(e.o)) {
744//   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
745//   graph->goNext(e.o);
746//   if(graph->valid(e.o)) return e;
747//   else graph->getFirst(e.i,e.n);
748//   }
749//   else {
750//   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
751//   graph->goNext(e.i);
752//   return e;
753//   }
754//   }
755//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
756// */
757//     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
758
759//     //FIXME
760//     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
761//       {
762//      e.n=n;
763//      graph->getFirst(e.i,n);
764//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
765//        graph->goNext(e.i);
766//      if(!graph->valid(e.i)) {
767//        graph->getFirst(e.o,n);
768//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
769//          graph->goNext(e.o);
770//      }
771//      return e;
772//       }
773// /*
774//   InEdgeIt &goNext(InEdgeIt &e)
775//   {
776//   if(graph->valid(e.i)) {
777//   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
778//   graph->goNext(e.i);
779//   if(graph->valid(e.i)) return e;
780//   else graph->getFirst(e.o,e.n);
781//   }
782//   else {
783//   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
784//   graph->goNext(e.o);
785//   return e;
786//   }
787//   }
788//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
789// */
790//     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
791
792//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
793//     //template<typename I> I next(const I i); { return graph->goNext(i); }
794
795//     template< typename It > It first() const {
796//       It e; getFirst(e); return e; }
797
798//     template< typename It > It first(NodeIt v) const {
799//       It e; getFirst(e, v); return e; }
800
801//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
802//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
803 
804//     template<typename I> NodeIt aNode(const I& e) const {
805//       return graph->aNode(e); }
806//     template<typename I> NodeIt bNode(const I& e) const {
807//       return graph->bNode(e); }
808 
809//     //template<typename I> bool valid(const I i);
810//     //{ return graph->valid(i); }
811 
812//     //template<typename I> void setInvalid(const I &i);
813//     //{ return graph->setInvalid(i); }
814 
815//     NodeIt addNode() { return graph->addNode(); }
816//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
817//       return graph->addEdge(tail, head); }
818 
819//     template<typename I> void erase(const I& i) { graph->erase(i); }
820 
821//     void clear() { graph->clear(); }
822 
823//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
824//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
825 
826//     void setGraph(Graph& _graph) { graph = &_graph; }
827//     Graph& getGraph() { return (*graph); }
828
829//     //ResGraphWrapper() : graph(0) { }
830//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
831//   };
832
833} //namespace hugo
834
835#endif //GRAPH_WRAPPER_H
836
Note: See TracBrowser for help on using the repository browser.