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

     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     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }

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

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

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

    28       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    50       return graph->aNode(e); }

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

    52       return graph->bNode(e); }

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

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

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

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

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

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

    63     public:

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

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

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

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

    68     };

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

    70     public:

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

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

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

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

    75     };

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

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

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

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

    82   };

    84   template<typename Graph>

    85   class RevGraphWrapper

    86   {

    87     Graph* graph;

    89   public:

    90     typedef Graph BaseGraph;

    92     typedef typename Graph::NodeIt NodeIt;

    93     typedef typename Graph::EachNodeIt EachNodeIt;

    95     typedef typename Graph::EdgeIt EdgeIt;

    96     typedef typename Graph::OutEdgeIt InEdgeIt;

    97     typedef typename Graph::InEdgeIt OutEdgeIt;

    98     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    99     typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

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

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

   106       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

   125       return graph->aNode(e); }

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

   127       return graph->bNode(e); }

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

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

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

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

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

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

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

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

   141     public:

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

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

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

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

   146     };

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

   148     public:

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

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

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

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

   153     };

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

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

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

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

   160   };

   163   template<typename Graph>

   164   class UndirGraphWrapper {

   165     Graph* graph;

   167   public:

   168     typedef Graph BaseGraph;

   170     typedef typename Graph::NodeIt NodeIt;

   171     typedef typename Graph::EachNodeIt EachNodeIt;

   173     //typedef typename Graph::EdgeIt EdgeIt;

   174     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   175     //typedef typename Graph::InEdgeIt InEdgeIt;

   176     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   177     //typedef typename Graph::EachEdgeIt EachEdgeIt;

   179     //private:

   180     typedef typename Graph::EdgeIt GraphEdgeIt;

   181     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   182     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   183     //public:

   185     class EdgeIt {

   186       friend class UndirGraphWrapper<Graph>;

   187       bool out_or_in; //true iff out

   188       GraphOutEdgeIt out;

   189       GraphInEdgeIt in;

   190     public:

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

   192       operator GraphEdgeIt() const {

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

   194       }

   195     };

   197     class OutEdgeIt : public EdgeIt {

   198       friend class UndirGraphWrapper<Graph>;

   199       //bool out_or_in; //true iff out

   200       //GraphOutEdgeIt out;

   201       //GraphInEdgeIt in;

   202     public:

   203       OutEdgeIt() : EdgeIt() { }

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

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

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

   207 	  out_or_in=false;

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

   209 	}

   210       }

   211     };

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

   214       e.out_or_in=true;

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

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

   217 	e.out_or_in=false;

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

   219       }

   220       return e;

   221     }

   223     OutEdgeIt& next(OutEdgeIt& e) const {

   224       if (e.out_or_in) {

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

   226 	graph->next(e.out);

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

   228 	  e.out_or_in=false;

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

   230 	}

   231       } else {

   232 	graph->next(e.in);

   233       }

   234       return e;

   235     }

   237     NodeIt aNode(const OutEdgeIt& e) const {

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

   239     NodeIt bNode(const OutEdgeIt& e) const {

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

   242     typedef OutEdgeIt InEdgeIt;

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

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

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

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

   249       return graph->getNext(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   284     public:

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

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

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

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

   289     };

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

   291     public:

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

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

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

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

   296     };

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

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

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

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

   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:

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

   390 	     const CapacityMap& _capacity) :

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

   392 //     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :

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

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

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

   396     class EdgeIt;

   397     class OutEdgeIt;

   398     friend class EdgeIt;

   399     friend class OutEdgeIt;

   401     class EdgeIt {

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

   403     protected:

   404       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;

   405       const Graph* G;

   406       FlowMap* flow;

   407       const CapacityMap* capacity;

   408       //OldSymEdgeIt sym;

   409       OldOutEdgeIt out;

   410       OldInEdgeIt in;

   411       bool out_or_in; //true, iff out

   412     public:

   413       EdgeIt() : out_or_in(true) { }

   414       EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :

   415 	G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }

   416       //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }

   417       Number free() const {

   418 	if (out_or_in) {

   419 	  return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));

   420 	} else {

   421 	  return (/*resG->*/flow->get(in));

   422 	}

   423       }

   424       bool valid() const {

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

   426       void augment(Number a) const {

   427 	if (out_or_in) {

   428 	  /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);

   429 	} else {

   430 	  /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);

   431 	}

   432       }

   433       void print() {

   434 	if (out_or_in) {

   435 	  std::cout << "out ";

   436 	  if (out.valid())

   437 	    std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));

   438 	  else

   439 	    std::cout << "invalid";

   440 	}

   441 	else {

   442 	  std::cout << "in ";

   443 	  if (in.valid())

   444 	    std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));

   445 	  else

   446 	    std::cout << "invalid";

   447 	}

   448 	std::cout << std::endl;

   449       }

   450     };

   452     Number free(OldOutEdgeIt out) const {

   453       return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));

   454     }

   455     Number free(OldInEdgeIt in) const {

   456       return (/*resG->*/flow->get(in));

   457     }

   459     class OutEdgeIt : public EdgeIt {

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

   461     public:

   462       OutEdgeIt() { }

   463     private:

   464       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {

   465 	//out=/*resG->*/G->template first<OldOutEdgeIt>(v);

   466 	G->getFirst(out, v);

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

   468 	if (!out.valid()) {

   469 	  out_or_in=0;

   470 	  //in=/*resG->*/G->template first<OldInEdgeIt>(v);

   471 	  G->getFirst(in, v);

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

   473 	}

   474       }

   475     public:

   476       OutEdgeIt& operator++() {

   477 	if (out_or_in) {

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

   479 	  ++out;

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

   481 	  if (!out.valid()) {

   482 	    out_or_in=0;

   483 	    G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);

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

   485 	  }

   486 	} else {

   487 	  ++in;

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

   489 	}

   490 	return *this;

   491       }

   492     };

   494     class EachEdgeIt : public EdgeIt {

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

   496       typename Graph::EachNodeIt v;

   497     public:

   498       EachEdgeIt() { }

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

   500       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {

   501 	out_or_in=true;

   502 	G->getFirst(v);

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

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

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

   506 	  ++v;

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

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

   509 	}

   510 	if (!out.valid()) {

   511 	  out_or_in=0;

   512 	  G->getFirst(v);

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

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

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

   516 	    ++v;

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

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

   519 	  }

   520 	}

   521       }

   522       EachEdgeIt& operator++() {

   523 	if (out_or_in) {

   524 	  ++out;

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

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

   527 	    ++v;

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

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

   530 	  }

   531 	  if (!out.valid()) {

   532 	    out_or_in=0;

   533 	    G->getFirst(v);

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

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

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

   537 	      ++v;

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

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

   540 	    }

   541 	  }

   542 	} else {

   543 	  ++in;

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

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

   546 	    ++v;

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

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

   549 	  }

   550 	}

   551 	return *this;

   552       }

   553     };

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

   556     void getFirst(OutEdgeIt& e, NodeIt v) const {

   557       e=OutEdgeIt(*G, v, *flow, *capacity);

   558     }

   559     void getFirst(EachEdgeIt& e) const {

   560       e=EachEdgeIt(*G, *flow, *capacity);

   561     }

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

   565     OutEdgeIt& next(OutEdgeIt& e) const {

   566       if (e.out_or_in) {

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

   568 	++(e.out);

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

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

   571 	  e.out_or_in=0;

   572 	  G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);

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

   574 	}

   575       } else {

   576 	++(e.in);

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

   578       }

   579       return e;

   580     }

   582     EachEdgeIt& next(EachEdgeIt& e) const {

   583       if (e.out_or_in) {

   584 	++(e.out);

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

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

   587 	    ++(e.v);

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

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

   590 	  }

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

   592 	    e.out_or_in=0;

   593 	    G->getFirst(e.v);

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

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

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

   597 	      ++(e.v);

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

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

   600 	    }

   601 	  }

   602 	} else {

   603 	  ++(e.in);

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

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

   606 	    ++(e.v);

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

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

   609 	  }

   610 	}

   611 	return e;

   612       }

   615     template< typename It >

   616     It first() const {

   617       It e;

   618       getFirst(e);

   619       return e;

   620     }

   622     template< typename It >

   623     It first(NodeIt v) const {

   624       It e;

   625       getFirst(e, v);

   626       return e;

   627     }

   629     NodeIt tail(EdgeIt e) const {

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

   631     NodeIt head(EdgeIt e) const {

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

   634     NodeIt aNode(OutEdgeIt e) const {

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

   636     NodeIt bNode(OutEdgeIt e) const {

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

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

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

   642     bool valid(EdgeIt e) const {

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

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

   646     public:

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

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

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

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

   651     };

   653 //     template <typename T>

   654 //     class NodeMap {

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

   656 //     public:

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

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

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

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

   661 //     };

   663     template <typename T>

   664     class EdgeMap {

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

   666     public:

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

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

   669       void set(EdgeIt e, T a) {

   670 	if (e.out_or_in)

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

   672 	else

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

   674       }

   675       T get(EdgeIt e) {

   676 	if (e.out_or_in)

   677 	  return forward_map.get(e.out);

   678 	else

   679 	  return backward_map.get(e.in);

   680       }

   681     };

   683   };

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

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

   689 //   class ResGraphWrapper

   690 //   {

   691 //     Graph* graph;

   693 //   public:

   694 //     typedef Graph BaseGraph;

   696 //     typedef typename Graph::NodeIt NodeIt;

   697 //     typedef typename Graph::EdgeIt EdgeIt;

   699 //     typedef typename Graph::EachNodeIt EachNodeIt;

   701 //     class OutEdgeIt {

   702 //     public:

   703 //       //Graph::NodeIt n;

   704 //       bool out_or_in;

   705 //       typename Graph::OutEdgeIt o;

   706 //       typename Graph::InEdgeIt i;

   707 //     };

   708 //     class InEdgeIt {

   709 //     public:

   710 //       //Graph::NodeIt n;

   711 //       bool out_or_in;

   712 //       typename Graph::OutEdgeIt o;

   713 //       typename Graph::InEdgeIt i;

   714 //     };

   715 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

   716 //     typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

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

   723 //     // EachEdge and SymEdge  is missing!!!!

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

   726 //     //FIXME

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

   728 //       {

   729 // 	e.n=n;

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

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

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

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

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

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

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

   737 // 	}

   738 // 	return e;

   739 //       }

   740 // /*

   741 //   OutEdgeIt &goNext(OutEdgeIt &e)

   742 //   {

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

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

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

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

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

   748 //   }

   749 //   else {

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

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

   752 //   return e;

   753 //   }

   754 //   }

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

   756 // */

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

   759 //     //FIXME

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

   761 //       {

   762 // 	e.n=n;

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

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

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

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

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

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

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

   770 // 	}

   771 // 	return e;

   772 //       }

   773 // /*

   774 //   InEdgeIt &goNext(InEdgeIt &e)

   775 //   {

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

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

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

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

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

   781 //   }

   782 //   else {

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

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

   785 //   return e;

   786 //   }

   787 //   }

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

   789 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   831 //   };

   833 } //namespace hugo

   835 #endif //GRAPH_WRAPPER_H

author	alpar
	Wed, 10 Mar 2004 16:43:50 +0000
changeset 162	abfae454c3b5
parent 156	a34e5a909e97
child 168	27fbd1559fb7
permissions	-rw-r--r--