misc
authormarci
Fri, 21 May 2004 08:15:45 +0000
changeset 653c3ad7c661a49
parent 652 4dfa1f79bf3e
child 654 8fd893331298
misc
src/hugo/graph_wrapper.h
src/work/jacint/max_flow.h
     1.1 --- a/src/hugo/graph_wrapper.h	Thu May 20 17:21:55 2004 +0000
     1.2 +++ b/src/hugo/graph_wrapper.h	Fri May 21 08:15:45 2004 +0000
     1.3 @@ -1012,346 +1012,340 @@
     1.4  
     1.5  
     1.6  
     1.7 -//   ///\brief A wrapper for composing bidirected graph from a directed one. 
     1.8 -//   /// experimental, for fezso's sake.
     1.9 -//   ///
    1.10 -//   /// A wrapper for composing bidirected graph from a directed one. 
    1.11 -//   /// experimental, for fezso's sake.
    1.12 -//   /// A bidirected graph is composed over the directed one without physical 
    1.13 -//   /// storage. As the oppositely directed edges are logically different ones 
    1.14 -//   /// the maps are able to attach different values for them.
    1.15 -//   template<typename Graph>
    1.16 -//   class BidirGraphWrapper : public GraphWrapper<Graph> {
    1.17 -//   public:
    1.18 -//     typedef GraphWrapper<Graph> Parent; 
    1.19 -//   protected:
    1.20 -//     //const CapacityMap* capacity;
    1.21 -//     //FlowMap* flow;
    1.22 +  template<typename Graph>
    1.23 +  class OldBidirGraphWrapper : public GraphWrapper<Graph> {
    1.24 +  public:
    1.25 +    typedef GraphWrapper<Graph> Parent; 
    1.26 +  protected:
    1.27 +    //const CapacityMap* capacity;
    1.28 +    //FlowMap* flow;
    1.29  
    1.30 -//     BidirGraphWrapper() : GraphWrapper<Graph>()/*, 
    1.31 -// 						 capacity(0), flow(0)*/ { }
    1.32 -// //     void setCapacityMap(const CapacityMap& _capacity) {
    1.33 -// //       capacity=&_capacity;
    1.34 -// //     }
    1.35 -// //     void setFlowMap(FlowMap& _flow) {
    1.36 -// //       flow=&_flow;
    1.37 -// //     }
    1.38 -
    1.39 -//   public:
    1.40 -
    1.41 -//     BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
    1.42 -// 				     FlowMap& _flow*/) : 
    1.43 -//       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
    1.44 -
    1.45 -//     class Edge; 
    1.46 -//     class OutEdgeIt; 
    1.47 -//     friend class Edge; 
    1.48 -//     friend class OutEdgeIt; 
    1.49 -
    1.50 -//     //template<typename T> class NodeMap;    
    1.51 -//     template<typename T> class EdgeMap;
    1.52 -
    1.53 -//     typedef typename GraphWrapper<Graph>::Node Node;
    1.54 -//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    1.55 -
    1.56 -//     class Edge : public Graph::Edge {
    1.57 -//       friend class BidirGraphWrapper<Graph>;
    1.58 -//       ///\bug ez nem is kell
    1.59 -//       //template<typename T> friend class NodeMap;
    1.60 -//       template<typename T> friend class EdgeMap;
    1.61 -//     protected:
    1.62 -//       bool backward; //true, iff backward
    1.63 -// //      typename Graph::Edge e;
    1.64 -//     public:
    1.65 -//       Edge() { }
    1.66 -//       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
    1.67 -//       Edge(const typename Graph::Edge& _e, bool _backward=false) : 
    1.68 -// 	Graph::Edge(_e), backward(_backward) { }
    1.69 -//       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
    1.70 -// //the unique invalid iterator
    1.71 -//       friend bool operator==(const Edge& u, const Edge& v) { 
    1.72 -// 	return (v.backward==u.backward && 
    1.73 -// 		static_cast<typename Graph::Edge>(u)==
    1.74 -// 		static_cast<typename Graph::Edge>(v));
    1.75 -//       } 
    1.76 -//       friend bool operator!=(const Edge& u, const Edge& v) { 
    1.77 -// 	return (v.backward!=u.backward || 
    1.78 -// 		static_cast<typename Graph::Edge>(u)!=
    1.79 -// 		static_cast<typename Graph::Edge>(v));
    1.80 -//       } 
    1.81 -//     };
    1.82 -
    1.83 -//     class OutEdgeIt {
    1.84 -//       friend class BidirGraphWrapper<Graph>;
    1.85 -//     protected:
    1.86 -//       typename Graph::OutEdgeIt out;
    1.87 -//       typename Graph::InEdgeIt in;
    1.88 -//       bool backward;
    1.89 -//     public:
    1.90 -//       OutEdgeIt() { }
    1.91 -//       //FIXME
    1.92 -// //      OutEdgeIt(const Edge& e) : Edge(e) { }
    1.93 -//       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    1.94 -// //the unique invalid iterator
    1.95 -//       OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
    1.96 -// 	backward=false;
    1.97 -// 	_G.graph->first(out, v);
    1.98 -// 	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
    1.99 -// 	if (!_G.graph->valid(out)) {
   1.100 -// 	  backward=true;
   1.101 -// 	  _G.graph->first(in, v);
   1.102 -// 	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
   1.103 -// 	}
   1.104 -//       }
   1.105 -//       operator Edge() const { 
   1.106 -// //	Edge e;
   1.107 -// //	e.forward=this->forward;
   1.108 -// //	if (this->forward) e=out; else e=in;
   1.109 -// //	return e;
   1.110 -// 	if (this->backward) 
   1.111 -// 	  return Edge(in, this->backward); 
   1.112 -// 	else 
   1.113 -// 	  return Edge(out, this->backward);
   1.114 -//       }
   1.115 -//     };
   1.116 -
   1.117 -//     class InEdgeIt {
   1.118 -//       friend class BidirGraphWrapper<Graph>;
   1.119 -//     protected:
   1.120 -//       typename Graph::OutEdgeIt out;
   1.121 -//       typename Graph::InEdgeIt in;
   1.122 -//       bool backward;
   1.123 -//     public:
   1.124 -//       InEdgeIt() { }
   1.125 -//       //FIXME
   1.126 -// //      OutEdgeIt(const Edge& e) : Edge(e) { }
   1.127 -//       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   1.128 -// //the unique invalid iterator
   1.129 -//       InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
   1.130 -// 	backward=false;
   1.131 -// 	_G.graph->first(in, v);
   1.132 -// 	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
   1.133 -// 	if (!_G.graph->valid(in)) {
   1.134 -// 	  backward=true;
   1.135 -// 	  _G.graph->first(out, v);
   1.136 -// 	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
   1.137 -// 	}
   1.138 -//       }
   1.139 -//       operator Edge() const { 
   1.140 -// //	Edge e;
   1.141 -// //	e.forward=this->forward;
   1.142 -// //	if (this->forward) e=out; else e=in;
   1.143 -// //	return e;
   1.144 -// 	if (this->backward) 
   1.145 -// 	  return Edge(out, this->backward); 
   1.146 -// 	else 
   1.147 -// 	  return Edge(in, this->backward);
   1.148 -//       }
   1.149 -//     };
   1.150 -
   1.151 -//     class EdgeIt {
   1.152 -//       friend class BidirGraphWrapper<Graph>;
   1.153 -//     protected:
   1.154 -//       typename Graph::EdgeIt e;
   1.155 -//       bool backward;
   1.156 -//     public:
   1.157 -//       EdgeIt() { }
   1.158 -//       EdgeIt(const Invalid& i) : e(i), backward(true) { }
   1.159 -//       EdgeIt(const BidirGraphWrapper<Graph>& _G) { 
   1.160 -// 	backward=false;
   1.161 -// 	_G.graph->first(e);
   1.162 -// 	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
   1.163 -// 	if (!_G.graph->valid(e)) {
   1.164 -// 	  backward=true;
   1.165 -// 	  _G.graph->first(e);
   1.166 -// 	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
   1.167 -// 	}
   1.168 -//       }
   1.169 -//       operator Edge() const { 
   1.170 -// 	return Edge(e, this->backward);
   1.171 -//       }
   1.172 -//     };
   1.173 -
   1.174 -//     using GraphWrapper<Graph>::first;
   1.175 -// //     NodeIt& first(NodeIt& i) const { 
   1.176 -// //       i=NodeIt(*this); return i;
   1.177 -// //     }
   1.178 -//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   1.179 -//       i=OutEdgeIt(*this, p); return i;
   1.180 +    OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
   1.181 +						 capacity(0), flow(0)*/ { }
   1.182 +//     void setCapacityMap(const CapacityMap& _capacity) {
   1.183 +//       capacity=&_capacity;
   1.184  //     }
   1.185 -// //    FIXME not tested
   1.186 -//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   1.187 -//       i=InEdgeIt(*this, p); return i;
   1.188 -//     }
   1.189 -//     EdgeIt& first(EdgeIt& i) const { 
   1.190 -//       i=EdgeIt(*this); return i;
   1.191 -//     }
   1.192 -  
   1.193 -//     using GraphWrapper<Graph>::next;
   1.194 -// //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
   1.195 -//     OutEdgeIt& next(OutEdgeIt& e) const { 
   1.196 -//       if (!e.backward) {
   1.197 -// 	Node v=this->graph->aNode(e.out);
   1.198 -// 	this->graph->next(e.out);
   1.199 -// 	while(this->graph->valid(e.out) && !enabled(e)) { 
   1.200 -// 	  this->graph->next(e.out); }
   1.201 -// 	if (!this->graph->valid(e.out)) {
   1.202 -// 	  e.backward=true;
   1.203 -// 	  this->graph->first(e.in, v); 
   1.204 -// 	  while(this->graph->valid(e.in) && !enabled(e)) { 
   1.205 -// 	    this->graph->next(e.in); }
   1.206 -// 	}
   1.207 -//       } else {
   1.208 -// 	this->graph->next(e.in);
   1.209 -// 	while(this->graph->valid(e.in) && !enabled(e)) { 
   1.210 -// 	  this->graph->next(e.in); } 
   1.211 -//       }
   1.212 -//       return e;
   1.213 -//     }
   1.214 -// //     FIXME Not tested
   1.215 -//     InEdgeIt& next(InEdgeIt& e) const { 
   1.216 -//       if (!e.backward) {
   1.217 -// 	Node v=this->graph->aNode(e.in);
   1.218 -// 	this->graph->next(e.in);
   1.219 -// 	while(this->graph->valid(e.in) && !enabled(e)) { 
   1.220 -// 	  this->graph->next(e.in); }
   1.221 -// 	if (!this->graph->valid(e.in)) {
   1.222 -// 	  e.backward=true;
   1.223 -// 	  this->graph->first(e.out, v); 
   1.224 -// 	  while(this->graph->valid(e.out) && !enabled(e)) { 
   1.225 -// 	    this->graph->next(e.out); }
   1.226 -// 	}
   1.227 -//       } else {
   1.228 -// 	this->graph->next(e.out);
   1.229 -// 	while(this->graph->valid(e.out) && !enabled(e)) { 
   1.230 -// 	  this->graph->next(e.out); } 
   1.231 -//       }
   1.232 -//       return e;
   1.233 -//     }
   1.234 -//     EdgeIt& next(EdgeIt& e) const {
   1.235 -//       if (!e.backward) {
   1.236 -// 	this->graph->next(e.e);
   1.237 -// 	while(this->graph->valid(e.e) && !enabled(e)) { 
   1.238 -// 	  this->graph->next(e.e); }
   1.239 -// 	if (!this->graph->valid(e.e)) {
   1.240 -// 	  e.backward=true;
   1.241 -// 	  this->graph->first(e.e); 
   1.242 -// 	  while(this->graph->valid(e.e) && !enabled(e)) { 
   1.243 -// 	    this->graph->next(e.e); }
   1.244 -// 	}
   1.245 -//       } else {
   1.246 -// 	this->graph->next(e.e);
   1.247 -// 	while(this->graph->valid(e.e) && !enabled(e)) { 
   1.248 -// 	  this->graph->next(e.e); } 
   1.249 -//       }
   1.250 -//       return e;
   1.251 +//     void setFlowMap(FlowMap& _flow) {
   1.252 +//       flow=&_flow;
   1.253  //     }
   1.254  
   1.255 -//     Node tail(Edge e) const { 
   1.256 -//       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
   1.257 -//     Node head(Edge e) const { 
   1.258 -//       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
   1.259 +  public:
   1.260  
   1.261 -//     Node aNode(OutEdgeIt e) const { 
   1.262 -//       return ((!e.backward) ? this->graph->aNode(e.out) : 
   1.263 -// 	      this->graph->aNode(e.in)); }
   1.264 -//     Node bNode(OutEdgeIt e) const { 
   1.265 -//       return ((!e.backward) ? this->graph->bNode(e.out) : 
   1.266 -// 	      this->graph->bNode(e.in)); }
   1.267 +    OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
   1.268 +				     FlowMap& _flow*/) : 
   1.269 +      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
   1.270  
   1.271 -//     Node aNode(InEdgeIt e) const { 
   1.272 -//       return ((!e.backward) ? this->graph->aNode(e.in) : 
   1.273 -// 	      this->graph->aNode(e.out)); }
   1.274 -//     Node bNode(InEdgeIt e) const { 
   1.275 -//       return ((!e.backward) ? this->graph->bNode(e.in) : 
   1.276 -// 	      this->graph->bNode(e.out)); }
   1.277 +    class Edge; 
   1.278 +    class OutEdgeIt; 
   1.279 +    friend class Edge; 
   1.280 +    friend class OutEdgeIt; 
   1.281  
   1.282 -//     /// Gives back the opposite edge.
   1.283 -//     Edge opposite(const Edge& e) const { 
   1.284 -//       Edge f=e;
   1.285 -//       f.backward=!f.backward;
   1.286 -//       return f;
   1.287 +    //template<typename T> class NodeMap;    
   1.288 +    template<typename T> class EdgeMap;
   1.289 +
   1.290 +    typedef typename GraphWrapper<Graph>::Node Node;
   1.291 +    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   1.292 +
   1.293 +    class Edge : public Graph::Edge {
   1.294 +      friend class OldBidirGraphWrapper<Graph>;
   1.295 +      ///\bug ez nem is kell
   1.296 +      //template<typename T> friend class NodeMap;
   1.297 +      template<typename T> friend class EdgeMap;
   1.298 +    protected:
   1.299 +      bool backward; //true, iff backward
   1.300 +//      typename Graph::Edge e;
   1.301 +    public:
   1.302 +      Edge() { }
   1.303 +      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
   1.304 +      Edge(const typename Graph::Edge& _e, bool _backward=false) : 
   1.305 +	Graph::Edge(_e), backward(_backward) { }
   1.306 +      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
   1.307 +//the unique invalid iterator
   1.308 +      friend bool operator==(const Edge& u, const Edge& v) { 
   1.309 +	return (v.backward==u.backward && 
   1.310 +		static_cast<typename Graph::Edge>(u)==
   1.311 +		static_cast<typename Graph::Edge>(v));
   1.312 +      } 
   1.313 +      friend bool operator!=(const Edge& u, const Edge& v) { 
   1.314 +	return (v.backward!=u.backward || 
   1.315 +		static_cast<typename Graph::Edge>(u)!=
   1.316 +		static_cast<typename Graph::Edge>(v));
   1.317 +      } 
   1.318 +    };
   1.319 +
   1.320 +    class OutEdgeIt {
   1.321 +      friend class OldBidirGraphWrapper<Graph>;
   1.322 +    protected:
   1.323 +      typename Graph::OutEdgeIt out;
   1.324 +      typename Graph::InEdgeIt in;
   1.325 +      bool backward;
   1.326 +    public:
   1.327 +      OutEdgeIt() { }
   1.328 +      //FIXME
   1.329 +//      OutEdgeIt(const Edge& e) : Edge(e) { }
   1.330 +      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   1.331 +//the unique invalid iterator
   1.332 +      OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 
   1.333 +	backward=false;
   1.334 +	_G.graph->first(out, v);
   1.335 +	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
   1.336 +	if (!_G.graph->valid(out)) {
   1.337 +	  backward=true;
   1.338 +	  _G.graph->first(in, v);
   1.339 +	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
   1.340 +	}
   1.341 +      }
   1.342 +      operator Edge() const { 
   1.343 +//	Edge e;
   1.344 +//	e.forward=this->forward;
   1.345 +//	if (this->forward) e=out; else e=in;
   1.346 +//	return e;
   1.347 +	if (this->backward) 
   1.348 +	  return Edge(in, this->backward); 
   1.349 +	else 
   1.350 +	  return Edge(out, this->backward);
   1.351 +      }
   1.352 +    };
   1.353 +
   1.354 +    class InEdgeIt {
   1.355 +      friend class OldBidirGraphWrapper<Graph>;
   1.356 +    protected:
   1.357 +      typename Graph::OutEdgeIt out;
   1.358 +      typename Graph::InEdgeIt in;
   1.359 +      bool backward;
   1.360 +    public:
   1.361 +      InEdgeIt() { }
   1.362 +      //FIXME
   1.363 +//      OutEdgeIt(const Edge& e) : Edge(e) { }
   1.364 +      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   1.365 +//the unique invalid iterator
   1.366 +      InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 
   1.367 +	backward=false;
   1.368 +	_G.graph->first(in, v);
   1.369 +	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
   1.370 +	if (!_G.graph->valid(in)) {
   1.371 +	  backward=true;
   1.372 +	  _G.graph->first(out, v);
   1.373 +	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
   1.374 +	}
   1.375 +      }
   1.376 +      operator Edge() const { 
   1.377 +//	Edge e;
   1.378 +//	e.forward=this->forward;
   1.379 +//	if (this->forward) e=out; else e=in;
   1.380 +//	return e;
   1.381 +	if (this->backward) 
   1.382 +	  return Edge(out, this->backward); 
   1.383 +	else 
   1.384 +	  return Edge(in, this->backward);
   1.385 +      }
   1.386 +    };
   1.387 +
   1.388 +    class EdgeIt {
   1.389 +      friend class OldBidirGraphWrapper<Graph>;
   1.390 +    protected:
   1.391 +      typename Graph::EdgeIt e;
   1.392 +      bool backward;
   1.393 +    public:
   1.394 +      EdgeIt() { }
   1.395 +      EdgeIt(const Invalid& i) : e(i), backward(true) { }
   1.396 +      EdgeIt(const OldBidirGraphWrapper<Graph>& _G) { 
   1.397 +	backward=false;
   1.398 +	_G.graph->first(e);
   1.399 +	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
   1.400 +	if (!_G.graph->valid(e)) {
   1.401 +	  backward=true;
   1.402 +	  _G.graph->first(e);
   1.403 +	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
   1.404 +	}
   1.405 +      }
   1.406 +      operator Edge() const { 
   1.407 +	return Edge(e, this->backward);
   1.408 +      }
   1.409 +    };
   1.410 +
   1.411 +    using GraphWrapper<Graph>::first;
   1.412 +//     NodeIt& first(NodeIt& i) const { 
   1.413 +//       i=NodeIt(*this); return i;
   1.414 +//     }
   1.415 +    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   1.416 +      i=OutEdgeIt(*this, p); return i;
   1.417 +    }
   1.418 +//    FIXME not tested
   1.419 +    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
   1.420 +      i=InEdgeIt(*this, p); return i;
   1.421 +    }
   1.422 +    EdgeIt& first(EdgeIt& i) const { 
   1.423 +      i=EdgeIt(*this); return i;
   1.424 +    }
   1.425 +  
   1.426 +    using GraphWrapper<Graph>::next;
   1.427 +//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
   1.428 +    OutEdgeIt& next(OutEdgeIt& e) const { 
   1.429 +      if (!e.backward) {
   1.430 +	Node v=this->graph->aNode(e.out);
   1.431 +	this->graph->next(e.out);
   1.432 +	while(this->graph->valid(e.out) && !enabled(e)) { 
   1.433 +	  this->graph->next(e.out); }
   1.434 +	if (!this->graph->valid(e.out)) {
   1.435 +	  e.backward=true;
   1.436 +	  this->graph->first(e.in, v); 
   1.437 +	  while(this->graph->valid(e.in) && !enabled(e)) { 
   1.438 +	    this->graph->next(e.in); }
   1.439 +	}
   1.440 +      } else {
   1.441 +	this->graph->next(e.in);
   1.442 +	while(this->graph->valid(e.in) && !enabled(e)) { 
   1.443 +	  this->graph->next(e.in); } 
   1.444 +      }
   1.445 +      return e;
   1.446 +    }
   1.447 +//     FIXME Not tested
   1.448 +    InEdgeIt& next(InEdgeIt& e) const { 
   1.449 +      if (!e.backward) {
   1.450 +	Node v=this->graph->aNode(e.in);
   1.451 +	this->graph->next(e.in);
   1.452 +	while(this->graph->valid(e.in) && !enabled(e)) { 
   1.453 +	  this->graph->next(e.in); }
   1.454 +	if (!this->graph->valid(e.in)) {
   1.455 +	  e.backward=true;
   1.456 +	  this->graph->first(e.out, v); 
   1.457 +	  while(this->graph->valid(e.out) && !enabled(e)) { 
   1.458 +	    this->graph->next(e.out); }
   1.459 +	}
   1.460 +      } else {
   1.461 +	this->graph->next(e.out);
   1.462 +	while(this->graph->valid(e.out) && !enabled(e)) { 
   1.463 +	  this->graph->next(e.out); } 
   1.464 +      }
   1.465 +      return e;
   1.466 +    }
   1.467 +    EdgeIt& next(EdgeIt& e) const {
   1.468 +      if (!e.backward) {
   1.469 +	this->graph->next(e.e);
   1.470 +	while(this->graph->valid(e.e) && !enabled(e)) { 
   1.471 +	  this->graph->next(e.e); }
   1.472 +	if (!this->graph->valid(e.e)) {
   1.473 +	  e.backward=true;
   1.474 +	  this->graph->first(e.e); 
   1.475 +	  while(this->graph->valid(e.e) && !enabled(e)) { 
   1.476 +	    this->graph->next(e.e); }
   1.477 +	}
   1.478 +      } else {
   1.479 +	this->graph->next(e.e);
   1.480 +	while(this->graph->valid(e.e) && !enabled(e)) { 
   1.481 +	  this->graph->next(e.e); } 
   1.482 +      }
   1.483 +      return e;
   1.484 +    }
   1.485 +
   1.486 +    Node tail(Edge e) const { 
   1.487 +      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
   1.488 +    Node head(Edge e) const { 
   1.489 +      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
   1.490 +
   1.491 +    Node aNode(OutEdgeIt e) const { 
   1.492 +      return ((!e.backward) ? this->graph->aNode(e.out) : 
   1.493 +	      this->graph->aNode(e.in)); }
   1.494 +    Node bNode(OutEdgeIt e) const { 
   1.495 +      return ((!e.backward) ? this->graph->bNode(e.out) : 
   1.496 +	      this->graph->bNode(e.in)); }
   1.497 +
   1.498 +    Node aNode(InEdgeIt e) const { 
   1.499 +      return ((!e.backward) ? this->graph->aNode(e.in) : 
   1.500 +	      this->graph->aNode(e.out)); }
   1.501 +    Node bNode(InEdgeIt e) const { 
   1.502 +      return ((!e.backward) ? this->graph->bNode(e.in) : 
   1.503 +	      this->graph->bNode(e.out)); }
   1.504 +
   1.505 +    /// Gives back the opposite edge.
   1.506 +    Edge opposite(const Edge& e) const { 
   1.507 +      Edge f=e;
   1.508 +      f.backward=!f.backward;
   1.509 +      return f;
   1.510 +    }
   1.511 +
   1.512 +//    int nodeNum() const { return graph->nodeNum(); }
   1.513 +    //FIXME
   1.514 +    void edgeNum() const { }
   1.515 +    //int edgeNum() const { return graph->edgeNum(); }
   1.516 +
   1.517 +
   1.518 +//    int id(Node v) const { return graph->id(v); }
   1.519 +
   1.520 +    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
   1.521 +    bool valid(Edge e) const { 
   1.522 +      return this->graph->valid(e);
   1.523 +	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   1.524 +    }
   1.525 +
   1.526 +    bool forward(const Edge& e) const { return !e.backward; }
   1.527 +    bool backward(const Edge& e) const { return e.backward; }
   1.528 +
   1.529 +//     void augment(const Edge& e, Number a) const {
   1.530 +//       if (!e.backward)  
   1.531 +// // 	flow->set(e.out, flow->get(e.out)+a);
   1.532 +// 	flow->set(e, (*flow)[e]+a);
   1.533 +//       else  
   1.534 +// // 	flow->set(e.in, flow->get(e.in)-a);
   1.535 +// 	flow->set(e, (*flow)[e]-a);
   1.536  //     }
   1.537  
   1.538 -// //    int nodeNum() const { return graph->nodeNum(); }
   1.539 -//     //FIXME
   1.540 -//     void edgeNum() const { }
   1.541 -//     //int edgeNum() const { return graph->edgeNum(); }
   1.542 +    bool enabled(const Edge& e) const { 
   1.543 +      if (!e.backward) 
   1.544 +//	return (capacity->get(e.out)-flow->get(e.out)); 
   1.545 +	//return ((*capacity)[e]-(*flow)[e]);
   1.546 +	return true;
   1.547 +      else 
   1.548 +//	return (flow->get(e.in)); 
   1.549 +	//return ((*flow)[e]); 
   1.550 +	return true;
   1.551 +    }
   1.552  
   1.553 -
   1.554 -// //    int id(Node v) const { return graph->id(v); }
   1.555 -
   1.556 -//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
   1.557 -//     bool valid(Edge e) const { 
   1.558 -//       return this->graph->valid(e);
   1.559 -// 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
   1.560 +//     Number enabled(typename Graph::OutEdgeIt out) const { 
   1.561 +// //      return (capacity->get(out)-flow->get(out)); 
   1.562 +//       return ((*capacity)[out]-(*flow)[out]); 
   1.563 +//     }
   1.564 +    
   1.565 +//     Number enabled(typename Graph::InEdgeIt in) const { 
   1.566 +// //      return (flow->get(in)); 
   1.567 +//       return ((*flow)[in]); 
   1.568  //     }
   1.569  
   1.570 -//     bool forward(const Edge& e) const { return !e.backward; }
   1.571 -//     bool backward(const Edge& e) const { return e.backward; }
   1.572 +    template <typename T>
   1.573 +    class EdgeMap {
   1.574 +      typename Graph::template EdgeMap<T> forward_map, backward_map; 
   1.575 +    public:
   1.576 +      typedef T ValueType;
   1.577 +      typedef Edge KeyType;
   1.578 +      EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
   1.579 +      EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
   1.580 +      void set(Edge e, T a) { 
   1.581 +	if (!e.backward) 
   1.582 +	  forward_map.set(e/*.out*/, a); 
   1.583 +	else 
   1.584 +	  backward_map.set(e/*.in*/, a); 
   1.585 +      }
   1.586 +      T operator[](Edge e) const { 
   1.587 +	if (!e.backward) 
   1.588 +	  return forward_map[e/*.out*/]; 
   1.589 +	else 
   1.590 +	  return backward_map[e/*.in*/]; 
   1.591 +      }
   1.592 +      void update() { 
   1.593 +	forward_map.update(); 
   1.594 +	backward_map.update();
   1.595 +      }
   1.596 +//       T get(Edge e) const { 
   1.597 +// 	if (e.out_or_in) 
   1.598 +// 	  return forward_map.get(e.out); 
   1.599 +// 	else 
   1.600 +// 	  return backward_map.get(e.in); 
   1.601 +//       }
   1.602 +    };
   1.603 +  };
   1.604  
   1.605 -// //     void augment(const Edge& e, Number a) const {
   1.606 -// //       if (!e.backward)  
   1.607 -// // // 	flow->set(e.out, flow->get(e.out)+a);
   1.608 -// // 	flow->set(e, (*flow)[e]+a);
   1.609 -// //       else  
   1.610 -// // // 	flow->set(e.in, flow->get(e.in)-a);
   1.611 -// // 	flow->set(e, (*flow)[e]-a);
   1.612 -// //     }
   1.613  
   1.614 -//     bool enabled(const Edge& e) const { 
   1.615 -//       if (!e.backward) 
   1.616 -// //	return (capacity->get(e.out)-flow->get(e.out)); 
   1.617 -// 	//return ((*capacity)[e]-(*flow)[e]);
   1.618 -// 	return true;
   1.619 -//       else 
   1.620 -// //	return (flow->get(e.in)); 
   1.621 -// 	//return ((*flow)[e]); 
   1.622 -// 	return true;
   1.623 -//     }
   1.624 -
   1.625 -// //     Number enabled(typename Graph::OutEdgeIt out) const { 
   1.626 -// // //      return (capacity->get(out)-flow->get(out)); 
   1.627 -// //       return ((*capacity)[out]-(*flow)[out]); 
   1.628 -// //     }
   1.629 -    
   1.630 -// //     Number enabled(typename Graph::InEdgeIt in) const { 
   1.631 -// // //      return (flow->get(in)); 
   1.632 -// //       return ((*flow)[in]); 
   1.633 -// //     }
   1.634 -
   1.635 -//     template <typename T>
   1.636 -//     class EdgeMap {
   1.637 -//       typename Graph::template EdgeMap<T> forward_map, backward_map; 
   1.638 -//     public:
   1.639 -//       typedef T ValueType;
   1.640 -//       typedef Edge KeyType;
   1.641 -//       EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
   1.642 -//       EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
   1.643 -//       void set(Edge e, T a) { 
   1.644 -// 	if (!e.backward) 
   1.645 -// 	  forward_map.set(e/*.out*/, a); 
   1.646 -// 	else 
   1.647 -// 	  backward_map.set(e/*.in*/, a); 
   1.648 -//       }
   1.649 -//       T operator[](Edge e) const { 
   1.650 -// 	if (!e.backward) 
   1.651 -// 	  return forward_map[e/*.out*/]; 
   1.652 -// 	else 
   1.653 -// 	  return backward_map[e/*.in*/]; 
   1.654 -//       }
   1.655 -//       void update() { 
   1.656 -// 	forward_map.update(); 
   1.657 -// 	backward_map.update();
   1.658 -//       }
   1.659 -// //       T get(Edge e) const { 
   1.660 -// // 	if (e.out_or_in) 
   1.661 -// // 	  return forward_map.get(e.out); 
   1.662 -// // 	else 
   1.663 -// // 	  return backward_map.get(e.in); 
   1.664 -// //       }
   1.665 -//     };
   1.666 -//   };
   1.667  
   1.668    /// \brief A bidirected graph template.
   1.669    ///
   1.670 @@ -1376,7 +1370,6 @@
   1.671  
   1.672  
   1.673  
   1.674 -  /// An experiment for ResGraphWrapper.
   1.675    template<typename Graph, typename Number,
   1.676  	   typename CapacityMap, typename FlowMap>
   1.677    class ForwardFilter {
   1.678 @@ -1392,7 +1385,6 @@
   1.679      }
   1.680    };
   1.681  
   1.682 -  /// An experiment for ResGraphWrapper.
   1.683    template<typename Graph, typename Number,
   1.684  	   typename CapacityMap, typename FlowMap>
   1.685    class BackwardFilter {
   1.686 @@ -1408,11 +1400,13 @@
   1.687      }
   1.688    };
   1.689  
   1.690 +  
   1.691 +  /// A wrapper for composing the residual graph for directed flow and circulation problems.
   1.692  
   1.693 -  /// An experiment for ResGraphWrapper.
   1.694 +  /// A wrapper for composing the residual graph for directed flow and circulation problems.
   1.695    template<typename Graph, typename Number, 
   1.696  	   typename CapacityMap, typename FlowMap>
   1.697 -  class ExpResGraphWrapper : 
   1.698 +  class ResGraphWrapper : 
   1.699      public SubBidirGraphWrapper< 
   1.700      Graph, 
   1.701      ForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
   1.702 @@ -1428,7 +1422,7 @@
   1.703      ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
   1.704      BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
   1.705    public:
   1.706 -    ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
   1.707 +    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
   1.708  		       FlowMap& _flow) : 
   1.709        Parent(), capacity(&_capacity), flow(&_flow), 
   1.710        forward_filter(_graph, _capacity, _flow), 
   1.711 @@ -1464,77 +1458,16 @@
   1.712  
   1.713  
   1.714  
   1.715 -//   /// An experiment for ResGraphWrapper.
   1.716 -//   template<typename Graph, typename Number, 
   1.717 -// 	   typename CapacityMap, typename FlowMap>
   1.718 -//   class ExpResGraphWrapper : 
   1.719 -//     public SubGraphWrapper< BidirGraphWrapper<Graph>, 
   1.720 -// 			    ConstMap<typename BidirGraphWrapper<Graph>::Node, 
   1.721 -// 				     bool>, 
   1.722 -// 			    EdgeFilter< BidirGraphWrapper<Graph>, 
   1.723 -// 					CapacityMap, FlowMap> > {
   1.724 -//   public:
   1.725 -//     typedef SubGraphWrapper< BidirGraphWrapper<Graph>, 
   1.726 -// 			     ConstMap<typename BidirGraphWrapper<Graph>::Node, 
   1.727 -// 				      bool>, 
   1.728 -// 			     EdgeFilter< BidirGraphWrapper<Graph>, 
   1.729 -// 					 CapacityMap, FlowMap> > Parent; 
   1.730 -//   protected:
   1.731 -//     const CapacityMap* capacity;
   1.732 -//     FlowMap* flow;
   1.733 -//     BidirGraphWrapper<Graph> bidir_graph;
   1.734 -//     ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;
   1.735 -//     EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter;
   1.736 -//   public:
   1.737 -//     ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
   1.738 -// 		       FlowMap& _flow) : 
   1.739 -//       Parent(), capacity(&_capacity), flow(&_flow), 
   1.740 -//       bidir_graph(_graph), 
   1.741 -//       node_filter(true),
   1.742 -//       edge_filter(bidir_graph, *capacity, *flow) { 
   1.743 -//       Parent::setGraph(bidir_graph);
   1.744 -//       Parent::setNodeFilterMap(node_filter);
   1.745 -//       Parent::setEdgeFilterMap(edge_filter);
   1.746 -//     }
   1.747 -
   1.748 -//     //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
   1.749 -//     //bool backward(const Edge& e) const { return e.backward; }
   1.750 -
   1.751 -//     void augment(const typename Parent::Edge& e, Number a) const {
   1.752 -//       if (Parent::forward(e))  
   1.753 -// // 	flow->set(e.out, flow->get(e.out)+a);
   1.754 -// 	flow->set(e, (*flow)[e]+a);
   1.755 -//       else  
   1.756 -// // 	flow->set(e.in, flow->get(e.in)-a);
   1.757 -// 	flow->set(e, (*flow)[e]-a);
   1.758 -//     }
   1.759 -
   1.760 -//     Number resCap(const typename Parent::Edge& e) const { 
   1.761 -//       if (Parent::forward(e)) 
   1.762 -// //	return (capacity->get(e.out)-flow->get(e.out)); 
   1.763 -// 	return ((*capacity)[e]-(*flow)[e]); 
   1.764 -//       else 
   1.765 -// //	return (flow->get(e.in)); 
   1.766 -// 	return ((*flow)[e]); 
   1.767 -//     }
   1.768 -
   1.769 -//   };
   1.770 -
   1.771 -
   1.772 -
   1.773 -  /// A wrapper for composing the residual graph for directed flow and circulation problems.
   1.774 -
   1.775 -  /// A wrapper for composing the residual graph for directed flow and circulation problems.
   1.776    template<typename Graph, typename Number, 
   1.777  	   typename CapacityMap, typename FlowMap>
   1.778 -  class ResGraphWrapper : public GraphWrapper<Graph> {
   1.779 +  class OldResGraphWrapper : public GraphWrapper<Graph> {
   1.780    public:
   1.781      typedef GraphWrapper<Graph> Parent; 
   1.782    protected:
   1.783      const CapacityMap* capacity;
   1.784      FlowMap* flow;
   1.785  
   1.786 -    ResGraphWrapper() : GraphWrapper<Graph>(0), 
   1.787 +    OldResGraphWrapper() : GraphWrapper<Graph>(0), 
   1.788  			capacity(0), flow(0) { }
   1.789      void setCapacityMap(const CapacityMap& _capacity) {
   1.790        capacity=&_capacity;
   1.791 @@ -1545,7 +1478,7 @@
   1.792  
   1.793    public:
   1.794  
   1.795 -    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
   1.796 +    OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
   1.797  		    FlowMap& _flow) : 
   1.798        GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
   1.799  
   1.800 @@ -1557,7 +1490,7 @@
   1.801      typedef typename GraphWrapper<Graph>::Node Node;
   1.802      typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   1.803      class Edge : public Graph::Edge {
   1.804 -      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.805 +      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.806      protected:
   1.807        bool backward; //true, iff backward
   1.808  //      typename Graph::Edge e;
   1.809 @@ -1580,7 +1513,7 @@
   1.810      };
   1.811  
   1.812      class OutEdgeIt {
   1.813 -      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.814 +      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.815      protected:
   1.816        typename Graph::OutEdgeIt out;
   1.817        typename Graph::InEdgeIt in;
   1.818 @@ -1591,7 +1524,7 @@
   1.819  //      OutEdgeIt(const Edge& e) : Edge(e) { }
   1.820        OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   1.821  //the unique invalid iterator
   1.822 -      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
   1.823 +      OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
   1.824  	backward=false;
   1.825  	_G.graph->first(out, v);
   1.826  	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
   1.827 @@ -1614,7 +1547,7 @@
   1.828      };
   1.829  
   1.830      class InEdgeIt {
   1.831 -      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.832 +      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.833      protected:
   1.834        typename Graph::OutEdgeIt out;
   1.835        typename Graph::InEdgeIt in;
   1.836 @@ -1625,7 +1558,7 @@
   1.837  //      OutEdgeIt(const Edge& e) : Edge(e) { }
   1.838        InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
   1.839  //the unique invalid iterator
   1.840 -      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
   1.841 +      InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
   1.842  	backward=false;
   1.843  	_G.graph->first(in, v);
   1.844  	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
   1.845 @@ -1648,14 +1581,14 @@
   1.846      };
   1.847  
   1.848      class EdgeIt {
   1.849 -      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.850 +      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
   1.851      protected:
   1.852        typename Graph::EdgeIt e;
   1.853        bool backward;
   1.854      public:
   1.855        EdgeIt() { }
   1.856        EdgeIt(const Invalid& i) : e(i), backward(true) { }
   1.857 -      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
   1.858 +      EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
   1.859  	backward=false;
   1.860  	_G.graph->first(e);
   1.861  	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
   1.862 @@ -1815,8 +1748,8 @@
   1.863      public:
   1.864        typedef T ValueType;
   1.865        typedef Edge KeyType;
   1.866 -      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
   1.867 -      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
   1.868 +      EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
   1.869 +      EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
   1.870        void set(Edge e, T a) { 
   1.871  	if (!e.backward) 
   1.872  	  forward_map.set(e/*.out*/, a); 
     2.1 --- a/src/work/jacint/max_flow.h	Thu May 20 17:21:55 2004 +0000
     2.2 +++ b/src/work/jacint/max_flow.h	Fri May 21 08:15:45 2004 +0000
     2.3 @@ -63,8 +63,8 @@
     2.4      const CapMap* capacity;
     2.5      FlowMap* flow;
     2.6      int n;      //the number of nodes of G
     2.7 -    //    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
     2.8 -    typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
     2.9 +    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
    2.10 +    //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
    2.11      typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    2.12      typedef typename ResGW::Edge ResGWEdge;
    2.13      //typedef typename ResGW::template NodeMap<bool> ReachedMap;