changelog

生成直角Steiner树的程序包

	* Tossed a fragmentation grenade into the file utils.c, leaving
	only four routines left in it!  All of which are reasonably
	general.  The other routines were either deleted from lack of use,
	or were moved into more appropriate files.

	* Upgraded from lp_solve version 2.0 to version 2.3.  As it turns
	out, the authors of that package have found *ALMOST* all of the
	same bugs that I have!  Oh well, I was hoping for a major
	improvement in its robustness.  Staying reasonably current has its
	advantages, however.

	* Modified lp_solve to recover better from failures to invert the
	matrix, and to detect loss of primal feasibility.  Also changed
	all of its error messages to print to stdout as postscript
	comments rather than to stderr as postscript trash.  Added quite a
	bit of debugging code to try to figure out why it is so unstable.
	Answer: not very picky about the pivots it picks!  Need to USE the
	lattitude afforded by the primal/dual simplex algorithms to find
	better pivots.  This would steer us away from singular bases in
	the long run!

	* Eliminated data.c.  All of the command line switch flags have
	now been moved to the various main program files (they are no
	longer declared in steiner.h either), the one_bits_in_byte stuff
	died with the backtrack search, Data_Num_Decimal_Places and Metric
	now reside in the cinfo, and nbits moved into utils.c where it is
	initialized.

	* Retired cra.c -- a closest rational approximation.  This was an
	attempt to improve the submodular SEC separator by getting rid of
	numeric noise in the LP solution vectors.

	* Retired mem.c.  Purify does a much better job at finding these
	problems and more!

	* Now using GNU autoconf to generate configure scripts!  This
	makes building the software much easier.  The new Makefile.in
	replaces Makefile in the distribution.  New distribution files
	supporting this include aclocal.m4, config.h.in, configure,
	configure.in, and install-sh.

	* Improved the method by which bb.h includes the CPLEX header
	file, and forces it to give us prototypes.  Also changed the
	include of lpkit.h to get rid of the subdir portion and just let
	the -I argument in the Makefile find it for us.

	* Added LP solution history values to the bbnode, in preparation
	for early branching heuristics (tailing off detection).  Also
	added fields to the bbnode so that we can save and restore the LP
	tableaux and basis when switching nodes.  Deleted all of the
	statistics we used to collect about the now-defunct submodular SEC
	separator.  Also added some new macros to bb.h for doing getbase
	and loadbase operations in CPLEX.

	* Modified the 'kill -15' handler so that it now forces the
	problem to branch, rather than continue endlessly generating
	constraints.  Also changed the name of the signal handler and flag
	variable to be more descriptive of its new purpose.

	* Modified the encoding of constraints in the constraint pool to
	permit more than 32768 variables.  The estein10000.txt problem
	instance yields 40878 FSTs, which exceeded this limit.  The new
	encoding permits up to 65533 variables, which suffices for now.

	* Replaced the old "record_binding_row_references" and
	"delete_binding_row_references" routines with the newer ones
	"save_node_basis", "restore_node_basis" and "destroy_node_basis".
	These provide the enhanced functionality of saving and restoring
	the entire LP tableaux and basis when switching nodes.

	* The old versions 0 and 1 of the FST data format are now
	completely obsolete.  Version 0 has now been redefined to be an
	"extended OR-library" format for the Steiner problem in
	hypergraphs.  Also introduced version 3 of the data which is the
	new default.  Also added the PURE_GRAPH metric, which is valid for
	both versions 2 and 3.

	* Performed major surgery on the major data structures to conserve
	memory.  The "struct cinfo" fields carray, cmasks, incmasks and
	fset_concat_terms, are all GONE now.  The only remaining source of
	compatibility info is the "inc_edges" array.  Also removed the
	"tmap" field from each FST, as this was also getting huge.  To
	reflect our more general focus on the hypergraph problem, we also
	renamed the various "fset" and "term" fields to be "edge" and
	"vert" respectively.  For example, we no longer have the
	initial_tmap and initial_fset_mask, we have initial_vert_mask and
	initial_edge_mask instead.  These changes required huge and
	extensive changes to a number of sections of the code that relied
	on the old data structures.  In many cases the algorithms needed
	to become more complex.  In every case, however, the new code is
	faster because less total memory is accessed.

	* The point.other_pnum field is now obsolete.  All uses of it have
	been eliminated.

	* The "geometric information" in the problem instance, namely the
	cinfo fields pts, full_trees and mst_length are now all entirely
	optional!  They are only really used to plot FSTs in postscript
	form.  Every other place where the code needs to access the
	terminals contained in a given hyperedge now use the new cinfo
	fields "edge", "edge_size" and "cost".

	* Moved the Metric and data scaling fields from global variables
	into the cinfo structure as fields metric, scale and scale_value.
	Obsoleted the duplicate terminal group info, and added an
	integrality_delta field to the cinfo.  In the future, this will
	permit us to cutoff suboptimal nodes a bit sooner.

	* Removed an enormous number of function prototypes from
	steiner.h, either because they are obsolete, or because they were
	moved elsewhere (bsd.h, genps.h, rfst.h, etc.).

	* Introduced the new file machine.c to solve the problem of how to
	get a machine description string.  It gets information that can be
	obtained from the uname command.

	* Reimplemented the routines in cpulimit.c to fix a bug and
	increase the accuracy of the math by computing in hundredths of a
	second.

	* Completely recoded the get_cpu_time routine to correct some
	significant errors in the math.  Also improved its efficiency
	somewhat, especially on systems for which CLK_TCK is a function
	call.  When doing UNIX_CPU_TIME, we now include <sys/time.h>,
	<sys/times.h> and <time.h> to maximize the probability of finding
	CLK_TCK in the system headers.

	* Major rewrite of prelude.ps!  Now conforming to Adobe Document
	Structuring Conventions version 3.0 (more or less).  Now defining
	the plotting region to be such that terminals plotted at the
	extreme edges of the plotting region will just graze the inside
	edge of the framing box.  Also defining a clipping region so that
	nothing crawls outside the box.  Now using arrays to hold all of
	the terminal X and Y coordinates rather than defining zillions of
	distinct words.  This prevents dictionary overflows that happened
	previously on large point sets.  The "DefineTerminals" procedure
	sets the number of terminals, and "DT" stores an X/Y coordinate
	pair into the next element of the arrays.  Added dynamic scaling
	of the X and Y axes via the SetAxes procedure.  Got rid of many
	procedures: Term, Seg, Seg2, LightSeg, BackBone, BackBone2,
	LightBackBone2 and ShadedRect.  The new drawing primitives
	introduced are "T" (gets X and Y coords for a given terminal), "S"
	(draws a line segment), "C" (draws a reclinear corner).  All
	drawing primitives use whatever graphics state they are given --
	no more "light" and "normal" versions of things!

	* Renamed output.c to be genps.c to better indicate its function
	-- generating postscript.  Major changes were made here.  Added
	code to dynamically scale the axes of generated plots.  Started a
	new naming convention: routines that generate COMPLETE PLOTS
	(i.e., including BeginPlot ... stuff ... EndPlot) are now named
	"plot_FOO".  Routines that emit postscript for an object that goes
	inside a BeginPlot/EndPlot pair are named "draw_OBJECT".  The draw
	routines no longer have "plot_lightly" flags.  It is up to the
	caller to force the graphics state before invoking the particular
	draw routine.  Now generating the new drawing primitives and other
	procedures defined in prelude.ps.  Defining all of the terminal
	coordinates in the %%BeginSetup section.  Now doing reasonable
	things for non-geometric problem instances (i.e., don't try to
	emit postscript plots for them... just dump data!).  Got rid of
	the plotting of split_full_sets.  Got rid of all the horrible
	cruft to try to adjust for FST generators that didn't do left-most
	top-most Hwang topologies -- we now just draw the FST edge list
	and be done with it!

	* In io.c, made get_points really read from a given stream, and
	return a dynamically allocated (and correctly sized) pset.  Also
	made get_points return the scale factor and value, rather than
	poking them into global variables.  Got rid of the
	check_for_integral_coordinates routine and replaced it with a
	somewhat more general init_output_conversion routine.  This
	routine takes a point set, metric and scale as arguments, and
	properly initializes the coord_t/dist_t to ASCII conversion
	routines.  The state variables set up by this routine are now
	known and accessed only inside this one file.  Now using feof on
	the stream, rather than inventing a local flag to prevent further
	reading at EOF.  Renamed the "struct slist" to be "struct
	numlist", added a "num_dp" field for gathering scaling factor
	info, and moved it into steiner.h.  Added two new entrypoints,
	parse_line_of_numbers and read_numlist to support the new version
	0 FST data file format.  Added a "find_newline" flag (as well as
	the explicit stream) parameter to parse_one_number to support
	parsing numbers up until a newline.

	* Massive changes to p1read.c and p1write.c.  First to obsolete
	the old version 0 and 1 formats, and introduce the new version 0
	and 3 formats.  p1read.c now leaves cinfo members NULL if the file
	didn't containt anything useful to put into those fields.  For
	example, of the metric is PURE_GRAPH, then fields like
	cinfo.full_trees will remain NULL.  Made p1write.c be more careful
	about accessing these fields that could be NULL.  Now reading the
	FST/hyperedge vertices into cinfo.edge, cinfo.edge_size and
	cinfo.cost as well as into the full_sets (that is, if we have such
	geometric info).  Compatibility info is now read into the
	cinfo.inc_edges member instead of carray, incmasks, cmasks, etc.
	p1write.c now gets the MST length from the cinfo, rather than
	recomputing it (rectilinear style) from scratch.  p1read.c now
	uses the new parse_line_of_numbers and read_numlist facilities to
	permit mixing of integers and scaled reals on one line.  The
	scaling of the hyperedge costs is deferred until all have been
	read in as a linked list of struct numlist's.  p1read.c now uses
	more efficient algorithms to process any compatibility info it
	reads in and/or generates.  There is also no longer any need
	generate the incmasks, cmasks, and term_tree_masks structures.  It
	also has code to verify that the incompatible relation is
	symmetric.

	* Moved the MAX_COORD equate from steiner.h into rand_points.c,
	the only place it was ever used.

	* In bb.c, made cut_off_existing_nodes() be static.  Got rid of
	concatenation terminal constraints, clique constraints, and
	everything dealing with the obsolete submodular SEC separator.
	Made check_for_better_IFS update the Z value with a more precise
	value if the solution happens to be integral.  Got rid of
	create_inc_fsets, since the inc_edges are now filled in by
	p1read.c.  Added the experimental test_branching_variables
	routine, to help determine a good branching variable when we see
	one.  Also added the -R option (Check_Root_Constraints) to see how
	fast we COULD be converging if we were smarter.  Added the @6
	output containing Martin's statistics about the FST's comprising
	the SMT.  Printing out the solution certificate ONLY if we have
	geometric FST information.  Added a @0 output that contains the
	description line from the FST data file.  Added % reduction
	compared the the MST statistic to the @2 output line.  The -b
	switch now DISABLES strong branching rather than enabling it -- in
	other words, strong branching is now the default.  Eliminated the
	-d and -m switches, which are now obsolete.  Added code to save
	the LP solution history for each node.  Now printing special
	messages to indicate when and which nodes are being suspended and
	resumed.  New code to save and restore the LP tableax and basis
	for each node.  Introduced the new update_node_preempt_value
	routine to fix some misfeatures in the way the preempt_z was
	updated.  Now using new macros instead of calling CPLEX's getbase
	and loadbase routines directly.  Now printing out the number of
	fractional variables for each LP solution.  The current node is
	now cutoff immediately if the heuristic discovers a new upper
	bound which can do so.  Now using the precomputed scale_value in
	the cinfo rather than recomputing it when needed.  Now updating
	the node_preempt_value when existing nodes are cutoff, just in
	case ALL INACTIVE nodes got cutoff.  Recoded the deductive
	variable fixing logic to use the new data structures (i.e.,
	cinfo.edges, cinfo.inc_edges, etc.).

	* In constrnt.c: implemented new save/restore/destroy node_basis
	routines that replace the old binding_row stuff.  Eliminated
	clique constraints and concatenation terminal constraints.
	Massive rewrite of initialize_constraint_pool to conserve memory
	and to eliminate references to huge data structures that went
	away.  Now printing out the CPU time taken by init_constraint_pool
	and both versions of build_initial_formulation.  Reworked the pool
	representation to permit 65533 variables.  Simplified th