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-bitonicmerge
  23     Creates a bitonic merge network with a given number of left and right
  24     inputs. The resulting network is printed to STDOUT.
  25
  26   * sn-bitonicsort
  27     Creates a bitonic mergesort network with a given number of inputs and
  28     prints the network to STDOUT.
  29
  30   * sn-check-bf
  31     Does a brute-force check whether a given comparator network is a sort
  32     network. It tries all 2^n 0-1-combinations resulting in exponential running
  33     time, so only small networks can be tested within a reasonable time.
  34
  35   * sn-cut
  36     Removes one or more inputs by assuming positive or negative infinity to be
  37     applied to the inputs to remove.
  38
  39   * sn-info
  40     Displays information about a comparator network in human readable form.
  41
  42   * sn-merge
  43     Combines two sort networks using the odd-even or bitonic merge network.
  44
  45   * sn-normalize
  46     Reads a sort network and prints a normalized version to STDOUT. A
  47     normalized sort network is a network in which all comparators face the same
  48     way.
  49
  50   * sn-oddevenmerge
  51     Creates an odd-even merge network with a given number of left and right
  52     inputs. The resulting network is printed to STDOUT.
  53
  54   * sn-oddevensort
  55     Creates an odd-even mergesort network with a given number of inputs and
  56     prints the network to STDOUT.
  57
  58   * sn-pairwisesort
  59     Creates a pairwise sorting network based on the paper by Ian Parberry.
  60     The number of inputs must be a power of two.
  61
  62   * sn-shmoo
  63     Prints a so-called "shmoo chart" of a comparator network to STDOUT. The
  64     running time of this tool is exponential, roughly O(m * 2^n) where m is the
  65     number of stages and n is the number of inputs.
  66
  67   * sn-show
  68     Prints an ASCII version of a sort network to STDOUT.
  69
  70   * sn-svg
  71     Prints the Scalable Vector Graphics (SVG) sources of a graphic
  72     representation of a comparator network to STDOUT.
  73
  74   * sn-tex
  75     Prints the TikZ / TeX sources of a graphic representation of a comparator
  76     network to STDOUT.
  77
  78   * sn-tex-cut
  79     Prints the TikZ / TeX sources of a graphic representation of a cut sequence
  80     to STDOUT.
  81
  82   * sn-transpositionsort
  83     Creates an odd-even transpositionsort network with the given number of
  84     inputs and prints the network to STDOUT.
  85
  86 Experimental / research applications:
  87
  88   * sn-bb
  89   * sn-bb-merge
  90   * sn-count-cuts
  91   * sn-count-markov
  92   * sn-markov
  93   * sn-evolution
  94   * sn-evolution2
  95   * sn-evolution-cut
  96   * sn-evolution-merge
  97
  98
  99 License
 100 -------
 101
 102 The libsortnetwork library is licensed under the GNU Lesser General Public
 103 License, version 2.1 or later (LGPLv2.1+).
 104
 105 Other utility programs included in this distribution, for example
 106 "sn-normalize", are licensed under the GNU General Public License, version 2
 107 (GPLv2). The exact terms of this license can be found in the file "COPYING" in
 108 the top source directory.
 109
 110
 111 Author
 112 ------
 113
 114 libsortnetwork has been written by Florian "octo" Forster.
 115 You can reach Florian at <ff at octo.it>.