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

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

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

    18     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

    22     typedef typename Graph::Node Node;

    23     class NodeIt : public Graph::NodeIt {

    24     public:

    25       NodeIt() { }

    26       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

    27       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

    28       NodeIt(const TrivGraphWrapper<Graph>& _G) :

    29 	Graph::NodeIt(*(_G.graph)) { }

    30     };

    31     typedef typename Graph::Edge Edge;

    32     class OutEdgeIt : public Graph::OutEdgeIt {

    33     public:

    34       OutEdgeIt() { }

    35       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

    36       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

    37       OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :

    38 	Graph::OutEdgeIt(*(_G.graph), n) { }

    39     };

    40     class InEdgeIt : public Graph::InEdgeIt {

    41     public:

    42       InEdgeIt() { }

    43       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

    44       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

    45       InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :

    46 	Graph::InEdgeIt(*(_G.graph), n) { }

    47     };

    48     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    49     class EdgeIt : public Graph::EdgeIt {

    50     public:

    51       EdgeIt() { }

    52       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

    53       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

    54       EdgeIt(const TrivGraphWrapper<Graph>& _G) :

    55 	Graph::EdgeIt(*(_G.graph)) { }

    56     };

    58     NodeIt& first(NodeIt& i) const {

    59       i=NodeIt(*this);

    60       return i;

    61     }

    62     EdgeIt& first(EdgeIt& i) const {

    63       i=EdgeIt(*this);

    64       return i;

    65     }

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

    67 //       i=I(*this);

    68 //       return i;

    69 //     }

    70     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

    71       i=OutEdgeIt(*this, p);

    72       return i;

    73     }

    74     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

    75       i=InEdgeIt(*this, p);

    76       return i;

    77     }

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

    79 //       i=I(*this, p);

    80 //       return i;

    81 //     }

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

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

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

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

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

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

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

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

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

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

    97       return graph->valid(i); }

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

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

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

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

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

   106       return graph->aNode(e); }

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

   108       return graph->bNode(e); }

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

   111     Edge addEdge(const Node& tail, const Node& head) const {

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

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

   116     void clear() const { graph->clear(); }

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

   119     public:

   120       NodeMap(const TrivGraphWrapper<Graph>& _G) :

   121 	Graph::NodeMap<T>(*(_G.graph)) { }

   122       NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :

   123 	Graph::NodeMap<T>(*(_G.graph), a) { }

   124     };

   126     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   127     public:

   128       EdgeMap(const TrivGraphWrapper<Graph>& _G) :

   129 	Graph::EdgeMap<T>(*(_G.graph)) { }

   130       EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :

   131 	Graph::EdgeMap<T>(*(_G.graph), a) { }

   132     };

   134 //     template<typename Map, typename T> class NodeMapWrapper {

   135 //     protected:

   136 //       Map* map;

   137 //     public:

   138 //       NodeMapWrapper(Map& _map) : map(&_map) { }

   139 //       void set(Node n, T a) { map->set(n, a); }

   140 //       T get(Node n) const { return map->get(n); }

   141 //     };

   143 //     template<typename Map, typename T> class EdgeMapWrapper {

   144 //     protected:

   145 //       Map* map;

   146 //     public:

   147 //       EdgeMapWrapper(Map& _map) : map(&_map) { }

   148 //       void set(Edge n, T a) { map->set(n, a); }

   149 //       T get(Edge n) const { return map->get(n); }

   150 //     };

   151   };

   154   template<typename Graph>

   155   class GraphWrapper {

   156   protected:

   157     Graph* graph;

   159   public:

   160     typedef Graph ParentGraph;

   162 //     GraphWrapper() : graph(0) { }

   163     GraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

   167     typedef typename Graph::Node Node;

   168     class NodeIt : public Graph::NodeIt {

   169     public:

   170       NodeIt() { }

   171       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

   172       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

   173       NodeIt(const GraphWrapper<Graph>& _G) :

   174 	Graph::NodeIt(*(_G.graph)) { }

   175     };

   176     typedef typename Graph::Edge Edge;

   177     class OutEdgeIt : public Graph::OutEdgeIt {

   178     public:

   179       OutEdgeIt() { }

   180       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

   181       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

   182       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :

   183 	Graph::OutEdgeIt(*(_G.graph), n) { }

   184     };

   185     class InEdgeIt : public Graph::InEdgeIt {

   186     public:

   187       InEdgeIt() { }

   188       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

   189       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

   190       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :

   191 	Graph::InEdgeIt(*(_G.graph), n) { }

   192     };

   193     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   194     class EdgeIt : public Graph::EdgeIt {

   195     public:

   196       EdgeIt() { }

   197       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

   198       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

   199       EdgeIt(const GraphWrapper<Graph>& _G) :

   200 	Graph::EdgeIt(*(_G.graph)) { }

   201     };

   203     NodeIt& first(NodeIt& i) const {

   204       i=NodeIt(*this);

   205       return i;

   206     }

   207     EdgeIt& first(EdgeIt& i) const {

   208       i=EdgeIt(*this);

   209       return i;

   210     }

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

   212 //       i=I(*this);

   213 //       return i;

   214 //     }

   215     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   216       i=OutEdgeIt(*this, p);

   217       return i;

   218     }

   219     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   220       i=InEdgeIt(*this, p);

   221       return i;

   222     }

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

   224 //       i=I(*this, p);

   225 //       return i;

   226 //     }

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

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

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

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

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

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

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

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

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

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

   242       return graph->valid(i); }

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

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

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

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

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

   251       return graph->aNode(e); }

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

   253       return graph->bNode(e); }

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

   256     Edge addEdge(const Node& tail, const Node& head) const {

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

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

   261     void clear() const { graph->clear(); }

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

   264     public:

   265       NodeMap(const GraphWrapper<Graph>& _G) :

   266 	Graph::NodeMap<T>(*(_G.graph)) { }

   267       NodeMap(const GraphWrapper<Graph>& _G, T a) :

   268 	Graph::NodeMap<T>(*(_G.graph), a) { }

   269     };

   271     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   272     public:

   273       EdgeMap(const GraphWrapper<Graph>& _G) :

   274 	Graph::EdgeMap<T>(*(_G.graph)) { }

   275       EdgeMap(const GraphWrapper<Graph>& _G, T a) :

   276 	Graph::EdgeMap<T>(*(_G.graph), a) { }

   277     };

   278   };

   281 //   template<typename Graph>

   282 //   class RevGraphWrapper

   283 //   {

   284 //   protected:

   285 //     Graph* graph;

   287 //   public:

   288 //     typedef Graph ParentGraph;

   290 //     typedef typename Graph::Node Node;

   291 //     typedef typename Graph::NodeIt NodeIt;

   293 //     typedef typename Graph::Edge Edge;

   294 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   295 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   296 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   297 //     typedef typename Graph::EdgeIt EdgeIt;

   299 //     //RevGraphWrapper() : graph(0) { }

   300 //     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   345 //     public:

   346 //       NodeMap(const RevGraphWrapper<Graph>& _G) :

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

   348 //       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :

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

   350 //     };

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

   353 //     public:

   354 //       EdgeMap(const RevGraphWrapper<Graph>& _G) :

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

   356 //       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :

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

   358 //     };

   359 //   };

   362   template<typename Graph>

   363   class RevGraphWrapper : public GraphWrapper<Graph> {

   364   public:

   365     typedef typename GraphWrapper<Graph>::Node Node;

   366     typedef typename GraphWrapper<Graph>::Edge Edge;

   367     //FIXME

   368     //If Graph::OutEdgeIt is not defined

   369     //and we do not want to use RevGraphWrapper::InEdgeIt,

   370     //this won't work, because of typedef

   371     //OR

   372     //graphs have to define their non-existing iterators to void

   373     //Unfortunately all the typedefs are instantiated in templates,

   374     //unlike other stuff

   375     typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;

   376     typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

   378 //     RevGraphWrapper() : GraphWrapper<Graph>() { }

   379     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   381     Node head(const Edge& e) const

   382       { return GraphWrapper<Graph>::tail(e); }

   383     Node tail(const Edge& e) const

   384       { return GraphWrapper<Graph>::head(e); }

   385   };

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

   388   template<typename Graph, typename EdgeFilterMap>

   389   class SubGraphWrapper : public GraphWrapper<Graph> {

   390   protected:

   391     EdgeFilterMap* filter_map;

   392   public:

   393     typedef typename GraphWrapper<Graph>::Node Node;

   394     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   395     typedef typename GraphWrapper<Graph>::Edge Edge;

   396     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

   397     typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;

   398     typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;

   400 //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }

   401     SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :

   402       GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }

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

   405       graph->first(i);

   406       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   407       while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }

   408       return i;

   409     }

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

   411       graph->first(i, p);

   412 //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   413       while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }

   414       return i;

   415     }

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

   418     //  return gw.getNext(i);

   419     //}

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

   421       graph->next(i);

   422 //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }

   423       while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }

   424       return i;

   425     }

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

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

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

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

   432   };

   434 //   template<typename GraphWrapper>

   435 //   class UndirGraphWrapper {

   436 //   protected:

   437 //     //Graph* graph;

   438 //     GraphWrapper gw;

   440 //   public:

   441 //     typedef GraphWrapper ParentGraph;

   443 //     typedef typename GraphWrapper::Node Node;

   444 //     typedef typename GraphWrapper::NodeIt NodeIt;

   446 //     //typedef typename Graph::Edge Edge;

   447 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   448 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   449 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   450 //     //typedef typename Graph::EdgeIt EdgeIt;

   452 //     //private:

   453 //     typedef typename GraphWrapper::Edge GraphEdge;

   454 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   455 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   456 //     //public:

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

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

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

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

   464 //     class Edge {

   465 //       friend class UndirGraphWrapper<GraphWrapper>;

   466 //       bool out_or_in; //true iff out

   467 //       GraphOutEdgeIt out;

   468 //       GraphInEdgeIt in;

   469 //     public:

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

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

   472 //       operator GraphEdge() const {

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

   474 //       }

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

   476 // 	if (v.out_or_in)

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

   478 // 	else

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

   480 //       }

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

   482 // 	if (v.out_or_in)

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

   484 // 	else

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

   486 //       }

   487 //     };

   489 //     class OutEdgeIt : public Edge {

   490 //       friend class UndirGraphWrapper<GraphWrapper>;

   491 //     public:

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

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

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

   495 // 	: Edge() {

   496 // 	out_or_in=true;

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

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

   499 // 	  out_or_in=false;

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

   501 // 	}

   502 //       }

   503 //     };

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

   506 //       e.out_or_in=true;

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

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

   509 // 	e.out_or_in=false;

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

   511 //       }

   512 //       return e;

   513 //     }

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

   516 //       if (e.out_or_in) {

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

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

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

   520 // 	  e.out_or_in=false;

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

   522 // 	}

   523 //       } else {

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

   525 //       }

   526 //       return e;

   527 //     }

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

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

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

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

   534 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   577 //     public:

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

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

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

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

   582 //     };

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

   585 //     public:

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

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

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

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

   590 //     };

   591 //   };

   594   template<typename Graph>

   595   class UndirGraphWrapper : public GraphWrapper<Graph> {

   596   protected:

   597     typedef typename Graph::Edge GraphEdge;

   598     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   599     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   600   public:

   601     typedef typename GraphWrapper<Graph>::Node Node;

   602     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   604 //     UndirGraphWrapper() : GraphWrapper<Graph>() { }

   605     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   607     class Edge {

   608       friend class UndirGraphWrapper<Graph>;

   609     protected:

   610       bool out_or_in; //true iff out

   611       GraphOutEdgeIt out;

   612       GraphInEdgeIt in;

   613     public:

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

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

   616       operator GraphEdge() const {

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

   618       }

   619 //FIXME

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

   621 //is it good?

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

   623 	if (v.out_or_in)

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

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

   626 	else

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

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

   629       }

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

   631 	if (v.out_or_in)

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

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

   634 	else

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

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

   637       }

   638     };

   640     class OutEdgeIt : public Edge {

   641       friend class UndirGraphWrapper<Graph>;

   642     public:

   643       OutEdgeIt() : Edge() { }

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

   645       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)

   646 	: Edge() {

   647 	out_or_in=true; _G.graph->first(out, n);

   648 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n);	}

   649       }

   650     };

   652     typedef OutEdgeIt InEdgeIt;

   654     class EdgeIt : public Edge {

   655       friend class UndirGraphWrapper<Graph>;

   656     protected:

   657       NodeIt v;

   658     public:

   659       EdgeIt() : Edge() { }

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

   661       EdgeIt(const UndirGraphWrapper<Graph>& _G)

   662 	: Edge() {

   663 	out_or_in=true;

   664 	//Node v;

   665 	_G.first(v);

   666 	if (_G.valid(v)) _G.graph->first(out); else out=INVALID;

   667 	while (_G.valid(v) && !_G.graph->valid(out)) {

   668 	  _G.graph->next(v);

   669 	  if (_G.valid(v)) _G.graph->first(out);

   670 	}

   671       }

   672     };

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

   675       e.out_or_in=true; graph->first(e.out, n);

   676       if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }

   677       return e;

   678     }

   680     EdgeIt& first(EdgeIt& e) const {

   681       e.out_or_in=true;

   682       //NodeIt v;

   683       first(e.v);

   684       if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;

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

   686 	graph->next(e.v);

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

   688       }

   689       return e;

   690     }

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

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

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

   696     OutEdgeIt& next(OutEdgeIt& e) const {

   697       if (e.out_or_in) {

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

   699 	graph->next(e.out);

   700 	if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }

   701       } else {

   702 	graph->next(e.in);

   703       }

   704       return e;

   705     }

   707     EdgeIt& next(EdgeIt& e) const {

   708       //NodeIt v=tail(e);

   709       graph->next(e.out);

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

   711 	next(e.v);

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

   713       }

   714       return e;

   715     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   740     Node aNode(const OutEdgeIt& e) const {

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

   742     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   756 //     public:

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

   758 // 	Graph::NodeMap<T>(_G.gw) { }

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

   760 // 	Graph::NodeMap<T>(_G.gw, a) { }

   761 //     };

   763 //     template<typename T> class EdgeMap :

   764 //       public GraphWrapperSkeleton<Graph>::EdgeMap<T> {

   765 //     public:

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

   767 // 	GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }

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

   769 // 	Graph::EdgeMap<T>(_G.gw, a) { }

   770 //     };

   771    };

   777 //   template<typename Graph>

   778 //   class SymGraphWrapper

   779 //   {

   780 //     Graph* graph;

   782 //   public:

   783 //     typedef Graph ParentGraph;

   785 //     typedef typename Graph::Node Node;

   786 //     typedef typename Graph::Edge Edge;

   788 //     typedef typename Graph::NodeIt NodeIt;

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

   791 //     //iranyitatlant, ami van

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

   793 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   795 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   796 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   843 //   };

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

   847   class ResGraphWrapper : public GraphWrapper<Graph>{

   848   public:

   849     typedef typename GraphWrapper<Graph>::Node Node;

   850     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   851   protected:

   852     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   853     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   854     typedef typename Graph::Edge GraphEdge;

   855     FlowMap* flow;

   856     const CapacityMap* capacity;

   857   public:

   859     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

   860 		    const CapacityMap& _capacity) :

   861       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }

   863     class Edge;

   864     class OutEdgeIt;

   865     friend class Edge;

   866     friend class OutEdgeIt;

   868     class Edge {

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

   870     protected:

   871       bool out_or_in; //true, iff out

   872       GraphOutEdgeIt out;

   873       GraphInEdgeIt in;

   874     public:

   875       Edge() : out_or_in(true) { }

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

   877 //       bool valid() const {

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

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

   880 	if (v.out_or_in)

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

   882 	else

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

   884       }

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

   886 	if (v.out_or_in)

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

   888 	else

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

   890       }

   891       operator GraphEdge() const {

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

   893       }

   894     };

   897     class OutEdgeIt : public Edge {

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

   899     public:

   900       OutEdgeIt() { }

   901       //FIXME

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

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

   904     protected:

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

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

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

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

   909 	  out_or_in=0;

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

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

   912 	}

   913       }

   914 //     public:

   915 //       OutEdgeIt& operator++() {

   916 // 	if (out_or_in) {

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

   918 // 	  ++out;

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

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

   921 // 	    out_or_in=0;

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

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

   924 // 	  }

   925 // 	} else {

   926 // 	  ++in;

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

   928 // 	}

   929 // 	return *this;

   930 //       }

   931     };

   933     //FIXME This is just for having InEdgeIt

   934     typedef void InEdgeIt;

   936     class EdgeIt : public Edge {

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

   938       NodeIt v;

   939     public:

   940       EdgeIt() { }

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

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

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

   944 	resG.graph->first(v);

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

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

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

   948 	  resG.graph->next(v);

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

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

   951 	}

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

   953 	  out_or_in=0;

   954 	  resG.graph->first(v);

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

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

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

   958 	    resG.graph->next(v);

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

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

   961 	  }

   962 	}

   963       }

   964 //       EdgeIt& operator++() {

   965 // 	if (out_or_in) {

   966 // 	  ++out;

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

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

   969 // 	    ++v;

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

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

   972 // 	  }

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

   974 // 	    out_or_in=0;

   975 // 	    G->first(v);

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

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

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

   979 // 	      ++v;

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

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

   982 // 	    }

   983 // 	  }

   984 // 	} else {

   985 // 	  ++in;

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

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

   988 // 	    ++v;

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

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

   991 // 	  }

   992 // 	}

   993 // 	return *this;

   994 //       }

   995     };

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

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

   999       e=OutEdgeIt(*this, v);

  1000       return e;

  1001     }

  1002     EdgeIt& first(EdgeIt& e) const {

  1003       e=EdgeIt(*this);

  1004       return e;

  1005     }

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

  1009     OutEdgeIt& next(OutEdgeIt& e) const {

  1010       if (e.out_or_in) {

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

  1012 	graph->next(e.out);

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

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

  1015 	  e.out_or_in=0;

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

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

  1018 	}

  1019       } else {

  1020 	graph->next(e.in);

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

  1022       }

  1023       return e;

  1024     }

  1026     EdgeIt& next(EdgeIt& e) const {

  1027       if (e.out_or_in) {

  1028 	graph->next(e.out);

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

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

  1031 	    graph->next(e.v);

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

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

  1034 	  }

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

  1036 	    e.out_or_in=0;

  1037 	    graph->first(e.v);

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

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

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

  1041 	      graph->next(e.v);

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

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

  1044 	    }

  1045 	  }

  1046 	} else {

  1047 	  graph->next(e.in);

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

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

  1050 	    graph->next(e.v);

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

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

  1053 	  }

  1054 	}

  1055 	return e;

  1056       }

  1059     template< typename It >

  1060     It first() const {

  1061       It e;

  1062       first(e);

  1063       return e;

  1064     }

  1066     template< typename It >

  1067     It first(Node v) const {

  1068       It e;

  1069       first(e, v);

  1070       return e;

  1071     }

  1073     Node tail(Edge e) const {

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

  1075     Node head(Edge e) const {

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

  1078     Node aNode(OutEdgeIt e) const {

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

  1080     Node bNode(OutEdgeIt e) const {

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

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

  1084     //FIXME

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

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

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

  1091     bool valid(Edge e) const {

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

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

  1095       if (e.out_or_in)

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

  1097 	flow->set(e.out, (*flow)[e.out]+a);

  1098       else

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

  1100 	flow->set(e.in, (*flow)[e.in]-a);

  1101     }

  1103     Number resCap(const Edge& e) const {

  1104       if (e.out_or_in)

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

  1106 	return ((*capacity)[e.out]-(*flow)[e.out]);

  1107       else

  1108 //	return (flow->get(e.in));

  1109 	return ((*flow)[e.in]);

  1110     }

  1112     Number resCap(GraphOutEdgeIt out) const {

  1113 //      return (capacity->get(out)-flow->get(out));

  1114       return ((*capacity)[out]-(*flow)[out]);

  1115     }

  1117     Number resCap(GraphInEdgeIt in) const {

  1118 //      return (flow->get(in));

  1119       return ((*flow)[in]);

  1120     }

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

  1123 //     public:

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

  1125 // 	: Graph::NodeMap<T>(_G.gw) { }

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

  1127 // 	      T a) : Graph::NodeMap<T>(_G.gw, a) { }

  1128 //     };

  1130 //     template <typename T>

  1131 //     class NodeMap {

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

  1133 //     public:

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

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

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

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

  1138 //     };

  1140     template <typename T>

  1141     class EdgeMap {

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

  1143     public:

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

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

  1146       void set(Edge e, T a) {

  1147 	if (e.out_or_in)

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

  1149 	else

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

  1151       }

  1152       T operator[](Edge e) const {

  1153 	if (e.out_or_in)

  1154 	  return forward_map[e.out];

  1155 	else

  1156 	  return backward_map[e.in];

  1157       }

  1158 //       T get(Edge e) const {

  1159 // 	if (e.out_or_in)

  1160 // 	  return forward_map.get(e.out);

  1161 // 	else

  1162 // 	  return backward_map.get(e.in);

  1163 //       }

  1164     };

  1165   };

  1167   //ErasingFirstGraphWrapper for blocking flows

  1168   template<typename Graph, typename FirstOutEdgesMap>

  1169   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1170   protected:

  1171     FirstOutEdgesMap* first_out_edges;

  1172   public:

  1173     typedef typename GraphWrapper<Graph>::Node Node;

  1174     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

  1175     typedef typename GraphWrapper<Graph>::Edge Edge;

  1176     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

  1177     typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;

  1178     typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;

  1180     ErasingFirstGraphWrapper(Graph& _graph,

  1181 			     FirstOutEdgesMap& _first_out_edges) :

  1182       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }

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

  1185       graph->first(i);

  1186       return i;

  1187     }

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

  1189 //      e=first_out_edges->get(n);

  1190       e=(*first_out_edges)[n];

  1191       return e;

  1192     }

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

  1194       graph->first(i, p);

  1195       return i;

  1196     }

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

  1199     //  return gw.getNext(i);

  1200     //}

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

  1202       graph->next(i);

  1203       return i;

  1204     }

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

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

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

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

  1212     void erase(const OutEdgeIt& e) const {

  1213       OutEdgeIt f=e;

  1214       this->next(f);

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

  1216     }

  1217   };

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

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

  1221 //   class ResGraphWrapper

  1222 //   {

  1223 //     Graph* graph;

  1225 //   public:

  1226 //     typedef Graph ParentGraph;

  1228 //     typedef typename Graph::Node Node;

  1229 //     typedef typename Graph::Edge Edge;

  1231 //     typedef typename Graph::NodeIt NodeIt;

  1233 //     class OutEdgeIt {

  1234 //     public:

  1235 //       //Graph::Node n;

  1236 //       bool out_or_in;

  1237 //       typename Graph::OutEdgeIt o;

  1238 //       typename Graph::InEdgeIt i;

  1239 //     };

  1240 //     class InEdgeIt {

  1241 //     public:

  1242 //       //Graph::Node n;

  1243 //       bool out_or_in;

  1244 //       typename Graph::OutEdgeIt o;

  1245 //       typename Graph::InEdgeIt i;

  1246 //     };

  1247 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1248 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1255 //     // Edge and SymEdge  is missing!!!!

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

  1258 //     //FIXME

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

  1260 //       {

  1261 // 	e.n=n;

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

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

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

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

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

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

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

  1269 // 	}

  1270 // 	return e;

  1271 //       }

  1272 // /*

  1273 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1274 //   {

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

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

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

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

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

  1280 //   }

  1281 //   else {

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

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

  1284 //   return e;

  1285 //   }

  1286 //   }

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

  1288 // */

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

  1291 //     //FIXME

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

  1293 //       {

  1294 // 	e.n=n;

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

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

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

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

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

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

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

  1302 // 	}

  1303 // 	return e;

  1304 //       }

  1305 // /*

  1306 //   InEdgeIt &goNext(InEdgeIt &e)

  1307 //   {

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

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

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

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

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

  1313 //   }

  1314 //   else {

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

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

  1317 //   return e;

  1318 //   }

  1319 //   }

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

  1321 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1363 //   };

  1365 } //namespace hugo

  1367 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Mon, 05 Apr 2004 16:52:46 +0000
changeset 303	1b377a730d02
parent 279	be43902fadb7
child 305	6720705c9095
permissions	-rw-r--r--