Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 #include <lemon/time_measure.h>
22 #include <lemon/smart_graph.h>
23 #include <lemon/graph_utils.h>
24 #include <lemon/maps.h>
25 #include <lemon/error.h>
27 #include <lemon/radix_sort.h>
29 #include <lemon/random.h>
36 using namespace lemon;
38 void testRadixSort() {
41 for (int i = 0; i < n; ++i) {
42 data[i] = rnd[1000] - 500;
44 radixSort(data.begin(), data.end());
48 void testCounterSort() {
51 for (int i = 0; i < n; ++i) {
52 data[i] = rnd[1000] - 500;
54 counterSort(data.begin(), data.end());
60 for (int i = 0; i < n; ++i) {
61 data[i] = rnd[1000] - 500;
63 sort(data.begin(), data.end());
66 void testStableSort() {
69 for (int i = 0; i < n; ++i) {
70 data[i] = rnd[1000] - 500;
72 stable_sort(data.begin(), data.end());
80 cout << "Radix sort: " << runningTimeTest(testRadixSort, 60) << endl;
81 cout << "Counter sort: " << runningTimeTest(testCounterSort, 60) << endl;
82 cout << "Standard sort: " << runningTimeTest(testSort, 60) << endl;
83 cout << "Stable sort: " << runningTimeTest(testStableSort, 60) << endl;