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

     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     RevGraphWrapper(GraphWrapper _gw) :

   337       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

   339     Node head(const Edge& e) const

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

   341     Node tail(const Edge& e) const

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

   343   };

   346 //   template<typename GraphWrapper>

   347 //   class UndirGraphWrapper {

   348 //   protected:

   349 //     //Graph* graph;

   350 //     GraphWrapper gw;

   352 //   public:

   353 //     typedef GraphWrapper BaseGraph;

   355 //     typedef typename GraphWrapper::Node Node;

   356 //     typedef typename GraphWrapper::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 GraphWrapper::Edge GraphEdge;

   366 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   367 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   368 //     //public:

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

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

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

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

   376 //     class Edge {

   377 //       friend class UndirGraphWrapper<GraphWrapper>;

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

   403 //     public:

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

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

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

   407 // 	: Edge() {

   408 // 	out_or_in=true;

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

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

   411 // 	  out_or_in=false;

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

   413 // 	}

   414 //       }

   415 //     };

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

   418 //       e.out_or_in=true;

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

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

   421 // 	e.out_or_in=false;

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

   423 //       }

   424 //       return e;

   425 //     }

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

   428 //       if (e.out_or_in) {

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

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

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

   432 // 	  e.out_or_in=false;

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

   434 // 	}

   435 //       } else {

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

   437 //       }

   438 //       return e;

   439 //     }

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

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

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

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

   446 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   489 //     public:

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

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

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

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

   494 //     };

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

   497 //     public:

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

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

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

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

   502 //     };

   503 //   };

   506   template<typename GraphWrapper>

   507   class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   508   protected:

   509 //    GraphWrapper gw;

   511   public:

   512     //typedef GraphWrapper BaseGraph;

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

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

   517     //private:

   518     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge GraphEdge;

   519     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt GraphOutEdgeIt;

   520     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt GraphInEdgeIt;

   521     //public:

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

   524     UndirGraphWrapper(GraphWrapper _gw) :

   525       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

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

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

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

   532     class Edge {

   533       friend class UndirGraphWrapper<GraphWrapper>;

   534       bool out_or_in; //true iff out

   535       GraphOutEdgeIt out;

   536       GraphInEdgeIt in;

   537     public:

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

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

   540       operator GraphEdge() const {

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

   542       }

   543 //FIXME

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

   545 //is it good?

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

   547 	if (v.out_or_in)

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

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

   550 	else

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

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

   553       }

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

   555 	if (v.out_or_in)

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

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

   558 	else

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

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

   561       }

   562     };

   564     class OutEdgeIt : public Edge {

   565       friend class UndirGraphWrapper<GraphWrapper>;

   566     public:

   567       OutEdgeIt() : Edge() { }

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

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

   570 	: Edge() {

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

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

   573       }

   574     };

   576     typedef OutEdgeIt InEdgeIt;

   578     class EdgeIt : public Edge {

   579       friend class UndirGraphWrapper<GraphWrapper>;

   580     protected:

   581       NodeIt v;

   582     public:

   583       EdgeIt() : Edge() { }

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

   585       EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)

   586 	: Edge() {

   587 	out_or_in=true;

   588 	//Node v;

   589 	_G.first(v);

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

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

   592 	  _G.gw.next(v);

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

   594 	}

   595       }

   596     };

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

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

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

   601       return e;

   602     }

   604     EdgeIt& first(EdgeIt& e) const {

   605       e.out_or_in=true;

   606       //NodeIt v;

   607       first(e.v);

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

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

   610 	gw.next(e.v);

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

   612       }

   613       return e;

   614     }

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

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

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

   620     OutEdgeIt& next(OutEdgeIt& e) const {

   621       if (e.out_or_in) {

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

   623 	gw.next(e.out);

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

   625       } else {

   626 	gw.next(e.in);

   627       }

   628       return e;

   629     }

   631     EdgeIt& next(EdgeIt& e) const {

   632       //NodeIt v=tail(e);

   633       gw.next(e.out);

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

   635 	next(e.v);

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

   637       }

   638       return e;

   639     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   664     Node aNode(const OutEdgeIt& e) const {

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

   666     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   680 //     public:

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

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

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

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

   685 //     };

   687 //     template<typename T> class EdgeMap :

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

   689 //     public:

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

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

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

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

   694 //     };

   695    };

   701 //   template<typename Graph>

   702 //   class SymGraphWrapper

   703 //   {

   704 //     Graph* graph;

   706 //   public:

   707 //     typedef Graph BaseGraph;

   709 //     typedef typename Graph::Node Node;

   710 //     typedef typename Graph::Edge Edge;

   712 //     typedef typename Graph::NodeIt NodeIt;

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

   715 //     //iranyitatlant, ami van

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

   717 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   719 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   720 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   767 //   };

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

   771   class ResGraphWrapper {

   772   public:

   773     typedef Graph BaseGraph;

   774     typedef typename Graph::Node Node;

   775     typedef typename Graph::NodeIt NodeIt;

   776   private:

   777     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   778     typedef typename Graph::InEdgeIt OldInEdgeIt;

   779   protected:

   780     const Graph* graph;

   781     FlowMap* flow;

   782     const CapacityMap* capacity;

   783   public:

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

   786 	     const CapacityMap& _capacity) :

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

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

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

   792     class Edge;

   793     class OutEdgeIt;

   794     friend class Edge;

   795     friend class OutEdgeIt;

   797     class Edge {

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

   799     protected:

   800       bool out_or_in; //true, iff out

   801       OldOutEdgeIt out;

   802       OldInEdgeIt in;

   803     public:

   804       Edge() : out_or_in(true) { }

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

   806 //       bool valid() const {

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

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

   809 	if (v.out_or_in)

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

   811 	else

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

   813       }

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

   815 	if (v.out_or_in)

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

   817 	else

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

   819       }

   820     };

   823     class OutEdgeIt : public Edge {

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

   825     public:

   826       OutEdgeIt() { }

   827       //FIXME

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

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

   830     private:

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

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

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

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

   835 	  out_or_in=0;

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

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

   838 	}

   839       }

   840 //     public:

   841 //       OutEdgeIt& operator++() {

   842 // 	if (out_or_in) {

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

   844 // 	  ++out;

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

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

   847 // 	    out_or_in=0;

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

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

   850 // 	  }

   851 // 	} else {

   852 // 	  ++in;

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

   854 // 	}

   855 // 	return *this;

   856 //       }

   857     };

   859     class EdgeIt : public Edge {

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

   861       typename Graph::NodeIt v;

   862     public:

   863       EdgeIt() { }

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

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

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

   867 	resG.graph->first(v);

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

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

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

   871 	  resG.graph->next(v);

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

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

   874 	}

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

   876 	  out_or_in=0;

   877 	  resG.graph->first(v);

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

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

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

   881 	    resG.graph->next(v);

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

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

   884 	  }

   885 	}

   886       }

   887 //       EdgeIt& operator++() {

   888 // 	if (out_or_in) {

   889 // 	  ++out;

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

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

   892 // 	    ++v;

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

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

   895 // 	  }

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

   897 // 	    out_or_in=0;

   898 // 	    G->first(v);

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

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

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

   902 // 	      ++v;

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

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

   905 // 	    }

   906 // 	  }

   907 // 	} else {

   908 // 	  ++in;

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

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

   911 // 	    ++v;

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

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

   914 // 	  }

   915 // 	}

   916 // 	return *this;

   917 //       }

   918     };

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

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

   922       e=OutEdgeIt(*this, v);

   923       return e;

   924     }

   925     EdgeIt& first(EdgeIt& e) const {

   926       e=EdgeIt(*this);

   927       return e;

   928     }

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

   932     OutEdgeIt& next(OutEdgeIt& e) const {

   933       if (e.out_or_in) {

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

   935 	graph->next(e.out);

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

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

   938 	  e.out_or_in=0;

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

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

   941 	}

   942       } else {

   943 	graph->next(e.in);

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

   945       }

   946       return e;

   947     }

   949     EdgeIt& next(EdgeIt& e) const {

   950       if (e.out_or_in) {

   951 	graph->next(e.out);

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

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

   954 	    graph->next(e.v);

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

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

   957 	  }

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

   959 	    e.out_or_in=0;

   960 	    graph->first(e.v);

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

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

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

   964 	      graph->next(e.v);

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

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

   967 	    }

   968 	  }

   969 	} else {

   970 	  graph->next(e.in);

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

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

   973 	    graph->next(e.v);

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

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

   976 	  }

   977 	}

   978 	return e;

   979       }

   982     template< typename It >

   983     It first() const {

   984       It e;

   985       first(e);

   986       return e;

   987     }

   989     template< typename It >

   990     It first(Node v) const {

   991       It e;

   992       first(e, v);

   993       return e;

   994     }

   996     Node tail(Edge e) const {

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

   998     Node head(Edge e) const {

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

  1001     Node aNode(OutEdgeIt e) const {

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

  1003     Node bNode(OutEdgeIt e) const {

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

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

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

  1009     bool valid(Edge e) const {

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

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

  1013       if (e.out_or_in)

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

  1015       else

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

  1017     }

  1019     Number free(const Edge& e) const {

  1020       if (e.out_or_in)

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

  1022       else

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

  1024     }

  1026     Number free(OldOutEdgeIt out) const {

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

  1028     }

  1030     Number free(OldInEdgeIt in) const {

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

  1032     }

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

  1035     public:

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

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

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

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

  1040     };

  1042 //     template <typename T>

  1043 //     class NodeMap {

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

  1045 //     public:

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

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

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

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

  1050 //     };

  1052     template <typename T>

  1053     class EdgeMap {

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

  1055     public:

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

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

  1058       void set(Edge e, T a) {

  1059 	if (e.out_or_in)

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

  1061 	else

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

  1063       }

  1064       T get(Edge e) {

  1065 	if (e.out_or_in)

  1066 	  return forward_map.get(e.out);

  1067 	else

  1068 	  return backward_map.get(e.in);

  1069       }

  1070     };

  1071   };

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

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

  1075   protected:

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

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

  1078   public:

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

  1080 			   const CapacityMap& _capacity) :

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

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

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

  1084 	OutEdgeIt e;

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

  1086 	first_out_edges.set(n, e);

  1087       }

  1088     }

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

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

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

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

  1096     //typedef Graph BaseGraph;

  1098     //typedef typename Graph::Node Node;

  1099     //typedef typename Graph::NodeIt NodeIt;

  1101     //typedef typename Graph::Edge Edge;

  1102     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1103     //typedef typename Graph::InEdgeIt InEdgeIt;

  1104     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1105     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

  1113     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

  1116     NodeIt& first(NodeIt& n) const {

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

  1118     }

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

  1121       e=first_out_edges.get(n);

  1122       return e;

  1123     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1159     //}

  1160     void erase(const Edge& e) {

  1161       OutEdgeIt f(e);

  1162       next(f);

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

  1164     }

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

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

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

  1170     public:

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

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

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

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

  1175     };

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

  1178     public:

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

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

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

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

  1183     };

  1184   };

  1186   template<typename GraphWrapper>

  1187   class FilterGraphWrapper {

  1188   };

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

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

  1193     //Graph* graph;

  1195   public:

  1196     //typedef Graph BaseGraph;

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

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

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

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

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

  1204     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

  1209   public:

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

  1211 			   const CapacityMap& _capacity) :

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

  1213     }

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

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

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

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

  1219       return e;

  1220     }

  1222     NodeIt& next(NodeIt& e) const {

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

  1224     }

  1226     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1230       return e;

  1231     }

  1233     NodeIt& first(NodeIt& n) const {

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

  1235     }

  1237     void erase(const Edge& e) {

  1238       OutEdgeIt f(e);

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

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

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

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

  1243     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1291     public:

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

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

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

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

  1296     };

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

  1299     public:

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

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

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

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

  1304     };

  1306   public:

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

  1309   };

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

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

  1315 //   class ResGraphWrapper

  1316 //   {

  1317 //     Graph* graph;

  1319 //   public:

  1320 //     typedef Graph BaseGraph;

  1322 //     typedef typename Graph::Node Node;

  1323 //     typedef typename Graph::Edge Edge;

  1325 //     typedef typename Graph::NodeIt NodeIt;

  1327 //     class OutEdgeIt {

  1328 //     public:

  1329 //       //Graph::Node n;

  1330 //       bool out_or_in;

  1331 //       typename Graph::OutEdgeIt o;

  1332 //       typename Graph::InEdgeIt i;

  1333 //     };

  1334 //     class InEdgeIt {

  1335 //     public:

  1336 //       //Graph::Node n;

  1337 //       bool out_or_in;

  1338 //       typename Graph::OutEdgeIt o;

  1339 //       typename Graph::InEdgeIt i;

  1340 //     };

  1341 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1342 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1349 //     // Edge and SymEdge  is missing!!!!

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

  1352 //     //FIXME

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

  1354 //       {

  1355 // 	e.n=n;

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

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

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

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

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

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

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

  1363 // 	}

  1364 // 	return e;

  1365 //       }

  1366 // /*

  1367 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1368 //   {

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

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

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

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

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

  1374 //   }

  1375 //   else {

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

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

  1378 //   return e;

  1379 //   }

  1380 //   }

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

  1382 // */

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

  1385 //     //FIXME

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

  1387 //       {

  1388 // 	e.n=n;

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

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

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

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

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

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

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

  1396 // 	}

  1397 // 	return e;

  1398 //       }

  1399 // /*

  1400 //   InEdgeIt &goNext(InEdgeIt &e)

  1401 //   {

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

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

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

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

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

  1407 //   }

  1408 //   else {

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

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

  1411 //   return e;

  1412 //   }

  1413 //   }

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

  1415 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1457 //   };

  1459 } //namespace hugo

  1461 #endif //GRAPH_WRAPPER_H

author	alpar
	Wed, 24 Mar 2004 13:06:06 +0000
changeset 242	b255f25ad394
parent 238	ad3bdd78f4f6
child 259	509ba9f136d2
permissions	-rw-r--r--