1.1 --- a/src/work/marci_max_flow.hh	Mon Jan 12 11:49:56 2004 +0000
     1.2 +++ b/src/work/marci_max_flow.hh	Mon Jan 12 11:50:52 2004 +0000
     1.3 @@ -94,40 +94,6 @@
     1.4      typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
     1.5    };
     1.6  
     1.7 -  template <typename graph_type, typename pred_type, typename free_type>
     1.8 -  struct flow_visitor {
     1.9 -    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    1.10 -    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    1.11 -    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    1.12 -    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    1.13 -    graph_type& G;
    1.14 -    pred_type& pred;
    1.15 -    free_type& free;
    1.16 -    flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
    1.17 -    void at_previously_reached(out_edge_iterator& e) { 
    1.18 -      //node_iterator v=G.tail(e);
    1.19 -      //node_iterator w=G.head(e);
    1.20 -      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
    1.21 -      //std::cout<<std::endl;
    1.22 -   }
    1.23 -    void at_newly_reached(out_edge_iterator& e) { 
    1.24 -      node_iterator v=G.tail(e);
    1.25 -      node_iterator w=G.head(e);
    1.26 -      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
    1.27 -      pred.put(w, e);
    1.28 -      if (pred.get(v).is_valid()) {
    1.29 -	free.put(w, std::min(free.get(v), e.free()));
    1.30 -	//std::cout <<" nem elso csucs: ";
    1.31 -	//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    1.32 -      } else {
    1.33 -	free.put(w, e.free()); 
    1.34 -	//std::cout <<" elso csucs: ";
    1.35 -	//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    1.36 -      }
    1.37 -      //std::cout<<std::endl;
    1.38 -    }
    1.39 -  };
    1.40 -
    1.41    template <typename graph_type, typename T>
    1.42    struct max_flow_type {
    1.43      
    1.44 @@ -152,55 +118,55 @@
    1.45        typedef res_graph_type<graph_type, T> aug_graph_type;
    1.46        aug_graph_type res_graph(G, flow, capacity);
    1.47  
    1.48 -      typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
    1.49 -      bfs_queue_type bfs_queue;
    1.50 -      //bfs_queue.push(res_graph.first_out_edge(s));
    1.51 -
    1.52 -      typedef node_property_vector<aug_graph_type, bool> reached_type;
    1.53 -      //reached_type reached(res_graph, false);
    1.54 -      reached_type reached(res_graph);
    1.55 -      //reached.put(s, true);
    1.56 -
    1.57 -      typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
    1.58 -      pred_type pred(res_graph);
    1.59 -      pred.put(s, res_graph.invalid_edge());
    1.60 -      
    1.61 -      typedef node_property_vector<aug_graph_type, int> free_type;
    1.62 -      free_type free(res_graph);
    1.63 -
    1.64 -      typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
    1.65 -      visitor_type vis(res_graph, pred, free);
    1.66 -      
    1.67 -      bfs_iterator< aug_graph_type, reached_type, visitor_type > 
    1.68 -	res_bfs(res_graph, bfs_queue, reached, vis);
    1.69 -
    1.70 -      //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { 
    1.71 -      //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
    1.72 -      //  std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
    1.73 -      //}
    1.74 -      //}
    1.75 -      //std::cout<<std::endl;
    1.76 -
    1.77 -      //char c; 
    1.78        bool augment;
    1.79        do {
    1.80  	augment=false;
    1.81 -	
    1.82 -	while (!bfs_queue.empty()) { bfs_queue.pop(); }
    1.83 +
    1.84 +	typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
    1.85 +	bfs_queue_type bfs_queue;
    1.86  	bfs_queue.push(res_graph.first_out_edge(s));
    1.87 -	
    1.88 -	for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
    1.89 +
    1.90 +	typedef node_property_vector<aug_graph_type, bool> reached_type;
    1.91 +	//reached_type reached(res_graph);
    1.92 +	//for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
    1.93 +	reached_type reached(res_graph, false);
    1.94  	reached.put(s, true); 
    1.95  	
    1.96 +	bfs_iterator1< aug_graph_type, reached_type > 
    1.97 +	res_bfs(res_graph, bfs_queue, reached);
    1.98 +
    1.99 +	typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
   1.100 +	pred_type pred(res_graph);
   1.101 +	pred.put(s, res_graph.invalid_edge());
   1.102 +
   1.103 +	typedef node_property_vector<aug_graph_type, int> free_type;
   1.104 +	free_type free(res_graph);
   1.105 +	
   1.106  	//searching for augmenting path
   1.107 -	while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { 
   1.108 -	  res_bfs.process(); 
   1.109 -	  //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
   1.110 +	while ( res_bfs.is_valid() ) { 
   1.111 +	  //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
   1.112 +	  if (res_bfs.is_newly_reached()) {
   1.113 +	    graph_traits<aug_graph_type>::edge_iterator e;
   1.114 +	    e=res_bfs;
   1.115 +	    node_iterator v=res_graph.tail(e);
   1.116 +	    node_iterator w=res_graph.head(e);
   1.117 +	    //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
   1.118 +	    pred.put(w, e);
   1.119 +	    if (pred.get(v).is_valid()) {
   1.120 +	      free.put(w, std::min(free.get(v), e.free()));
   1.121 +	      //std::cout <<" nem elso csucs: ";
   1.122 +	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
   1.123 +	    } else {
   1.124 +	      free.put(w, e.free()); 
   1.125 +	      //std::cout <<" elso csucs: ";
   1.126 +	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
   1.127 +	    }
   1.128 +	    //std::cout<<std::endl;
   1.129 +	  }
   1.130 +	
   1.131  	  if (res_graph.head(res_bfs)==t) break;
   1.132 -	  //res_bfs.next();
   1.133  	  ++res_bfs;
   1.134  	}
   1.135 -	//for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); } 
   1.136  	if (reached.get(t)) {
   1.137  	  augment=true;
   1.138  	  node_iterator n=t;
   1.139 @@ -215,7 +181,7 @@
   1.140  	  std::cout<<std::endl;
   1.141  	}
   1.142  
   1.143 -	std::cout << "max flow:"<< std::endl;
   1.144 +	std::cout << "actual flow: "<< std::endl;
   1.145  	for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { 
   1.146  	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   1.147  	}