lemon-0.x: src/work/marci/graph_wrapper.h@7fb8b67d2c5e

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

   329   class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   330   public:

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

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

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

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

   336     Node head(const Edge& e) const

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

   338     Node tail(const Edge& e) const

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

   341     RevGraphWrapper(GraphWrapper _gw) :

   342       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

   343   };

   347 //   template<typename Graph>

   348 //   class UndirGraphWrapper {

   349 //   protected:

   350 //     Graph* graph;

   352 //   public:

   353 //     typedef Graph BaseGraph;

   355 //     typedef typename Graph::Node Node;

   356 //     typedef typename Graph::NodeIt NodeIt;

   358 //     //typedef typename Graph::Edge Edge;

   359 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   360 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   361 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   362 //     //typedef typename Graph::EdgeIt EdgeIt;

   364 //     //private:

   365 //     typedef typename Graph::Edge GraphEdge;

   366 //     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   367 //     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   368 //     //public:

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

   371 //     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

   376 //     class Edge {

   377 //       friend class UndirGraphWrapper<Graph>;

   378 //       bool out_or_in; //true iff out

   379 //       GraphOutEdgeIt out;

   380 //       GraphInEdgeIt in;

   381 //     public:

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

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

   384 //       operator GraphEdge() const {

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

   386 //       }

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

   388 // 	if (v.out_or_in)

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

   390 // 	else

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

   392 //       }

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

   394 // 	if (v.out_or_in)

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

   396 // 	else

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

   398 //       }

   399 //     };

   401 //     class OutEdgeIt : public Edge {

   402 //       friend class UndirGraphWrapper<Graph>;

   403 //     public:

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

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

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

   407 // 	out_or_in=true;

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

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

   410 // 	  out_or_in=false;

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

   412 // 	}

   413 //       }

   414 //     };

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

   417 //       e.out_or_in=true;

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

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

   420 // 	e.out_or_in=false;

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

   422 //       }

   423 //       return e;

   424 //     }

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

   427 //       if (e.out_or_in) {

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

   429 // 	graph->next(e.out);

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

   431 // 	  e.out_or_in=false;

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

   433 // 	}

   434 //       } else {

   435 // 	graph->next(e.in);

   436 //       }

   437 //       return e;

   438 //     }

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

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

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

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

   445 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   488 //     public:

   489 //       NodeMap(const UndirGraphWrapper<Graph>& _G) :

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

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

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

   493 //     };

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

   496 //     public:

   497 //       EdgeMap(const UndirGraphWrapper<Graph>& _G) :

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

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

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

   501 //     };

   502 //   };

   505   template<typename GraphWrapper>

   506   class UndirGraphWrapper {

   507   protected:

   508     //Graph* graph;

   509     GraphWrapper gw;

   511   public:

   512     typedef GraphWrapper BaseGraph;

   514     typedef typename GraphWrapper::Node Node;

   515     typedef typename GraphWrapper::NodeIt NodeIt;

   517     //typedef typename Graph::Edge Edge;

   518     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   519     //typedef typename Graph::InEdgeIt InEdgeIt;

   520     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   521     //typedef typename Graph::EdgeIt EdgeIt;

   523     //private:

   524     typedef typename GraphWrapper::Edge GraphEdge;

   525     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   526     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   527     //public:

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

   530     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

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

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

   535     class Edge {

   536       friend class UndirGraphWrapper<GraphWrapper>;

   537       bool out_or_in; //true iff out

   538       GraphOutEdgeIt out;

   539       GraphInEdgeIt in;

   540     public:

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

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

   543       operator GraphEdge() const {

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

   545       }

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

   547 	if (v.out_or_in)

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

   549 	else

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

   551       }

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

   553 	if (v.out_or_in)

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

   555 	else

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

   557       }

   558     };

   560     class OutEdgeIt : public Edge {

   561       friend class UndirGraphWrapper<GraphWrapper>;

   562     public:

   563       OutEdgeIt() : Edge() { }

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

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

   566 	: Edge() {

   567 	out_or_in=true;

   568 	_G.gw.first(out, n);

   569 	if (!(_G.gw.valid(out))) {

   570 	  out_or_in=false;

   571 	  _G.gw.first(in, n);

   572 	}

   573       }

   574     };

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

   577       e.out_or_in=true;

   578       gw.first(e.out, n);

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

   580 	e.out_or_in=false;

   581 	gw.first(e.in, n);

   582       }

   583       return e;

   584     }

   586     OutEdgeIt& next(OutEdgeIt& e) const {

   587       if (e.out_or_in) {

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

   589 	gw.next(e.out);

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

   591 	  e.out_or_in=false;

   592 	  gw.first(e.in, n);

   593 	}

   594       } else {

   595 	gw.next(e.in);

   596       }

   597       return e;

   598     }

   600     Node aNode(const OutEdgeIt& e) const {

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

   602     Node bNode(const OutEdgeIt& e) const {

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

   605     typedef OutEdgeIt InEdgeIt;

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

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

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

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

   612       return gw.getNext(i); }

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

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

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

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

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

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

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

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

   625       { return gw.valid(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   648     public:

   649       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

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

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

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

   653     };

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

   656     public:

   657       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

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

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

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

   661     };

   662   };

   668 //   template<typename Graph>

   669 //   class SymGraphWrapper

   670 //   {

   671 //     Graph* graph;

   673 //   public:

   674 //     typedef Graph BaseGraph;

   676 //     typedef typename Graph::Node Node;

   677 //     typedef typename Graph::Edge Edge;

   679 //     typedef typename Graph::NodeIt NodeIt;

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

   682 //     //iranyitatlant, ami van

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

   684 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   686 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   687 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   734 //   };

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

   738   class ResGraphWrapper {

   739   public:

   740     typedef Graph BaseGraph;

   741     typedef typename Graph::Node Node;

   742     typedef typename Graph::NodeIt NodeIt;

   743   private:

   744     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   745     typedef typename Graph::InEdgeIt OldInEdgeIt;

   746   protected:

   747     const Graph* graph;

   748     FlowMap* flow;

   749     const CapacityMap* capacity;

   750   public:

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

   753 	     const CapacityMap& _capacity) :

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

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

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

   759     class Edge;

   760     class OutEdgeIt;

   761     friend class Edge;

   762     friend class OutEdgeIt;

   764     class Edge {

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

   766     protected:

   767       bool out_or_in; //true, iff out

   768       OldOutEdgeIt out;

   769       OldInEdgeIt in;

   770     public:

   771       Edge() : out_or_in(true) { }

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

   773 //       bool valid() const {

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

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

   776 	if (v.out_or_in)

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

   778 	else

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

   780       }

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

   782 	if (v.out_or_in)

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

   784 	else

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

   786       }

   787     };

   790     class OutEdgeIt : public Edge {

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

   792     public:

   793       OutEdgeIt() { }

   794       //FIXME

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

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

   797     private:

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

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

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

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

   802 	  out_or_in=0;

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

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

   805 	}

   806       }

   807 //     public:

   808 //       OutEdgeIt& operator++() {

   809 // 	if (out_or_in) {

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

   811 // 	  ++out;

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

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

   814 // 	    out_or_in=0;

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

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

   817 // 	  }

   818 // 	} else {

   819 // 	  ++in;

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

   821 // 	}

   822 // 	return *this;

   823 //       }

   824     };

   826     class EdgeIt : public Edge {

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

   828       typename Graph::NodeIt v;

   829     public:

   830       EdgeIt() { }

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

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

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

   834 	resG.graph->first(v);

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

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

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

   838 	  resG.graph->next(v);

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

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

   841 	}

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

   843 	  out_or_in=0;

   844 	  resG.graph->first(v);

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

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

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

   848 	    resG.graph->next(v);

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

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

   851 	  }

   852 	}

   853       }

   854 //       EdgeIt& operator++() {

   855 // 	if (out_or_in) {

   856 // 	  ++out;

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

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

   859 // 	    ++v;

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

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

   862 // 	  }

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

   864 // 	    out_or_in=0;

   865 // 	    G->first(v);

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

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

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

   869 // 	      ++v;

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

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

   872 // 	    }

   873 // 	  }

   874 // 	} else {

   875 // 	  ++in;

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

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

   878 // 	    ++v;

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

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

   881 // 	  }

   882 // 	}

   883 // 	return *this;

   884 //       }

   885     };

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

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

   889       e=OutEdgeIt(*this, v);

   890       return e;

   891     }

   892     EdgeIt& first(EdgeIt& e) const {

   893       e=EdgeIt(*this);

   894       return e;

   895     }

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

   899     OutEdgeIt& next(OutEdgeIt& e) const {

   900       if (e.out_or_in) {

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

   902 	graph->next(e.out);

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

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

   905 	  e.out_or_in=0;

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

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

   908 	}

   909       } else {

   910 	graph->next(e.in);

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

   912       }

   913       return e;

   914     }

   916     EdgeIt& next(EdgeIt& e) const {

   917       if (e.out_or_in) {

   918 	graph->next(e.out);

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

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

   921 	    graph->next(e.v);

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

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

   924 	  }

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

   926 	    e.out_or_in=0;

   927 	    graph->first(e.v);

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

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

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

   931 	      graph->next(e.v);

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

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

   934 	    }

   935 	  }

   936 	} else {

   937 	  graph->next(e.in);

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

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

   940 	    graph->next(e.v);

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

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

   943 	  }

   944 	}

   945 	return e;

   946       }

   949     template< typename It >

   950     It first() const {

   951       It e;

   952       first(e);

   953       return e;

   954     }

   956     template< typename It >

   957     It first(Node v) const {

   958       It e;

   959       first(e, v);

   960       return e;

   961     }

   963     Node tail(Edge e) const {

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

   965     Node head(Edge e) const {

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

   968     Node aNode(OutEdgeIt e) const {

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

   970     Node bNode(OutEdgeIt e) const {

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

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

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

   976     bool valid(Edge e) const {

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

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

   980       if (e.out_or_in)

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

   982       else

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

   984     }

   986     Number free(const Edge& e) const {

   987       if (e.out_or_in)

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

   989       else

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

   991     }

   993     Number free(OldOutEdgeIt out) const {

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

   995     }

   997     Number free(OldInEdgeIt in) const {

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

   999     }

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

  1002     public:

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

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

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

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

  1007     };

  1009 //     template <typename T>

  1010 //     class NodeMap {

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

  1012 //     public:

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

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

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

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

  1017 //     };

  1019     template <typename T>

  1020     class EdgeMap {

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

  1022     public:

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

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

  1025       void set(Edge e, T a) {

  1026 	if (e.out_or_in)

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

  1028 	else

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

  1030       }

  1031       T get(Edge e) {

  1032 	if (e.out_or_in)

  1033 	  return forward_map.get(e.out);

  1034 	else

  1035 	  return backward_map.get(e.in);

  1036       }

  1037     };

  1038   };

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

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

  1042   protected:

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

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

  1045   public:

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

  1047 			   const CapacityMap& _capacity) :

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

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

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

  1051 	OutEdgeIt e;

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

  1053 	first_out_edges.set(n, e);

  1054       }

  1055     }

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

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

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

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

  1063     //typedef Graph BaseGraph;

  1065     //typedef typename Graph::Node Node;

  1066     //typedef typename Graph::NodeIt NodeIt;

  1068     //typedef typename Graph::Edge Edge;

  1069     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1070     //typedef typename Graph::InEdgeIt InEdgeIt;

  1071     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1072     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

  1080     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

  1083     NodeIt& first(NodeIt& n) const {

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

  1085     }

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

  1088       e=first_out_edges.get(n);

  1089       return e;

  1090     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1126     //}

  1127     void erase(const Edge& e) {

  1128       OutEdgeIt f(e);

  1129       next(f);

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

  1131     }

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

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

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

  1137     public:

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

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

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

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

  1142     };

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

  1145     public:

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

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

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

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

  1150     };

  1151   };

  1153   template<typename GraphWrapper>

  1154   class FilterGraphWrapper {

  1155   };

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

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

  1160     //Graph* graph;

  1162   public:

  1163     //typedef Graph BaseGraph;

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

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

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

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

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

  1171     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

  1176   public:

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

  1178 			   const CapacityMap& _capacity) :

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

  1180     }

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

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

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

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

  1186       return e;

  1187     }

  1189     NodeIt& next(NodeIt& e) const {

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

  1191     }

  1193     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1197       return e;

  1198     }

  1200     NodeIt& first(NodeIt& n) const {

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

  1202     }

  1204     void erase(const Edge& e) {

  1205       OutEdgeIt f(e);

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

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

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

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

  1210     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1258     public:

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

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

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

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

  1263     };

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

  1266     public:

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

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

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

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

  1271     };

  1273   public:

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

  1276   };

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

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

  1282 //   class ResGraphWrapper

  1283 //   {

  1284 //     Graph* graph;

  1286 //   public:

  1287 //     typedef Graph BaseGraph;

  1289 //     typedef typename Graph::Node Node;

  1290 //     typedef typename Graph::Edge Edge;

  1292 //     typedef typename Graph::NodeIt NodeIt;

  1294 //     class OutEdgeIt {

  1295 //     public:

  1296 //       //Graph::Node n;

  1297 //       bool out_or_in;

  1298 //       typename Graph::OutEdgeIt o;

  1299 //       typename Graph::InEdgeIt i;

  1300 //     };

  1301 //     class InEdgeIt {

  1302 //     public:

  1303 //       //Graph::Node n;

  1304 //       bool out_or_in;

  1305 //       typename Graph::OutEdgeIt o;

  1306 //       typename Graph::InEdgeIt i;

  1307 //     };

  1308 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1309 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1316 //     // Edge and SymEdge  is missing!!!!

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

  1319 //     //FIXME

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

  1321 //       {

  1322 // 	e.n=n;

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

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

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

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

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

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

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

  1330 // 	}

  1331 // 	return e;

  1332 //       }

  1333 // /*

  1334 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1335 //   {

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

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

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

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

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

  1341 //   }

  1342 //   else {

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

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

  1345 //   return e;

  1346 //   }

  1347 //   }

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

  1349 // */

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

  1352 //     //FIXME

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

  1354 //       {

  1355 // 	e.n=n;

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

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

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

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

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

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

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

  1363 // 	}

  1364 // 	return e;

  1365 //       }

  1366 // /*

  1367 //   InEdgeIt &goNext(InEdgeIt &e)

  1368 //   {

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

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

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

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

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

  1374 //   }

  1375 //   else {

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

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

  1378 //   return e;

  1379 //   }

  1380 //   }

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

  1382 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1424 //   };

  1426 } //namespace hugo

  1428 #endif //GRAPH_WRAPPER_H

author	marci
	Tue, 23 Mar 2004 11:12:48 +0000
changeset 237	7fb8b67d2c5e
parent 236	ea3de9530ee8
child 238	ad3bdd78f4f6
permissions	-rw-r--r--