lemon-0.x: src/work/marci/experiment/graph_wrapper

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

     2 #ifndef LEMON_GRAPH_WRAPPER_H

     3 #define LEMON_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     7 namespace lemon {

     9   template<typename Graph>

    10   class TrivGraphWrapper {

    11   protected:

    12     Graph* graph;

    14   public:

    15     typedef Graph BaseGraph;

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

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

   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       return i;

   408     }

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

   410       graph->first(i, p);

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

   412       return i;

   413     }

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

   416     //  return gw.getNext(i);

   417     //}

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

   419       graph->next(i);

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

   421       return i;

   422     }

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

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

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

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

   429   };

   431 //   template<typename GraphWrapper>

   432 //   class UndirGraphWrapper {

   433 //   protected:

   434 //     //Graph* graph;

   435 //     GraphWrapper gw;

   437 //   public:

   438 //     typedef GraphWrapper BaseGraph;

   440 //     typedef typename GraphWrapper::Node Node;

   441 //     typedef typename GraphWrapper::NodeIt NodeIt;

   443 //     //typedef typename Graph::Edge Edge;

   444 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   445 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   446 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   447 //     //typedef typename Graph::EdgeIt EdgeIt;

   449 //     //private:

   450 //     typedef typename GraphWrapper::Edge GraphEdge;

   451 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   452 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   453 //     //public:

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

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

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

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

   461 //     class Edge {

   462 //       friend class UndirGraphWrapper<GraphWrapper>;

   463 //       bool out_or_in; //true iff out

   464 //       GraphOutEdgeIt out;

   465 //       GraphInEdgeIt in;

   466 //     public:

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

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

   469 //       operator GraphEdge() const {

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

   471 //       }

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

   473 // 	if (v.out_or_in)

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

   475 // 	else

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

   477 //       }

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

   479 // 	if (v.out_or_in)

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

   481 // 	else

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

   483 //       }

   484 //     };

   486 //     class OutEdgeIt : public Edge {

   487 //       friend class UndirGraphWrapper<GraphWrapper>;

   488 //     public:

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

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

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

   492 // 	: Edge() {

   493 // 	out_or_in=true;

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

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

   496 // 	  out_or_in=false;

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

   498 // 	}

   499 //       }

   500 //     };

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

   503 //       e.out_or_in=true;

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

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

   506 // 	e.out_or_in=false;

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

   508 //       }

   509 //       return e;

   510 //     }

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

   513 //       if (e.out_or_in) {

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

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

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

   517 // 	  e.out_or_in=false;

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

   519 // 	}

   520 //       } else {

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

   522 //       }

   523 //       return e;

   524 //     }

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

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

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

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

   531 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   574 //     public:

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

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

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

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

   579 //     };

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

   582 //     public:

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

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

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

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

   587 //     };

   588 //   };

   591   template<typename Graph>

   592   class UndirGraphWrapper : public GraphWrapper<Graph> {

   593   protected:

   594     typedef typename Graph::Edge GraphEdge;

   595     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   596     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   597   public:

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

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

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

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

   604     class Edge {

   605       friend class UndirGraphWrapper<Graph>;

   606     protected:

   607       bool out_or_in; //true iff out

   608       GraphOutEdgeIt out;

   609       GraphInEdgeIt in;

   610     public:

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

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

   613       operator GraphEdge() const {

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

   615       }

   616 //FIXME

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

   618 //is it good?

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

   620 	if (v.out_or_in)

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

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

   623 	else

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

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

   626       }

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

   628 	if (v.out_or_in)

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

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

   631 	else

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

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

   634       }

   635     };

   637     class OutEdgeIt : public Edge {

   638       friend class UndirGraphWrapper<Graph>;

   639     public:

   640       OutEdgeIt() : Edge() { }

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

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

   643 	: Edge() {

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

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

   646       }

   647     };

   649     typedef OutEdgeIt InEdgeIt;

   651     class EdgeIt : public Edge {

   652       friend class UndirGraphWrapper<Graph>;

   653     protected:

   654       NodeIt v;

   655     public:

   656       EdgeIt() : Edge() { }

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

   658       EdgeIt(const UndirGraphWrapper<Graph>& _G)

   659 	: Edge() {

   660 	out_or_in=true;

   661 	//Node v;

   662 	_G.first(v);

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

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

   665 	  _G.graph->next(v);

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

   667 	}

   668       }

   669     };

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

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

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

   674       return e;

   675     }

   677     EdgeIt& first(EdgeIt& e) const {

   678       e.out_or_in=true;

   679       //NodeIt v;

   680       first(e.v);

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

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

   683 	graph->next(e.v);

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

   685       }

   686       return e;

   687     }

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

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

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

   693     OutEdgeIt& next(OutEdgeIt& e) const {

   694       if (e.out_or_in) {

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

   696 	graph->next(e.out);

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

   698       } else {

   699 	graph->next(e.in);

   700       }

   701       return e;

   702     }

   704     EdgeIt& next(EdgeIt& e) const {

   705       //NodeIt v=tail(e);

   706       graph->next(e.out);

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

   708 	next(e.v);

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

   710       }

   711       return e;

   712     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   737     Node aNode(const OutEdgeIt& e) const {

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

   739     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   753 //     public:

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

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

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

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

   758 //     };

   760 //     template<typename T> class EdgeMap :

   761 //       public GraphWrapper<Graph>::EdgeMap<T> {

   762 //     public:

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

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

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

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

   767 //     };

   768    };

   774 //   template<typename Graph>

   775 //   class SymGraphWrapper

   776 //   {

   777 //     Graph* graph;

   779 //   public:

   780 //     typedef Graph BaseGraph;

   782 //     typedef typename Graph::Node Node;

   783 //     typedef typename Graph::Edge Edge;

   785 //     typedef typename Graph::NodeIt NodeIt;

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

   788 //     //iranyitatlant, ami van

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

   790 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   792 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   793 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   840 //   };

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

   844   class ResGraphWrapper : public GraphWrapper<Graph>{

   845   public:

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

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

   848   protected:

   849     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   850     typedef typename Graph::InEdgeIt OldInEdgeIt;

   851     FlowMap* flow;

   852     const CapacityMap* capacity;

   853   public:

   855     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

   856 		    const CapacityMap& _capacity) :

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

   859     class Edge;

   860     class OutEdgeIt;

   861     friend class Edge;

   862     friend class OutEdgeIt;

   864     class Edge {

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

   866     protected:

   867       bool out_or_in; //true, iff out

   868       OldOutEdgeIt out;

   869       OldInEdgeIt in;

   870     public:

   871       Edge() : out_or_in(true) { }

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

   873 //       bool valid() const {

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

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

   876 	if (v.out_or_in)

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

   878 	else

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

   880       }

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

   882 	if (v.out_or_in)

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

   884 	else

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

   886       }

   887     };

   890     class OutEdgeIt : public Edge {

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

   892     public:

   893       OutEdgeIt() { }

   894       //FIXME

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

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

   897     protected:

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

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

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

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

   902 	  out_or_in=0;

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

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

   905 	}

   906       }

   907 //     public:

   908 //       OutEdgeIt& operator++() {

   909 // 	if (out_or_in) {

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

   911 // 	  ++out;

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

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

   914 // 	    out_or_in=0;

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

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

   917 // 	  }

   918 // 	} else {

   919 // 	  ++in;

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

   921 // 	}

   922 // 	return *this;

   923 //       }

   924     };

   926     //FIXME This is just for having InEdgeIt

   927     typedef void InEdgeIt;

   929     class EdgeIt : public Edge {

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

   931       NodeIt v;

   932     public:

   933       EdgeIt() { }

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

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

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

   937 	resG.graph->first(v);

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

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

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

   941 	  resG.graph->next(v);

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

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

   944 	}

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

   946 	  out_or_in=0;

   947 	  resG.graph->first(v);

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

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

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

   951 	    resG.graph->next(v);

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

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

   954 	  }

   955 	}

   956       }

   957 //       EdgeIt& operator++() {

   958 // 	if (out_or_in) {

   959 // 	  ++out;

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

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

   962 // 	    ++v;

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

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

   965 // 	  }

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

   967 // 	    out_or_in=0;

   968 // 	    G->first(v);

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

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

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

   972 // 	      ++v;

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

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

   975 // 	    }

   976 // 	  }

   977 // 	} else {

   978 // 	  ++in;

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

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

   981 // 	    ++v;

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

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

   984 // 	  }

   985 // 	}

   986 // 	return *this;

   987 //       }

   988     };

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

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

   992       e=OutEdgeIt(*this, v);

   993       return e;

   994     }

   995     EdgeIt& first(EdgeIt& e) const {

   996       e=EdgeIt(*this);

   997       return e;

   998     }

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

  1002     OutEdgeIt& next(OutEdgeIt& e) const {

  1003       if (e.out_or_in) {

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

  1005 	graph->next(e.out);

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

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

  1008 	  e.out_or_in=0;

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

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

  1011 	}

  1012       } else {

  1013 	graph->next(e.in);

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

  1015       }

  1016       return e;

  1017     }

  1019     EdgeIt& next(EdgeIt& e) const {

  1020       if (e.out_or_in) {

  1021 	graph->next(e.out);

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

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

  1024 	    graph->next(e.v);

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

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

  1027 	  }

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

  1029 	    e.out_or_in=0;

  1030 	    graph->first(e.v);

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

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

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

  1034 	      graph->next(e.v);

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

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

  1037 	    }

  1038 	  }

  1039 	} else {

  1040 	  graph->next(e.in);

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

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

  1043 	    graph->next(e.v);

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

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

  1046 	  }

  1047 	}

  1048 	return e;

  1049       }

  1052     template< typename It >

  1053     It first() const {

  1054       It e;

  1055       first(e);

  1056       return e;

  1057     }

  1059     template< typename It >

  1060     It first(Node v) const {

  1061       It e;

  1062       first(e, v);

  1063       return e;

  1064     }

  1066     Node tail(Edge e) const {

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

  1068     Node head(Edge e) const {

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

  1071     Node aNode(OutEdgeIt e) const {

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

  1073     Node bNode(OutEdgeIt e) const {

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

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

  1077     //FIXME

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

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

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

  1084     bool valid(Edge e) const {

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

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

  1088       if (e.out_or_in)

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

  1090       else

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

  1092     }

  1094     Number resCap(const Edge& e) const {

  1095       if (e.out_or_in)

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

  1097       else

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

  1099     }

  1101     Number resCap(OldOutEdgeIt out) const {

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

  1103     }

  1105     Number resCap(OldInEdgeIt in) const {

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

  1107     }

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

  1110 //     public:

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

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

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

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

  1115 //     };

  1117 //     template <typename T>

  1118 //     class NodeMap {

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

  1120 //     public:

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

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

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

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

  1125 //     };

  1127     template <typename T>

  1128     class EdgeMap {

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

  1130     public:

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

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

  1133       void set(Edge e, T a) {

  1134 	if (e.out_or_in)

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

  1136 	else

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

  1138       }

  1139       T get(Edge e) {

  1140 	if (e.out_or_in)

  1141 	  return forward_map.get(e.out);

  1142 	else

  1143 	  return backward_map.get(e.in);

  1144       }

  1145     };

  1146   };

  1148   //ErasingFirstGraphWrapper for blocking flows

  1149   template<typename Graph, typename FirstOutEdgesMap>

  1150   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1151   protected:

  1152     FirstOutEdgesMap* first_out_edges;

  1153   public:

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

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

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

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

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

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

  1161     ErasingFirstGraphWrapper(Graph& _graph,

  1162 			     FirstOutEdgesMap& _first_out_edges) :

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

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

  1166       graph->first(i);

  1167       return i;

  1168     }

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

  1170       e=first_out_edges->get(n);

  1171       return e;

  1172     }

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

  1174       graph->first(i, p);

  1175       return i;

  1176     }

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

  1179     //  return gw.getNext(i);

  1180     //}

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

  1182       graph->next(i);

  1183       return i;

  1184     }

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

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

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

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

  1192     void erase(const OutEdgeIt& e) const {

  1193       OutEdgeIt f=e;

  1194       this->next(f);

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

  1196     }

  1197   };

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

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

  1201 //   class ResGraphWrapper

  1202 //   {

  1203 //     Graph* graph;

  1205 //   public:

  1206 //     typedef Graph BaseGraph;

  1208 //     typedef typename Graph::Node Node;

  1209 //     typedef typename Graph::Edge Edge;

  1211 //     typedef typename Graph::NodeIt NodeIt;

  1213 //     class OutEdgeIt {

  1214 //     public:

  1215 //       //Graph::Node n;

  1216 //       bool out_or_in;

  1217 //       typename Graph::OutEdgeIt o;

  1218 //       typename Graph::InEdgeIt i;

  1219 //     };

  1220 //     class InEdgeIt {

  1221 //     public:

  1222 //       //Graph::Node n;

  1223 //       bool out_or_in;

  1224 //       typename Graph::OutEdgeIt o;

  1225 //       typename Graph::InEdgeIt i;

  1226 //     };

  1227 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1228 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1235 //     // Edge and SymEdge  is missing!!!!

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

  1238 //     //FIXME

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

  1240 //       {

  1241 // 	e.n=n;

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

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

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

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

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

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

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

  1249 // 	}

  1250 // 	return e;

  1251 //       }

  1252 // /*

  1253 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1254 //   {

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

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

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

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

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

  1260 //   }

  1261 //   else {

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

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

  1264 //   return e;

  1265 //   }

  1266 //   }

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

  1268 // */

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

  1271 //     //FIXME

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

  1273 //       {

  1274 // 	e.n=n;

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

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

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

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

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

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

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

  1282 // 	}

  1283 // 	return e;

  1284 //       }

  1285 // /*

  1286 //   InEdgeIt &goNext(InEdgeIt &e)

  1287 //   {

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

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

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

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

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

  1293 //   }

  1294 //   else {

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

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

  1297 //   return e;

  1298 //   }

  1299 //   }

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

  1301 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1343 //   };

  1345 } //namespace lemon

  1347 #endif //LEMON_GRAPH_WRAPPER_H

author	klao
	Wed, 10 Nov 2004 21:42:28 +0000
changeset 978	175cf8c3a994
parent 880	9d0bfd35b97c
child 986	e997802b855c
permissions	-rw-r--r--