lemon-0.x: src/work/marci/graph_wrapper.h@348f8fd374ee

     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*/GraphWrapper

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

   245   class RevGraphWrapper :

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

   247   protected:

   248     //Graph* graph;

   250   public:

   251     //typedef Graph BaseGraph;

   253     //typedef typename Graph::Node Node;

   254     //typedef typename Graph::NodeIt NodeIt;

   256     //typedef typename Graph::Edge Edge;

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

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

   259     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   260     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   307     template<typename T> class NodeMap :

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

   309     {

   310     public:

   311       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :

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

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

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

   315     };

   317     template<typename T> class EdgeMap :

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

   319     public:

   320       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :

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

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

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

   324     };

   325   };

   328   template<typename Graph>

   329   class UndirGraphWrapper {

   330   protected:

   331     Graph* graph;

   333   public:

   334     typedef Graph BaseGraph;

   336     typedef typename Graph::Node Node;

   337     typedef typename Graph::NodeIt NodeIt;

   339     //typedef typename Graph::Edge Edge;

   340     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   341     //typedef typename Graph::InEdgeIt InEdgeIt;

   342     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   343     //typedef typename Graph::EdgeIt EdgeIt;

   345     //private:

   346     typedef typename Graph::Edge GraphEdge;

   347     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   348     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   349     //public:

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

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

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

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

   357     class Edge {

   358       friend class UndirGraphWrapper<Graph>;

   359       bool out_or_in; //true iff out

   360       GraphOutEdgeIt out;

   361       GraphInEdgeIt in;

   362     public:

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

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

   365       operator GraphEdge() const {

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

   367       }

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

   369 	if (v.out_or_in)

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

   371 	else

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

   373       }

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

   375 	if (v.out_or_in)

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

   377 	else

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

   379       }

   380     };

   382     class OutEdgeIt : public Edge {

   383       friend class UndirGraphWrapper<Graph>;

   384     public:

   385       OutEdgeIt() : Edge() { }

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

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

   388 	out_or_in=true;

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

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

   391 	  out_or_in=false;

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

   393 	}

   394       }

   395     };

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

   398       e.out_or_in=true;

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

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

   401 	e.out_or_in=false;

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

   403       }

   404       return e;

   405     }

   407     OutEdgeIt& next(OutEdgeIt& e) const {

   408       if (e.out_or_in) {

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

   410 	graph->next(e.out);

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

   412 	  e.out_or_in=false;

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

   414 	}

   415       } else {

   416 	graph->next(e.in);

   417       }

   418       return e;

   419     }

   421     Node aNode(const OutEdgeIt& e) const {

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

   423     Node bNode(const OutEdgeIt& e) const {

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

   426     typedef OutEdgeIt InEdgeIt;

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

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

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

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

   433       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   469     public:

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

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

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

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

   474     };

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

   477     public:

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

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

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

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

   482     };

   483   };

   487 //   template<typename Graph>

   488 //   class SymGraphWrapper

   489 //   {

   490 //     Graph* graph;

   492 //   public:

   493 //     typedef Graph BaseGraph;

   495 //     typedef typename Graph::Node Node;

   496 //     typedef typename Graph::Edge Edge;

   498 //     typedef typename Graph::NodeIt NodeIt;

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

   501 //     //iranyitatlant, ami van

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

   503 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

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

   506 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   553 //   };

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

   557   class ResGraphWrapper {

   558   public:

   559     typedef Graph BaseGraph;

   560     typedef typename Graph::Node Node;

   561     typedef typename Graph::NodeIt NodeIt;

   562   private:

   563     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   564     typedef typename Graph::InEdgeIt OldInEdgeIt;

   565   protected:

   566     const Graph* graph;

   567     FlowMap* flow;

   568     const CapacityMap* capacity;

   569   public:

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

   572 	     const CapacityMap& _capacity) :

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

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

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

   578     class Edge;

   579     class OutEdgeIt;

   580     friend class Edge;

   581     friend class OutEdgeIt;

   583     class Edge {

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

   585     protected:

   586       bool out_or_in; //true, iff out

   587       OldOutEdgeIt out;

   588       OldInEdgeIt in;

   589     public:

   590       Edge() : out_or_in(true) { }

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

   592 //       bool valid() const {

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

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

   595 	if (v.out_or_in)

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

   597 	else

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

   599       }

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

   601 	if (v.out_or_in)

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

   603 	else

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

   605       }

   606     };

   609     class OutEdgeIt : public Edge {

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

   611     public:

   612       OutEdgeIt() { }

   613       //FIXME

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

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

   616     private:

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

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

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

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

   621 	  out_or_in=0;

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

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

   624 	}

   625       }

   626 //     public:

   627 //       OutEdgeIt& operator++() {

   628 // 	if (out_or_in) {

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

   630 // 	  ++out;

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

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

   633 // 	    out_or_in=0;

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

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

   636 // 	  }

   637 // 	} else {

   638 // 	  ++in;

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

   640 // 	}

   641 // 	return *this;

   642 //       }

   643     };

   645     class EdgeIt : public Edge {

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

   647       typename Graph::NodeIt v;

   648     public:

   649       EdgeIt() { }

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

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

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

   653 	resG.graph->first(v);

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

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

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

   657 	  resG.graph->next(v);

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

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

   660 	}

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

   662 	  out_or_in=0;

   663 	  resG.graph->first(v);

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

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

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

   667 	    resG.graph->next(v);

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

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

   670 	  }

   671 	}

   672       }

   673 //       EdgeIt& operator++() {

   674 // 	if (out_or_in) {

   675 // 	  ++out;

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

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

   678 // 	    ++v;

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

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

   681 // 	  }

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

   683 // 	    out_or_in=0;

   684 // 	    G->first(v);

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

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

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

   688 // 	      ++v;

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

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

   691 // 	    }

   692 // 	  }

   693 // 	} else {

   694 // 	  ++in;

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

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

   697 // 	    ++v;

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

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

   700 // 	  }

   701 // 	}

   702 // 	return *this;

   703 //       }

   704     };

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

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

   708       e=OutEdgeIt(*this, v);

   709       return e;

   710     }

   711     EdgeIt& first(EdgeIt& e) const {

   712       e=EdgeIt(*this);

   713       return e;

   714     }

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

   718     OutEdgeIt& next(OutEdgeIt& e) const {

   719       if (e.out_or_in) {

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

   721 	graph->next(e.out);

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

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

   724 	  e.out_or_in=0;

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

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

   727 	}

   728       } else {

   729 	graph->next(e.in);

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

   731       }

   732       return e;

   733     }

   735     EdgeIt& next(EdgeIt& e) const {

   736       if (e.out_or_in) {

   737 	graph->next(e.out);

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

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

   740 	    graph->next(e.v);

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

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

   743 	  }

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

   745 	    e.out_or_in=0;

   746 	    graph->first(e.v);

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

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

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

   750 	      graph->next(e.v);

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

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

   753 	    }

   754 	  }

   755 	} else {

   756 	  graph->next(e.in);

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

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

   759 	    graph->next(e.v);

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

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

   762 	  }

   763 	}

   764 	return e;

   765       }

   768     template< typename It >

   769     It first() const {

   770       It e;

   771       first(e);

   772       return e;

   773     }

   775     template< typename It >

   776     It first(Node v) const {

   777       It e;

   778       first(e, v);

   779       return e;

   780     }

   782     Node tail(Edge e) const {

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

   784     Node head(Edge e) const {

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

   787     Node aNode(OutEdgeIt e) const {

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

   789     Node bNode(OutEdgeIt e) const {

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

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

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

   795     bool valid(Edge e) const {

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

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

   799       if (e.out_or_in)

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

   801       else

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

   803     }

   805     Number free(const Edge& e) const {

   806       if (e.out_or_in)

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

   808       else

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

   810     }

   812     Number free(OldOutEdgeIt out) const {

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

   814     }

   816     Number free(OldInEdgeIt in) const {

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

   818     }

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

   821     public:

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

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

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

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

   826     };

   828 //     template <typename T>

   829 //     class NodeMap {

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

   831 //     public:

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

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

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

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

   836 //     };

   838     template <typename T>

   839     class EdgeMap {

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

   841     public:

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

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

   844       void set(Edge e, T a) {

   845 	if (e.out_or_in)

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

   847 	else

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

   849       }

   850       T get(Edge e) {

   851 	if (e.out_or_in)

   852 	  return forward_map.get(e.out);

   853 	else

   854 	  return backward_map.get(e.in);

   855       }

   856     };

   857   };

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

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

   861   protected:

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

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

   864   public:

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

   866 			   const CapacityMap& _capacity) :

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

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

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

   870 	OutEdgeIt e;

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

   872 	first_out_edges.set(n, e);

   873       }

   874     }

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

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

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

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

   882     //typedef Graph BaseGraph;

   884     //typedef typename Graph::Node Node;

   885     //typedef typename Graph::NodeIt NodeIt;

   887     //typedef typename Graph::Edge Edge;

   888     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   889     //typedef typename Graph::InEdgeIt InEdgeIt;

   890     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   891     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

   899     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

   902     NodeIt& first(NodeIt& n) const {

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

   904     }

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

   907       e=first_out_edges.get(n);

   908       return e;

   909     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   945     //}

   946     void erase(const Edge& e) {

   947       OutEdgeIt f(e);

   948       next(f);

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

   950     }

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

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

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

   956     public:

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

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

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

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

   961     };

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

   964     public:

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

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

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

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

   969     };

   970   };

   972   template<typename GraphWrapper>

   973   class FilterGraphWrapper {

   974   };

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

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

   979     //Graph* graph;

   981   public:

   982     //typedef Graph BaseGraph;

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

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

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

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

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

   990     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

   995   public:

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

   997 			   const CapacityMap& _capacity) :

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

   999     }

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

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

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

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

  1005       return e;

  1006     }

  1008     NodeIt& next(NodeIt& e) const {

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

  1010     }

  1012     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1016       return e;

  1017     }

  1019     NodeIt& first(NodeIt& n) const {

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

  1021     }

  1023     void erase(const Edge& e) {

  1024       OutEdgeIt f(e);

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

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

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

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

  1029     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1077     public:

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

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

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

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

  1082     };

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

  1085     public:

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

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

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

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

  1090     };

  1092   public:

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

  1095   };

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

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

  1101 //   class ResGraphWrapper

  1102 //   {

  1103 //     Graph* graph;

  1105 //   public:

  1106 //     typedef Graph BaseGraph;

  1108 //     typedef typename Graph::Node Node;

  1109 //     typedef typename Graph::Edge Edge;

  1111 //     typedef typename Graph::NodeIt NodeIt;

  1113 //     class OutEdgeIt {

  1114 //     public:

  1115 //       //Graph::Node n;

  1116 //       bool out_or_in;

  1117 //       typename Graph::OutEdgeIt o;

  1118 //       typename Graph::InEdgeIt i;

  1119 //     };

  1120 //     class InEdgeIt {

  1121 //     public:

  1122 //       //Graph::Node n;

  1123 //       bool out_or_in;

  1124 //       typename Graph::OutEdgeIt o;

  1125 //       typename Graph::InEdgeIt i;

  1126 //     };

  1127 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1128 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1135 //     // Edge and SymEdge  is missing!!!!

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

  1138 //     //FIXME

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

  1140 //       {

  1141 // 	e.n=n;

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

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

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

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

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

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

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

  1149 // 	}

  1150 // 	return e;

  1151 //       }

  1152 // /*

  1153 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1154 //   {

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

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

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

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

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

  1160 //   }

  1161 //   else {

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

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

  1164 //   return e;

  1165 //   }

  1166 //   }

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

  1168 // */

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

  1171 //     //FIXME

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

  1173 //       {

  1174 // 	e.n=n;

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

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

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

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

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

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

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

  1182 // 	}

  1183 // 	return e;

  1184 //       }

  1185 // /*

  1186 //   InEdgeIt &goNext(InEdgeIt &e)

  1187 //   {

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

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

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

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

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

  1193 //   }

  1194 //   else {

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

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

  1197 //   return e;

  1198 //   }

  1199 //   }

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

  1201 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1243 //   };

  1245 } //namespace hugo

  1247 #endif //GRAPH_WRAPPER_H

author	marci
	Mon, 22 Mar 2004 16:37:10 +0000
changeset 234	348f8fd374ee
parent 231	f62f11c9e6df
child 235	aa50acc936dc
permissions	-rw-r--r--