# HG changeset patch
# User deba
# Date 1133176441 0
# Node ID 6d107b0b6b46937c2cbed3f6edc9583e6abdd247
# Parent  d0c28d9c9141673475be09d77a02bc1b57c787f4
Radix sort algorithm

diff -r d0c28d9c9141 -r 6d107b0b6b46 benchmark/Makefile.am
--- a/benchmark/Makefile.am	Thu Nov 24 15:48:53 2005 +0000
+++ b/benchmark/Makefile.am	Mon Nov 28 11:14:01 2005 +0000
@@ -2,10 +2,12 @@
 
 noinst_HEADERS = bench_tools.h
 
-noinst_PROGRAMS = graph-bench hcube bfs-bench
+noinst_PROGRAMS = graph-bench hcube bfs-bench radix_sort-bench
 
 graph_bench_SOURCES = graph-bench.cc
 
 hcube_SOURCES = hcube.cc
 
 bfs_bench_SOURCES = bfs-bench.cc
+
+radix_sort_bench_SOURCES = radix_sort-bench.cc
diff -r d0c28d9c9141 -r 6d107b0b6b46 benchmark/radix_sort-bench.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/benchmark/radix_sort-bench.cc	Mon Nov 28 11:14:01 2005 +0000
@@ -0,0 +1,70 @@
+#define NDEBUG
+
+#include <lemon/time_measure.h>
+#include <lemon/smart_graph.h>
+#include <lemon/graph_utils.h>
+#include <lemon/maps.h>
+#include <lemon/error.h>
+
+#include <lemon/radix_sort.h>
+
+#include <vector>
+#include <algorithm>
+#include <cmath>
+
+using namespace std;
+using namespace lemon;
+
+void testRadixSort() {
+  int n = 10000000;
+  vector<int> data(n);
+  for (int i = 0; i < n; ++i) {
+    data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+  }
+  radixSort(data.begin(), data.end());
+}
+
+
+void testCounterSort() {
+  int n = 10000000;
+  vector<int> data(n);
+  for (int i = 0; i < n; ++i) {
+    data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+  }
+  counterSort(data.begin(), data.end());
+}
+
+void testSort() {
+  int n = 10000000;
+  vector<int> data(n);
+  for (int i = 0; i < n; ++i) {
+    data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+  }
+  sort(data.begin(), data.end());
+}
+
+void testStableSort() {
+  int n = 10000000;
+  vector<int> data(n);
+  for (int i = 0; i < n; ++i) {
+    data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+  }
+  stable_sort(data.begin(), data.end());
+}
+
+void testSorts() {
+  {
+    int n = 10000000;
+    vector<int> data(n);
+  }
+  cout << "Radix sort: " << runningTimeTest(testRadixSort, 60) << endl;
+  cout << "Counter sort: " << runningTimeTest(testCounterSort, 60) << endl;
+  cout << "Standard sort: " << runningTimeTest(testSort, 60) << endl;
+  cout << "Stable sort: " << runningTimeTest(testStableSort, 60) << endl;
+}
+
+
+int main() {
+  testSorts();
+  return 0;
+}
diff -r d0c28d9c9141 -r 6d107b0b6b46 lemon/Makefile.am
--- a/lemon/Makefile.am	Thu Nov 24 15:48:53 2005 +0000
+++ b/lemon/Makefile.am	Mon Nov 28 11:14:01 2005 +0000
@@ -57,6 +57,7 @@
 	preflow.h \
 	path.h \
 	radix_heap.h \
+	radix_sort.h \
 	smart_graph.h \
 	time_measure.h \
 	topology.h \
diff -r d0c28d9c9141 -r 6d107b0b6b46 lemon/radix_sort.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/radix_sort.h	Mon Nov 28 11:14:01 2005 +0000
@@ -0,0 +1,483 @@
+/* -*- C++ -*-
+ * lemon/radix_sort.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef RADIX_SORT_H
+#define RADIX_SORT_H
+
+/// \ingroup auxdat
+/// \file
+/// \brief Radix sort
+///
+
+#include <vector>
+#include <limits>
+#include <iterator>
+#include <algorithm>
+
+#include <lemon/error.h>
+
+namespace lemon {
+
+  namespace _radix_sort_bits {
+
+    template <typename Value>
+    struct Identity {
+      const Value& operator()(const Value& val) {
+	return val;
+      }
+    };
+
+  }
+
+  template <typename Value, typename Iterator, typename Functor>
+  Iterator radixSortPartition(Iterator first, Iterator last, 
+			      Functor functor, Value mask) {
+    while (first != last && !(functor(*first) & mask)) {
+      ++first;
+    }
+    if (first == last) {
+      return first;
+    }
+    --last;
+    while (first != last && (functor(*last) & mask)) {
+      --last;
+    }
+    if (first == last) {
+      return first;
+    }
+    std::iter_swap(first, last);
+    ++first;
+    if (!(first < last)) {
+      return first;
+    }
+    while (true) {
+      while (!(functor(*first) & mask)) {
+	++first;
+      }
+      --last;
+      while (functor(*last) & mask) {
+	--last;
+      }
+      if (!(first < last)) {
+	return first;
+      }
+      std::iter_swap(first, last);
+      ++first;
+    }
+  }
+
+  template <typename Iterator, typename Functor>
+  Iterator radixSortSignPartition(Iterator first, Iterator last, 
+				  Functor functor) {
+    while (first != last && functor(*first) < 0) {
+      ++first;
+    }
+    if (first == last) {
+      return first;
+    }
+    --last;
+    while (first != last && functor(*last) >= 0) {
+      --last;
+    }
+    if (first == last) {
+      return first;
+    }
+    std::iter_swap(first, last);
+    ++first;
+    if (!(first < last)) {
+      return first;
+    }
+    while (true) {
+      while (functor(*first) < 0) {
+	++first;
+      }
+      --last;
+      while (functor(*last) >= 0) {
+	--last;
+      }
+      if (!(first < last)) {
+	return first;
+      }
+      std::iter_swap(first, last);
+      ++first;
+    }
+  }
+
+  template <typename Value, typename Iterator, typename Functor>
+  void radixIntroSort(Iterator first, Iterator last, 
+		      Functor functor, Value mask) {
+    while (mask != 0 && last - first > 1) {
+      Iterator cut = radixSortPartition(first, last, functor, mask);
+      mask >>= 1;
+      radixIntroSort(first, cut, functor, mask);
+      first = cut;
+    }
+  }
+
+  template <typename Value, typename Iterator, typename Functor>
+  void radixSignedSort(Iterator first, Iterator last, Functor functor) {
+    Iterator cut = radixSortSignPartition(first, last, functor);
+
+    Value mask;
+    int max_digit;
+    Iterator it;
+
+    mask = 0; max_digit = 0;
+    for (it = first; it != cut; ++it) {
+      if ((mask | functor(*it)) != ~0) {
+	++max_digit;
+	mask <<= 1; 
+	mask |= 1;
+      }
+    }
+    radixIntroSort(first, cut, functor, 1 << max_digit);
+
+    mask = ~0; max_digit = 0;
+    for (it = cut; it != last; ++it) {
+      if (mask & functor(*it)) {
+	++max_digit;
+	mask <<= 1;
+      }
+    }
+    radixIntroSort(cut, last, functor, 1 << max_digit);
+  }
+
+  template <typename Value, typename Iterator, typename Functor>
+  void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
+
+    Value mask = ~0;
+    int max_digit = 0;
+
+    Iterator it;
+    for (it = first; it != last; ++it) {
+      if (mask & functor(*it)) {
+	++max_digit;
+	mask <<= 1;
+      }
+    }
+    radixIntroSort(first, last, functor, 1 << max_digit);
+  }
+
+  namespace _radix_sort_bits {
+
+    template <typename Value, 
+	      bool sign = std::numeric_limits<Value>::is_signed >
+    struct RadixSortSelector {
+      template <typename Iterator, typename Functor>
+      static void sort(Iterator first, Iterator last, Functor functor) {
+	radixSignedSort<Value>(first, last, functor);
+      }
+    };
+
+    template <typename Value>
+    struct RadixSortSelector<Value, false> {
+      template <typename Iterator, typename Functor>
+      static void sort(Iterator first, Iterator last, Functor functor) {
+	radixUnsignedSort<Value>(first, last, functor);
+      }
+    };
+
+  }
+
+  /// \ingroup auxdat
+  ///
+  /// \brief Sorts the stl compatible range into ascending order.
+  ///
+  /// The \c radixSort sorts the stl compatible range into ascending order.
+  /// The radix sort algorithm can sort the items which mapped to an
+  /// integer by the adaptable unary function \c functor and the order
+  /// will be ascending by these mapped values. As function specialization
+  /// there is possible to use a normal function as the functor object
+  /// or if the functor is not given it will use an identity function instead.
+  ///
+  /// This implemented radix sort is a special quick sort which pivot value
+  /// is choosen to partite the items on the next bit. This way, let be
+  /// \c c the maximal capacity and \c n the number of the items in
+  /// the container, the time complexity of the algorithm \c O(log(c)*n)
+  /// and the additional space complexity is \c O(log(c)).
+  ///
+  /// \param first The begin of the given range.
+  /// \param last The end of the given range.
+  /// \param functor An adaptible unary function or a normal function which
+  /// maps the items to any integer type which can be wheter signed or 
+  /// unsigned.
+  template <typename Iterator, typename Functor>
+  void radixSort(Iterator first, Iterator last, Functor functor) {
+    using namespace _radix_sort_bits;
+    typedef typename Functor::result_type Value;
+    RadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
+    using namespace _radix_sort_bits;
+    RadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
+    using namespace _radix_sort_bits;
+    RadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
+    using namespace _radix_sort_bits;
+    RadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
+    using namespace _radix_sort_bits;
+    RadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator>
+  void radixSort(Iterator first, Iterator last) {
+    using namespace _radix_sort_bits;
+    typedef typename std::iterator_traits<Iterator>::value_type Value;
+    RadixSortSelector<Value>::sort(first, last, Identity<Value>());
+  }
+
+  template <typename Value>
+  unsigned char valueByte(Value value, int byte) {
+    return *((unsigned char *)(&value) + byte);
+  }
+
+  template <typename Functor, typename Key>
+  void counterIntroSort(Key *first, Key *last, Key *target, 
+		       int byte, Functor functor) {
+    const int size = 
+      (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
+    int counter[size];
+    for (int i = 0; i < size; ++i) {
+      counter[i] = 0;
+    }
+    Key *it = first;
+    while (first != last) {
+      ++counter[valueByte(functor(*first), byte)]; 
+      ++first;
+    }
+    int prev, num = 0;
+    for (int i = 0; i < size; ++i) {
+      prev = num;
+      num += counter[i];
+      counter[i] = prev;
+    }
+    while (it != last) {
+      target[counter[valueByte(functor(*it), byte)]++] = *it;
+      ++it;
+    }
+  }
+
+  template <typename Functor, typename Key>
+  void signedCounterIntroSort(Key *first, Key *last, Key *target, 
+			     int byte, Functor functor) {
+    const int size = 
+      (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
+    int counter[size];
+    for (int i = 0; i < size; ++i) {
+      counter[i] = 0;
+    }
+    Key *it = first;
+    while (first != last) {
+      counter[valueByte(functor(*first), byte)]++;
+      ++first;
+    }
+    int prev, num = 0;
+    for (int i = size / 2; i < size; ++i) {
+      prev = num;
+      num += counter[i];
+      counter[i] = prev;
+    }
+    for (int i = 0; i < size / 2; ++i) {
+      prev = num;
+      num += counter[i];
+      counter[i] = prev;
+    }
+    while (it != last) {
+      target[counter[valueByte(functor(*it), byte)]++] = *it;
+      ++it;
+    }
+  }
+
+  
+  template <typename Value, typename Iterator, typename Functor>
+  void counterSignedSort(Iterator first, Iterator last, Functor functor) {
+    typedef typename std::iterator_traits<Iterator>::value_type Key;
+    typedef std::allocator<Key> Allocator;
+    Allocator allocator;
+
+    int length = std::distance(first, last);
+    Key* buffer;
+    buffer = allocator.allocate(2 * length);
+    try {
+      bool dir = true;
+      std::copy(first, last, buffer);
+      for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
+	if (dir) {
+	  counterIntroSort(buffer, buffer + length, buffer + length, 
+			   i, functor);
+	} else {
+	  counterIntroSort(buffer + length, buffer + 2 * length, buffer, 
+			   i, functor);
+	}
+	dir = !dir;
+      }
+      if (dir) {
+	signedCounterIntroSort(buffer, buffer + length, buffer + length, 
+			       sizeof(Value) - 1, functor);
+	std::copy(buffer + length, buffer + 2 * length, first);
+      }	else {
+	signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer, 
+			       sizeof(Value) - 1, functor);
+	std::copy(buffer, buffer + length, first);
+      }
+    } catch (...) {
+      allocator.deallocate(buffer, 2 * length);
+      throw;
+    }
+    allocator.deallocate(buffer, 2 * length);
+  }
+
+  template <typename Value, typename Iterator, typename Functor>
+  void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
+    typedef typename std::iterator_traits<Iterator>::value_type Key;
+    typedef std::allocator<Key> Allocator;
+    Allocator allocator;
+
+    int length = std::distance(first, last);
+    Key *buffer;
+    buffer = allocator.allocate(2 * length);
+    try {
+      bool dir = true;
+      std::copy(first, last, buffer);
+      for (int i = 0; i < sizeof(Value); ++i) {
+	if (dir) {
+	  counterIntroSort(buffer, buffer + length, buffer + length, 
+			   i, functor);
+	} else {
+	  counterIntroSort(buffer + length, buffer + 2 * length, buffer, 
+			   i, functor);
+	}
+	dir = !dir;
+      }
+      if (dir) {
+	std::copy(buffer, buffer + length, first);
+      }	else {
+	std::copy(buffer + length, buffer + 2 * length, first);
+      }
+    } catch (...) {
+      allocator.deallocate(buffer, 2 * length);
+      throw;
+    }
+    allocator.deallocate(buffer, 2 * length);
+  }
+
+  namespace _radix_sort_bits {
+
+    template <typename Value, 
+	      bool sign = std::numeric_limits<Value>::is_signed >
+    struct CounterSortSelector {
+      template <typename Iterator, typename Functor>
+      static void sort(Iterator first, Iterator last, Functor functor) {
+	counterSignedSort<Value>(first, last, functor);
+      }
+    };
+
+    template <typename Value>
+    struct CounterSortSelector<Value, false> {
+      template <typename Iterator, typename Functor>
+      static void sort(Iterator first, Iterator last, Functor functor) {
+	counterUnsignedSort<Value>(first, last, functor);
+      }
+    };
+
+  }
+
+  /// \ingroup auxdat
+  ///
+  /// \brief Sorts stable the stl compatible range into ascending order.
+  ///
+  /// The \c counterSort sorts the stl compatible range into ascending order.
+  /// The counter sort algorithm can sort the items which mapped to an
+  /// integer by the adaptable unary function \c functor and the order
+  /// will be ascending by these mapped values. As function specialization
+  /// there is possible to use a normal function as the functor object
+  /// or if the functor is not given it will use an identity function instead.
+  ///
+  /// This implemented counter sort use a radix forward sort on the bytes of
+  /// the integer. The algorithm can sort the items on a given byte. 
+  /// First time it counts how many times occurs a byte value in the container.
+  /// By the occurence number it is possible to copy the container
+  /// in the right order in \c O(n) time. The algorithm sorts the container
+  /// by each bytes in forward direction which sorts the container by the
+  /// whole value. This way, let be
+  /// \c c the maximal capacity and \c n the number of the items in
+  /// the container, the time complexity of the algorithm \c O(log(c)*n)
+  /// and the additional space complexity is \c O(n).
+  ///
+  /// This sorting algorithm is stable so the order of two equal element
+  /// stay in the same order.
+  ///
+  /// \param first The begin of the given range.
+  /// \param last The end of the given range.
+  /// \param functor An adaptible unary function or a normal function which
+  /// maps the items to any integer type which can be wheter signed or 
+  /// unsigned.
+  template <typename Iterator, typename Functor>
+  void counterSort(Iterator first, Iterator last, Functor functor) {
+    using namespace _radix_sort_bits;
+    typedef typename Functor::result_type Value;
+    CounterSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
+    using namespace _radix_sort_bits;
+    CounterSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
+    using namespace _radix_sort_bits;
+    CounterSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
+    using namespace _radix_sort_bits;
+    CounterSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
+    using namespace _radix_sort_bits;
+    CounterSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator>
+  void counterSort(Iterator first, Iterator last) {
+    using namespace _radix_sort_bits;
+    typedef typename std::iterator_traits<Iterator>::value_type Value;
+    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
+  }
+
+}
+
+
+
+#endif
diff -r d0c28d9c9141 -r 6d107b0b6b46 test/Makefile.am
--- a/test/Makefile.am	Thu Nov 24 15:48:53 2005 +0000
+++ b/test/Makefile.am	Mon Nov 28 11:14:01 2005 +0000
@@ -26,6 +26,7 @@
 	suurballe_test \
 	path_test \
 	preflow_test \
+	radix_sort_test \
 	test_tools_fail \
 	test_tools_pass \
 	time_measure_test \
@@ -59,6 +60,7 @@
 max_matching_test_SOURCES = max_matching_test.cc
 suurballe_test_SOURCES = suurballe_test.cc
 path_test_SOURCES = path_test.cc
+radix_sort_test_SOURCES = radix_sort_test.cc
 preflow_test_SOURCES = preflow_test.cc
 time_measure_test_SOURCES = time_measure_test.cc
 test_tools_fail_SOURCES = test_tools_fail.cc
diff -r d0c28d9c9141 -r 6d107b0b6b46 test/radix_sort_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/radix_sort_test.cc	Mon Nov 28 11:14:01 2005 +0000
@@ -0,0 +1,144 @@
+#include <lemon/time_measure.h>
+#include <lemon/smart_graph.h>
+#include <lemon/graph_utils.h>
+#include <lemon/maps.h>
+#include <lemon/radix_sort.h>
+
+#include "test_tools.h"
+
+
+#include <vector>
+#include <algorithm>
+#include <cmath>
+
+using namespace std;
+using namespace lemon;
+
+void checkRadixSort() {
+  int n = 10000;
+  vector<int> data1(n), data2(n);
+  for (int i = 0; i < n; ++i) {
+    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+  }
+  radixSort(data1.begin(), data1.end());
+  sort(data2.begin(), data2.end());
+  for (int i = 0; i < n; ++i) {
+    check(data1[i] == data2[i], "Test failed");
+  }
+}
+
+
+void checkCounterSort() {
+  int n = 10000;
+  vector<int> data1(n), data2(n);
+  for (int i = 0; i < n; ++i) {
+    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+  }
+  counterSort(data1.begin(), data1.end());
+  sort(data2.begin(), data2.end());
+  for (int i = 0; i < n; ++i) {
+    check(data1[i] == data2[i], "Test failed");
+  }
+}
+
+void checkSorts() {
+  checkRadixSort();
+  checkCounterSort();
+}
+
+void checkGraphRadixSort() {
+  typedef SmartGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
+
+  const int n = 100;
+  const int e = (int)(n * log((double)n));
+
+  Graph graph;
+  vector<Node> nodes;
+
+  for (int i = 0; i < n; ++i) {
+    nodes.push_back(graph.addNode());
+  }
+  vector<Edge> edges;
+  for (int i = 0; i < e; ++i) {
+    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
+    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
+    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
+  }
+
+  radixSort(edges.begin(), edges.end(), 
+	    mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
+				  sourceMap(graph))));
+
+  Graph::EdgeMap<bool> was(graph, false);
+
+  for (int i = 0; i < (int)edges.size(); ++i) {
+    check(!was[edges[i]], "Test failed");
+    was[edges[i]] = true;
+  }
+
+  for (int i = 1; i < (int)edges.size(); ++i) {
+    check(graph.id(graph.source(edges[i - 1])) <= 
+	  graph.id(graph.source(edges[i])), "Test failed");
+  }
+
+}
+
+void checkGraphCounterSort() {
+  typedef SmartGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
+
+  const int n = 100;
+  const int e = (int)(n * log((double)n));
+
+  Graph graph;
+  vector<Node> nodes;
+
+  for (int i = 0; i < n; ++i) {
+    nodes.push_back(graph.addNode());
+  }
+  vector<Edge> edges;
+  for (int i = 0; i < e; ++i) {
+    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
+    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
+    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
+  }
+
+  counterSort(edges.begin(), edges.end(), 
+	      mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
+				    sourceMap(graph))));
+
+  counterSort(edges.begin(), edges.end(), 
+	      mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
+				    targetMap(graph))));
+
+  Graph::EdgeMap<bool> was(graph, false);
+
+  for (int i = 0; i < (int)edges.size(); ++i) {
+    check(!was[edges[i]], "Test failed");
+    was[edges[i]] = true;
+  }
+
+  for (int i = 1; i < (int)edges.size(); ++i) {
+    check(graph.id(graph.target(edges[i - 1])) < 
+	  graph.id(graph.target(edges[i])) || 
+	  (graph.id(graph.target(edges[i - 1])) ==
+	   graph.id(graph.target(edges[i])) &&
+	   graph.id(graph.source(edges[i - 1])) <= 
+	   graph.id(graph.source(edges[i]))), "Test failed");
+  }
+
+}
+
+void checkGraphSorts() {
+  checkGraphRadixSort();
+  checkGraphCounterSort();
+}
+
+int main() {
+  checkSorts();
+  checkGraphSorts();
+  return 0;
+}