COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/radix_sort_test.cc @ 1955:daca31868d70

Last change on this file since 1955:daca31868d70 was 1844:eaa5f5b855f7, checked in by Balazs Dezso, 18 years ago

Changed implementation and bug fix

File size: 4.1 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  {
19    int n = 10000;
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;
23    }
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");
28    }
29  } {
30    int n = 10000;
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)));
34    }
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");
39    }
40  }
41}
42
43
44void checkCounterSort() {
45  {
46    int n = 10000;
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;
50    }
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");
55    }
56  } {
57    int n = 10000;
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)));
61    }
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");
66    }
67  }
68}
69
70void checkSorts() {
71  checkRadixSort();
72  checkCounterSort();
73}
74
75void checkGraphRadixSort() {
76  typedef SmartGraph Graph;
77  typedef Graph::Node Node;
78  typedef Graph::Edge Edge;
79
80  const int n = 100;
81  const int e = (int)(n * log((double)n));
82
83  Graph graph;
84  vector<Node> nodes;
85
86  for (int i = 0; i < n; ++i) {
87    nodes.push_back(graph.addNode());
88  }
89  vector<Edge> edges;
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]));
94  }
95
96  radixSort(edges.begin(), edges.end(),
97            mapFunctor(composeMap(IdMap<Graph, Node>(graph),
98                                  sourceMap(graph))));
99
100  Graph::EdgeMap<bool> was(graph, false);
101
102  for (int i = 0; i < (int)edges.size(); ++i) {
103    check(!was[edges[i]], "Test failed");
104    was[edges[i]] = true;
105  }
106
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");
110  }
111
112}
113
114void checkGraphCounterSort() {
115  typedef SmartGraph Graph;
116  typedef Graph::Node Node;
117  typedef Graph::Edge Edge;
118
119  const int n = 100;
120  const int e = (int)(n * log((double)n));
121
122  Graph graph;
123  vector<Node> nodes;
124
125  for (int i = 0; i < n; ++i) {
126    nodes.push_back(graph.addNode());
127  }
128  vector<Edge> edges;
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]));
133  }
134
135  counterSort(edges.begin(), edges.end(),
136              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
137                                    sourceMap(graph))));
138
139  counterSort(edges.begin(), edges.end(),
140              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
141                                    targetMap(graph))));
142
143  Graph::EdgeMap<bool> was(graph, false);
144
145  for (int i = 0; i < (int)edges.size(); ++i) {
146    check(!was[edges[i]], "Test failed");
147    was[edges[i]] = true;
148  }
149
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");
157  }
158
159}
160
161void checkGraphSorts() {
162  checkGraphRadixSort();
163  checkGraphCounterSort();
164}
165
166int main() {
167  checkSorts();
168  checkGraphSorts();
169  return 0;
170}
Note: See TracBrowser for help on using the repository browser.