COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 304:10d035c2e81c

Last change on this file since 304:10d035c2e81c was 303:1b377a730d02, checked in by marci, 20 years ago

konvergalunk, konvergalunk...

File size: 43.2 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 ParentGraph;
16
17//     TrivGraphWrapper() : graph(0) { }
18    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
19//     void setGraph(Graph& _graph) { graph = &_graph; }
20//     Graph& getGraph() const { return *graph; }
21
22    typedef typename Graph::Node Node;
23    class NodeIt : public Graph::NodeIt {
24    public:
25      NodeIt() { }
26      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
27      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
28      NodeIt(const TrivGraphWrapper<Graph>& _G) :
29        Graph::NodeIt(*(_G.graph)) { }
30    };
31    typedef typename Graph::Edge Edge;
32    class OutEdgeIt : public Graph::OutEdgeIt {
33    public:
34      OutEdgeIt() { }
35      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
36      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
37      OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
38        Graph::OutEdgeIt(*(_G.graph), n) { }
39    };
40    class InEdgeIt : public Graph::InEdgeIt {
41    public:
42      InEdgeIt() { }
43      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
44      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
45      InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
46        Graph::InEdgeIt(*(_G.graph), n) { }
47    };
48    //typedef typename Graph::SymEdgeIt SymEdgeIt;
49    class EdgeIt : public Graph::EdgeIt {
50    public:
51      EdgeIt() { }
52      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
53      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
54      EdgeIt(const TrivGraphWrapper<Graph>& _G) :
55        Graph::EdgeIt(*(_G.graph)) { }
56    };
57
58    NodeIt& first(NodeIt& i) const {
59      i=NodeIt(*this);
60      return i;
61    }
62    EdgeIt& first(EdgeIt& i) const {
63      i=EdgeIt(*this);
64      return i;
65    }
66//     template<typename I> I& first(I& i) const {
67//       i=I(*this);
68//       return i;
69//     }
70    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
71      i=OutEdgeIt(*this, p);
72      return i;
73    }
74    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
75      i=InEdgeIt(*this, p);
76      return i;
77    }
78//     template<typename I, typename P> I& first(I& i, const P& p) const {
79//       i=I(*this, p);
80//       return i;
81//     }
82   
83//    template<typename I> I getNext(const I& i) const {
84//      return graph->getNext(i); }
85    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
86
87    template< typename It > It first() const {
88      It e; this->first(e); return e; }
89
90    template< typename It > It first(const Node& v) const {
91      It e; this->first(e, v); return e; }
92
93    Node head(const Edge& e) const { return graph->head(e); }
94    Node tail(const Edge& e) const { return graph->tail(e); }
95
96    template<typename I> bool valid(const I& i) const {
97      return graph->valid(i); }
98 
99    //template<typename I> void setInvalid(const I &i);
100    //{ return graph->setInvalid(i); }
101
102    int nodeNum() const { return graph->nodeNum(); }
103    int edgeNum() const { return graph->edgeNum(); }
104 
105    template<typename I> Node aNode(const I& e) const {
106      return graph->aNode(e); }
107    template<typename I> Node bNode(const I& e) const {
108      return graph->bNode(e); }
109 
110    Node addNode() const { return graph->addNode(); }
111    Edge addEdge(const Node& tail, const Node& head) const {
112      return graph->addEdge(tail, head); }
113 
114    template<typename I> void erase(const I& i) const { graph->erase(i); }
115 
116    void clear() const { graph->clear(); }
117   
118    template<typename T> class NodeMap : public Graph::NodeMap<T> {
119    public:
120      NodeMap(const TrivGraphWrapper<Graph>& _G) : 
121        Graph::NodeMap<T>(*(_G.graph)) { }
122      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
123        Graph::NodeMap<T>(*(_G.graph), a) { }
124    };
125
126    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
127    public:
128      EdgeMap(const TrivGraphWrapper<Graph>& _G) : 
129        Graph::EdgeMap<T>(*(_G.graph)) { }
130      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
131        Graph::EdgeMap<T>(*(_G.graph), a) { }
132    };
133
134//     template<typename Map, typename T> class NodeMapWrapper {
135//     protected:
136//       Map* map;
137//     public:
138//       NodeMapWrapper(Map& _map) : map(&_map) { }
139//       void set(Node n, T a) { map->set(n, a); }
140//       T get(Node n) const { return map->get(n); }
141//     };
142
143//     template<typename Map, typename T> class EdgeMapWrapper {
144//     protected:
145//       Map* map;
146//     public:
147//       EdgeMapWrapper(Map& _map) : map(&_map) { }
148//       void set(Edge n, T a) { map->set(n, a); }
149//       T get(Edge n) const { return map->get(n); }
150//     };
151  };
152
153
154  template<typename Graph>
155  class GraphWrapper {
156  protected:
157    Graph* graph;
158 
159  public:
160    typedef Graph ParentGraph;
161
162//     GraphWrapper() : graph(0) { }
163    GraphWrapper(Graph& _graph) : graph(&_graph) { }
164//     void setGraph(Graph& _graph) { graph=&_graph; }
165//     Graph& getGraph() const { return *graph; }
166 
167    typedef typename Graph::Node Node;
168    class NodeIt : public Graph::NodeIt {
169    public:
170      NodeIt() { }
171      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
172      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
173      NodeIt(const GraphWrapper<Graph>& _G) :
174        Graph::NodeIt(*(_G.graph)) { }
175    };
176    typedef typename Graph::Edge Edge;
177    class OutEdgeIt : public Graph::OutEdgeIt {
178    public:
179      OutEdgeIt() { }
180      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
181      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
182      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
183        Graph::OutEdgeIt(*(_G.graph), n) { }
184    };
185    class InEdgeIt : public Graph::InEdgeIt {
186    public:
187      InEdgeIt() { }
188      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
189      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
190      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
191        Graph::InEdgeIt(*(_G.graph), n) { }
192    };
193    //typedef typename Graph::SymEdgeIt SymEdgeIt;
194    class EdgeIt : public Graph::EdgeIt {
195    public:
196      EdgeIt() { }
197      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
198      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
199      EdgeIt(const GraphWrapper<Graph>& _G) :
200        Graph::EdgeIt(*(_G.graph)) { }
201    };
202   
203    NodeIt& first(NodeIt& i) const {
204      i=NodeIt(*this);
205      return i;
206    }
207    EdgeIt& first(EdgeIt& i) const {
208      i=EdgeIt(*this);
209      return i;
210    }
211//     template<typename I> I& first(I& i) const {       
212//       i=I(*this);
213//       return i;
214//     }
215    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
216      i=OutEdgeIt(*this, p);
217      return i;
218    }
219    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
220      i=InEdgeIt(*this, p);
221      return i;
222    }
223//     template<typename I, typename P> I& first(I& i, const P& p) const {
224//       i=I(*this, p);
225//       return i;
226//     }
227   
228//    template<typename I> I getNext(const I& i) const {
229//      return gw.getNext(i); }
230    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
231
232    template< typename It > It first() const {
233      It e; this->first(e); return e; }
234
235    template< typename It > It first(const Node& v) const {
236      It e; this->first(e, v); return e; }
237
238    Node head(const Edge& e) const { return graph->head(e); }
239    Node tail(const Edge& e) const { return graph->tail(e); }
240
241    template<typename I> bool valid(const I& i) const {
242      return graph->valid(i); }
243 
244    //template<typename I> void setInvalid(const I &i);
245    //{ return graph->setInvalid(i); }
246
247    int nodeNum() const { return graph->nodeNum(); }
248    int edgeNum() const { return graph->edgeNum(); }
249 
250    template<typename I> Node aNode(const I& e) const {
251      return graph->aNode(e); }
252    template<typename I> Node bNode(const I& e) const {
253      return graph->bNode(e); }
254 
255    Node addNode() const { return graph->addNode(); }
256    Edge addEdge(const Node& tail, const Node& head) const {
257      return graph->addEdge(tail, head); }
258 
259    template<typename I> void erase(const I& i) const { graph->erase(i); }
260 
261    void clear() const { graph->clear(); }
262   
263    template<typename T> class NodeMap : public Graph::NodeMap<T> {
264    public:
265      NodeMap(const GraphWrapper<Graph>& _G) : 
266        Graph::NodeMap<T>(*(_G.graph)) { }
267      NodeMap(const GraphWrapper<Graph>& _G, T a) :
268        Graph::NodeMap<T>(*(_G.graph), a) { }
269    };
270
271    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
272    public:
273      EdgeMap(const GraphWrapper<Graph>& _G) : 
274        Graph::EdgeMap<T>(*(_G.graph)) { }
275      EdgeMap(const GraphWrapper<Graph>& _G, T a) :
276        Graph::EdgeMap<T>(*(_G.graph), a) { }
277    };
278  };
279
280
281//   template<typename Graph>
282//   class RevGraphWrapper
283//   {
284//   protected:
285//     Graph* graph;
286 
287//   public:
288//     typedef Graph ParentGraph;
289
290//     typedef typename Graph::Node Node;   
291//     typedef typename Graph::NodeIt NodeIt;
292 
293//     typedef typename Graph::Edge Edge;
294//     typedef typename Graph::OutEdgeIt InEdgeIt;
295//     typedef typename Graph::InEdgeIt OutEdgeIt;
296//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
297//     typedef typename Graph::EdgeIt EdgeIt;
298
299//     //RevGraphWrapper() : graph(0) { }
300//     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
301
302//     void setGraph(Graph& _graph) { graph = &_graph; }
303//     Graph& getGraph() const { return (*graph); }
304   
305//     template<typename I> I& first(I& i) const { return graph->first(i); }
306//     template<typename I, typename P> I& first(I& i, const P& p) const {
307//       return graph->first(i, p); }
308
309//     template<typename I> I getNext(const I& i) const {
310//       return graph->getNext(i); }
311//     template<typename I> I& next(I &i) const { return graph->next(i); }   
312
313//     template< typename It > It first() const {
314//       It e; first(e); return e; }
315
316//     template< typename It > It first(const Node& v) const {
317//       It e; first(e, v); return e; }
318
319//     Node head(const Edge& e) const { return graph->tail(e); }
320//     Node tail(const Edge& e) const { return graph->head(e); }
321 
322//     template<typename I> bool valid(const I& i) const
323//       { return graph->valid(i); }
324 
325//     //template<typename I> void setInvalid(const I &i);
326//     //{ return graph->setInvalid(i); }
327 
328//     template<typename I> Node aNode(const I& e) const {
329//       return graph->aNode(e); }
330//     template<typename I> Node bNode(const I& e) const {
331//       return graph->bNode(e); }
332
333//     Node addNode() const { return graph->addNode(); }
334//     Edge addEdge(const Node& tail, const Node& head) const {
335//       return graph->addEdge(tail, head); }
336 
337//     int nodeNum() const { return graph->nodeNum(); }
338//     int edgeNum() const { return graph->edgeNum(); }
339 
340//     template<typename I> void erase(const I& i) const { graph->erase(i); }
341 
342//     void clear() const { graph->clear(); }
343
344//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
345//     public:
346//       NodeMap(const RevGraphWrapper<Graph>& _G) :
347//      Graph::NodeMap<T>(_G.getGraph()) { }
348//       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
349//      Graph::NodeMap<T>(_G.getGraph(), a) { }
350//     };
351
352//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
353//     public:
354//       EdgeMap(const RevGraphWrapper<Graph>& _G) :
355//      Graph::EdgeMap<T>(_G.getGraph()) { }
356//       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
357//      Graph::EdgeMap<T>(_G.getGraph(), a) { }
358//     };
359//   };
360
361
362  template<typename Graph>
363  class RevGraphWrapper : public GraphWrapper<Graph> {
364  public:
365    typedef typename GraphWrapper<Graph>::Node Node;
366    typedef typename GraphWrapper<Graph>::Edge Edge;
367    //FIXME
368    //If Graph::OutEdgeIt is not defined
369    //and we do not want to use RevGraphWrapper::InEdgeIt,
370    //this won't work, because of typedef
371    //OR
372    //graphs have to define their non-existing iterators to void
373    //Unfortunately all the typedefs are instantiated in templates,
374    //unlike other stuff
375    typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
376    typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
377
378//     RevGraphWrapper() : GraphWrapper<Graph>() { }
379    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
380
381    Node head(const Edge& e) const
382      { return GraphWrapper<Graph>::tail(e); }
383    Node tail(const Edge& e) const
384      { return GraphWrapper<Graph>::head(e); }
385  };
386
387  //Subgraph on the same node-set and partial edge-set
388  template<typename Graph, typename EdgeFilterMap>
389  class SubGraphWrapper : public GraphWrapper<Graph> {
390  protected:
391    EdgeFilterMap* filter_map;
392  public:
393    typedef typename GraphWrapper<Graph>::Node Node;
394    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
395    typedef typename GraphWrapper<Graph>::Edge Edge;
396    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
397    typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
398    typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
399
400//     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
401    SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
402      GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { } 
403
404    template<typename I> I& first(I& i) const {
405      graph->first(i);
406      //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
407      while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
408      return i;
409    }
410    template<typename I, typename P> I& first(I& i, const P& p) const {
411      graph->first(i, p);
412//      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
413      while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
414      return i;
415    }
416   
417    //template<typename I> I getNext(const I& i) const {
418    //  return gw.getNext(i);
419    //}
420    template<typename I> I& next(I &i) const {
421      graph->next(i);
422//      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
423      while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
424      return i;
425    }
426   
427    template< typename It > It first() const {
428      It e; this->first(e); return e; }
429   
430    template< typename It > It first(const Node& v) const {
431      It e; this->first(e, v); return e; }
432  };
433
434//   template<typename GraphWrapper>
435//   class UndirGraphWrapper {
436//   protected:
437//     //Graph* graph;
438//     GraphWrapper gw;
439
440//   public:
441//     typedef GraphWrapper ParentGraph;
442
443//     typedef typename GraphWrapper::Node Node;
444//     typedef typename GraphWrapper::NodeIt NodeIt;
445
446//     //typedef typename Graph::Edge Edge;
447//     //typedef typename Graph::OutEdgeIt OutEdgeIt;
448//     //typedef typename Graph::InEdgeIt InEdgeIt;
449//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
450//     //typedef typename Graph::EdgeIt EdgeIt;
451
452//     //private:
453//     typedef typename GraphWrapper::Edge GraphEdge;
454//     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
455//     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
456//     //public:
457
458//     //UndirGraphWrapper() : graph(0) { }
459//     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
460
461//     //void setGraph(Graph& _graph) { graph = &_graph; }
462//     //Graph& getGraph() const { return (*graph); }
463 
464//     class Edge {
465//       friend class UndirGraphWrapper<GraphWrapper>;
466//       bool out_or_in; //true iff out
467//       GraphOutEdgeIt out;
468//       GraphInEdgeIt in;
469//     public:
470//       Edge() : out_or_in(), out(), in() { }
471//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
472//       operator GraphEdge() const {
473//      if (out_or_in) return(out); else return(in);
474//       }
475//       friend bool operator==(const Edge& u, const Edge& v) {
476//      if (v.out_or_in)
477//        return (u.out_or_in && u.out==v.out);
478//      else
479//        return (!u.out_or_in && u.in==v.in);
480//       }
481//       friend bool operator!=(const Edge& u, const Edge& v) {
482//      if (v.out_or_in)
483//        return (!u.out_or_in || u.out!=v.out);
484//      else
485//        return (u.out_or_in || u.in!=v.in);
486//       }
487//     };
488
489//     class OutEdgeIt : public Edge {
490//       friend class UndirGraphWrapper<GraphWrapper>;
491//     public:
492//       OutEdgeIt() : Edge() { }
493//       OutEdgeIt(const Invalid& i) : Edge(i) { }
494//       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
495//      : Edge() {
496//      out_or_in=true;
497//      _G.gw.first(out, n);
498//      if (!(_G.gw.valid(out))) {
499//        out_or_in=false;
500//        _G.gw.first(in, n);
501//      }
502//       }
503//     };
504
505//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
506//       e.out_or_in=true;
507//       gw.first(e.out, n);
508//       if (!(gw.valid(e.out))) {
509//      e.out_or_in=false;
510//      gw.first(e.in, n);
511//       }
512//       return e;
513//     }
514
515//     OutEdgeIt& next(OutEdgeIt& e) const {
516//       if (e.out_or_in) {
517//      Node n=gw.tail(e.out);
518//      gw.next(e.out);
519//      if (!gw.valid(e.out)) {
520//        e.out_or_in=false;
521//        gw.first(e.in, n);
522//      }
523//       } else {
524//      gw.next(e.in);
525//       }
526//       return e;
527//     }
528
529//     Node aNode(const OutEdgeIt& e) const {
530//       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
531//     Node bNode(const OutEdgeIt& e) const {
532//       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
533
534//     typedef OutEdgeIt InEdgeIt;
535
536//     template<typename I> I& first(I& i) const { return gw.first(i); }
537// //     template<typename I, typename P> I& first(I& i, const P& p) const {
538// //       return graph->first(i, p); }
539   
540//     template<typename I> I getNext(const I& i) const {
541//       return gw.getNext(i); }
542//     template<typename I> I& next(I &i) const { return gw.next(i); }   
543
544//     template< typename It > It first() const {
545//       It e; first(e); return e; }
546
547//     template< typename It > It first(const Node& v) const {
548//       It e; first(e, v); return e; }
549
550//     Node head(const Edge& e) const { return gw.head(e); }
551//     Node tail(const Edge& e) const { return gw.tail(e); }
552
553//     template<typename I> bool valid(const I& i) const
554//       { return gw.valid(i); }
555 
556//     //template<typename I> void setInvalid(const I &i);
557//     //{ return graph->setInvalid(i); }
558
559//     int nodeNum() const { return gw.nodeNum(); }
560//     int edgeNum() const { return gw.edgeNum(); }
561 
562// //     template<typename I> Node aNode(const I& e) const {
563// //       return graph->aNode(e); }
564// //     template<typename I> Node bNode(const I& e) const {
565// //       return graph->bNode(e); }
566 
567//     Node addNode() const { return gw.addNode(); }
568// // FIXME: ez igy nem jo, mert nem
569// //    Edge addEdge(const Node& tail, const Node& head) const {
570// //      return graph->addEdge(tail, head); }
571 
572//     template<typename I> void erase(const I& i) const { gw.erase(i); }
573 
574//     void clear() const { gw.clear(); }
575   
576//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
577//     public:
578//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
579//      GraphWrapper::NodeMap<T>(_G.gw) { }
580//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
581//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
582//     };
583
584//     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
585//     public:
586//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
587//      GraphWrapper::EdgeMap<T>(_G.gw) { }
588//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
589//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
590//     };
591//   };
592
593
594  template<typename Graph>
595  class UndirGraphWrapper : public GraphWrapper<Graph> {
596  protected:
597    typedef typename Graph::Edge GraphEdge;
598    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
599    typedef typename Graph::InEdgeIt GraphInEdgeIt;   
600  public:
601    typedef typename GraphWrapper<Graph>::Node Node;
602    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
603
604//     UndirGraphWrapper() : GraphWrapper<Graph>() { }
605    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
606
607    class Edge {
608      friend class UndirGraphWrapper<Graph>;
609    protected:
610      bool out_or_in; //true iff out
611      GraphOutEdgeIt out;
612      GraphInEdgeIt in;
613    public:
614      Edge() : out_or_in(), out(), in() { }
615      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
616      operator GraphEdge() const {
617        if (out_or_in) return(out); else return(in);
618      }
619//FIXME
620//2 edges are equal if they "refer" to the same physical edge
621//is it good?
622      friend bool operator==(const Edge& u, const Edge& v) {
623        if (v.out_or_in)
624          if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
625        //return (u.out_or_in && u.out==v.out);
626        else
627          if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
628        //return (!u.out_or_in && u.in==v.in);
629      }
630      friend bool operator!=(const Edge& u, const Edge& v) {
631        if (v.out_or_in)
632          if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
633        //return (!u.out_or_in || u.out!=v.out);
634        else
635          if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
636        //return (u.out_or_in || u.in!=v.in);
637      }
638    };
639
640    class OutEdgeIt : public Edge {
641      friend class UndirGraphWrapper<Graph>;
642    public:
643      OutEdgeIt() : Edge() { }
644      OutEdgeIt(const Invalid& i) : Edge(i) { }
645      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
646        : Edge() {
647        out_or_in=true; _G.graph->first(out, n);
648        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
649      }
650    };
651
652    typedef OutEdgeIt InEdgeIt;
653
654    class EdgeIt : public Edge {
655      friend class UndirGraphWrapper<Graph>;
656    protected:
657      NodeIt v;
658    public:
659      EdgeIt() : Edge() { }
660      EdgeIt(const Invalid& i) : Edge(i) { }
661      EdgeIt(const UndirGraphWrapper<Graph>& _G)
662        : Edge() {
663        out_or_in=true;
664        //Node v;
665        _G.first(v);
666        if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
667        while (_G.valid(v) && !_G.graph->valid(out)) {
668          _G.graph->next(v);
669          if (_G.valid(v)) _G.graph->first(out);
670        }
671      }
672    };
673
674    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
675      e.out_or_in=true; graph->first(e.out, n);
676      if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
677      return e;
678    }
679
680    EdgeIt& first(EdgeIt& e) const {
681      e.out_or_in=true;
682      //NodeIt v;
683      first(e.v);
684      if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
685      while (valid(e.v) && !graph->valid(e.out)) {
686        graph->next(e.v);
687        if (valid(e.v)) graph->first(e.out, e.v);
688      }
689      return e;
690    }
691
692    template<typename I> I& first(I& i) const { graph->first(i); return i; }
693    template<typename I, typename P> I& first(I& i, const P& p) const {
694      graph->first(i, p); return i; }
695
696    OutEdgeIt& next(OutEdgeIt& e) const {
697      if (e.out_or_in) {
698        Node n=graph->tail(e.out);
699        graph->next(e.out);
700        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
701      } else {
702        graph->next(e.in);
703      }
704      return e;
705    }
706
707    EdgeIt& next(EdgeIt& e) const {
708      //NodeIt v=tail(e);
709      graph->next(e.out);
710      while (valid(e.v) && !graph->valid(e.out)) {
711        next(e.v);
712        if (valid(e.v)) graph->first(e.out, e.v);
713      }
714      return e;
715    }
716
717    template<typename I> I& next(I &i) const { return graph->next(i); }   
718//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
719
720    template< typename It > It first() const {
721      It e; this->first(e); return e; }
722
723    template< typename It > It first(const Node& v) const {
724      It e; this->first(e, v); return e; }
725
726//    Node head(const Edge& e) const { return gw.head(e); }
727//    Node tail(const Edge& e) const { return gw.tail(e); }
728
729//    template<typename I> bool valid(const I& i) const
730//      { return gw.valid(i); }
731 
732//    int nodeNum() const { return gw.nodeNum(); }
733//    int edgeNum() const { return gw.edgeNum(); }
734 
735//     template<typename I> Node aNode(const I& e) const {
736//       return graph->aNode(e); }
737//     template<typename I> Node bNode(const I& e) const {
738//       return graph->bNode(e); }
739
740    Node aNode(const OutEdgeIt& e) const {
741      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
742    Node bNode(const OutEdgeIt& e) const {
743      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
744 
745//    Node addNode() const { return gw.addNode(); }
746
747// FIXME: ez igy nem jo, mert nem
748//    Edge addEdge(const Node& tail, const Node& head) const {
749//      return graph->addEdge(tail, head); }
750 
751//    template<typename I> void erase(const I& i) const { gw.erase(i); }
752 
753//    void clear() const { gw.clear(); }
754   
755//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
756//     public:
757//       NodeMap(const UndirGraphWrapper<Graph>& _G) :
758//      Graph::NodeMap<T>(_G.gw) { }
759//       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
760//      Graph::NodeMap<T>(_G.gw, a) { }
761//     };
762
763//     template<typename T> class EdgeMap :
764//       public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
765//     public:
766//       EdgeMap(const UndirGraphWrapper<Graph>& _G) :
767//      GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
768//       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
769//      Graph::EdgeMap<T>(_G.gw, a) { }
770//     };
771   };
772
773
774
775
776
777//   template<typename Graph>
778//   class SymGraphWrapper
779//   {
780//     Graph* graph;
781 
782//   public:
783//     typedef Graph ParentGraph;
784
785//     typedef typename Graph::Node Node;
786//     typedef typename Graph::Edge Edge;
787 
788//     typedef typename Graph::NodeIt NodeIt;
789   
790//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
791//     //iranyitatlant, ami van
792//     //mert csak 1 dolgot lehet be typedef-elni
793//     typedef typename Graph::OutEdgeIt SymEdgeIt;
794//     //typedef typename Graph::InEdgeIt SymEdgeIt;
795//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
796//     typedef typename Graph::EdgeIt EdgeIt;
797
798//     int nodeNum() const { return graph->nodeNum(); }
799//     int edgeNum() const { return graph->edgeNum(); }
800   
801//     template<typename I> I& first(I& i) const { return graph->first(i); }
802//     template<typename I, typename P> I& first(I& i, const P& p) const {
803//       return graph->first(i, p); }
804//     //template<typename I> I next(const I i); { return graph->goNext(i); }
805//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
806
807//     template< typename It > It first() const {
808//       It e; first(e); return e; }
809
810//     template< typename It > It first(Node v) const {
811//       It e; first(e, v); return e; }
812
813//     Node head(const Edge& e) const { return graph->head(e); }
814//     Node tail(const Edge& e) const { return graph->tail(e); }
815 
816//     template<typename I> Node aNode(const I& e) const {
817//       return graph->aNode(e); }
818//     template<typename I> Node bNode(const I& e) const {
819//       return graph->bNode(e); }
820 
821//     //template<typename I> bool valid(const I i);
822//     //{ return graph->valid(i); }
823 
824//     //template<typename I> void setInvalid(const I &i);
825//     //{ return graph->setInvalid(i); }
826 
827//     Node addNode() { return graph->addNode(); }
828//     Edge addEdge(const Node& tail, const Node& head) {
829//       return graph->addEdge(tail, head); }
830 
831//     template<typename I> void erase(const I& i) { graph->erase(i); }
832 
833//     void clear() { graph->clear(); }
834 
835//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
836//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
837 
838//     void setGraph(Graph& _graph) { graph = &_graph; }
839//     Graph& getGraph() { return (*graph); }
840
841//     //SymGraphWrapper() : graph(0) { }
842//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
843//   };
844
845
846  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
847  class ResGraphWrapper : public GraphWrapper<Graph>{
848  public:
849    typedef typename GraphWrapper<Graph>::Node Node;
850    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
851  protected:
852    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
853    typedef typename Graph::InEdgeIt GraphInEdgeIt;
854    typedef typename Graph::Edge GraphEdge;
855    FlowMap* flow;
856    const CapacityMap* capacity;
857  public:
858
859    ResGraphWrapper(Graph& _graph, FlowMap& _flow,
860                    const CapacityMap& _capacity) :
861      GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
862
863    class Edge;
864    class OutEdgeIt;
865    friend class Edge;
866    friend class OutEdgeIt;
867
868    class Edge {
869      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
870    protected:
871      bool out_or_in; //true, iff out
872      GraphOutEdgeIt out;
873      GraphInEdgeIt in;
874    public:
875      Edge() : out_or_in(true) { }
876      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
877//       bool valid() const {
878//      return out_or_in && out.valid() || in.valid(); }
879      friend bool operator==(const Edge& u, const Edge& v) {
880        if (v.out_or_in)
881          return (u.out_or_in && u.out==v.out);
882        else
883          return (!u.out_or_in && u.in==v.in);
884      }
885      friend bool operator!=(const Edge& u, const Edge& v) {
886        if (v.out_or_in)
887          return (!u.out_or_in || u.out!=v.out);
888        else
889          return (u.out_or_in || u.in!=v.in);
890      }
891      operator GraphEdge() const {
892        if (out_or_in) return(out); else return(in);
893      }
894    };
895
896
897    class OutEdgeIt : public Edge {
898      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
899    public:
900      OutEdgeIt() { }
901      //FIXME
902      OutEdgeIt(const Edge& e) : Edge(e) { }
903      OutEdgeIt(const Invalid& i) : Edge(i) { }
904    protected:
905      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
906        resG.graph->first(out, v);
907        while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
908        if (!resG.graph->valid(out)) {
909          out_or_in=0;
910          resG.graph->first(in, v);
911          while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
912        }
913      }
914//     public:
915//       OutEdgeIt& operator++() {
916//      if (out_or_in) {
917//        Node v=/*resG->*/G->aNode(out);
918//        ++out;
919//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
920//        if (!out.valid()) {
921//          out_or_in=0;
922//          G->first(in, v);
923//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
924//        }
925//      } else {
926//        ++in;
927//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
928//      }
929//      return *this;
930//       }
931    };
932
933    //FIXME This is just for having InEdgeIt
934    typedef void InEdgeIt;
935
936    class EdgeIt : public Edge {
937      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
938      NodeIt v;
939    public:
940      EdgeIt() { }
941      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
942      EdgeIt(const Invalid& i) : Edge(i) { }
943      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
944        resG.graph->first(v);
945        if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
946        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
947        while (resG.graph->valid(v) && !resG.graph->valid(out)) {
948          resG.graph->next(v);
949          if (resG.graph->valid(v)) resG.graph->first(out, v);
950          while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
951        }
952        if (!resG.graph->valid(out)) {
953          out_or_in=0;
954          resG.graph->first(v);
955          if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
956          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
957          while (resG.graph->valid(v) && !resG.graph->valid(in)) {
958            resG.graph->next(v);
959            if (resG.graph->valid(v)) resG.graph->first(in, v);
960            while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
961          }
962        }
963      }
964//       EdgeIt& operator++() {
965//      if (out_or_in) {
966//        ++out;
967//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
968//        while (v.valid() && !out.valid()) {
969//          ++v;
970//          if (v.valid()) G->first(out, v);
971//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
972//        }
973//        if (!out.valid()) {
974//          out_or_in=0;
975//          G->first(v);
976//          if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
977//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
978//          while (v.valid() && !in.valid()) {
979//            ++v;
980//            if (v.valid()) G->first(in, v);
981//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
982//          } 
983//        }
984//      } else {
985//        ++in;
986//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
987//        while (v.valid() && !in.valid()) {
988//          ++v;
989//          if (v.valid()) G->first(in, v);
990//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
991//        }
992//      }
993//      return *this;
994//       }
995    };
996
997    NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
998    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
999      e=OutEdgeIt(*this, v);
1000      return e;
1001    }
1002    EdgeIt& first(EdgeIt& e) const {
1003      e=EdgeIt(*this);
1004      return e;
1005    }
1006   
1007    NodeIt& next(NodeIt& n) const { return graph->next(n); }
1008
1009    OutEdgeIt& next(OutEdgeIt& e) const {
1010      if (e.out_or_in) {
1011        Node v=graph->aNode(e.out);
1012        graph->next(e.out);
1013        while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1014        if (!graph->valid(e.out)) {
1015          e.out_or_in=0;
1016          graph->first(e.in, v);
1017          while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1018        }
1019      } else {
1020        graph->next(e.in);
1021        while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1022      }
1023      return e;
1024    }
1025
1026    EdgeIt& next(EdgeIt& e) const {
1027      if (e.out_or_in) {
1028        graph->next(e.out);
1029        while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1030          while (graph->valid(e.v) && !graph->valid(e.out)) {
1031            graph->next(e.v);
1032            if (graph->valid(e.v)) graph->first(e.out, e.v);
1033            while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1034          }
1035          if (!graph->valid(e.out)) {
1036            e.out_or_in=0;
1037            graph->first(e.v);
1038            if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1039            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1040            while (graph->valid(e.v) && !graph->valid(e.in)) {
1041              graph->next(e.v);
1042              if (graph->valid(e.v)) graph->first(e.in, e.v);
1043              while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1044            } 
1045          }
1046        } else {
1047          graph->next(e.in);
1048          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1049          while (graph->valid(e.v) && !graph->valid(e.in)) {
1050            graph->next(e.v);
1051            if (graph->valid(e.v)) graph->first(e.in, e.v);
1052            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1053          }
1054        }
1055        return e;
1056      }
1057   
1058
1059    template< typename It >
1060    It first() const {
1061      It e;
1062      first(e);
1063      return e;
1064    }
1065
1066    template< typename It >
1067    It first(Node v) const {
1068      It e;
1069      first(e, v);
1070      return e;
1071    }
1072
1073    Node tail(Edge e) const {
1074      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1075    Node head(Edge e) const {
1076      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1077
1078    Node aNode(OutEdgeIt e) const {
1079      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1080    Node bNode(OutEdgeIt e) const {
1081      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1082
1083    int nodeNum() const { return graph->nodeNum(); }
1084    //FIXME
1085    //int edgeNum() const { return graph->edgeNum(); }
1086
1087
1088    int id(Node v) const { return graph->id(v); }
1089
1090    bool valid(Node n) const { return graph->valid(n); }
1091    bool valid(Edge e) const {
1092      return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1093
1094    void augment(const Edge& e, Number a) const {
1095      if (e.out_or_in) 
1096//      flow->set(e.out, flow->get(e.out)+a);
1097        flow->set(e.out, (*flow)[e.out]+a);
1098      else 
1099//      flow->set(e.in, flow->get(e.in)-a);
1100        flow->set(e.in, (*flow)[e.in]-a);
1101    }
1102
1103    Number resCap(const Edge& e) const {
1104      if (e.out_or_in)
1105//      return (capacity->get(e.out)-flow->get(e.out));
1106        return ((*capacity)[e.out]-(*flow)[e.out]);
1107      else
1108//      return (flow->get(e.in));
1109        return ((*flow)[e.in]);
1110    }
1111
1112    Number resCap(GraphOutEdgeIt out) const {
1113//      return (capacity->get(out)-flow->get(out));
1114      return ((*capacity)[out]-(*flow)[out]);
1115    }
1116   
1117    Number resCap(GraphInEdgeIt in) const {
1118//      return (flow->get(in));
1119      return ((*flow)[in]);
1120    }
1121
1122//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1123//     public:
1124//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1125//      : Graph::NodeMap<T>(_G.gw) { }
1126//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1127//            T a) : Graph::NodeMap<T>(_G.gw, a) { }
1128//     };
1129
1130//     template <typename T>
1131//     class NodeMap {
1132//       typename Graph::NodeMap<T> node_map;
1133//     public:
1134//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1135//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1136//       void set(Node nit, T a) { node_map.set(nit, a); }
1137//       T get(Node nit) const { return node_map.get(nit); }
1138//     };
1139
1140    template <typename T>
1141    class EdgeMap {
1142      typename Graph::EdgeMap<T> forward_map, backward_map;
1143    public:
1144      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1145      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1146      void set(Edge e, T a) {
1147        if (e.out_or_in)
1148          forward_map.set(e.out, a);
1149        else
1150          backward_map.set(e.in, a);
1151      }
1152      T operator[](Edge e) const {
1153        if (e.out_or_in)
1154          return forward_map[e.out];
1155        else
1156          return backward_map[e.in];
1157      }
1158//       T get(Edge e) const {
1159//      if (e.out_or_in)
1160//        return forward_map.get(e.out);
1161//      else
1162//        return backward_map.get(e.in);
1163//       }
1164    };
1165  };
1166
1167  //ErasingFirstGraphWrapper for blocking flows
1168  template<typename Graph, typename FirstOutEdgesMap>
1169  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1170  protected:
1171    FirstOutEdgesMap* first_out_edges;
1172  public:
1173    typedef typename GraphWrapper<Graph>::Node Node;
1174    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1175    typedef typename GraphWrapper<Graph>::Edge Edge;
1176    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1177    typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
1178    typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
1179
1180    ErasingFirstGraphWrapper(Graph& _graph,
1181                             FirstOutEdgesMap& _first_out_edges) :
1182      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1183
1184    template<typename I> I& first(I& i) const {
1185      graph->first(i);
1186      return i;
1187    }
1188    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1189//      e=first_out_edges->get(n);
1190      e=(*first_out_edges)[n];
1191      return e;
1192    }
1193    template<typename I, typename P> I& first(I& i, const P& p) const {
1194      graph->first(i, p);
1195      return i;
1196    }
1197   
1198    //template<typename I> I getNext(const I& i) const {
1199    //  return gw.getNext(i);
1200    //}
1201    template<typename I> I& next(I &i) const {
1202      graph->next(i);
1203      return i;
1204    }
1205   
1206    template< typename It > It first() const {
1207      It e; this->first(e); return e; }
1208   
1209    template< typename It > It first(const Node& v) const {
1210      It e; this->first(e, v); return e; }
1211
1212    void erase(const OutEdgeIt& e) const {
1213      OutEdgeIt f=e;
1214      this->next(f);
1215      first_out_edges->set(this->tail(e), f);
1216    }
1217  };
1218
1219// // FIXME: comparison should be made better!!!
1220//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1221//   class ResGraphWrapper
1222//   {
1223//     Graph* graph;
1224 
1225//   public:
1226//     typedef Graph ParentGraph;
1227
1228//     typedef typename Graph::Node Node;
1229//     typedef typename Graph::Edge Edge;
1230 
1231//     typedef typename Graph::NodeIt NodeIt;
1232   
1233//     class OutEdgeIt {
1234//     public:
1235//       //Graph::Node n;
1236//       bool out_or_in;
1237//       typename Graph::OutEdgeIt o;
1238//       typename Graph::InEdgeIt i;   
1239//     };
1240//     class InEdgeIt {
1241//     public:
1242//       //Graph::Node n;
1243//       bool out_or_in;
1244//       typename Graph::OutEdgeIt o;
1245//       typename Graph::InEdgeIt i;   
1246//     };
1247//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1248//     typedef typename Graph::EdgeIt EdgeIt;
1249
1250//     int nodeNum() const { return gw.nodeNum(); }
1251//     int edgeNum() const { return gw.edgeNum(); }
1252
1253//     Node& first(Node& n) const { return gw.first(n); }
1254
1255//     // Edge and SymEdge  is missing!!!!
1256//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1257
1258//     //FIXME
1259//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1260//       {
1261//      e.n=n;
1262//      gw.first(e.o,n);
1263//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1264//        gw.goNext(e.o);
1265//      if(!gw.valid(e.o)) {
1266//        gw.first(e.i,n);
1267//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1268//          gw.goNext(e.i);
1269//      }
1270//      return e;
1271//       }
1272// /*
1273//   OutEdgeIt &goNext(OutEdgeIt &e)
1274//   {
1275//   if(gw.valid(e.o)) {
1276//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1277//   gw.goNext(e.o);
1278//   if(gw.valid(e.o)) return e;
1279//   else gw.first(e.i,e.n);
1280//   }
1281//   else {
1282//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1283//   gw.goNext(e.i);
1284//   return e;
1285//   }
1286//   }
1287//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1288// */
1289//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1290
1291//     //FIXME
1292//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1293//       {
1294//      e.n=n;
1295//      gw.first(e.i,n);
1296//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1297//        gw.goNext(e.i);
1298//      if(!gw.valid(e.i)) {
1299//        gw.first(e.o,n);
1300//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1301//          gw.goNext(e.o);
1302//      }
1303//      return e;
1304//       }
1305// /*
1306//   InEdgeIt &goNext(InEdgeIt &e)
1307//   {
1308//   if(gw.valid(e.i)) {
1309//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1310//   gw.goNext(e.i);
1311//   if(gw.valid(e.i)) return e;
1312//   else gw.first(e.o,e.n);
1313//   }
1314//   else {
1315//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1316//   gw.goNext(e.o);
1317//   return e;
1318//   }
1319//   }
1320//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1321// */
1322//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1323
1324//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1325//     //template<typename I> I next(const I i); { return gw.goNext(i); }
1326
1327//     template< typename It > It first() const {
1328//       It e; first(e); return e; }
1329
1330//     template< typename It > It first(Node v) const {
1331//       It e; first(e, v); return e; }
1332
1333//     Node head(const Edge& e) const { return gw.head(e); }
1334//     Node tail(const Edge& e) const { return gw.tail(e); }
1335 
1336//     template<typename I> Node aNode(const I& e) const {
1337//       return gw.aNode(e); }
1338//     template<typename I> Node bNode(const I& e) const {
1339//       return gw.bNode(e); }
1340 
1341//     //template<typename I> bool valid(const I i);
1342//     //{ return gw.valid(i); }
1343 
1344//     //template<typename I> void setInvalid(const I &i);
1345//     //{ return gw.setInvalid(i); }
1346 
1347//     Node addNode() { return gw.addNode(); }
1348//     Edge addEdge(const Node& tail, const Node& head) {
1349//       return gw.addEdge(tail, head); }
1350 
1351//     template<typename I> void erase(const I& i) { gw.erase(i); }
1352 
1353//     void clear() { gw.clear(); }
1354 
1355//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1356//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1357 
1358//     void setGraph(Graph& _graph) { graph = &_graph; }
1359//     Graph& getGraph() { return (*graph); }
1360
1361//     //ResGraphWrapper() : graph(0) { }
1362//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1363//   };
1364
1365} //namespace hugo
1366
1367#endif //HUGO_GRAPH_WRAPPER_H
1368
Note: See TracBrowser for help on using the repository browser.