Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/hugo/graph_wrapper.h
changeset 565 18787f6db0db
parent 561 a10e6f1769e2
child 569 3b6afd33c221
equal deleted inserted replaced
2:cf5eb092632c 3:3483eccee998 
   595     typedef typename GraphWrapper<Graph>::Node Node;
 
   595     typedef typename GraphWrapper<Graph>::Node Node;
 
   596     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
 
   596     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
 
   597     class Edge : public Graph::Edge {
 
   597     class Edge : public Graph::Edge {
 
   598       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   598       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   599     protected:
 
   599     protected:
 
   600       bool forward; //true, iff forward
 
   600       bool backward; //true, iff backward
 
   601 //      typename Graph::Edge e;
 
   601 //      typename Graph::Edge e;
 
   602     public:
 
   602     public:
 
   603       Edge() { }
 
   603       Edge() { }
 
   604       Edge(const typename Graph::Edge& _e, bool _forward) : 
   604       Edge(const typename Graph::Edge& _e, bool _backward) : 
   605 	Graph::Edge(_e), forward(_forward) { }
 
   605 	Graph::Edge(_e), backward(_backward) { }
 
   606       Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
 
   606       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
 
   607 //the unique invalid iterator
 
   607 //the unique invalid iterator
 
   608       friend bool operator==(const Edge& u, const Edge& v) { 
   608       friend bool operator==(const Edge& u, const Edge& v) { 
   609 	return (v.forward==u.forward && 
   609 	return (v.backward==u.backward && 
   610 		static_cast<typename Graph::Edge>(u)==
 
   610 		static_cast<typename Graph::Edge>(u)==
 
   611 		static_cast<typename Graph::Edge>(v));
 
   611 		static_cast<typename Graph::Edge>(v));
 
   612       } 
   612       } 
   613       friend bool operator!=(const Edge& u, const Edge& v) { 
   613       friend bool operator!=(const Edge& u, const Edge& v) { 
   614 	return (v.forward!=u.forward || 
   614 	return (v.backward!=u.backward || 
   615 		static_cast<typename Graph::Edge>(u)!=
 
   615 		static_cast<typename Graph::Edge>(u)!=
 
   616 		static_cast<typename Graph::Edge>(v));
 
   616 		static_cast<typename Graph::Edge>(v));
 
   617       } 
   617       } 
   618     };
 
   618     };
 
   619 
   619 
   620     class OutEdgeIt {
 
   620     class OutEdgeIt {
 
   621       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   621       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   622     protected:
 
   622     protected:
 
   623       typename Graph::OutEdgeIt out;
 
   623       typename Graph::OutEdgeIt out;
 
   624       typename Graph::InEdgeIt in;
 
   624       typename Graph::InEdgeIt in;
 
   625       bool forward;
 
   625       bool backward;
 
   626     public:
 
   626     public:
 
   627       OutEdgeIt() { }
 
   627       OutEdgeIt() { }
 
   628       //FIXME
 
   628       //FIXME
 
   629 //      OutEdgeIt(const Edge& e) : Edge(e) { }
 
   629 //      OutEdgeIt(const Edge& e) : Edge(e) { }
 
   630       OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
 
   630       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
 
   631 //the unique invalid iterator
 
   631 //the unique invalid iterator
 
   632       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
   632       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
   633 	forward=true;
 
   633 	backward=false;
 
   634 	resG.graph->first(out, v);
 
   634 	resG.graph->first(out, v);
 
   635 	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
 
   635 	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
 
   636 	if (!resG.graph->valid(out)) {
 
   636 	if (!resG.graph->valid(out)) {
 
   637 	  forward=false;
 
   637 	  backward=true;
 
   638 	  resG.graph->first(in, v);
 
   638 	  resG.graph->first(in, v);
 
   639 	  while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
 
   639 	  while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
 
   640 	}
 
   640 	}
 
   641       }
 
   641       }
 
   642       operator Edge() const { 
   642       operator Edge() const { 
   643 //	Edge e;
 
   643 //	Edge e;
 
   644 //	e.forward=this->forward;
 
   644 //	e.forward=this->forward;
 
   645 //	if (this->forward) e=out; else e=in;
 
   645 //	if (this->forward) e=out; else e=in;
 
   646 //	return e;
 
   646 //	return e;
 
   647 	if (this->forward) 
   647 	if (this->backward) 
   648 	  return Edge(out, this->forward); 
   648 	  return Edge(in, this->backward); 
   649 	else 
   649 	else 
   650 	  return Edge(in, this->forward);
 
   650 	  return Edge(out, this->backward);
 
   651       }
 
   651       }
 
   652     };
 
   652     };
 
   653 
   653 
   654     class InEdgeIt {
 
   654     class InEdgeIt {
 
   655       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   655       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   656     protected:
 
   656     protected:
 
   657       typename Graph::OutEdgeIt out;
 
   657       typename Graph::OutEdgeIt out;
 
   658       typename Graph::InEdgeIt in;
 
   658       typename Graph::InEdgeIt in;
 
   659       bool forward;
 
   659       bool backward;
 
   660     public:
 
   660     public:
 
   661       InEdgeIt() { }
 
   661       InEdgeIt() { }
 
   662       //FIXME
 
   662       //FIXME
 
   663 //      OutEdgeIt(const Edge& e) : Edge(e) { }
 
   663 //      OutEdgeIt(const Edge& e) : Edge(e) { }
 
   664       InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
 
   664       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
 
   665 //the unique invalid iterator
 
   665 //the unique invalid iterator
 
   666       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
   666       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
   667 	forward=true;
 
   667 	backward=false;
 
   668 	resG.graph->first(in, v);
 
   668 	resG.graph->first(in, v);
 
   669 	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
 
   669 	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
 
   670 	if (!resG.graph->valid(in)) {
 
   670 	if (!resG.graph->valid(in)) {
 
   671 	  forward=false;
 
   671 	  backward=true;
 
   672 	  resG.graph->first(out, v);
 
   672 	  resG.graph->first(out, v);
 
   673 	  while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
 
   673 	  while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
 
   674 	}
 
   674 	}
 
   675       }
 
   675       }
 
   676       operator Edge() const { 
   676       operator Edge() const { 
   677 //	Edge e;
 
   677 //	Edge e;
 
   678 //	e.forward=this->forward;
 
   678 //	e.forward=this->forward;
 
   679 //	if (this->forward) e=out; else e=in;
 
   679 //	if (this->forward) e=out; else e=in;
 
   680 //	return e;
 
   680 //	return e;
 
   681 	if (this->forward) 
   681 	if (this->backward) 
   682 	  return Edge(in, this->forward); 
   682 	  return Edge(out, this->backward); 
   683 	else 
   683 	else 
   684 	  return Edge(out, this->forward);
 
   684 	  return Edge(in, this->backward);
 
   685       }
 
   685       }
 
   686     };
 
   686     };
 
   687 
   687 
   688     class EdgeIt {
 
   688     class EdgeIt {
 
   689       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   689       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
 
   690     protected:
 
   690     protected:
 
   691       typename Graph::EdgeIt e;
 
   691       typename Graph::EdgeIt e;
 
   692       bool forward;
 
   692       bool backward;
 
   693     public:
 
   693     public:
 
   694       EdgeIt() { }
 
   694       EdgeIt() { }
 
   695       EdgeIt(const Invalid& i) : e(i), forward(false) { }
 
   695       EdgeIt(const Invalid& i) : e(i), backward(true) { }
 
   696       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
   696       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
   697 	forward=true;
 
   697 	backward=false;
 
   698 	resG.graph->first(e);
 
   698 	resG.graph->first(e);
 
   699 	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
 
   699 	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
 
   700 	if (!resG.graph->valid(e)) {
 
   700 	if (!resG.graph->valid(e)) {
 
   701 	  forward=false;
 
   701 	  backward=true;
 
   702 	  resG.graph->first(e);
 
   702 	  resG.graph->first(e);
 
   703 	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
 
   703 	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
 
   704 	}
 
   704 	}
 
   705       }
 
   705       }
 
   706       operator Edge() const { 
   706       operator Edge() const { 
   707 	return Edge(e, this->forward);
 
   707 	return Edge(e, this->backward);
 
   708       }
 
   708       }
 
   709     };
 
   709     };
 
   710 
   710 
   711     using GraphWrapper<Graph>::first;
 
   711     using GraphWrapper<Graph>::first;
 
   712 //     NodeIt& first(NodeIt& i) const { 
   712 //     NodeIt& first(NodeIt& i) const { 
   724     }
 
   724     }
 
   725   
   725   
   726     using GraphWrapper<Graph>::next;
 
   726     using GraphWrapper<Graph>::next;
 
   727 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
 
   727 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
 
   728     OutEdgeIt& next(OutEdgeIt& e) const { 
   728     OutEdgeIt& next(OutEdgeIt& e) const { 
   729       if (e.forward) {
 
   729       if (!e.backward) {
 
   730 	Node v=this->graph->aNode(e.out);
 
   730 	Node v=this->graph->aNode(e.out);
 
   731 	this->graph->next(e.out);
 
   731 	this->graph->next(e.out);
 
   732 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
   732 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
   733 	  this->graph->next(e.out); }
 
   733 	  this->graph->next(e.out); }
 
   734 	if (!this->graph->valid(e.out)) {
 
   734 	if (!this->graph->valid(e.out)) {
 
   735 	  e.forward=false;
 
   735 	  e.backward=true;
 
   736 	  this->graph->first(e.in, v); 
   736 	  this->graph->first(e.in, v); 
   737 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
   737 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
   738 	    this->graph->next(e.in); }
 
   738 	    this->graph->next(e.in); }
 
   739 	}
 
   739 	}
 
   740       } else {
 
   740       } else {
 
   744       }
 
   744       }
 
   745       return e;
 
   745       return e;
 
   746     }
 
   746     }
 
   747 //     FIXME Not tested
 
   747 //     FIXME Not tested
 
   748     InEdgeIt& next(InEdgeIt& e) const { 
   748     InEdgeIt& next(InEdgeIt& e) const { 
   749       if (e.forward) {
 
   749       if (!e.backward) {
 
   750 	Node v=this->graph->aNode(e.in);
 
   750 	Node v=this->graph->aNode(e.in);
 
   751 	this->graph->next(e.in);
 
   751 	this->graph->next(e.in);
 
   752 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
   752 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
   753 	  this->graph->next(e.in); }
 
   753 	  this->graph->next(e.in); }
 
   754 	if (!this->graph->valid(e.in)) {
 
   754 	if (!this->graph->valid(e.in)) {
 
   755 	  e.forward=false;
 
   755 	  e.backward=true;
 
   756 	  this->graph->first(e.out, v); 
   756 	  this->graph->first(e.out, v); 
   757 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
   757 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
   758 	    this->graph->next(e.out); }
 
   758 	    this->graph->next(e.out); }
 
   759 	}
 
   759 	}
 
   760       } else {
 
   760       } else {
 
   763 	  this->graph->next(e.out); } 
   763 	  this->graph->next(e.out); } 
   764       }
 
   764       }
 
   765       return e;
 
   765       return e;
 
   766     }
 
   766     }
 
   767     EdgeIt& next(EdgeIt& e) const {
 
   767     EdgeIt& next(EdgeIt& e) const {
 
   768       if (e.forward) {
 
   768       if (!e.backward) {
 
   769 	this->graph->next(e.e);
 
   769 	this->graph->next(e.e);
 
   770 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
   770 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
   771 	  this->graph->next(e.e); }
 
   771 	  this->graph->next(e.e); }
 
   772 	if (!this->graph->valid(e.e)) {
 
   772 	if (!this->graph->valid(e.e)) {
 
   773 	  e.forward=false;
 
   773 	  e.backward=true;
 
   774 	  this->graph->first(e.e); 
   774 	  this->graph->first(e.e); 
   775 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
   775 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
   776 	    this->graph->next(e.e); }
 
   776 	    this->graph->next(e.e); }
 
   777 	}
 
   777 	}
 
   778       } else {
 
   778       } else {
 
   782       }
 
   782       }
 
   783       return e;
 
   783       return e;
 
   784     }
 
   784     }
 
   785 
   785 
   786     Node tail(Edge e) const { 
   786     Node tail(Edge e) const { 
   787       return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
 
   787       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
 
   788     Node head(Edge e) const { 
   788     Node head(Edge e) const { 
   789       return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
 
   789       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
 
   790 
   790 
   791     Node aNode(OutEdgeIt e) const { 
   791     Node aNode(OutEdgeIt e) const { 
   792       return ((e.forward) ? this->graph->aNode(e.out) : 
   792       return ((!e.backward) ? this->graph->aNode(e.out) : 
   793 	      this->graph->aNode(e.in)); }
 
   793 	      this->graph->aNode(e.in)); }
 
   794     Node bNode(OutEdgeIt e) const { 
   794     Node bNode(OutEdgeIt e) const { 
   795       return ((e.forward) ? this->graph->bNode(e.out) : 
   795       return ((!e.backward) ? this->graph->bNode(e.out) : 
   796 	      this->graph->bNode(e.in)); }
 
   796 	      this->graph->bNode(e.in)); }
 
   797 
   797 
   798     Node aNode(InEdgeIt e) const { 
   798     Node aNode(InEdgeIt e) const { 
   799       return ((e.forward) ? this->graph->aNode(e.in) : 
   799       return ((!e.backward) ? this->graph->aNode(e.in) : 
   800 	      this->graph->aNode(e.out)); }
 
   800 	      this->graph->aNode(e.out)); }
 
   801     Node bNode(InEdgeIt e) const { 
   801     Node bNode(InEdgeIt e) const { 
   802       return ((e.forward) ? this->graph->bNode(e.in) : 
   802       return ((!e.backward) ? this->graph->bNode(e.in) : 
   803 	      this->graph->bNode(e.out)); }
 
   803 	      this->graph->bNode(e.out)); }
 
   804 
   804 
   805 //    int nodeNum() const { return graph->nodeNum(); }
 
   805 //    int nodeNum() const { return graph->nodeNum(); }
 
   806     //FIXME
 
   806     //FIXME
 
   807     void edgeNum() const { }
 
   807     void edgeNum() const { }
 
   814     bool valid(Edge e) const { 
   814     bool valid(Edge e) const { 
   815       return this->graph->valid(e);
 
   815       return this->graph->valid(e);
 
   816 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   816 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   817     }
 
   817     }
 
   818 
   818 
   819     bool forward(const Edge& e) const { return e.forward; }
 
   819     bool forward(const Edge& e) const { return !e.backward; }
 
   820     bool backward(const Edge& e) const { return !e.forward; }
 
   820     bool backward(const Edge& e) const { return e.backward; }
 
   821 
   821 
   822     void augment(const Edge& e, Number a) const {
 
   822     void augment(const Edge& e, Number a) const {
 
   823       if (e.forward)  
   823       if (!e.backward)  
   824 // 	flow->set(e.out, flow->get(e.out)+a);
 
   824 // 	flow->set(e.out, flow->get(e.out)+a);
 
   825 	flow->set(e, (*flow)[e]+a);
 
   825 	flow->set(e, (*flow)[e]+a);
 
   826       else  
   826       else  
   827 // 	flow->set(e.in, flow->get(e.in)-a);
 
   827 // 	flow->set(e.in, flow->get(e.in)-a);
 
   828 	flow->set(e, (*flow)[e]-a);
 
   828 	flow->set(e, (*flow)[e]-a);
 
   829     }
 
   829     }
 
   830 
   830 
   831     Number resCap(const Edge& e) const { 
   831     Number resCap(const Edge& e) const { 
   832       if (e.forward) 
   832       if (!e.backward) 
   833 //	return (capacity->get(e.out)-flow->get(e.out)); 
   833 //	return (capacity->get(e.out)-flow->get(e.out)); 
   834 	return ((*capacity)[e]-(*flow)[e]); 
   834 	return ((*capacity)[e]-(*flow)[e]); 
   835       else 
   835       else 
   836 //	return (flow->get(e.in)); 
   836 //	return (flow->get(e.in)); 
   837 	return ((*flow)[e]); 
   837 	return ((*flow)[e]); 
   852       typename Graph::template EdgeMap<T> forward_map, backward_map; 
   852       typename Graph::template EdgeMap<T> forward_map, backward_map; 
   853     public:
 
   853     public:
 
   854       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
 
   854       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
 
   855       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
 
   855       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
 
   856       void set(Edge e, T a) { 
   856       void set(Edge e, T a) { 
   857 	if (e.forward) 
   857 	if (!e.backward) 
   858 	  forward_map.set(e.out, a); 
   858 	  forward_map.set(e.out, a); 
   859 	else 
   859 	else 
   860 	  backward_map.set(e.in, a); 
   860 	  backward_map.set(e.in, a); 
   861       }
 
   861       }
 
   862       T operator[](Edge e) const { 
   862       T operator[](Edge e) const { 
   863 	if (e.forward) 
   863 	if (!e.backward) 
   864 	  return forward_map[e.out]; 
   864 	  return forward_map[e.out]; 
   865 	else 
   865 	else 
   866 	  return backward_map[e.in]; 
   866 	  return backward_map[e.in]; 
   867       }
 
   867       }
 
   868 //       T get(Edge e) const { 
   868 //       T get(Edge e) const {
lemon-0.x