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 }