COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/radix_sort_test.cc @ 2100:6fbe90faf02a

Last change on this file since 2100:6fbe90faf02a was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 4.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#include <lemon/time_measure.h>
20#include <lemon/smart_graph.h>
21#include <lemon/graph_utils.h>
22#include <lemon/maps.h>
23#include <lemon/radix_sort.h>
24
25#include "test_tools.h"
26
27
28#include <vector>
29#include <algorithm>
30#include <cmath>
31
32using namespace std;
33using namespace lemon;
34
35void checkRadixSort() {
36  {
37    int n = 10000;
38    vector<int> data1(n), data2(n);
39    for (int i = 0; i < n; ++i) {
40      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
41    }
42    radixSort(data1.begin(), data1.end());
43    sort(data2.begin(), data2.end());
44    for (int i = 0; i < n; ++i) {
45      check(data1[i] == data2[i], "Test failed");
46    }
47  } {
48    int n = 10000;
49    vector<unsigned char> data1(n), data2(n);
50    for (int i = 0; i < n; ++i) {
51      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
52    }
53    radixSort(data1.begin(), data1.end());
54    sort(data2.begin(), data2.end());
55    for (int i = 0; i < n; ++i) {
56      check(data1[i] == data2[i], "Test failed");
57    }
58  }
59}
60
61
62void checkCounterSort() {
63  {
64    int n = 10000;
65    vector<int> data1(n), data2(n);
66    for (int i = 0; i < n; ++i) {
67      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
68    }
69    counterSort(data1.begin(), data1.end());
70    sort(data2.begin(), data2.end());
71    for (int i = 0; i < n; ++i) {
72      check(data1[i] == data2[i], "Test failed");
73    }
74  } {
75    int n = 10000;
76    vector<unsigned char> data1(n), data2(n);
77    for (int i = 0; i < n; ++i) {
78      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
79    }
80    counterSort(data1.begin(), data1.end());
81    sort(data2.begin(), data2.end());
82    for (int i = 0; i < n; ++i) {
83      check(data1[i] == data2[i], "Test failed");
84    }
85  }
86}
87
88void checkSorts() {
89  checkRadixSort();
90  checkCounterSort();
91}
92
93void checkGraphRadixSort() {
94  typedef SmartGraph Graph;
95  typedef Graph::Node Node;
96  typedef Graph::Edge Edge;
97
98  const int n = 100;
99  const int e = (int)(n * log((double)n));
100
101  Graph graph;
102  vector<Node> nodes;
103
104  for (int i = 0; i < n; ++i) {
105    nodes.push_back(graph.addNode());
106  }
107  vector<Edge> edges;
108  for (int i = 0; i < e; ++i) {
109    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
110    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
111    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
112  }
113
114  radixSort(edges.begin(), edges.end(),
115            mapFunctor(composeMap(IdMap<Graph, Node>(graph),
116                                  sourceMap(graph))));
117
118  Graph::EdgeMap<bool> was(graph, false);
119
120  for (int i = 0; i < (int)edges.size(); ++i) {
121    check(!was[edges[i]], "Test failed");
122    was[edges[i]] = true;
123  }
124
125  for (int i = 1; i < (int)edges.size(); ++i) {
126    check(graph.id(graph.source(edges[i - 1])) <=
127          graph.id(graph.source(edges[i])), "Test failed");
128  }
129
130}
131
132void checkGraphCounterSort() {
133  typedef SmartGraph Graph;
134  typedef Graph::Node Node;
135  typedef Graph::Edge Edge;
136
137  const int n = 100;
138  const int e = (int)(n * log((double)n));
139
140  Graph graph;
141  vector<Node> nodes;
142
143  for (int i = 0; i < n; ++i) {
144    nodes.push_back(graph.addNode());
145  }
146  vector<Edge> edges;
147  for (int i = 0; i < e; ++i) {
148    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
149    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
150    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
151  }
152
153  counterSort(edges.begin(), edges.end(),
154              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
155                                    sourceMap(graph))));
156
157  counterSort(edges.begin(), edges.end(),
158              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
159                                    targetMap(graph))));
160
161  Graph::EdgeMap<bool> was(graph, false);
162
163  for (int i = 0; i < (int)edges.size(); ++i) {
164    check(!was[edges[i]], "Test failed");
165    was[edges[i]] = true;
166  }
167
168  for (int i = 1; i < (int)edges.size(); ++i) {
169    check(graph.id(graph.target(edges[i - 1])) <
170          graph.id(graph.target(edges[i])) ||
171          (graph.id(graph.target(edges[i - 1])) ==
172           graph.id(graph.target(edges[i])) &&
173           graph.id(graph.source(edges[i - 1])) <=
174           graph.id(graph.source(edges[i]))), "Test failed");
175  }
176
177}
178
179void checkGraphSorts() {
180  checkGraphRadixSort();
181  checkGraphCounterSort();
182}
183
184int main() {
185  checkSorts();
186  checkGraphSorts();
187  return 0;
188}
Note: See TracBrowser for help on using the repository browser.