1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/radix_sort_test.cc Mon Nov 28 11:14:01 2005 +0000
1.3 @@ -0,0 +1,144 @@
1.4 +#include <lemon/time_measure.h>
1.5 +#include <lemon/smart_graph.h>
1.6 +#include <lemon/graph_utils.h>
1.7 +#include <lemon/maps.h>
1.8 +#include <lemon/radix_sort.h>
1.9 +
1.10 +#include "test_tools.h"
1.11 +
1.12 +
1.13 +#include <vector>
1.14 +#include <algorithm>
1.15 +#include <cmath>
1.16 +
1.17 +using namespace std;
1.18 +using namespace lemon;
1.19 +
1.20 +void checkRadixSort() {
1.21 + int n = 10000;
1.22 + vector<int> data1(n), data2(n);
1.23 + for (int i = 0; i < n; ++i) {
1.24 + data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
1.25 + }
1.26 + radixSort(data1.begin(), data1.end());
1.27 + sort(data2.begin(), data2.end());
1.28 + for (int i = 0; i < n; ++i) {
1.29 + check(data1[i] == data2[i], "Test failed");
1.30 + }
1.31 +}
1.32 +
1.33 +
1.34 +void checkCounterSort() {
1.35 + int n = 10000;
1.36 + vector<int> data1(n), data2(n);
1.37 + for (int i = 0; i < n; ++i) {
1.38 + data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
1.39 + }
1.40 + counterSort(data1.begin(), data1.end());
1.41 + sort(data2.begin(), data2.end());
1.42 + for (int i = 0; i < n; ++i) {
1.43 + check(data1[i] == data2[i], "Test failed");
1.44 + }
1.45 +}
1.46 +
1.47 +void checkSorts() {
1.48 + checkRadixSort();
1.49 + checkCounterSort();
1.50 +}
1.51 +
1.52 +void checkGraphRadixSort() {
1.53 + typedef SmartGraph Graph;
1.54 + typedef Graph::Node Node;
1.55 + typedef Graph::Edge Edge;
1.56 +
1.57 + const int n = 100;
1.58 + const int e = (int)(n * log((double)n));
1.59 +
1.60 + Graph graph;
1.61 + vector<Node> nodes;
1.62 +
1.63 + for (int i = 0; i < n; ++i) {
1.64 + nodes.push_back(graph.addNode());
1.65 + }
1.66 + vector<Edge> edges;
1.67 + for (int i = 0; i < e; ++i) {
1.68 + int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
1.69 + int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
1.70 + edges.push_back(graph.addEdge(nodes[s], nodes[t]));
1.71 + }
1.72 +
1.73 + radixSort(edges.begin(), edges.end(),
1.74 + mapFunctor(composeMap(IdMap<Graph, Node>(graph),
1.75 + sourceMap(graph))));
1.76 +
1.77 + Graph::EdgeMap<bool> was(graph, false);
1.78 +
1.79 + for (int i = 0; i < (int)edges.size(); ++i) {
1.80 + check(!was[edges[i]], "Test failed");
1.81 + was[edges[i]] = true;
1.82 + }
1.83 +
1.84 + for (int i = 1; i < (int)edges.size(); ++i) {
1.85 + check(graph.id(graph.source(edges[i - 1])) <=
1.86 + graph.id(graph.source(edges[i])), "Test failed");
1.87 + }
1.88 +
1.89 +}
1.90 +
1.91 +void checkGraphCounterSort() {
1.92 + typedef SmartGraph Graph;
1.93 + typedef Graph::Node Node;
1.94 + typedef Graph::Edge Edge;
1.95 +
1.96 + const int n = 100;
1.97 + const int e = (int)(n * log((double)n));
1.98 +
1.99 + Graph graph;
1.100 + vector<Node> nodes;
1.101 +
1.102 + for (int i = 0; i < n; ++i) {
1.103 + nodes.push_back(graph.addNode());
1.104 + }
1.105 + vector<Edge> edges;
1.106 + for (int i = 0; i < e; ++i) {
1.107 + int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
1.108 + int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
1.109 + edges.push_back(graph.addEdge(nodes[s], nodes[t]));
1.110 + }
1.111 +
1.112 + counterSort(edges.begin(), edges.end(),
1.113 + mapFunctor(composeMap(IdMap<Graph, Node>(graph),
1.114 + sourceMap(graph))));
1.115 +
1.116 + counterSort(edges.begin(), edges.end(),
1.117 + mapFunctor(composeMap(IdMap<Graph, Node>(graph),
1.118 + targetMap(graph))));
1.119 +
1.120 + Graph::EdgeMap<bool> was(graph, false);
1.121 +
1.122 + for (int i = 0; i < (int)edges.size(); ++i) {
1.123 + check(!was[edges[i]], "Test failed");
1.124 + was[edges[i]] = true;
1.125 + }
1.126 +
1.127 + for (int i = 1; i < (int)edges.size(); ++i) {
1.128 + check(graph.id(graph.target(edges[i - 1])) <
1.129 + graph.id(graph.target(edges[i])) ||
1.130 + (graph.id(graph.target(edges[i - 1])) ==
1.131 + graph.id(graph.target(edges[i])) &&
1.132 + graph.id(graph.source(edges[i - 1])) <=
1.133 + graph.id(graph.source(edges[i]))), "Test failed");
1.134 + }
1.135 +
1.136 +}
1.137 +
1.138 +void checkGraphSorts() {
1.139 + checkGraphRadixSort();
1.140 + checkGraphCounterSort();
1.141 +}
1.142 +
1.143 +int main() {
1.144 + checkSorts();
1.145 + checkGraphSorts();
1.146 + return 0;
1.147 +}