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

 3 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 
src/work/iterator_bfs_dfs_demo.cc
r45 r59 182 182 } 183 183 184 { 185 std::cout << "iterator bfs demo 2 ..." << std::endl; 186 //ListGraph::NodeMap<bool> reached(G, false); 187 //reached.set(s, true); 188 //std::queue<ListGraph::OutEdgeIt> bfs_queue; 189 //bfs_queue.push(G.first<OutEdgeIt>(s)); 190 BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); 191 bfs.pushAndSetReached(s); 192 while (!bfs.finished()) { 193 if (OutEdgeIt(bfs).valid()) { 194 std::cout << "OutEdgeIt: " << bfs; 195 std::cout << " aNode: " << G.aNode(bfs); 196 std::cout << " bNode: " << G.bNode(bfs) << " "; 197 } else { 198 std::cout << "OutEdgeIt: " << "invalid"; 199 std::cout << " aNode: " << G.aNode(bfs); 200 std::cout << " bNode: " << "invalid" << " "; 201 } 202 if (bfs.isBNodeNewlyReached()) { 203 std::cout << "bNodeIsNewlyReached "; 204 } else { 205 std::cout << "bNodeIsNotNewlyReached "; 206 } 207 if (bfs.isANodeExamined()) { 208 std::cout << "aNodeIsExamined "; 209 } else { 210 std::cout << "aNodeIsNotExamined "; 211 } 212 std::cout<<std::endl; 213 ++bfs; 214 } 215 } 216 217 218 184 219 185 220 { 
src/work/list_graph.hh
r46 r59 1 #ifndef MARCI_LIST_GRAPH_HH2 #define MARCI_LIST_GRAPH_HH1 #ifndef LIST_GRAPH_HH 2 #define LIST_GRAPH_HH 3 3 4 4 #include <iostream> 5 5 6 6 namespace marci { 7 8 template <typename It>9 int number_of(It _it) {10 int i=0;11 for( ; _it.valid(); ++_it) { ++i; }12 return i;13 }14 7 15 8 template <typename It> … … 21 14 22 15 class ListGraph { 16 23 17 class node_item; 24 18 class edge_item; 19 25 20 public: 21 26 22 class NodeIt; 27 23 class EachNodeIt; … … 31 27 class InEdgeIt; 32 28 class SymEdgeIt; 33 34 template <typename T> 29 template <typename ValueType> class NodeMap; 30 template <typename ValueType> class EdgeMap; 31 32 private: 33 34 template <typename ValueType> friend class NodeMap; 35 template <typename ValueType> friend class EdgeMap; 36 37 template <typename ValueType> 35 38 class NodeMap { 36 //typedef typename Graph::NodeIt NodeIt;37 //typedef typename Graph::EachNodeIt EachNodeIt;38 39 const ListGraph& G; 39 std::vector<T> container; 40 public: 41 NodeMap(const ListGraph& _G) : G(_G) { 42 int i=0; 43 for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i; 44 container.resize(i); 45 } 46 NodeMap(const ListGraph& _G, const T a) : G(_G) { 47 for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) { 48 container.push_back(a); 49 } 50 } 51 void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; } 52 T get(const NodeIt nit) const { return container[G.id(nit)]; } 53 }; 54 55 template <typename T> 40 std::vector<ValueType> container; 41 public: 42 NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { } 43 NodeMap(const ListGraph& _G, const ValueType a) : 44 G(_G), container(_G.node_id, a) { } 45 void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; } 46 ValueType get(const NodeIt nit) const { return container[G.id(nit)]; } 47 }; 48 49 template <typename ValueType> 56 50 class EdgeMap { 57 //typedef typename Graph::EdgeIt EdgeIt;58 //typedef typename Graph::EachEdgeIt EachEdgeIt;59 51 const ListGraph& G; 60 std::vector<T> container; 61 public: 62 EdgeMap(const ListGraph& _G) : G(_G) { 63 int i=0; 64 for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i; 65 container.resize(i); 66 } 67 EdgeMap(const ListGraph& _G, const T a) : G(_G) { 68 for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) { 69 container.push_back(a); 70 } 71 } 72 void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; } 73 T get(const EdgeIt eit) const { return container[G.id(eit)]; } 74 }; 75 76 //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap; 77 //template <typename T> 78 //typedef NodePropertyVector<ListGraph, T> NodeMap; 79 //template <typename T> 80 //typedef typename NodePropertyVector<ListGraph, T> NodeMap; 81 //template <typename T> 82 //typedef NodePropertyVector<typename ListGraph, T> NodeMap; 83 //template <typename T> 84 //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap; 85 //template <typename T> 86 //typedef template NodePropertyVector<ListGraph, T> NodeMap; 87 //template <typename T> 88 //typedef template typename NodePropertyVector<ListGraph, T> NodeMap; 89 //template <typename T> 90 //typedef template NodePropertyVector<typename ListGraph, T> NodeMap; 91 //template <typename T> 92 //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap; 93 //template <typename T> 94 //typedef EdgePropertyVector<ListGraph, T> EdgeMap; 95 96 private: 52 std::vector<ValueType> container; 53 public: 54 EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { } 55 EdgeMap(const ListGraph& _G, const ValueType a) : 56 G(_G), container(_G.edge_id, a) { } 57 void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; } 58 ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; } 59 }; 60 97 61 int node_id; 98 62 int edge_id; … … 114 78 friend std::ostream& operator<<(std::ostream& os, const NodeIt& i); 115 79 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i); 116 ListGraph* G;80 //ListGraph* G; 117 81 int id; 118 82 edge_item* _first_out_edge; … … 136 100 friend class SymEdgeIt; 137 101 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i); 138 ListGraph* G;102 //ListGraph* G; 139 103 int id; 140 104 node_item* _tail; … … 257 221 /* functions to construct iterators from the graph, or from each other */ 258 222 259 EachNodeIt firstNode() const { return EachNodeIt(_first_node); } 260 EachEdgeIt firstEdge() const { 261 node_item* v=_first_node; 262 edge_item* edge=v>_first_out_edge; 263 while (v && !edge) { v=v>_next_node; if (v) edge=v>_first_out_edge; } 264 return EachEdgeIt(v, edge); 265 } 223 //EachNodeIt firstNode() const { return EachNodeIt(*this); } 224 //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); } 266 225 267 226 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); } 268 InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }269 SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }227 //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); } 228 //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); } 270 229 NodeIt tail(const EdgeIt e) const { return e.tailNode(); } 271 230 NodeIt head(const EdgeIt e) const { return e.headNode(); } … … 288 247 /* for experimental purpose */ 289 248 290 void getFirst(EachNodeIt& v) const { v=EachNodeIt( _first_node); }291 void getFirst(EachEdgeIt& e) const { e= firstEdge(); }249 void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); } 250 void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); } 292 251 void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); } 293 252 void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); } … … 387 346 class EachNodeIt : public NodeIt { 388 347 friend class ListGraph; 348 protected: 349 EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { } 389 350 public: 390 351 EachNodeIt() : NodeIt() { } 391 352 EachNodeIt(node_item* v) : NodeIt(v) { } 392 EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }393 353 EachNodeIt& operator++() { node=node>_next_node; return *this; } 394 354 }; … … 423 383 class EachEdgeIt : public EdgeIt { 424 384 friend class ListGraph; 425 node_item* v; 426 public: 427 EachEdgeIt() : EdgeIt(), v(0) { } 428 EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { } 385 protected: 429 386 EachEdgeIt(const ListGraph& G) { 430 v=G._first_node;431 edge=v>_first_out_edge;387 node_item* v=G._first_node; 388 if (v) edge=v>_first_out_edge; else edge=0; 432 389 while (v && !edge) { v=v>_next_node; if (v) edge=v>_first_out_edge; } 433 390 } 391 public: 392 EachEdgeIt() : EdgeIt() { } 393 EachEdgeIt(edge_item* _e) : EdgeIt(_e) { } 434 394 EachEdgeIt& operator++() { 395 node_item* v=edge>_tail; 435 396 edge=edge>_next_out; 436 397 while (v && !edge) { v=v>_next_node; if (v) edge=v>_first_out_edge; } … … 442 403 friend class ListGraph; 443 404 node_item* v; 405 protected: 406 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v>_first_out_edge; } 444 407 public: 445 408 OutEdgeIt() : EdgeIt(), v(0) { } 446 protected:447 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v>_first_out_edge; }448 public:449 409 OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v>_first_out_edge; } 450 410 OutEdgeIt& operator++() { edge=edge>_next_out; return *this; } … … 458 418 friend class ListGraph; 459 419 node_item* v; 420 protected: 421 InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v>_first_in_edge; } 460 422 public: 461 423 InEdgeIt() : EdgeIt(), v(0) { } 462 protected:463 InEdgeIt(const NodeIt& _v) : v(_v.node) {464 edge=v>_first_in_edge;465 }466 public:467 424 InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v>_first_in_edge; } 468 425 InEdgeIt& operator++() { edge=edge>_next_in; return *this; } … … 477 434 bool out_or_in; //1 iff out, 0 iff in 478 435 node_item* v; 479 public:480 SymEdgeIt() : EdgeIt(), v(0) { }481 436 protected: 482 437 SymEdgeIt(const NodeIt& _v) : v(_v.node) { … … 486 441 } 487 442 public: 443 SymEdgeIt() : EdgeIt(), v(0) { } 488 444 SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { 489 445 out_or_in=1; … … 550 506 } //namespace marci 551 507 552 #endif // MARCI_LIST_GRAPH_HH508 #endif //LIST_GRAPH_HH
Note: See TracChangeset
for help on using the changeset viewer.