equal
deleted
inserted
replaced
28 #include <vector> |
28 #include <vector> |
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 |
|
34 #ifdef WITH_SCALING |
|
35 #define SCALING_FACTOR 2 |
|
36 #endif |
33 |
37 |
34 //#define _DEBUG_ITER_ |
38 //#define _DEBUG_ITER_ |
35 |
39 |
36 namespace lemon { |
40 namespace lemon { |
37 |
41 |
540 for (NodeIt n(graph); n != INVALID; ++n) { |
544 for (NodeIt n(graph); n != INVALID; ++n) { |
541 if (supply[n] > max_sup) max_sup = supply[n]; |
545 if (supply[n] > max_sup) max_sup = supply[n]; |
542 if (supply[n] < -max_dem) max_dem = -supply[n]; |
546 if (supply[n] < -max_dem) max_dem = -supply[n]; |
543 } |
547 } |
544 if (max_dem < max_sup) max_sup = max_dem; |
548 if (max_dem < max_sup) max_sup = max_dem; |
545 for (delta = 1; 2 * delta < max_sup; delta *= 2) ; |
549 for ( delta = 1; SCALING_FACTOR * delta < max_sup; |
|
550 delta *= SCALING_FACTOR ) ; |
546 #endif |
551 #endif |
547 return true; |
552 return true; |
548 } |
553 } |
549 |
554 |
550 #ifdef WITH_SCALING |
555 #ifdef WITH_SCALING |
557 int dijk_num = 0; |
562 int dijk_num = 0; |
558 #endif |
563 #endif |
559 |
564 |
560 // Processing capacity scaling phases |
565 // Processing capacity scaling phases |
561 ResNode s, t; |
566 ResNode s, t; |
562 for ( ; delta >= 1; delta = delta < 4 && delta > 1 ? |
567 for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ? |
563 1 : delta / 4 ) |
568 1 : delta / SCALING_FACTOR ) |
564 { |
569 { |
565 // Saturating edges not satisfying the optimality condition |
570 // Saturating edges not satisfying the optimality condition |
566 Capacity r; |
571 Capacity r; |
567 for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) { |
572 for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) { |
568 if (red_cost[e] < 0) { |
573 if (red_cost[e] < 0) { |