1 #ifndef MARCI_MAX_FLOW_HH
2 #define MARCI_MAX_FLOW_HH
6 #include <marci_graph_traits.hh>
7 #include <marci_property_vector.hh>
8 #include <marci_bfs.hh>
12 template<typename graph_type, typename T>
13 class res_graph_type {
14 typedef typename graph_traits<graph_type>::node_iterator node_iterator;
15 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
16 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
17 typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
20 edge_property_vector<graph_type, T>& flow;
21 edge_property_vector<graph_type, T>& capacity;
23 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) { }
26 friend class res_graph_type<graph_type, T>;
28 res_graph_type<graph_type, T>* resG;
29 sym_edge_iterator sym;
33 //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
34 // return (resG->flow.get(sym)<resG->capacity.get(sym));
36 // return (resG->flow.get(sym)>0);
40 if (resG->G.a_node(sym)==resG->G.tail(sym)) {
41 return (resG->capacity.get(sym)-resG->flow.get(sym));
43 return (resG->flow.get(sym));
46 bool is_valid() { return sym.is_valid(); }
48 if (resG->G.a_node(sym)==resG->G.tail(sym)) {
49 resG->flow.put(sym, resG->flow.get(sym)+a);
51 resG->flow.put(sym, resG->flow.get(sym)-a);
56 class res_out_edge_it : public res_edge_it {
59 res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
61 sym=resG->G.first_sym_edge(v);
62 while( sym.is_valid() && !(free()>0) ) { ++sym; }
64 res_out_edge_it& operator++() {
66 while( sym.is_valid() && !(free()>0) ) { ++sym; }
71 res_out_edge_it first_out_edge(const node_iterator& v) {
72 return res_out_edge_it(*this, v);
75 each_node_iterator first_node() {
76 return G.first_node();
79 node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
80 node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
82 int id(const node_iterator& v) { return G.id(v); }
84 node_iterator invalid_node() { return G.invalid_node(); }
85 res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
89 template <typename graph_type, typename T>
90 struct graph_traits< res_graph_type<graph_type, T> > {
91 typedef typename graph_traits<graph_type>::node_iterator node_iterator;
92 typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
93 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
94 typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
97 template <typename graph_type, typename T>
98 struct max_flow_type {
100 typedef typename graph_traits<graph_type>::node_iterator node_iterator;
101 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
102 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
103 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
104 typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
109 edge_property_vector<graph_type, T> flow;
110 edge_property_vector<graph_type, T>& capacity;
112 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) {
113 for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
114 for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
118 typedef res_graph_type<graph_type, T> aug_graph_type;
119 aug_graph_type res_graph(G, flow, capacity);
125 typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
126 bfs_queue_type bfs_queue;
127 bfs_queue.push(res_graph.first_out_edge(s));
129 typedef node_property_vector<aug_graph_type, bool> reached_type;
130 //reached_type reached(res_graph);
131 //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
132 reached_type reached(res_graph, false);
133 reached.put(s, true);
135 bfs_iterator1< aug_graph_type, reached_type >
136 res_bfs(res_graph, bfs_queue, reached);
138 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
139 pred_type pred(res_graph);
140 pred.put(s, res_graph.invalid_edge());
142 typedef node_property_vector<aug_graph_type, int> free_type;
143 free_type free(res_graph);
145 //searching for augmenting path
146 while ( res_bfs.is_valid() ) {
147 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
148 if (res_bfs.is_newly_reached()) {
149 graph_traits<aug_graph_type>::edge_iterator e;
151 node_iterator v=res_graph.tail(e);
152 node_iterator w=res_graph.head(e);
153 //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
155 if (pred.get(v).is_valid()) {
156 free.put(w, std::min(free.get(v), e.free()));
157 //std::cout <<" nem elso csucs: ";
158 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
160 free.put(w, e.free());
161 //std::cout <<" elso csucs: ";
162 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
164 //std::cout<<std::endl;
167 if (res_graph.head(res_bfs)==t) break;
170 if (reached.get(t)) {
173 T augment_value=free.get(t);
174 std::cout<<"augmentation: ";
175 while (pred.get(n).is_valid()) {
176 graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
177 e.augment(augment_value);
178 std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
181 std::cout<<std::endl;
184 std::cout << "actual flow: "<< std::endl;
185 for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
186 std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
188 std::cout<<std::endl;
196 #endif //MARCI_MAX_FLOW_HH