# source:lemon-0.x/test/radix_sort_test.cc@1833:6d107b0b6b46

Last change on this file since 1833:6d107b0b6b46 was 1833:6d107b0b6b46, checked in by Balazs Dezso, 15 years ago

Radix sort algorithm

File size: 3.4 KB
Line
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>
6
7#include "test_tools.h"
8
9
10#include <vector>
11#include <algorithm>
12#include <cmath>
13
14using namespace std;
15using namespace lemon;
16
17void checkRadixSort() {
18  int n = 10000;
19  vector<int> data1(n), data2(n);
20  for (int i = 0; i < n; ++i) {
21    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
22  }
23  radixSort(data1.begin(), data1.end());
24  sort(data2.begin(), data2.end());
25  for (int i = 0; i < n; ++i) {
26    check(data1[i] == data2[i], "Test failed");
27  }
28}
29
30
31void checkCounterSort() {
32  int n = 10000;
33  vector<int> data1(n), data2(n);
34  for (int i = 0; i < n; ++i) {
35    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
36  }
37  counterSort(data1.begin(), data1.end());
38  sort(data2.begin(), data2.end());
39  for (int i = 0; i < n; ++i) {
40    check(data1[i] == data2[i], "Test failed");
41  }
42}
43
44void checkSorts() {
45  checkRadixSort();
46  checkCounterSort();
47}
48
49void checkGraphRadixSort() {
50  typedef SmartGraph Graph;
51  typedef Graph::Node Node;
52  typedef Graph::Edge Edge;
53
54  const int n = 100;
55  const int e = (int)(n * log((double)n));
56
57  Graph graph;
58  vector<Node> nodes;
59
60  for (int i = 0; i < n; ++i) {
61    nodes.push_back(graph.addNode());
62  }
63  vector<Edge> edges;
64  for (int i = 0; i < e; ++i) {
65    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
66    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
67    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
68  }
69
70  radixSort(edges.begin(), edges.end(),
71            mapFunctor(composeMap(IdMap<Graph, Node>(graph),
72                                  sourceMap(graph))));
73
74  Graph::EdgeMap<bool> was(graph, false);
75
76  for (int i = 0; i < (int)edges.size(); ++i) {
77    check(!was[edges[i]], "Test failed");
78    was[edges[i]] = true;
79  }
80
81  for (int i = 1; i < (int)edges.size(); ++i) {
82    check(graph.id(graph.source(edges[i - 1])) <=
83          graph.id(graph.source(edges[i])), "Test failed");
84  }
85
86}
87
88void checkGraphCounterSort() {
89  typedef SmartGraph Graph;
90  typedef Graph::Node Node;
91  typedef Graph::Edge Edge;
92
93  const int n = 100;
94  const int e = (int)(n * log((double)n));
95
96  Graph graph;
97  vector<Node> nodes;
98
99  for (int i = 0; i < n; ++i) {
100    nodes.push_back(graph.addNode());
101  }
102  vector<Edge> edges;
103  for (int i = 0; i < e; ++i) {
104    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
105    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
106    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
107  }
108
109  counterSort(edges.begin(), edges.end(),
110              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
111                                    sourceMap(graph))));
112
113  counterSort(edges.begin(), edges.end(),
114              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
115                                    targetMap(graph))));
116
117  Graph::EdgeMap<bool> was(graph, false);
118
119  for (int i = 0; i < (int)edges.size(); ++i) {
120    check(!was[edges[i]], "Test failed");
121    was[edges[i]] = true;
122  }
123
124  for (int i = 1; i < (int)edges.size(); ++i) {
125    check(graph.id(graph.target(edges[i - 1])) <
126          graph.id(graph.target(edges[i])) ||
127          (graph.id(graph.target(edges[i - 1])) ==
128           graph.id(graph.target(edges[i])) &&
129           graph.id(graph.source(edges[i - 1])) <=
130           graph.id(graph.source(edges[i]))), "Test failed");
131  }
132
133}
134
135void checkGraphSorts() {
136  checkGraphRadixSort();
137  checkGraphCounterSort();
138}
139
140int main() {
141  checkSorts();
142  checkGraphSorts();
143  return 0;
144}
Note: See TracBrowser for help on using the repository browser.