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

     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       friend bool operator==(const Edge& u, const Edge& v) {

   544 	if (v.out_or_in)

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

   546 	else

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

   548       }

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

   550 	if (v.out_or_in)

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

   552 	else

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

   554       }

   555     };

   557     class OutEdgeIt : public Edge {

   558       friend class UndirGraphWrapper<GraphWrapper>;

   559     public:

   560       OutEdgeIt() : Edge() { }

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

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

   563 	: Edge() {

   564 	out_or_in=true;

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

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

   567 	  out_or_in=false;

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

   569 	}

   570       }

   571     };

   573     typedef OutEdgeIt InEdgeIt;

   575     class EdgeIt : public Edge {

   576       friend class UndirGraphWrapper<GraphWrapper>;

   577     protected:

   578       NodeIt v;

   579     public:

   580       EdgeIt() : Edge() { }

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

   582       EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)

   583 	: Edge() {

   584 	out_or_in=true;

   585 	//Node v;

   586 	_G.first(v);

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

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

   589 	  _G.gw.next(v);

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

   591 	}

   592       }

   593     };

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

   596       e.out_or_in=true;

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

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

   599 	e.out_or_in=false;

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

   601       }

   602       return e;

   603     }

   605     EdgeIt& first(EdgeIt& e) const {

   606       e.out_or_in=true;

   607       //NodeIt v;

   608       first(e.v);

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

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

   611 	gw.next(e.v);

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

   613       }

   614       return e;

   615     }

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

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

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

   621     OutEdgeIt& next(OutEdgeIt& e) const {

   622       if (e.out_or_in) {

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

   624 	gw.next(e.out);

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

   626 	  e.out_or_in=false;

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

   628 	}

   629       } else {

   630 	gw.next(e.in);

   631       }

   632       return e;

   633     }

   635     EdgeIt& next(EdgeIt& e) const {

   636       //NodeIt v=tail(e);

   637       gw.next(e.out);

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

   639 	next(e.v);

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

   641       }

   642       return e;

   643     }

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

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

   648       return gw.getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   670     Node aNode(const OutEdgeIt& e) const {

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

   672     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   686 //     public:

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

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

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

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

   691 //     };

   693 //     template<typename T> class EdgeMap :

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

   695 //     public:

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

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

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

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

   700 //     };

   701    };

   707 //   template<typename Graph>

   708 //   class SymGraphWrapper

   709 //   {

   710 //     Graph* graph;

   712 //   public:

   713 //     typedef Graph BaseGraph;

   715 //     typedef typename Graph::Node Node;

   716 //     typedef typename Graph::Edge Edge;

   718 //     typedef typename Graph::NodeIt NodeIt;

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

   721 //     //iranyitatlant, ami van

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

   723 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   725 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   726 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   773 //   };

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

   777   class ResGraphWrapper {

   778   public:

   779     typedef Graph BaseGraph;

   780     typedef typename Graph::Node Node;

   781     typedef typename Graph::NodeIt NodeIt;

   782   private:

   783     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   784     typedef typename Graph::InEdgeIt OldInEdgeIt;

   785   protected:

   786     const Graph* graph;

   787     FlowMap* flow;

   788     const CapacityMap* capacity;

   789   public:

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

   792 	     const CapacityMap& _capacity) :

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

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

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

   798     class Edge;

   799     class OutEdgeIt;

   800     friend class Edge;

   801     friend class OutEdgeIt;

   803     class Edge {

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

   805     protected:

   806       bool out_or_in; //true, iff out

   807       OldOutEdgeIt out;

   808       OldInEdgeIt in;

   809     public:

   810       Edge() : out_or_in(true) { }

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

   812 //       bool valid() const {

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

   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       friend bool operator!=(const Edge& u, const Edge& v) {

   821 	if (v.out_or_in)

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

   823 	else

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

   825       }

   826     };

   829     class OutEdgeIt : public Edge {

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

   831     public:

   832       OutEdgeIt() { }

   833       //FIXME

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

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

   836     private:

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

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

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

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

   841 	  out_or_in=0;

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

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

   844 	}

   845       }

   846 //     public:

   847 //       OutEdgeIt& operator++() {

   848 // 	if (out_or_in) {

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

   850 // 	  ++out;

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

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

   853 // 	    out_or_in=0;

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

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

   856 // 	  }

   857 // 	} else {

   858 // 	  ++in;

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

   860 // 	}

   861 // 	return *this;

   862 //       }

   863     };

   865     class EdgeIt : public Edge {

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

   867       typename Graph::NodeIt v;

   868     public:

   869       EdgeIt() { }

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

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

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

   873 	resG.graph->first(v);

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

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

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

   877 	  resG.graph->next(v);

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

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

   880 	}

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

   882 	  out_or_in=0;

   883 	  resG.graph->first(v);

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

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

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

   887 	    resG.graph->next(v);

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

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

   890 	  }

   891 	}

   892       }

   893 //       EdgeIt& operator++() {

   894 // 	if (out_or_in) {

   895 // 	  ++out;

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

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

   898 // 	    ++v;

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

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

   901 // 	  }

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

   903 // 	    out_or_in=0;

   904 // 	    G->first(v);

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

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

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

   908 // 	      ++v;

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

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

   911 // 	    }

   912 // 	  }

   913 // 	} else {

   914 // 	  ++in;

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

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

   917 // 	    ++v;

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

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

   920 // 	  }

   921 // 	}

   922 // 	return *this;

   923 //       }

   924     };

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

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

   928       e=OutEdgeIt(*this, v);

   929       return e;

   930     }

   931     EdgeIt& first(EdgeIt& e) const {

   932       e=EdgeIt(*this);

   933       return e;

   934     }

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

   938     OutEdgeIt& next(OutEdgeIt& e) const {

   939       if (e.out_or_in) {

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

   941 	graph->next(e.out);

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

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

   944 	  e.out_or_in=0;

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

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

   947 	}

   948       } else {

   949 	graph->next(e.in);

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

   951       }

   952       return e;

   953     }

   955     EdgeIt& next(EdgeIt& e) const {

   956       if (e.out_or_in) {

   957 	graph->next(e.out);

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

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

   960 	    graph->next(e.v);

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

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

   963 	  }

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

   965 	    e.out_or_in=0;

   966 	    graph->first(e.v);

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

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

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

   970 	      graph->next(e.v);

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

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

   973 	    }

   974 	  }

   975 	} else {

   976 	  graph->next(e.in);

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

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

   979 	    graph->next(e.v);

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

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

   982 	  }

   983 	}

   984 	return e;

   985       }

   988     template< typename It >

   989     It first() const {

   990       It e;

   991       first(e);

   992       return e;

   993     }

   995     template< typename It >

   996     It first(Node v) const {

   997       It e;

   998       first(e, v);

   999       return e;

  1000     }

  1002     Node tail(Edge e) const {

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

  1004     Node head(Edge e) const {

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

  1007     Node aNode(OutEdgeIt e) const {

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

  1009     Node bNode(OutEdgeIt e) const {

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

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

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

  1015     bool valid(Edge e) const {

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

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

  1019       if (e.out_or_in)

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

  1021       else

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

  1023     }

  1025     Number free(const Edge& e) const {

  1026       if (e.out_or_in)

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

  1028       else

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

  1030     }

  1032     Number free(OldOutEdgeIt out) const {

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

  1034     }

  1036     Number free(OldInEdgeIt in) const {

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

  1038     }

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

  1041     public:

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

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

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

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

  1046     };

  1048 //     template <typename T>

  1049 //     class NodeMap {

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

  1051 //     public:

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

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

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

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

  1056 //     };

  1058     template <typename T>

  1059     class EdgeMap {

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

  1061     public:

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

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

  1064       void set(Edge e, T a) {

  1065 	if (e.out_or_in)

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

  1067 	else

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

  1069       }

  1070       T get(Edge e) {

  1071 	if (e.out_or_in)

  1072 	  return forward_map.get(e.out);

  1073 	else

  1074 	  return backward_map.get(e.in);

  1075       }

  1076     };

  1077   };

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

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

  1081   protected:

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

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

  1084   public:

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

  1086 			   const CapacityMap& _capacity) :

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

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

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

  1090 	OutEdgeIt e;

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

  1092 	first_out_edges.set(n, e);

  1093       }

  1094     }

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

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

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

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

  1102     //typedef Graph BaseGraph;

  1104     //typedef typename Graph::Node Node;

  1105     //typedef typename Graph::NodeIt NodeIt;

  1107     //typedef typename Graph::Edge Edge;

  1108     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1109     //typedef typename Graph::InEdgeIt InEdgeIt;

  1110     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1111     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

  1119     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

  1122     NodeIt& first(NodeIt& n) const {

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

  1124     }

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

  1127       e=first_out_edges.get(n);

  1128       return e;

  1129     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1165     //}

  1166     void erase(const Edge& e) {

  1167       OutEdgeIt f(e);

  1168       next(f);

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

  1170     }

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

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

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

  1176     public:

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

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

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

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

  1181     };

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

  1184     public:

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

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

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

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

  1189     };

  1190   };

  1192   template<typename GraphWrapper>

  1193   class FilterGraphWrapper {

  1194   };

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

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

  1199     //Graph* graph;

  1201   public:

  1202     //typedef Graph BaseGraph;

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

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

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

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

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

  1210     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

  1215   public:

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

  1217 			   const CapacityMap& _capacity) :

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

  1219     }

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

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

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

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

  1225       return e;

  1226     }

  1228     NodeIt& next(NodeIt& e) const {

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

  1230     }

  1232     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1236       return e;

  1237     }

  1239     NodeIt& first(NodeIt& n) const {

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

  1241     }

  1243     void erase(const Edge& e) {

  1244       OutEdgeIt f(e);

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

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

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

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

  1249     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1297     public:

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

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

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

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

  1302     };

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

  1305     public:

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

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

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

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

  1310     };

  1312   public:

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

  1315   };

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

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

  1321 //   class ResGraphWrapper

  1322 //   {

  1323 //     Graph* graph;

  1325 //   public:

  1326 //     typedef Graph BaseGraph;

  1328 //     typedef typename Graph::Node Node;

  1329 //     typedef typename Graph::Edge Edge;

  1331 //     typedef typename Graph::NodeIt NodeIt;

  1333 //     class OutEdgeIt {

  1334 //     public:

  1335 //       //Graph::Node n;

  1336 //       bool out_or_in;

  1337 //       typename Graph::OutEdgeIt o;

  1338 //       typename Graph::InEdgeIt i;

  1339 //     };

  1340 //     class InEdgeIt {

  1341 //     public:

  1342 //       //Graph::Node n;

  1343 //       bool out_or_in;

  1344 //       typename Graph::OutEdgeIt o;

  1345 //       typename Graph::InEdgeIt i;

  1346 //     };

  1347 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1348 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1355 //     // Edge and SymEdge  is missing!!!!

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

  1358 //     //FIXME

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

  1360 //       {

  1361 // 	e.n=n;

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

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

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

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

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

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

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

  1369 // 	}

  1370 // 	return e;

  1371 //       }

  1372 // /*

  1373 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1374 //   {

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

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

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

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

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

  1380 //   }

  1381 //   else {

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

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

  1384 //   return e;

  1385 //   }

  1386 //   }

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

  1388 // */

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

  1391 //     //FIXME

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

  1393 //       {

  1394 // 	e.n=n;

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

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

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

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

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

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

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

  1402 // 	}

  1403 // 	return e;

  1404 //       }

  1405 // /*

  1406 //   InEdgeIt &goNext(InEdgeIt &e)

  1407 //   {

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

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

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

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

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

  1413 //   }

  1414 //   else {

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

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

  1417 //   return e;

  1418 //   }

  1419 //   }

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

  1421 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1463 //   };

  1465 } //namespace hugo

  1467 #endif //GRAPH_WRAPPER_H

author	marci
	Tue, 23 Mar 2004 13:31:02 +0000
changeset 238	ad3bdd78f4f6
parent 237	7fb8b67d2c5e
child 239	3f76d1aa9d37
permissions	-rw-r--r--