29 #include <lemon/dijkstra.h> |
29 #include <lemon/dijkstra.h> |
30 #include <lemon/graph_adaptor.h> |
30 #include <lemon/graph_adaptor.h> |
31 |
31 |
32 #define WITH_SCALING |
32 #define WITH_SCALING |
33 |
33 |
|
34 //#define _DEBUG_ITER_ |
|
35 |
34 namespace lemon { |
36 namespace lemon { |
35 |
37 |
36 /// \addtogroup min_cost_flow |
38 /// \addtogroup min_cost_flow |
37 /// @{ |
39 /// @{ |
38 |
40 |
39 /// \brief Implementation of the capacity scaling version of the |
41 /// \brief Implementation of the capacity scaling version of the |
40 /// succesive shortest path algorithm for finding a minimum cost flow. |
42 /// successive shortest path algorithm for finding a minimum cost flow. |
41 /// |
43 /// |
42 /// \ref lemon::CapacityScaling "CapacityScaling" implements a |
44 /// \ref lemon::CapacityScaling "CapacityScaling" implements a |
43 /// capacity scaling algorithm for finding a minimum cost flow. |
45 /// capacity scaling algorithm for finding a minimum cost flow. |
44 /// |
46 /// |
45 /// \param Graph The directed graph type the algorithm runs on. |
47 /// \param Graph The directed graph type the algorithm runs on. |
296 DeltaFilterMap delta_filter; |
298 DeltaFilterMap delta_filter; |
297 /// \brief The delta residual graph. |
299 /// \brief The delta residual graph. |
298 DeltaResGraph dres_graph; |
300 DeltaResGraph dres_graph; |
299 /// \brief Map for identifing deficit nodes. |
301 /// \brief Map for identifing deficit nodes. |
300 DeficitBoolMap delta_deficit; |
302 DeficitBoolMap delta_deficit; |
|
303 |
|
304 /// \brief The deficit nodes. |
|
305 std::vector<ResNode> deficit_nodes; |
301 |
306 |
302 #else //WITHOUT_CAPACITY_SCALING |
307 #else //WITHOUT_CAPACITY_SCALING |
303 typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits> |
308 typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits> |
304 ResDijkstra; |
309 ResDijkstra; |
305 /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding |
310 /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding |
508 for (EdgeIt e(graph); e != INVALID; ++e) |
513 for (EdgeIt e(graph); e != INVALID; ++e) |
509 c += flow[e] * cost[e]; |
514 c += flow[e] * cost[e]; |
510 return c; |
515 return c; |
511 } |
516 } |
512 |
517 |
513 /// \brief Runs the successive shortest path algorithm. |
518 /// \brief Runs the algorithm. |
514 /// |
519 /// |
515 /// Runs the successive shortest path algorithm. |
520 /// Runs the algorithm. |
516 /// |
521 /// |
517 /// \return \c true if a feasible flow can be found. |
522 /// \return \c true if a feasible flow can be found. |
518 bool run() { |
523 bool run() { |
519 return init() && start(); |
524 return init() && start(); |
520 } |
525 } |
529 updater.potentialMap(potential); |
534 updater.potentialMap(potential); |
530 dijkstra.distMap(updater).predMap(pred); |
535 dijkstra.distMap(updater).predMap(pred); |
531 |
536 |
532 #ifdef WITH_SCALING |
537 #ifdef WITH_SCALING |
533 // Initilaizing delta value |
538 // Initilaizing delta value |
534 Capacity max_cap = 0; |
539 Supply max_sup = 0, max_dem = 0; |
535 for (EdgeIt e(graph); e != INVALID; ++e) { |
540 for (NodeIt n(graph); n != INVALID; ++n) { |
536 if (capacity[e] > max_cap) max_cap = capacity[e]; |
541 if (supply[n] > max_sup) max_sup = supply[n]; |
537 } |
542 if (supply[n] < -max_dem) max_dem = -supply[n]; |
538 for (delta = 1; 2 * delta < max_cap; delta *= 2) ; |
543 } |
|
544 if (max_dem < max_sup) max_sup = max_dem; |
|
545 for (delta = 1; 2 * delta < max_sup; delta *= 2) ; |
539 #endif |
546 #endif |
540 return true; |
547 return true; |
541 } |
548 } |
542 |
549 |
543 #ifdef WITH_SCALING |
550 #ifdef WITH_SCALING |
544 /// \brief Executes the capacity scaling version of the successive |
551 /// \brief Executes the capacity scaling version of the successive |
545 /// shortest path algorithm. |
552 /// shortest path algorithm. |
546 bool start() { |
553 bool start() { |
547 typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt; |
554 typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt; |
548 typedef typename DeltaResGraph::Edge DeltaResEdge; |
555 typedef typename DeltaResGraph::Edge DeltaResEdge; |
|
556 #ifdef _DEBUG_ITER_ |
|
557 int dijk_num = 0; |
|
558 #endif |
549 |
559 |
550 // Processing capacity scaling phases |
560 // Processing capacity scaling phases |
551 ResNode s, t; |
561 ResNode s, t; |
552 for ( ; delta >= 1; delta = delta < 4 && delta > 1 ? |
562 for ( ; delta >= 1; delta = delta < 4 && delta > 1 ? |
553 1 : delta / 4 ) |
563 1 : delta / 4 ) |
562 } |
572 } |
563 } |
573 } |
564 |
574 |
565 // Finding excess nodes |
575 // Finding excess nodes |
566 excess_nodes.clear(); |
576 excess_nodes.clear(); |
|
577 deficit_nodes.clear(); |
567 for (ResNodeIt n(res_graph); n != INVALID; ++n) { |
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 next_node = 0; |
582 next_node = 0; |
571 |
583 |
572 // Finding successive shortest paths |
584 // Finding shortest paths |
573 while (next_node < excess_nodes.size()) { |
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 // Running Dijkstra |
598 // Running Dijkstra |
575 s = excess_nodes[next_node]; |
599 s = excess_nodes[next_node]; |
576 updater.init(); |
600 updater.init(); |
577 dijkstra.init(); |
601 dijkstra.init(); |
578 dijkstra.addSource(s); |
602 dijkstra.addSource(s); |
|
603 #ifdef _DEBUG_ITER_ |
|
604 ++dijk_num; |
|
605 #endif |
579 if ((t = dijkstra.start(delta_deficit)) == INVALID) { |
606 if ((t = dijkstra.start(delta_deficit)) == INVALID) { |
580 if (delta > 1) { |
607 if (delta > 1) { |
581 ++next_node; |
608 ++next_node; |
582 continue; |
609 continue; |
583 } |
610 } |
606 imbalance[s] -= d; |
633 imbalance[s] -= d; |
607 imbalance[t] += d; |
634 imbalance[t] += d; |
608 if (imbalance[s] < delta) ++next_node; |
635 if (imbalance[s] < delta) ++next_node; |
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 // Handling nonzero lower bounds |
643 // Handling nonzero lower bounds |
613 if (lower) { |
644 if (lower) { |
614 for (EdgeIt e(graph); e != INVALID; ++e) |
645 for (EdgeIt e(graph); e != INVALID; ++e) |
615 flow[e] += (*lower)[e]; |
646 flow[e] += (*lower)[e]; |
626 if (imbalance[n] > 0) excess_nodes.push_back(n); |
657 if (imbalance[n] > 0) excess_nodes.push_back(n); |
627 } |
658 } |
628 if (excess_nodes.size() == 0) return true; |
659 if (excess_nodes.size() == 0) return true; |
629 next_node = 0; |
660 next_node = 0; |
630 |
661 |
631 // Finding successive shortest paths |
662 // Finding shortest paths |
632 ResNode s, t; |
663 ResNode s, t; |
633 while ( imbalance[excess_nodes[next_node]] > 0 || |
664 while ( imbalance[excess_nodes[next_node]] > 0 || |
634 ++next_node < excess_nodes.size() ) |
665 ++next_node < excess_nodes.size() ) |
635 { |
666 { |
636 // Running Dijkstra |
667 // Running Dijkstra |