Do not append -Wall -W to CXXFLAGS when it is set on the commandline.
1 #include <lemon/time_measure.h>
2 #include <lemon/smart_graph.h>
3 #include <lemon/graph_utils.h>
4 #include <lemon/maps.h>
5 #include <lemon/radix_sort.h>
7 #include "test_tools.h"
15 using namespace lemon;
17 void checkRadixSort() {
20 vector<int> data1(n), data2(n);
21 for (int i = 0; i < n; ++i) {
22 data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
24 radixSort(data1.begin(), data1.end());
25 sort(data2.begin(), data2.end());
26 for (int i = 0; i < n; ++i) {
27 check(data1[i] == data2[i], "Test failed");
31 vector<unsigned char> data1(n), data2(n);
32 for (int i = 0; i < n; ++i) {
33 data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
35 radixSort(data1.begin(), data1.end());
36 sort(data2.begin(), data2.end());
37 for (int i = 0; i < n; ++i) {
38 check(data1[i] == data2[i], "Test failed");
44 void checkCounterSort() {
47 vector<int> data1(n), data2(n);
48 for (int i = 0; i < n; ++i) {
49 data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
51 counterSort(data1.begin(), data1.end());
52 sort(data2.begin(), data2.end());
53 for (int i = 0; i < n; ++i) {
54 check(data1[i] == data2[i], "Test failed");
58 vector<unsigned char> data1(n), data2(n);
59 for (int i = 0; i < n; ++i) {
60 data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
62 counterSort(data1.begin(), data1.end());
63 sort(data2.begin(), data2.end());
64 for (int i = 0; i < n; ++i) {
65 check(data1[i] == data2[i], "Test failed");
75 void checkGraphRadixSort() {
76 typedef SmartGraph Graph;
77 typedef Graph::Node Node;
78 typedef Graph::Edge Edge;
81 const int e = (int)(n * log((double)n));
86 for (int i = 0; i < n; ++i) {
87 nodes.push_back(graph.addNode());
90 for (int i = 0; i < e; ++i) {
91 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
92 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
93 edges.push_back(graph.addEdge(nodes[s], nodes[t]));
96 radixSort(edges.begin(), edges.end(),
97 mapFunctor(composeMap(IdMap<Graph, Node>(graph),
100 Graph::EdgeMap<bool> was(graph, false);
102 for (int i = 0; i < (int)edges.size(); ++i) {
103 check(!was[edges[i]], "Test failed");
104 was[edges[i]] = true;
107 for (int i = 1; i < (int)edges.size(); ++i) {
108 check(graph.id(graph.source(edges[i - 1])) <=
109 graph.id(graph.source(edges[i])), "Test failed");
114 void checkGraphCounterSort() {
115 typedef SmartGraph Graph;
116 typedef Graph::Node Node;
117 typedef Graph::Edge Edge;
120 const int e = (int)(n * log((double)n));
125 for (int i = 0; i < n; ++i) {
126 nodes.push_back(graph.addNode());
129 for (int i = 0; i < e; ++i) {
130 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
131 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
132 edges.push_back(graph.addEdge(nodes[s], nodes[t]));
135 counterSort(edges.begin(), edges.end(),
136 mapFunctor(composeMap(IdMap<Graph, Node>(graph),
139 counterSort(edges.begin(), edges.end(),
140 mapFunctor(composeMap(IdMap<Graph, Node>(graph),
143 Graph::EdgeMap<bool> was(graph, false);
145 for (int i = 0; i < (int)edges.size(); ++i) {
146 check(!was[edges[i]], "Test failed");
147 was[edges[i]] = true;
150 for (int i = 1; i < (int)edges.size(); ++i) {
151 check(graph.id(graph.target(edges[i - 1])) <
152 graph.id(graph.target(edges[i])) ||
153 (graph.id(graph.target(edges[i - 1])) ==
154 graph.id(graph.target(edges[i])) &&
155 graph.id(graph.source(edges[i - 1])) <=
156 graph.id(graph.source(edges[i]))), "Test failed");
161 void checkGraphSorts() {
162 checkGraphRadixSort();
163 checkGraphCounterSort();