1 #ifndef MARCI_MAX_FLOW_HH |
1 #ifndef EDMONDS_KARP_HH |
2 #define MARCI_MAX_FLOW_HH |
2 #define EDMONDS_KARP_HH |
3 |
3 |
4 #include <algorithm> |
4 #include <algorithm> |
5 |
5 |
6 #include <bfs_iterator.hh> |
6 #include <bfs_iterator.hh> |
7 |
7 |
8 namespace marci { |
8 namespace marci { |
9 |
9 |
10 template<typename Graph, typename T> |
10 template<typename Graph, typename T, typename FlowMap, typename CapacityMap> |
11 class ResGraph { |
11 class ResGraph { |
12 typedef typename Graph::NodeIt NodeIt; |
12 typedef typename Graph::NodeIt NodeIt; |
13 typedef typename Graph::EachNodeIt EachNodeIt; |
13 typedef typename Graph::EachNodeIt EachNodeIt; |
14 typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
14 typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
15 const Graph& G; |
15 const Graph& G; |
16 typename Graph::EdgeMap<T>& flow; |
16 FlowMap& flow; |
17 const typename Graph::EdgeMap<T>& capacity; |
17 const CapacityMap& capacity; |
18 public: |
18 public: |
19 ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow, |
19 ResGraph(const Graph& _G, FlowMap& _flow, |
20 const typename Graph::EdgeMap<T>& _capacity) : |
20 const CapacityMap& _capacity) : |
21 G(_G), flow(_flow), capacity(_capacity) { } |
21 G(_G), flow(_flow), capacity(_capacity) { } |
22 |
22 |
23 class EdgeIt; |
23 class EdgeIt; |
24 class OutEdgeIt; |
24 class OutEdgeIt; |
25 friend class EdgeIt; |
25 friend class EdgeIt; |
26 friend class OutEdgeIt; |
26 friend class OutEdgeIt; |
27 |
27 |
28 class EdgeIt { |
28 class EdgeIt { |
29 friend class ResGraph<Graph, T>; |
29 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; |
30 protected: |
30 protected: |
31 const ResGraph<Graph, T>* resG; |
31 const ResGraph<Graph, T, FlowMap, CapacityMap>* resG; |
32 OldSymEdgeIt sym; |
32 OldSymEdgeIt sym; |
33 public: |
33 public: |
34 EdgeIt() { } |
34 EdgeIt() { } |
35 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } |
35 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } |
36 T free() const { |
36 T free() const { |
96 |
96 |
97 int id(const NodeIt v) const { return G.id(v); } |
97 int id(const NodeIt v) const { return G.id(v); } |
98 |
98 |
99 template <typename ValueType> |
99 template <typename ValueType> |
100 class NodeMap { |
100 class NodeMap { |
101 //const ResGraph<Graph, T>& G; |
|
102 typename Graph::NodeMap<ValueType> node_map; |
101 typename Graph::NodeMap<ValueType> node_map; |
103 public: |
102 public: |
104 NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { } |
103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
105 NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { } |
104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { } |
106 void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); } |
105 void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); } |
107 ValueType get(const NodeIt nit) const { return node_map.get(nit); } |
106 ValueType get(const NodeIt nit) const { return node_map.get(nit); } |
108 }; |
107 }; |
109 |
108 |
110 }; |
109 }; |
111 |
110 |
112 template <typename Graph, typename T> |
111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
113 struct max_flow_type { |
112 class MaxFlow { |
114 typedef typename Graph::NodeIt NodeIt; |
113 typedef typename Graph::NodeIt NodeIt; |
115 typedef typename Graph::EdgeIt EdgeIt; |
114 typedef typename Graph::EdgeIt EdgeIt; |
116 typedef typename Graph::EachEdgeIt EachEdgeIt; |
115 typedef typename Graph::EachEdgeIt EachEdgeIt; |
117 typedef typename Graph::OutEdgeIt OutEdgeIt; |
116 typedef typename Graph::OutEdgeIt OutEdgeIt; |
118 typedef typename Graph::InEdgeIt InEdgeIt; |
117 typedef typename Graph::InEdgeIt InEdgeIt; |
119 const Graph& G; |
118 const Graph& G; |
120 NodeIt s; |
119 const NodeIt s; |
121 NodeIt t; |
120 const NodeIt t; |
122 typename Graph::EdgeMap<T> flow; |
121 FlowMap& flow; |
123 const typename Graph::EdgeMap<T>& capacity; |
122 const CapacityMap& capacity; |
124 |
123 typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph; |
125 max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } |
124 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
125 typedef typename AugGraph::EdgeIt AugEdgeIt; |
|
126 public: |
|
127 MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { } |
|
128 bool augment() { |
|
129 AugGraph res_graph(G, flow, capacity); |
|
130 bool _augment=false; |
|
131 |
|
132 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
133 BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
|
134 res_bfs.pushAndSetReached(s); |
|
135 |
|
136 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); |
|
137 //filled with invalid iterators |
|
138 |
|
139 typename AugGraph::NodeMap<int> free(res_graph); |
|
140 |
|
141 //searching for augmenting path |
|
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); |
|
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()) { |
|
161 NodeIt v=res_graph.tail(e); |
|
162 NodeIt w=res_graph.head(e); |
|
163 //std::cout<<v<<"->"<<w<<std::endl; |
|
164 pred.set(w, e); |
|
165 if (pred.get(v).valid()) { |
|
166 free.set(w, std::min(free.get(v), e.free())); |
|
167 } else { |
|
168 free.set(w, e.free()); |
|
169 } |
|
170 if (res_graph.head(e)==t) { _augment=true; break; } |
|
171 } |
|
172 |
|
173 ++res_bfs; |
|
174 } //end of searching augmenting path |
|
175 |
|
176 if (_augment) { |
|
177 NodeIt n=t; |
|
178 T augment_value=free.get(t); |
|
179 //std::cout<<"augmentation: "; |
|
180 while (pred.get(n).valid()) { |
|
181 AugEdgeIt e=pred.get(n); |
|
182 e.augment(augment_value); |
|
183 //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; |
|
184 n=res_graph.tail(e); |
|
185 } |
|
186 //std::cout<<std::endl; |
|
187 } |
|
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 |
|
194 return _augment; |
|
195 } |
126 void run() { |
196 void run() { |
127 typedef ResGraph<Graph, T> AugGraph; |
197 while (augment()) { } |
128 AugGraph res_graph(G, flow, capacity); |
|
129 |
|
130 bool augment; |
|
131 do { |
|
132 augment=false; |
|
133 |
|
134 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
135 typedef typename AugGraph::EdgeIt AugEdgeIt; |
|
136 typedef std::queue<AugOutEdgeIt> BfsQueue; |
|
137 BfsQueue bfs_queue; |
|
138 bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s)); |
|
139 |
|
140 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
141 ReachedMap reached(res_graph, false); |
|
142 reached.set(s, true); |
|
143 |
|
144 bfs_iterator1< AugGraph, ReachedMap > |
|
145 res_bfs(res_graph, bfs_queue, reached); |
|
146 |
|
147 typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap; |
|
148 PredMap pred(res_graph); |
|
149 //typename AugGraph::EdgeIt a; //invalid |
|
150 //a.makeInvalid(); |
|
151 //pred.set(s, a); |
|
152 |
|
153 typedef typename AugGraph::NodeMap<int> FreeMap; |
|
154 FreeMap free(res_graph); |
|
155 |
|
156 //searching for augmenting path |
|
157 while ( res_bfs.valid() ) { |
|
158 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl; |
|
159 if (res_bfs.newly_reached()) { |
|
160 AugOutEdgeIt e=AugOutEdgeIt(res_bfs); |
|
161 NodeIt v=res_graph.tail(e); |
|
162 NodeIt w=res_graph.head(e); |
|
163 //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; |
|
164 pred.set(w, e); |
|
165 if (pred.get(v).valid()) { |
|
166 free.set(w, std::min(free.get(v), e.free())); |
|
167 //std::cout <<" nem elso csucs: "; |
|
168 //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
|
169 } else { |
|
170 free.set(w, e.free()); |
|
171 //std::cout <<" elso csucs: "; |
|
172 //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
|
173 } |
|
174 //std::cout<<std::endl; |
|
175 } |
|
176 |
|
177 if (res_graph.head(res_bfs)==t) break; |
|
178 ++res_bfs; |
|
179 } //end searching augmenting path |
|
180 if (reached.get(t)) { |
|
181 augment=true; |
|
182 NodeIt n=t; |
|
183 T augment_value=free.get(t); |
|
184 std::cout<<"augmentation: "; |
|
185 while (pred.get(n).valid()) { |
|
186 AugEdgeIt e=pred.get(n); |
|
187 e.augment(augment_value); |
|
188 std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; |
|
189 n=res_graph.tail(e); |
|
190 } |
|
191 std::cout<<std::endl; |
|
192 } |
|
193 |
|
194 std::cout << "actual flow: "<< std::endl; |
|
195 for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { |
|
196 std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
197 } |
|
198 std::cout<<std::endl; |
|
199 |
|
200 } while (augment); |
|
201 } |
198 } |
202 }; |
199 }; |
203 |
200 |
204 } // namespace marci |
201 } // namespace marci |
205 |
202 |
206 #endif //MARCI_MAX_FLOW_HH |
203 #endif //EDMONDS_KARP_HH |