lemon-0.x: src/work/edmonds_karp.h@f4eb1ae59b50

     1 // -*- c++ -*-

     2 #ifndef HUGO_EDMONDS_KARP_H

     3 #define HUGO_EDMONDS_KARP_H

     5 #include <algorithm>

     6 #include <list>

     7 #include <iterator>

     9 #include <bfs_iterator.h>

    10 #include <invalid.h>

    12 namespace hugo {

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

    15   class ResGraph {

    16   public:

    17     typedef typename Graph::Node Node;

    18     typedef typename Graph::NodeIt NodeIt;

    19   private:

    20     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

    21     const Graph& G;

    22     FlowMap& flow;

    23     const CapacityMap& capacity;

    24   public:

    25     ResGraph(const Graph& _G, FlowMap& _flow,

    26 	     const CapacityMap& _capacity) :

    27       G(_G), flow(_flow), capacity(_capacity) { }

    29     class Edge;

    30     class OutEdgeIt;

    31     friend class Edge;

    32     friend class OutEdgeIt;

    34     class Edge {

    35       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    36     protected:

    37       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;

    38       OldSymEdgeIt sym;

    39     public:

    40       Edge() { }

    41       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }

    42       Number free() const {

    43 	if (resG->G.aNode(sym)==resG->G.tail(sym)) {

    44 	  return (resG->capacity.get(sym)-resG->flow.get(sym));

    45 	} else {

    46 	  return (resG->flow.get(sym));

    47 	}

    48       }

    49       bool valid() const { return sym.valid(); }

    50       void augment(Number a) const {

    51 	if (resG->G.aNode(sym)==resG->G.tail(sym)) {

    52 	  resG->flow.set(sym, resG->flow.get(sym)+a);

    53 	  //resG->flow[sym]+=a;

    54 	} else {

    55 	  resG->flow.set(sym, resG->flow.get(sym)-a);

    56 	  //resG->flow[sym]-=a;

    57 	}

    58       }

    59     };

    61     class OutEdgeIt : public Edge {

    62       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    63     public:

    64       OutEdgeIt() { }

    65       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }

    66     private:

    67       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {

    68       	resG=&_resG;

    69 	sym=resG->G.template first<OldSymEdgeIt>(v);

    70 	while( sym.valid() && !(free()>0) ) { ++sym; }

    71       }

    72     public:

    73       OutEdgeIt& operator++() {

    74 	++sym;

    75 	while( sym.valid() && !(free()>0) ) { ++sym; }

    76 	return *this;

    77       }

    78     };

    80     void /*getF*/first(OutEdgeIt& e, Node v) const {

    81       e=OutEdgeIt(*this, v);

    82     }

    83     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

    85     template< typename It >

    86     It first() const {

    87       It e;

    88       /*getF*/first(e);

    89       return e;

    90     }

    92     template< typename It >

    93     It first(Node v) const {

    94       It e;

    95       /*getF*/first(e, v);

    96       return e;

    97     }

    99     Node tail(Edge e) const { return G.aNode(e.sym); }

   100     Node head(Edge e) const { return G.bNode(e.sym); }

   102     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }

   103     Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

   105     int id(Node v) const { return G.id(v); }

   107     template <typename S>

   108     class NodeMap {

   109       typename Graph::NodeMap<S> node_map;

   110     public:

   111       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

   112       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

   113       void set(Node nit, S a) { node_map.set(nit, a); }

   114       S get(Node nit) const { return node_map.get(nit); }

   115       S& operator[](Node nit) { return node_map[nit]; }

   116       const S& operator[](Node nit) const { return node_map[nit]; }

   117     };

   119   };

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

   123   class ResGraph2 {

   124   public:

   125     typedef typename Graph::Node Node;

   126     typedef typename Graph::NodeIt NodeIt;

   127   private:

   128     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   129     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   130     typedef typename Graph::InEdgeIt OldInEdgeIt;

   132     const Graph& G;

   133     FlowMap& flow;

   134     const CapacityMap& capacity;

   135   public:

   136     ResGraph2(const Graph& _G, FlowMap& _flow,

   137 	     const CapacityMap& _capacity) :

   138       G(_G), flow(_flow), capacity(_capacity) { }

   140     class Edge;

   141     class OutEdgeIt;

   142     friend class Edge;

   143     friend class OutEdgeIt;

   145     class Edge {

   146       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   147     protected:

   148       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;

   149       //OldSymEdgeIt sym;

   150       OldOutEdgeIt out;

   151       OldInEdgeIt in;

   152       bool out_or_in; //true, iff out

   153     public:

   154       Edge() : out_or_in(true) { }

   155       Number free() const {

   156 	if (out_or_in) {

   157 	  return (resG->capacity.get(out)-resG->flow.get(out));

   158 	} else {

   159 	  return (resG->flow.get(in));

   160 	}

   161       }

   162       bool valid() const {

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

   164       void augment(Number a) const {

   165 	if (out_or_in) {

   166 	  resG->flow.set(out, resG->flow.get(out)+a);

   167 	} else {

   168 	  resG->flow.set(in, resG->flow.get(in)-a);

   169 	}

   170       }

   171     };

   173     class OutEdgeIt : public Edge {

   174       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   175     public:

   176       OutEdgeIt() { }

   177     private:

   178       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {

   179       	resG=&_resG;

   180 	out=resG->G.template first<OldOutEdgeIt>(v);

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

   182 	if (!out.valid()) {

   183 	  out_or_in=0;

   184 	  in=resG->G.template first<OldInEdgeIt>(v);

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

   186 	}

   187       }

   188     public:

   189       OutEdgeIt& operator++() {

   190 	if (out_or_in) {

   191 	  Node v=resG->G.aNode(out);

   192 	  ++out;

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

   194 	  if (!out.valid()) {

   195 	    out_or_in=0;

   196 	    in=resG->G.template first<OldInEdgeIt>(v);

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

   198 	  }

   199 	} else {

   200 	  ++in;

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

   202 	}

   203 	return *this;

   204       }

   205     };

   207     void /*getF*/first(OutEdgeIt& e, Node v) const {

   208       e=OutEdgeIt(*this, v);

   209     }

   210     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

   212     template< typename It >

   213     It first() const {

   214       It e;

   215       /*getF*/first(e);

   216       return e;

   217     }

   219     template< typename It >

   220     It first(Node v) const {

   221       It e;

   222       /*getF*/first(e, v);

   223       return e;

   224     }

   226     Node tail(Edge e) const {

   227       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }

   228     Node head(Edge e) const {

   229       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }

   231     Node aNode(OutEdgeIt e) const {

   232       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }

   233     Node bNode(OutEdgeIt e) const {

   234       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }

   236     int id(Node v) const { return G.id(v); }

   238     template <typename S>

   239     class NodeMap {

   240       typename Graph::NodeMap<S> node_map;

   241     public:

   242       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

   243       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

   244       void set(Node nit, S a) { node_map.set(nit, a); }

   245       S get(Node nit) const { return node_map.get(nit); }

   246     };

   247   };

   250   template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>

   251   class MaxFlow {

   252   public:

   253     typedef typename GraphWrapper::Node Node;

   254     typedef typename GraphWrapper::Edge Edge;

   255     typedef typename GraphWrapper::EdgeIt EdgeIt;

   256     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   257     typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   259   private:

   260     //const Graph* G;

   261     GraphWrapper gw;

   262     Node s;

   263     Node t;

   264     FlowMap* flow;

   265     const CapacityMap* capacity;

   266     typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap >

   267     AugGraph;

   268     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   269     typedef typename AugGraph::Edge AugEdge;

   271   public:

   272     MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :

   273       gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }

   274     bool augmentOnShortestPath() {

   275       AugGraph res_graph(gw, *flow, *capacity);

   276       bool _augment=false;

   278       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   279       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);

   280       res_bfs.pushAndSetReached(s);

   282       typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   283       pred.set(s, AugEdge(INVALID));

   285       typename AugGraph::NodeMap<Number> free(res_graph);

   287       //searching for augmenting path

   288       while ( !res_bfs.finished() ) {

   289 	AugOutEdgeIt e=res_bfs;

   290 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   291 	  Node v=res_graph.tail(e);

   292 	  Node w=res_graph.head(e);

   293 	  pred.set(w, e);

   294 	  if (res_graph.valid(pred.get(v))) {

   295 	    free.set(w, std::min(free.get(v), res_graph.free(e)));

   296 	  } else {

   297 	    free.set(w, res_graph.free(e));

   298 	  }

   299 	  if (res_graph.head(e)==t) { _augment=true; break; }

   300 	}

   302 	++res_bfs;

   303       } //end of searching augmenting path

   305       if (_augment) {

   306 	Node n=t;

   307 	Number augment_value=free.get(t);

   308 	while (res_graph.valid(pred.get(n))) {

   309 	  AugEdge e=pred.get(n);

   310 	  res_graph.augment(e, augment_value);

   311 	  n=res_graph.tail(e);

   312 	}

   313       }

   315       return _augment;

   316     }

   318     template<typename MapGraphWrapper>

   319     class DistanceMap {

   320     protected:

   321       MapGraphWrapper gw;

   322       typename MapGraphWrapper::NodeMap<int> dist;

   323     public:

   324       DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }

   325       void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }

   326       int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }

   327       bool get(const typename MapGraphWrapper::Edge& e) const {

   328 	return (dist.get(gw.tail(e))<dist.get(gw.head(e)));

   329       }

   330     };

   332     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   333       bool _augment=false;

   335       AugGraph res_graph(gw, *flow, *capacity);

   337       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   338       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);

   340       bfs.pushAndSetReached(s);

   341       //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's

   342       DistanceMap<AugGraph> dist(res_graph);

   343       while ( !bfs.finished() ) {

   344 	AugOutEdgeIt e=bfs;

   345 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   346 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   347 	}

   348 	++bfs;

   349       } //computing distances from s in the residual graph

   351       MutableGraph F;

   352       typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;

   353       FilterResGraph filter_res_graph(res_graph, dist);

   354       typename AugGraph::NodeMap<typename MutableGraph::Node>

   355 	res_graph_to_F(res_graph);

   356       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   357 	res_graph_to_F.set(n, F.addNode());

   358       }

   360       typename MutableGraph::Node sF=res_graph_to_F.get(s);

   361       typename MutableGraph::Node tF=res_graph_to_F.get(t);

   363       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);

   364       typename MutableGraph::EdgeMap<Number> residual_capacity(F);

   366       //Making F to the graph containing the edges of the residual graph

   367       //which are in some shortest paths

   368       for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {

   369 	//if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {

   370 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   371 	  original_edge.update();

   372 	  original_edge.set(f, e);

   373 	  residual_capacity.update();

   374 	  residual_capacity.set(f, res_graph.free(e));

   375 	  //}

   376       }

   378       bool __augment=true;

   380       while (__augment) {

   381 	__augment=false;

   382 	//computing blocking flow with dfs

   383 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;

   384 	DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);

   385 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);

   386 	pred.set(sF, typename MutableGraph::Edge(INVALID));

   387 	//invalid iterators for sources

   389 	typename MutableGraph::NodeMap<Number> free(F);

   391 	dfs.pushAndSetReached(sF);

   392 	while (!dfs.finished()) {

   393 	  ++dfs;

   394 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {

   395 	    if (dfs.isBNodeNewlyReached()) {

   396 	      typename MutableGraph::Node v=F.aNode(dfs);

   397 	      typename MutableGraph::Node w=F.bNode(dfs);

   398 	      pred.set(w, dfs);

   399 	      if (F.valid(pred.get(v))) {

   400 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));

   401 	      } else {

   402 		free.set(w, residual_capacity.get(dfs));

   403 	      }

   404 	      if (w==tF) {

   405 		__augment=true;

   406 		_augment=true;

   407 		break;

   408 	      }

   410 	    } else {

   411 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   412 	    }

   413 	  }

   414 	}

   416 	if (__augment) {

   417 	  typename MutableGraph::Node n=tF;

   418 	  Number augment_value=free.get(tF);

   419 	  while (F.valid(pred.get(n))) {

   420 	    typename MutableGraph::Edge e=pred.get(n);

   421 	    res_graph.augment(original_edge.get(e), augment_value);

   422 	    n=F.tail(e);

   423 	    if (residual_capacity.get(e)==augment_value)

   424 	      F.erase(e);

   425 	    else

   426 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   427 	  }

   428 	}

   430       }

   432       return _augment;

   433     }

   435     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   436       bool _augment=false;

   438       AugGraph res_graph(gw, *flow, *capacity);

   440       //bfs for distances on the residual graph

   441       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   442       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);

   443       bfs.pushAndSetReached(s);

   444       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's

   446       //F will contain the physical copy of the residual graph

   447       //with the set of edges which areon shortest paths

   448       MutableGraph F;

   449       typename AugGraph::NodeMap<typename MutableGraph::Node>

   450 	res_graph_to_F(res_graph);

   451       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   452 	res_graph_to_F.set(n, F.addNode());

   453       }

   454       typename MutableGraph::Node sF=res_graph_to_F.get(s);

   455       typename MutableGraph::Node tF=res_graph_to_F.get(t);

   456       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);

   457       typename MutableGraph::EdgeMap<Number> residual_capacity(F);

   459       while ( !bfs.finished() ) {

   460 	AugOutEdgeIt e=bfs;

   461 	if (res_graph.valid(e)) {

   462 	  if (bfs.isBNodeNewlyReached()) {

   463 	    dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   464 	    typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   465 	    original_edge.update();

   466 	    original_edge.set(f, e);

   467 	    residual_capacity.update();

   468 	    residual_capacity.set(f, res_graph.free(e));

   469 	  } else {

   470 	    if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {

   471 	      typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   472 	      original_edge.update();

   473 	      original_edge.set(f, e);

   474 	      residual_capacity.update();

   475 	      residual_capacity.set(f, res_graph.free(e));

   476 	    }

   477 	  }

   478 	}

   479 	++bfs;

   480       } //computing distances from s in the residual graph

   482       bool __augment=true;

   484       while (__augment) {

   485 	__augment=false;

   486 	//computing blocking flow with dfs

   487 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;

   488 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);

   489 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);

   490 	pred.set(sF, typename MutableGraph::Edge(INVALID));

   491 	//invalid iterators for sources

   493 	typename MutableGraph::NodeMap<Number> free(F);

   495 	dfs.pushAndSetReached(sF);

   496 	while (!dfs.finished()) {

   497 	  ++dfs;

   498 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {

   499 	    if (dfs.isBNodeNewlyReached()) {

   500 	      typename MutableGraph::Node v=F.aNode(dfs);

   501 	      typename MutableGraph::Node w=F.bNode(dfs);

   502 	      pred.set(w, dfs);

   503 	      if (F.valid(pred.get(v))) {

   504 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));

   505 	      } else {

   506 		free.set(w, residual_capacity.get(dfs));

   507 	      }

   508 	      if (w==tF) {

   509 		__augment=true;

   510 		_augment=true;

   511 		break;

   512 	      }

   514 	    } else {

   515 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   516 	    }

   517 	  }

   518 	}

   520 	if (__augment) {

   521 	  typename MutableGraph::Node n=tF;

   522 	  Number augment_value=free.get(tF);

   523 	  while (F.valid(pred.get(n))) {

   524 	    typename MutableGraph::Edge e=pred.get(n);

   525 	    res_graph.augment(original_edge.get(e), augment_value);

   526 	    n=F.tail(e);

   527 	    if (residual_capacity.get(e)==augment_value)

   528 	      F.erase(e);

   529 	    else

   530 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   531 	  }

   532 	}

   534       }

   536       return _augment;

   537     }

   539 //     bool augmentOnBlockingFlow2() {

   540 //       bool _augment=false;

   542 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;

   543 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;

   544 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   545 //       typedef typename EAugGraph::Edge EAugEdge;

   547 //       EAugGraph res_graph(*G, *flow, *capacity);

   549 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;

   550 //       BfsIterator5<

   551 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,

   552 // 	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/

   553 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);

   555 //       bfs.pushAndSetReached(s);

   557 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   558 // 	NodeMap<int>& dist=res_graph.dist;

   560 //       while ( !bfs.finished() ) {

   561 // 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;

   562 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   563 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   564 // 	}

   565 // 	++bfs;

   566 //       } //computing distances from s in the residual graph

   568 //       bool __augment=true;

   570 //       while (__augment) {

   572 // 	__augment=false;

   573 // 	//computing blocking flow with dfs

   574 // 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   575 // 	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >

   576 // 	  dfs(res_graph);

   577 // 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);

   578 // 	pred.set(s, EAugEdge(INVALID));

   579 // 	//invalid iterators for sources

   581 // 	typename EAugGraph::NodeMap<Number> free(res_graph);

   583 // 	dfs.pushAndSetReached(s);

   584 // 	while (!dfs.finished()) {

   585 // 	  ++dfs;

   586 // 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) {

   587 // 	    if (dfs.isBNodeNewlyReached()) {

   589 // 	      typename EAugGraph::Node v=res_graph.aNode(dfs);

   590 // 	      typename EAugGraph::Node w=res_graph.bNode(dfs);

   592 // 	      pred.set(w, EAugOutEdgeIt(dfs));

   593 // 	      if (res_graph.valid(pred.get(v))) {

   594 // 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));

   595 // 	      } else {

   596 // 		free.set(w, res_graph.free(dfs));

   597 // 	      }

   599 // 	      if (w==t) {

   600 // 		__augment=true;

   601 // 		_augment=true;

   602 // 		break;

   603 // 	      }

   604 // 	    } else {

   605 // 	      res_graph.erase(dfs);

   606 // 	    }

   607 // 	  }

   609 // 	}

   611 // 	if (__augment) {

   612 // 	  typename EAugGraph::Node n=t;

   613 // 	  Number augment_value=free.get(t);

   614 // 	  while (res_graph.valid(pred.get(n))) {

   615 // 	    EAugEdge e=pred.get(n);

   616 // 	    res_graph.augment(e, augment_value);

   617 // 	    n=res_graph.tail(e);

   618 // 	    if (res_graph.free(e)==0)

   619 // 	      res_graph.erase(e);

   620 // 	  }

   621 // 	}

   623 //       }

   625 //       return _augment;

   626 //     }

   627 //     void run() {

   628 //       //int num_of_augmentations=0;

   629 //       while (augmentOnShortestPath()) {

   630 // 	//while (augmentOnBlockingFlow<MutableGraph>()) {

   631 // 	//std::cout << ++num_of_augmentations << " ";

   632 // 	//std::cout<<std::endl;

   633 //       }

   634 //     }

   635 //     template<typename MutableGraph> void run() {

   636 //       //int num_of_augmentations=0;

   637 //       //while (augmentOnShortestPath()) {

   638 // 	while (augmentOnBlockingFlow<MutableGraph>()) {

   639 // 	//std::cout << ++num_of_augmentations << " ";

   640 // 	//std::cout<<std::endl;

   641 //       }

   642 //     }

   643     Number flowValue() {

   644       Number a=0;

   645       OutEdgeIt e;

   646       for(gw.first(e, s); gw.valid(e); gw.next(e)) {

   647 	a+=flow->get(e);

   648       }

   649       return a;

   650     }

   651   };

   654 //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   655 //   class MaxMatching {

   656 //   public:

   657 //     typedef typename Graph::Node Node;

   658 //     typedef typename Graph::NodeIt NodeIt;

   659 //     typedef typename Graph::Edge Edge;

   660 //     typedef typename Graph::EdgeIt EdgeIt;

   661 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   662 //     typedef typename Graph::InEdgeIt InEdgeIt;

   664 //     typedef typename Graph::NodeMap<bool> SMap;

   665 //     typedef typename Graph::NodeMap<bool> TMap;

   666 //   private:

   667 //     const Graph* G;

   668 //     SMap* S;

   669 //     TMap* T;

   670 //     //Node s;

   671 //     //Node t;

   672 //     FlowMap* flow;

   673 //     const CapacityMap* capacity;

   674 //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   675 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   676 //     typedef typename AugGraph::Edge AugEdge;

   677 //     typename Graph::NodeMap<int> used; //0

   679 //   public:

   680 //     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :

   681 //       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }

   682 //     bool augmentOnShortestPath() {

   683 //       AugGraph res_graph(*G, *flow, *capacity);

   684 //       bool _augment=false;

   686 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   687 //       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);

   688 //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   689 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   690 // 	if ((S->get(s)) && (used.get(s)<1) ) {

   691 // 	  //Number u=0;

   692 // 	  //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   693 // 	  //u+=flow->get(e);

   694 // 	  //if (u<1) {

   695 // 	    res_bfs.pushAndSetReached(s);

   696 // 	    pred.set(s, AugEdge(INVALID));

   697 // 	    //}

   698 // 	}

   699 //       }

   701 //       typename AugGraph::NodeMap<Number> free(res_graph);

   703 //       Node n;

   704 //       //searching for augmenting path

   705 //       while ( !res_bfs.finished() ) {

   706 // 	AugOutEdgeIt e=res_bfs;

   707 // 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {

   708 // 	  Node v=res_graph.tail(e);

   709 // 	  Node w=res_graph.head(e);

   710 // 	  pred.set(w, e);

   711 // 	  if (res_graph.valid(pred.get(v))) {

   712 // 	    free.set(w, std::min(free.get(v), res_graph.free(e)));

   713 // 	  } else {

   714 // 	    free.set(w, res_graph.free(e));

   715 // 	  }

   716 // 	  n=res_graph.head(e);

   717 // 	  if (T->get(n) && (used.get(n)<1) ) {

   718 // 	    //Number u=0;

   719 // 	    //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))

   720 // 	    //u+=flow->get(f);

   721 // 	    //if (u<1) {

   722 // 	      _augment=true;

   723 // 	      break;

   724 // 	      //}

   725 // 	  }

   726 // 	}

   728 // 	++res_bfs;

   729 //       } //end of searching augmenting path

   731 //       if (_augment) {

   732 // 	//Node n=t;

   733 // 	used.set(n, 1); //mind2 vegen jav

   734 // 	Number augment_value=free.get(n);

   735 // 	while (res_graph.valid(pred.get(n))) {

   736 // 	  AugEdge e=pred.get(n);

   737 // 	  res_graph.augment(e, augment_value);

   738 // 	  n=res_graph.tail(e);

   739 // 	}

   740 // 	used.set(n, 1); //mind2 vegen jav

   741 //       }

   743 //       return _augment;

   744 //     }

   746 // //     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   747 // //       bool _augment=false;

   749 // //       AugGraph res_graph(*G, *flow, *capacity);

   751 // //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   752 // //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);

   758 // //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   759 // //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   760 // // 	if (S->get(s)) {

   761 // // 	  Number u=0;

   762 // // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   763 // // 	    u+=flow->get(e);

   764 // // 	  if (u<1) {

   765 // // 	    res_bfs.pushAndSetReached(s);

   766 // // 	    //pred.set(s, AugEdge(INVALID));

   767 // // 	  }

   768 // // 	}

   769 // //       }

   774 // //       //bfs.pushAndSetReached(s);

   775 // //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's

   776 // //       while ( !bfs.finished() ) {

   777 // // 	AugOutEdgeIt e=bfs;

   778 // // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   779 // // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   780 // // 	}

   782 // // 	++bfs;

   783 // //       } //computing distances from s in the residual graph

   785 // //       MutableGraph F;

   786 // //       typename AugGraph::NodeMap<typename MutableGraph::Node>

   787 // // 	res_graph_to_F(res_graph);

   788 // //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   789 // // 	res_graph_to_F.set(n, F.addNode());

   790 // //       }

   792 // //       typename MutableGraph::Node sF=res_graph_to_F.get(s);

   793 // //       typename MutableGraph::Node tF=res_graph_to_F.get(t);

   795 // //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);

   796 // //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);

   798 // //       //Making F to the graph containing the edges of the residual graph

   799 // //       //which are in some shortest paths

   800 // //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {

   801 // // 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {

   802 // // 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   803 // // 	  original_edge.update();

   804 // // 	  original_edge.set(f, e);

   805 // // 	  residual_capacity.update();

   806 // // 	  residual_capacity.set(f, res_graph.free(e));

   807 // // 	}

   808 // //       }

   810 // //       bool __augment=true;

   812 // //       while (__augment) {

   813 // // 	__augment=false;

   814 // // 	//computing blocking flow with dfs

   815 // // 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

   816 // // 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);

   817 // // 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);

   818 // // 	pred.set(sF, typename MutableGraph::Edge(INVALID));

   819 // // 	//invalid iterators for sources

   821 // // 	typename MutableGraph::NodeMap<Number> free(F);

   823 // // 	dfs.pushAndSetReached(sF);

   824 // // 	while (!dfs.finished()) {

   825 // // 	  ++dfs;

   826 // // 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {

   827 // // 	    if (dfs.isBNodeNewlyReached()) {

   828 // // 	      typename MutableGraph::Node v=F.aNode(dfs);

   829 // // 	      typename MutableGraph::Node w=F.bNode(dfs);

   830 // // 	      pred.set(w, dfs);

   831 // // 	      if (F.valid(pred.get(v))) {

   832 // // 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));

   833 // // 	      } else {

   834 // // 		free.set(w, residual_capacity.get(dfs));

   835 // // 	      }

   836 // // 	      if (w==tF) {

   837 // // 		__augment=true;

   838 // // 		_augment=true;

   839 // // 		break;

   840 // // 	      }

   842 // // 	    } else {

   843 // // 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   844 // // 	    }

   845 // // 	  }

   846 // // 	}

   848 // // 	if (__augment) {

   849 // // 	  typename MutableGraph::Node n=tF;

   850 // // 	  Number augment_value=free.get(tF);

   851 // // 	  while (F.valid(pred.get(n))) {

   852 // // 	    typename MutableGraph::Edge e=pred.get(n);

   853 // // 	    res_graph.augment(original_edge.get(e), augment_value);

   854 // // 	    n=F.tail(e);

   855 // // 	    if (residual_capacity.get(e)==augment_value)

   856 // // 	      F.erase(e);

   857 // // 	    else

   858 // // 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   859 // // 	  }

   860 // // 	}

   862 // //       }

   864 // //       return _augment;

   865 // //     }

   866 //     bool augmentOnBlockingFlow2() {

   867 //       bool _augment=false;

   869 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;

   870 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;

   871 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   872 //       typedef typename EAugGraph::Edge EAugEdge;

   874 //       EAugGraph res_graph(*G, *flow, *capacity);

   876 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;

   877 //       BfsIterator5<

   878 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,

   879 // 	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/

   880 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);

   883 //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   884 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   885 // 	if (S->get(s)) {

   886 // 	  Number u=0;

   887 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   888 // 	    u+=flow->get(e);

   889 // 	  if (u<1) {

   890 // 	    bfs.pushAndSetReached(s);

   891 // 	    //pred.set(s, AugEdge(INVALID));

   892 // 	  }

   893 // 	}

   894 //       }

   897 //       //bfs.pushAndSetReached(s);

   899 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   900 // 	NodeMap<int>& dist=res_graph.dist;

   902 //       while ( !bfs.finished() ) {

   903 // 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;

   904 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   905 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   906 // 	}

   907 // 	++bfs;

   908 //       } //computing distances from s in the residual graph

   910 //       bool __augment=true;

   912 //       while (__augment) {

   914 // 	__augment=false;

   915 // 	//computing blocking flow with dfs

   916 // 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   917 // 	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >

   918 // 	  dfs(res_graph);

   919 // 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);

   920 // 	//pred.set(s, EAugEdge(INVALID));

   921 // 	//invalid iterators for sources

   923 // 	typename EAugGraph::NodeMap<Number> free(res_graph);

   926 // 	//typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   927 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   928 // 	if (S->get(s)) {

   929 // 	  Number u=0;

   930 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   931 // 	    u+=flow->get(e);

   932 // 	  if (u<1) {

   933 // 	    dfs.pushAndSetReached(s);

   934 // 	    //pred.set(s, AugEdge(INVALID));

   935 // 	  }

   936 // 	}

   937 //       }

   941 //       //dfs.pushAndSetReached(s);

   942 //       typename EAugGraph::Node n;

   943 // 	while (!dfs.finished()) {

   944 // 	  ++dfs;

   945 // 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) {

   946 // 	    if (dfs.isBNodeNewlyReached()) {

   948 // 	      typename EAugGraph::Node v=res_graph.aNode(dfs);

   949 // 	      typename EAugGraph::Node w=res_graph.bNode(dfs);

   951 // 	      pred.set(w, EAugOutEdgeIt(dfs));

   952 // 	      if (res_graph.valid(pred.get(v))) {

   953 // 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));

   954 // 	      } else {

   955 // 		free.set(w, res_graph.free(dfs));

   956 // 	      }

   958 // 	      n=w;

   959 // 	      if (T->get(w)) {

   960 // 		Number u=0;

   961 // 		for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))

   962 // 		  u+=flow->get(f);

   963 // 		if (u<1) {

   964 // 		  __augment=true;

   965 // 		  _augment=true;

   966 // 		  break;

   967 // 		}

   968 // 	      }

   969 // 	    } else {

   970 // 	      res_graph.erase(dfs);

   971 // 	    }

   972 // 	  }

   974 // 	}

   976 // 	if (__augment) {

   977 // 	  // typename EAugGraph::Node n=t;

   978 // 	  Number augment_value=free.get(n);

   979 // 	  while (res_graph.valid(pred.get(n))) {

   980 // 	    EAugEdge e=pred.get(n);

   981 // 	    res_graph.augment(e, augment_value);

   982 // 	    n=res_graph.tail(e);

   983 // 	    if (res_graph.free(e)==0)

   984 // 	      res_graph.erase(e);

   985 // 	  }

   986 // 	}

   988 //       }

   990 //       return _augment;

   991 //     }

   992 //     void run() {

   993 //       //int num_of_augmentations=0;

   994 //       while (augmentOnShortestPath()) {

   995 // 	//while (augmentOnBlockingFlow<MutableGraph>()) {

   996 // 	//std::cout << ++num_of_augmentations << " ";

   997 // 	//std::cout<<std::endl;

   998 //       }

   999 //     }

  1000 // //     template<typename MutableGraph> void run() {

  1001 // //       //int num_of_augmentations=0;

  1002 // //       //while (augmentOnShortestPath()) {

  1003 // // 	while (augmentOnBlockingFlow<MutableGraph>()) {

  1004 // // 	//std::cout << ++num_of_augmentations << " ";

  1005 // // 	//std::cout<<std::endl;

  1006 // //       }

  1007 // //     }

  1008 //     Number flowValue() {

  1009 //       Number a=0;

  1010 //       EdgeIt e;

  1011 //       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {

  1012 // 	a+=flow->get(e);

  1013 //       }

  1014 //       return a;

  1015 //     }

  1016 //   };

  1023 // //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1024 // //   class MaxFlow2 {

  1025 // //   public:

  1026 // //     typedef typename Graph::Node Node;

  1027 // //     typedef typename Graph::Edge Edge;

  1028 // //     typedef typename Graph::EdgeIt EdgeIt;

  1029 // //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1030 // //     typedef typename Graph::InEdgeIt InEdgeIt;

  1031 // //   private:

  1032 // //     const Graph& G;

  1033 // //     std::list<Node>& S;

  1034 // //     std::list<Node>& T;

  1035 // //     FlowMap& flow;

  1036 // //     const CapacityMap& capacity;

  1037 // //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

  1038 // //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

  1039 // //     typedef typename AugGraph::Edge AugEdge;

  1040 // //     typename Graph::NodeMap<bool> SMap;

  1041 // //     typename Graph::NodeMap<bool> TMap;

  1042 // //   public:

  1043 // //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {

  1044 // //       for(typename std::list<Node>::const_iterator i=S.begin();

  1045 // // 	  i!=S.end(); ++i) {

  1046 // // 	SMap.set(*i, true);

  1047 // //       }

  1048 // //       for (typename std::list<Node>::const_iterator i=T.begin();

  1049 // // 	   i!=T.end(); ++i) {

  1050 // // 	TMap.set(*i, true);

  1051 // //       }

  1052 // //     }

  1053 // //     bool augment() {

  1054 // //       AugGraph res_graph(G, flow, capacity);

  1055 // //       bool _augment=false;

  1056 // //       Node reached_t_node;

  1058 // //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

  1059 // //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);

  1060 // //       for(typename std::list<Node>::const_iterator i=S.begin();

  1061 // // 	  i!=S.end(); ++i) {

  1062 // // 	res_bfs.pushAndSetReached(*i);

  1063 // //       }

  1064 // //       //res_bfs.pushAndSetReached(s);

  1066 // //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);

  1067 // //       //filled up with invalid iterators

  1069 // //       typename AugGraph::NodeMap<Number> free(res_graph);

  1071 // //       //searching for augmenting path

  1072 // //       while ( !res_bfs.finished() ) {

  1073 // // 	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);

  1074 // // 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

  1075 // // 	  Node v=res_graph.tail(e);

  1076 // // 	  Node w=res_graph.head(e);

  1077 // // 	  pred.set(w, e);

  1078 // // 	  if (pred.get(v).valid()) {

  1079 // // 	    free.set(w, std::min(free.get(v), e.free()));

  1080 // // 	  } else {

  1081 // // 	    free.set(w, e.free());

  1082 // // 	  }

  1083 // // 	  if (TMap.get(res_graph.head(e))) {

  1084 // // 	    _augment=true;

  1085 // // 	    reached_t_node=res_graph.head(e);

  1086 // // 	    break;

  1087 // // 	  }

  1088 // // 	}

  1090 // // 	++res_bfs;

  1091 // //       } //end of searching augmenting path

  1093 // //       if (_augment) {

  1094 // // 	Node n=reached_t_node;

  1095 // // 	Number augment_value=free.get(reached_t_node);

  1096 // // 	while (pred.get(n).valid()) {

  1097 // // 	  AugEdge e=pred.get(n);

  1098 // // 	  e.augment(augment_value);

  1099 // // 	  n=res_graph.tail(e);

  1100 // // 	}

  1101 // //       }

  1103 // //       return _augment;

  1104 // //     }

  1105 // //     void run() {

  1106 // //       while (augment()) { }

  1107 // //     }

  1108 // //     Number flowValue() {

  1109 // //       Number a=0;

  1110 // //       for(typename std::list<Node>::const_iterator i=S.begin();

  1111 // // 	  i!=S.end(); ++i) {

  1112 // // 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {

  1113 // // 	  a+=flow.get(e);

  1114 // // 	}

  1115 // // 	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {

  1116 // // 	  a-=flow.get(e);

  1117 // // 	}

  1118 // //       }

  1119 // //       return a;

  1120 // //     }

  1121 // //   };

  1124 } // namespace hugo

  1126 #endif //HUGO_EDMONDS_KARP_H

author	marci
	Tue, 30 Mar 2004 17:47:51 +0000
changeset 268	f4eb1ae59b50
parent 266	4cec4981dfd1
child 269	07af3069c0b8
permissions	-rw-r--r--