COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 311:6635b11938fe

Last change on this file since 311:6635b11938fe was 311:6635b11938fe, checked in by marci, 17 years ago

gw

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