Changeset 59:41c7f9c09a12 in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 02/04/04 13:46:33 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@74
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r43 r59 1 #ifndef MARCI_MAX_FLOW_HH2 #define MARCI_MAX_FLOW_HH1 #ifndef EDMONDS_KARP_HH 2 #define EDMONDS_KARP_HH 3 3 4 4 #include <algorithm> … … 8 8 namespace marci { 9 9 10 template<typename Graph, typename T >10 template<typename Graph, typename T, typename FlowMap, typename CapacityMap> 11 11 class ResGraph { 12 12 typedef typename Graph::NodeIt NodeIt; … … 14 14 typedef typename Graph::SymEdgeIt OldSymEdgeIt; 15 15 const Graph& G; 16 typename Graph::EdgeMap<T>& flow;17 const typename Graph::EdgeMap<T>& capacity;16 FlowMap& flow; 17 const CapacityMap& capacity; 18 18 public: 19 ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow,20 const typename Graph::EdgeMap<T>& _capacity) :19 ResGraph(const Graph& _G, FlowMap& _flow, 20 const CapacityMap& _capacity) : 21 21 G(_G), flow(_flow), capacity(_capacity) { } 22 22 … … 27 27 28 28 class EdgeIt { 29 friend class ResGraph<Graph, T >;29 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; 30 30 protected: 31 const ResGraph<Graph, T >* resG;31 const ResGraph<Graph, T, FlowMap, CapacityMap>* resG; 32 32 OldSymEdgeIt sym; 33 33 public: … … 52 52 53 53 class OutEdgeIt : public EdgeIt { 54 friend class ResGraph<Graph, T >;54 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; 55 55 public: 56 56 OutEdgeIt() { } 57 57 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } 58 58 private: 59 OutEdgeIt(const ResGraph<Graph, T >& _resG, const NodeIt v) {59 OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) { 60 60 resG=&_resG; 61 61 sym=resG>G.template first<OldSymEdgeIt>(v); … … 99 99 template <typename ValueType> 100 100 class NodeMap { 101 //const ResGraph<Graph, T>& G;102 101 typename Graph::NodeMap<ValueType> node_map; 103 102 public: 104 NodeMap(const ResGraph<Graph, T >& _G) : node_map(_G.G)/*: G(_G)*/{ }105 NodeMap(const ResGraph<Graph, T >& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/{ }103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } 104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { } 106 105 void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); } 107 106 ValueType get(const NodeIt nit) const { return node_map.get(nit); } … … 110 109 }; 111 110 112 template <typename Graph, typename T >113 struct max_flow_type{111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> 112 class MaxFlow { 114 113 typedef typename Graph::NodeIt NodeIt; 115 114 typedef typename Graph::EdgeIt EdgeIt; … … 118 117 typedef typename Graph::InEdgeIt InEdgeIt; 119 118 const Graph& G; 120 NodeIt s; 121 NodeIt t; 122 typename Graph::EdgeMap<T> flow; 123 const typename Graph::EdgeMap<T>& capacity; 124 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) { } 119 const NodeIt s; 120 const NodeIt t; 121 FlowMap& flow; 122 const CapacityMap& capacity; 123 typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph; 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 196 void run() { 127 typedef ResGraph<Graph, T> AugGraph; 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); 197 while (augment()) { } 201 198 } 202 199 }; … … 204 201 } // namespace marci 205 202 206 #endif // MARCI_MAX_FLOW_HH203 #endif //EDMONDS_KARP_HH
Note: See TracChangeset
for help on using the changeset viewer.