COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 231:f62f11c9e6df

Last change on this file since 231:f62f11c9e6df was 231:f62f11c9e6df, checked in by marci, 20 years ago

.

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