lemon-0.x: src/work/athos/graph_wrapper.h@044f5898b769

     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 Graph>

   288 //   class RevGraphWrapper

   289 //   {

   290 //   protected:

   291 //     Graph* graph;

   293 //   public:

   294 //     typedef Graph BaseGraph;

   296 //     typedef typename Graph::Node Node;

   297 //     typedef typename Graph::NodeIt NodeIt;

   299 //     typedef typename Graph::Edge Edge;

   300 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   301 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   302 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   303 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   351 //     public:

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

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

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

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

   356 //     };

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

   359 //     public:

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

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

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

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

   364 //     };

   365 //   };

   367 //   template<typename /*Graph*/GraphWrapper

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

   369 //   class RevGraphWrapper :

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

   371 //   protected:

   372 //     //Graph* graph;

   374 //   public:

   375 //     //typedef Graph BaseGraph;

   377 //     //typedef typename Graph::Node Node;

   378 //     //typedef typename Graph::NodeIt NodeIt;

   380 //     //typedef typename Graph::Edge Edge;

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

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

   383 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   384 //     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   431 //     template<typename T> class NodeMap :

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

   433 //     {

   434 //     public:

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

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

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

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

   439 //     };

   441 //     template<typename T> class EdgeMap :

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

   443 //     public:

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

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

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

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

   448 //     };

   449 //   };

   452   template<typename GraphWrapper>

   453   class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   454   public:

   455     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   456     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;

   457     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;

   458     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;

   460     RevGraphWrapper(GraphWrapper _gw) :

   461       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

   463     Node head(const Edge& e) const

   464       { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }

   465     Node tail(const Edge& e) const

   466       { return GraphWrapperSkeleton<GraphWrapper>::head(e); }

   467   };

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

   470   template<typename GraphWrapper, typename EdgeFilterMap>

   471   class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   472   protected:

   473     EdgeFilterMap* filter_map;

   474   public:

   475     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   476     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

   477     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;

   478     typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;

   479     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;

   480     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

   482     SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :

   483       GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }

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

   486       gw.first(i);

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

   488       return i;

   489     }

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

   491       gw.first(i, p);

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

   493       return i;

   494     }

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

   497     //  return gw.getNext(i);

   498     //}

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

   500       gw.next(i);

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

   502       return i;

   503     }

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

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

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

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

   510   };

   512 //   template<typename GraphWrapper>

   513 //   class UndirGraphWrapper {

   514 //   protected:

   515 //     //Graph* graph;

   516 //     GraphWrapper gw;

   518 //   public:

   519 //     typedef GraphWrapper BaseGraph;

   521 //     typedef typename GraphWrapper::Node Node;

   522 //     typedef typename GraphWrapper::NodeIt NodeIt;

   524 //     //typedef typename Graph::Edge Edge;

   525 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   526 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   527 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   528 //     //typedef typename Graph::EdgeIt EdgeIt;

   530 //     //private:

   531 //     typedef typename GraphWrapper::Edge GraphEdge;

   532 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   533 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   534 //     //public:

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

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

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

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

   542 //     class Edge {

   543 //       friend class UndirGraphWrapper<GraphWrapper>;

   544 //       bool out_or_in; //true iff out

   545 //       GraphOutEdgeIt out;

   546 //       GraphInEdgeIt in;

   547 //     public:

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

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

   550 //       operator GraphEdge() const {

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

   552 //       }

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

   554 // 	if (v.out_or_in)

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

   556 // 	else

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

   558 //       }

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

   560 // 	if (v.out_or_in)

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

   562 // 	else

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

   564 //       }

   565 //     };

   567 //     class OutEdgeIt : public Edge {

   568 //       friend class UndirGraphWrapper<GraphWrapper>;

   569 //     public:

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

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

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

   573 // 	: Edge() {

   574 // 	out_or_in=true;

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

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

   577 // 	  out_or_in=false;

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

   579 // 	}

   580 //       }

   581 //     };

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

   584 //       e.out_or_in=true;

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

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

   587 // 	e.out_or_in=false;

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

   589 //       }

   590 //       return e;

   591 //     }

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

   594 //       if (e.out_or_in) {

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

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

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

   598 // 	  e.out_or_in=false;

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

   600 // 	}

   601 //       } else {

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

   603 //       }

   604 //       return e;

   605 //     }

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

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

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

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

   612 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   655 //     public:

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

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

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

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

   660 //     };

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

   663 //     public:

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

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

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

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

   668 //     };

   669 //   };

   672   template<typename GraphWrapper>

   673   class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   674   protected:

   675 //    GraphWrapper gw;

   677   public:

   678     //typedef GraphWrapper BaseGraph;

   680     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   681     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

   683     //private:

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

   685     //legyenek, at kell irni

   686     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   687     GraphWrapper::Edge GraphEdge;

   688     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   689     GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   690     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   691     GraphWrapper::InEdgeIt GraphInEdgeIt;

   692     //public:

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

   695     UndirGraphWrapper(GraphWrapper _gw) :

   696       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

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

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

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

   703     class Edge {

   704       friend class UndirGraphWrapper<GraphWrapper>;

   705       bool out_or_in; //true iff out

   706       GraphOutEdgeIt out;

   707       GraphInEdgeIt in;

   708     public:

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

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

   711       operator GraphEdge() const {

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

   713       }

   714 //FIXME

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

   716 //is it good?

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

   718 	if (v.out_or_in)

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

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

   721 	else

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

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

   724       }

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

   726 	if (v.out_or_in)

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

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

   729 	else

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

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

   732       }

   733     };

   735     class OutEdgeIt : public Edge {

   736       friend class UndirGraphWrapper<GraphWrapper>;

   737     public:

   738       OutEdgeIt() : Edge() { }

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

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

   741 	: Edge() {

   742 	out_or_in=true; _G.gw.first(out, n);

   743 	if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n);	}

   744       }

   745     };

   747     typedef OutEdgeIt InEdgeIt;

   749     class EdgeIt : public Edge {

   750       friend class UndirGraphWrapper<GraphWrapper>;

   751     protected:

   752       NodeIt v;

   753     public:

   754       EdgeIt() : Edge() { }

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

   756       EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)

   757 	: Edge() {

   758 	out_or_in=true;

   759 	//Node v;

   760 	_G.first(v);

   761 	if (_G.valid(v)) _G.gw.first(out); else out=INVALID;

   762 	while (_G.valid(v) && !_G.gw.valid(out)) {

   763 	  _G.gw.next(v);

   764 	  if (_G.valid(v)) _G.gw.first(out);

   765 	}

   766       }

   767     };

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

   770       e.out_or_in=true; gw.first(e.out, n);

   771       if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }

   772       return e;

   773     }

   775     EdgeIt& first(EdgeIt& e) const {

   776       e.out_or_in=true;

   777       //NodeIt v;

   778       first(e.v);

   779       if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;

   780       while (valid(e.v) && !gw.valid(e.out)) {

   781 	gw.next(e.v);

   782 	if (valid(e.v)) gw.first(e.out, e.v);

   783       }

   784       return e;

   785     }

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

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

   789       gw.first(i, p); return i; }

   791     OutEdgeIt& next(OutEdgeIt& e) const {

   792       if (e.out_or_in) {

   793 	Node n=gw.tail(e.out);

   794 	gw.next(e.out);

   795 	if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }

   796       } else {

   797 	gw.next(e.in);

   798       }

   799       return e;

   800     }

   802     EdgeIt& next(EdgeIt& e) const {

   803       //NodeIt v=tail(e);

   804       gw.next(e.out);

   805       while (valid(e.v) && !gw.valid(e.out)) {

   806 	next(e.v);

   807 	if (valid(e.v)) gw.first(e.out, e.v);

   808       }

   809       return e;

   810     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   835     Node aNode(const OutEdgeIt& e) const {

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

   837     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   851 //     public:

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

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

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

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

   856 //     };

   858 //     template<typename T> class EdgeMap :

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

   860 //     public:

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

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

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

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

   865 //     };

   866    };

   872 //   template<typename Graph>

   873 //   class SymGraphWrapper

   874 //   {

   875 //     Graph* graph;

   877 //   public:

   878 //     typedef Graph BaseGraph;

   880 //     typedef typename Graph::Node Node;

   881 //     typedef typename Graph::Edge Edge;

   883 //     typedef typename Graph::NodeIt NodeIt;

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

   886 //     //iranyitatlant, ami van

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

   888 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   890 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   891 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   938 //   };

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

   942   class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{

   943   public:

   944     //typedef Graph BaseGraph;

   945     //typedef TrivGraphWrapper<const Graph> GraphWrapper;

   946     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   947     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

   948   private:

   949     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   950     GraphWrapper::OutEdgeIt OldOutEdgeIt;

   951     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   952     GraphWrapper::InEdgeIt OldInEdgeIt;

   954     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   955     GraphWrapper::Edge OldEdge;

   956   protected:

   957     //const Graph* graph;

   958     //GraphWrapper gw;

   959     FlowMap* flow;

   960     const CapacityMap* capacity;

   961   public:

   963     ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,

   964 		    const CapacityMap& _capacity) :

   965       GraphWrapperSkeleton<GraphWrapper>(_gw),

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

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

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

   971     class Edge;

   972     class OutEdgeIt;

   973     friend class Edge;

   974     friend class OutEdgeIt;

   976     class Edge {

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

   978     protected:

   979       bool out_or_in; //true, iff out

   980       OldOutEdgeIt out;

   981       OldInEdgeIt in;

   982     public:

   983       Edge() : out_or_in(true) { }

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

   985 //       bool valid() const {

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

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

   988 	if (v.out_or_in)

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

   990 	else

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

   992       }

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

   994 	if (v.out_or_in)

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

   996 	else

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

   998       }

   999       operator OldEdge() {

  1000 	if(out_or_in)

  1001 	  return out;

  1002 	else

  1003 	  return in;

  1004       }

  1005     };

  1008     class OutEdgeIt : public Edge {

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

  1010     public:

  1011       OutEdgeIt() { }

  1012       //FIXME

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

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

  1015     protected:

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

  1017 	resG.gw.first(out, v);

  1018 	while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }

  1019 	if (!resG.gw.valid(out)) {

  1020 	  out_or_in=0;

  1021 	  resG.gw.first(in, v);

  1022 	  while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }

  1023 	}

  1024       }

  1025 //     public:

  1026 //       OutEdgeIt& operator++() {

  1027 // 	if (out_or_in) {

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

  1029 // 	  ++out;

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

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

  1032 // 	    out_or_in=0;

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

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

  1035 // 	  }

  1036 // 	} else {

  1037 // 	  ++in;

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

  1039 // 	}

  1040 // 	return *this;

  1041 //       }

  1042     };

  1044     //FIXME This is just for having InEdgeIt

  1045     typedef void InEdgeIt;

  1047     class EdgeIt : public Edge {

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

  1049       NodeIt v;

  1050     public:

  1051       EdgeIt() { }

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

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

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

  1055 	resG.gw.first(v);

  1056 	if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;

  1057 	while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }

  1058 	while (resG.gw.valid(v) && !resG.gw.valid(out)) {

  1059 	  resG.gw.next(v);

  1060 	  if (resG.gw.valid(v)) resG.gw.first(out, v);

  1061 	  while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }

  1062 	}

  1063 	if (!resG.gw.valid(out)) {

  1064 	  out_or_in=0;

  1065 	  resG.gw.first(v);

  1066 	  if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;

  1067 	  while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }

  1068 	  while (resG.gw.valid(v) && !resG.gw.valid(in)) {

  1069 	    resG.gw.next(v);

  1070 	    if (resG.gw.valid(v)) resG.gw.first(in, v);

  1071 	    while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }

  1072 	  }

  1073 	}

  1074       }

  1075 //       EdgeIt& operator++() {

  1076 // 	if (out_or_in) {

  1077 // 	  ++out;

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

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

  1080 // 	    ++v;

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

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

  1083 // 	  }

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

  1085 // 	    out_or_in=0;

  1086 // 	    G->first(v);

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

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

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

  1090 // 	      ++v;

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

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

  1093 // 	    }

  1094 // 	  }

  1095 // 	} else {

  1096 // 	  ++in;

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

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

  1099 // 	    ++v;

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

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

  1102 // 	  }

  1103 // 	}

  1104 // 	return *this;

  1105 //       }

  1106     };

  1108     NodeIt& first(NodeIt& v) const { gw.first(v); return v; }

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

  1110       e=OutEdgeIt(*this, v);

  1111       return e;

  1112     }

  1113     EdgeIt& first(EdgeIt& e) const {

  1114       e=EdgeIt(*this);

  1115       return e;

  1116     }

  1118     NodeIt& next(NodeIt& n) const { return gw.next(n); }

  1120     OutEdgeIt& next(OutEdgeIt& e) const {

  1121       if (e.out_or_in) {

  1122 	Node v=gw.aNode(e.out);

  1123 	gw.next(e.out);

  1124 	while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }

  1125 	if (!gw.valid(e.out)) {

  1126 	  e.out_or_in=0;

  1127 	  gw.first(e.in, v);

  1128 	  while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1129 	}

  1130       } else {

  1131 	gw.next(e.in);

  1132 	while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1133       }

  1134       return e;

  1135     }

  1137     EdgeIt& next(EdgeIt& e) const {

  1138       if (e.out_or_in) {

  1139 	gw.next(e.out);

  1140 	while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }

  1141 	  while (gw.valid(e.v) && !gw.valid(e.out)) {

  1142 	    gw.next(e.v);

  1143 	    if (gw.valid(e.v)) gw.first(e.out, e.v);

  1144 	    while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }

  1145 	  }

  1146 	  if (!gw.valid(e.out)) {

  1147 	    e.out_or_in=0;

  1148 	    gw.first(e.v);

  1149 	    if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;

  1150 	    while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1151 	    while (gw.valid(e.v) && !gw.valid(e.in)) {

  1152 	      gw.next(e.v);

  1153 	      if (gw.valid(e.v)) gw.first(e.in, e.v);

  1154 	      while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1155 	    }

  1156 	  }

  1157 	} else {

  1158 	  gw.next(e.in);

  1159 	  while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1160 	  while (gw.valid(e.v) && !gw.valid(e.in)) {

  1161 	    gw.next(e.v);

  1162 	    if (gw.valid(e.v)) gw.first(e.in, e.v);

  1163 	    while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1164 	  }

  1165 	}

  1166 	return e;

  1167       }

  1170     template< typename It >

  1171     It first() const {

  1172       It e;

  1173       first(e);

  1174       return e;

  1175     }

  1177     template< typename It >

  1178     It first(Node v) const {

  1179       It e;

  1180       first(e, v);

  1181       return e;

  1182     }

  1184     Node tail(Edge e) const {

  1185       return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }

  1186     Node head(Edge e) const {

  1187       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

  1189     Node aNode(OutEdgeIt e) const {

  1190       return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }

  1191     Node bNode(OutEdgeIt e) const {

  1192       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

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

  1195     //FIXME

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

  1199     int id(Node v) const { return gw.id(v); }

  1201     bool valid(Node n) const { return gw.valid(n); }

  1202     bool valid(Edge e) const {

  1203       return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }

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

  1206       if (e.out_or_in)

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

  1208       else

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

  1210     }

  1212     Number resCap(const Edge& e) const {

  1213       if (e.out_or_in)

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

  1215       else

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

  1217     }

  1219     Number resCap(OldOutEdgeIt out) const {

  1220       return ( (*capacity)[out] - (*flow)[out]);

  1221     }

  1223     Number resCap(OldInEdgeIt in) const {

  1224       return ( (*flow)[in] );

  1225     }

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

  1228 //     public:

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

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

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

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

  1233 //     };

  1235 //     template <typename T>

  1236 //     class NodeMap {

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

  1238 //     public:

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

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

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

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

  1243 //     };

  1245     template <typename T>

  1246     class EdgeMap {

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

  1248     public:

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

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

  1251       void set(Edge e, T a) {

  1252 	if (e.out_or_in)

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

  1254 	else

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

  1256       }

  1257       T get(Edge e) {

  1258 	if (e.out_or_in)

  1259 	  return forward_map.get(e.out);

  1260 	else

  1261 	  return backward_map.get(e.in);

  1262       }

  1263     };

  1264   };

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

  1267   template<typename GraphWrapper, typename FirstOutEdgesMap>

  1268   class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

  1269   protected:

  1270     FirstOutEdgesMap* first_out_edges;

  1271   public:

  1272     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

  1273     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

  1274     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;

  1275     typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;

  1276     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;

  1277     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

  1279     ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :

  1280       GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }

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

  1283       gw.first(i);

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

  1285       return i;

  1286     }

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

  1288       e=first_out_edges->get(n);

  1289       return e;

  1290     }

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

  1292       gw.first(i, p);

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

  1294       return i;

  1295     }

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

  1298     //  return gw.getNext(i);

  1299     //}

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

  1301       gw.next(i);

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

  1303       return i;

  1304     }

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

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

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

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

  1312     void erase(const OutEdgeIt& e) const {

  1313       OutEdgeIt f=e;

  1314       this->next(f);

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

  1316     }

  1317   };

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

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

  1321 //   protected:

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

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

  1324 //   public:

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

  1326 // 			   const CapacityMap& _capacity) :

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

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

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

  1330 // 	OutEdgeIt e;

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

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

  1333 //       }

  1334 //     }

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

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

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

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

  1342 //     //typedef Graph BaseGraph;

  1344 //     //typedef typename Graph::Node Node;

  1345 //     //typedef typename Graph::NodeIt NodeIt;

  1347 //     //typedef typename Graph::Edge Edge;

  1348 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1349 //     //typedef typename Graph::InEdgeIt InEdgeIt;

  1350 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1351 //     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

  1359 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

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

  1364 //     }

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

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

  1368 //       return e;

  1369 //     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1405 //     //}

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

  1407 //       OutEdgeIt f(e);

  1408 //       next(f);

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

  1410 //     }

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

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

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

  1416 //     public:

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

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

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

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

  1421 //     };

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

  1424 //     public:

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

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

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

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

  1429 //     };

  1430 //   };

  1432 //   template<typename GraphWrapper>

  1433 //   class FilterGraphWrapper {

  1434 //   };

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

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

  1439 //     //Graph* graph;

  1441 //   public:

  1442 //     //typedef Graph BaseGraph;

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

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

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

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

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

  1450 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

  1455 //   public:

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

  1457 // 			   const CapacityMap& _capacity) :

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

  1459 //     }

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

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

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

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

  1465 //       return e;

  1466 //     }

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

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

  1470 //     }

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

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

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

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

  1476 //       return e;

  1477 //     }

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

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

  1481 //     }

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

  1484 //       OutEdgeIt f(e);

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

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

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

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

  1489 //     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1537 //     public:

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

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

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

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

  1542 //     };

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

  1545 //     public:

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

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

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

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

  1550 //     };

  1552 //   public:

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

  1555 //   };

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

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

  1561 //   class ResGraphWrapper

  1562 //   {

  1563 //     Graph* graph;

  1565 //   public:

  1566 //     typedef Graph BaseGraph;

  1568 //     typedef typename Graph::Node Node;

  1569 //     typedef typename Graph::Edge Edge;

  1571 //     typedef typename Graph::NodeIt NodeIt;

  1573 //     class OutEdgeIt {

  1574 //     public:

  1575 //       //Graph::Node n;

  1576 //       bool out_or_in;

  1577 //       typename Graph::OutEdgeIt o;

  1578 //       typename Graph::InEdgeIt i;

  1579 //     };

  1580 //     class InEdgeIt {

  1581 //     public:

  1582 //       //Graph::Node n;

  1583 //       bool out_or_in;

  1584 //       typename Graph::OutEdgeIt o;

  1585 //       typename Graph::InEdgeIt i;

  1586 //     };

  1587 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1588 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1595 //     // Edge and SymEdge  is missing!!!!

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

  1598 //     //FIXME

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

  1600 //       {

  1601 // 	e.n=n;

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

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

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

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

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

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

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

  1609 // 	}

  1610 // 	return e;

  1611 //       }

  1612 // /*

  1613 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1614 //   {

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

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

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

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

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

  1620 //   }

  1621 //   else {

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

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

  1624 //   return e;

  1625 //   }

  1626 //   }

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

  1628 // */

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

  1631 //     //FIXME

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

  1633 //       {

  1634 // 	e.n=n;

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

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

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

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

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

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

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

  1642 // 	}

  1643 // 	return e;

  1644 //       }

  1645 // /*

  1646 //   InEdgeIt &goNext(InEdgeIt &e)

  1647 //   {

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

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

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

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

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

  1653 //   }

  1654 //   else {

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

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

  1657 //   return e;

  1658 //   }

  1659 //   }

  1660 //   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}

  1661 // */

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

  1664 //     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1687 //     Node addNode() { return gw.addNode(); }

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

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

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

  1693 //     void clear() { gw.clear(); }

  1695 //     template<typename S> class NodeMap : public Graph::NodeMap<S> { };

  1696 //     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };

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

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

  1701 //     //ResGraphWrapper() : graph(0) { }

  1702 //     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1703 //   };

  1705 } //namespace hugo

  1707 #endif //HUGO_GRAPH_WRAPPER_H

author	athos
	Fri, 02 Apr 2004 15:59:17 +0000
changeset 277	044f5898b769
parent 275	2dd19df03593
permissions	-rw-r--r--