readme

生成直角Steiner树的程序包

		@RC	Experimental output from -R switch.
		@UO
		@UN	This pair of messages is emitted every time the
			upper bound gets tighter.  They contain the CPU
			time and the old/new bound, as well as the
			old/new gap percentages.  These can be plotted
			(i.e., using gnuplot) to graphically show the
			convergence rate of the algorithm.

prunefst
	- Reduce the set of FSTs generated by "rfst" or "efst" while
	  still retaining at least one optimal solution among the
	  remaining set of FSTs.  This program can reduce the time to
	  solve the FST concatenation problem considerably, but is
	  only worthwhile for large instances.  The following options
	  are permitted:

		-d txt	Description of problem instance.
		-f E	Epsilon multiplication factor for floating
			point comparisons.  Default is 32.
		-t	Print detailed timings to stderr.

dumpfst	- Dumps information about the FSTs generated by "rfst" and
	  "efst" in a readable form.  There are two forms of this
	  command, each producing different types of output.  The first
	  form of the command is obtained whenever the -d or -h switches
	  are used.  These switches provide summary information ONLY --
	  FST statistics, and/or a histogram of FST sizes:

		dumpfst [-d | -h [-a]] <FSTs

	  where the switches

		-d	Display statistics about FSTs.
		-h	Display histogram of FST sizes.
		-a	Include all FSTs in histogram, even those that
			were "pruned" by the FST generator or a pruning
			algorithm.

	  The second form of the command is obtained when neither -d nor
	  -h are specified.  This form dumps all of the FSTs in a
	  readable form.  Each line of output represents a single FST,
	  listing its terminal numbers (0 through N-1).  The terminals
	  are listed in the same order that they occur in the actual
	  data structures, although they can optionally be sorted in
	  numeric order.  The length of each FST can optionally be
	  appended to each line:

		dumpfst [-als] <FSTs

	  The command line switches are:

		-a	Include all FSTs, even those that were "pruned"
			by the FST generator or a pruning algorithm.
		-l	Append the FST length to each output line.
		-s	Terminals of each FST are listed in numeric
			(sorted) order instead of internal order.

plotfst	- Program to generate various plots of FSTs in an FST data
	  file.  Reads the FST data file on stdin and produces
	  postscript on stdout for the plots indicated by the command
	  line switches:

		-f	Prints all FSTs, 12 FSTs per page.
		-g	Prints FSTs in "grouped" fashion, 12 groups per
			page.
		-o	Prints all FSTs overlaid together.
		-p	Prints only the points, no FSTs.

	  Note that the file "prelude.ps" must be PREPENDED to the
	  output of this program in order to have a complete postscript
	  document.

fst2graph
	- Reads FSTs from stdin and produces an (ordinary) graph
	  on stdout representing the FSTs.  For the rectilinear
	  problem, the FSTs are overlaid on the Hanan grid and the
	  remaining Hanan grid is output.  For the Euclidean problem
	  the set of all terminals and Steiner points in all FSTs
	  forms the set of vertices and the line segments the edges.
	  Output data is printed in OR-Library format by default, but
	  the SteinLib format is also supported:

		-d txt	Description of problem instance.
		-s	Prints data in SteinLib format.
		-e	Generate edge graph for the rectilinear problem.
		-u	Output unscaled (fractional) data for the
			rectilinear problem.

kr	- Reads a point set from stdin.  It then computes a minimum
	  spanning tree, and a heuristic Steiner tree using the
	  1-Steiner heuristic of Kahng and Robins.  The plots go to
	  stdout in "incomplete" postscript form.  Prepend the
	  "prelude.ps" file to obtain a printable postscript file.  This
	  implementation of 1-Steiner is substantially slower than
	  Robins' own code.  The following switches are permitted:

		-k	Skip the Kahng-Robins heuristic.

		-l T	Set a CPU time limit of T, which may be
			expressed for example as 1day4hours20min30sec,
			1d4h20m30s, 10000s, 300m, etc.

		-m	Skip the minimum spanning tree.


Examples of Program Invocation
==============================

The following command will generate a set of 70 random points and
compute a rectilinear Steiner minimal tree for it:

	rand_points 70 | rfst | bb

The following computes an ESMT for the same set of points:

	rand_points 70 | efst | bb

Note that rand_points always generates the same sequence of points
unless given the `-r' or `-s seed' option.

The following (Bourne shell) examples can be used to generate complete
printable postscript plots for these problems:

	(cat prelude.ps; rand_points 70 | rfst | bb) >rsmt70.ps

	(cat prelude.ps; rand_points 70 | efst | bb) >esmt70.ps

The complete set of FSTs can also be plotted as follows:

	(cat prelude.ps; rand_points 70 | rfst | plotfst -fgo) >rfsts.ps

	(cat prelude.ps; rand_points 70 | efst | plotfst -fgo) >efsts.ps

A reduced Hanan grid in the OR-Library format (for the rectilinear
problem) can be generated as follows:

	rand_points 70 | rfst | fst2graph

By pruning the set of FSTs an even more reduced grid graph can be
generated:

	rand_points 70 | rfst | prunefst | fst2graph

An Euclidean Steiner minimal tree for the "berlin52.tsp" instance from
TSPLIB can be constructed and displayed as follows (assuming that the
file "berlin52.tsp" is present in your GeoSteiner directory):

	(cat prelude.ps; cat berlin52.tsp | lib_points | efst | bb) | \
		ghostview -


Overview of the Source Code
===========================

The GeoSteiner source code resides entirely in the top-level
directory.  There is a single subdirectory "lp_solve_2.3" that contains
the source code for a *CUSTOMIZED* version of this public-domain LP
solver written by Michel Berkelaar and Jeroen Dirks.  For a description
of the changes we have made to this package, see the file:

	lp_solve_2.3/README.custom

The original unmodified distribution of lp_solve_2.3 can be obtained
from:

	ftp://ftp.es.ele.tue.nl/pub/lp_solve


Detailed description of each file in the GeoSteiner distribution:

bb.c		(Branch-and-cut)
	All of the gory details of the branch-and-cut algorithm.  The
	various separation procedures are called from this file, but
	are defined in other files.

bb.h		(Branch-and-cut)
	Data structures and function prototypes pertaining to the
	branch-and-bound / branch-and-cut algorithm.

bbmain.c	(Main program)
	The main routine for the "bb" program.

bbsubs.c	(Branch-and-cut)
	Low-level subroutines of the branch-and-cut.

bbsubs.h	(Branch-and-cut)
	Declarations of low-level branch-and-cut routines.

bmst.c		(FST generator, miscellaneous utility)
	Routines to compute the MST of a subset of the terminals using
	the bottleneck Steiner distance as the metric.

bsd.c		(FST generator, miscellaneous utility)
	Routines to compute the bottleneck Steiner distance between two
	terminals.

bsd.h		(FST generator, miscellaneous utility)
	Data structures and function prototypes pertaining to the
	bottleneck Steiner distance routines.

btsearch.c      (FST pruning)
	Routines to perform backtrack search for a solution.  Faster
	than branch-and-cut for small instances.

btsearch.h	(FST pruning)
	Declarations for the special backtrack search used by the FST
	pruning code.

config.h	(General utility)
	Created by running the ./configure script.  Defines various
	constants and switches that control the configuration of
	GeoSteiner 3.1.  This file is automatically generated from the
	template file `config.h.in'.

constrnt.c	(Branch-and-cut)
	Routines that maintain the constraint pool and the constraints
	currently in the LP tableaux.  Most of the details of
	interfacing to a particular LP solver reside in this file.

constrnt.h	(Branch-and-cut)
	Data structures and function prototypes pertaining to
	constraints and the constraint pool.

cpulimit.c	(Utility)
	Routines for monitoring and limiting CPU time usage by a
	program.

cputime.c	(Utility)
	Routines for metering CPU time usage, and converting CPU times
	into printable form.

cra.c		(Utility)
	Closest rational approximation routine.

		(Utility)
cra.h	Declaration of closest rational approximation routine.

cutset.c	(Branch-and-cut)
	The separation routines for finding violated cutset constraints
	-- a fast one that identifies cutsets of zero weight (connected
	components), and another for finding fractional weight cutsets.

cutset.h	(Branch-and-cut)
	Data structures and function prototypes pertaining to the cutset
	separation algorithms.

cutsubs.c	(Branch-and-cut)
	Subroutines for processing of violated cutset constraints.

dsuf.c		(Utility)
	A general disjoint-set union-find data structure.

dsuf.h		(Utility)
	Data structures and function prototypes pertaining to the
	disjoint-set union-find routines.

dumpfst.c	(Main program)
	Main routine for a utility program to dump FSTs in a meaningful
	format.

efst.c		(Main program)
	Main routine for the Euclidean FST generator.  The bulk of the
	EFST generation algorithm resides in this file.

efst.h		(Euclidean FST generator)
	Data structures and function prototypes pertaining to the
	Euclidean FST generator.

efuncs.h	(Euclidean FST generator)
	Basic plane geometry functions used by Euclidean FST generator
        and pruning algorithms.

egmp.c		(Euclidean FST generator)
	Support routines for the EFST generator that use the GNU
	Multi-Precision arithmetic library (GMP -- if we have
        it) to compute certain items with high accuracy.

	        (Euclidean FST generator)
egmp.h	Declarations for GMP support routines.

emptyr.c	(Rectilinear FST generator)
	Routines to quickly determine whether or not a given pair of
	terminals define an empty rectangle or not.  This information is
	computed as part of the preprocessing step before recursively
	growing rectilinear FSTs.

emptyr.h	(Rectilinear FST generator)
	Data structures and function prototypes pertaining to the empty
	rectangle testing routines.

emst.c		(Euclidean FST generator)
	Routines to compute Euclidean minimum spanning trees.

expand.c	(Branch-and-cut)
	Subroutine to expand logical constraints into physical form.

flow.c		(Branch-and-cut)
	A general purpose maximum-flow network solver.  It uses the very
	standard method -- breadth-first search to find an augmenting
	path.  It is used in three of the separation procedures: the one
	for fractional cutsets, the heuristic flow formulation for
	SEC's, and the deterministic flow formulation for SEC's.

flow.h		(Branch-and-cut)
	Data structures and function prototypes pertaining to the
	general network maximum-flow solver.

fst2graph.c	(Main program)
	The main routine to generate ordinary graphs from FST.

genps.c		(Utility)
	Routines for generating postscript plots of things.

genps.h		(Utility)
	Data structures and function prototypes pertaining to the
	postscript generation routines.

greedy.c	(Euclidean FST generator)
	Implementation of greedy O(n^2) heuristic for computing
	Euclidean Steiner trees (Algorithmica 25, 418-437, 1999).

io.c		(Utility)
	Routines for reading in coordinates, and converting coordinate
	values and distances into printable form.  It also performs
	scaling of coordinates and distances to and from the internal
	representation, which strives to store coordinates exactly as
	INTEGER values stored in floating point variables.

kr.c		(Main program)
	The main program for the "kr" program, which plots minimum
	spanning trees and heuristic Steiner trees using the 1-Steiner
	heuristic of Kahng and Robins.

lib_points.c	(Main program)
	Conversion of OR-LIBRARY or TSPLIB files into a "clean" set of
        points that can be read by "rfst" or "efst".