TOMS456
Routing Problem

TOMS456 is a FORTRAN77 program, using single precision arithmetic, which implements ACM TOMS algorithm 456, for the routing problem.

While the text of many ACM TOMS algorithms is available online through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html, most of the early algorithms are not available. This is one of them. I typed it in.

Related Programs and Data:

CITIES is a library of FORTRAN90 routines for various problems associated with a set of "cities" on a map.

CITIES contains some sets of intercity distances that can be used with this code.

LAU_NP includes a routine for the heuristic solution of the traveling salesman problem.

Usage:

call routng ( n, p, sn, en, m, d, l, r )

N is the number of nodes,
P is the node number index, but on output is replaced by the optimal connection,
SN and EN are the start and end nodes,
M is the order of the distance matrix,
D is the distance matrix,
L is output as the length of the shortest connection,
R is the number of runs (that is, the number of iterations of the algorithm. This should be less than or equal to 2*N).

Reference:

1. Zdenek Fencl,
   Algorithm 456: Routing Problem,
   Communications of the ACM,
   Volume 16, Number 9, September 1973, pages 572-574.

Source Code:

• toms456.f, the source code.
• toms456.csh, commands to compile the source code.

Examples and Tests:

• toms456_prb.f, a sample calling program.
• toms456_prb.csh, commands to compile and run the sample program.
• toms456_prb.out, the output from a run of the sample program.

List of Routines:

• ROUTNG finds the shortest serial branchless connection between N nodes of a net beginning at a start node SN and terminating at the end node EN.

You can go up one level to the FORTRAN77 source codes.