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

     1 // -*- c++ -*-

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_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     typedef TrivGraphWrapper<const Graph> GraphWrapper;

   782     GraphWrapper gw;

   783     FlowMap* flow;

   784     const CapacityMap* capacity;

   785   public:

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

   788 	     const CapacityMap& _capacity) :

   789       gw(_G), flow(&_flow), capacity(&_capacity) { }

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

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

   794     class Edge;

   795     class OutEdgeIt;

   796     friend class Edge;

   797     friend class OutEdgeIt;

   799     class Edge {

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

   801     protected:

   802       bool out_or_in; //true, iff out

   803       OldOutEdgeIt out;

   804       OldInEdgeIt in;

   805     public:

   806       Edge() : out_or_in(true) { }

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

   808 //       bool valid() const {

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

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

   811 	if (v.out_or_in)

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

   813 	else

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

   815       }

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

   817 	if (v.out_or_in)

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

   819 	else

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

   821       }

   822     };

   825     class OutEdgeIt : public Edge {

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

   827     public:

   828       OutEdgeIt() { }

   829       //FIXME

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

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

   832     private:

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

   834 	resG.gw.first(out, v);

   835 	while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }

   836 	if (!resG.gw.valid(out)) {

   837 	  out_or_in=0;

   838 	  resG.gw.first(in, v);

   839 	  while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }

   840 	}

   841       }

   842 //     public:

   843 //       OutEdgeIt& operator++() {

   844 // 	if (out_or_in) {

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

   846 // 	  ++out;

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

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

   849 // 	    out_or_in=0;

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

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

   852 // 	  }

   853 // 	} else {

   854 // 	  ++in;

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

   856 // 	}

   857 // 	return *this;

   858 //       }

   859     };

   861     class EdgeIt : public Edge {

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

   863       typename Graph::NodeIt v;

   864     public:

   865       EdgeIt() { }

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

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

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

   869 	resG.gw.first(v);

   870 	if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);

   871 	while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }

   872 	while (resG.gw.valid(v) && !resG.gw.valid(out)) {

   873 	  resG.gw.next(v);

   874 	  if (resG.gw.valid(v)) resG.gw.first(out, v);

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

   876 	}

   877 	if (!resG.gw.valid(out)) {

   878 	  out_or_in=0;

   879 	  resG.gw.first(v);

   880 	  if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);

   881 	  while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }

   882 	  while (resG.gw.valid(v) && !resG.gw.valid(in)) {

   883 	    resG.gw.next(v);

   884 	    if (resG.gw.valid(v)) resG.gw.first(in, v);

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

   886 	  }

   887 	}

   888       }

   889 //       EdgeIt& operator++() {

   890 // 	if (out_or_in) {

   891 // 	  ++out;

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

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

   894 // 	    ++v;

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

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

   897 // 	  }

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

   899 // 	    out_or_in=0;

   900 // 	    G->first(v);

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

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

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

   904 // 	      ++v;

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

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

   907 // 	    }

   908 // 	  }

   909 // 	} else {

   910 // 	  ++in;

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

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

   913 // 	    ++v;

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

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

   916 // 	  }

   917 // 	}

   918 // 	return *this;

   919 //       }

   920     };

   922     NodeIt& first(NodeIt& v) const { return gw.first(v); }

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

   924       e=OutEdgeIt(*this, v);

   925       return e;

   926     }

   927     EdgeIt& first(EdgeIt& e) const {

   928       e=EdgeIt(*this);

   929       return e;

   930     }

   932     NodeIt& next(NodeIt& n) const { return gw.next(n); }

   934     OutEdgeIt& next(OutEdgeIt& e) const {

   935       if (e.out_or_in) {

   936 	Node v=gw.aNode(e.out);

   937 	gw.next(e.out);

   938 	while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }

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

   940 	  e.out_or_in=0;

   941 	  gw.first(e.in, v);

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

   943 	}

   944       } else {

   945 	gw.next(e.in);

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

   947       }

   948       return e;

   949     }

   951     EdgeIt& next(EdgeIt& e) const {

   952       if (e.out_or_in) {

   953 	gw.next(e.out);

   954 	while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }

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

   956 	    gw.next(e.v);

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

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

   959 	  }

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

   961 	    e.out_or_in=0;

   962 	    gw.first(e.v);

   963 	    if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);

   964 	    while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }

   965 	    while (gw.valid(e.v) && !gw.valid(e.in)) {

   966 	      gw.next(e.v);

   967 	      if (gw.valid(e.v)) gw.first(e.in, e.v);

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

   969 	    }

   970 	  }

   971 	} else {

   972 	  gw.next(e.in);

   973 	  while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }

   974 	  while (gw.valid(e.v) && !gw.valid(e.in)) {

   975 	    gw.next(e.v);

   976 	    if (gw.valid(e.v)) gw.first(e.in, e.v);

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

   978 	  }

   979 	}

   980 	return e;

   981       }

   984     template< typename It >

   985     It first() const {

   986       It e;

   987       first(e);

   988       return e;

   989     }

   991     template< typename It >

   992     It first(Node v) const {

   993       It e;

   994       first(e, v);

   995       return e;

   996     }

   998     Node tail(Edge e) const {

   999       return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }

  1000     Node head(Edge e) const {

  1001       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

  1003     Node aNode(OutEdgeIt e) const {

  1004       return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }

  1005     Node bNode(OutEdgeIt e) const {

  1006       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

  1008     int id(Node v) const { return gw.id(v); }

  1010     bool valid(Node n) const { return gw.valid(n); }

  1011     bool valid(Edge e) const {

  1012       return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }

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

  1015       if (e.out_or_in)

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

  1017       else

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

  1019     }

  1021     Number free(const Edge& e) const {

  1022       if (e.out_or_in)

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

  1024       else

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

  1026     }

  1028     Number free(OldOutEdgeIt out) const {

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

  1030     }

  1032     Number free(OldInEdgeIt in) const {

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

  1034     }

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

  1037     public:

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

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

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

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

  1042     };

  1044 //     template <typename T>

  1045 //     class NodeMap {

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

  1047 //     public:

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

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

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

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

  1052 //     };

  1054     template <typename T>

  1055     class EdgeMap {

  1056       typename GraphWrapper::EdgeMap<T> forward_map, backward_map;

  1057     public:

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

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

  1060       void set(Edge e, T a) {

  1061 	if (e.out_or_in)

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

  1063 	else

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

  1065       }

  1066       T get(Edge e) {

  1067 	if (e.out_or_in)

  1068 	  return forward_map.get(e.out);

  1069 	else

  1070 	  return backward_map.get(e.in);

  1071       }

  1072     };

  1073   };

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

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

  1077   protected:

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

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

  1080   public:

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

  1082 			   const CapacityMap& _capacity) :

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

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

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

  1086 	OutEdgeIt e;

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

  1088 	first_out_edges.set(n, e);

  1089       }

  1090     }

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

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

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

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

  1098     //typedef Graph BaseGraph;

  1100     //typedef typename Graph::Node Node;

  1101     //typedef typename Graph::NodeIt NodeIt;

  1103     //typedef typename Graph::Edge Edge;

  1104     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1105     //typedef typename Graph::InEdgeIt InEdgeIt;

  1106     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1107     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

  1115     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

  1118     NodeIt& first(NodeIt& n) const {

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

  1120     }

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

  1123       e=first_out_edges.get(n);

  1124       return e;

  1125     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1151     //  return gw.aNode(e); }

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

  1153     //  return gw.bNode(e); }

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

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

  1157     //  return gw.addEdge(tail, head); }

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

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

  1161     //}

  1162     void erase(const Edge& e) {

  1163       OutEdgeIt f(e);

  1164       next(f);

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

  1166     }

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

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

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

  1172     public:

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

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

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

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

  1177     };

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

  1180     public:

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

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

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

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

  1185     };

  1186   };

  1188   template<typename GraphWrapper>

  1189   class FilterGraphWrapper {

  1190   };

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

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

  1195     //Graph* graph;

  1197   public:

  1198     //typedef Graph BaseGraph;

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

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

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

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

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

  1206     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

  1211   public:

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

  1213 			   const CapacityMap& _capacity) :

  1214       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {

  1215     }

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

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

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

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

  1221       return e;

  1222     }

  1224     NodeIt& next(NodeIt& e) const {

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

  1226     }

  1228     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1232       return e;

  1233     }

  1235     NodeIt& first(NodeIt& n) const {

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

  1237     }

  1239     void erase(const Edge& e) {

  1240       OutEdgeIt f(e);

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

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

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

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

  1245     }

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

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

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

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

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

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

  1255     //  return gw.first(i, p); }

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

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

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

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

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

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

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

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

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

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

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

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

  1274     //{ return gw.setInvalid(i); }

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

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

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

  1280     //  return gw.aNode(e); }

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

  1282     //  return gw.bNode(e); }

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

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

  1286     //  return gw.addEdge(tail, head); }

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

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

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

  1293     public:

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

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

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

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

  1298     };

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

  1301     public:

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

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

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

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

  1306     };

  1308   public:

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

  1311   };

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

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

  1317 //   class ResGraphWrapper

  1318 //   {

  1319 //     Graph* graph;

  1321 //   public:

  1322 //     typedef Graph BaseGraph;

  1324 //     typedef typename Graph::Node Node;

  1325 //     typedef typename Graph::Edge Edge;

  1327 //     typedef typename Graph::NodeIt NodeIt;

  1329 //     class OutEdgeIt {

  1330 //     public:

  1331 //       //Graph::Node n;

  1332 //       bool out_or_in;

  1333 //       typename Graph::OutEdgeIt o;

  1334 //       typename Graph::InEdgeIt i;

  1335 //     };

  1336 //     class InEdgeIt {

  1337 //     public:

  1338 //       //Graph::Node n;

  1339 //       bool out_or_in;

  1340 //       typename Graph::OutEdgeIt o;

  1341 //       typename Graph::InEdgeIt i;

  1342 //     };

  1343 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1344 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

  1349 //     Node& first(Node& n) const { return gw.first(n); }

  1351 //     // Edge and SymEdge  is missing!!!!

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

  1354 //     //FIXME

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

  1356 //       {

  1357 // 	e.n=n;

  1358 // 	gw.first(e.o,n);

  1359 // 	while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1360 // 	  gw.goNext(e.o);

  1361 // 	if(!gw.valid(e.o)) {

  1362 // 	  gw.first(e.i,n);

  1363 // 	  while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1364 // 	    gw.goNext(e.i);

  1365 // 	}

  1366 // 	return e;

  1367 //       }

  1368 // /*

  1369 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1370 //   {

  1371 //   if(gw.valid(e.o)) {

  1372 //   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1373 //   gw.goNext(e.o);

  1374 //   if(gw.valid(e.o)) return e;

  1375 //   else gw.first(e.i,e.n);

  1376 //   }

  1377 //   else {

  1378 //   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1379 //   gw.goNext(e.i);

  1380 //   return e;

  1381 //   }

  1382 //   }

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

  1384 // */

  1385 //     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}

  1387 //     //FIXME

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

  1389 //       {

  1390 // 	e.n=n;

  1391 // 	gw.first(e.i,n);

  1392 // 	while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1393 // 	  gw.goNext(e.i);

  1394 // 	if(!gw.valid(e.i)) {

  1395 // 	  gw.first(e.o,n);

  1396 // 	  while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1397 // 	    gw.goNext(e.o);

  1398 // 	}

  1399 // 	return e;

  1400 //       }

  1401 // /*

  1402 //   InEdgeIt &goNext(InEdgeIt &e)

  1403 //   {

  1404 //   if(gw.valid(e.i)) {

  1405 //   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1406 //   gw.goNext(e.i);

  1407 //   if(gw.valid(e.i)) return e;

  1408 //   else gw.first(e.o,e.n);

  1409 //   }

  1410 //   else {

  1411 //   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1412 //   gw.goNext(e.o);

  1413 //   return e;

  1414 //   }

  1415 //   }

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

  1417 // */

  1418 //     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}

  1420 //     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }

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

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

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

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

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

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

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

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

  1433 //       return gw.aNode(e); }

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

  1435 //       return gw.bNode(e); }

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

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

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

  1441 //     //{ return gw.setInvalid(i); }

  1443 //     Node addNode() { return gw.addNode(); }

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

  1445 //       return gw.addEdge(tail, head); }

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

  1449 //     void clear() { gw.clear(); }

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

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

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

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

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

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

  1459 //   };

  1461 } //namespace hugo

  1463 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Mon, 29 Mar 2004 16:00:00 +0000
changeset 259	509ba9f136d2
parent 239	3f76d1aa9d37
child 263	f24f276e0b6b
permissions	-rw-r--r--