lemon-0.x: src/work/marci/graph_wrapper.h@734dd0649941

     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   };

   330   template<typename Graph>

   331   class UndirGraphWrapper {

   332   protected:

   333     Graph* graph;

   335   public:

   336     typedef Graph BaseGraph;

   338     typedef typename Graph::Node Node;

   339     typedef typename Graph::NodeIt NodeIt;

   341     //typedef typename Graph::Edge Edge;

   342     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   343     //typedef typename Graph::InEdgeIt InEdgeIt;

   344     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   345     //typedef typename Graph::EdgeIt EdgeIt;

   347     //private:

   348     typedef typename Graph::Edge GraphEdge;

   349     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   350     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   351     //public:

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

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

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

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

   359     class Edge {

   360       friend class UndirGraphWrapper<Graph>;

   361       bool out_or_in; //true iff out

   362       GraphOutEdgeIt out;

   363       GraphInEdgeIt in;

   364     public:

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

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

   367       operator GraphEdge() const {

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

   369       }

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

   371 	if (v.out_or_in)

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

   373 	else

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

   375       }

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

   377 	if (v.out_or_in)

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

   379 	else

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

   381       }

   382     };

   384     class OutEdgeIt : public Edge {

   385       friend class UndirGraphWrapper<Graph>;

   386     public:

   387       OutEdgeIt() : Edge() { }

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

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

   390 	out_or_in=true;

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

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

   393 	  out_or_in=false;

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

   395 	}

   396       }

   397     };

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

   400       e.out_or_in=true;

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

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

   403 	e.out_or_in=false;

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

   405       }

   406       return e;

   407     }

   409     OutEdgeIt& next(OutEdgeIt& e) const {

   410       if (e.out_or_in) {

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

   412 	graph->next(e.out);

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

   414 	  e.out_or_in=false;

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

   416 	}

   417       } else {

   418 	graph->next(e.in);

   419       }

   420       return e;

   421     }

   423     Node aNode(const OutEdgeIt& e) const {

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

   425     Node bNode(const OutEdgeIt& e) const {

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

   428     typedef OutEdgeIt InEdgeIt;

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

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

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

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

   435       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   470     public:

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

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

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

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

   475     };

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

   478     public:

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

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

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

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

   483     };

   484   };

   488 //   template<typename Graph>

   489 //   class SymGraphWrapper

   490 //   {

   491 //     Graph* graph;

   493 //   public:

   494 //     typedef Graph BaseGraph;

   496 //     typedef typename Graph::Node Node;

   497 //     typedef typename Graph::Edge Edge;

   499 //     typedef typename Graph::NodeIt NodeIt;

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

   502 //     //iranyitatlant, ami van

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

   504 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   506 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   507 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   554 //   };

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

   558   class ResGraphWrapper {

   559   public:

   560     typedef Graph BaseGraph;

   561     typedef typename Graph::Node Node;

   562     typedef typename Graph::NodeIt NodeIt;

   563   private:

   564     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   565     typedef typename Graph::InEdgeIt OldInEdgeIt;

   566   protected:

   567     const Graph* graph;

   568     FlowMap* flow;

   569     const CapacityMap* capacity;

   570   public:

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

   573 	     const CapacityMap& _capacity) :

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

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

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

   579     class Edge;

   580     class OutEdgeIt;

   581     friend class Edge;

   582     friend class OutEdgeIt;

   584     class Edge {

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

   586     protected:

   587       bool out_or_in; //true, iff out

   588       OldOutEdgeIt out;

   589       OldInEdgeIt in;

   590     public:

   591       Edge() : out_or_in(true) { }

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

   593 //       bool valid() const {

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

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

   596 	if (v.out_or_in)

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

   598 	else

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

   600       }

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

   602 	if (v.out_or_in)

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

   604 	else

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

   606       }

   607     };

   610     class OutEdgeIt : public Edge {

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

   612     public:

   613       OutEdgeIt() { }

   614       //FIXME

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

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

   617     private:

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

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

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

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

   622 	  out_or_in=0;

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

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

   625 	}

   626       }

   627 //     public:

   628 //       OutEdgeIt& operator++() {

   629 // 	if (out_or_in) {

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

   631 // 	  ++out;

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

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

   634 // 	    out_or_in=0;

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

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

   637 // 	  }

   638 // 	} else {

   639 // 	  ++in;

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

   641 // 	}

   642 // 	return *this;

   643 //       }

   644     };

   646     class EdgeIt : public Edge {

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

   648       typename Graph::NodeIt v;

   649     public:

   650       EdgeIt() { }

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

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

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

   654 	resG.graph->first(v);

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

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

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

   658 	  resG.graph->next(v);

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

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

   661 	}

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

   663 	  out_or_in=0;

   664 	  resG.graph->first(v);

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

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

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

   668 	    resG.graph->next(v);

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

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

   671 	  }

   672 	}

   673       }

   674 //       EdgeIt& operator++() {

   675 // 	if (out_or_in) {

   676 // 	  ++out;

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

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

   679 // 	    ++v;

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

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

   682 // 	  }

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

   684 // 	    out_or_in=0;

   685 // 	    G->first(v);

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

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

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

   689 // 	      ++v;

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

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

   692 // 	    }

   693 // 	  }

   694 // 	} else {

   695 // 	  ++in;

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

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

   698 // 	    ++v;

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

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

   701 // 	  }

   702 // 	}

   703 // 	return *this;

   704 //       }

   705     };

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

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

   709       e=OutEdgeIt(*this, v);

   710       return e;

   711     }

   712     EdgeIt& first(EdgeIt& e) const {

   713       e=EdgeIt(*this);

   714       return e;

   715     }

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

   719     OutEdgeIt& next(OutEdgeIt& e) const {

   720       if (e.out_or_in) {

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

   722 	graph->next(e.out);

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

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

   725 	  e.out_or_in=0;

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

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

   728 	}

   729       } else {

   730 	graph->next(e.in);

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

   732       }

   733       return e;

   734     }

   736     EdgeIt& next(EdgeIt& e) const {

   737       if (e.out_or_in) {

   738 	graph->next(e.out);

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

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

   741 	    graph->next(e.v);

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

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

   744 	  }

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

   746 	    e.out_or_in=0;

   747 	    graph->first(e.v);

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

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

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

   751 	      graph->next(e.v);

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

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

   754 	    }

   755 	  }

   756 	} else {

   757 	  graph->next(e.in);

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

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

   760 	    graph->next(e.v);

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

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

   763 	  }

   764 	}

   765 	return e;

   766       }

   769     template< typename It >

   770     It first() const {

   771       It e;

   772       first(e);

   773       return e;

   774     }

   776     template< typename It >

   777     It first(Node v) const {

   778       It e;

   779       first(e, v);

   780       return e;

   781     }

   783     Node tail(Edge e) const {

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

   785     Node head(Edge e) const {

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

   788     Node aNode(OutEdgeIt e) const {

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

   790     Node bNode(OutEdgeIt e) const {

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

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

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

   796     bool valid(Edge e) const {

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

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

   800       if (e.out_or_in)

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

   802       else

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

   804     }

   806     Number free(const Edge& e) const {

   807       if (e.out_or_in)

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

   809       else

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

   811     }

   813     Number free(OldOutEdgeIt out) const {

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

   815     }

   817     Number free(OldInEdgeIt in) const {

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

   819     }

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

   822     public:

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

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

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

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

   827     };

   829 //     template <typename T>

   830 //     class NodeMap {

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

   832 //     public:

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

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

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

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

   837 //     };

   839     template <typename T>

   840     class EdgeMap {

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

   842     public:

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

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

   845       void set(Edge e, T a) {

   846 	if (e.out_or_in)

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

   848 	else

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

   850       }

   851       T get(Edge e) {

   852 	if (e.out_or_in)

   853 	  return forward_map.get(e.out);

   854 	else

   855 	  return backward_map.get(e.in);

   856       }

   857     };

   858   };

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

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

   862   protected:

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

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

   865   public:

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

   867 			   const CapacityMap& _capacity) :

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

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

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

   871 	OutEdgeIt e;

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

   873 	first_out_edges.set(n, e);

   874       }

   875     }

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

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

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

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

   883     //typedef Graph BaseGraph;

   885     //typedef typename Graph::Node Node;

   886     //typedef typename Graph::NodeIt NodeIt;

   888     //typedef typename Graph::Edge Edge;

   889     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   890     //typedef typename Graph::InEdgeIt InEdgeIt;

   891     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   892     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

   900     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

   903     NodeIt& first(NodeIt& n) const {

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

   905     }

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

   908       e=first_out_edges.get(n);

   909       return e;

   910     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   946     //}

   947     void erase(const Edge& e) {

   948       OutEdgeIt f(e);

   949       next(f);

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

   951     }

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

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

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

   957     public:

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

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

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

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

   962     };

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

   965     public:

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

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

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

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

   970     };

   971   };

   973   template<typename GraphWrapper>

   974   class FilterGraphWrapper {

   975   };

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

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

   980     //Graph* graph;

   982   public:

   983     //typedef Graph BaseGraph;

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

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

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

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

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

   991     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

   996   public:

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

   998 			   const CapacityMap& _capacity) :

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

  1000     }

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

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

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

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

  1006       return e;

  1007     }

  1009     NodeIt& next(NodeIt& e) const {

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

  1011     }

  1013     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1017       return e;

  1018     }

  1020     NodeIt& first(NodeIt& n) const {

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

  1022     }

  1024     void erase(const Edge& e) {

  1025       OutEdgeIt f(e);

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

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

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

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

  1030     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1078     public:

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

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

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

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

  1083     };

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

  1086     public:

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

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

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

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

  1091     };

  1093   public:

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

  1096   };

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

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

  1102 //   class ResGraphWrapper

  1103 //   {

  1104 //     Graph* graph;

  1106 //   public:

  1107 //     typedef Graph BaseGraph;

  1109 //     typedef typename Graph::Node Node;

  1110 //     typedef typename Graph::Edge Edge;

  1112 //     typedef typename Graph::NodeIt NodeIt;

  1114 //     class OutEdgeIt {

  1115 //     public:

  1116 //       //Graph::Node n;

  1117 //       bool out_or_in;

  1118 //       typename Graph::OutEdgeIt o;

  1119 //       typename Graph::InEdgeIt i;

  1120 //     };

  1121 //     class InEdgeIt {

  1122 //     public:

  1123 //       //Graph::Node n;

  1124 //       bool out_or_in;

  1125 //       typename Graph::OutEdgeIt o;

  1126 //       typename Graph::InEdgeIt i;

  1127 //     };

  1128 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1129 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1136 //     // Edge and SymEdge  is missing!!!!

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

  1139 //     //FIXME

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

  1141 //       {

  1142 // 	e.n=n;

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

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

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

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

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

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

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

  1150 // 	}

  1151 // 	return e;

  1152 //       }

  1153 // /*

  1154 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1155 //   {

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

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

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

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

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

  1161 //   }

  1162 //   else {

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

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

  1165 //   return e;

  1166 //   }

  1167 //   }

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

  1169 // */

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

  1172 //     //FIXME

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

  1174 //       {

  1175 // 	e.n=n;

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

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

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

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

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

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

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

  1183 // 	}

  1184 // 	return e;

  1185 //       }

  1186 // /*

  1187 //   InEdgeIt &goNext(InEdgeIt &e)

  1188 //   {

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

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

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

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

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

  1194 //   }

  1195 //   else {

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

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

  1198 //   return e;

  1199 //   }

  1200 //   }

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

  1202 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1244 //   };

  1246 } //namespace hugo

  1248 #endif //GRAPH_WRAPPER_H

author	marci
	Mon, 22 Mar 2004 12:17:44 +0000
changeset 230	734dd0649941
parent 212	c07e4dd32438
child 231	f62f11c9e6df
permissions	-rw-r--r--