README

   1 libsortnetwork
   2 --------------
   3 <http://octo.cx/sn>
   4
   5 Library for handling comparator networks in general and sort networks in
   6 particular.
   7
   8
   9 Utility applications
  10 --------------------
  11
  12 The distribution includes a number of utility applications for handling sort
  13 networks. Most tools operate in the typical UNIX fashion of reading from STDIN
  14 and writing to STDOUT, so that it is able to chain tools together.
  15
  16 The distribution includes the following utility programs:
  17
  18   * sn-apply
  19     Reads a list of values from STDIN and applies a given comparator network to
  20     the list. The resulting list of printed to STDOUT.
  21
  22   * sn-bitonicsort
  23     Creates a bitonic mergesort network with a given number of inputs and
  24     prints the network to STDOUT. The number of inputs must be a power of two.
  25
  26   * sn-check-bf
  27     Does a brute-force check whether a given comparator network is a sort
  28     network. It tries all 2^n 0-1-combinations resulting in exponential running
  29     time, so only small networks can be tested within a reasonable time.
  30
  31   * sn-cut
  32     Remove an input by assuming positive or negative infinity to be applied to
  33     one input and "winning" or "losing" all comparisons.
  34
  35   * sn-info
  36     Display information about a comparator network in human readable form.
  37
  38   * sn-merge
  39     Combine two sort networks using the odd-even-merge network.
  40
  41   * sn-normalize
  42     Reads a sort network and prints a normalized version to STDOUT. A
  43     normalized sort network is a network in which all comparators face the same
  44     way.
  45
  46   * sn-oddevenmerge
  47     Create an odd-even merge network with a given number of left and right
  48     inputs. The resulting network is printed to STDOUT.
  49
  50   * sn-oddevensort
  51     Creates an odd-even mergesort network with a given number of inputs and
  52     prints the network to STDOUT.
  53
  54   * sn-pairwise
  55     Create a pairwise sorting network based on the paper by Ian Parberry.
  56
  57   * sn-shmoo
  58     Prints a so-called "shmoo chart" of a comparator network to STDOUT. The
  59     running time of this tool is exponential, roughly O(m * 2^n) where m is the
  60     number of stages and n is the number of inputs.
  61
  62   * sn-show
  63     Prints an ASCII version of a sort network to STDOUT.
  64
  65   * sn-tex
  66     Prints the TikZ / TeX sources of a graphic representation of a comparator
  67     network to STDOUT.
  68
  69 Experimental / research applications:
  70
  71   * sn-bb
  72   * sn-bb-merge
  73   * sn-markov
  74   * sn-evolution
  75   * sn-evolution2
  76   * sn-evolution-cut
  77   * sn-evolution-merge
  78
  79
  80 License
  81 -------
  82
  83 The libsortnetwork library is licensed under the GNU Lesser General Public
  84 License, version 2.1 or later (LGPLv2.1+).
  85
  86 Other utility programs included in this distribution, for example
  87 "sn-normalize", are licensed under the GNU General Public License, version 2
  88 (GPLv2). The exact terms of this license can be found in the file "COPYING" in
  89 the top source directory.
  90
  91
  92 Author
  93 ------
  94
  95 libsortnetwork has been written by Florian "octo" Forster.
  96 You can reach Florian at <ff at octo.it>.