lemon-0.x: src/work/marci/experiment/graph_wrapper

     1 // -*- c++ -*-

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     7 namespace hugo {

     9   template<typename Graph>

    10   class TrivGraphWrapper {

    11   protected:

    12     Graph* graph;

    14   public:

    15     typedef Graph BaseGraph;

    17     typedef typename Graph::Node Node;

    18     class NodeIt : public Graph::NodeIt {

    19     public:

    20       NodeIt() { }

    21       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

    22       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

    23       NodeIt(const TrivGraphWrapper<Graph>& _G) :

    24 	Graph::NodeIt(*(_G.graph)) { }

    25     };

    26     typedef typename Graph::Edge Edge;

    27     //typedef typename Graph::OutEdgeIt OutEdgeIt;

    28     class OutEdgeIt : public Graph::OutEdgeIt {

    29     public:

    30       OutEdgeIt() { }

    31       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

    32       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

    33       OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :

    34 	Graph::OutEdgeIt(*(_G.graph), n) { }

    35     };

    36     //typedef typename Graph::InEdgeIt InEdgeIt;

    37     class InEdgeIt : public Graph::InEdgeIt {

    38     public:

    39       InEdgeIt() { }

    40       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

    41       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

    42       InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :

    43 	Graph::InEdgeIt(*(_G.graph), n) { }

    44     };

    45     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    46     //typedef typename Graph::EdgeIt EdgeIt;

    47     class EdgeIt : public Graph::EdgeIt {

    48     public:

    49       EdgeIt() { }

    50       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

    51       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

    52       EdgeIt(const TrivGraphWrapper<Graph>& _G) :

    53 	Graph::EdgeIt(*(_G.graph)) { }

    54     };

    56     //TrivGraphWrapper() : graph(0) { }

    57     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }

    59 //    void setGraph(Graph& _graph) { graph = &_graph; }

    60 //    Graph& getGraph() const { return (*graph); }

    62     NodeIt& first(NodeIt& i) const {

    63       i=NodeIt(*this);

    64       return i;

    65     }

    66     EdgeIt& first(EdgeIt& i) const {

    67       i=EdgeIt(*this);

    68       return i;

    69     }

    70 //     template<typename I> I& first(I& i) const {

    71 //       //return graph->first(i);

    72 //       i=I(*this);

    73 //       return i;

    74 //     }

    75     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

    76       i=OutEdgeIt(*this, p);

    77       return i;

    78     }

    79     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

    80       i=InEdgeIt(*this, p);

    81       return i;

    82     }

    83 //     template<typename I, typename P> I& first(I& i, const P& p) const {

    84 //       //return graph->first(i, p);

    85 //       i=I(*this, p);

    86 //       return i;

    87 //     }

    89 //    template<typename I> I getNext(const I& i) const {

    90 //      return graph->getNext(i); }

    91     template<typename I> I& next(I &i) const { graph->next(i); return i; }

    93     template< typename It > It first() const {

    94       It e; first(e); return e; }

    96     template< typename It > It first(const Node& v) const {

    97       It e; first(e, v); return e; }

    99     Node head(const Edge& e) const { return graph->head(e); }

   100     Node tail(const Edge& e) const { return graph->tail(e); }

   102     template<typename I> bool valid(const I& i) const

   103       { return graph->valid(i); }

   105     //template<typename I> void setInvalid(const I &i);

   106     //{ return graph->setInvalid(i); }

   108     int nodeNum() const { return graph->nodeNum(); }

   109     int edgeNum() const { return graph->edgeNum(); }

   111     template<typename I> Node aNode(const I& e) const {

   112       return graph->aNode(e); }

   113     template<typename I> Node bNode(const I& e) const {

   114       return graph->bNode(e); }

   116     Node addNode() const { return graph->addNode(); }

   117     Edge addEdge(const Node& tail, const Node& head) const {

   118       return graph->addEdge(tail, head); }

   120     template<typename I> void erase(const I& i) const { graph->erase(i); }

   122     void clear() const { graph->clear(); }

   124     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   125     public:

   126       NodeMap(const TrivGraphWrapper<Graph>& _G) :

   127 	Graph::NodeMap<T>(*(_G.graph)) { }

   128       NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :

   129 	Graph::NodeMap<T>(*(_G.graph), a) { }

   130     };

   132     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   133     public:

   134       EdgeMap(const TrivGraphWrapper<Graph>& _G) :

   135 	Graph::EdgeMap<T>(*(_G.graph)) { }

   136       EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :

   137 	Graph::EdgeMap<T>(*(_G.graph), a) { }

   138     };

   140     template<typename Map, typename T> class NodeMapWrapper {

   141     protected:

   142       Map* map;

   143     public:

   144       NodeMapWrapper(Map& _map) : map(&_map) { }

   145       //template<typename T>

   146       void set(Node n, T a) { map->set(n, a); }

   147       //template<typename T>

   148       T get(Node n) const { return map->get(n); }

   149     };

   151     template<typename Map, typename T> class EdgeMapWrapper {

   152     protected:

   153       Map* map;

   154     public:

   155       EdgeMapWrapper(Map& _map) : map(&_map) { }

   156       //template<typename T>

   157       void set(Edge n, T a) { map->set(n, a); }

   158       //template<typename T>

   159       T get(Edge n) const { return map->get(n); }

   160     };

   161   };

   163   template<typename GraphWrapper>

   164   class GraphWrapperSkeleton {

   165   protected:

   166     GraphWrapper gw;

   168   public:

   169     //typedef typename GraphWrapper::BaseGraph BaseGraph;

   171 //     typedef typename GraphWrapper::Node Node;

   172 //     typedef typename GraphWrapper::NodeIt NodeIt;

   174 //     typedef typename GraphWrapper::Edge Edge;

   175 //     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   176 //     typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   177 //     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   178 //     typedef typename GraphWrapper::EdgeIt EdgeIt;

   180     typedef typename GraphWrapper::Node Node;

   181     class NodeIt : public GraphWrapper::NodeIt {

   182     public:

   183       NodeIt() { }

   184       NodeIt(const typename GraphWrapper::NodeIt& n) :

   185 	GraphWrapper::NodeIt(n) { }

   186       NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }

   187       NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   188 	GraphWrapper::NodeIt(_G.gw) { }

   189     };

   190     typedef typename GraphWrapper::Edge Edge;

   191     //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   192     class OutEdgeIt : public GraphWrapper::OutEdgeIt {

   193     public:

   194       OutEdgeIt() { }

   195       OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :

   196 	GraphWrapper::OutEdgeIt(e) { }

   197       OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }

   198       OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :

   199 	GraphWrapper::OutEdgeIt(_G.gw, n) { }

   200     };

   201     //typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   202     class InEdgeIt : public GraphWrapper::InEdgeIt {

   203     public:

   204       InEdgeIt() { }

   205       InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :

   206 	GraphWrapper::InEdgeIt(e) { }

   207       InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }

   208       InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :

   209 	GraphWrapper::InEdgeIt(_G.gw, n) { }

   210     };

   211     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   212     //typedef typename GraphWrapper::EdgeIt EdgeIt;

   213     class EdgeIt : public GraphWrapper::EdgeIt {

   214     public:

   215       EdgeIt() { }

   216       EdgeIt(const typename GraphWrapper::EdgeIt& e) :

   217 	GraphWrapper::EdgeIt(e) { }

   218       EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }

   219       EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   220 	GraphWrapper::EdgeIt(_G.gw) { }

   221     };

   224     //GraphWrapperSkeleton() : gw() { }

   225     GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }

   227     //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }

   228     //BaseGraph& getGraph() const { return gw.getGraph(); }

   230     template<typename I> I& first(I& i) const {

   231       i=I(*this);

   232       return i;

   233     }

   234     template<typename I, typename P> I& first(I& i, const P& p) const {

   235       i=I(*this, p);

   236       return i;

   237     }

   239 //    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }

   240     template<typename I> I& next(I &i) const { gw.next(i); return i; }

   242     template< typename It > It first() const {

   243       It e; this->first(e); return e; }

   245     template< typename It > It first(const Node& v) const {

   246       It e; this->first(e, v); return e; }

   248     Node head(const Edge& e) const { return gw.head(e); }

   249     Node tail(const Edge& e) const { return gw.tail(e); }

   251     template<typename I> bool valid(const I& i) const { return gw.valid(i); }

   253     //template<typename I> void setInvalid(const I &i);

   254     //{ return graph->setInvalid(i); }

   256     int nodeNum() const { return gw.nodeNum(); }

   257     int edgeNum() const { return gw.edgeNum(); }

   259     template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }

   260     template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }

   262     Node addNode() const { return gw.addNode(); }

   263     Edge addEdge(const Node& tail, const Node& head) const {

   264       return gw.addEdge(tail, head); }

   266     template<typename I> void erase(const I& i) const { gw.erase(i); }

   268     void clear() const { gw.clear(); }

   270     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   271     public:

   272       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   273 	GraphWrapper::NodeMap<T>(_G.gw) { }

   274       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :

   275 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

   276     };

   278     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {

   279     public:

   280       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   281 	GraphWrapper::EdgeMap<T>(_G.gw) { }

   282       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :

   283 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

   284     };

   285   };

   287   template<typename GraphWrapper>

   288   class GraphWrapperSkeleton1 {

   289   protected:

   290     GraphWrapper* g;

   292   public:

   293     //typedef typename GraphWrapper::BaseGraph BaseGraph;

   295 //     typedef typename GraphWrapper::Node Node;

   296 //     typedef typename GraphWrapper::NodeIt NodeIt;

   298 //     typedef typename GraphWrapper::Edge Edge;

   299 //     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   300 //     typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   301 //     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   302 //     typedef typename GraphWrapper::EdgeIt EdgeIt;

   304     typedef typename GraphWrapper::Node Node;

   305     class NodeIt : public GraphWrapper::NodeIt {

   306     public:

   307       NodeIt() { }

   308       NodeIt(const typename GraphWrapper::NodeIt& n) :

   309 	GraphWrapper::NodeIt(n) { }

   310       NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }

   311       NodeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) :

   312 	GraphWrapper::NodeIt(*(_G.g)) { }

   313     };

   314     typedef typename GraphWrapper::Edge Edge;

   315     //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   316     class OutEdgeIt : public GraphWrapper::OutEdgeIt {

   317     public:

   318       OutEdgeIt() { }

   319       OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :

   320 	GraphWrapper::OutEdgeIt(e) { }

   321       OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }

   322       OutEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) :

   323 	GraphWrapper::OutEdgeIt(*(_G.g), n) { }

   324     };

   325     //typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   326     class InEdgeIt : public GraphWrapper::InEdgeIt {

   327     public:

   328       InEdgeIt() { }

   329       InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :

   330 	GraphWrapper::InEdgeIt(e) { }

   331       InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }

   332       InEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) :

   333 	GraphWrapper::InEdgeIt(*(_G.g), n) { }

   334     };

   335     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   336     //typedef typename GraphWrapper::EdgeIt EdgeIt;

   337     class EdgeIt : public GraphWrapper::EdgeIt {

   338     public:

   339       EdgeIt() { }

   340       EdgeIt(const typename GraphWrapper::EdgeIt& e) :

   341 	GraphWrapper::EdgeIt(e) { }

   342       EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }

   343       EdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) :

   344 	GraphWrapper::EdgeIt(*(_G.g)) { }

   345     };

   348     //GraphWrapperSkeleton() : gw() { }

   349     GraphWrapperSkeleton1(GraphWrapper& _gw) : g(&_gw) { }

   351     //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }

   352     //BaseGraph& getGraph() const { return gw.getGraph(); }

   354     template<typename I> I& first(I& i) const {

   355       i=I(*this);

   356       return i;

   357     }

   358     template<typename I, typename P> I& first(I& i, const P& p) const {

   359       i=I(*this, p);

   360       return i;

   361     }

   363 //    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }

   364     template<typename I> I& next(I &i) const { g->next(i); return i; }

   366     template< typename It > It first() const {

   367       It e; this->first(e); return e; }

   369     template< typename It > It first(const Node& v) const {

   370       It e; this->first(e, v); return e; }

   372     Node head(const Edge& e) const { return g->head(e); }

   373     Node tail(const Edge& e) const { return g->tail(e); }

   375     template<typename I> bool valid(const I& i) const { return g->valid(i); }

   377     //template<typename I> void setInvalid(const I &i);

   378     //{ return graph->setInvalid(i); }

   380     int nodeNum() const { return g->nodeNum(); }

   381     int edgeNum() const { return g->edgeNum(); }

   383     template<typename I> Node aNode(const I& e) const { return g->aNode(e); }

   384     template<typename I> Node bNode(const I& e) const { return g->bNode(e); }

   386     Node addNode() const { return g->addNode(); }

   387     Edge addEdge(const Node& tail, const Node& head) const {

   388       return g->addEdge(tail, head); }

   390     template<typename I> void erase(const I& i) const { g->erase(i); }

   392     void clear() const { g->clear(); }

   394     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   395     public:

   396       NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) :

   397 	GraphWrapper::NodeMap<T>(*(_G.g)) { }

   398       NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) :

   399 	GraphWrapper::NodeMap<T>(*(_G.g), a) { }

   400     };

   402     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {

   403     public:

   404       EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) :

   405 	GraphWrapper::EdgeMap<T>(*(_G.g)) { }

   406       EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) :

   407 	GraphWrapper::EdgeMap<T>(*(_G.g), a) { }

   408     };

   409   };

   412 //   template<typename Graph>

   413 //   class RevGraphWrapper

   414 //   {

   415 //   protected:

   416 //     Graph* graph;

   418 //   public:

   419 //     typedef Graph BaseGraph;

   421 //     typedef typename Graph::Node Node;

   422 //     typedef typename Graph::NodeIt NodeIt;

   424 //     typedef typename Graph::Edge Edge;

   425 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   426 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   427 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   428 //     typedef typename Graph::EdgeIt EdgeIt;

   430 //     //RevGraphWrapper() : graph(0) { }

   431 //     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }

   433 //     void setGraph(Graph& _graph) { graph = &_graph; }

   434 //     Graph& getGraph() const { return (*graph); }

   436 //     template<typename I> I& first(I& i) const { return graph->first(i); }

   437 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   438 //       return graph->first(i, p); }

   440 //     template<typename I> I getNext(const I& i) const {

   441 //       return graph->getNext(i); }

   442 //     template<typename I> I& next(I &i) const { return graph->next(i); }

   444 //     template< typename It > It first() const {

   445 //       It e; first(e); return e; }

   447 //     template< typename It > It first(const Node& v) const {

   448 //       It e; first(e, v); return e; }

   450 //     Node head(const Edge& e) const { return graph->tail(e); }

   451 //     Node tail(const Edge& e) const { return graph->head(e); }

   453 //     template<typename I> bool valid(const I& i) const

   454 //       { return graph->valid(i); }

   456 //     //template<typename I> void setInvalid(const I &i);

   457 //     //{ return graph->setInvalid(i); }

   459 //     template<typename I> Node aNode(const I& e) const {

   460 //       return graph->aNode(e); }

   461 //     template<typename I> Node bNode(const I& e) const {

   462 //       return graph->bNode(e); }

   464 //     Node addNode() const { return graph->addNode(); }

   465 //     Edge addEdge(const Node& tail, const Node& head) const {

   466 //       return graph->addEdge(tail, head); }

   468 //     int nodeNum() const { return graph->nodeNum(); }

   469 //     int edgeNum() const { return graph->edgeNum(); }

   471 //     template<typename I> void erase(const I& i) const { graph->erase(i); }

   473 //     void clear() const { graph->clear(); }

   475 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   476 //     public:

   477 //       NodeMap(const RevGraphWrapper<Graph>& _G) :

   478 // 	Graph::NodeMap<T>(_G.getGraph()) { }

   479 //       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :

   480 // 	Graph::NodeMap<T>(_G.getGraph(), a) { }

   481 //     };

   483 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   484 //     public:

   485 //       EdgeMap(const RevGraphWrapper<Graph>& _G) :

   486 // 	Graph::EdgeMap<T>(_G.getGraph()) { }

   487 //       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :

   488 // 	Graph::EdgeMap<T>(_G.getGraph(), a) { }

   489 //     };

   490 //   };

   492 //   template<typename /*Graph*/GraphWrapper

   493 //   /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >

   494 //   class RevGraphWrapper :

   495 //     public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {

   496 //   protected:

   497 //     //Graph* graph;

   499 //   public:

   500 //     //typedef Graph BaseGraph;

   502 //     //typedef typename Graph::Node Node;

   503 //     //typedef typename Graph::NodeIt NodeIt;

   505 //     //typedef typename Graph::Edge Edge;

   506 //     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;

   507 //     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;

   508 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   509 //     //typedef typename Graph::EdgeIt EdgeIt;

   511 //     //RevGraphWrapper() : graph(0) { }

   512 //     RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }

   514 //     //void setGraph(Graph& _graph) { graph = &_graph; }

   515 //     //Graph& getGraph() const { return (*graph); }

   517 //     //template<typename I> I& first(I& i) const { return graph->first(i); }

   518 //     //template<typename I, typename P> I& first(I& i, const P& p) const {

   519 //     //  return graph->first(i, p); }

   521 //     //template<typename I> I getNext(const I& i) const {

   522 //     //  return graph->getNext(i); }

   523 //     //template<typename I> I& next(I &i) const { return graph->next(i); }

   525 //     //template< typename It > It first() const {

   526 //     //  It e; first(e); return e; }

   528 //     //template< typename It > It first(const Node& v) const {

   529 //     //  It e; first(e, v); return e; }

   531 //     //Node head(const Edge& e) const { return graph->tail(e); }

   532 //     //Node tail(const Edge& e) const { return graph->head(e); }

   534 //     //template<typename I> bool valid(const I& i) const

   535 //     //  { return graph->valid(i); }

   537 //     //template<typename I> void setInvalid(const I &i);

   538 //     //{ return graph->setInvalid(i); }

   540 //     //template<typename I> Node aNode(const I& e) const {

   541 //     //  return graph->aNode(e); }

   542 //     //template<typename I> Node bNode(const I& e) const {

   543 //     //  return graph->bNode(e); }

   545 //     //Node addNode() const { return graph->addNode(); }

   546 //     //Edge addEdge(const Node& tail, const Node& head) const {

   547 //     //  return graph->addEdge(tail, head); }

   549 //     //int nodeNum() const { return graph->nodeNum(); }

   550 //     //int edgeNum() const { return graph->edgeNum(); }

   552 //     //template<typename I> void erase(const I& i) const { graph->erase(i); }

   554 //     //void clear() const { graph->clear(); }

   556 //     template<typename T> class NodeMap :

   557 //       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>

   558 //     {

   559 //     public:

   560 //       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :

   561 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }

   562 //       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :

   563 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }

   564 //     };

   566 //     template<typename T> class EdgeMap :

   567 //       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {

   568 //     public:

   569 //       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :

   570 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }

   571 //       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :

   572 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }

   573 //     };

   574 //   };

   576   template<typename GraphWrapper>

   577   class RevGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {

   578   public:

   579     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;

   580     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;

   581     //FIXME

   582     //If GraphWrapper::OutEdgeIt is not defined

   583     //and we do not want to use RevGraphWrapper::InEdgeIt,

   584     //this won't work, because of typedef

   585     //OR

   586     //graphs have to define their non-existing iterators to void

   587     //Unfortunately all the typedefs are instantiated in templates,

   588     //unlike other stuff

   589     typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt InEdgeIt;

   590     typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt OutEdgeIt;

   592     RevGraphWrapper(GraphWrapper& _gw) :

   593       GraphWrapperSkeleton1<GraphWrapper>(_gw) { }

   595     Node head(const Edge& e) const

   596       { return GraphWrapperSkeleton1<GraphWrapper>::tail(e); }

   597     Node tail(const Edge& e) const

   598       { return GraphWrapperSkeleton1<GraphWrapper>::head(e); }

   599   };

   601   //Subgraph on the same node-set and partial edge-set

   602   template<typename GraphWrapper, typename EdgeFilterMap>

   603   class SubGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {

   604   protected:

   605     EdgeFilterMap* filter_map;

   606   public:

   607     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;

   608     typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;

   609     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;

   610     typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt;

   611     typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt;

   612     typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt;

   614     SubGraphWrapper(GraphWrapper& _gw, EdgeFilterMap& _filter_map) :

   615       GraphWrapperSkeleton1<GraphWrapper>(_gw), filter_map(&_filter_map) { }

   617     template<typename I> I& first(I& i) const {

   618       g->first(i);

   619       while (g->valid(i) && !filter_map->get(i)) { g->next(i); }

   620       return i;

   621     }

   622     template<typename I, typename P> I& first(I& i, const P& p) const {

   623       g->first(i, p);

   624       while (g->valid(i) && !filter_map->get(i)) { g->next(i); }

   625       return i;

   626     }

   628     //template<typename I> I getNext(const I& i) const {

   629     //  return gw.getNext(i);

   630     //}

   631     template<typename I> I& next(I &i) const {

   632       g->next(i);

   633       while (g->valid(i) && !filter_map->get(i)) { g->next(i); }

   634       return i;

   635     }

   637     template< typename It > It first() const {

   638       It e; this->first(e); return e; }

   640     template< typename It > It first(const Node& v) const {

   641       It e; this->first(e, v); return e; }

   642   };

   644 //   template<typename GraphWrapper>

   645 //   class UndirGraphWrapper {

   646 //   protected:

   647 //     //Graph* graph;

   648 //     GraphWrapper gw;

   650 //   public:

   651 //     typedef GraphWrapper BaseGraph;

   653 //     typedef typename GraphWrapper::Node Node;

   654 //     typedef typename GraphWrapper::NodeIt NodeIt;

   656 //     //typedef typename Graph::Edge Edge;

   657 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   658 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   659 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   660 //     //typedef typename Graph::EdgeIt EdgeIt;

   662 //     //private:

   663 //     typedef typename GraphWrapper::Edge GraphEdge;

   664 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   665 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   666 //     //public:

   668 //     //UndirGraphWrapper() : graph(0) { }

   669 //     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

   671 //     //void setGraph(Graph& _graph) { graph = &_graph; }

   672 //     //Graph& getGraph() const { return (*graph); }

   674 //     class Edge {

   675 //       friend class UndirGraphWrapper<GraphWrapper>;

   676 //       bool out_or_in; //true iff out

   677 //       GraphOutEdgeIt out;

   678 //       GraphInEdgeIt in;

   679 //     public:

   680 //       Edge() : out_or_in(), out(), in() { }

   681 //       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

   682 //       operator GraphEdge() const {

   683 // 	if (out_or_in) return(out); else return(in);

   684 //       }

   685 //       friend bool operator==(const Edge& u, const Edge& v) {

   686 // 	if (v.out_or_in)

   687 // 	  return (u.out_or_in && u.out==v.out);

   688 // 	else

   689 // 	  return (!u.out_or_in && u.in==v.in);

   690 //       }

   691 //       friend bool operator!=(const Edge& u, const Edge& v) {

   692 // 	if (v.out_or_in)

   693 // 	  return (!u.out_or_in || u.out!=v.out);

   694 // 	else

   695 // 	  return (u.out_or_in || u.in!=v.in);

   696 //       }

   697 //     };

   699 //     class OutEdgeIt : public Edge {

   700 //       friend class UndirGraphWrapper<GraphWrapper>;

   701 //     public:

   702 //       OutEdgeIt() : Edge() { }

   703 //       OutEdgeIt(const Invalid& i) : Edge(i) { }

   704 //       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)

   705 // 	: Edge() {

   706 // 	out_or_in=true;

   707 // 	_G.gw.first(out, n);

   708 // 	if (!(_G.gw.valid(out))) {

   709 // 	  out_or_in=false;

   710 // 	  _G.gw.first(in, n);

   711 // 	}

   712 //       }

   713 //     };

   715 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

   716 //       e.out_or_in=true;

   717 //       gw.first(e.out, n);

   718 //       if (!(gw.valid(e.out))) {

   719 // 	e.out_or_in=false;

   720 // 	gw.first(e.in, n);

   721 //       }

   722 //       return e;

   723 //     }

   725 //     OutEdgeIt& next(OutEdgeIt& e) const {

   726 //       if (e.out_or_in) {

   727 // 	Node n=gw.tail(e.out);

   728 // 	gw.next(e.out);

   729 // 	if (!gw.valid(e.out)) {

   730 // 	  e.out_or_in=false;

   731 // 	  gw.first(e.in, n);

   732 // 	}

   733 //       } else {

   734 // 	gw.next(e.in);

   735 //       }

   736 //       return e;

   737 //     }

   739 //     Node aNode(const OutEdgeIt& e) const {

   740 //       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }

   741 //     Node bNode(const OutEdgeIt& e) const {

   742 //       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }

   744 //     typedef OutEdgeIt InEdgeIt;

   746 //     template<typename I> I& first(I& i) const { return gw.first(i); }

   747 // //     template<typename I, typename P> I& first(I& i, const P& p) const {

   748 // //       return graph->first(i, p); }

   750 //     template<typename I> I getNext(const I& i) const {

   751 //       return gw.getNext(i); }

   752 //     template<typename I> I& next(I &i) const { return gw.next(i); }

   754 //     template< typename It > It first() const {

   755 //       It e; first(e); return e; }

   757 //     template< typename It > It first(const Node& v) const {

   758 //       It e; first(e, v); return e; }

   760 //     Node head(const Edge& e) const { return gw.head(e); }

   761 //     Node tail(const Edge& e) const { return gw.tail(e); }

   763 //     template<typename I> bool valid(const I& i) const

   764 //       { return gw.valid(i); }

   766 //     //template<typename I> void setInvalid(const I &i);

   767 //     //{ return graph->setInvalid(i); }

   769 //     int nodeNum() const { return gw.nodeNum(); }

   770 //     int edgeNum() const { return gw.edgeNum(); }

   772 // //     template<typename I> Node aNode(const I& e) const {

   773 // //       return graph->aNode(e); }

   774 // //     template<typename I> Node bNode(const I& e) const {

   775 // //       return graph->bNode(e); }

   777 //     Node addNode() const { return gw.addNode(); }

   778 // // FIXME: ez igy nem jo, mert nem

   779 // //    Edge addEdge(const Node& tail, const Node& head) const {

   780 // //      return graph->addEdge(tail, head); }

   782 //     template<typename I> void erase(const I& i) const { gw.erase(i); }

   784 //     void clear() const { gw.clear(); }

   786 //     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   787 //     public:

   788 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   789 // 	GraphWrapper::NodeMap<T>(_G.gw) { }

   790 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   791 // 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

   792 //     };

   794 //     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {

   795 //     public:

   796 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   797 // 	GraphWrapper::EdgeMap<T>(_G.gw) { }

   798 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   799 // 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

   800 //     };

   801 //   };

   804   template<typename GraphWrapper>

   805   class UndirGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {

   806   protected:

   807 //    GraphWrapper gw;

   809   public:

   810     //typedef GraphWrapper BaseGraph;

   812     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;

   813     typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;

   815     //private:

   816     //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy

   817     //legyenek, at kell irni

   818     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   819     GraphWrapper::Edge GraphEdge;

   820     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   821     GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   822     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   823     GraphWrapper::InEdgeIt GraphInEdgeIt;

   824     //public:

   826     //UndirGraphWrapper() : graph(0) { }

   827     UndirGraphWrapper(GraphWrapper& _gw) :

   828       GraphWrapperSkeleton1<GraphWrapper>(_gw) { }

   830     //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

   832     //void setGraph(Graph& _graph) { graph = &_graph; }

   833     //Graph& getGraph() const { return (*graph); }

   835     class Edge {

   836       friend class UndirGraphWrapper<GraphWrapper>;

   837     protected:

   838       bool out_or_in; //true iff out

   839       GraphOutEdgeIt out;

   840       GraphInEdgeIt in;

   841     public:

   842       Edge() : out_or_in(), out(), in() { }

   843       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

   844       operator GraphEdge() const {

   845 	if (out_or_in) return(out); else return(in);

   846       }

   847 //FIXME

   848 //2 edges are equal if they "refer" to the same physical edge

   849 //is it good?

   850       friend bool operator==(const Edge& u, const Edge& v) {

   851 	if (v.out_or_in)

   852 	  if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);

   853 	//return (u.out_or_in && u.out==v.out);

   854 	else

   855 	  if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);

   856 	//return (!u.out_or_in && u.in==v.in);

   857       }

   858       friend bool operator!=(const Edge& u, const Edge& v) {

   859 	if (v.out_or_in)

   860 	  if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);

   861 	//return (!u.out_or_in || u.out!=v.out);

   862 	else

   863 	  if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);

   864 	//return (u.out_or_in || u.in!=v.in);

   865       }

   866     };

   868     class OutEdgeIt : public Edge {

   869       friend class UndirGraphWrapper<GraphWrapper>;

   870     public:

   871       OutEdgeIt() : Edge() { }

   872       OutEdgeIt(const Invalid& i) : Edge(i) { }

   873       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)

   874 	: Edge() {

   875 	out_or_in=true; _G.g->first(out, n);

   876 	if (!(_G.g->valid(out))) { out_or_in=false; _G.g->first(in, n);	}

   877       }

   878     };

   880     typedef OutEdgeIt InEdgeIt;

   882     class EdgeIt : public Edge {

   883       friend class UndirGraphWrapper<GraphWrapper>;

   884     protected:

   885       NodeIt v;

   886     public:

   887       EdgeIt() : Edge() { }

   888       EdgeIt(const Invalid& i) : Edge(i) { }

   889       EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)

   890 	: Edge() {

   891 	out_or_in=true;

   892 	//Node v;

   893 	_G.first(v);

   894 	if (_G.valid(v)) _G.g->first(out); else out=INVALID;

   895 	while (_G.valid(v) && !_G.g->valid(out)) {

   896 	  _G.g->next(v);

   897 	  if (_G.valid(v)) _G.g->first(out);

   898 	}

   899       }

   900     };

   902     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

   903       e.out_or_in=true; g->first(e.out, n);

   904       if (!(g->valid(e.out))) { e.out_or_in=false; g->first(e.in, n); }

   905       return e;

   906     }

   908     EdgeIt& first(EdgeIt& e) const {

   909       e.out_or_in=true;

   910       //NodeIt v;

   911       first(e.v);

   912       if (valid(e.v)) g->first(e.out, e.v); else e.out=INVALID;

   913       while (valid(e.v) && !g->valid(e.out)) {

   914 	g->next(e.v);

   915 	if (valid(e.v)) g->first(e.out, e.v);

   916       }

   917       return e;

   918     }

   920     template<typename I> I& first(I& i) const { g->first(i); return i; }

   921     template<typename I, typename P> I& first(I& i, const P& p) const {

   922       g->first(i, p); return i; }

   924     OutEdgeIt& next(OutEdgeIt& e) const {

   925       if (e.out_or_in) {

   926 	Node n=g->tail(e.out);

   927 	g->next(e.out);

   928 	if (!g->valid(e.out)) { e.out_or_in=false; g->first(e.in, n); }

   929       } else {

   930 	g->next(e.in);

   931       }

   932       return e;

   933     }

   935     EdgeIt& next(EdgeIt& e) const {

   936       //NodeIt v=tail(e);

   937       g->next(e.out);

   938       while (valid(e.v) && !g->valid(e.out)) {

   939 	next(e.v);

   940 	if (valid(e.v)) g->first(e.out, e.v);

   941       }

   942       return e;

   943     }

   945     template<typename I> I& next(I &i) const { return g->next(i); }

   946 //    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }

   948     template< typename It > It first() const {

   949       It e; first(e); return e; }

   951     template< typename It > It first(const Node& v) const {

   952       It e; first(e, v); return e; }

   954 //    Node head(const Edge& e) const { return gw.head(e); }

   955 //    Node tail(const Edge& e) const { return gw.tail(e); }

   957 //    template<typename I> bool valid(const I& i) const

   958 //      { return gw.valid(i); }

   960 //    int nodeNum() const { return gw.nodeNum(); }

   961 //    int edgeNum() const { return gw.edgeNum(); }

   963 //     template<typename I> Node aNode(const I& e) const {

   964 //       return graph->aNode(e); }

   965 //     template<typename I> Node bNode(const I& e) const {

   966 //       return graph->bNode(e); }

   968     Node aNode(const OutEdgeIt& e) const {

   969       if (e.out_or_in) return g->tail(e); else return g->head(e); }

   970     Node bNode(const OutEdgeIt& e) const {

   971       if (e.out_or_in) return g->head(e); else return g->tail(e); }

   973 //    Node addNode() const { return gw.addNode(); }

   975 // FIXME: ez igy nem jo, mert nem

   976 //    Edge addEdge(const Node& tail, const Node& head) const {

   977 //      return graph->addEdge(tail, head); }

   979 //    template<typename I> void erase(const I& i) const { gw.erase(i); }

   981 //    void clear() const { gw.clear(); }

   983 //     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   984 //     public:

   985 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   986 // 	GraphWrapper::NodeMap<T>(_G.gw) { }

   987 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   988 // 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

   989 //     };

   991 //     template<typename T> class EdgeMap :

   992 //       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {

   993 //     public:

   994 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   995 // 	GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }

   996 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   997 // 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

   998 //     };

   999    };

  1005 //   template<typename Graph>

  1006 //   class SymGraphWrapper

  1007 //   {

  1008 //     Graph* graph;

  1010 //   public:

  1011 //     typedef Graph BaseGraph;

  1013 //     typedef typename Graph::Node Node;

  1014 //     typedef typename Graph::Edge Edge;

  1016 //     typedef typename Graph::NodeIt NodeIt;

  1018 //     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon

  1019 //     //iranyitatlant, ami van

  1020 //     //mert csak 1 dolgot lehet be typedef-elni

  1021 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

  1022 //     //typedef typename Graph::InEdgeIt SymEdgeIt;

  1023 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1024 //     typedef typename Graph::EdgeIt EdgeIt;

  1026 //     int nodeNum() const { return graph->nodeNum(); }

  1027 //     int edgeNum() const { return graph->edgeNum(); }

  1029 //     template<typename I> I& first(I& i) const { return graph->first(i); }

  1030 //     template<typename I, typename P> I& first(I& i, const P& p) const {

  1031 //       return graph->first(i, p); }

  1032 //     //template<typename I> I next(const I i); { return graph->goNext(i); }

  1033 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }

  1035 //     template< typename It > It first() const {

  1036 //       It e; first(e); return e; }

  1038 //     template< typename It > It first(Node v) const {

  1039 //       It e; first(e, v); return e; }

  1041 //     Node head(const Edge& e) const { return graph->head(e); }

  1042 //     Node tail(const Edge& e) const { return graph->tail(e); }

  1044 //     template<typename I> Node aNode(const I& e) const {

  1045 //       return graph->aNode(e); }

  1046 //     template<typename I> Node bNode(const I& e) const {

  1047 //       return graph->bNode(e); }

  1049 //     //template<typename I> bool valid(const I i);

  1050 //     //{ return graph->valid(i); }

  1052 //     //template<typename I> void setInvalid(const I &i);

  1053 //     //{ return graph->setInvalid(i); }

  1055 //     Node addNode() { return graph->addNode(); }

  1056 //     Edge addEdge(const Node& tail, const Node& head) {

  1057 //       return graph->addEdge(tail, head); }

  1059 //     template<typename I> void erase(const I& i) { graph->erase(i); }

  1061 //     void clear() { graph->clear(); }

  1063 //     template<typename T> class NodeMap : public Graph::NodeMap<T> { };

  1064 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };

  1066 //     void setGraph(Graph& _graph) { graph = &_graph; }

  1067 //     Graph& getGraph() { return (*graph); }

  1069 //     //SymGraphWrapper() : graph(0) { }

  1070 //     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1071 //   };

  1074   template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>

  1075   class ResGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper>{

  1076   public:

  1077     //typedef Graph BaseGraph;

  1078     //typedef TrivGraphWrapper<const Graph> GraphWrapper;

  1079     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;

  1080     typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;

  1081   private:

  1082     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

  1083     GraphWrapper::OutEdgeIt OldOutEdgeIt;

  1084     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

  1085     GraphWrapper::InEdgeIt OldInEdgeIt;

  1086   protected:

  1087     //const Graph* graph;

  1088     //GraphWrapper gw;

  1089     FlowMap* flow;

  1090     const CapacityMap* capacity;

  1091   public:

  1093     ResGraphWrapper(GraphWrapper& _gw, FlowMap& _flow,

  1094 		    const CapacityMap& _capacity) :

  1095       GraphWrapperSkeleton1<GraphWrapper>(_gw),

  1096       flow(&_flow), capacity(&_capacity) { }

  1098     //void setGraph(const Graph& _graph) { graph = &_graph; }

  1099     //const Graph& getGraph() const { return (*graph); }

  1101     class Edge;

  1102     class OutEdgeIt;

  1103     friend class Edge;

  1104     friend class OutEdgeIt;

  1106     class Edge {

  1107       friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;

  1108     protected:

  1109       bool out_or_in; //true, iff out

  1110       OldOutEdgeIt out;

  1111       OldInEdgeIt in;

  1112     public:

  1113       Edge() : out_or_in(true) { }

  1114       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

  1115 //       bool valid() const {

  1116 // 	return out_or_in && out.valid() || in.valid(); }

  1117       friend bool operator==(const Edge& u, const Edge& v) {

  1118 	if (v.out_or_in)

  1119 	  return (u.out_or_in && u.out==v.out);

  1120 	else

  1121 	  return (!u.out_or_in && u.in==v.in);

  1122       }

  1123       friend bool operator!=(const Edge& u, const Edge& v) {

  1124 	if (v.out_or_in)

  1125 	  return (!u.out_or_in || u.out!=v.out);

  1126 	else

  1127 	  return (u.out_or_in || u.in!=v.in);

  1128       }

  1129     };

  1132     class OutEdgeIt : public Edge {

  1133       friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;

  1134     public:

  1135       OutEdgeIt() { }

  1136       //FIXME

  1137       OutEdgeIt(const Edge& e) : Edge(e) { }

  1138       OutEdgeIt(const Invalid& i) : Edge(i) { }

  1139     protected:

  1140       OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {

  1141 	resG.g->first(out, v);

  1142 	while( resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }

  1143 	if (!resG.g->valid(out)) {

  1144 	  out_or_in=0;

  1145 	  resG.g->first(in, v);

  1146 	  while( resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }

  1147 	}

  1148       }

  1149 //     public:

  1150 //       OutEdgeIt& operator++() {

  1151 // 	if (out_or_in) {

  1152 // 	  Node v=/*resG->*/G->aNode(out);

  1153 // 	  ++out;

  1154 // 	  while( out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1155 // 	  if (!out.valid()) {

  1156 // 	    out_or_in=0;

  1157 // 	    G->first(in, v);

  1158 // 	    while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1159 // 	  }

  1160 // 	} else {

  1161 // 	  ++in;

  1162 // 	  while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1163 // 	}

  1164 // 	return *this;

  1165 //       }

  1166     };

  1168     //FIXME This is just for having InEdgeIt

  1169     typedef void InEdgeIt;

  1171     class EdgeIt : public Edge {

  1172       friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;

  1173       NodeIt v;

  1174     public:

  1175       EdgeIt() { }

  1176       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }

  1177       EdgeIt(const Invalid& i) : Edge(i) { }

  1178       EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {

  1179 	resG.g->first(v);

  1180 	if (resG.g->valid(v)) resG.g->first(out, v); else out=INVALID;

  1181 	while (resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }

  1182 	while (resG.g->valid(v) && !resG.g->valid(out)) {

  1183 	  resG.g->next(v);

  1184 	  if (resG.g->valid(v)) resG.g->first(out, v);

  1185 	  while (resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }

  1186 	}

  1187 	if (!resG.g->valid(out)) {

  1188 	  out_or_in=0;

  1189 	  resG.g->first(v);

  1190 	  if (resG.g->valid(v)) resG.g->first(in, v); else in=INVALID;

  1191 	  while (resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }

  1192 	  while (resG.g->valid(v) && !resG.g->valid(in)) {

  1193 	    resG.g->next(v);

  1194 	    if (resG.g->valid(v)) resG.g->first(in, v);

  1195 	    while (resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }

  1196 	  }

  1197 	}

  1198       }

  1199 //       EdgeIt& operator++() {

  1200 // 	if (out_or_in) {

  1201 // 	  ++out;

  1202 // 	  while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1203 // 	  while (v.valid() && !out.valid()) {

  1204 // 	    ++v;

  1205 // 	    if (v.valid()) G->first(out, v);

  1206 // 	    while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1207 // 	  }

  1208 // 	  if (!out.valid()) {

  1209 // 	    out_or_in=0;

  1210 // 	    G->first(v);

  1211 // 	    if (v.valid()) G->first(in, v); else in=OldInEdgeIt();

  1212 // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1213 // 	    while (v.valid() && !in.valid()) {

  1214 // 	      ++v;

  1215 // 	      if (v.valid()) G->first(in, v);

  1216 // 	      while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1217 // 	    }

  1218 // 	  }

  1219 // 	} else {

  1220 // 	  ++in;

  1221 // 	  while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1222 // 	  while (v.valid() && !in.valid()) {

  1223 // 	    ++v;

  1224 // 	    if (v.valid()) G->first(in, v);

  1225 // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1226 // 	  }

  1227 // 	}

  1228 // 	return *this;

  1229 //       }

  1230     };

  1232     NodeIt& first(NodeIt& v) const { g->first(v); return v; }

  1233     OutEdgeIt& first(OutEdgeIt& e, Node v) const {

  1234       e=OutEdgeIt(*this, v);

  1235       return e;

  1236     }

  1237     EdgeIt& first(EdgeIt& e) const {

  1238       e=EdgeIt(*this);

  1239       return e;

  1240     }

  1242     NodeIt& next(NodeIt& n) const { return g->next(n); }

  1244     OutEdgeIt& next(OutEdgeIt& e) const {

  1245       if (e.out_or_in) {

  1246 	Node v=g->aNode(e.out);

  1247 	g->next(e.out);

  1248 	while( g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }

  1249 	if (!g->valid(e.out)) {

  1250 	  e.out_or_in=0;

  1251 	  g->first(e.in, v);

  1252 	  while( g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }

  1253 	}

  1254       } else {

  1255 	g->next(e.in);

  1256 	while( g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }

  1257       }

  1258       return e;

  1259     }

  1261     EdgeIt& next(EdgeIt& e) const {

  1262       if (e.out_or_in) {

  1263 	g->next(e.out);

  1264 	while (g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }

  1265 	  while (g->valid(e.v) && !g->valid(e.out)) {

  1266 	    g->next(e.v);

  1267 	    if (g->valid(e.v)) g->first(e.out, e.v);

  1268 	    while (g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }

  1269 	  }

  1270 	  if (!g->valid(e.out)) {

  1271 	    e.out_or_in=0;

  1272 	    g->first(e.v);

  1273 	    if (g->valid(e.v)) g->first(e.in, e.v); else e.in=INVALID;

  1274 	    while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }

  1275 	    while (g->valid(e.v) && !g->valid(e.in)) {

  1276 	      g->next(e.v);

  1277 	      if (g->valid(e.v)) g->first(e.in, e.v);

  1278 	      while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }

  1279 	    }

  1280 	  }

  1281 	} else {

  1282 	  g->next(e.in);

  1283 	  while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }

  1284 	  while (g->valid(e.v) && !g->valid(e.in)) {

  1285 	    g->next(e.v);

  1286 	    if (g->valid(e.v)) g->first(e.in, e.v);

  1287 	    while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }

  1288 	  }

  1289 	}

  1290 	return e;

  1291       }

  1294     template< typename It >

  1295     It first() const {

  1296       It e;

  1297       first(e);

  1298       return e;

  1299     }

  1301     template< typename It >

  1302     It first(Node v) const {

  1303       It e;

  1304       first(e, v);

  1305       return e;

  1306     }

  1308     Node tail(Edge e) const {

  1309       return ((e.out_or_in) ? g->aNode(e.out) : g->aNode(e.in)); }

  1310     Node head(Edge e) const {

  1311       return ((e.out_or_in) ? g->bNode(e.out) : g->bNode(e.in)); }

  1313     Node aNode(OutEdgeIt e) const {

  1314       return ((e.out_or_in) ? g->aNode(e.out) : g->aNode(e.in)); }

  1315     Node bNode(OutEdgeIt e) const {

  1316       return ((e.out_or_in) ? g->bNode(e.out) : g->bNode(e.in)); }

  1318     int nodeNum() const { return g->nodeNum(); }

  1319     //FIXME

  1320     //int edgeNum() const { return g->edgeNum(); }

  1323     int id(Node v) const { return g->id(v); }

  1325     bool valid(Node n) const { return g->valid(n); }

  1326     bool valid(Edge e) const {

  1327       return e.out_or_in ? g->valid(e.out) : g->valid(e.in); }

  1329     void augment(const Edge& e, Number a) const {

  1330       if (e.out_or_in)

  1331 	flow->set(e.out, flow->get(e.out)+a);

  1332       else

  1333 	flow->set(e.in, flow->get(e.in)-a);

  1334     }

  1336     Number resCap(const Edge& e) const {

  1337       if (e.out_or_in)

  1338 	return (capacity->get(e.out)-flow->get(e.out));

  1339       else

  1340 	return (flow->get(e.in));

  1341     }

  1343     Number resCap(OldOutEdgeIt out) const {

  1344       return (capacity->get(out)-flow->get(out));

  1345     }

  1347     Number resCap(OldInEdgeIt in) const {

  1348       return (flow->get(in));

  1349     }

  1351 //     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

  1352 //     public:

  1353 //       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)

  1354 // 	: GraphWrapper::NodeMap<T>(_G.gw) { }

  1355 //       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,

  1356 // 	      T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }

  1357 //     };

  1359 //     template <typename T>

  1360 //     class NodeMap {

  1361 //       typename Graph::NodeMap<T> node_map;

  1362 //     public:

  1363 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }

  1364 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }

  1365 //       void set(Node nit, T a) { node_map.set(nit, a); }

  1366 //       T get(Node nit) const { return node_map.get(nit); }

  1367 //     };

  1369     template <typename T>

  1370     class EdgeMap {

  1371       typename GraphWrapper::EdgeMap<T> forward_map, backward_map;

  1372     public:

  1373       EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }

  1374       EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }

  1375       void set(Edge e, T a) {

  1376 	if (e.out_or_in)

  1377 	  forward_map.set(e.out, a);

  1378 	else

  1379 	  backward_map.set(e.in, a);

  1380       }

  1381       T get(Edge e) {

  1382 	if (e.out_or_in)

  1383 	  return forward_map.get(e.out);

  1384 	else

  1385 	  return backward_map.get(e.in);

  1386       }

  1387     };

  1388   };

  1390   //Subgraph on the same node-set and partial edge-set

  1391   template<typename GraphWrapper, typename FirstOutEdgesMap>

  1392   class ErasingFirstGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {

  1393   protected:

  1394     FirstOutEdgesMap* first_out_edges;

  1395   public:

  1396     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;

  1397     typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;

  1398     typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;

  1399     typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt;

  1400     typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt;

  1401     typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt;

  1403     ErasingFirstGraphWrapper(GraphWrapper& _gw, FirstOutEdgesMap& _first_out_edges) :

  1404       GraphWrapperSkeleton1<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }

  1406     template<typename I> I& first(I& i) const {

  1407       g->first(i);

  1408       //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

  1409       return i;

  1410     }

  1411     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1412       e=first_out_edges->get(n);

  1413       return e;

  1414     }

  1415     template<typename I, typename P> I& first(I& i, const P& p) const {

  1416       g->first(i, p);

  1417       //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

  1418       return i;

  1419     }

  1421     //template<typename I> I getNext(const I& i) const {

  1422     //  return gw.getNext(i);

  1423     //}

  1424     template<typename I> I& next(I &i) const {

  1425       g->next(i);

  1426       //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

  1427       return i;

  1428     }

  1430     template< typename It > It first() const {

  1431       It e; this->first(e); return e; }

  1433     template< typename It > It first(const Node& v) const {

  1434       It e; this->first(e, v); return e; }

  1436     void erase(const OutEdgeIt& e) const {

  1437       OutEdgeIt f=e;

  1438       this->next(f);

  1439       first_out_edges->set(this->tail(e), f);

  1440     }

  1441   };

  1443 //   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1444 //   class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {

  1445 //   protected:

  1446 //     ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;

  1447 //     //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;

  1448 //   public:

  1449 //     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,

  1450 // 			   const CapacityMap& _capacity) :

  1451 //       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),

  1452 //       first_out_edges(*this) /*, dist(*this)*/ {

  1453 //       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {

  1454 // 	OutEdgeIt e;

  1455 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);

  1456 // 	first_out_edges.set(n, e);

  1457 //       }

  1458 //     }

  1460 //     //void setGraph(Graph& _graph) { graph = &_graph; }

  1461 //     //Graph& getGraph() const { return (*graph); }

  1463 //     //TrivGraphWrapper() : graph(0) { }

  1464 //     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1466 //     //typedef Graph BaseGraph;

  1468 //     //typedef typename Graph::Node Node;

  1469 //     //typedef typename Graph::NodeIt NodeIt;

  1471 //     //typedef typename Graph::Edge Edge;

  1472 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1473 //     //typedef typename Graph::InEdgeIt InEdgeIt;

  1474 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1475 //     //typedef typename Graph::EdgeIt EdgeIt;

  1477 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;

  1478 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;

  1480 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;

  1481 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;

  1482 //     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;

  1483 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1484 //     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;

  1486 //     NodeIt& first(NodeIt& n) const {

  1487 //       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);

  1488 //     }

  1490 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1491 //       e=first_out_edges.get(n);

  1492 //       return e;

  1493 //     }

  1495 //     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }

  1496 //     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {

  1497 //     //  return first(i, p); }

  1499 //     //template<typename I> I getNext(const I& i) const {

  1500 //     //  return gw.getNext(i); }

  1501 //     //template<typename I> I& next(I &i) const { return gw.next(i); }

  1503 //     template< typename It > It first() const {

  1504 //       It e; first(e); return e; }

  1506 //     template< typename It > It first(const Node& v) const {

  1507 //       It e; first(e, v); return e; }

  1509 //     //Node head(const Edge& e) const { return gw.head(e); }

  1510 //     //Node tail(const Edge& e) const { return gw.tail(e); }

  1512 //     //template<typename I> bool valid(const I& i) const

  1513 //     //  { return gw.valid(i); }

  1515 //     //int nodeNum() const { return gw.nodeNum(); }

  1516 //     //int edgeNum() const { return gw.edgeNum(); }

  1518 //     //template<typename I> Node aNode(const I& e) const {

  1519 //     //  return gw.aNode(e); }

  1520 //     //template<typename I> Node bNode(const I& e) const {

  1521 //     //  return gw.bNode(e); }

  1523 //     //Node addNode() const { return gw.addNode(); }

  1524 //     //Edge addEdge(const Node& tail, const Node& head) const {

  1525 //     //  return gw.addEdge(tail, head); }

  1527 //     //void erase(const OutEdgeIt& e) {

  1528 //     //  first_out_edge(this->tail(e))=e;

  1529 //     //}

  1530 //     void erase(const Edge& e) {

  1531 //       OutEdgeIt f(e);

  1532 //       next(f);

  1533 //       first_out_edges.set(this->tail(e), f);

  1534 //     }

  1535 //     //template<typename I> void erase(const I& i) const { gw.erase(i); }

  1537 //     //void clear() const { gw.clear(); }

  1539 //     template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {

  1540 //     public:

  1541 //       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :

  1542 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }

  1543 //       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :

  1544 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }

  1545 //     };

  1547 //     template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {

  1548 //     public:

  1549 //       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :

  1550 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }

  1551 //       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :

  1552 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }

  1553 //     };

  1554 //   };

  1556 //   template<typename GraphWrapper>

  1557 //   class FilterGraphWrapper {

  1558 //   };

  1560 //   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1561 //   class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {

  1563 //     //Graph* graph;

  1565 //   public:

  1566 //     //typedef Graph BaseGraph;

  1568 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;

  1569 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;

  1571 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;

  1572 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;

  1573 //     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;

  1574 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1575 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;

  1577 //     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;

  1579 //   public:

  1580 //     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,

  1581 // 			   const CapacityMap& _capacity) :

  1582 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {

  1583 //     }

  1585 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1586 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);

  1587 //       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))

  1588 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1589 //       return e;

  1590 //     }

  1592 //     NodeIt& next(NodeIt& e) const {

  1593 //       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1594 //     }

  1596 //     OutEdgeIt& next(OutEdgeIt& e) const {

  1597 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1598 //       while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))

  1599 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1600 //       return e;

  1601 //     }

  1603 //     NodeIt& first(NodeIt& n) const {

  1604 //       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);

  1605 //     }

  1607 //     void erase(const Edge& e) {

  1608 //       OutEdgeIt f(e);

  1609 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);

  1610 //       while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))

  1611 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);

  1612 //       first_out_edges.set(this->tail(e), f);

  1613 //     }

  1615 //     //TrivGraphWrapper() : graph(0) { }

  1616 //     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1618 //     //void setGraph(Graph& _graph) { graph = &_graph; }

  1619 //     //Graph& getGraph() const { return (*graph); }

  1621 //     //template<typename I> I& first(I& i) const { return gw.first(i); }

  1622 //     //template<typename I, typename P> I& first(I& i, const P& p) const {

  1623 //     //  return gw.first(i, p); }

  1625 //     //template<typename I> I getNext(const I& i) const {

  1626 //     //  return gw.getNext(i); }

  1627 //     //template<typename I> I& next(I &i) const { return gw.next(i); }

  1629 //     template< typename It > It first() const {

  1630 //       It e; first(e); return e; }

  1632 //     template< typename It > It first(const Node& v) const {

  1633 //       It e; first(e, v); return e; }

  1635 //     //Node head(const Edge& e) const { return gw.head(e); }

  1636 //     //Node tail(const Edge& e) const { return gw.tail(e); }

  1638 //     //template<typename I> bool valid(const I& i) const

  1639 //     //  { return gw.valid(i); }

  1641 //     //template<typename I> void setInvalid(const I &i);

  1642 //     //{ return gw.setInvalid(i); }

  1644 //     //int nodeNum() const { return gw.nodeNum(); }

  1645 //     //int edgeNum() const { return gw.edgeNum(); }

  1647 //     //template<typename I> Node aNode(const I& e) const {

  1648 //     //  return gw.aNode(e); }

  1649 //     //template<typename I> Node bNode(const I& e) const {

  1650 //     //  return gw.bNode(e); }

  1652 //     //Node addNode() const { return gw.addNode(); }

  1653 //     //Edge addEdge(const Node& tail, const Node& head) const {

  1654 //     //  return gw.addEdge(tail, head); }

  1656 //     //template<typename I> void erase(const I& i) const { gw.erase(i); }

  1658 //     //void clear() const { gw.clear(); }

  1660 //     template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {

  1661 //     public:

  1662 //       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :

  1663 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }

  1664 //       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :

  1665 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }

  1666 //     };

  1668 //     template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {

  1669 //     public:

  1670 //       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :

  1671 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }

  1672 //       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :

  1673 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }

  1674 //     };

  1676 //   public:

  1677 //     ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;

  1679 //   };

  1683 // // FIXME: comparison should be made better!!!

  1684 //   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>

  1685 //   class ResGraphWrapper

  1686 //   {

  1687 //     Graph* graph;

  1689 //   public:

  1690 //     typedef Graph BaseGraph;

  1692 //     typedef typename Graph::Node Node;

  1693 //     typedef typename Graph::Edge Edge;

  1695 //     typedef typename Graph::NodeIt NodeIt;

  1697 //     class OutEdgeIt {

  1698 //     public:

  1699 //       //Graph::Node n;

  1700 //       bool out_or_in;

  1701 //       typename Graph::OutEdgeIt o;

  1702 //       typename Graph::InEdgeIt i;

  1703 //     };

  1704 //     class InEdgeIt {

  1705 //     public:

  1706 //       //Graph::Node n;

  1707 //       bool out_or_in;

  1708 //       typename Graph::OutEdgeIt o;

  1709 //       typename Graph::InEdgeIt i;

  1710 //     };

  1711 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1712 //     typedef typename Graph::EdgeIt EdgeIt;

  1714 //     int nodeNum() const { return gw.nodeNum(); }

  1715 //     int edgeNum() const { return gw.edgeNum(); }

  1717 //     Node& first(Node& n) const { return gw.first(n); }

  1719 //     // Edge and SymEdge  is missing!!!!

  1720 //     // Edge <-> In/OutEdgeIt conversion is missing!!!!

  1722 //     //FIXME

  1723 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const

  1724 //       {

  1725 // 	e.n=n;

  1726 // 	gw.first(e.o,n);

  1727 // 	while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1728 // 	  gw.goNext(e.o);

  1729 // 	if(!gw.valid(e.o)) {

  1730 // 	  gw.first(e.i,n);

  1731 // 	  while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1732 // 	    gw.goNext(e.i);

  1733 // 	}

  1734 // 	return e;

  1735 //       }

  1736 // /*

  1737 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1738 //   {

  1739 //   if(gw.valid(e.o)) {

  1740 //   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1741 //   gw.goNext(e.o);

  1742 //   if(gw.valid(e.o)) return e;

  1743 //   else gw.first(e.i,e.n);

  1744 //   }

  1745 //   else {

  1746 //   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1747 //   gw.goNext(e.i);

  1748 //   return e;

  1749 //   }

  1750 //   }

  1751 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}

  1752 // */

  1753 //     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}

  1755 //     //FIXME

  1756 //     InEdgeIt& first(InEdgeIt& e, const Node& n) const

  1757 //       {

  1758 // 	e.n=n;

  1759 // 	gw.first(e.i,n);

  1760 // 	while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1761 // 	  gw.goNext(e.i);

  1762 // 	if(!gw.valid(e.i)) {

  1763 // 	  gw.first(e.o,n);

  1764 // 	  while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1765 // 	    gw.goNext(e.o);

  1766 // 	}

  1767 // 	return e;

  1768 //       }

  1769 // /*

  1770 //   InEdgeIt &goNext(InEdgeIt &e)

  1771 //   {

  1772 //   if(gw.valid(e.i)) {

  1773 //   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1774 //   gw.goNext(e.i);

  1775 //   if(gw.valid(e.i)) return e;

  1776 //   else gw.first(e.o,e.n);

  1777 //   }

  1778 //   else {

  1779 //   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1780 //   gw.goNext(e.o);

  1781 //   return e;

  1782 //   }

  1783 //   }

  1784 //   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}

  1785 // */

  1786 //     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}

  1788 //     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }

  1789 //     //template<typename I> I next(const I i); { return gw.goNext(i); }

  1791 //     template< typename It > It first() const {

  1792 //       It e; first(e); return e; }

  1794 //     template< typename It > It first(Node v) const {

  1795 //       It e; first(e, v); return e; }

  1797 //     Node head(const Edge& e) const { return gw.head(e); }

  1798 //     Node tail(const Edge& e) const { return gw.tail(e); }

  1800 //     template<typename I> Node aNode(const I& e) const {

  1801 //       return gw.aNode(e); }

  1802 //     template<typename I> Node bNode(const I& e) const {

  1803 //       return gw.bNode(e); }

  1805 //     //template<typename I> bool valid(const I i);

  1806 //     //{ return gw.valid(i); }

  1808 //     //template<typename I> void setInvalid(const I &i);

  1809 //     //{ return gw.setInvalid(i); }

  1811 //     Node addNode() { return gw.addNode(); }

  1812 //     Edge addEdge(const Node& tail, const Node& head) {

  1813 //       return gw.addEdge(tail, head); }

  1815 //     template<typename I> void erase(const I& i) { gw.erase(i); }

  1817 //     void clear() { gw.clear(); }

  1819 //     template<typename S> class NodeMap : public Graph::NodeMap<S> { };

  1820 //     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };

  1822 //     void setGraph(Graph& _graph) { graph = &_graph; }

  1823 //     Graph& getGraph() { return (*graph); }

  1825 //     //ResGraphWrapper() : graph(0) { }

  1826 //     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1827 //   };

  1829 } //namespace hugo

  1831 #endif //HUGO_GRAPH_WRAPPER_H

author	alpar
	Mon, 05 Apr 2004 13:48:25 +0000
changeset 294	f0ff6981d4fd
child 298	315d826faa8f
permissions	-rw-r--r--