This program calculates the movements for one representing
triangle in the all-to-all mapping
on a torus consisting of (2k+1)(2k+1) blocks as
an alternative (and more practical) demonstration of Theorem 4.1 in
"Optimal Deterministic Sorting and Routing on Grids and Tori with
Diagonals"[KNRR96a] of
Kunde,
Niedermeier ,
Reinhardt and
Rossmanith .
The program works with units of size 1/(2k+1)(2k+1) and
accordingly with a capacity of (2k+2)(2k+1).
After choosing k and calling the Startposition,
You get those 12(k-1)k/2 units (of the 12(2k+1)(2k+1) units) on the
center block, which have to be distributed on one triangle.
Then You can perform stages.
The source.
The concentrating mapping.
Last modified: 31-May-97 by
Klaus Reinhardt