|
1 #ifndef MARCI_MAX_FLOW_HH |
|
2 #define MARCI_MAX_FLOW_HH |
|
3 |
|
4 #include <algorithm> |
|
5 |
|
6 #include <marci_property_vector.hh> |
|
7 #include <marci_bfs.hh> |
|
8 |
|
9 namespace hugo { |
|
10 |
|
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; |
|
16 graph_type& G; |
|
17 edge_property_vector<graph_type, T>& flow; |
|
18 edge_property_vector<graph_type, T>& capacity; |
|
19 public: |
|
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) { } |
|
21 |
|
22 class edge_iterator { |
|
23 friend class res_graph_type<graph_type, T>; |
|
24 protected: |
|
25 res_graph_type<graph_type, T>* resG; |
|
26 old_sym_edge_iterator sym; |
|
27 public: |
|
28 edge_iterator() { } |
|
29 //bool is_free() { |
|
30 //if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
|
31 // return (resG->flow.get(sym)<resG->capacity.get(sym)); |
|
32 //} else { |
|
33 // return (resG->flow.get(sym)>0); |
|
34 //} |
|
35 //} |
|
36 T free() { |
|
37 if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
|
38 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
|
39 } else { |
|
40 return (resG->flow.get(sym)); |
|
41 } |
|
42 } |
|
43 bool valid() { return sym.valid(); } |
|
44 void make_invalid() { sym.make_invalid(); } |
|
45 void augment(T a) { |
|
46 if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
|
47 resG->flow.put(sym, resG->flow.get(sym)+a); |
|
48 } else { |
|
49 resG->flow.put(sym, resG->flow.get(sym)-a); |
|
50 } |
|
51 } |
|
52 }; |
|
53 |
|
54 class out_edge_iterator : public edge_iterator { |
|
55 public: |
|
56 out_edge_iterator() { } |
|
57 out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { |
|
58 resG=&_resG; |
|
59 sym=resG->G.first_sym_edge(v); |
|
60 while( sym.valid() && !(free()>0) ) { ++sym; } |
|
61 } |
|
62 out_edge_iterator& operator++() { |
|
63 ++sym; |
|
64 while( sym.valid() && !(free()>0) ) { ++sym; } |
|
65 return *this; |
|
66 } |
|
67 }; |
|
68 |
|
69 out_edge_iterator first_out_edge(const node_iterator& v) { |
|
70 return out_edge_iterator(*this, v); |
|
71 } |
|
72 |
|
73 each_node_iterator first_node() { |
|
74 return G.first_node(); |
|
75 } |
|
76 |
|
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); } |
|
79 |
|
80 int id(const node_iterator& v) { return G.id(v); } |
|
81 |
|
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; } |
|
84 }; |
|
85 |
|
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; |
|
93 graph_type& G; |
|
94 node_iterator s; |
|
95 node_iterator t; |
|
96 edge_property_vector<graph_type, T> flow; |
|
97 edge_property_vector<graph_type, T>& capacity; |
|
98 |
|
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) |
|
102 flow.put(j, 0); |
|
103 } |
|
104 void run() { |
|
105 typedef res_graph_type<graph_type, T> aug_graph_type; |
|
106 aug_graph_type res_graph(G, flow, capacity); |
|
107 |
|
108 bool augment; |
|
109 do { |
|
110 augment=false; |
|
111 |
|
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)); |
|
115 |
|
116 typedef node_property_vector<aug_graph_type, bool> reached_type; |
|
117 reached_type reached(res_graph, false); |
|
118 reached.put(s, true); |
|
119 |
|
120 bfs_iterator1< aug_graph_type, reached_type > |
|
121 res_bfs(res_graph, bfs_queue, reached); |
|
122 |
|
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; |
|
126 a.make_invalid(); |
|
127 pred.put(s, a); |
|
128 |
|
129 typedef node_property_vector<aug_graph_type, int> free_type; |
|
130 free_type free(res_graph); |
|
131 |
|
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; |
|
137 e=res_bfs; |
|
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"; |
|
141 pred.put(w, e); |
|
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) << " "; |
|
146 } else { |
|
147 free.put(w, e.free()); |
|
148 //std::cout <<" elso csucs: "; |
|
149 //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
|
150 } |
|
151 //std::cout<<std::endl; |
|
152 } |
|
153 |
|
154 if (res_graph.head(res_bfs)==t) break; |
|
155 ++res_bfs; |
|
156 } |
|
157 if (reached.get(t)) { |
|
158 augment=true; |
|
159 node_iterator n=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)<<") "; |
|
166 n=res_graph.tail(e); |
|
167 } |
|
168 std::cout<<std::endl; |
|
169 } |
|
170 |
|
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)<<") "; |
|
174 } |
|
175 std::cout<<std::endl; |
|
176 |
|
177 } while (augment); |
|
178 } |
|
179 }; |
|
180 |
|
181 } // namespace hugo |
|
182 |
|
183 #endif //MARCI_MAX_FLOW_HH |