Changeset 671:708df4dc6ab6 in lemon0.x
 Timestamp:
 06/01/04 13:00:24 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@905
 Location:
 src/work
 Files:

 1 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/makefile
r661 r671 1 BINARIES = min_cost_flow1 BINARIES = bfs_test min_cost_flow 2 2 INCLUDEDIRS= I../.. I.. I../{athos,klao,marci,jacint,alpar,johanna,akos} 3 3 include ../makefile 
src/work/athos/mincostflow.h
r662 r671 214 214 bfs_pred(res_ab_graph); 215 215 NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy; 216 //Teszt celbol: 217 //BfsIterator<ResAbGraph, typename ResAbGraph::template NodeMap<bool> > 218 //izebize(res_ab_graph, bfs_reached); 216 219 //We want to run bfses (more) on this graph 'res_ab_graph' 217 Bfs < ResAbGraph ,220 Bfs < const ResAbGraph , 218 221 typename ResAbGraph::template NodeMap<bool>, 219 222 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>, … … 234 237 Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost); 235 238 239 //We will use the number of the nodes of the graph often 240 int number_of_nodes = graph.nodeNum(); 236 241 237 242 while (max_excess > 0){ … … 251 256 typename std::list<Edge>::iterator i = nonabundant_arcs.begin(); 252 257 while ( i != nonabundant_arcs.end() ){ 253 if (flow[ i]>=buf){254 Node a = abundant_components.find(res_graph.head( i));255 Node b = abundant_components.find(res_graph.tail( i));258 if (flow[*i]>=buf){ 259 Node a = abundant_components.find(res_graph.head(*i)); 260 Node b = abundant_components.find(res_graph.tail(*i)); 256 261 //Merge 257 262 if (a != b){ … … 270 275 if (qty_to_augment>0){ 271 276 //Find path and augment 272 bfs.run( non_root);277 bfs.run(typename AbundantGraph::Node(non_root)); 273 278 //root should be reached 274 279 … … 277 282 ResGraphEdge e; 278 283 while (n!=non_root){ 279 e = bfs_pred (n);284 e = bfs_pred[n]; 280 285 n = res_graph.tail(e); 281 286 res_graph.augment(e,qty_to_augment); … … 283 288 284 289 //We know that non_root had positive excess 285 excess_nodes[non_root] = qty_to_augment; 290 excess_nodes.set(non_root, 291 excess_nodes[non_root]  qty_to_augment); 286 292 //But what about root node 287 293 //It might have been positive and so became larger 288 294 if (excess_deficit[root]>0){ 289 excess_nodes[root] += qty_to_augment; 295 excess_nodes.set(root, 296 excess_nodes[root] + qty_to_augment); 290 297 } 291 298 else{ 292 299 //Or negative but not turned into positive 293 deficit_nodes[root] = qty_to_augment; 300 deficit_nodes.set(root, 301 deficit_nodes[root]  qty_to_augment); 294 302 } 295 303 … … 304 312 //Marci and Zsolt says I shouldn't do such things 305 313 nonabundant_arcs.erase(i++); 306 abundant_arcs[ i] = true;314 abundant_arcs[*i] = true; 307 315 } 308 316 else … … 370 378 } 371 379 else{ 372 excess_nodes [s] = delta;380 excess_nodes.set(s, excess_nodes[s]  delta); 373 381 } 374 382 //Update the deficit_nodes heap … … 380 388 } 381 389 else{ 382 deficit_nodes [t] = delta;390 deficit_nodes.set(t, deficit_nodes[t]  delta); 383 391 } 384 392 //Dijkstra part ends here … … 415 423 416 424 417 return i;425 //return i; 418 426 } 419 427 
src/work/marci/bfs_dfs.h
r650 r671 152 152 /// the nodes which are \c false initially. 153 153 /// The constructor makes no initial changes on the maps. 154 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } 154 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : 155 BfsIterator<Graph, ReachedMap>(_graph, _reached), 156 pred(_pred), dist(_dist) { } 155 157 /// \c s is marked to be reached and pushed in the bfs queue. 156 158 /// If the queue is empty, then the first outedge is processed. … … 297 299 /// the nodes which are \c false initially. 298 300 /// The constructor makes no initial changes on the maps. 299 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred( &_pred) { }301 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { } 300 302 /// \c s is marked to be reached and pushed in the bfs queue. 301 303 /// If the queue is empty, then the first outedge is processed.
Note: See TracChangeset
for help on using the changeset viewer.