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

     1 // -*-mode: c++; -*-

     2 #ifndef GRAPH_WRAPPER_H

     3 #define GRAPH_WRAPPER_H

     5 namespace hugo {

     7   template<typename Graph>

     8   class TrivGraphWrapper {

     9     Graph* graph;

    11   public:

    12     typedef Graph BaseGraph;

    14     typedef typename Graph::NodeIt NodeIt;

    15     typedef typename Graph::EachNodeIt EachNodeIt;

    17     typedef typename Graph::EdgeIt EdgeIt;

    18     typedef typename Graph::OutEdgeIt OutEdgeIt;

    19     typedef typename Graph::InEdgeIt InEdgeIt;

    20     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    21     typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

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

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

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

    30     template<typename I, typename P> I& getFirst(I& i, const P& p) const {

    31       return graph->getFirst(i, p); }

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

    34       return graph->getNext(i); }

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

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

    38       It e; getFirst(e); return e; }

    40     template< typename It > It first(const NodeIt& v) const {

    41       It e; getFirst(e, v); return e; }

    43     NodeIt head(const EdgeIt& e) const { return graph->head(e); }

    44     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

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

    47       { return graph->valid(i); }

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

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

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

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

    55     template<typename I> NodeIt aNode(const I& e) const {

    56       return graph->aNode(e); }

    57     template<typename I> NodeIt bNode(const I& e) const {

    58       return graph->bNode(e); }

    60     NodeIt addNode() const { return graph->addNode(); }

    61     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {

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

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

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

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

    69     public:

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

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

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

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

    74     };

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

    77     public:

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

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

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

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

    82     };

    83   };

    85   template<typename Graph>

    86   class RevGraphWrapper

    87   {

    88     Graph* graph;

    90   public:

    91     typedef Graph BaseGraph;

    93     typedef typename Graph::NodeIt NodeIt;

    94     typedef typename Graph::EachNodeIt EachNodeIt;

    96     typedef typename Graph::EdgeIt EdgeIt;

    97     typedef typename Graph::OutEdgeIt InEdgeIt;

    98     typedef typename Graph::InEdgeIt OutEdgeIt;

    99     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   100     typedef typename Graph::EachEdgeIt EachEdgeIt;

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

   103     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

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

   109     template<typename I, typename P> I& getFirst(I& i, const P& p) const {

   110       return graph->getFirst(i, p); }

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

   113       return graph->getNext(i); }

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

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

   117       It e; getFirst(e); return e; }

   119     template< typename It > It first(const NodeIt& v) const {

   120       It e; getFirst(e, v); return e; }

   122     NodeIt head(const EdgeIt& e) const { return graph->tail(e); }

   123     NodeIt tail(const EdgeIt& e) const { return graph->head(e); }

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

   126       { return graph->valid(i); }

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

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

   131     template<typename I> NodeIt aNode(const I& e) const {

   132       return graph->aNode(e); }

   133     template<typename I> NodeIt bNode(const I& e) const {

   134       return graph->bNode(e); }

   136     NodeIt addNode() const { return graph->addNode(); }

   137     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {

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

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

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

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

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

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

   148     public:

   149       NodeMap(const RevGraphWrapper<Graph>& _G) :

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

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

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

   153     };

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

   156     public:

   157       EdgeMap(const RevGraphWrapper<Graph>& _G) :

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

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

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

   161     };

   162   };

   165   template<typename Graph>

   166   class UndirGraphWrapper {

   167     Graph* graph;

   169   public:

   170     typedef Graph BaseGraph;

   172     typedef typename Graph::NodeIt NodeIt;

   173     typedef typename Graph::EachNodeIt EachNodeIt;

   175     //typedef typename Graph::EdgeIt EdgeIt;

   176     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   177     //typedef typename Graph::InEdgeIt InEdgeIt;

   178     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   179     //typedef typename Graph::EachEdgeIt EachEdgeIt;

   181     //private:

   182     typedef typename Graph::EdgeIt GraphEdgeIt;

   183     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   184     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   185     //public:

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

   188     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

   193     class EdgeIt {

   194       friend class UndirGraphWrapper<Graph>;

   195       bool out_or_in; //true iff out

   196       GraphOutEdgeIt out;

   197       GraphInEdgeIt in;

   198     public:

   199       EdgeIt() : out_or_in(true), out(), in() { }

   200       operator GraphEdgeIt() const {

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

   202       }

   203     };

   205     class OutEdgeIt : public EdgeIt {

   206       friend class UndirGraphWrapper<Graph>;

   207     public:

   208       OutEdgeIt() : EdgeIt() { }

   209       OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {

   210 	_G.graph->getFirst(out, n);

   211 	if (!(_G.graph->valid(out))) {

   212 	  out_or_in=false;

   213 	  _G.graph->getFirst(in, n);

   214 	}

   215       }

   216     };

   218     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {

   219       e.out_or_in=true;

   220       graph->getFirst(e.out, n);

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

   222 	e.out_or_in=false;

   223 	graph->getFirst(e.in, n);

   224       }

   225       return e;

   226     }

   228     OutEdgeIt& next(OutEdgeIt& e) const {

   229       if (e.out_or_in) {

   230 	NodeIt n=graph->tail(e.out);

   231 	graph->next(e.out);

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

   233 	  e.out_or_in=false;

   234 	  graph->getFirst(e.in, n);

   235 	}

   236       } else {

   237 	graph->next(e.in);

   238       }

   239       return e;

   240     }

   242     NodeIt aNode(const OutEdgeIt& e) const {

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

   244     NodeIt bNode(const OutEdgeIt& e) const {

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

   247     typedef OutEdgeIt InEdgeIt;

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

   250 //     template<typename I, typename P> I& getFirst(I& i, const P& p) const {

   251 //       return graph->getFirst(i, p); }

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

   254       return graph->getNext(i); }

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

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

   258       It e; getFirst(e); return e; }

   260     template< typename It > It first(const NodeIt& v) const {

   261       It e; getFirst(e, v); return e; }

   263     NodeIt head(const EdgeIt& e) const { return graph->head(e); }

   264     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

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

   267       { return graph->valid(i); }

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

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

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

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

   275 //     template<typename I> NodeIt aNode(const I& e) const {

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

   277 //     template<typename I> NodeIt bNode(const I& e) const {

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

   280     NodeIt addNode() const { return graph->addNode(); }

   281     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {

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

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

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

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

   289     public:

   290       NodeMap(const UndirGraphWrapper<Graph>& _G) :

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

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

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

   294     };

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

   297     public:

   298       EdgeMap(const UndirGraphWrapper<Graph>& _G) :

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

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

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

   302     };

   303   };

   307 //   template<typename Graph>

   308 //   class SymGraphWrapper

   309 //   {

   310 //     Graph* graph;

   312 //   public:

   313 //     typedef Graph BaseGraph;

   315 //     typedef typename Graph::NodeIt NodeIt;

   316 //     typedef typename Graph::EdgeIt EdgeIt;

   318 //     typedef typename Graph::EachNodeIt EachNodeIt;

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

   321 //     //iranyitatlant, ami van

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

   323 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   325 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   326 //     typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

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

   332 //     template<typename I, typename P> I& getFirst(I& i, const P& p) const {

   333 //       return graph->getFirst(i, p); }

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

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

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

   338 //       It e; getFirst(e); return e; }

   340 //     template< typename It > It first(NodeIt v) const {

   341 //       It e; getFirst(e, v); return e; }

   343 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }

   344 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

   346 //     template<typename I> NodeIt aNode(const I& e) const {

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

   348 //     template<typename I> NodeIt bNode(const I& e) const {

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

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

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

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

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

   357 //     NodeIt addNode() { return graph->addNode(); }

   358 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {

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

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

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

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

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

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

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

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

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

   373 //   };

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

   377   class ResGraphWrapper {

   378   public:

   379     typedef Graph BaseGraph;

   380     typedef typename Graph::NodeIt NodeIt;

   381     typedef typename Graph::EachNodeIt EachNodeIt;

   382   private:

   383     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   384     typedef typename Graph::InEdgeIt OldInEdgeIt;

   385     const Graph* G;

   386     FlowMap* flow;

   387     const CapacityMap* capacity;

   388   public:

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

   391 	     const CapacityMap& _capacity) :

   392       G(&_G), flow(&_flow), capacity(&_capacity) { }

   393 //     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :

   394 //       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }

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

   397     const Graph& getGraph() const { return (*G); }

   399     class EdgeIt;

   400     class OutEdgeIt;

   401     friend class EdgeIt;

   402     friend class OutEdgeIt;

   404     class EdgeIt {

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

   406     protected:

   407       bool out_or_in; //true, iff out

   408       OldOutEdgeIt out;

   409       OldInEdgeIt in;

   410     public:

   411       EdgeIt() : out_or_in(true) { }

   412 //       bool valid() const {

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

   414     };

   417     class OutEdgeIt : public EdgeIt {

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

   419     public:

   420       OutEdgeIt() { }

   421       //FIXME

   422       OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }

   423     private:

   424       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {

   425 	resG.G->getFirst(out, v);

   426 	while( out.valid() && !(resG.free(out)>0) ) { ++out; }

   427 	if (!out.valid()) {

   428 	  out_or_in=0;

   429 	  resG.G->getFirst(in, v);

   430 	  while( in.valid() && !(resG.free(in)>0) ) { ++in; }

   431 	}

   432       }

   433 //     public:

   434 //       OutEdgeIt& operator++() {

   435 // 	if (out_or_in) {

   436 // 	  NodeIt v=/*resG->*/G->aNode(out);

   437 // 	  ++out;

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

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

   440 // 	    out_or_in=0;

   441 // 	    G->getFirst(in, v);

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

   443 // 	  }

   444 // 	} else {

   445 // 	  ++in;

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

   447 // 	}

   448 // 	return *this;

   449 //       }

   450     };

   452     class EachEdgeIt : public EdgeIt {

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

   454       typename Graph::EachNodeIt v;

   455     public:

   456       EachEdgeIt() { }

   457       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }

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

   459 	resG.G->getFirst(v);

   460 	if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();

   461 	while (out.valid() && !(resG.free(out)>0) ) { ++out; }

   462 	while (v.valid() && !out.valid()) {

   463 	  ++v;

   464 	  if (v.valid()) resG.G->getFirst(out, v);

   465 	  while (out.valid() && !(resG.free(out)>0) ) { ++out; }

   466 	}

   467 	if (!out.valid()) {

   468 	  out_or_in=0;

   469 	  resG.G->getFirst(v);

   470 	  if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();

   471 	  while (in.valid() && !(resG.free(in)>0) ) { ++in; }

   472 	  while (v.valid() && !in.valid()) {

   473 	    ++v;

   474 	    if (v.valid()) resG.G->getFirst(in, v);

   475 	    while (in.valid() && !(resG.free(in)>0) ) { ++in; }

   476 	  }

   477 	}

   478       }

   479 //       EachEdgeIt& operator++() {

   480 // 	if (out_or_in) {

   481 // 	  ++out;

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

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

   484 // 	    ++v;

   485 // 	    if (v.valid()) G->getFirst(out, v);

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

   487 // 	  }

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

   489 // 	    out_or_in=0;

   490 // 	    G->getFirst(v);

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

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

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

   494 // 	      ++v;

   495 // 	      if (v.valid()) G->getFirst(in, v);

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

   497 // 	    }

   498 // 	  }

   499 // 	} else {

   500 // 	  ++in;

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

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

   503 // 	    ++v;

   504 // 	    if (v.valid()) G->getFirst(in, v);

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

   506 // 	  }

   507 // 	}

   508 // 	return *this;

   509 //       }

   510     };

   512     EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }

   513     OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {

   514       e=OutEdgeIt(*this, v);

   515     }

   516     EachEdgeIt& getFirst(EachEdgeIt& e) const {

   517       e=EachEdgeIt(*this);

   518     }

   520     EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }

   522     OutEdgeIt& next(OutEdgeIt& e) const {

   523       if (e.out_or_in) {

   524 	NodeIt v=G->aNode(e.out);

   525 	++(e.out);

   526 	while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }

   527 	if (!G->valid(e.out)) {

   528 	  e.out_or_in=0;

   529 	  G->getFirst(e.in, v);

   530 	  while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }

   531 	}

   532       } else {

   533 	++(e.in);

   534 	while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }

   535       }

   536       return e;

   537     }

   539     EachEdgeIt& next(EachEdgeIt& e) const {

   540       if (e.out_or_in) {

   541 	++(e.out);

   542 	while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }

   543 	  while (G->valid(e.v) && !G->valid(e.out)) {

   544 	    ++(e.v);

   545 	    if (G->valid(e.v)) G->getFirst(e.out, e.v);

   546 	    while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }

   547 	  }

   548 	  if (!G->valid(e.out)) {

   549 	    e.out_or_in=0;

   550 	    G->getFirst(e.v);

   551 	    if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();

   552 	    while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }

   553 	    while (G->valid(e.v) && !G->valid(e.in)) {

   554 	      ++(e.v);

   555 	      if (G->valid(e.v)) G->getFirst(e.in, e.v);

   556 	      while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }

   557 	    }

   558 	  }

   559 	} else {

   560 	  ++(e.in);

   561 	  while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }

   562 	  while (G->valid(e.v) && !G->valid(e.in)) {

   563 	    ++(e.v);

   564 	    if (G->valid(e.v)) G->getFirst(e.in, e.v);

   565 	    while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }

   566 	  }

   567 	}

   568 	return e;

   569       }

   572     template< typename It >

   573     It first() const {

   574       It e;

   575       getFirst(e);

   576       return e;

   577     }

   579     template< typename It >

   580     It first(NodeIt v) const {

   581       It e;

   582       getFirst(e, v);

   583       return e;

   584     }

   586     NodeIt tail(EdgeIt e) const {

   587       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }

   588     NodeIt head(EdgeIt e) const {

   589       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }

   591     NodeIt aNode(OutEdgeIt e) const {

   592       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }

   593     NodeIt bNode(OutEdgeIt e) const {

   594       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }

   596     int id(NodeIt v) const { return G->id(v); }

   598     bool valid(NodeIt n) const { return G->valid(n); }

   599     bool valid(EdgeIt e) const {

   600       return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }

   602     void augment(const EdgeIt& e, Number a) const {

   603       if (e.out_or_in)

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

   605       else

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

   607     }

   609     Number free(const EdgeIt& e) const {

   610       if (e.out_or_in)

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

   612       else

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

   614     }

   616     Number free(OldOutEdgeIt out) const {

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

   618     }

   620     Number free(OldInEdgeIt in) const {

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

   622     }

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

   625     public:

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

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

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

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

   630     };

   632 //     template <typename T>

   633 //     class NodeMap {

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

   635 //     public:

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

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

   638 //       void set(NodeIt nit, T a) { node_map.set(nit, a); }

   639 //       T get(NodeIt nit) const { return node_map.get(nit); }

   640 //     };

   642     template <typename T>

   643     class EdgeMap {

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

   645     public:

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

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

   648       void set(EdgeIt e, T a) {

   649 	if (e.out_or_in)

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

   651 	else

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

   653       }

   654       T get(EdgeIt e) {

   655 	if (e.out_or_in)

   656 	  return forward_map.get(e.out);

   657 	else

   658 	  return backward_map.get(e.in);

   659       }

   660     };

   661   };

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

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

   665   protected:

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

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

   668   public:

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

   670 			   const CapacityMap& _capacity) :

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

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

   673       for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {

   674 	OutEdgeIt e;

   675 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);

   676 	first_out_edges.set(n, e);

   677       }

   678     }

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

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

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

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

   686     //typedef Graph BaseGraph;

   688     //typedef typename Graph::NodeIt NodeIt;

   689     //typedef typename Graph::EachNodeIt EachNodeIt;

   691     //typedef typename Graph::EdgeIt EdgeIt;

   692     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   693     //typedef typename Graph::InEdgeIt InEdgeIt;

   694     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   695     //typedef typename Graph::EachEdgeIt EachEdgeIt;

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

   698     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;

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

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

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

   703     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   704     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;

   706     EachNodeIt& getFirst(EachNodeIt& n) const {

   707       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);

   708     }

   710     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {

   711       e=first_out_edges.get(n);

   712       return e;

   713     }

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

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

   717     //  return getFirst(i, p); }

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

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

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

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

   724       It e; getFirst(e); return e; }

   726     template< typename It > It first(const NodeIt& v) const {

   727       It e; getFirst(e, v); return e; }

   729     //NodeIt head(const EdgeIt& e) const { return graph->head(e); }

   730     //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

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

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

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

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

   738     //template<typename I> NodeIt aNode(const I& e) const {

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

   740     //template<typename I> NodeIt bNode(const I& e) const {

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

   743     //NodeIt addNode() const { return graph->addNode(); }

   744     //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {

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

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

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

   749     //}

   750     void erase(const EdgeIt& e) {

   751       OutEdgeIt f(e);

   752       next(f);

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

   754     }

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

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

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

   760     public:

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

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

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

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

   765     };

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

   768     public:

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

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

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

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

   773     };

   774   };

   776   template<typename GraphWrapper>

   777   class FilterGraphWrapper {

   778   };

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

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

   783     //Graph* graph;

   785   public:

   786     //typedef Graph BaseGraph;

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

   789     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;

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

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

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

   794     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   795     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;

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

   799   public:

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

   801 			   const CapacityMap& _capacity) :

   802       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {

   803     }

   805     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {

   806       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);

   807       while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))

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

   809       return e;

   810     }

   812     EachNodeIt& next(EachNodeIt& e) const {

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

   814     }

   816     OutEdgeIt& next(OutEdgeIt& e) const {

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

   818       while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))

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

   820       return e;

   821     }

   823     EachNodeIt& getFirst(EachNodeIt& n) const {

   824       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);

   825     }

   827     void erase(const EdgeIt& e) {

   828       OutEdgeIt f(e);

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

   830       while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))

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

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

   833     }

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

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

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

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

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

   842     //template<typename I, typename P> I& getFirst(I& i, const P& p) const {

   843     //  return graph->getFirst(i, p); }

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

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

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

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

   850       It e; getFirst(e); return e; }

   852     template< typename It > It first(const NodeIt& v) const {

   853       It e; getFirst(e, v); return e; }

   855     //NodeIt head(const EdgeIt& e) const { return graph->head(e); }

   856     //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

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

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

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

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

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

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

   867     //template<typename I> NodeIt aNode(const I& e) const {

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

   869     //template<typename I> NodeIt bNode(const I& e) const {

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

   872     //NodeIt addNode() const { return graph->addNode(); }

   873     //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {

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

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

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

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

   881     public:

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

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

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

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

   886     };

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

   889     public:

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

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

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

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

   894     };

   896   public:

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

   899   };

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

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

   905 //   class ResGraphWrapper

   906 //   {

   907 //     Graph* graph;

   909 //   public:

   910 //     typedef Graph BaseGraph;

   912 //     typedef typename Graph::NodeIt NodeIt;

   913 //     typedef typename Graph::EdgeIt EdgeIt;

   915 //     typedef typename Graph::EachNodeIt EachNodeIt;

   917 //     class OutEdgeIt {

   918 //     public:

   919 //       //Graph::NodeIt n;

   920 //       bool out_or_in;

   921 //       typename Graph::OutEdgeIt o;

   922 //       typename Graph::InEdgeIt i;

   923 //     };

   924 //     class InEdgeIt {

   925 //     public:

   926 //       //Graph::NodeIt n;

   927 //       bool out_or_in;

   928 //       typename Graph::OutEdgeIt o;

   929 //       typename Graph::InEdgeIt i;

   930 //     };

   931 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

   932 //     typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

   937 //     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }

   939 //     // EachEdge and SymEdge  is missing!!!!

   940 //     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!

   942 //     //FIXME

   943 //     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const

   944 //       {

   945 // 	e.n=n;

   946 // 	graph->getFirst(e.o,n);

   947 // 	while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

   948 // 	  graph->goNext(e.o);

   949 // 	if(!graph->valid(e.o)) {

   950 // 	  graph->getFirst(e.i,n);

   951 // 	  while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

   952 // 	    graph->goNext(e.i);

   953 // 	}

   954 // 	return e;

   955 //       }

   956 // /*

   957 //   OutEdgeIt &goNext(OutEdgeIt &e)

   958 //   {

   959 //   if(graph->valid(e.o)) {

   960 //   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

   961 //   graph->goNext(e.o);

   962 //   if(graph->valid(e.o)) return e;

   963 //   else graph->getFirst(e.i,e.n);

   964 //   }

   965 //   else {

   966 //   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

   967 //   graph->goNext(e.i);

   968 //   return e;

   969 //   }

   970 //   }

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

   972 // */

   973 //     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}

   975 //     //FIXME

   976 //     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const

   977 //       {

   978 // 	e.n=n;

   979 // 	graph->getFirst(e.i,n);

   980 // 	while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

   981 // 	  graph->goNext(e.i);

   982 // 	if(!graph->valid(e.i)) {

   983 // 	  graph->getFirst(e.o,n);

   984 // 	  while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

   985 // 	    graph->goNext(e.o);

   986 // 	}

   987 // 	return e;

   988 //       }

   989 // /*

   990 //   InEdgeIt &goNext(InEdgeIt &e)

   991 //   {

   992 //   if(graph->valid(e.i)) {

   993 //   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

   994 //   graph->goNext(e.i);

   995 //   if(graph->valid(e.i)) return e;

   996 //   else graph->getFirst(e.o,e.n);

   997 //   }

   998 //   else {

   999 //   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1000 //   graph->goNext(e.o);

  1001 //   return e;

  1002 //   }

  1003 //   }

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

  1005 // */

  1006 //     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}

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

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

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

  1012 //       It e; getFirst(e); return e; }

  1014 //     template< typename It > It first(NodeIt v) const {

  1015 //       It e; getFirst(e, v); return e; }

  1017 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }

  1018 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

  1020 //     template<typename I> NodeIt aNode(const I& e) const {

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

  1022 //     template<typename I> NodeIt bNode(const I& e) const {

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

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

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

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

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

  1031 //     NodeIt addNode() { return graph->addNode(); }

  1032 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {

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

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

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

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

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

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

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

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

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

  1047 //   };

  1049 } //namespace hugo

  1051 #endif //GRAPH_WRAPPER_H

author	marci
	Thu, 11 Mar 2004 14:15:07 +0000
changeset 168	27fbd1559fb7
parent 158	4f54d89fa9d2
child 174	44700ed9ffaa
permissions	-rw-r--r--