test/radix_sort_test.cc
author deba
Wed, 01 Mar 2006 10:17:25 +0000
changeset 1990 15fb7a4ea6be
parent 1844 eaa5f5b855f7
child 2242 16523135943d
permissions -rw-r--r--
Some classes assumed that the GraphMaps should be inherited
from an ObserverBase. These classes parents replaced with
DefaultMap which cause that the graph maps should not be
inherited from the ObserverBase.
     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 
    32 using namespace std;
    33 using namespace lemon;
    34 
    35 void 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 
    62 void 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 
    88 void checkSorts() {
    89   checkRadixSort();
    90   checkCounterSort();
    91 }
    92 
    93 void 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 
   132 void 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 
   179 void checkGraphSorts() {
   180   checkGraphRadixSort();
   181   checkGraphCounterSort();
   182 }
   183 
   184 int main() {
   185   checkSorts();
   186   checkGraphSorts();
   187   return 0;
   188 }