lemon-0.x: src/work/marci/graph_wrapper.h@57ef4fd493d5

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

     2 #ifndef GRAPH_WRAPPER_H

     3 #define 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     typedef typename Graph::NodeIt NodeIt;

    20     typedef typename Graph::Edge Edge;

    21     typedef typename Graph::OutEdgeIt OutEdgeIt;

    22     typedef typename Graph::InEdgeIt InEdgeIt;

    23     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    24     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

    37       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    59       return graph->aNode(e); }

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

    61       return graph->bNode(e); }

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

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

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

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

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

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

    72     public:

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

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

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

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

    77     };

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

    80     public:

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

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

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

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

    85     };

    86   };

    88   template<typename GraphWrapper>

    89   class GraphWrapperSkeleton {

    90   protected:

    91     GraphWrapper gw;

    93   public:

    94     typedef typename GraphWrapper::BaseGraph BaseGraph;

    96     typedef typename GraphWrapper::Node Node;

    97     typedef typename GraphWrapper::NodeIt NodeIt;

    99     typedef typename GraphWrapper::Edge Edge;

   100     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   101     typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   102     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   103     typedef typename GraphWrapper::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   147     public:

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

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

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

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

   152     };

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

   155     public:

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

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

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

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

   160     };

   161   };

   163 //   template<typename Graph>

   164 //   class RevGraphWrapper

   165 //   {

   166 //   protected:

   167 //     Graph* graph;

   169 //   public:

   170 //     typedef Graph BaseGraph;

   172 //     typedef typename Graph::Node Node;

   173 //     typedef typename Graph::NodeIt NodeIt;

   175 //     typedef typename Graph::Edge Edge;

   176 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   177 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   178 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   179 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   227 //     public:

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

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

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

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

   232 //     };

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

   235 //     public:

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

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

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

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

   240 //     };

   241 //   };

   243   template<typename Graph>

   244   class RevGraphWrapper :

   245     public GraphWrapperSkeleton< TrivGraphWrapper<Graph> > {

   246   protected:

   247     //Graph* graph;

   249   public:

   250     //typedef Graph BaseGraph;

   252     //typedef typename Graph::Node Node;

   253     //typedef typename Graph::NodeIt NodeIt;

   255     //typedef typename Graph::Edge Edge;

   256     typedef typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::OutEdgeIt InEdgeIt;

   257     typedef typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::InEdgeIt OutEdgeIt;

   258     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   259     //typedef typename Graph::EdgeIt EdgeIt;

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

   262     RevGraphWrapper(Graph& _graph) : GraphWrapperSkeleton< TrivGraphWrapper<Graph> >(TrivGraphWrapper<Graph>(_graph)) { }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   306     template<typename T> class NodeMap :

   307       public GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::NodeMap<T>

   308     {

   309     public:

   310       NodeMap(const RevGraphWrapper<Graph>& _G) :

   311 	GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::NodeMap<T>(_G) { }

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

   313 	GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::NodeMap<T>(_G, a) { }

   314     };

   316     template<typename T> class EdgeMap :

   317       public GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::EdgeMap<T> {

   318     public:

   319       EdgeMap(const RevGraphWrapper<Graph>& _G) :

   320 	GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::EdgeMap<T>(_G) { }

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

   322 	GraphWrapperSkeleton< TrivGraphWrapper<Graph> >::EdgeMap<T>(_G, a) { }

   323     };

   324   };

   327   template<typename Graph>

   328   class UndirGraphWrapper {

   329   protected:

   330     Graph* graph;

   332   public:

   333     typedef Graph BaseGraph;

   335     typedef typename Graph::Node Node;

   336     typedef typename Graph::NodeIt NodeIt;

   338     //typedef typename Graph::Edge Edge;

   339     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   340     //typedef typename Graph::InEdgeIt InEdgeIt;

   341     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   342     //typedef typename Graph::EdgeIt EdgeIt;

   344     //private:

   345     typedef typename Graph::Edge GraphEdge;

   346     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   347     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   348     //public:

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

   351     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

   356     class Edge {

   357       friend class UndirGraphWrapper<Graph>;

   358       bool out_or_in; //true iff out

   359       GraphOutEdgeIt out;

   360       GraphInEdgeIt in;

   361     public:

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

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

   364       operator GraphEdge() const {

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

   366       }

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

   368 	if (v.out_or_in)

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

   370 	else

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

   372       }

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

   374 	if (v.out_or_in)

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

   376 	else

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

   378       }

   379     };

   381     class OutEdgeIt : public Edge {

   382       friend class UndirGraphWrapper<Graph>;

   383     public:

   384       OutEdgeIt() : Edge() { }

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

   386       OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {

   387 	out_or_in=true;

   388 	_G.graph->first(out, n);

   389 	if (!(_G.graph->valid(out))) {

   390 	  out_or_in=false;

   391 	  _G.graph->first(in, n);

   392 	}

   393       }

   394     };

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

   397       e.out_or_in=true;

   398       graph->first(e.out, n);

   399       if (!(graph->valid(e.out))) {

   400 	e.out_or_in=false;

   401 	graph->first(e.in, n);

   402       }

   403       return e;

   404     }

   406     OutEdgeIt& next(OutEdgeIt& e) const {

   407       if (e.out_or_in) {

   408 	Node n=graph->tail(e.out);

   409 	graph->next(e.out);

   410 	if (!graph->valid(e.out)) {

   411 	  e.out_or_in=false;

   412 	  graph->first(e.in, n);

   413 	}

   414       } else {

   415 	graph->next(e.in);

   416       }

   417       return e;

   418     }

   420     Node aNode(const OutEdgeIt& e) const {

   421       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }

   422     Node bNode(const OutEdgeIt& e) const {

   423       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }

   425     typedef OutEdgeIt InEdgeIt;

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

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

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

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

   432       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   468     public:

   469       NodeMap(const UndirGraphWrapper<Graph>& _G) :

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

   471       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :

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

   473     };

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

   476     public:

   477       EdgeMap(const UndirGraphWrapper<Graph>& _G) :

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

   479       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :

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

   481     };

   482   };

   486 //   template<typename Graph>

   487 //   class SymGraphWrapper

   488 //   {

   489 //     Graph* graph;

   491 //   public:

   492 //     typedef Graph BaseGraph;

   494 //     typedef typename Graph::Node Node;

   495 //     typedef typename Graph::Edge Edge;

   497 //     typedef typename Graph::NodeIt NodeIt;

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

   500 //     //iranyitatlant, ami van

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

   502 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   504 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   505 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   552 //   };

   555   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   556   class ResGraphWrapper {

   557   public:

   558     typedef Graph BaseGraph;

   559     typedef typename Graph::Node Node;

   560     typedef typename Graph::NodeIt NodeIt;

   561   private:

   562     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   563     typedef typename Graph::InEdgeIt OldInEdgeIt;

   564   protected:

   565     const Graph* graph;

   566     FlowMap* flow;

   567     const CapacityMap* capacity;

   568   public:

   570     ResGraphWrapper(const Graph& _G, FlowMap& _flow,

   571 	     const CapacityMap& _capacity) :

   572       graph(&_G), flow(&_flow), capacity(&_capacity) { }

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

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

   577     class Edge;

   578     class OutEdgeIt;

   579     friend class Edge;

   580     friend class OutEdgeIt;

   582     class Edge {

   583       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   584     protected:

   585       bool out_or_in; //true, iff out

   586       OldOutEdgeIt out;

   587       OldInEdgeIt in;

   588     public:

   589       Edge() : out_or_in(true) { }

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

   591 //       bool valid() const {

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

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

   594 	if (v.out_or_in)

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

   596 	else

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

   598       }

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

   600 	if (v.out_or_in)

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

   602 	else

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

   604       }

   605     };

   608     class OutEdgeIt : public Edge {

   609       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   610     public:

   611       OutEdgeIt() { }

   612       //FIXME

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

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

   615     private:

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

   617 	resG.graph->first(out, v);

   618 	while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }

   619 	if (!resG.graph->valid(out)) {

   620 	  out_or_in=0;

   621 	  resG.graph->first(in, v);

   622 	  while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }

   623 	}

   624       }

   625 //     public:

   626 //       OutEdgeIt& operator++() {

   627 // 	if (out_or_in) {

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

   629 // 	  ++out;

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

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

   632 // 	    out_or_in=0;

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

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

   635 // 	  }

   636 // 	} else {

   637 // 	  ++in;

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

   639 // 	}

   640 // 	return *this;

   641 //       }

   642     };

   644     class EdgeIt : public Edge {

   645       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   646       typename Graph::NodeIt v;

   647     public:

   648       EdgeIt() { }

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

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

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

   652 	resG.graph->first(v);

   653 	if (resG.graph->valid(v)) resG.graph->first(out, v); else out=OldOutEdgeIt(INVALID);

   654 	while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }

   655 	while (resG.graph->valid(v) && !resG.graph->valid(out)) {

   656 	  resG.graph->next(v);

   657 	  if (resG.graph->valid(v)) resG.graph->first(out, v);

   658 	  while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }

   659 	}

   660 	if (!resG.graph->valid(out)) {

   661 	  out_or_in=0;

   662 	  resG.graph->first(v);

   663 	  if (resG.graph->valid(v)) resG.graph->first(in, v); else in=OldInEdgeIt(INVALID);

   664 	  while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }

   665 	  while (resG.graph->valid(v) && !resG.graph->valid(in)) {

   666 	    resG.graph->next(v);

   667 	    if (resG.graph->valid(v)) resG.graph->first(in, v);

   668 	    while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }

   669 	  }

   670 	}

   671       }

   672 //       EdgeIt& operator++() {

   673 // 	if (out_or_in) {

   674 // 	  ++out;

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

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

   677 // 	    ++v;

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

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

   680 // 	  }

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

   682 // 	    out_or_in=0;

   683 // 	    G->first(v);

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

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

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

   687 // 	      ++v;

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

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

   690 // 	    }

   691 // 	  }

   692 // 	} else {

   693 // 	  ++in;

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

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

   696 // 	    ++v;

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

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

   699 // 	  }

   700 // 	}

   701 // 	return *this;

   702 //       }

   703     };

   705     NodeIt& first(NodeIt& v) const { return graph->first(v); }

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

   707       e=OutEdgeIt(*this, v);

   708       return e;

   709     }

   710     EdgeIt& first(EdgeIt& e) const {

   711       e=EdgeIt(*this);

   712       return e;

   713     }

   715     NodeIt& next(NodeIt& n) const { return graph->next(n); }

   717     OutEdgeIt& next(OutEdgeIt& e) const {

   718       if (e.out_or_in) {

   719 	Node v=graph->aNode(e.out);

   720 	graph->next(e.out);

   721 	while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }

   722 	if (!graph->valid(e.out)) {

   723 	  e.out_or_in=0;

   724 	  graph->first(e.in, v);

   725 	  while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }

   726 	}

   727       } else {

   728 	graph->next(e.in);

   729 	while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }

   730       }

   731       return e;

   732     }

   734     EdgeIt& next(EdgeIt& e) const {

   735       if (e.out_or_in) {

   736 	graph->next(e.out);

   737 	while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }

   738 	  while (graph->valid(e.v) && !graph->valid(e.out)) {

   739 	    graph->next(e.v);

   740 	    if (graph->valid(e.v)) graph->first(e.out, e.v);

   741 	    while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }

   742 	  }

   743 	  if (!graph->valid(e.out)) {

   744 	    e.out_or_in=0;

   745 	    graph->first(e.v);

   746 	    if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);

   747 	    while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }

   748 	    while (graph->valid(e.v) && !graph->valid(e.in)) {

   749 	      graph->next(e.v);

   750 	      if (graph->valid(e.v)) graph->first(e.in, e.v);

   751 	      while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }

   752 	    }

   753 	  }

   754 	} else {

   755 	  graph->next(e.in);

   756 	  while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }

   757 	  while (graph->valid(e.v) && !graph->valid(e.in)) {

   758 	    graph->next(e.v);

   759 	    if (graph->valid(e.v)) graph->first(e.in, e.v);

   760 	    while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }

   761 	  }

   762 	}

   763 	return e;

   764       }

   767     template< typename It >

   768     It first() const {

   769       It e;

   770       first(e);

   771       return e;

   772     }

   774     template< typename It >

   775     It first(Node v) const {

   776       It e;

   777       first(e, v);

   778       return e;

   779     }

   781     Node tail(Edge e) const {

   782       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }

   783     Node head(Edge e) const {

   784       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

   786     Node aNode(OutEdgeIt e) const {

   787       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }

   788     Node bNode(OutEdgeIt e) const {

   789       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

   791     int id(Node v) const { return graph->id(v); }

   793     bool valid(Node n) const { return graph->valid(n); }

   794     bool valid(Edge e) const {

   795       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }

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

   798       if (e.out_or_in)

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

   800       else

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

   802     }

   804     Number free(const Edge& e) const {

   805       if (e.out_or_in)

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

   807       else

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

   809     }

   811     Number free(OldOutEdgeIt out) const {

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

   813     }

   815     Number free(OldInEdgeIt in) const {

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

   817     }

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

   820     public:

   821       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)

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

   823       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,

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

   825     };

   827 //     template <typename T>

   828 //     class NodeMap {

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

   830 //     public:

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

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

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

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

   835 //     };

   837     template <typename T>

   838     class EdgeMap {

   839       typename Graph::EdgeMap<T> forward_map, backward_map;

   840     public:

   841       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }

   842       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }

   843       void set(Edge e, T a) {

   844 	if (e.out_or_in)

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

   846 	else

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

   848       }

   849       T get(Edge e) {

   850 	if (e.out_or_in)

   851 	  return forward_map.get(e.out);

   852 	else

   853 	  return backward_map.get(e.in);

   854       }

   855     };

   856   };

   858   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

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

   860   protected:

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

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

   863   public:

   864     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,

   865 			   const CapacityMap& _capacity) :

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

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

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

   869 	OutEdgeIt e;

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

   871 	first_out_edges.set(n, e);

   872       }

   873     }

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

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

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

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

   881     //typedef Graph BaseGraph;

   883     //typedef typename Graph::Node Node;

   884     //typedef typename Graph::NodeIt NodeIt;

   886     //typedef typename Graph::Edge Edge;

   887     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   888     //typedef typename Graph::InEdgeIt InEdgeIt;

   889     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   890     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

   898     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

   901     NodeIt& first(NodeIt& n) const {

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

   903     }

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

   906       e=first_out_edges.get(n);

   907       return e;

   908     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   944     //}

   945     void erase(const Edge& e) {

   946       OutEdgeIt f(e);

   947       next(f);

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

   949     }

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

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

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

   955     public:

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

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

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

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

   960     };

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

   963     public:

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

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

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

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

   968     };

   969   };

   971   template<typename GraphWrapper>

   972   class FilterGraphWrapper {

   973   };

   975   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

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

   978     //Graph* graph;

   980   public:

   981     //typedef Graph BaseGraph;

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

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

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

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

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

   989     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

   994   public:

   995     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,

   996 			   const CapacityMap& _capacity) :

   997       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, graph->nodeNum()) {

   998     }

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

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

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

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

  1004       return e;

  1005     }

  1007     NodeIt& next(NodeIt& e) const {

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

  1009     }

  1011     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1015       return e;

  1016     }

  1018     NodeIt& first(NodeIt& n) const {

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

  1020     }

  1022     void erase(const Edge& e) {

  1023       OutEdgeIt f(e);

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

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

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

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

  1028     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1076     public:

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

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

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

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

  1081     };

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

  1084     public:

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

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

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

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

  1089     };

  1091   public:

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

  1094   };

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

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

  1100 //   class ResGraphWrapper

  1101 //   {

  1102 //     Graph* graph;

  1104 //   public:

  1105 //     typedef Graph BaseGraph;

  1107 //     typedef typename Graph::Node Node;

  1108 //     typedef typename Graph::Edge Edge;

  1110 //     typedef typename Graph::NodeIt NodeIt;

  1112 //     class OutEdgeIt {

  1113 //     public:

  1114 //       //Graph::Node n;

  1115 //       bool out_or_in;

  1116 //       typename Graph::OutEdgeIt o;

  1117 //       typename Graph::InEdgeIt i;

  1118 //     };

  1119 //     class InEdgeIt {

  1120 //     public:

  1121 //       //Graph::Node n;

  1122 //       bool out_or_in;

  1123 //       typename Graph::OutEdgeIt o;

  1124 //       typename Graph::InEdgeIt i;

  1125 //     };

  1126 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1127 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

  1132 //     Node& first(Node& n) const { return graph->first(n); }

  1134 //     // Edge and SymEdge  is missing!!!!

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

  1137 //     //FIXME

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

  1139 //       {

  1140 // 	e.n=n;

  1141 // 	graph->first(e.o,n);

  1142 // 	while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1143 // 	  graph->goNext(e.o);

  1144 // 	if(!graph->valid(e.o)) {

  1145 // 	  graph->first(e.i,n);

  1146 // 	  while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1147 // 	    graph->goNext(e.i);

  1148 // 	}

  1149 // 	return e;

  1150 //       }

  1151 // /*

  1152 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1153 //   {

  1154 //   if(graph->valid(e.o)) {

  1155 //   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1156 //   graph->goNext(e.o);

  1157 //   if(graph->valid(e.o)) return e;

  1158 //   else graph->first(e.i,e.n);

  1159 //   }

  1160 //   else {

  1161 //   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1162 //   graph->goNext(e.i);

  1163 //   return e;

  1164 //   }

  1165 //   }

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

  1167 // */

  1168 //     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}

  1170 //     //FIXME

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

  1172 //       {

  1173 // 	e.n=n;

  1174 // 	graph->first(e.i,n);

  1175 // 	while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1176 // 	  graph->goNext(e.i);

  1177 // 	if(!graph->valid(e.i)) {

  1178 // 	  graph->first(e.o,n);

  1179 // 	  while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1180 // 	    graph->goNext(e.o);

  1181 // 	}

  1182 // 	return e;

  1183 //       }

  1184 // /*

  1185 //   InEdgeIt &goNext(InEdgeIt &e)

  1186 //   {

  1187 //   if(graph->valid(e.i)) {

  1188 //   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1189 //   graph->goNext(e.i);

  1190 //   if(graph->valid(e.i)) return e;

  1191 //   else graph->first(e.o,e.n);

  1192 //   }

  1193 //   else {

  1194 //   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1195 //   graph->goNext(e.o);

  1196 //   return e;

  1197 //   }

  1198 //   }

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

  1200 // */

  1201 //     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1242 //   };

  1244 } //namespace hugo

  1246 #endif //GRAPH_WRAPPER_H

author	marci
	Mon, 22 Mar 2004 16:07:42 +0000
changeset 233	57ef4fd493d5
parent 230	734dd0649941
child 234	348f8fd374ee
permissions	-rw-r--r--