diff -r be43902fadb7 -r 19f3943521ab src/work/marci_max_flow.hh
--- a/src/work/marci_max_flow.hh	Sat Apr 03 14:22:33 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,183 +0,0 @@
-#ifndef MARCI_MAX_FLOW_HH
-#define MARCI_MAX_FLOW_HH
-
-#include <algorithm>
-
-#include <marci_property_vector.hh>
-#include <marci_bfs.hh>
-
-namespace hugo {
-
-  template<typename graph_type, typename T>
-  class res_graph_type { 
-    typedef typename graph_type::node_iterator node_iterator;
-    typedef typename graph_type::each_node_iterator each_node_iterator;
-    typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
-    graph_type& G;
-    edge_property_vector<graph_type, T>& flow;
-    edge_property_vector<graph_type, T>& capacity;
-  public:
-    res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { }
-
-    class edge_iterator {
-      friend class res_graph_type<graph_type, T>;
-    protected:
-      res_graph_type<graph_type, T>* resG;
-      old_sym_edge_iterator sym;
-    public:
-      edge_iterator() { }
-      //bool is_free() {  
-      //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
-      //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 
-      //} else { 
-      //  return (resG->flow.get(sym)>0); 
-      //}
-      //}
-      T free() { 
-	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
-	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
-	} else { 
-	  return (resG->flow.get(sym)); 
-	}
-      }
-      bool valid() { return sym.valid(); }
-      void make_invalid() { sym.make_invalid(); }
-      void augment(T a) {
-	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
-	  resG->flow.put(sym, resG->flow.get(sym)+a);
-	} else { 
-	  resG->flow.put(sym, resG->flow.get(sym)-a);
-	}
-      }
-    };
-
-    class out_edge_iterator : public edge_iterator {
-    public:
-      out_edge_iterator() { }
-      out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 
-      	resG=&_resG;
-	sym=resG->G.first_sym_edge(v);
-	while( sym.valid() && !(free()>0) ) { ++sym; }
-      }
-      out_edge_iterator& operator++() { 
-	++sym; 
-	while( sym.valid() && !(free()>0) ) { ++sym; }
-	return *this; 
-      }
-    };
-
-    out_edge_iterator first_out_edge(const node_iterator& v) {
-      return out_edge_iterator(*this, v);
-    }
-
-    each_node_iterator first_node() {
-      return G.first_node();
-    }
-
-    node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
-    node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
-
-    int id(const node_iterator& v) { return G.id(v); }
-
-    //node_iterator invalid_node() { return G.invalid_node(); }
-    //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } 
-  };
-
-  template <typename graph_type, typename T>
-  struct max_flow_type {
-    typedef typename graph_type::node_iterator node_iterator;
-    typedef typename graph_type::edge_iterator edge_iterator;
-    typedef typename graph_type::each_node_iterator each_node_iterator;
-    typedef typename graph_type::out_edge_iterator out_edge_iterator;
-    typedef typename graph_type::in_edge_iterator in_edge_iterator;
-    graph_type& G;
-    node_iterator s;
-    node_iterator t;
-    edge_property_vector<graph_type, T> flow;
-    edge_property_vector<graph_type, T>& capacity;
-
-    max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 
-      for(each_node_iterator i=G.first_node(); i.valid(); ++i) 
-	for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) 
-	  flow.put(j, 0);
-    }
-    void run() {
-      typedef res_graph_type<graph_type, T> aug_graph_type;
-      aug_graph_type res_graph(G, flow, capacity);
-
-      bool augment;
-      do {
-	augment=false;
-
-	typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
-	bfs_queue_type bfs_queue;
-	bfs_queue.push(res_graph.first_out_edge(s));
-
-	typedef node_property_vector<aug_graph_type, bool> reached_type;
-	reached_type reached(res_graph, false);
-	reached.put(s, true); 
-	
-	bfs_iterator1< aug_graph_type, reached_type > 
-	res_bfs(res_graph, bfs_queue, reached);
-
-	typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
-	pred_type pred(res_graph);
-	aug_graph_type::edge_iterator a; 
-	a.make_invalid();
-	pred.put(s, a);
-
-	typedef node_property_vector<aug_graph_type, int> free_type;
-	free_type free(res_graph);
-	
-	//searching for augmenting path
-	while ( res_bfs.valid() ) { 
-	  //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
-	  if (res_bfs.newly_reached()) {
-	    aug_graph_type::edge_iterator e;
-	    e=res_bfs;
-	    node_iterator v=res_graph.tail(e);
-	    node_iterator w=res_graph.head(e);
-	    //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
-	    pred.put(w, e);
-	    if (pred.get(v).valid()) {
-	      free.put(w, std::min(free.get(v), e.free()));
-	      //std::cout <<" nem elso csucs: ";
-	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-	    } else {
-	      free.put(w, e.free()); 
-	      //std::cout <<" elso csucs: ";
-	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-	    }
-	    //std::cout<<std::endl;
-	  }
-	
-	  if (res_graph.head(res_bfs)==t) break;
-	  ++res_bfs;
-	}
-	if (reached.get(t)) {
-	  augment=true;
-	  node_iterator n=t;
-	  T augment_value=free.get(t);
-	  std::cout<<"augmentation: ";
-	  while (pred.get(n).valid()) { 
-	    aug_graph_type::edge_iterator e=pred.get(n);
-	    e.augment(augment_value); 
-	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
-	    n=res_graph.tail(e);
-	  }
-	  std::cout<<std::endl;
-	}
-
-	std::cout << "actual flow: "<< std::endl;
-	for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) { 
-	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-	}
-	std::cout<<std::endl;
-
-      } while (augment);
-    }
-  };
-
-} // namespace hugo
-
-#endif //MARCI_MAX_FLOW_HH