94 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
94 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
95 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
95 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
96 |
96 |
97 int id(NodeIt v) const { return G.id(v); } |
97 int id(NodeIt v) const { return G.id(v); } |
98 |
98 |
99 template <typename ValueType> |
99 template <typename S> |
100 class NodeMap { |
100 class NodeMap { |
101 typename Graph::NodeMap<ValueType> node_map; |
101 typename Graph::NodeMap<S> node_map; |
102 public: |
102 public: |
103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { } |
104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
105 void set(NodeIt nit, ValueType a) { node_map.set(nit, a); } |
105 void set(NodeIt nit, S a) { node_map.set(nit, a); } |
106 ValueType get(NodeIt nit) const { return node_map.get(nit); } |
106 S get(NodeIt nit) const { return node_map.get(nit); } |
107 }; |
107 }; |
108 |
108 |
109 }; |
109 }; |
110 |
110 |
111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
138 |
138 |
139 typename AugGraph::NodeMap<int> free(res_graph); |
139 typename AugGraph::NodeMap<int> free(res_graph); |
140 |
140 |
141 //searching for augmenting path |
141 //searching for augmenting path |
142 while ( !res_bfs.finished() ) { |
142 while ( !res_bfs.finished() ) { |
143 //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue()); |
|
144 //while (!bfs_copy.empty()) { |
|
145 // AugOutEdgeIt e=bfs_copy.front(); |
|
146 // bfs_copy.pop(); |
|
147 // if (e.valid()) { |
|
148 // std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" "; |
|
149 // } else { |
|
150 // std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" "; |
|
151 // } |
|
152 //} |
|
153 //std::cout<<std::endl; |
|
154 AugOutEdgeIt e=AugOutEdgeIt(res_bfs); |
143 AugOutEdgeIt e=AugOutEdgeIt(res_bfs); |
155 //if (e.valid()) { |
|
156 // std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl; |
|
157 //} else { |
|
158 // std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl; |
|
159 //} |
|
160 if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
144 if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
161 NodeIt v=res_graph.tail(e); |
145 NodeIt v=res_graph.tail(e); |
162 NodeIt w=res_graph.head(e); |
146 NodeIt w=res_graph.head(e); |
163 //std::cout<<v<<"->"<<w<<std::endl; |
|
164 pred.set(w, e); |
147 pred.set(w, e); |
165 if (pred.get(v).valid()) { |
148 if (pred.get(v).valid()) { |
166 free.set(w, std::min(free.get(v), e.free())); |
149 free.set(w, std::min(free.get(v), e.free())); |
167 } else { |
150 } else { |
168 free.set(w, e.free()); |
151 free.set(w, e.free()); |
174 } //end of searching augmenting path |
157 } //end of searching augmenting path |
175 |
158 |
176 if (_augment) { |
159 if (_augment) { |
177 NodeIt n=t; |
160 NodeIt n=t; |
178 T augment_value=free.get(t); |
161 T augment_value=free.get(t); |
179 //std::cout<<"augmentation: "; |
|
180 while (pred.get(n).valid()) { |
162 while (pred.get(n).valid()) { |
181 AugEdgeIt e=pred.get(n); |
163 AugEdgeIt e=pred.get(n); |
182 e.augment(augment_value); |
164 e.augment(augment_value); |
183 //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; |
|
184 n=res_graph.tail(e); |
165 n=res_graph.tail(e); |
185 } |
166 } |
186 //std::cout<<std::endl; |
|
187 } |
167 } |
188 //std::cout << "actual flow: "<< std::endl; |
|
189 //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { |
|
190 //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
191 //} |
|
192 //std::cout<<std::endl; |
|
193 |
168 |
194 return _augment; |
169 return _augment; |
195 } |
170 } |
196 void run() { |
171 void run() { |
197 while (augment()) { } |
172 while (augment()) { } |
198 } |
173 } |
|
174 T flowValue() { |
|
175 T a=0; |
|
176 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { |
|
177 a+=flow.get(i); |
|
178 } |
|
179 return a; |
|
180 } |
199 }; |
181 }; |
200 |
182 |
201 } // namespace marci |
183 } // namespace marci |
202 |
184 |
203 #endif //EDMONDS_KARP_HH |
185 #endif //EDMONDS_KARP_HH |