Changeset 69:24c2c2989e0f in lemon0.x for src/work
 Timestamp:
 02/09/04 14:11:10 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@85
 Location:
 src/work
 Files:

 7 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r64 r69 97 97 int id(NodeIt v) const { return G.id(v); } 98 98 99 template <typename ValueType>99 template <typename S> 100 100 class NodeMap { 101 typename Graph::NodeMap< ValueType> node_map;101 typename Graph::NodeMap<S> node_map; 102 102 public: 103 103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } 104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueTypea) : node_map(_G.G, a) { }105 void set(NodeIt nit, ValueTypea) { node_map.set(nit, a); }106 ValueTypeget(NodeIt nit) const { return node_map.get(nit); }104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } 105 void set(NodeIt nit, S a) { node_map.set(nit, a); } 106 S get(NodeIt nit) const { return node_map.get(nit); } 107 107 }; 108 108 … … 141 141 //searching for augmenting path 142 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 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 144 if (e.valid() && res_bfs.isBNodeNewlyReached()) { 161 145 NodeIt v=res_graph.tail(e); 162 146 NodeIt w=res_graph.head(e); 163 //std::cout<<v<<">"<<w<<std::endl;164 147 pred.set(w, e); 165 148 if (pred.get(v).valid()) { … … 177 160 NodeIt n=t; 178 161 T augment_value=free.get(t); 179 //std::cout<<"augmentation: ";180 162 while (pred.get(n).valid()) { 181 163 AugEdgeIt e=pred.get(n); 182 164 e.augment(augment_value); 183 //std::cout<<"("<<res_graph.tail(e)<< ">"<<res_graph.head(e)<<") ";184 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 169 return _augment; … … 197 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 
src/work/list_graph.hh
r67 r69 27 27 class InEdgeIt; 28 28 class SymEdgeIt; 29 template <typename ValueType> class NodeMap;30 template <typename ValueType> class EdgeMap;29 template <typename T> class NodeMap; 30 template <typename T> class EdgeMap; 31 31 32 32 private: 33 33 34 template <typename ValueType> friend class NodeMap;35 template <typename ValueType> friend class EdgeMap;36 37 template <typename ValueType>34 template <typename T> friend class NodeMap; 35 template <typename T> friend class EdgeMap; 36 37 template <typename T> 38 38 class NodeMap { 39 39 const ListGraph& G; 40 std::vector<ValueType> container; 41 public: 42 NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { } 43 NodeMap(const ListGraph& _G, ValueType a) : 44 G(_G), container(_G.node_id, a) { } 45 void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; } 46 ValueType get(NodeIt nit) const { return container[G.id(nit)]; } 47 }; 48 49 template <typename ValueType> 40 std::vector<T> container; 41 public: 42 typedef T ValueType; 43 typedef NodeIt KeyType; 44 NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { } 45 NodeMap(const ListGraph& _G, T a) : 46 G(_G), container(G.node_id, a) { } 47 void set(NodeIt nit, T a) { container[G.id(nit)]=a; } 48 T get(NodeIt nit) const { return container[G.id(nit)]; } 49 void resize() { container.resize(G.node_id); } 50 void resize(T a) { container.resize(G.node_id, a); } 51 }; 52 53 template <typename T> 50 54 class EdgeMap { 51 55 const ListGraph& G; 52 std::vector<ValueType> container; 53 public: 54 EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { } 55 EdgeMap(const ListGraph& _G, ValueType a) : 56 G(_G), container(_G.edge_id, a) { } 57 void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; } 58 ValueType get(EdgeIt eit) const { return container[G.id(eit)]; } 56 std::vector<T> container; 57 public: 58 typedef T ValueType; 59 typedef EdgeIt KeyType; 60 EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { } 61 EdgeMap(const ListGraph& _G, T a) : 62 G(_G), container(G.edge_id, a) { } 63 void set(EdgeIt eit, T a) { container[G.id(eit)]=a; } 64 T get(EdgeIt eit) const { return container[G.id(eit)]; } 65 void resize() { container.resize(G.edge_id); } 66 void resize(T a) { container.resize(G.edge_id, a); } 59 67 }; 60 68 … … 302 310 void erase(EdgeIt e) { _delete_edge(e.edge); } 303 311 312 void clear() { 313 while (first<EachNodeIt>().valid()) erase(first<EachNodeIt>()); 314 } 315 304 316 void setTail(EdgeIt e, NodeIt tail) { 305 317 _set_tail(e.edge, tail.node); 
src/work/marci_graph_demo.cc
r60 r69 232 232 } 233 233 std::cout<<std::endl; 234 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 234 235 235 236 return 0;
Note: See TracChangeset
for help on using the changeset viewer.