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

     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 { graph->next(i); return 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       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {

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

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

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

   908 	  out_or_in=0;

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

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

   911 	}

   912       }

   913 //     public:

   914 //       OutEdgeIt& operator++() {

   915 // 	if (out_or_in) {

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

   917 // 	  ++out;

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

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

   920 // 	    out_or_in=0;

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

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

   923 // 	  }

   924 // 	} else {

   925 // 	  ++in;

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

   927 // 	}

   928 // 	return *this;

   929 //       }

   930     };

   932     //FIXME This is just for having InEdgeIt

   933     typedef void InEdgeIt;

   935     class EdgeIt : public Edge {

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

   937       NodeIt v;

   938     public:

   939       EdgeIt() { }

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

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

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

   943 	resG.graph->first(v);

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

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

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

   947 	  resG.graph->next(v);

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

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

   950 	}

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

   952 	  out_or_in=0;

   953 	  resG.graph->first(v);

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

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

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

   957 	    resG.graph->next(v);

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

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

   960 	  }

   961 	}

   962       }

   963 //       EdgeIt& operator++() {

   964 // 	if (out_or_in) {

   965 // 	  ++out;

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

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

   968 // 	    ++v;

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

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

   971 // 	  }

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

   973 // 	    out_or_in=0;

   974 // 	    G->first(v);

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

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

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

   978 // 	      ++v;

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

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

   981 // 	    }

   982 // 	  }

   983 // 	} else {

   984 // 	  ++in;

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

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

   987 // 	    ++v;

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

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

   990 // 	  }

   991 // 	}

   992 // 	return *this;

   993 //       }

   994     };

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

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

   998       e=OutEdgeIt(*this, v);

   999       return e;

  1000     }

  1001     EdgeIt& first(EdgeIt& e) const {

  1002       e=EdgeIt(*this);

  1003       return e;

  1004     }

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

  1008     OutEdgeIt& next(OutEdgeIt& e) const {

  1009       if (e.out_or_in) {

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

  1011 	graph->next(e.out);

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

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

  1014 	  e.out_or_in=0;

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

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

  1017 	}

  1018       } else {

  1019 	graph->next(e.in);

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

  1021       }

  1022       return e;

  1023     }

  1025     EdgeIt& next(EdgeIt& e) const {

  1026       if (e.out_or_in) {

  1027 	graph->next(e.out);

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

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

  1030 	    graph->next(e.v);

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

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

  1033 	  }

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

  1035 	    e.out_or_in=0;

  1036 	    graph->first(e.v);

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

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

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

  1040 	      graph->next(e.v);

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

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

  1043 	    }

  1044 	  }

  1045 	} else {

  1046 	  graph->next(e.in);

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

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

  1049 	    graph->next(e.v);

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

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

  1052 	  }

  1053 	}

  1054 	return e;

  1055       }

  1058     template< typename It >

  1059     It first() const {

  1060       It e;

  1061       first(e);

  1062       return e;

  1063     }

  1065     template< typename It >

  1066     It first(Node v) const {

  1067       It e;

  1068       first(e, v);

  1069       return e;

  1070     }

  1072     Node tail(Edge e) const {

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

  1074     Node head(Edge e) const {

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

  1077     Node aNode(OutEdgeIt e) const {

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

  1079     Node bNode(OutEdgeIt e) const {

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

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

  1083     //FIXME

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

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

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

  1090     bool valid(Edge e) const {

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

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

  1094       if (e.out_or_in)

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

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

  1097       else

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

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

  1100     }

  1102     Number resCap(const Edge& e) const {

  1103       if (e.out_or_in)

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

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

  1106       else

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

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

  1109     }

  1111     Number resCap(GraphOutEdgeIt out) const {

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

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

  1114     }

  1116     Number resCap(GraphInEdgeIt in) const {

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

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

  1119     }

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

  1122 //     public:

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

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

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

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

  1127 //     };

  1129 //     template <typename T>

  1130 //     class NodeMap {

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

  1132 //     public:

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

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

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

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

  1137 //     };

  1139     template <typename T>

  1140     class EdgeMap {

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

  1142     public:

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

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

  1145       void set(Edge e, T a) {

  1146 	if (e.out_or_in)

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

  1148 	else

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

  1150       }

  1151       T operator[](Edge e) const {

  1152 	if (e.out_or_in)

  1153 	  return forward_map[e.out];

  1154 	else

  1155 	  return backward_map[e.in];

  1156       }

  1157 //       T get(Edge e) const {

  1158 // 	if (e.out_or_in)

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

  1160 // 	else

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

  1162 //       }

  1163     };

  1164   };

  1166   //ErasingFirstGraphWrapper for blocking flows

  1167   template<typename Graph, typename FirstOutEdgesMap>

  1168   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1169   protected:

  1170     FirstOutEdgesMap* first_out_edges;

  1171   public:

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

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

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

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

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

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

  1179     ErasingFirstGraphWrapper(Graph& _graph,

  1180 			     FirstOutEdgesMap& _first_out_edges) :

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

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

  1184       graph->first(i);

  1185       return i;

  1186     }

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

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

  1189       e=(*first_out_edges)[n];

  1190       return e;

  1191     }

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

  1193       graph->first(i, p);

  1194       return i;

  1195     }

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

  1198     //  return gw.getNext(i);

  1199     //}

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

  1201       graph->next(i);

  1202       return i;

  1203     }

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

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

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

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

  1211     void erase(const OutEdgeIt& e) const {

  1212       OutEdgeIt f=e;

  1213       this->next(f);

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

  1215     }

  1216   };

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

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

  1220 //   class ResGraphWrapper

  1221 //   {

  1222 //     Graph* graph;

  1224 //   public:

  1225 //     typedef Graph ParentGraph;

  1227 //     typedef typename Graph::Node Node;

  1228 //     typedef typename Graph::Edge Edge;

  1230 //     typedef typename Graph::NodeIt NodeIt;

  1232 //     class OutEdgeIt {

  1233 //     public:

  1234 //       //Graph::Node n;

  1235 //       bool out_or_in;

  1236 //       typename Graph::OutEdgeIt o;

  1237 //       typename Graph::InEdgeIt i;

  1238 //     };

  1239 //     class InEdgeIt {

  1240 //     public:

  1241 //       //Graph::Node n;

  1242 //       bool out_or_in;

  1243 //       typename Graph::OutEdgeIt o;

  1244 //       typename Graph::InEdgeIt i;

  1245 //     };

  1246 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1247 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1254 //     // Edge and SymEdge  is missing!!!!

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

  1257 //     //FIXME

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

  1259 //       {

  1260 // 	e.n=n;

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

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

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

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

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

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

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

  1268 // 	}

  1269 // 	return e;

  1270 //       }

  1271 // /*

  1272 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1273 //   {

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

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

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

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

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

  1279 //   }

  1280 //   else {

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

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

  1283 //   return e;

  1284 //   }

  1285 //   }

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

  1287 // */

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

  1290 //     //FIXME

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

  1292 //       {

  1293 // 	e.n=n;

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

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

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

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

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

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

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

  1301 // 	}

  1302 // 	return e;

  1303 //       }

  1304 // /*

  1305 //   InEdgeIt &goNext(InEdgeIt &e)

  1306 //   {

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

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

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

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

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

  1312 //   }

  1313 //   else {

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

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

  1316 //   return e;

  1317 //   }

  1318 //   }

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

  1320 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1362 //   };

  1364 } //namespace hugo

  1366 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Mon, 05 Apr 2004 17:38:54 +0000
changeset 307	0fac67bef95a
parent 305	6720705c9095
child 311	6635b11938fe
permissions	-rw-r--r--