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

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

   345   //Subgraph on the same node-set and partial edge-set

   346   template<typename GraphWrapper, typename EdgeFilterMap>

   347   class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   348   protected:

   349     EdgeFilterMap* filter_map;

   350   public:

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

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

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

   354     typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;

   355     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;

   356     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

   358     SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :

   359       GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }

   361     template<typename I> I& first(I& i) const {

   362       gw.first(i);

   363       while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

   364       return i;

   365     }

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

   367       gw.first(i, p);

   368       while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

   369       return i;

   370     }

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

   373     //  return gw.getNext(i);

   374     //}

   375     template<typename I> I& next(I &i) const {

   376       gw.next(i);

   377       while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

   378       return i;

   379     }

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

   382       It e; this->first(e); return e; }

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

   385       It e; this->first(e, v); return e; }

   386   };

   388 //   template<typename GraphWrapper>

   389 //   class UndirGraphWrapper {

   390 //   protected:

   391 //     //Graph* graph;

   392 //     GraphWrapper gw;

   394 //   public:

   395 //     typedef GraphWrapper BaseGraph;

   397 //     typedef typename GraphWrapper::Node Node;

   398 //     typedef typename GraphWrapper::NodeIt NodeIt;

   400 //     //typedef typename Graph::Edge Edge;

   401 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   402 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   403 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   404 //     //typedef typename Graph::EdgeIt EdgeIt;

   406 //     //private:

   407 //     typedef typename GraphWrapper::Edge GraphEdge;

   408 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   409 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   410 //     //public:

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

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

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

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

   418 //     class Edge {

   419 //       friend class UndirGraphWrapper<GraphWrapper>;

   420 //       bool out_or_in; //true iff out

   421 //       GraphOutEdgeIt out;

   422 //       GraphInEdgeIt in;

   423 //     public:

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

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

   426 //       operator GraphEdge() const {

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

   428 //       }

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

   430 // 	if (v.out_or_in)

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

   432 // 	else

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

   434 //       }

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

   436 // 	if (v.out_or_in)

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

   438 // 	else

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

   440 //       }

   441 //     };

   443 //     class OutEdgeIt : public Edge {

   444 //       friend class UndirGraphWrapper<GraphWrapper>;

   445 //     public:

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

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

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

   449 // 	: Edge() {

   450 // 	out_or_in=true;

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

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

   453 // 	  out_or_in=false;

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

   455 // 	}

   456 //       }

   457 //     };

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

   460 //       e.out_or_in=true;

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

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

   463 // 	e.out_or_in=false;

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

   465 //       }

   466 //       return e;

   467 //     }

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

   470 //       if (e.out_or_in) {

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

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

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

   474 // 	  e.out_or_in=false;

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

   476 // 	}

   477 //       } else {

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

   479 //       }

   480 //       return e;

   481 //     }

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

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

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

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

   488 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   531 //     public:

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

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

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

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

   536 //     };

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

   539 //     public:

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

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

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

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

   544 //     };

   545 //   };

   548   template<typename GraphWrapper>

   549   class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   550   protected:

   551 //    GraphWrapper gw;

   553   public:

   554     //typedef GraphWrapper BaseGraph;

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

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

   559     //private:

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

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

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

   563     //public:

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

   566     UndirGraphWrapper(GraphWrapper _gw) :

   567       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

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

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

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

   574     class Edge {

   575       friend class UndirGraphWrapper<GraphWrapper>;

   576       bool out_or_in; //true iff out

   577       GraphOutEdgeIt out;

   578       GraphInEdgeIt in;

   579     public:

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

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

   582       operator GraphEdge() const {

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

   584       }

   585 //FIXME

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

   587 //is it good?

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

   589 	if (v.out_or_in)

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

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

   592 	else

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

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

   595       }

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

   597 	if (v.out_or_in)

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

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

   600 	else

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

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

   603       }

   604     };

   606     class OutEdgeIt : public Edge {

   607       friend class UndirGraphWrapper<GraphWrapper>;

   608     public:

   609       OutEdgeIt() : Edge() { }

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

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

   612 	: Edge() {

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

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

   615       }

   616     };

   618     typedef OutEdgeIt InEdgeIt;

   620     class EdgeIt : public Edge {

   621       friend class UndirGraphWrapper<GraphWrapper>;

   622     protected:

   623       NodeIt v;

   624     public:

   625       EdgeIt() : Edge() { }

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

   627       EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)

   628 	: Edge() {

   629 	out_or_in=true;

   630 	//Node v;

   631 	_G.first(v);

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

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

   634 	  _G.gw.next(v);

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

   636 	}

   637       }

   638     };

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

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

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

   643       return e;

   644     }

   646     EdgeIt& first(EdgeIt& e) const {

   647       e.out_or_in=true;

   648       //NodeIt v;

   649       first(e.v);

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

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

   652 	gw.next(e.v);

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

   654       }

   655       return e;

   656     }

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

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

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

   662     OutEdgeIt& next(OutEdgeIt& e) const {

   663       if (e.out_or_in) {

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

   665 	gw.next(e.out);

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

   667       } else {

   668 	gw.next(e.in);

   669       }

   670       return e;

   671     }

   673     EdgeIt& next(EdgeIt& e) const {

   674       //NodeIt v=tail(e);

   675       gw.next(e.out);

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

   677 	next(e.v);

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

   679       }

   680       return e;

   681     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   706     Node aNode(const OutEdgeIt& e) const {

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

   708     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   722 //     public:

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

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

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

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

   727 //     };

   729 //     template<typename T> class EdgeMap :

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

   731 //     public:

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

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

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

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

   736 //     };

   737    };

   743 //   template<typename Graph>

   744 //   class SymGraphWrapper

   745 //   {

   746 //     Graph* graph;

   748 //   public:

   749 //     typedef Graph BaseGraph;

   751 //     typedef typename Graph::Node Node;

   752 //     typedef typename Graph::Edge Edge;

   754 //     typedef typename Graph::NodeIt NodeIt;

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

   757 //     //iranyitatlant, ami van

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

   759 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   761 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   762 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   809 //   };

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

   813   class ResGraphWrapper {

   814   public:

   815     //typedef Graph BaseGraph;

   816     typedef typename Graph::Node Node;

   817     typedef typename Graph::NodeIt NodeIt;

   818   private:

   819     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   820     typedef typename Graph::InEdgeIt OldInEdgeIt;

   821   protected:

   822     //const Graph* graph;

   823     typedef TrivGraphWrapper<const Graph> GraphWrapper;

   824     GraphWrapper gw;

   825     FlowMap* flow;

   826     const CapacityMap* capacity;

   827   public:

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

   830 	     const CapacityMap& _capacity) :

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

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

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

   836     class Edge;

   837     class OutEdgeIt;

   838     friend class Edge;

   839     friend class OutEdgeIt;

   841     class Edge {

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

   843     protected:

   844       bool out_or_in; //true, iff out

   845       OldOutEdgeIt out;

   846       OldInEdgeIt in;

   847     public:

   848       Edge() : out_or_in(true) { }

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

   850 //       bool valid() const {

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

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

   853 	if (v.out_or_in)

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

   855 	else

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

   857       }

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

   859 	if (v.out_or_in)

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

   861 	else

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

   863       }

   864     };

   867     class OutEdgeIt : public Edge {

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

   869     public:

   870       OutEdgeIt() { }

   871       //FIXME

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

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

   874     private:

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

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

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

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

   879 	  out_or_in=0;

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

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

   882 	}

   883       }

   884 //     public:

   885 //       OutEdgeIt& operator++() {

   886 // 	if (out_or_in) {

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

   888 // 	  ++out;

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

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

   891 // 	    out_or_in=0;

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

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

   894 // 	  }

   895 // 	} else {

   896 // 	  ++in;

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

   898 // 	}

   899 // 	return *this;

   900 //       }

   901     };

   903     //FIXME This is just for having InEdgeIt

   904     typedef void InEdgeIt;

   906     class EdgeIt : public Edge {

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

   908       typename Graph::NodeIt v;

   909     public:

   910       EdgeIt() { }

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

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

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

   914 	resG.gw.first(v);

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

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

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

   918 	  resG.gw.next(v);

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

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

   921 	}

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

   923 	  out_or_in=0;

   924 	  resG.gw.first(v);

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

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

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

   928 	    resG.gw.next(v);

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

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

   931 	  }

   932 	}

   933       }

   934 //       EdgeIt& operator++() {

   935 // 	if (out_or_in) {

   936 // 	  ++out;

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

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

   939 // 	    ++v;

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

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

   942 // 	  }

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

   944 // 	    out_or_in=0;

   945 // 	    G->first(v);

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

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

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

   949 // 	      ++v;

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

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

   952 // 	    }

   953 // 	  }

   954 // 	} else {

   955 // 	  ++in;

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

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

   958 // 	    ++v;

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

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

   961 // 	  }

   962 // 	}

   963 // 	return *this;

   964 //       }

   965     };

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

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

   969       e=OutEdgeIt(*this, v);

   970       return e;

   971     }

   972     EdgeIt& first(EdgeIt& e) const {

   973       e=EdgeIt(*this);

   974       return e;

   975     }

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

   979     OutEdgeIt& next(OutEdgeIt& e) const {

   980       if (e.out_or_in) {

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

   982 	gw.next(e.out);

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

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

   985 	  e.out_or_in=0;

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

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

   988 	}

   989       } else {

   990 	gw.next(e.in);

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

   992       }

   993       return e;

   994     }

   996     EdgeIt& next(EdgeIt& e) const {

   997       if (e.out_or_in) {

   998 	gw.next(e.out);

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

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

  1001 	    gw.next(e.v);

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

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

  1004 	  }

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

  1006 	    e.out_or_in=0;

  1007 	    gw.first(e.v);

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

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

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

  1011 	      gw.next(e.v);

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

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

  1014 	    }

  1015 	  }

  1016 	} else {

  1017 	  gw.next(e.in);

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

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

  1020 	    gw.next(e.v);

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

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

  1023 	  }

  1024 	}

  1025 	return e;

  1026       }

  1029     template< typename It >

  1030     It first() const {

  1031       It e;

  1032       first(e);

  1033       return e;

  1034     }

  1036     template< typename It >

  1037     It first(Node v) const {

  1038       It e;

  1039       first(e, v);

  1040       return e;

  1041     }

  1043     Node tail(Edge e) const {

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

  1045     Node head(Edge e) const {

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

  1048     Node aNode(OutEdgeIt e) const {

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

  1050     Node bNode(OutEdgeIt e) const {

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

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

  1054     //FIXME

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

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

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

  1061     bool valid(Edge e) const {

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

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

  1065       if (e.out_or_in)

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

  1067       else

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

  1069     }

  1071     Number free(const Edge& e) const {

  1072       if (e.out_or_in)

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

  1074       else

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

  1076     }

  1078     Number free(OldOutEdgeIt out) const {

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

  1080     }

  1082     Number free(OldInEdgeIt in) const {

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

  1084     }

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

  1087     public:

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

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

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

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

  1092     };

  1094 //     template <typename T>

  1095 //     class NodeMap {

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

  1097 //     public:

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

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

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

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

  1102 //     };

  1104     template <typename T>

  1105     class EdgeMap {

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

  1107     public:

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

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

  1110       void set(Edge e, T a) {

  1111 	if (e.out_or_in)

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

  1113 	else

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

  1115       }

  1116       T get(Edge e) {

  1117 	if (e.out_or_in)

  1118 	  return forward_map.get(e.out);

  1119 	else

  1120 	  return backward_map.get(e.in);

  1121       }

  1122     };

  1123   };

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

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

  1127   protected:

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

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

  1130   public:

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

  1132 			   const CapacityMap& _capacity) :

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

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

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

  1136 	OutEdgeIt e;

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

  1138 	first_out_edges.set(n, e);

  1139       }

  1140     }

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

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

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

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

  1148     //typedef Graph BaseGraph;

  1150     //typedef typename Graph::Node Node;

  1151     //typedef typename Graph::NodeIt NodeIt;

  1153     //typedef typename Graph::Edge Edge;

  1154     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1155     //typedef typename Graph::InEdgeIt InEdgeIt;

  1156     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1157     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

  1165     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

  1168     NodeIt& first(NodeIt& n) const {

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

  1170     }

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

  1173       e=first_out_edges.get(n);

  1174       return e;

  1175     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1211     //}

  1212     void erase(const Edge& e) {

  1213       OutEdgeIt f(e);

  1214       next(f);

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

  1216     }

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

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

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

  1222     public:

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

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

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

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

  1227     };

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

  1230     public:

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

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

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

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

  1235     };

  1236   };

  1238   template<typename GraphWrapper>

  1239   class FilterGraphWrapper {

  1240   };

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

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

  1245     //Graph* graph;

  1247   public:

  1248     //typedef Graph BaseGraph;

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

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

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

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

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

  1256     //typedef typename Graph::SymEdgeIt SymEdgeIt;

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

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

  1261   public:

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

  1263 			   const CapacityMap& _capacity) :

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

  1265     }

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

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

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

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

  1271       return e;

  1272     }

  1274     NodeIt& next(NodeIt& e) const {

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

  1276     }

  1278     OutEdgeIt& next(OutEdgeIt& e) const {

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

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

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

  1282       return e;

  1283     }

  1285     NodeIt& first(NodeIt& n) const {

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

  1287     }

  1289     void erase(const Edge& e) {

  1290       OutEdgeIt f(e);

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

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

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

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

  1295     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1343     public:

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

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

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

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

  1348     };

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

  1351     public:

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

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

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

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

  1356     };

  1358   public:

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

  1361   };

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

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

  1367 //   class ResGraphWrapper

  1368 //   {

  1369 //     Graph* graph;

  1371 //   public:

  1372 //     typedef Graph BaseGraph;

  1374 //     typedef typename Graph::Node Node;

  1375 //     typedef typename Graph::Edge Edge;

  1377 //     typedef typename Graph::NodeIt NodeIt;

  1379 //     class OutEdgeIt {

  1380 //     public:

  1381 //       //Graph::Node n;

  1382 //       bool out_or_in;

  1383 //       typename Graph::OutEdgeIt o;

  1384 //       typename Graph::InEdgeIt i;

  1385 //     };

  1386 //     class InEdgeIt {

  1387 //     public:

  1388 //       //Graph::Node n;

  1389 //       bool out_or_in;

  1390 //       typename Graph::OutEdgeIt o;

  1391 //       typename Graph::InEdgeIt i;

  1392 //     };

  1393 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1394 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1401 //     // Edge and SymEdge  is missing!!!!

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

  1404 //     //FIXME

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

  1406 //       {

  1407 // 	e.n=n;

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

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

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

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

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

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

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

  1415 // 	}

  1416 // 	return e;

  1417 //       }

  1418 // /*

  1419 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1420 //   {

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

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

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

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

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

  1426 //   }

  1427 //   else {

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

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

  1430 //   return e;

  1431 //   }

  1432 //   }

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

  1434 // */

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

  1437 //     //FIXME

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

  1439 //       {

  1440 // 	e.n=n;

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

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

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

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

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

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

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

  1448 // 	}

  1449 // 	return e;

  1450 //       }

  1451 // /*

  1452 //   InEdgeIt &goNext(InEdgeIt &e)

  1453 //   {

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

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

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

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

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

  1459 //   }

  1460 //   else {

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

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

  1463 //   return e;

  1464 //   }

  1465 //   }

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

  1467 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1509 //   };

  1511 } //namespace hugo

  1513 #endif //HUGO_GRAPH_WRAPPER_H

author	alpar
	Tue, 30 Mar 2004 13:18:10 +0000
changeset 264	fe81c4b117f4
parent 259	509ba9f136d2
child 265	bf7aea53635a
permissions	-rw-r--r--