Aprosagok...
1 #ifndef MARCI_MAX_FLOW_HH
2 #define MARCI_MAX_FLOW_HH
6 #include <marci_property_vector.hh>
7 #include <marci_bfs.hh>
11 template<typename graph_type, typename T>
12 class res_graph_type {
13 typedef typename graph_type::node_iterator node_iterator;
14 typedef typename graph_type::each_node_iterator each_node_iterator;
15 typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
17 edge_property_vector<graph_type, T>& flow;
18 edge_property_vector<graph_type, T>& capacity;
20 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) { }
23 friend class res_graph_type<graph_type, T>;
25 res_graph_type<graph_type, T>* resG;
26 old_sym_edge_iterator sym;
30 //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
31 // return (resG->flow.get(sym)<resG->capacity.get(sym));
33 // return (resG->flow.get(sym)>0);
37 if (resG->G.a_node(sym)==resG->G.tail(sym)) {
38 return (resG->capacity.get(sym)-resG->flow.get(sym));
40 return (resG->flow.get(sym));
43 bool valid() { return sym.valid(); }
44 void make_invalid() { sym.make_invalid(); }
46 if (resG->G.a_node(sym)==resG->G.tail(sym)) {
47 resG->flow.put(sym, resG->flow.get(sym)+a);
49 resG->flow.put(sym, resG->flow.get(sym)-a);
54 class out_edge_iterator : public edge_iterator {
56 out_edge_iterator() { }
57 out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
59 sym=resG->G.first_sym_edge(v);
60 while( sym.valid() && !(free()>0) ) { ++sym; }
62 out_edge_iterator& operator++() {
64 while( sym.valid() && !(free()>0) ) { ++sym; }
69 out_edge_iterator first_out_edge(const node_iterator& v) {
70 return out_edge_iterator(*this, v);
73 each_node_iterator first_node() {
74 return G.first_node();
77 node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
78 node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
80 int id(const node_iterator& v) { return G.id(v); }
82 //node_iterator invalid_node() { return G.invalid_node(); }
83 //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
86 template <typename graph_type, typename T>
87 struct max_flow_type {
88 typedef typename graph_type::node_iterator node_iterator;
89 typedef typename graph_type::edge_iterator edge_iterator;
90 typedef typename graph_type::each_node_iterator each_node_iterator;
91 typedef typename graph_type::out_edge_iterator out_edge_iterator;
92 typedef typename graph_type::in_edge_iterator in_edge_iterator;
96 edge_property_vector<graph_type, T> flow;
97 edge_property_vector<graph_type, T>& capacity;
99 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) {
100 for(each_node_iterator i=G.first_node(); i.valid(); ++i)
101 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
105 typedef res_graph_type<graph_type, T> aug_graph_type;
106 aug_graph_type res_graph(G, flow, capacity);
112 typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
113 bfs_queue_type bfs_queue;
114 bfs_queue.push(res_graph.first_out_edge(s));
116 typedef node_property_vector<aug_graph_type, bool> reached_type;
117 reached_type reached(res_graph, false);
118 reached.put(s, true);
120 bfs_iterator1< aug_graph_type, reached_type >
121 res_bfs(res_graph, bfs_queue, reached);
123 typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
124 pred_type pred(res_graph);
125 aug_graph_type::edge_iterator a;
129 typedef node_property_vector<aug_graph_type, int> free_type;
130 free_type free(res_graph);
132 //searching for augmenting path
133 while ( res_bfs.valid() ) {
134 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
135 if (res_bfs.newly_reached()) {
136 aug_graph_type::edge_iterator e;
138 node_iterator v=res_graph.tail(e);
139 node_iterator w=res_graph.head(e);
140 //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
142 if (pred.get(v).valid()) {
143 free.put(w, std::min(free.get(v), e.free()));
144 //std::cout <<" nem elso csucs: ";
145 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
147 free.put(w, e.free());
148 //std::cout <<" elso csucs: ";
149 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
151 //std::cout<<std::endl;
154 if (res_graph.head(res_bfs)==t) break;
157 if (reached.get(t)) {
160 T augment_value=free.get(t);
161 std::cout<<"augmentation: ";
162 while (pred.get(n).valid()) {
163 aug_graph_type::edge_iterator e=pred.get(n);
164 e.augment(augment_value);
165 std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
168 std::cout<<std::endl;
171 std::cout << "actual flow: "<< std::endl;
172 for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
173 std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
175 std::cout<<std::endl;
183 #endif //MARCI_MAX_FLOW_HH