Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/graph_wrapper.h
changeset 389 770cc1f4861f
parent 381 d72470496fbe
child 393 4535f78639e2
equal deleted inserted replaced
46:3c58571359b2 47:c178f3be2b17 
   181     void erase(const Node& i) const { graph->erase(i); }
 
   181     void erase(const Node& i) const { graph->erase(i); }
 
   182     void erase(const Edge& i) const { graph->erase(i); }
 
   182     void erase(const Edge& i) const { graph->erase(i); }
 
   183   
   183   
   184     void clear() const { graph->clear(); }
 
   184     void clear() const { graph->clear(); }
 
   185     
   185     
   186     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
   186     template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
   187     public:
 
   187       typedef typename Graph::template NodeMap<T> Parent;
 
   188       NodeMap(const GraphWrapper<Graph>& _G) :  
   188     public:
 
   189 	Graph::NodeMap<T>(*(_G.graph)) { }
 
   189       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
 
   190       NodeMap(const GraphWrapper<Graph>& _G, T a) : 
   190       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
 
   191 	Graph::NodeMap<T>(*(_G.graph), a) { }
 
   191     };
 
   192     };
 
   192 
   193 
   193     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
   194     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
   194       typedef typename Graph::template EdgeMap<T> Parent;
 
   195     public:
 
   195     public:
 
   196       EdgeMap(const GraphWrapper<Graph>& _G) :  
   196       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
 
   197 	Graph::EdgeMap<T>(*(_G.graph)) { }
 
   197       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
 
   198       EdgeMap(const GraphWrapper<Graph>& _G, T a) : 
       
   199 	Graph::EdgeMap<T>(*(_G.graph), a) { }
 
       
   200     };
 
   198     };
 
   201   };
 
   199   };
 
   202 
   200 
   203   /// A graph wrapper which reverses the orientation of the edges.
 
   201   /// A graph wrapper which reverses the orientation of the edges.
 
   204 
   202 
   250     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   248     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   251       i=InEdgeIt(*this, p); return i;
 
   249       i=InEdgeIt(*this, p); return i;
 
   252     }
 
   250     }
 
   253 
   251 
   254     using GraphWrapper<Graph>::next;
 
   252     using GraphWrapper<Graph>::next;
 
   255     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
 
   253     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
 
   256     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
 
   254     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
 
   257 
   255 
   258     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
 
   256     Node aNode(const OutEdgeIt& e) const { 
   259     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
 
   257       return Node(this->graph->aNode(e.e)); }
 
   260     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
 
   258     Node aNode(const InEdgeIt& e) const { 
   261     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
 
   259       return Node(this->graph->aNode(e.e)); }
 
       
   260     Node bNode(const OutEdgeIt& e) const { 
       
   261       return Node(this->graph->bNode(e.e)); }
 
       
   262     Node bNode(const InEdgeIt& e) const { 
       
   263       return Node(this->graph->bNode(e.e)); }
 
   262 
   264 
   263     Node tail(const Edge& e) const { 
   265     Node tail(const Edge& e) const { 
   264       return GraphWrapper<Graph>::head(e); }
 
   266       return GraphWrapper<Graph>::head(e); }
 
   265     Node head(const Edge& e) const { 
   267     Node head(const Edge& e) const { 
   266       return GraphWrapper<Graph>::tail(e); }
 
   268       return GraphWrapper<Graph>::tail(e); }
 
   364     EdgeIt& first(EdgeIt& i) const { 
   366     EdgeIt& first(EdgeIt& i) const { 
   365       i=EdgeIt(*this); return i;
 
   367       i=EdgeIt(*this); return i;
 
   366     }
 
   368     }
 
   367     
   369     
   368     NodeIt& next(NodeIt& i) const {
 
   370     NodeIt& next(NodeIt& i) const {
 
   369       graph->next(i.n); 
   371       this->graph->next(i.n); 
   370       while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
 
   372       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
       
   373 	this->graph->next(i.n); }
 
   371       return i;
 
   374       return i;
 
   372     }
 
   375     }
 
   373     OutEdgeIt& next(OutEdgeIt& i) const {
 
   376     OutEdgeIt& next(OutEdgeIt& i) const {
 
   374       graph->next(i.e); 
   377       this->graph->next(i.e); 
   375       while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
 
   378       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
       
   379 	this->graph->next(i.e); }
 
   376       return i;
 
   380       return i;
 
   377     }
 
   381     }
 
   378     InEdgeIt& next(InEdgeIt& i) const {
 
   382     InEdgeIt& next(InEdgeIt& i) const {
 
   379       graph->next(i.e); 
   383       this->graph->next(i.e); 
   380       while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
 
   384       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
       
   385 	this->graph->next(i.e); }
 
   381       return i;
 
   386       return i;
 
   382     }
 
   387     }
 
   383     EdgeIt& next(EdgeIt& i) const {
 
   388     EdgeIt& next(EdgeIt& i) const {
 
   384       graph->next(i.e); 
   389       this->graph->next(i.e); 
   385       while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
 
   390       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
       
   391 	this->graph->next(i.e); }
 
   386       return i;
 
   392       return i;
 
   387     }
 
   393     }
 
   388 
   394 
   389     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
 
   395     Node aNode(const OutEdgeIt& e) const { 
   390     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
 
   396       return Node(this->graph->aNode(e.e)); }
 
   391     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
 
   397     Node aNode(const InEdgeIt& e) const { 
   392     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
 
   398       return Node(this->graph->aNode(e.e)); }
 
       
   399     Node bNode(const OutEdgeIt& e) const { 
       
   400       return Node(this->graph->bNode(e.e)); }
 
       
   401     Node bNode(const InEdgeIt& e) const { 
       
   402       return Node(this->graph->bNode(e.e)); }
 
   393 
   403 
   394     ///\todo
 
   404     ///\todo
 
   395     ///Some doki, please.
 
   405     ///Some doki, please.
 
   396     void hide(const Node& n) const { node_filter_map->set(n, false); }
 
   406     void hide(const Node& n) const { node_filter_map->set(n, false); }
 
   397     ///\todo
 
   407     ///\todo
 
   467 //       GraphWrapper<Graph>::next(n);
 
   477 //       GraphWrapper<Graph>::next(n);
 
   468 //       return n;
 
   478 //       return n;
 
   469 //     }
 
   479 //     }
 
   470     OutEdgeIt& next(OutEdgeIt& e) const {
 
   480     OutEdgeIt& next(OutEdgeIt& e) const {
 
   471       if (e.out_or_in) {
 
   481       if (e.out_or_in) {
 
   472 	typename Graph::Node n=graph->tail(e.out);
 
   482 	typename Graph::Node n=this->graph->tail(e.out);
 
   473 	graph->next(e.out);
 
   483 	this->graph->next(e.out);
 
   474 	if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
 
   484 	if (!this->graph->valid(e.out)) { 
       
   485 	  e.out_or_in=false; this->graph->first(e.in, n); }
 
   475       } else {
 
   486       } else {
 
   476 	graph->next(e.in);
 
   487 	this->graph->next(e.in);
 
   477       }
 
   488       }
 
   478       return e;
 
   489       return e;
 
   479     }
 
   490     }
 
   480     //FIXME InEdgeIt
 
   491     //FIXME InEdgeIt
 
   481 //     EdgeIt& next(EdgeIt& e) const {
 
   492 //     EdgeIt& next(EdgeIt& e) const {
 
   483 // //      graph->next(e.e);
 
   494 // //      graph->next(e.e);
 
   484 //       return e;
 
   495 //       return e;
 
   485 //     }
 
   496 //     }
 
   486 
   497 
   487     Node aNode(const OutEdgeIt& e) const { 
   498     Node aNode(const OutEdgeIt& e) const { 
   488       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
 
   499       if (e.out_or_in) return this->graph->tail(e); else 
       
   500 	return this->graph->head(e); }
 
   489     Node bNode(const OutEdgeIt& e) const { 
   501     Node bNode(const OutEdgeIt& e) const { 
   490       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
 
   502       if (e.out_or_in) return this->graph->head(e); else 
       
   503 	return this->graph->tail(e); }
 
   491   };
 
   504   };
 
   492   
   505   
   493   /// A wrapper for composing the residual graph for directed flow and circulation problems.
 
   506   /// A wrapper for composing the residual graph for directed flow and circulation problems.
 
   494 
   507 
   495   /// A wrapper for composing the residual graph for directed flow and circulation problems.
 
   508   /// A wrapper for composing the residual graph for directed flow and circulation problems.
 
   643   
   656   
   644     using GraphWrapper<Graph>::next;
 
   657     using GraphWrapper<Graph>::next;
 
   645 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
 
   658 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
 
   646     OutEdgeIt& next(OutEdgeIt& e) const { 
   659     OutEdgeIt& next(OutEdgeIt& e) const { 
   647       if (e.forward) {
 
   660       if (e.forward) {
 
   648 	Node v=graph->aNode(e.out);
 
   661 	Node v=this->graph->aNode(e.out);
 
   649 	graph->next(e.out);
 
   662 	this->graph->next(e.out);
 
   650 	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
 
   663 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
   651 	if (!graph->valid(e.out)) {
 
   664 	  this->graph->next(e.out); }
 
       
   665 	if (!this->graph->valid(e.out)) {
 
   652 	  e.forward=false;
 
   666 	  e.forward=false;
 
   653 	  graph->first(e.in, v); 
   667 	  this->graph->first(e.in, v); 
   654 	  while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
 
   668 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
       
   669 	    this->graph->next(e.in); }
 
   655 	}
 
   670 	}
 
   656       } else {
 
   671       } else {
 
   657 	graph->next(e.in);
 
   672 	this->graph->next(e.in);
 
   658 	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 
   673 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
       
   674 	  this->graph->next(e.in); } 
   659       }
 
   675       }
 
   660       return e;
 
   676       return e;
 
   661     }
 
   677     }
 
   662 //     FIXME Not tested
 
   678 //     FIXME Not tested
 
   663     InEdgeIt& next(InEdgeIt& e) const { 
   679     InEdgeIt& next(InEdgeIt& e) const { 
   664       if (e.forward) {
 
   680       if (e.forward) {
 
   665 	Node v=graph->aNode(e.in);
 
   681 	Node v=this->graph->aNode(e.in);
 
   666 	graph->next(e.in);
 
   682 	this->graph->next(e.in);
 
   667 	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
 
   683 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
   668 	if (!graph->valid(e.in)) {
 
   684 	  this->graph->next(e.in); }
 
       
   685 	if (!this->graph->valid(e.in)) {
 
   669 	  e.forward=false;
 
   686 	  e.forward=false;
 
   670 	  graph->first(e.out, v); 
   687 	  this->graph->first(e.out, v); 
   671 	  while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
 
   688 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
       
   689 	    this->graph->next(e.out); }
 
   672 	}
 
   690 	}
 
   673       } else {
 
   691       } else {
 
   674 	graph->next(e.out);
 
   692 	this->graph->next(e.out);
 
   675 	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 
   693 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
       
   694 	  this->graph->next(e.out); } 
   676       }
 
   695       }
 
   677       return e;
 
   696       return e;
 
   678     }
 
   697     }
 
   679     EdgeIt& next(EdgeIt& e) const {
 
   698     EdgeIt& next(EdgeIt& e) const {
 
   680       if (e.forward) {
 
   699       if (e.forward) {
 
   681 	graph->next(e.e);
 
   700 	this->graph->next(e.e);
 
   682 	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
 
   701 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
   683 	if (!graph->valid(e.e)) {
 
   702 	  this->graph->next(e.e); }
 
       
   703 	if (!this->graph->valid(e.e)) {
 
   684 	  e.forward=false;
 
   704 	  e.forward=false;
 
   685 	  graph->first(e.e); 
   705 	  this->graph->first(e.e); 
   686 	  while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
 
   706 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
       
   707 	    this->graph->next(e.e); }
 
   687 	}
 
   708 	}
 
   688       } else {
 
   709       } else {
 
   689 	graph->next(e.e);
 
   710 	this->graph->next(e.e);
 
   690 	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 
   711 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
       
   712 	  this->graph->next(e.e); } 
   691       }
 
   713       }
 
   692       return e;
 
   714       return e;
 
   693     }
 
   715     }
 
   694 
   716 
   695     Node tail(Edge e) const { 
   717     Node tail(Edge e) const { 
   696       return ((e.forward) ? graph->tail(e) : graph->head(e)); }
 
   718       return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
 
   697     Node head(Edge e) const { 
   719     Node head(Edge e) const { 
   698       return ((e.forward) ? graph->head(e) : graph->tail(e)); }
 
   720       return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
 
   699 
   721 
   700     Node aNode(OutEdgeIt e) const { 
   722     Node aNode(OutEdgeIt e) const { 
   701       return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
 
   723       return ((e.forward) ? this->graph->aNode(e.out) : 
       
   724 	      this->graph->aNode(e.in)); }
 
   702     Node bNode(OutEdgeIt e) const { 
   725     Node bNode(OutEdgeIt e) const { 
   703       return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
 
   726       return ((e.forward) ? this->graph->bNode(e.out) : 
       
   727 	      this->graph->bNode(e.in)); }
 
   704 
   728 
   705     Node aNode(InEdgeIt e) const { 
   729     Node aNode(InEdgeIt e) const { 
   706       return ((e.forward) ? graph->aNode(e.in) : graph->aNode(e.out)); }
 
   730       return ((e.forward) ? this->graph->aNode(e.in) : 
       
   731 	      this->graph->aNode(e.out)); }
 
   707     Node bNode(InEdgeIt e) const { 
   732     Node bNode(InEdgeIt e) const { 
   708       return ((e.forward) ? graph->bNode(e.in) : graph->bNode(e.out)); }
 
   733       return ((e.forward) ? this->graph->bNode(e.in) : 
       
   734 	      this->graph->bNode(e.out)); }
 
   709 
   735 
   710 //    int nodeNum() const { return graph->nodeNum(); }
 
   736 //    int nodeNum() const { return graph->nodeNum(); }
 
   711     //FIXME
 
   737     //FIXME
 
   712     void edgeNum() const { }
 
   738     void edgeNum() const { }
 
   713     //int edgeNum() const { return graph->edgeNum(); }
 
   739     //int edgeNum() const { return graph->edgeNum(); }
 
   715 
   741 
   716 //    int id(Node v) const { return graph->id(v); }
 
   742 //    int id(Node v) const { return graph->id(v); }
 
   717 
   743 
   718     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
 
   744     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
 
   719     bool valid(Edge e) const { 
   745     bool valid(Edge e) const { 
   720       return graph->valid(e);
 
   746       return this->graph->valid(e);
 
   721 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   747 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   722     }
 
   748     }
 
   723 
   749 
   724     void augment(const Edge& e, Number a) const {
 
   750     void augment(const Edge& e, Number a) const {
 
   725       if (e.forward)  
   751       if (e.forward)  
   749 //       return ((*flow)[in]); 
   775 //       return ((*flow)[in]); 
   750 //     }
 
   776 //     }
 
   751 
   777 
   752     template <typename T>
 
   778     template <typename T>
 
   753     class EdgeMap {
 
   779     class EdgeMap {
 
   754       typename Graph::EdgeMap<T> forward_map, backward_map; 
   780       typename Graph::template EdgeMap<T> forward_map, backward_map; 
   755     public:
 
   781     public:
 
   756       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
 
   782       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
 
   757       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
 
   783       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
 
   758       void set(Edge e, T a) { 
   784       void set(Edge e, T a) { 
   759 	if (e.forward) 
   785 	if (e.forward) 
   859       i=EdgeIt(*this); return i;
 
   885       i=EdgeIt(*this); return i;
 
   860     }
 
   886     }
 
   861 
   887 
   862     using GraphWrapper<Graph>::next;
 
   888     using GraphWrapper<Graph>::next;
 
   863 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
 
   889 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
 
   864     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
 
   890     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
 
   865     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
 
   891     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
 
   866     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
   892     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
   867     
   893     
   868     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
 
   894     Node aNode(const OutEdgeIt& e) const { 
   869     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
 
   895       return Node(this->graph->aNode(e.e)); }
 
   870     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
 
   896     Node aNode(const InEdgeIt& e) const { 
   871     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
 
   897       return Node(this->graph->aNode(e.e)); }
 
       
   898     Node bNode(const OutEdgeIt& e) const { 
       
   899       return Node(this->graph->bNode(e.e)); }
 
       
   900     Node bNode(const InEdgeIt& e) const { 
       
   901       return Node(this->graph->bNode(e.e)); }
 
   872 
   902 
   873     void erase(const OutEdgeIt& e) const {
 
   903     void erase(const OutEdgeIt& e) const {
 
   874       OutEdgeIt f=e;
 
   904       OutEdgeIt f=e;
 
   875       this->next(f);
 
   905       this->next(f);
 
   876       first_out_edges->set(this->tail(e), f.e);
 
   906       first_out_edges->set(this->tail(e), f.e);
 
   883   /// reference containing the elements for the 
   913   /// reference containing the elements for the 
   884   /// color classes S and T. \c _graph is to be referred to an undirected 
   914   /// color classes S and T. \c _graph is to be referred to an undirected 
   885   /// graph or a directed graph with edges oriented from S to T.
 
   915   /// graph or a directed graph with edges oriented from S to T.
 
   886   template<typename Graph> 
   916   template<typename Graph> 
   887   class BipartiteGraphWrapper : public GraphWrapper<Graph> {
 
   917   class BipartiteGraphWrapper : public GraphWrapper<Graph> {
 
   888     typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
 
   918     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
       
   919     SFalseTTrueMap;
 
   889     SFalseTTrueMap* s_false_t_true_map;
 
   920     SFalseTTrueMap* s_false_t_true_map;
 
   890     
   921     
   891   public:
 
   922   public:
 
   892     static const bool S_CLASS=false;
 
   923     static const bool S_CLASS=false;
 
   893     static const bool T_CLASS=true;
 
   924     static const bool T_CLASS=true;
 
   981 //       this->s_false_t_true_map->next(n); return n; 
  1012 //       this->s_false_t_true_map->next(n); return n; 
   982 //     }
 
  1013 //     }
 
   983 //     TNodeIt& next(TNodeIt& n) const { 
  1014 //     TNodeIt& next(TNodeIt& n) const { 
   984 //       this->s_false_t_true_map->next(n); return n; 
  1015 //       this->s_false_t_true_map->next(n); return n; 
   985 //     }
 
  1016 //     }
 
   986     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
 
  1017     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
 
   987     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
 
  1018     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
 
   988 
  1019 
   989     Node tail(const Edge& e) { 
  1020     Node tail(const Edge& e) { 
   990       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
  1021       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
   991 	return Node(this->graph->tail(e));
 
  1022 	return Node(this->graph->tail(e));
 
   992       else
 
  1023       else
 
  1076 
  1107 
  1077     class Node : public Graph::Node {
 
  1108     class Node : public Graph::Node {
 
  1078     protected:
 
  1109     protected:
 
  1079       friend class GraphWrapper<Graph>;
 
  1110       friend class GraphWrapper<Graph>;
 
  1080       friend class stGraphWrapper<Graph>;
 
  1111       friend class stGraphWrapper<Graph>;
 
  1081       template <typename T> friend class stGraphWrapper<Graph>::NodeMap;
 
  1112       template <typename T> friend class NodeMap;
 
  1082       friend class Edge;
 
  1113       friend class Edge;
 
  1083       friend class OutEdgeIt;
 
  1114       friend class OutEdgeIt;
 
  1084       friend class InEdgeIt;
 
  1115       friend class InEdgeIt;
 
  1085       friend class EdgeIt;
 
  1116       friend class EdgeIt;
 
  1086       int spec; 
  1117       int spec; 
  1117       operator Node() const { return Node(n, spec); }
 
  1148       operator Node() const { return Node(n, spec); }
 
  1118     };
 
  1149     };
 
  1119     class Edge : public Graph::Edge {
 
  1150     class Edge : public Graph::Edge {
 
  1120       friend class GraphWrapper<Graph>;
 
  1151       friend class GraphWrapper<Graph>;
 
  1121       friend class stGraphWrapper<Graph>;
 
  1152       friend class stGraphWrapper<Graph>;
 
  1122       template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;
 
  1153       template <typename T> friend class EdgeMap;
 
  1123       int spec;
 
  1154       int spec;
 
  1124       typename Graph::Node n;
 
  1155       typename Graph::Node n;
 
  1125     public:
 
  1156     public:
 
  1126       Edge() { }
 
  1157       Edge() { }
 
  1127       Edge(const typename Graph::Edge& _e, int _spec, 
  1158       Edge(const typename Graph::Edge& _e, int _spec, 
  1271     }
 
  1302     }
 
  1272 
  1303 
  1273     NodeIt& next(NodeIt& i) const { 
  1304     NodeIt& next(NodeIt& i) const { 
  1274       switch (i.spec) {
 
  1305       switch (i.spec) {
 
  1275 	case 0:
 
  1306 	case 0:
 
  1276 	  graph->next(i.n);
 
  1307 	  this->graph->next(i.n);
 
  1277 	  if (!graph->valid(i.n)) {
 
  1308 	  if (!this->graph->valid(i.n)) {
 
  1278 	    i.spec=1;
 
  1309 	    i.spec=1;
 
  1279 	  }
 
  1310 	  }
 
  1280 	  break;
 
  1311 	  break;
 
  1281 	case 1:
 
  1312 	case 1:
 
  1282 	  i.spec=2;
 
  1313 	  i.spec=2;
 
  1288       return i; 
  1319       return i; 
  1289     }
 
  1320     }
 
  1290     OutEdgeIt& next(OutEdgeIt& i) const { 
  1321     OutEdgeIt& next(OutEdgeIt& i) const { 
  1291       switch (i.spec) {
 
  1322       switch (i.spec) {
 
  1292 	case 0: //normal edge
 
  1323 	case 0: //normal edge
 
  1293 	  typename Graph::Node v=graph->aNode(i.e);
 
  1324 	  typename Graph::Node v=this->graph->aNode(i.e);
 
  1294 	  graph->next(i.e);
 
  1325 	  this->graph->next(i.e);
 
  1295 	  if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
 
  1326 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
 
  1296 	    if (graph->inSClass(v)) { //S, nincs kiel
 
  1327 	    if (this->graph->inSClass(v)) { //S, nincs kiel
 
  1297 	      i.spec=3;
 
  1328 	      i.spec=3;
 
  1298 	      i.n=INVALID;
 
  1329 	      i.n=INVALID;
 
  1299 	    } else { //T, van kiel
 
  1330 	    } else { //T, van kiel
 
  1300 	      i.spec=2; 
  1331 	      i.spec=2; 
  1301 	      i.n=v;
 
  1332 	      i.n=v;
 
  1302 	    }
 
  1333 	    }
 
  1303 	  }
 
  1334 	  }
 
  1304 	  break;
 
  1335 	  break;
 
  1305 	case 1: //s->vmi
 
  1336 	case 1: //s->vmi
 
  1306 	  graph->next(i.n);
 
  1337 	  this->graph->next(i.n);
 
  1307 	  if (!graph->valid(i.n)) i.spec=3;
 
  1338 	  if (!this->graph->valid(i.n)) i.spec=3;
 
  1308 	  break;
 
  1339 	  break;
 
  1309 	case 2: //vmi->t
 
  1340 	case 2: //vmi->t
 
  1310 	  i.spec=3;
 
  1341 	  i.spec=3;
 
  1311 	  i.n=INVALID;
 
  1342 	  i.n=INVALID;
 
  1312 	  break;
 
  1343 	  break;
 
  1314       return i; 
  1345       return i; 
  1315     }
 
  1346     }
 
  1316     InEdgeIt& next(InEdgeIt& i) const { 
  1347     InEdgeIt& next(InEdgeIt& i) const { 
  1317       switch (i.spec) {
 
  1348       switch (i.spec) {
 
  1318 	case 0: //normal edge
 
  1349 	case 0: //normal edge
 
  1319 	  typename Graph::Node v=graph->aNode(i.e);
 
  1350 	  typename Graph::Node v=this->graph->aNode(i.e);
 
  1320 	  graph->next(i.e);
 
  1351 	  this->graph->next(i.e);
 
  1321 	  if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
 
  1352 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
 
  1322 	    if (graph->inTClass(v)) { //S, nincs beel
 
  1353 	    if (this->graph->inTClass(v)) { //S, nincs beel
 
  1323 	      i.spec=3;
 
  1354 	      i.spec=3;
 
  1324 	      i.n=INVALID;
 
  1355 	      i.n=INVALID;
 
  1325 	    } else { //S, van beel
 
  1356 	    } else { //S, van beel
 
  1326 	      i.spec=1; 
  1357 	      i.spec=1; 
  1327 	      i.n=v;
 
  1358 	      i.n=v;
 
  1331 	case 1: //s->vmi
 
  1362 	case 1: //s->vmi
 
  1332 	  i.spec=3;
 
  1363 	  i.spec=3;
 
  1333 	  i.n=INVALID;
 
  1364 	  i.n=INVALID;
 
  1334 	  break;
 
  1365 	  break;
 
  1335 	case 2: //vmi->t
 
  1366 	case 2: //vmi->t
 
  1336 	  graph->next(i.n);
 
  1367 	  this->graph->next(i.n);
 
  1337 	  if (!graph->valid(i.n)) i.spec=3;
 
  1368 	  if (!this->graph->valid(i.n)) i.spec=3;
 
  1338 	  break;
 
  1369 	  break;
 
  1339       }
 
  1370       }
 
  1340       return i; 
  1371       return i; 
  1341     }
 
  1372     }
 
  1342 
  1373 
  1343     EdgeIt& next(EdgeIt& i) const { 
  1374     EdgeIt& next(EdgeIt& i) const { 
  1344       switch (i.spec) {
 
  1375       switch (i.spec) {
 
  1345 	case 0:
 
  1376 	case 0:
 
  1346 	  graph->next(i.e);
 
  1377 	  this->graph->next(i.e);
 
  1347 	  if (!graph->valid(i.e)) { 
  1378 	  if (!this->graph->valid(i.e)) { 
  1348 	    i.spec=1;
 
  1379 	    i.spec=1;
 
  1349 	    graph->first(n, S_CLASS);
 
  1380 	    this->graph->first(i.n, S_CLASS);
 
  1350 	    if (!graph->valid(i.n)) {
 
  1381 	    if (!this->graph->valid(i.n)) {
 
  1351 	      i.spec=2;
 
  1382 	      i.spec=2;
 
  1352 	      graph->first(n, T_CLASS);
 
  1383 	      this->graph->first(i.n, T_CLASS);
 
  1353 	      if (!graph->valid(i.n)) spec=3;
 
  1384 	      if (!this->graph->valid(i.n)) i.spec=3;
 
  1354 	    }
 
  1385 	    }
 
  1355 	  }
 
  1386 	  }
 
  1356 	  break;
 
  1387 	  break;
 
  1357 	case 1:
 
  1388 	case 1:
 
  1358 	  graph->next(i.n);
 
  1389 	  this->graph->next(i.n);
 
  1359 	  if (!graph->valid(i.n)) {
 
  1390 	  if (!this->graph->valid(i.n)) {
 
  1360 	    i.spec=2;
 
  1391 	    i.spec=2;
 
  1361 	    graph->first(n, T_CLASS);
 
  1392 	    this->graph->first(i.n, T_CLASS);
 
  1362 	    if (!graph->valid(i.n)) spec=3;
 
  1393 	    if (!this->graph->valid(i.n)) i.spec=3;
 
  1363 	  }
 
  1394 	  }
 
  1364 	  break;
 
  1395 	  break;
 
  1365 	case 2:
 
  1396 	case 2:
 
  1366 	  graph->next(i.n);
 
  1397 	  this->graph->next(i.n);
 
  1367 	  if (!graph->valid(i.n)) i.spec=3;
 
  1398 	  if (!this->graph->valid(i.n)) i.spec=3;
 
  1368 	  break;
 
  1399 	  break;
 
  1369       }
 
  1400       }
 
  1370       return i; 
  1401       return i; 
  1371     }    
  1402     }    
  1372 
  1403 
  1373     Node tail(const Edge& e) const { 
  1404     Node tail(const Edge& e) const { 
  1374       switch (e.spec) {
 
  1405       switch (e.spec) {
 
  1375 	case 0: 
  1406 	case 0: 
  1376 	  return Node(graph->tail(e));
 
  1407 	  return Node(this->graph->tail(e));
 
  1377 	  break;
 
  1408 	  break;
 
  1378 	case 1:
 
  1409 	case 1:
 
  1379 	  return S_NODE;
 
  1410 	  return S_NODE;
 
  1380 	  break;
 
  1411 	  break;
 
  1381 	case 2:
 
  1412 	case 2:
 
  1384       }
 
  1415       }
 
  1385     }
 
  1416     }
 
  1386     Node head(const Edge& e) const { 
  1417     Node head(const Edge& e) const { 
  1387       switch (e.spec) {
 
  1418       switch (e.spec) {
 
  1388 	case 0: 
  1419 	case 0: 
  1389 	  return Node(graph->head(e));
 
  1420 	  return Node(this->graph->head(e));
 
  1390 	  break;
 
  1421 	  break;
 
  1391 	case 1:
 
  1422 	case 1:
 
  1392 	  return Node(e.n);
 
  1423 	  return Node(e.n);
 
  1393 	  break;
 
  1424 	  break;
 
  1394 	case 2:
 
  1425 	case 2:
 
  1398     }
 
  1429     }
 
  1399 
  1430 
  1400     bool valid(const Node& n) const { return (n.spec<3); }
 
  1431     bool valid(const Node& n) const { return (n.spec<3); }
 
  1401     bool valid(const Edge& e) const { return (e.spec<3); }
 
  1432     bool valid(const Edge& e) const { return (e.spec<3); }
 
  1402 
  1433 
  1403 //    int nodeNum() const { return graph->nodeNum(); }
 
  1434 //    int nodeNum() const { return this->graph->nodeNum(); }
 
  1404 //    int edgeNum() const { return graph->edgeNum(); }
 
  1435 //    int edgeNum() const { return this->graph->edgeNum(); }
 
  1405   
  1436   
  1406     Node aNode(const OutEdgeIt& e) const { return tail(e); }
 
  1437     Node aNode(const OutEdgeIt& e) const { return tail(e); }
 
  1407     Node aNode(const InEdgeIt& e) const { return head(e); }
 
  1438     Node aNode(const InEdgeIt& e) const { return head(e); }
 
  1408     Node bNode(const OutEdgeIt& e) const { return head(e); }
 
  1439     Node bNode(const OutEdgeIt& e) const { return head(e); }
 
  1409     Node bNode(const InEdgeIt& e) const { return tail(e); }
 
  1440     Node bNode(const InEdgeIt& e) const { return tail(e); }
 
  1410   
  1441   
  1411 //    Node addNode() const { return Node(graph->addNode()); }
 
  1442 //    Node addNode() const { return Node(this->graph->addNode()); }
 
  1412 //    Edge addEdge(const Node& tail, const Node& head) const { 
  1443 //    Edge addEdge(const Node& tail, const Node& head) const { 
  1413 //      return Edge(graph->addEdge(tail, head)); }
 
  1444 //      return Edge(this->graph->addEdge(tail, head)); }
 
  1414 
  1445 
  1415 //    void erase(const Node& i) const { graph->erase(i); }
 
  1446 //    void erase(const Node& i) const { this->graph->erase(i); }
 
  1416 //    void erase(const Edge& i) const { graph->erase(i); }
 
  1447 //    void erase(const Edge& i) const { this->graph->erase(i); }
 
  1417   
  1448   
  1418 //    void clear() const { graph->clear(); }
 
  1449 //    void clear() const { this->graph->clear(); }
 
  1419     
  1450     
  1420     template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> { 
  1451     template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 
       
  1452       typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
 
  1421       T s_value, t_value;
 
  1453       T s_value, t_value;
 
  1422     public:
 
  1454     public:
 
  1423       NodeMap(const stGraphWrapper<Graph>& _G) :  
  1455       NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G) { }
 
  1424 	GraphWrapper<Graph>::NodeMap<T>(_G) { }
 
  1456       NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
  1425       NodeMap(const stGraphWrapper<Graph>& _G, T a) : 
  1457 						      s_value(a), 
  1426 	GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { }
 
  1458 						      t_value(a) { }
 
  1427       T operator[](const Node& n) const { 
  1459       T operator[](const Node& n) const { 
  1428 	switch (n.spec) {
 
  1460 	switch (n.spec) {
 
  1429 	  case 0: 
  1461 	  case 0: 
  1430 	    return (*this)[n];
 
  1462 	    return (*this)[n];
 
  1431 	    break;
 
  1463 	    break;
 
  1438 	}
 
  1470 	}
 
  1439       }
 
  1471       }
 
  1440       void set(const Node& n, T t) { 
  1472       void set(const Node& n, T t) { 
  1441 	switch (n.spec) {
 
  1473 	switch (n.spec) {
 
  1442 	  case 0: 
  1474 	  case 0: 
  1443 	    GraphWrapper<Graph>::NodeMap<T>::set(n, t);
 
  1475 	    GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
 
  1444 	    break;
 
  1476 	    break;
 
  1445 	  case 1:
 
  1477 	  case 1:
 
  1446 	    s_value=t;
 
  1478 	    s_value=t;
 
  1447 	    break;
 
  1479 	    break;
 
  1448 	  case 2:
 
  1480 	  case 2:
 
  1450 	    break;
 
  1482 	    break;
 
  1451 	}
 
  1483 	}
 
  1452       }
 
  1484       }
 
  1453     };
 
  1485     };
 
  1454 
  1486 
  1455     template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> { 
  1487     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
  1456       typename GraphWrapper<Graph>::NodeMap<T> node_value;
 
  1488       typedef typename Graph::template NodeMap<T> Parent;
 
  1457     public:
 
  1489       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
 
  1458       EdgeMap(const stGraphWrapper<Graph>& _G) :  
  1490     public:
 
  1459 	GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { }
 
  1491       EdgeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G), 
  1460       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : 
  1492 						  node_value(_G) { }
 
  1461 	GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { }
 
  1493       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
       
  1494 						      node_value(_G, a) { }
 
  1462       T operator[](const Edge& e) const { 
  1495       T operator[](const Edge& e) const { 
  1463 	switch (e.spec) {
 
  1496 	switch (e.spec) {
 
  1464 	  case 0: 
  1497 	  case 0: 
  1465 	    return (*this)[e];
 
  1498 	    return (*this)[e];
 
  1466 	    break;
 
  1499 	    break;
lemon-0.x