Changeset 331:f5461f8bc59b in lemon0.x
 Timestamp:
 04/15/04 19:03:44 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@449
 Location:
 src/work/athos
 Files:

 1 added
 1 deleted
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/makefile
r322 r331 7 7 INCLUDEDIRS ?= I../../include I.. I../{marci,jacint,alpar,athos,akos,klao} #I$(BOOSTROOT) 8 8 #LEDAINCLUDE ?= I$(LEDAROOT)/incl 9 CXXFLAGS = g  W Wall $(INCLUDEDIRS) ansi pedantic9 CXXFLAGS = g O W Wall $(INCLUDEDIRS) ansi pedantic 10 10 11 11 #LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 
src/work/athos/pf_demo.cc
r201 r331 3 3 #include <string> 4 4 5 #include "list_graph.h h"6 #include "marci_graph_traits.hh"5 #include "list_graph.h" 6 //#include "marci_graph_traits.hh" 7 7 //#include "marci_property_vector.hh" 8 8 #include "preflow_push.hh" … … 14 14 { 15 15 16 17 typedef ListGraph::NodeIt NodeIt; 18 typedef ListGraph::EdgeIt EdgeIt; 19 /* 20 typedef ListGraph::EachNodeIt EachNodeIt; 21 typedef ListGraph::EachEdgeIt EachEdgeIt; 22 typedef ListGraph::OutEdgeIt OutEdgeIt; 23 typedef ListGraph::InEdgeIt InEdgeIt; 24 typedef ListGraph::SymEdgeIt SymEdgeIt; 25 */ 26 ListGraph flowG; 16 typedef ListGraph::Node Node; 17 typedef ListGraph::Edge Edge; 18 19 ListGraph graph; 27 20 28 21 /* … … 30 23 31 24 32 NodeIt s= flowG.addNode();33 NodeIt v1= flowG.addNode();34 NodeIt v2= flowG.addNode();35 NodeIt v3= flowG.addNode();36 NodeIt v4= flowG.addNode();37 NodeIt t= flowG.addNode();25 NodeIt s=graph.addNode(); 26 NodeIt v1=graph.addNode(); 27 NodeIt v2=graph.addNode(); 28 NodeIt v3=graph.addNode(); 29 NodeIt v4=graph.addNode(); 30 NodeIt t=graph.addNode(); 38 31 39 32 40 EdgeIt s_v1= flowG.addEdge(s, v1);41 EdgeIt s_v2= flowG.addEdge(s, v2);42 EdgeIt v1_v2= flowG.addEdge(v1, v2);43 EdgeIt v2_v1= flowG.addEdge(v2, v1);44 EdgeIt v1_v3= flowG.addEdge(v1, v3);45 EdgeIt v3_v2= flowG.addEdge(v3, v2);46 EdgeIt v2_v4= flowG.addEdge(v2, v4);47 EdgeIt v4_v3= flowG.addEdge(v4, v3);48 EdgeIt v3_t= flowG.addEdge(v3, t);49 EdgeIt v4_t= flowG.addEdge(v4, t);33 EdgeIt s_v1=graph.addEdge(s, v1); 34 EdgeIt s_v2=graph.addEdge(s, v2); 35 EdgeIt v1_v2=graph.addEdge(v1, v2); 36 EdgeIt v2_v1=graph.addEdge(v2, v1); 37 EdgeIt v1_v3=graph.addEdge(v1, v3); 38 EdgeIt v3_v2=graph.addEdge(v3, v2); 39 EdgeIt v2_v4=graph.addEdge(v2, v4); 40 EdgeIt v4_v3=graph.addEdge(v4, v3); 41 EdgeIt v3_t=graph.addEdge(v3, t); 42 EdgeIt v4_t=graph.addEdge(v4, t); 50 43 51 ListGraph::EdgeMap<int> cap(flowG);44 ListGraph::EdgeMap<int> length(graph); 52 45 53 cap.set(s_v1, 16);54 cap.set(s_v2, 13);55 cap.set(v1_v2, 10);56 cap.set(v2_v1, 4);57 cap.set(v1_v3, 12);58 cap.set(v3_v2, 9);59 cap.set(v2_v4, 14);60 cap.set(v4_v3, 7);61 cap.set(v3_t, 20);62 cap.set(v4_t, 4);46 length.set(s_v1, 16); 47 length.set(s_v2, 13); 48 length.set(v1_v2, 10); 49 length.set(v2_v1, 4); 50 length.set(v1_v3, 12); 51 length.set(v3_v2, 9); 52 length.set(v2_v4, 14); 53 length.set(v4_v3, 7); 54 length.set(v3_t, 20); 55 length.set(v4_t, 4); 63 56 */ 64 57 … … 66 59 //Ahuja könyv példája 67 60 68 Node It s=flowG.addNode();69 Node It v2=flowG.addNode();70 Node It v3=flowG.addNode();71 Node It v4=flowG.addNode();72 Node It v5=flowG.addNode();73 Node It t=flowG.addNode();61 Node s=graph.addNode(); 62 Node v2=graph.addNode(); 63 Node v3=graph.addNode(); 64 Node v4=graph.addNode(); 65 Node v5=graph.addNode(); 66 Node t=graph.addNode(); 74 67 75 Edge It s_v2=flowG.addEdge(s, v2);76 Edge It s_v3=flowG.addEdge(s, v3);77 Edge It v2_v4=flowG.addEdge(v2, v4);78 Edge It v2_v5=flowG.addEdge(v2, v5);79 Edge It v3_v5=flowG.addEdge(v3, v5);80 Edge It v4_t=flowG.addEdge(v4, t);81 Edge It v5_t=flowG.addEdge(v5, t);68 Edge s_v2=graph.addEdge(s, v2); 69 Edge s_v3=graph.addEdge(s, v3); 70 Edge v2_v4=graph.addEdge(v2, v4); 71 Edge v2_v5=graph.addEdge(v2, v5); 72 Edge v3_v5=graph.addEdge(v3, v5); 73 Edge v4_t=graph.addEdge(v4, t); 74 Edge v5_t=graph.addEdge(v5, t); 82 75 83 76 //Kis modositas 84 //edge_iterator v2_s= flowG.add_edge(v2, s);77 //edge_iterator v2_s=graph.add_edge(v2, s); 85 78 86 ListGraph::EdgeMap<int> cap(flowG);79 ListGraph::EdgeMap<int> length(graph); 87 80 88 cap.set(s_v2, 10);89 cap.set(s_v3, 10);90 cap.set(v2_v4, 5);91 cap.set(v2_v5, 8);92 cap.set(v3_v5, 5);93 cap.set(v4_t, 8);94 cap.set(v5_t, 8);81 length.set(s_v2, 10); 82 length.set(s_v3, 10); 83 length.set(v2_v4, 5); 84 length.set(v2_v5, 8); 85 length.set(v3_v5, 5); 86 length.set(v4_t, 8); 87 length.set(v5_t, 8); 95 88 96 89 //Kis modositas 97 //cap.put(v2_s, 100); 98 90 //length.put(v2_s, 100); 99 91 100 92 101 93 102 /*Egyszerû példa103 NodeIt s=flow_test.add_node();104 NodeIt v1=flow_test.add_node();105 NodeIt v2=flow_test.add_node();106 NodeIt t=flow_test.add_node();107 108 node_property_vector<list_graph, std::string> node_name(flow_test);109 node_name.put(s, "s");110 node_name.put(v1, "v1");111 node_name.put(v2, "v2");112 node_name.put(t, "t");113 114 edge_iterator s_v1=flow_test.add_edge(s, v1);115 edge_iterator v1_v2=flow_test.add_edge(v1, v2);116 edge_iterator v2_t=flow_test.add_edge(v2, t);117 118 edge_property_vector<list_graph, int> cap(flow_test);119 120 cap.put(s_v1, 16);121 cap.put(v1_v2, 10);122 cap.put(v2_t, 4);123 */124 125 94 std::cout << "preflowpush algorithm test..." << std::endl; 126 95 127 /*128 std::cout << "on directed graph graph" << std::endl; //<< flow_test;129 std::cout << "names and capacity values" << std::endl;130 for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {131 std::cout << node_name.get(i) << ": ";132 std::cout << "out edges: ";133 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)134 std::cout << node_name.get(flow_test.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flow_test.head(j)) << " ";135 std::cout << "in edges: ";136 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)137 std::cout << node_name.get(flow_test.tail(j)) << ""<< cap.get(j) << ">" << node_name.get(flow_test.head(j)) << " ";138 std::cout << std::endl;139 }140 */141 96 142 //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { 143 // std::cout << i << " "; 144 //} 145 146 preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap); 97 preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length); 147 98 cout << preflow_push_test.run()<<endl; 148 99 … … 152 103 return 0; 153 104 } 154 155 156 157 158 159 160 161 162 
src/work/athos/preflow_push.hh
r119 r331 1 #ifndef PREFLOW_PUSH_HH2 #define PREFLOW_PUSH_HH3 4 #include <algorithm>1 #ifndef HUGO_PREFLOW_PUSH_HH 2 #define HUGO_PREFLOW_PUSH_HH 3 4 //#include <algorithm> 5 5 #include <list> 6 6 #include <vector> 7 #include <queue> 7 8 //#include "pf_hiba.hh" 8 9 //#include <marci_list_graph.hh> 9 10 //#include <marci_graph_traits.hh> 10 11 #include <reverse_bfs.hh> 11 #include <invalid.h> 12 #include <graph_wrapper.h> 13 //#include <reverse_bfs.hh> 12 14 13 15 using namespace std; … … 15 17 namespace hugo { 16 18 17 template <typename graph_type, typename T>19 template <typename Graph, typename T> 18 20 class preflow_push { 19 21 20 //Hasznos typedefek 21 typedef typename graph_type::NodeIt NodeIt; 22 typedef typename graph_type::EdgeIt EdgeIt; 23 typedef typename graph_type::EachNodeIt EachNodeIt; 24 typedef typename graph_type::EachEdgeIt EachEdgeIt; 25 typedef typename graph_type::OutEdgeIt OutEdgeIt; 26 typedef typename graph_type::InEdgeIt InEdgeIt; 27 typedef typename graph_type::SymEdgeIt SymEdgeIt; 28 29 30 31 /* 32 typedef graph_traits<graph_type>::node_iterator node_iterator; 33 typedef graph_traits<graph_type>::EdgeIt EdgeIt; 34 typedef graph_traits<graph_type>::each_node_iterator each_node_iterator; 35 typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt; 36 typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt; 37 typedef graph_traits<graph_type>::InEdgeIt InEdgeIt; 38 typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt; 39 */ 22 //Useful typedefs 23 typedef typename Graph::Node Node; 24 typedef typename Graph::NodeIt NodeIt; 25 typedef typename Graph::Edge Edge; 26 typedef typename Graph::OutEdgeIt OutEdgeIt; 27 typedef typename Graph::InEdgeIt InEdgeIt; 28 40 29 41 30 // … … 56 45 private: 57 46 //input 58 graph_type& G;59 Node Its;60 Node Itt;61 typename graph_type::EdgeMap<T> &capacity;62 //typename graph_type::EdgeMap<T> &capacity; 47 Graph& G; 48 Node s; 49 Node t; 50 typename Graph::EdgeMap<T> &capacity; 51 63 52 //output 64 //typename graph_type::EdgeMap<T> 65 typename graph_type::EdgeMap<T> preflow; 53 typename Graph::EdgeMap<T> preflow; 66 54 T maxflow_value; 67 55 68 56 //auxiliary variables for computation 57 //The number of the nodes 69 58 int number_of_nodes; 70 71 72 typename graph_type::NodeMap<int> level; 73 typename graph_type::NodeMap<T> excess; 74 //node_property_vector<graph_type, int> level; 75 //node_property_vector<graph_type, T> excess; 59 //A nodemap for the level 60 typename Graph::NodeMap<int> level; 61 //A nodemap for the excess 62 typename Graph::NodeMap<T> excess; 76 63 77 64 //Number of nodes on each level … … 79 66 80 67 //For the FIFO implementation 81 list<Node It> fifo_nodes;68 list<Node> fifo_nodes; 82 69 //For 'highest label' implementation 83 70 int highest_active; 84 71 //int second_highest_active; 85 vector< list<Node It> > active_nodes;72 vector< list<Node> > active_nodes; 86 73 87 74 public: … … 89 76 //Constructing the object using the graph, source, sink and capacity vector 90 77 preflow_push( 91 graph_type& _G,92 Node It_s,93 Node It_t,94 typename graph_type::EdgeMap<T> & _capacity)78 Graph& _G, 79 Node _s, 80 Node _t, 81 typename Graph::EdgeMap<T> & _capacity) 95 82 : G(_G), s(_s), t(_t), 96 83 capacity(_capacity), … … 115 102 switch(implementation){ 116 103 case impl_highest_label :{ 104 active_nodes.clear(); 117 105 active_nodes.resize(2*number_of_nodes1); 118 active_nodes.clear();106 119 107 break; 120 108 } … … 128 116 T run(); 129 117 130 typename graph_type::EdgeMap<T> getmaxflow(){118 typename Graph::EdgeMap<T> getmaxflow(){ 131 119 return preflow; 132 120 } … … 136 124 //For testing purposes only 137 125 //Lists the node_properties 138 void write_property_vector(typename graph_type::NodeMap<T> a,139 //node_property_vector< graph_type, T> a,126 void write_property_vector(typename Graph::NodeMap<T> a, 127 //node_property_vector<Graph, T> a, 140 128 char* prop_name="property"){ 141 for( EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {142 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a .get(i)<<endl;129 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { 130 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; 143 131 } 144 132 cout<<endl; … … 146 134 147 135 //Modifies the excess of the node and makes sufficient changes 148 void modify_excess(const Node It& a ,T v){149 T old_value=excess.get(a);150 excess.set(a,old_value+v);136 void modify_excess(const Node& a ,T v){ 137 //T old_value=excess[a]; 138 excess[a] += v; 151 139 } 152 140 … … 155 143 //and maintain the excess on the head and tail 156 144 //Here we do not check whether this is possible or not 157 void modify_preflow(EdgeIt j, const T& v){ 158 159 //Auxiliary variable 160 T old_value; 161 145 void modify_preflow(Edge j, const T& v){ 146 162 147 //Modifiyng the edge 163 old_value=preflow.get(j); 164 preflow.set(j,old_value+v); 148 preflow[j] += v; 165 149 166 150 … … 175 159 //Gives the active node to work with 176 160 //(depending on the implementation to be used) 177 Node Itget_active_node(){161 Node get_active_node(){ 178 162 179 163 … … 181 165 case impl_highest_label : { 182 166 183 //First need to find the highest label for which there "s an active node167 //First need to find the highest label for which there's an active node 184 168 while( highest_active>=0 && active_nodes[highest_active].empty() ){ 185 169 highest_active; … … 189 173 190 174 191 Node Ita=active_nodes[highest_active].front();175 Node a=active_nodes[highest_active].front(); 192 176 active_nodes[highest_active].pop_front(); 193 177 … … 195 179 } 196 180 else { 197 return NodeIt();181 return INVALID; 198 182 } 199 183 … … 204 188 205 189 if( ! fifo_nodes.empty() ) { 206 Node Ita=fifo_nodes.front();190 Node a=fifo_nodes.front(); 207 191 fifo_nodes.pop_front(); 208 192 return a; 209 193 } 210 194 else { 211 return NodeIt();195 return INVALID; 212 196 } 213 197 break; … … 215 199 } 216 200 // 217 return NodeIt();201 return INVALID; 218 202 } 219 203 220 204 //Puts node 'a' among the active nodes 221 void make_active(const Node It& a){205 void make_active(const Node& a){ 222 206 //s and t never become active 223 207 if (a!=s && a!= t){ 224 208 switch(implementation){ 225 209 case impl_highest_label : 226 active_nodes[level .get(a)].push_back(a);210 active_nodes[level[a]].push_back(a); 227 211 break; 228 212 case impl_fifo : … … 234 218 235 219 //Update highest_active label 236 if (highest_active<level .get(a)){237 highest_active=level .get(a);220 if (highest_active<level[a]){ 221 highest_active=level[a]; 238 222 } 239 223 … … 241 225 242 226 //Changes the level of node a and make sufficent changes 243 void change_level_to(Node Ita, int new_value){244 int seged = level .get(a);227 void change_level_to(Node a, int new_value){ 228 int seged = level[a]; 245 229 level.set(a,new_value); 246 230 num_of_nodes_on_level[seged]; … … 258 242 //Setting starting preflow, level and excess values to zero 259 243 //This can be important, if the algorithm is run more then once 260 for( EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {244 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { 261 245 level.set(i,0); 262 246 excess.set(i,0); 263 for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)247 for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j)) 264 248 preflow.set(j, 0); 265 249 } … … 274 258 //This is the only part that uses BFS 275 259 // 260 261 /*Reverse_bfs from t, to find the starting level.*/ 262 //Copyright: Jacint 263 change_level_to(t,0); 264 265 std::queue<Node> bfs_queue; 266 bfs_queue.push(t); 267 268 while (!bfs_queue.empty()) { 269 270 Node v=bfs_queue.front(); 271 bfs_queue.pop(); 272 int l=level[v]+1; 273 274 InEdgeIt e; 275 for(G.first(e,v); G.valid(e); G.next(e)) { 276 Node w=G.tail(e); 277 if ( level[w] == number_of_nodes && w != s ) { 278 bfs_queue.push(w); 279 //Node first=level_list[l]; 280 //if ( G.valid(first) ) left.set(first,w); 281 //right.set(w,first); 282 //level_list[l]=w; 283 change_level_to(w, l); 284 //level.set(w, l); 285 } 286 } 287 } 288 change_level_to(s,number_of_nodes); 289 //level.set(s,number_of_nodes); 290 291 /* 276 292 //Setting starting level values using reverse bfs 277 reverse_bfs< graph_type> rev_bfs(G,t);293 reverse_bfs<Graph> rev_bfs(G,t); 278 294 rev_bfs.run(); 279 295 //write_property_vector(rev_bfs.dist,"rev_bfs"); 280 for( EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {296 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { 281 297 change_level_to(i,rev_bfs.dist(i)); 282 298 //level.put(i,rev_bfs.dist.get(i)); 283 299 } 300 */ 284 301 // 285 302 //This is the only part that uses BFS … … 293 310 294 311 //we push as much preflow from s as possible to start with 295 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){296 modify_preflow(j,capacity .get(j));312 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ 313 modify_preflow(j,capacity[j] ); 297 314 make_active(G.head(j)); 298 int lev=level .get(G.head(j));315 int lev=level[G.head(j)]; 299 316 if(highest_active<lev){ 300 317 highest_active=lev; … … 307 324 //If the preflow is less than the capacity on the given edge 308 325 //then it is an edge in the residual graph 309 bool is_admissible_forward_edge( OutEdgeItj, int& new_level){310 311 if (capacity .get(j)>preflow.get(j)){312 if(level .get(G.tail(j))==level.get(G.head(j))+1){326 bool is_admissible_forward_edge(Edge j, int& new_level){ 327 328 if (capacity[j]>preflow[j]){ 329 if(level[G.tail(j)]==level[G.head(j)]+1){ 313 330 return true; 314 331 } 315 332 else{ 316 if (level .get(G.head(j))< new_level)317 new_level=level .get(G.head(j));333 if (level[G.head(j)] < new_level) 334 new_level=level[G.head(j)]; 318 335 } 319 336 } … … 323 340 //If the preflow is greater than 0 on the given edge 324 341 //then the edge reversd is an edge in the residual graph 325 bool is_admissible_backward_edge( InEdgeItj, int& new_level){326 327 if (0<preflow .get(j)){328 if(level .get(G.tail(j))==level.get(G.head(j))1){342 bool is_admissible_backward_edge(Edge j, int& new_level){ 343 344 if (0<preflow[j]){ 345 if(level[G.tail(j)]==level[G.head(j)]1){ 329 346 330 347 return true; 331 348 } 332 349 else{ 333 if (level .get(G.tail(j))< new_level)334 new_level=level .get(G.tail(j));350 if (level[G.tail(j)] < new_level) 351 new_level=level[G.tail(j)]; 335 352 } 336 353 … … 342 359 }; //class preflow_push 343 360 344 template<typename graph_type, typename T> 345 T preflow_push<graph_type, T>::run() { 361 template<typename Graph, typename T> 362 T preflow_push<Graph, T>::run() { 363 364 //We need a residual graph 365 ResGraphType res_graph(G, preflow, capacity); 346 366 347 367 preprocess(); 348 368 //write_property_vector(level,"level"); 349 369 T e,v; 350 NodeIt a; 351 while (a=get_active_node(), a.valid()){ 352 353 //cout<<G.id(a)<<endl; 354 //write_property_vector(excess,"excess"); 355 //write_property_vector(level,"level"); 356 357 370 Node a; 371 while (a=get_active_node(), G.valid(a)){ 372 358 373 bool go_to_next_node=false; 359 e = excess .get(a);374 e = excess[a]; 360 375 while (!go_to_next_node){ 376 361 377 //Initial value for the new level for the active node we are dealing with 362 378 int new_level=2*number_of_nodes; 363 //write_property_vector(excess,"excess"); 364 //write_property_vector(level,"level"); 365 //cout<<G.id(a)<<endl; 379 380 366 381 //Out edges from node a 367 382 { 368 383 OutEdgeIt j=G.template first<OutEdgeIt>(a); 369 while ( j.valid() && e){384 while (G.valid(j) && e){ 370 385 371 386 if (is_admissible_forward_edge(j,new_level)){ 372 v=min(e,capacity .get(j)  preflow.get(j));387 v=min(e,capacity[j]  preflow[j]); 373 388 e = v; 374 389 //New node might become active 375 if (excess .get(G.head(j))==0){390 if (excess[G.head(j)]==0){ 376 391 make_active(G.head(j)); 377 392 } 378 393 modify_preflow(j,v); 379 394 } 380 ++j;395 G.next(j); 381 396 } 382 397 } … … 384 399 { 385 400 InEdgeIt j=G.template first<InEdgeIt>(a); 386 while ( j.valid() && e){401 while (G.valid(j) && e){ 387 402 if (is_admissible_backward_edge(j,new_level)){ 388 v=min(e,preflow .get(j));403 v=min(e,preflow[j]); 389 404 e = v; 390 405 //New node might become active 391 if (excess .get(G.tail(j))==0){406 if (excess[G.tail(j)]==0){ 392 407 make_active(G.tail(j)); 393 408 } 394 409 modify_preflow(j,v); 395 410 } 396 ++j;411 G.next(j); 397 412 } 398 413 } … … 411 426 412 427 //Level remains empty 413 if (num_of_nodes_on_level[level .get(a)]==1){428 if (num_of_nodes_on_level[level[a]]==1){ 414 429 change_level_to(a,number_of_nodes); 415 430 //go_to_next_node=True; … … 438 453 } 439 454 } 440 maxflow_value = excess .get(t);455 maxflow_value = excess[t]; 441 456 return maxflow_value; 442 457 }//run
Note: See TracChangeset
for help on using the changeset viewer.