COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 265:bf7aea53635a

Last change on this file since 265:bf7aea53635a was 265:bf7aea53635a, checked in by marci, 21 years ago

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