COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 312:54e07057eb47

Last change on this file since 312:54e07057eb47 was 312:54e07057eb47, checked in by marci, 21 years ago

gw

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