COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 307:0fac67bef95a

Last change on this file since 307:0fac67bef95a was 307:0fac67bef95a, checked in by marci, 20 years ago

1 konstruktor nem volt publikus

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 { graph->next(i); return 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      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
905        resG.graph->first(out, v);
906        while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
907        if (!resG.graph->valid(out)) {
908          out_or_in=0;
909          resG.graph->first(in, v);
910          while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
911        }
912      }
913//     public:
914//       OutEdgeIt& operator++() {
915//      if (out_or_in) {
916//        Node v=/*resG->*/G->aNode(out);
917//        ++out;
918//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
919//        if (!out.valid()) {
920//          out_or_in=0;
921//          G->first(in, v);
922//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
923//        }
924//      } else {
925//        ++in;
926//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
927//      }
928//      return *this;
929//       }
930    };
931
932    //FIXME This is just for having InEdgeIt
933    typedef void InEdgeIt;
934
935    class EdgeIt : public Edge {
936      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
937      NodeIt v;
938    public:
939      EdgeIt() { }
940      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
941      EdgeIt(const Invalid& i) : Edge(i) { }
942      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
943        resG.graph->first(v);
944        if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
945        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
946        while (resG.graph->valid(v) && !resG.graph->valid(out)) {
947          resG.graph->next(v);
948          if (resG.graph->valid(v)) resG.graph->first(out, v);
949          while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
950        }
951        if (!resG.graph->valid(out)) {
952          out_or_in=0;
953          resG.graph->first(v);
954          if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
955          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
956          while (resG.graph->valid(v) && !resG.graph->valid(in)) {
957            resG.graph->next(v);
958            if (resG.graph->valid(v)) resG.graph->first(in, v);
959            while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
960          }
961        }
962      }
963//       EdgeIt& operator++() {
964//      if (out_or_in) {
965//        ++out;
966//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
967//        while (v.valid() && !out.valid()) {
968//          ++v;
969//          if (v.valid()) G->first(out, v);
970//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
971//        }
972//        if (!out.valid()) {
973//          out_or_in=0;
974//          G->first(v);
975//          if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
976//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
977//          while (v.valid() && !in.valid()) {
978//            ++v;
979//            if (v.valid()) G->first(in, v);
980//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
981//          } 
982//        }
983//      } else {
984//        ++in;
985//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
986//        while (v.valid() && !in.valid()) {
987//          ++v;
988//          if (v.valid()) G->first(in, v);
989//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
990//        }
991//      }
992//      return *this;
993//       }
994    };
995
996    NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
997    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
998      e=OutEdgeIt(*this, v);
999      return e;
1000    }
1001    EdgeIt& first(EdgeIt& e) const {
1002      e=EdgeIt(*this);
1003      return e;
1004    }
1005   
1006    NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
1007
1008    OutEdgeIt& next(OutEdgeIt& e) const {
1009      if (e.out_or_in) {
1010        Node v=graph->aNode(e.out);
1011        graph->next(e.out);
1012        while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1013        if (!graph->valid(e.out)) {
1014          e.out_or_in=0;
1015          graph->first(e.in, v);
1016          while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1017        }
1018      } else {
1019        graph->next(e.in);
1020        while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1021      }
1022      return e;
1023    }
1024
1025    EdgeIt& next(EdgeIt& e) const {
1026      if (e.out_or_in) {
1027        graph->next(e.out);
1028        while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1029          while (graph->valid(e.v) && !graph->valid(e.out)) {
1030            graph->next(e.v);
1031            if (graph->valid(e.v)) graph->first(e.out, e.v);
1032            while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1033          }
1034          if (!graph->valid(e.out)) {
1035            e.out_or_in=0;
1036            graph->first(e.v);
1037            if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1038            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1039            while (graph->valid(e.v) && !graph->valid(e.in)) {
1040              graph->next(e.v);
1041              if (graph->valid(e.v)) graph->first(e.in, e.v);
1042              while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1043            } 
1044          }
1045        } else {
1046          graph->next(e.in);
1047          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1048          while (graph->valid(e.v) && !graph->valid(e.in)) {
1049            graph->next(e.v);
1050            if (graph->valid(e.v)) graph->first(e.in, e.v);
1051            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1052          }
1053        }
1054        return e;
1055      }
1056   
1057
1058    template< typename It >
1059    It first() const {
1060      It e;
1061      first(e);
1062      return e;
1063    }
1064
1065    template< typename It >
1066    It first(Node v) const {
1067      It e;
1068      first(e, v);
1069      return e;
1070    }
1071
1072    Node tail(Edge e) const {
1073      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1074    Node head(Edge e) const {
1075      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1076
1077    Node aNode(OutEdgeIt e) const {
1078      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1079    Node bNode(OutEdgeIt e) const {
1080      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1081
1082    int nodeNum() const { return graph->nodeNum(); }
1083    //FIXME
1084    //int edgeNum() const { return graph->edgeNum(); }
1085
1086
1087    int id(Node v) const { return graph->id(v); }
1088
1089    bool valid(Node n) const { return graph->valid(n); }
1090    bool valid(Edge e) const {
1091      return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1092
1093    void augment(const Edge& e, Number a) const {
1094      if (e.out_or_in) 
1095//      flow->set(e.out, flow->get(e.out)+a);
1096        flow->set(e.out, (*flow)[e.out]+a);
1097      else 
1098//      flow->set(e.in, flow->get(e.in)-a);
1099        flow->set(e.in, (*flow)[e.in]-a);
1100    }
1101
1102    Number resCap(const Edge& e) const {
1103      if (e.out_or_in)
1104//      return (capacity->get(e.out)-flow->get(e.out));
1105        return ((*capacity)[e.out]-(*flow)[e.out]);
1106      else
1107//      return (flow->get(e.in));
1108        return ((*flow)[e.in]);
1109    }
1110
1111    Number resCap(GraphOutEdgeIt out) const {
1112//      return (capacity->get(out)-flow->get(out));
1113      return ((*capacity)[out]-(*flow)[out]);
1114    }
1115   
1116    Number resCap(GraphInEdgeIt in) const {
1117//      return (flow->get(in));
1118      return ((*flow)[in]);
1119    }
1120
1121//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1122//     public:
1123//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1124//      : Graph::NodeMap<T>(_G.gw) { }
1125//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1126//            T a) : Graph::NodeMap<T>(_G.gw, a) { }
1127//     };
1128
1129//     template <typename T>
1130//     class NodeMap {
1131//       typename Graph::NodeMap<T> node_map;
1132//     public:
1133//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1134//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1135//       void set(Node nit, T a) { node_map.set(nit, a); }
1136//       T get(Node nit) const { return node_map.get(nit); }
1137//     };
1138
1139    template <typename T>
1140    class EdgeMap {
1141      typename Graph::EdgeMap<T> forward_map, backward_map;
1142    public:
1143      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1144      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1145      void set(Edge e, T a) {
1146        if (e.out_or_in)
1147          forward_map.set(e.out, a);
1148        else
1149          backward_map.set(e.in, a);
1150      }
1151      T operator[](Edge e) const {
1152        if (e.out_or_in)
1153          return forward_map[e.out];
1154        else
1155          return backward_map[e.in];
1156      }
1157//       T get(Edge e) const {
1158//      if (e.out_or_in)
1159//        return forward_map.get(e.out);
1160//      else
1161//        return backward_map.get(e.in);
1162//       }
1163    };
1164  };
1165
1166  //ErasingFirstGraphWrapper for blocking flows
1167  template<typename Graph, typename FirstOutEdgesMap>
1168  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1169  protected:
1170    FirstOutEdgesMap* first_out_edges;
1171  public:
1172    typedef typename GraphWrapper<Graph>::Node Node;
1173    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1174    typedef typename GraphWrapper<Graph>::Edge Edge;
1175    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1176    typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
1177    typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
1178
1179    ErasingFirstGraphWrapper(Graph& _graph,
1180                             FirstOutEdgesMap& _first_out_edges) :
1181      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1182
1183    template<typename I> I& first(I& i) const {
1184      graph->first(i);
1185      return i;
1186    }
1187    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1188//      e=first_out_edges->get(n);
1189      e=(*first_out_edges)[n];
1190      return e;
1191    }
1192    template<typename I, typename P> I& first(I& i, const P& p) const {
1193      graph->first(i, p);
1194      return i;
1195    }
1196   
1197    //template<typename I> I getNext(const I& i) const {
1198    //  return gw.getNext(i);
1199    //}
1200    template<typename I> I& next(I &i) const {
1201      graph->next(i);
1202      return i;
1203    }
1204   
1205    template< typename It > It first() const {
1206      It e; this->first(e); return e; }
1207   
1208    template< typename It > It first(const Node& v) const {
1209      It e; this->first(e, v); return e; }
1210
1211    void erase(const OutEdgeIt& e) const {
1212      OutEdgeIt f=e;
1213      this->next(f);
1214      first_out_edges->set(this->tail(e), f);
1215    }
1216  };
1217
1218// // FIXME: comparison should be made better!!!
1219//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1220//   class ResGraphWrapper
1221//   {
1222//     Graph* graph;
1223 
1224//   public:
1225//     typedef Graph ParentGraph;
1226
1227//     typedef typename Graph::Node Node;
1228//     typedef typename Graph::Edge Edge;
1229 
1230//     typedef typename Graph::NodeIt NodeIt;
1231   
1232//     class OutEdgeIt {
1233//     public:
1234//       //Graph::Node n;
1235//       bool out_or_in;
1236//       typename Graph::OutEdgeIt o;
1237//       typename Graph::InEdgeIt i;   
1238//     };
1239//     class InEdgeIt {
1240//     public:
1241//       //Graph::Node n;
1242//       bool out_or_in;
1243//       typename Graph::OutEdgeIt o;
1244//       typename Graph::InEdgeIt i;   
1245//     };
1246//     typedef typename Graph::SymEdgeIt SymEdgeIt;
1247//     typedef typename Graph::EdgeIt EdgeIt;
1248
1249//     int nodeNum() const { return gw.nodeNum(); }
1250//     int edgeNum() const { return gw.edgeNum(); }
1251
1252//     Node& first(Node& n) const { return gw.first(n); }
1253
1254//     // Edge and SymEdge  is missing!!!!
1255//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
1256
1257//     //FIXME
1258//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1259//       {
1260//      e.n=n;
1261//      gw.first(e.o,n);
1262//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1263//        gw.goNext(e.o);
1264//      if(!gw.valid(e.o)) {
1265//        gw.first(e.i,n);
1266//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1267//          gw.goNext(e.i);
1268//      }
1269//      return e;
1270//       }
1271// /*
1272//   OutEdgeIt &goNext(OutEdgeIt &e)
1273//   {
1274//   if(gw.valid(e.o)) {
1275//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1276//   gw.goNext(e.o);
1277//   if(gw.valid(e.o)) return e;
1278//   else gw.first(e.i,e.n);
1279//   }
1280//   else {
1281//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1282//   gw.goNext(e.i);
1283//   return e;
1284//   }
1285//   }
1286//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1287// */
1288//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1289
1290//     //FIXME
1291//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
1292//       {
1293//      e.n=n;
1294//      gw.first(e.i,n);
1295//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1296//        gw.goNext(e.i);
1297//      if(!gw.valid(e.i)) {
1298//        gw.first(e.o,n);
1299//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1300//          gw.goNext(e.o);
1301//      }
1302//      return e;
1303//       }
1304// /*
1305//   InEdgeIt &goNext(InEdgeIt &e)
1306//   {
1307//   if(gw.valid(e.i)) {
1308//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1309//   gw.goNext(e.i);
1310//   if(gw.valid(e.i)) return e;
1311//   else gw.first(e.o,e.n);
1312//   }
1313//   else {
1314//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1315//   gw.goNext(e.o);
1316//   return e;
1317//   }
1318//   }
1319//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1320// */
1321//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1322
1323//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1324//     //template<typename I> I next(const I i); { return gw.goNext(i); }
1325
1326//     template< typename It > It first() const {
1327//       It e; first(e); return e; }
1328
1329//     template< typename It > It first(Node v) const {
1330//       It e; first(e, v); return e; }
1331
1332//     Node head(const Edge& e) const { return gw.head(e); }
1333//     Node tail(const Edge& e) const { return gw.tail(e); }
1334 
1335//     template<typename I> Node aNode(const I& e) const {
1336//       return gw.aNode(e); }
1337//     template<typename I> Node bNode(const I& e) const {
1338//       return gw.bNode(e); }
1339 
1340//     //template<typename I> bool valid(const I i);
1341//     //{ return gw.valid(i); }
1342 
1343//     //template<typename I> void setInvalid(const I &i);
1344//     //{ return gw.setInvalid(i); }
1345 
1346//     Node addNode() { return gw.addNode(); }
1347//     Edge addEdge(const Node& tail, const Node& head) {
1348//       return gw.addEdge(tail, head); }
1349 
1350//     template<typename I> void erase(const I& i) { gw.erase(i); }
1351 
1352//     void clear() { gw.clear(); }
1353 
1354//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1355//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1356 
1357//     void setGraph(Graph& _graph) { graph = &_graph; }
1358//     Graph& getGraph() { return (*graph); }
1359
1360//     //ResGraphWrapper() : graph(0) { }
1361//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1362//   };
1363
1364} //namespace hugo
1365
1366#endif //HUGO_GRAPH_WRAPPER_H
1367
Note: See TracBrowser for help on using the repository browser.