Changeset 2457:8c791ee69a45 in lemon-0.x
- Timestamp:
- 06/15/07 16:36:24 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3294
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r2440 r2457 32 32 #define WITH_SCALING 33 33 34 //#define _DEBUG_ITER_ 35 34 36 namespace lemon { 35 37 … … 38 40 39 41 /// \brief Implementation of the capacity scaling version of the 40 /// succes ive shortest path algorithm for finding a minimum cost flow.42 /// successive shortest path algorithm for finding a minimum cost flow. 41 43 /// 42 44 /// \ref lemon::CapacityScaling "CapacityScaling" implements a … … 299 301 /// \brief Map for identifing deficit nodes. 300 302 DeficitBoolMap delta_deficit; 303 304 /// \brief The deficit nodes. 305 std::vector<ResNode> deficit_nodes; 301 306 302 307 #else //WITHOUT_CAPACITY_SCALING … … 511 516 } 512 517 513 /// \brief Runs the successive shortest pathalgorithm.514 /// 515 /// Runs the successive shortest pathalgorithm.518 /// \brief Runs the algorithm. 519 /// 520 /// Runs the algorithm. 516 521 /// 517 522 /// \return \c true if a feasible flow can be found. … … 532 537 #ifdef WITH_SCALING 533 538 // Initilaizing delta value 534 Capacity max_cap = 0; 535 for (EdgeIt e(graph); e != INVALID; ++e) { 536 if (capacity[e] > max_cap) max_cap = capacity[e]; 537 } 538 for (delta = 1; 2 * delta < max_cap; delta *= 2) ; 539 Supply max_sup = 0, max_dem = 0; 540 for (NodeIt n(graph); n != INVALID; ++n) { 541 if (supply[n] > max_sup) max_sup = supply[n]; 542 if (supply[n] < -max_dem) max_dem = -supply[n]; 543 } 544 if (max_dem < max_sup) max_sup = max_dem; 545 for (delta = 1; 2 * delta < max_sup; delta *= 2) ; 539 546 #endif 540 547 return true; … … 547 554 typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt; 548 555 typedef typename DeltaResGraph::Edge DeltaResEdge; 556 #ifdef _DEBUG_ITER_ 557 int dijk_num = 0; 558 #endif 549 559 550 560 // Processing capacity scaling phases … … 565 575 // Finding excess nodes 566 576 excess_nodes.clear(); 577 deficit_nodes.clear(); 567 578 for (ResNodeIt n(res_graph); n != INVALID; ++n) { 568 if (imbalance[n] >= delta) excess_nodes.push_back(n); 579 if (imbalance[n] >= delta) excess_nodes.push_back(n); 580 if (imbalance[n] <= -delta) deficit_nodes.push_back(n); 569 581 } 570 582 next_node = 0; 571 583 572 // Finding s uccessive shortest paths584 // Finding shortest paths 573 585 while (next_node < excess_nodes.size()) { 586 // Checking deficit nodes 587 if (delta > 1) { 588 bool delta_def = false; 589 for (int i = 0; i < deficit_nodes.size(); ++i) { 590 if (imbalance[deficit_nodes[i]] <= -delta) { 591 delta_def = true; 592 break; 593 } 594 } 595 if (!delta_def) break; 596 } 597 574 598 // Running Dijkstra 575 599 s = excess_nodes[next_node]; … … 577 601 dijkstra.init(); 578 602 dijkstra.addSource(s); 603 #ifdef _DEBUG_ITER_ 604 ++dijk_num; 605 #endif 579 606 if ((t = dijkstra.start(delta_deficit)) == INVALID) { 580 607 if (delta > 1) { … … 609 636 } 610 637 } 638 #ifdef _DEBUG_ITER_ 639 std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm " 640 << dijk_num << " times." << std::endl; 641 #endif 611 642 612 643 // Handling nonzero lower bounds … … 629 660 next_node = 0; 630 661 631 // Finding s uccessive shortest paths662 // Finding shortest paths 632 663 ResNode s, t; 633 664 while ( imbalance[excess_nodes[next_node]] > 0 || -
lemon/cycle_canceling.h
r2440 r2457 23 23 /// 24 24 /// \file 25 /// \brief A cycle 25 /// \brief A cycle-canceling algorithm for finding a minimum cost flow. 26 26 27 27 #include <vector> … … 29 29 #include <lemon/graph_adaptor.h> 30 30 31 /// \brief The used cycle 31 /// \brief The used cycle-canceling method. 32 32 #define LIMITED_CYCLE_CANCELING 33 33 //#define MIN_MEAN_CYCLE_CANCELING … … 37 37 /// \brief The maximum number of iterations for the first execution 38 38 /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm. 39 /// It should be at least 2. 39 40 #define STARTING_LIMIT 2 40 41 /// \brief The iteration limit for the 41 42 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by 42 /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round. 43 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round. 44 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1. 43 45 #define ALPHA_MUL 3 44 46 /// \brief The iteration limit for the 45 47 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by 46 /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round. 48 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round. 49 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1. 47 50 #define ALPHA_DIV 2 48 51 49 52 //#define _ONLY_ONE_CYCLE_ 53 //#define _NO_BACK_STEP_ 50 54 //#define _DEBUG_ITER_ 51 55 #endif … … 61 65 /// @{ 62 66 63 /// \brief Implementation of a cycle 67 /// \brief Implementation of a cycle-canceling algorithm for finding 64 68 /// a minimum cost flow. 65 69 /// 66 /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle67 /// c anceling algorithm for finding a minimum cost flow.70 /// \ref lemon::CycleCanceling "CycleCanceling" implements a 71 /// cycle-canceling algorithm for finding a minimum cost flow. 68 72 /// 69 73 /// \param Graph The directed graph type the algorithm runs on. … … 119 123 protected: 120 124 121 /// \brief Map adaptor class for demand map.122 class DemandMap : public MapBase<Node, Supply>123 {124 private:125 126 const SupplyMap *map;127 128 public:129 130 typedef typename MapBase<Node, Supply>::Value Value;131 typedef typename MapBase<Node, Supply>::Key Key;132 133 DemandMap(const SupplyMap &_map) : map(&_map) {}134 135 Value operator[](const Key &e) const {136 return -(*map)[e];137 }138 139 }; //class DemandMap140 141 125 /// \brief Map adaptor class for handling residual edge costs. 142 126 class ResCostMap : public MapBase<ResEdge, Cost> … … 171 155 /// \brief The modified supply map. 172 156 SupplyRefMap supply; 173 /// \brief The modified demand map.174 DemandMap demand;175 157 /// \brief The sum of supply values equals zero. 176 158 bool valid_supply; … … 200 182 const SupplyMap &_supply ) : 201 183 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), 202 supply(_graph), demand(supply),flow(_graph, 0),184 supply(_graph), flow(_graph, 0), 203 185 res_graph(_graph, capacity, flow), res_cost(cost) 204 186 { … … 230 212 const SupplyMap &_supply ) : 231 213 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), 232 supply(_supply), demand(supply),flow(_graph, 0),214 supply(_supply), flow(_graph, 0), 233 215 res_graph(_graph, capacity, flow), res_cost(cost) 234 216 { … … 260 242 Supply _flow_value ) : 261 243 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), 262 supply(_graph), demand(supply),flow(_graph, 0),244 supply(_graph), flow(_graph, 0), 263 245 res_graph(_graph, capacity, flow), res_cost(cost) 264 246 { … … 296 278 Supply _flow_value ) : 297 279 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), 298 supply(_graph, 0), demand(supply),flow(_graph, 0),280 supply(_graph, 0), flow(_graph, 0), 299 281 res_graph(_graph, capacity, flow), res_cost(cost) 300 282 { … … 346 328 // Finding a feasible flow 347 329 Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>, 348 CapacityRefMap, DemandMap >330 CapacityRefMap, SupplyMap > 349 331 circulation( graph, constMap<Edge>((Capacity)0), 350 capacity, demand, flow );332 capacity, supply, flow ); 351 333 return circulation.run() == -1; 352 334 } 353 335 354 336 #ifdef LIMITED_CYCLE_CANCELING 355 /// \brief Executes a cycle 337 /// \brief Executes a cycle-canceling algorithm using 356 338 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited 357 339 /// iteration count. … … 374 356 bool cycle_found = false; 375 357 while (!cycle_found) { 358 #ifdef _NO_BACK_STEP_ 359 int curr_iter_num = length_bound <= node_num ? 360 length_bound - iter_num : node_num - iter_num; 361 #else 376 362 int curr_iter_num = iter_num + length_bound <= node_num ? 377 363 length_bound : node_num - iter_num; 364 #endif 378 365 iter_num += curr_iter_num; 379 366 int real_iter_num = curr_iter_num; … … 433 420 434 421 #ifdef _DEBUG_ITER_ 435 std::cout << "Limited cycle 422 std::cout << "Limited cycle-canceling algorithm finished. " 436 423 << "Found " << cycle_num << " negative cycles." 437 424 << std::endl; … … 448 435 449 436 #ifdef MIN_MEAN_CYCLE_CANCELING 450 /// \brief Executes the minimum mean cycle 437 /// \brief Executes the minimum mean cycle-canceling algorithm 451 438 /// using \ref lemon::MinMeanCycle "MinMeanCycle" class. 452 439 bool start() { … … 487 474 488 475 #ifdef _DEBUG_ITER_ 489 std::cout << "Minimum mean cycle 476 std::cout << "Minimum mean cycle-canceling algorithm finished. " 490 477 << "Found " << cycle_num << " negative cycles." 491 478 << std::endl; -
lemon/network_simplex.h
r2444 r2457 276 276 277 277 // Copying graph_ref to graph 278 graph.reserveNode(countNodes(graph_ref) + 1); 279 graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref)); 278 280 copyGraph(graph, graph_ref) 279 281 .edgeMap(cost, _cost) … … 478 480 parent[root] = INVALID; 479 481 pred_edge[root] = INVALID; 480 depth[root] = supply[root] = potential[root] = 0; 482 depth[root] = 0; 483 supply[root] = 0; 484 potential[root] = 0; 481 485 482 486 // Adding artificial edges to the graph and initializing the node … … 514 518 // Initializing block_size for the edge block pivot rule 515 519 int edge_num = countEdges(graph); 516 block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 520 block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 517 521 edge_num / BLOCK_NUM : MIN_BLOCK_SIZE; 518 522 #endif
Note: See TracChangeset
for help on using the changeset viewer.