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/experiment/graph_wrapper_1.h @ 281:3fefabfd00b7

Last change on this file since 281:3fefabfd00b7 was 281:3fefabfd00b7, checked in by marci, 20 years ago

One more experimental study about dereferation vs optimization
File size: 62.7 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_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    class NodeIt : public Graph::NodeIt {
19    public:
20      NodeIt() { }
21      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
22      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
23      NodeIt(const TrivGraphWrapper<Graph>& _G) :
24        Graph::NodeIt(*(_G.graph)) { }
25    };
26    typedef typename Graph::Edge Edge;
27    //typedef typename Graph::OutEdgeIt OutEdgeIt;
28    class OutEdgeIt : public Graph::OutEdgeIt {
29    public:
30      OutEdgeIt() { }
31      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
32      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
33      OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
34        Graph::OutEdgeIt(*(_G.graph), n) { }
35    };
36    //typedef typename Graph::InEdgeIt InEdgeIt;
37    class InEdgeIt : public Graph::InEdgeIt {
38    public:
39      InEdgeIt() { }
40      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
41      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
42      InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
43        Graph::InEdgeIt(*(_G.graph), n) { }
44    };
45    //typedef typename Graph::SymEdgeIt SymEdgeIt;
46    //typedef typename Graph::EdgeIt EdgeIt;
47    class EdgeIt : public Graph::EdgeIt {
48    public:
49      EdgeIt() { }
50      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
51      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
52      EdgeIt(const TrivGraphWrapper<Graph>& _G) :
53        Graph::EdgeIt(*(_G.graph)) { }
54    };
55
56    //TrivGraphWrapper() : graph(0) { }
57    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
58
59//    void setGraph(Graph& _graph) { graph = &_graph; }
60//    Graph& getGraph() const { return (*graph); }
61
62    NodeIt& first(NodeIt& i) const {
63      i=NodeIt(*this);
64      return i;
65    }
66    EdgeIt& first(EdgeIt& i) const {
67      i=EdgeIt(*this);
68      return i;
69    }
70//     template<typename I> I& first(I& i) const {
71//       //return graph->first(i);
72//       i=I(*this);
73//       return i;
74//     }
75    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
76      i=OutEdgeIt(*this, p);
77      return i;
78    }
79    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
80      i=InEdgeIt(*this, p);
81      return i;
82    }
83//     template<typename I, typename P> I& first(I& i, const P& p) const {
84//       //return graph->first(i, p);
85//       i=I(*this, p);
86//       return i;
87//     }
88   
89//    template<typename I> I getNext(const I& i) const {
90//      return graph->getNext(i); }
91    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
92
93    template< typename It > It first() const {
94      It e; first(e); return e; }
95
96    template< typename It > It first(const Node& v) const {
97      It e; first(e, v); return e; }
98
99    Node head(const Edge& e) const { return graph->head(e); }
100    Node tail(const Edge& e) const { return graph->tail(e); }
101
102    template<typename I> bool valid(const I& i) const
103      { return graph->valid(i); }
104 
105    //template<typename I> void setInvalid(const I &i);
106    //{ return graph->setInvalid(i); }
107
108    int nodeNum() const { return graph->nodeNum(); }
109    int edgeNum() const { return graph->edgeNum(); }
110 
111    template<typename I> Node aNode(const I& e) const {
112      return graph->aNode(e); }
113    template<typename I> Node bNode(const I& e) const {
114      return graph->bNode(e); }
115 
116    Node addNode() const { return graph->addNode(); }
117    Edge addEdge(const Node& tail, const Node& head) const {
118      return graph->addEdge(tail, head); }
119 
120    template<typename I> void erase(const I& i) const { graph->erase(i); }
121 
122    void clear() const { graph->clear(); }
123   
124    template<typename T> class NodeMap : public Graph::NodeMap<T> {
125    public:
126      NodeMap(const TrivGraphWrapper<Graph>& _G) : 
127        Graph::NodeMap<T>(*(_G.graph)) { }
128      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
129        Graph::NodeMap<T>(*(_G.graph), a) { }
130    };
131
132    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
133    public:
134      EdgeMap(const TrivGraphWrapper<Graph>& _G) : 
135        Graph::EdgeMap<T>(*(_G.graph)) { }
136      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
137        Graph::EdgeMap<T>(*(_G.graph), a) { }
138    };
139
140    template<typename Map, typename T> class NodeMapWrapper {
141    protected:
142      Map* map;
143    public:
144      NodeMapWrapper(Map& _map) : map(&_map) { }
145      //template<typename T>
146      void set(Node n, T a) { map->set(n, a); }
147      //template<typename T>
148      T get(Node n) const { return map->get(n); }
149    };
150
151    template<typename Map, typename T> class EdgeMapWrapper {
152    protected:
153      Map* map;
154    public:
155      EdgeMapWrapper(Map& _map) : map(&_map) { }
156      //template<typename T>
157      void set(Edge n, T a) { map->set(n, a); }
158      //template<typename T>
159      T get(Edge n) const { return map->get(n); }
160    };
161  };
162
163  template<typename GraphWrapper>
164  class GraphWrapperSkeleton {
165  protected:
166    GraphWrapper gw;
167 
168  public:
169    //typedef typename GraphWrapper::BaseGraph BaseGraph;
170
171//     typedef typename GraphWrapper::Node Node;
172//     typedef typename GraphWrapper::NodeIt NodeIt;
173
174//     typedef typename GraphWrapper::Edge Edge;
175//     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
176//     typedef typename GraphWrapper::InEdgeIt InEdgeIt;
177//     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
178//     typedef typename GraphWrapper::EdgeIt EdgeIt;
179
180    typedef typename GraphWrapper::Node Node;
181    class NodeIt : public GraphWrapper::NodeIt {
182    public:
183      NodeIt() { }
184      NodeIt(const typename GraphWrapper::NodeIt& n) :
185        GraphWrapper::NodeIt(n) { }
186      NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
187      NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
188        GraphWrapper::NodeIt(_G.gw) { }
189    };
190    typedef typename GraphWrapper::Edge Edge;
191    //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
192    class OutEdgeIt : public GraphWrapper::OutEdgeIt {
193    public:
194      OutEdgeIt() { }
195      OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
196        GraphWrapper::OutEdgeIt(e) { }
197      OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
198      OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
199        GraphWrapper::OutEdgeIt(_G.gw, n) { }
200    };
201    //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
202    class InEdgeIt : public GraphWrapper::InEdgeIt {
203    public:
204      InEdgeIt() { }
205      InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
206        GraphWrapper::InEdgeIt(e) { }
207      InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
208      InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
209        GraphWrapper::InEdgeIt(_G.gw, n) { }
210    };
211    //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
212    //typedef typename GraphWrapper::EdgeIt EdgeIt;
213    class EdgeIt : public GraphWrapper::EdgeIt {
214    public:
215      EdgeIt() { }
216      EdgeIt(const typename GraphWrapper::EdgeIt& e) :
217        GraphWrapper::EdgeIt(e) { }
218      EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
219      EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
220        GraphWrapper::EdgeIt(_G.gw) { }
221    };
222
223
224    //GraphWrapperSkeleton() : gw() { }
225    GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
226
227    //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
228    //BaseGraph& getGraph() const { return gw.getGraph(); }
229   
230    template<typename I> I& first(I& i) const {       
231      i=I(*this);
232      return i;
233    }
234    template<typename I, typename P> I& first(I& i, const P& p) const {
235      i=I(*this, p);
236      return i;
237    }
238   
239//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
240    template<typename I> I& next(I &i) const { gw.next(i); return i; }   
241
242    template< typename It > It first() const {
243      It e; this->first(e); return e; }
244
245    template< typename It > It first(const Node& v) const {
246      It e; this->first(e, v); return e; }
247
248    Node head(const Edge& e) const { return gw.head(e); }
249    Node tail(const Edge& e) const { return gw.tail(e); }
250
251    template<typename I> bool valid(const I& i) const { return gw.valid(i); }
252 
253    //template<typename I> void setInvalid(const I &i);
254    //{ return graph->setInvalid(i); }
255
256    int nodeNum() const { return gw.nodeNum(); }
257    int edgeNum() const { return gw.edgeNum(); }
258 
259    template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
260    template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
261 
262    Node addNode() const { return gw.addNode(); }
263    Edge addEdge(const Node& tail, const Node& head) const {
264      return gw.addEdge(tail, head); }
265 
266    template<typename I> void erase(const I& i) const { gw.erase(i); }
267 
268    void clear() const { gw.clear(); }
269   
270    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
271    public:
272      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 
273        GraphWrapper::NodeMap<T>(_G.gw) { }
274      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
275        GraphWrapper::NodeMap<T>(_G.gw, a) { }
276    };
277
278    template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
279    public:
280      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 
281        GraphWrapper::EdgeMap<T>(_G.gw) { }
282      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
283        GraphWrapper::EdgeMap<T>(_G.gw, a) { }
284    };
285  };
286
287  template<typename GraphWrapper>
288  class GraphWrapperSkeleton1 {
289  protected:
290    GraphWrapper* g;
291 
292  public:
293    //typedef typename GraphWrapper::BaseGraph BaseGraph;
294
295//     typedef typename GraphWrapper::Node Node;
296//     typedef typename GraphWrapper::NodeIt NodeIt;
297
298//     typedef typename GraphWrapper::Edge Edge;
299//     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
300//     typedef typename GraphWrapper::InEdgeIt InEdgeIt;
301//     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
302//     typedef typename GraphWrapper::EdgeIt EdgeIt;
303
304    typedef typename GraphWrapper::Node Node;
305    class NodeIt : public GraphWrapper::NodeIt {
306    public:
307      NodeIt() { }
308      NodeIt(const typename GraphWrapper::NodeIt& n) :
309        GraphWrapper::NodeIt(n) { }
310      NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
311      NodeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) :
312        GraphWrapper::NodeIt(*(_G.g)) { }
313    };
314    typedef typename GraphWrapper::Edge Edge;
315    //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
316    class OutEdgeIt : public GraphWrapper::OutEdgeIt {
317    public:
318      OutEdgeIt() { }
319      OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
320        GraphWrapper::OutEdgeIt(e) { }
321      OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
322      OutEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) :
323        GraphWrapper::OutEdgeIt(*(_G.g), n) { }
324    };
325    //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
326    class InEdgeIt : public GraphWrapper::InEdgeIt {
327    public:
328      InEdgeIt() { }
329      InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
330        GraphWrapper::InEdgeIt(e) { }
331      InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
332      InEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) :
333        GraphWrapper::InEdgeIt(*(_G.g), n) { }
334    };
335    //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
336    //typedef typename GraphWrapper::EdgeIt EdgeIt;
337    class EdgeIt : public GraphWrapper::EdgeIt {
338    public:
339      EdgeIt() { }
340      EdgeIt(const typename GraphWrapper::EdgeIt& e) :
341        GraphWrapper::EdgeIt(e) { }
342      EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
343      EdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) :
344        GraphWrapper::EdgeIt(*(_G.g)) { }
345    };
346
347
348    //GraphWrapperSkeleton() : gw() { }
349    GraphWrapperSkeleton1(GraphWrapper& _gw) : g(&_gw) { }
350
351    //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
352    //BaseGraph& getGraph() const { return gw.getGraph(); }
353   
354    template<typename I> I& first(I& i) const {       
355      i=I(*this);
356      return i;
357    }
358    template<typename I, typename P> I& first(I& i, const P& p) const {
359      i=I(*this, p);
360      return i;
361    }
362   
363//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
364    template<typename I> I& next(I &i) const { g->next(i); return i; }   
365
366    template< typename It > It first() const {
367      It e; this->first(e); return e; }
368
369    template< typename It > It first(const Node& v) const {
370      It e; this->first(e, v); return e; }
371
372    Node head(const Edge& e) const { return g->head(e); }
373    Node tail(const Edge& e) const { return g->tail(e); }
374
375    template<typename I> bool valid(const I& i) const { return g->valid(i); }
376 
377    //template<typename I> void setInvalid(const I &i);
378    //{ return graph->setInvalid(i); }
379
380    int nodeNum() const { return g->nodeNum(); }
381    int edgeNum() const { return g->edgeNum(); }
382 
383    template<typename I> Node aNode(const I& e) const { return g->aNode(e); }
384    template<typename I> Node bNode(const I& e) const { return g->bNode(e); }
385 
386    Node addNode() const { return g->addNode(); }
387    Edge addEdge(const Node& tail, const Node& head) const {
388      return g->addEdge(tail, head); }
389 
390    template<typename I> void erase(const I& i) const { g->erase(i); }
391 
392    void clear() const { g->clear(); }
393   
394    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
395    public:
396      NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) : 
397        GraphWrapper::NodeMap<T>(*(_G.g)) { }
398      NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) :
399        GraphWrapper::NodeMap<T>(*(_G.g), a) { }
400    };
401
402    template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
403    public:
404      EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) : 
405        GraphWrapper::EdgeMap<T>(*(_G.g)) { }
406      EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) :
407        GraphWrapper::EdgeMap<T>(*(_G.g), a) { }
408    };
409  };
410
411
412//   template<typename Graph>
413//   class RevGraphWrapper
414//   {
415//   protected:
416//     Graph* graph;
417 
418//   public:
419//     typedef Graph BaseGraph;
420
421//     typedef typename Graph::Node Node;   
422//     typedef typename Graph::NodeIt NodeIt;
423 
424//     typedef typename Graph::Edge Edge;
425//     typedef typename Graph::OutEdgeIt InEdgeIt;
426//     typedef typename Graph::InEdgeIt OutEdgeIt;
427//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
428//     typedef typename Graph::EdgeIt EdgeIt;
429
430//     //RevGraphWrapper() : graph(0) { }
431//     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
432
433//     void setGraph(Graph& _graph) { graph = &_graph; }
434//     Graph& getGraph() const { return (*graph); }
435   
436//     template<typename I> I& first(I& i) const { return graph->first(i); }
437//     template<typename I, typename P> I& first(I& i, const P& p) const {
438//       return graph->first(i, p); }
439
440//     template<typename I> I getNext(const I& i) const {
441//       return graph->getNext(i); }
442//     template<typename I> I& next(I &i) const { return graph->next(i); }   
443
444//     template< typename It > It first() const {
445//       It e; first(e); return e; }
446
447//     template< typename It > It first(const Node& v) const {
448//       It e; first(e, v); return e; }
449
450//     Node head(const Edge& e) const { return graph->tail(e); }
451//     Node tail(const Edge& e) const { return graph->head(e); }
452 
453//     template<typename I> bool valid(const I& i) const
454//       { return graph->valid(i); }
455 
456//     //template<typename I> void setInvalid(const I &i);
457//     //{ return graph->setInvalid(i); }
458 
459//     template<typename I> Node aNode(const I& e) const {
460//       return graph->aNode(e); }
461//     template<typename I> Node bNode(const I& e) const {
462//       return graph->bNode(e); }
463
464//     Node addNode() const { return graph->addNode(); }
465//     Edge addEdge(const Node& tail, const Node& head) const {
466//       return graph->addEdge(tail, head); }
467 
468//     int nodeNum() const { return graph->nodeNum(); }
469//     int edgeNum() const { return graph->edgeNum(); }
470 
471//     template<typename I> void erase(const I& i) const { graph->erase(i); }
472 
473//     void clear() const { graph->clear(); }
474
475//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
476//     public:
477//       NodeMap(const RevGraphWrapper<Graph>& _G) :
478//      Graph::NodeMap<T>(_G.getGraph()) { }
479//       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
480//      Graph::NodeMap<T>(_G.getGraph(), a) { }
481//     };
482
483//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
484//     public:
485//       EdgeMap(const RevGraphWrapper<Graph>& _G) :
486//      Graph::EdgeMap<T>(_G.getGraph()) { }
487//       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
488//      Graph::EdgeMap<T>(_G.getGraph(), a) { }
489//     };
490//   };
491
492//   template<typename /*Graph*/GraphWrapper
493//   /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
494//   class RevGraphWrapper :
495//     public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
496//   protected:
497//     //Graph* graph;
498   
499//   public:
500//     //typedef Graph BaseGraph;
501
502//     //typedef typename Graph::Node Node;   
503//     //typedef typename Graph::NodeIt NodeIt;
504 
505//     //typedef typename Graph::Edge Edge;
506//     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
507//     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
508//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
509//     //typedef typename Graph::EdgeIt EdgeIt;
510
511//     //RevGraphWrapper() : graph(0) { }
512//     RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
513   
514//     //void setGraph(Graph& _graph) { graph = &_graph; }
515//     //Graph& getGraph() const { return (*graph); }
516   
517//     //template<typename I> I& first(I& i) const { return graph->first(i); }
518//     //template<typename I, typename P> I& first(I& i, const P& p) const {
519//     //  return graph->first(i, p); }
520
521//     //template<typename I> I getNext(const I& i) const {
522//     //  return graph->getNext(i); }
523//     //template<typename I> I& next(I &i) const { return graph->next(i); }   
524
525//     //template< typename It > It first() const {
526//     //  It e; first(e); return e; }
527
528//     //template< typename It > It first(const Node& v) const {
529//     //  It e; first(e, v); return e; }
530
531//     //Node head(const Edge& e) const { return graph->tail(e); }
532//     //Node tail(const Edge& e) const { return graph->head(e); }
533 
534//     //template<typename I> bool valid(const I& i) const
535//     //  { return graph->valid(i); }
536 
537//     //template<typename I> void setInvalid(const I &i);
538//     //{ return graph->setInvalid(i); }
539 
540//     //template<typename I> Node aNode(const I& e) const {
541//     //  return graph->aNode(e); }
542//     //template<typename I> Node bNode(const I& e) const {
543//     //  return graph->bNode(e); }
544
545//     //Node addNode() const { return graph->addNode(); }
546//     //Edge addEdge(const Node& tail, const Node& head) const {
547//     //  return graph->addEdge(tail, head); }
548 
549//     //int nodeNum() const { return graph->nodeNum(); }
550//     //int edgeNum() const { return graph->edgeNum(); }
551 
552//     //template<typename I> void erase(const I& i) const { graph->erase(i); }
553 
554//     //void clear() const { graph->clear(); }
555
556//     template<typename T> class NodeMap :
557//       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
558//     {
559//     public:
560//       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
561//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
562//       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
563//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
564//     };
565   
566//     template<typename T> class EdgeMap :
567//       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
568//     public:
569//       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
570//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
571//       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
572//      GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
573//     };
574//   };
575
576  template<typename GraphWrapper>
577  class RevGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
578  public:
579    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
580    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;
581    //FIXME
582    //If GraphWrapper::OutEdgeIt is not defined
583    //and we do not want to use RevGraphWrapper::InEdgeIt,
584    //this won't work, because of typedef
585    //OR
586    //graphs have to define their non-existing iterators to void
587    //Unfortunately all the typedefs are instantiated in templates,
588    //unlike other stuff
589    typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt InEdgeIt;
590    typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt OutEdgeIt;
591
592    RevGraphWrapper(GraphWrapper& _gw) :
593      GraphWrapperSkeleton1<GraphWrapper>(_gw) { } 
594
595    Node head(const Edge& e) const
596      { return GraphWrapperSkeleton1<GraphWrapper>::tail(e); }
597    Node tail(const Edge& e) const
598      { return GraphWrapperSkeleton1<GraphWrapper>::head(e); }
599  };
600
601  //Subgraph on the same node-set and partial edge-set
602  template<typename GraphWrapper, typename EdgeFilterMap>
603  class SubGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
604  protected:
605    EdgeFilterMap* filter_map;
606  public:
607    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
608    typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
609    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;
610    typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt;
611    typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt;
612    typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt;
613
614    SubGraphWrapper(GraphWrapper& _gw, EdgeFilterMap& _filter_map) :
615      GraphWrapperSkeleton1<GraphWrapper>(_gw), filter_map(&_filter_map) { } 
616
617    template<typename I> I& first(I& i) const {
618      g->first(i);
619      while (g->valid(i) && !filter_map->get(i)) { g->next(i); }
620      return i;
621    }
622    template<typename I, typename P> I& first(I& i, const P& p) const {
623      g->first(i, p);
624      while (g->valid(i) && !filter_map->get(i)) { g->next(i); }
625      return i;
626    }
627   
628    //template<typename I> I getNext(const I& i) const {
629    //  return gw.getNext(i);
630    //}
631    template<typename I> I& next(I &i) const {
632      g->next(i);
633      while (g->valid(i) && !filter_map->get(i)) { g->next(i); }
634      return i;
635    }
636   
637    template< typename It > It first() const {
638      It e; this->first(e); return e; }
639   
640    template< typename It > It first(const Node& v) const {
641      It e; this->first(e, v); return e; }
642  };
643
644//   template<typename GraphWrapper>
645//   class UndirGraphWrapper {
646//   protected:
647//     //Graph* graph;
648//     GraphWrapper gw;
649
650//   public:
651//     typedef GraphWrapper BaseGraph;
652
653//     typedef typename GraphWrapper::Node Node;
654//     typedef typename GraphWrapper::NodeIt NodeIt;
655
656//     //typedef typename Graph::Edge Edge;
657//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
658//     //typedef typename Graph::InEdgeIt InEdgeIt;
659//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
660//     //typedef typename Graph::EdgeIt EdgeIt;
661
662//     //private:
663//     typedef typename GraphWrapper::Edge GraphEdge;
664//     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
665//     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
666//     //public:
667
668//     //UndirGraphWrapper() : graph(0) { }
669//     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
670
671//     //void setGraph(Graph& _graph) { graph = &_graph; }
672//     //Graph& getGraph() const { return (*graph); }
673 
674//     class Edge {
675//       friend class UndirGraphWrapper<GraphWrapper>;
676//       bool out_or_in; //true iff out
677//       GraphOutEdgeIt out;
678//       GraphInEdgeIt in;
679//     public:
680//       Edge() : out_or_in(), out(), in() { }
681//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
682//       operator GraphEdge() const {
683//      if (out_or_in) return(out); else return(in);
684//       }
685//       friend bool operator==(const Edge& u, const Edge& v) {
686//      if (v.out_or_in)
687//        return (u.out_or_in && u.out==v.out);
688//      else
689//        return (!u.out_or_in && u.in==v.in);
690//       }
691//       friend bool operator!=(const Edge& u, const Edge& v) {
692//      if (v.out_or_in)
693//        return (!u.out_or_in || u.out!=v.out);
694//      else
695//        return (u.out_or_in || u.in!=v.in);
696//       }
697//     };
698
699//     class OutEdgeIt : public Edge {
700//       friend class UndirGraphWrapper<GraphWrapper>;
701//     public:
702//       OutEdgeIt() : Edge() { }
703//       OutEdgeIt(const Invalid& i) : Edge(i) { }
704//       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
705//      : Edge() {
706//      out_or_in=true;
707//      _G.gw.first(out, n);
708//      if (!(_G.gw.valid(out))) {
709//        out_or_in=false;
710//        _G.gw.first(in, n);
711//      }
712//       }
713//     };
714
715//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
716//       e.out_or_in=true;
717//       gw.first(e.out, n);
718//       if (!(gw.valid(e.out))) {
719//      e.out_or_in=false;
720//      gw.first(e.in, n);
721//       }
722//       return e;
723//     }
724
725//     OutEdgeIt& next(OutEdgeIt& e) const {
726//       if (e.out_or_in) {
727//      Node n=gw.tail(e.out);
728//      gw.next(e.out);
729//      if (!gw.valid(e.out)) {
730//        e.out_or_in=false;
731//        gw.first(e.in, n);
732//      }
733//       } else {
734//      gw.next(e.in);
735//       }
736//       return e;
737//     }
738
739//     Node aNode(const OutEdgeIt& e) const {
740//       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
741//     Node bNode(const OutEdgeIt& e) const {
742//       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
743
744//     typedef OutEdgeIt InEdgeIt;
745
746//     template<typename I> I& first(I& i) const { return gw.first(i); }
747// //     template<typename I, typename P> I& first(I& i, const P& p) const {
748// //       return graph->first(i, p); }
749   
750//     template<typename I> I getNext(const I& i) const {
751//       return gw.getNext(i); }
752//     template<typename I> I& next(I &i) const { return gw.next(i); }   
753
754//     template< typename It > It first() const {
755//       It e; first(e); return e; }
756
757//     template< typename It > It first(const Node& v) const {
758//       It e; first(e, v); return e; }
759
760//     Node head(const Edge& e) const { return gw.head(e); }
761//     Node tail(const Edge& e) const { return gw.tail(e); }
762
763//     template<typename I> bool valid(const I& i) const
764//       { return gw.valid(i); }
765 
766//     //template<typename I> void setInvalid(const I &i);
767//     //{ return graph->setInvalid(i); }
768
769//     int nodeNum() const { return gw.nodeNum(); }
770//     int edgeNum() const { return gw.edgeNum(); }
771 
772// //     template<typename I> Node aNode(const I& e) const {
773// //       return graph->aNode(e); }
774// //     template<typename I> Node bNode(const I& e) const {
775// //       return graph->bNode(e); }
776 
777//     Node addNode() const { return gw.addNode(); }
778// // FIXME: ez igy nem jo, mert nem
779// //    Edge addEdge(const Node& tail, const Node& head) const {
780// //      return graph->addEdge(tail, head); }
781 
782//     template<typename I> void erase(const I& i) const { gw.erase(i); }
783 
784//     void clear() const { gw.clear(); }
785   
786//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
787//     public:
788//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
789//      GraphWrapper::NodeMap<T>(_G.gw) { }
790//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
791//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
792//     };
793
794//     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
795//     public:
796//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
797//      GraphWrapper::EdgeMap<T>(_G.gw) { }
798//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
799//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
800//     };
801//   };
802
803
804  template<typename GraphWrapper>
805  class UndirGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
806  protected:
807//    GraphWrapper gw;
808
809  public:
810    //typedef GraphWrapper BaseGraph;
811
812    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
813    typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
814
815    //private:
816    //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
817    //legyenek, at kell irni
818    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
819    GraphWrapper::Edge GraphEdge;
820    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
821    GraphWrapper::OutEdgeIt GraphOutEdgeIt;
822    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
823    GraphWrapper::InEdgeIt GraphInEdgeIt;
824    //public:
825
826    //UndirGraphWrapper() : graph(0) { }
827    UndirGraphWrapper(GraphWrapper& _gw) :
828      GraphWrapperSkeleton1<GraphWrapper>(_gw) { } 
829
830    //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
831
832    //void setGraph(Graph& _graph) { graph = &_graph; }
833    //Graph& getGraph() const { return (*graph); }
834 
835    class Edge {
836      friend class UndirGraphWrapper<GraphWrapper>;
837    protected:
838      bool out_or_in; //true iff out
839      GraphOutEdgeIt out;
840      GraphInEdgeIt in;
841    public:
842      Edge() : out_or_in(), out(), in() { }
843      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
844      operator GraphEdge() const {
845        if (out_or_in) return(out); else return(in);
846      }
847//FIXME
848//2 edges are equal if they "refer" to the same physical edge
849//is it good?
850      friend bool operator==(const Edge& u, const Edge& v) {
851        if (v.out_or_in)
852          if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
853        //return (u.out_or_in && u.out==v.out);
854        else
855          if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
856        //return (!u.out_or_in && u.in==v.in);
857      }
858      friend bool operator!=(const Edge& u, const Edge& v) {
859        if (v.out_or_in)
860          if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
861        //return (!u.out_or_in || u.out!=v.out);
862        else
863          if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
864        //return (u.out_or_in || u.in!=v.in);
865      }
866    };
867
868    class OutEdgeIt : public Edge {
869      friend class UndirGraphWrapper<GraphWrapper>;
870    public:
871      OutEdgeIt() : Edge() { }
872      OutEdgeIt(const Invalid& i) : Edge(i) { }
873      OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
874        : Edge() {
875        out_or_in=true; _G.g->first(out, n);
876        if (!(_G.g->valid(out))) { out_or_in=false; _G.g->first(in, n); }
877      }
878    };
879
880    typedef OutEdgeIt InEdgeIt;
881
882    class EdgeIt : public Edge {
883      friend class UndirGraphWrapper<GraphWrapper>;
884    protected:
885      NodeIt v;
886    public:
887      EdgeIt() : Edge() { }
888      EdgeIt(const Invalid& i) : Edge(i) { }
889      EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
890        : Edge() {
891        out_or_in=true;
892        //Node v;
893        _G.first(v);
894        if (_G.valid(v)) _G.g->first(out); else out=INVALID;
895        while (_G.valid(v) && !_G.g->valid(out)) {
896          _G.g->next(v);
897          if (_G.valid(v)) _G.g->first(out);
898        }
899      }
900    };
901
902    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
903      e.out_or_in=true; g->first(e.out, n);
904      if (!(g->valid(e.out))) { e.out_or_in=false; g->first(e.in, n); }
905      return e;
906    }
907
908    EdgeIt& first(EdgeIt& e) const {
909      e.out_or_in=true;
910      //NodeIt v;
911      first(e.v);
912      if (valid(e.v)) g->first(e.out, e.v); else e.out=INVALID;
913      while (valid(e.v) && !g->valid(e.out)) {
914        g->next(e.v);
915        if (valid(e.v)) g->first(e.out, e.v);
916      }
917      return e;
918    }
919
920    template<typename I> I& first(I& i) const { g->first(i); return i; }
921    template<typename I, typename P> I& first(I& i, const P& p) const {
922      g->first(i, p); return i; }
923
924    OutEdgeIt& next(OutEdgeIt& e) const {
925      if (e.out_or_in) {
926        Node n=g->tail(e.out);
927        g->next(e.out);
928        if (!g->valid(e.out)) { e.out_or_in=false; g->first(e.in, n); }
929      } else {
930        g->next(e.in);
931      }
932      return e;
933    }
934
935    EdgeIt& next(EdgeIt& e) const {
936      //NodeIt v=tail(e);
937      g->next(e.out);
938      while (valid(e.v) && !g->valid(e.out)) {
939        next(e.v);
940        if (valid(e.v)) g->first(e.out, e.v);
941      }
942      return e;
943    }
944
945    template<typename I> I& next(I &i) const { return g->next(i); }   
946//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
947
948    template< typename It > It first() const {
949      It e; first(e); return e; }
950
951    template< typename It > It first(const Node& v) const {
952      It e; first(e, v); return e; }
953
954//    Node head(const Edge& e) const { return gw.head(e); }
955//    Node tail(const Edge& e) const { return gw.tail(e); }
956
957//    template<typename I> bool valid(const I& i) const
958//      { return gw.valid(i); }
959 
960//    int nodeNum() const { return gw.nodeNum(); }
961//    int edgeNum() const { return gw.edgeNum(); }
962 
963//     template<typename I> Node aNode(const I& e) const {
964//       return graph->aNode(e); }
965//     template<typename I> Node bNode(const I& e) const {
966//       return graph->bNode(e); }
967
968    Node aNode(const OutEdgeIt& e) const {
969      if (e.out_or_in) return g->tail(e); else return g->head(e); }
970    Node bNode(const OutEdgeIt& e) const {
971      if (e.out_or_in) return g->head(e); else return g->tail(e); }
972 
973//    Node addNode() const { return gw.addNode(); }
974
975// FIXME: ez igy nem jo, mert nem
976//    Edge addEdge(const Node& tail, const Node& head) const {
977//      return graph->addEdge(tail, head); }
978 
979//    template<typename I> void erase(const I& i) const { gw.erase(i); }
980 
981//    void clear() const { gw.clear(); }
982   
983//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
984//     public:
985//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
986//      GraphWrapper::NodeMap<T>(_G.gw) { }
987//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
988//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
989//     };
990
991//     template<typename T> class EdgeMap :
992//       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
993//     public:
994//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
995//      GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
996//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
997//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
998//     };
999   };
1000
1001
1002
1003
1004
1005//   template<typename Graph>
1006//   class SymGraphWrapper
1007//   {
1008//     Graph* graph;
1009 
1010//   public:
1011//     typedef Graph BaseGraph;
1012
1013//     typedef typename Graph::Node Node;
1014//     typedef typename Graph::Edge Edge;
1015 
1016//     typedef typename Graph::NodeIt NodeIt;
1017   
1018//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1019//     //iranyitatlant, ami van
1020//     //mert csak 1 dolgot lehet be typedef-elni
1021//     typedef typename Graph::OutEdgeIt SymEdgeIt;
1022//     //typedef typename Graph::InEdgeIt SymEdgeIt;
1023//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1024//     typedef typename Graph::EdgeIt EdgeIt;
1025
1026//     int nodeNum() const { return graph->nodeNum(); }
1027//     int edgeNum() const { return graph->edgeNum(); }
1028   
1029//     template<typename I> I& first(I& i) const { return graph->first(i); }
1030//     template<typename I, typename P> I& first(I& i, const P& p) const {
1031//       return graph->first(i, p); }
1032//     //template<typename I> I next(const I i); { return graph->goNext(i); }
1033//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1034
1035//     template< typename It > It first() const {
1036//       It e; first(e); return e; }
1037
1038//     template< typename It > It first(Node v) const {
1039//       It e; first(e, v); return e; }
1040
1041//     Node head(const Edge& e) const { return graph->head(e); }
1042//     Node tail(const Edge& e) const { return graph->tail(e); }
1043 
1044//     template<typename I> Node aNode(const I& e) const {
1045//       return graph->aNode(e); }
1046//     template<typename I> Node bNode(const I& e) const {
1047//       return graph->bNode(e); }
1048 
1049//     //template<typename I> bool valid(const I i);
1050//     //{ return graph->valid(i); }
1051 
1052//     //template<typename I> void setInvalid(const I &i);
1053//     //{ return graph->setInvalid(i); }
1054 
1055//     Node addNode() { return graph->addNode(); }
1056//     Edge addEdge(const Node& tail, const Node& head) {
1057//       return graph->addEdge(tail, head); }
1058 
1059//     template<typename I> void erase(const I& i) { graph->erase(i); }
1060 
1061//     void clear() { graph->clear(); }
1062 
1063//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1064//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1065 
1066//     void setGraph(Graph& _graph) { graph = &_graph; }
1067//     Graph& getGraph() { return (*graph); }
1068
1069//     //SymGraphWrapper() : graph(0) { }
1070//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1071//   };
1072
1073
1074  template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
1075  class ResGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper>{
1076  public:
1077    //typedef Graph BaseGraph;
1078    //typedef TrivGraphWrapper<const Graph> GraphWrapper;
1079    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
1080    typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
1081  private:
1082    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1083    GraphWrapper::OutEdgeIt OldOutEdgeIt;
1084    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1085    GraphWrapper::InEdgeIt OldInEdgeIt;
1086  protected:
1087    //const Graph* graph;
1088    //GraphWrapper gw;
1089    FlowMap* flow;
1090    const CapacityMap* capacity;
1091  public:
1092
1093    ResGraphWrapper(GraphWrapper& _gw, FlowMap& _flow,
1094                    const CapacityMap& _capacity) :
1095      GraphWrapperSkeleton1<GraphWrapper>(_gw),
1096      flow(&_flow), capacity(&_capacity) { }
1097
1098    //void setGraph(const Graph& _graph) { graph = &_graph; }
1099    //const Graph& getGraph() const { return (*graph); }
1100
1101    class Edge;
1102    class OutEdgeIt;
1103    friend class Edge;
1104    friend class OutEdgeIt;
1105
1106    class Edge {
1107      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1108    protected:
1109      bool out_or_in; //true, iff out
1110      OldOutEdgeIt out;
1111      OldInEdgeIt in;
1112    public:
1113      Edge() : out_or_in(true) { }
1114      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1115//       bool valid() const {
1116//      return out_or_in && out.valid() || in.valid(); }
1117      friend bool operator==(const Edge& u, const Edge& v) {
1118        if (v.out_or_in)
1119          return (u.out_or_in && u.out==v.out);
1120        else
1121          return (!u.out_or_in && u.in==v.in);
1122      }
1123      friend bool operator!=(const Edge& u, const Edge& v) {
1124        if (v.out_or_in)
1125          return (!u.out_or_in || u.out!=v.out);
1126        else
1127          return (u.out_or_in || u.in!=v.in);
1128      }
1129    };
1130
1131
1132    class OutEdgeIt : public Edge {
1133      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1134    public:
1135      OutEdgeIt() { }
1136      //FIXME
1137      OutEdgeIt(const Edge& e) : Edge(e) { }
1138      OutEdgeIt(const Invalid& i) : Edge(i) { }
1139    protected:
1140      OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1141        resG.g->first(out, v);
1142        while( resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }
1143        if (!resG.g->valid(out)) {
1144          out_or_in=0;
1145          resG.g->first(in, v);
1146          while( resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }
1147        }
1148      }
1149//     public:
1150//       OutEdgeIt& operator++() {
1151//      if (out_or_in) {
1152//        Node v=/*resG->*/G->aNode(out);
1153//        ++out;
1154//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1155//        if (!out.valid()) {
1156//          out_or_in=0;
1157//          G->first(in, v);
1158//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1159//        }
1160//      } else {
1161//        ++in;
1162//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1163//      }
1164//      return *this;
1165//       }
1166    };
1167
1168    //FIXME This is just for having InEdgeIt
1169    typedef void InEdgeIt;
1170
1171    class EdgeIt : public Edge {
1172      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1173      NodeIt v;
1174    public:
1175      EdgeIt() { }
1176      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1177      EdgeIt(const Invalid& i) : Edge(i) { }
1178      EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
1179        resG.g->first(v);
1180        if (resG.g->valid(v)) resG.g->first(out, v); else out=INVALID;
1181        while (resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }
1182        while (resG.g->valid(v) && !resG.g->valid(out)) {
1183          resG.g->next(v);
1184          if (resG.g->valid(v)) resG.g->first(out, v);
1185          while (resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }
1186        }
1187        if (!resG.g->valid(out)) {
1188          out_or_in=0;
1189          resG.g->first(v);
1190          if (resG.g->valid(v)) resG.g->first(in, v); else in=INVALID;
1191          while (resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }
1192          while (resG.g->valid(v) && !resG.g->valid(in)) {
1193            resG.g->next(v);
1194            if (resG.g->valid(v)) resG.g->first(in, v);
1195            while (resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }
1196          }
1197        }
1198      }
1199//       EdgeIt& operator++() {
1200//      if (out_or_in) {
1201//        ++out;
1202//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1203//        while (v.valid() && !out.valid()) {
1204//          ++v;
1205//          if (v.valid()) G->first(out, v);
1206//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1207//        }
1208//        if (!out.valid()) {
1209//          out_or_in=0;
1210//          G->first(v);
1211//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1212//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1213//          while (v.valid() && !in.valid()) {
1214//            ++v;
1215//            if (v.valid()) G->first(in, v);
1216//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1217//          } 
1218//        }
1219//      } else {
1220//        ++in;
1221//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1222//        while (v.valid() && !in.valid()) {
1223//          ++v;
1224//          if (v.valid()) G->first(in, v);
1225//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1226//        }
1227//      }
1228//      return *this;
1229//       }
1230    };
1231
1232    NodeIt& first(NodeIt& v) const { g->first(v); return v; }
1233    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1234      e=OutEdgeIt(*this, v);
1235      return e;
1236    }
1237    EdgeIt& first(EdgeIt& e) const {
1238      e=EdgeIt(*this);
1239      return e;
1240    }
1241   
1242    NodeIt& next(NodeIt& n) const { return g->next(n); }
1243
1244    OutEdgeIt& next(OutEdgeIt& e) const {
1245      if (e.out_or_in) {
1246        Node v=g->aNode(e.out);
1247        g->next(e.out);
1248        while( g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }
1249        if (!g->valid(e.out)) {
1250          e.out_or_in=0;
1251          g->first(e.in, v);
1252          while( g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
1253        }
1254      } else {
1255        g->next(e.in);
1256        while( g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
1257      }
1258      return e;
1259    }
1260
1261    EdgeIt& next(EdgeIt& e) const {
1262      if (e.out_or_in) {
1263        g->next(e.out);
1264        while (g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }
1265          while (g->valid(e.v) && !g->valid(e.out)) {
1266            g->next(e.v);
1267            if (g->valid(e.v)) g->first(e.out, e.v);
1268            while (g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }
1269          }
1270          if (!g->valid(e.out)) {
1271            e.out_or_in=0;
1272            g->first(e.v);
1273            if (g->valid(e.v)) g->first(e.in, e.v); else e.in=INVALID;
1274            while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
1275            while (g->valid(e.v) && !g->valid(e.in)) {
1276              g->next(e.v);
1277              if (g->valid(e.v)) g->first(e.in, e.v);
1278              while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
1279            } 
1280          }
1281        } else {
1282          g->next(e.in);
1283          while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
1284          while (g->valid(e.v) && !g->valid(e.in)) {
1285            g->next(e.v);
1286            if (g->valid(e.v)) g->first(e.in, e.v);
1287            while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
1288          }
1289        }
1290        return e;
1291      }
1292   
1293
1294    template< typename It >
1295    It first() const {
1296      It e;
1297      first(e);
1298      return e;
1299    }
1300
1301    template< typename It >
1302    It first(Node v) const {
1303      It e;
1304      first(e, v);
1305      return e;
1306    }
1307
1308    Node tail(Edge e) const {
1309      return ((e.out_or_in) ? g->aNode(e.out) : g->aNode(e.in)); }
1310    Node head(Edge e) const {
1311      return ((e.out_or_in) ? g->bNode(e.out) : g->bNode(e.in)); }
1312
1313    Node aNode(OutEdgeIt e) const {
1314      return ((e.out_or_in) ? g->aNode(e.out) : g->aNode(e.in)); }
1315    Node bNode(OutEdgeIt e) const {
1316      return ((e.out_or_in) ? g->bNode(e.out) : g->bNode(e.in)); }
1317
1318    int nodeNum() const { return g->nodeNum(); }
1319    //FIXME
1320    //int edgeNum() const { return g->edgeNum(); }
1321
1322
1323    int id(Node v) const { return g->id(v); }
1324
1325    bool valid(Node n) const { return g->valid(n); }
1326    bool valid(Edge e) const {
1327      return e.out_or_in ? g->valid(e.out) : g->valid(e.in); }
1328
1329    void augment(const Edge& e, Number a) const {
1330      if (e.out_or_in) 
1331        flow->set(e.out, flow->get(e.out)+a);
1332      else 
1333        flow->set(e.in, flow->get(e.in)-a);
1334    }
1335
1336    Number resCap(const Edge& e) const {
1337      if (e.out_or_in)
1338        return (capacity->get(e.out)-flow->get(e.out));
1339      else
1340        return (flow->get(e.in));
1341    }
1342
1343    Number resCap(OldOutEdgeIt out) const {
1344      return (capacity->get(out)-flow->get(out));
1345    }
1346   
1347    Number resCap(OldInEdgeIt in) const {
1348      return (flow->get(in));
1349    }
1350
1351//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1352//     public:
1353//       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
1354//      : GraphWrapper::NodeMap<T>(_G.gw) { }
1355//       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
1356//            T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1357//     };
1358
1359//     template <typename T>
1360//     class NodeMap {
1361//       typename Graph::NodeMap<T> node_map;
1362//     public:
1363//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1364//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1365//       void set(Node nit, T a) { node_map.set(nit, a); }
1366//       T get(Node nit) const { return node_map.get(nit); }
1367//     };
1368
1369    template <typename T>
1370    class EdgeMap {
1371      typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1372    public:
1373      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1374      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1375      void set(Edge e, T a) {
1376        if (e.out_or_in)
1377          forward_map.set(e.out, a);
1378        else
1379          backward_map.set(e.in, a);
1380      }
1381      T get(Edge e) {
1382        if (e.out_or_in)
1383          return forward_map.get(e.out);
1384        else
1385          return backward_map.get(e.in);
1386      }
1387    };
1388  };
1389
1390  //Subgraph on the same node-set and partial edge-set
1391  template<typename GraphWrapper, typename FirstOutEdgesMap>
1392  class ErasingFirstGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
1393  protected:
1394    FirstOutEdgesMap* first_out_edges;
1395  public:
1396    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
1397    typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
1398    typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;
1399    typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt;
1400    typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt;
1401    typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt;
1402
1403    ErasingFirstGraphWrapper(GraphWrapper& _gw, FirstOutEdgesMap& _first_out_edges) :
1404      GraphWrapperSkeleton1<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { } 
1405
1406    template<typename I> I& first(I& i) const {
1407      g->first(i);
1408      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1409      return i;
1410    }
1411    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1412      e=first_out_edges->get(n);
1413      return e;
1414    }
1415    template<typename I, typename P> I& first(I& i, const P& p) const {
1416      g->first(i, p);
1417      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1418      return i;
1419    }
1420   
1421    //template<typename I> I getNext(const I& i) const {
1422    //  return gw.getNext(i);
1423    //}
1424    template<typename I> I& next(I &i) const {
1425      g->next(i);
1426      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1427      return i;
1428    }
1429   
1430    template< typename It > It first() const {
1431      It e; this->first(e); return e; }
1432   
1433    template< typename It > It first(const Node& v) const {
1434      It e; this->first(e, v); return e; }
1435
1436    void erase(const OutEdgeIt& e) const {
1437      OutEdgeIt f=e;
1438      this->next(f);
1439      first_out_edges->set(this->tail(e), f);
1440    }
1441  };
1442
1443//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1444//   class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1445//   protected:
1446//     ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1447//     //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1448//   public:
1449//     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1450//                         const CapacityMap& _capacity) :
1451//       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1452//       first_out_edges(*this) /*, dist(*this)*/ {
1453//       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1454//      OutEdgeIt e;
1455//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1456//      first_out_edges.set(n, e);
1457//       }
1458//     }
1459
1460//     //void setGraph(Graph& _graph) { graph = &_graph; }
1461//     //Graph& getGraph() const { return (*graph); }
1462 
1463//     //TrivGraphWrapper() : graph(0) { }
1464//     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1465
1466//     //typedef Graph BaseGraph;
1467
1468//     //typedef typename Graph::Node Node;
1469//     //typedef typename Graph::NodeIt NodeIt;
1470
1471//     //typedef typename Graph::Edge Edge;
1472//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
1473//     //typedef typename Graph::InEdgeIt InEdgeIt;
1474//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1475//     //typedef typename Graph::EdgeIt EdgeIt;
1476
1477//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1478//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1479
1480//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1481//     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1482//     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1483//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1484//     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1485
1486//     NodeIt& first(NodeIt& n) const {
1487//       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1488//     }
1489
1490//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1491//       e=first_out_edges.get(n);
1492//       return e;
1493//     }
1494   
1495//     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1496//     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1497//     //  return first(i, p); }
1498   
1499//     //template<typename I> I getNext(const I& i) const {
1500//     //  return gw.getNext(i); }
1501//     //template<typename I> I& next(I &i) const { return gw.next(i); }   
1502
1503//     template< typename It > It first() const {
1504//       It e; first(e); return e; }
1505
1506//     template< typename It > It first(const Node& v) const {
1507//       It e; first(e, v); return e; }
1508
1509//     //Node head(const Edge& e) const { return gw.head(e); }
1510//     //Node tail(const Edge& e) const { return gw.tail(e); }
1511
1512//     //template<typename I> bool valid(const I& i) const
1513//     //  { return gw.valid(i); }
1514 
1515//     //int nodeNum() const { return gw.nodeNum(); }
1516//     //int edgeNum() const { return gw.edgeNum(); }
1517 
1518//     //template<typename I> Node aNode(const I& e) const {
1519//     //  return gw.aNode(e); }
1520//     //template<typename I> Node bNode(const I& e) const {
1521//     //  return gw.bNode(e); }
1522 
1523//     //Node addNode() const { return gw.addNode(); }
1524//     //Edge addEdge(const Node& tail, const Node& head) const {
1525//     //  return gw.addEdge(tail, head); }
1526 
1527//     //void erase(const OutEdgeIt& e) {
1528//     //  first_out_edge(this->tail(e))=e;
1529//     //}
1530//     void erase(const Edge& e) {
1531//       OutEdgeIt f(e);
1532//       next(f);
1533//       first_out_edges.set(this->tail(e), f);
1534//     }
1535//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
1536 
1537//     //void clear() const { gw.clear(); }
1538   
1539//     template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1540//     public:
1541//       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1542//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1543//       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1544//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1545//     };
1546
1547//     template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1548//     public:
1549//       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1550//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1551//       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1552//      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1553//     };
1554//   };
1555
1556//   template<typename GraphWrapper>
1557//   class FilterGraphWrapper {
1558//   };
1559
1560//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1561//   class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1562
1563//     //Graph* graph;
1564 
1565//   public:
1566//     //typedef Graph BaseGraph;
1567
1568//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1569//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1570
1571//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1572//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1573//     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1574//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1575//     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1576
1577//     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1578   
1579//   public:
1580//     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1581//                         const CapacityMap& _capacity) :
1582//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1583//     }
1584
1585//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1586//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1587//       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1588//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1589//       return e;
1590//     }
1591
1592//     NodeIt& next(NodeIt& e) const {
1593//       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1594//     }
1595
1596//     OutEdgeIt& next(OutEdgeIt& e) const {
1597//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1598//       while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1599//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1600//       return e;
1601//     }
1602
1603//     NodeIt& first(NodeIt& n) const {
1604//       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1605//     }
1606
1607//     void erase(const Edge& e) {
1608//       OutEdgeIt f(e);
1609//       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1610//       while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1611//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1612//       first_out_edges.set(this->tail(e), f);
1613//     }
1614
1615//     //TrivGraphWrapper() : graph(0) { }
1616//     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1617
1618//     //void setGraph(Graph& _graph) { graph = &_graph; }
1619//     //Graph& getGraph() const { return (*graph); }
1620   
1621//     //template<typename I> I& first(I& i) const { return gw.first(i); }
1622//     //template<typename I, typename P> I& first(I& i, const P& p) const {
1623//     //  return gw.first(i, p); }
1624   
1625//     //template<typename I> I getNext(const I& i) const {
1626//     //  return gw.getNext(i); }
1627//     //template<typename I> I& next(I &i) const { return gw.next(i); }   
1628
1629//     template< typename It > It first() const {
1630//       It e; first(e); return e; }
1631
1632//     template< typename It > It first(const Node& v) const {
1633//       It e; first(e, v); return e; }
1634
1635//     //Node head(const Edge& e) const { return gw.head(e); }
1636//     //Node tail(const Edge& e) const { return gw.tail(e); }
1637
1638//     //template<typename I> bool valid(const I& i) const
1639//     //  { return gw.valid(i); }
1640 
1641//     //template<typename I> void setInvalid(const I &i);
1642//     //{ return gw.setInvalid(i); }
1643
1644//     //int nodeNum() const { return gw.nodeNum(); }
1645//     //int edgeNum() const { return gw.edgeNum(); }
1646 
1647//     //template<typename I> Node aNode(const I& e) const {
1648//     //  return gw.aNode(e); }
1649//     //template<typename I> Node bNode(const I& e) const {
1650//     //  return gw.bNode(e); }
1651 
1652//     //Node addNode() const { return gw.addNode(); }
1653//     //Edge addEdge(const Node& tail, const Node& head) const {
1654//     //  return gw.addEdge(tail, head); }
1655 
1656//     //template<typename I> void erase(const I& i) const { gw.erase(i); }
1657 
1658//     //void clear() const { gw.clear(); }
1659   
1660//     template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1661//     public:
1662//       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1663//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1664//       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1665//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1666//     };
1667
1668//     template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1669//     public:
1670//       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1671//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1672//       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1673//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1674//     };
1675
1676//   public:
1677//     ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1678
1679//   };
1680
1681
1682
1683// // FIXME: comparison should be made better!!!
1684//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1685//   class ResGraphWrapper
1686//   {
1687//     Graph* graph;
1688 
1689//   public:
1690//     typedef Graph BaseGraph;
1691
1692//     typedef typename Graph::Node Node;
1693//     typedef typename Graph::Edge Edge;
1694 
1695//     typedef typename Graph::NodeIt NodeIt;
1696   
1697//     class OutEdgeIt {
1698//     public:
1699//       //Graph::Node n;
1700//       bool out_or_in;
1701//       typename Graph::OutEdgeIt o;
1702//       typename Graph::InEdgeIt i;   
1703//     };
1704//     class InEdgeIt {
1705//     public:
1706//       //Graph::Node n;
1707//       bool out_or_in;
1708//       typename Graph::OutEdgeIt o;
1709//       typename Graph::InEdgeIt i;   
1710//     };
1711//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1712//     typedef typename Graph::EdgeIt EdgeIt;
1713
1714//     int nodeNum() const { return gw.nodeNum(); }
1715//     int edgeNum() const { return gw.edgeNum(); }
1716
1717//     Node& first(Node& n) const { return gw.first(n); }
1718
1719//     // Edge and SymEdge  is missing!!!!
1720//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1721
1722//     //FIXME
1723//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1724//       {
1725//      e.n=n;
1726//      gw.first(e.o,n);
1727//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1728//        gw.goNext(e.o);
1729//      if(!gw.valid(e.o)) {
1730//        gw.first(e.i,n);
1731//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1732//          gw.goNext(e.i);
1733//      }
1734//      return e;
1735//       }
1736// /*
1737//   OutEdgeIt &goNext(OutEdgeIt &e)
1738//   {
1739//   if(gw.valid(e.o)) {
1740//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1741//   gw.goNext(e.o);
1742//   if(gw.valid(e.o)) return e;
1743//   else gw.first(e.i,e.n);
1744//   }
1745//   else {
1746//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1747//   gw.goNext(e.i);
1748//   return e;
1749//   }
1750//   }
1751//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1752// */
1753//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1754
1755//     //FIXME
1756//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1757//       {
1758//      e.n=n;
1759//      gw.first(e.i,n);
1760//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1761//        gw.goNext(e.i);
1762//      if(!gw.valid(e.i)) {
1763//        gw.first(e.o,n);
1764//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1765//          gw.goNext(e.o);
1766//      }
1767//      return e;
1768//       }
1769// /*
1770//   InEdgeIt &goNext(InEdgeIt &e)
1771//   {
1772//   if(gw.valid(e.i)) {
1773//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1774//   gw.goNext(e.i);
1775//   if(gw.valid(e.i)) return e;
1776//   else gw.first(e.o,e.n);
1777//   }
1778//   else {
1779//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1780//   gw.goNext(e.o);
1781//   return e;
1782//   }
1783//   }
1784//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1785// */
1786//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1787
1788//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1789//     //template<typename I> I next(const I i); { return gw.goNext(i); }
1790
1791//     template< typename It > It first() const {
1792//       It e; first(e); return e; }
1793
1794//     template< typename It > It first(Node v) const {
1795//       It e; first(e, v); return e; }
1796
1797//     Node head(const Edge& e) const { return gw.head(e); }
1798//     Node tail(const Edge& e) const { return gw.tail(e); }
1799 
1800//     template<typename I> Node aNode(const I& e) const {
1801//       return gw.aNode(e); }
1802//     template<typename I> Node bNode(const I& e) const {
1803//       return gw.bNode(e); }
1804 
1805//     //template<typename I> bool valid(const I i);
1806//     //{ return gw.valid(i); }
1807 
1808//     //template<typename I> void setInvalid(const I &i);
1809//     //{ return gw.setInvalid(i); }
1810 
1811//     Node addNode() { return gw.addNode(); }
1812//     Edge addEdge(const Node& tail, const Node& head) {
1813//       return gw.addEdge(tail, head); }
1814 
1815//     template<typename I> void erase(const I& i) { gw.erase(i); }
1816 
1817//     void clear() { gw.clear(); }
1818 
1819//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1820//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1821 
1822//     void setGraph(Graph& _graph) { graph = &_graph; }
1823//     Graph& getGraph() { return (*graph); }
1824
1825//     //ResGraphWrapper() : graph(0) { }
1826//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1827//   };
1828
1829} //namespace hugo
1830
1831#endif //HUGO_GRAPH_WRAPPER_H
1832
Note: See TracBrowser for help on using the repository browser.