changelog

生成直角Steiner树的程序包

	an "int16u" instead of a "short" to double the range of
	permissible problem instance sizes.

	* Freeing up the memory used by the rectangle data structure in
	efst.c.

	* Fixed bug in compute_efsts_for_unique_terminals() (in efst.c)
	wherein term_check was allocated, initialized, and then allocated
	once again.  This yielded a memory leak and an uninitialized
	array.

	* Fixed memory leak in build_fst_list() (in efst.c).

	* Fixed bug in add_zero_length_fsts() (in efst.c) wherein the
	added zero-length FSTs had incorrect vertex numbers in their FST
	graph edges.

	* Fixed save_eqp_rectangles (in efst.c) to avoid NULLing out the
	squares array when there are no eqpoints to save.  This could have
	produced stores beyond the end of the array.

	* Fixed the wedge_test (in efst.c) to ignore terminals that are
	part of the eq-point.

	* Modified efst.c to handle new switches -f (epsilon factor), -g
	(use new greedy heuristic instead of SLL), -m 0,1,2 (multiple
	precision level).  Now also passing BSD info to upper bound
	heuristics.

	* Split off the elementary geometric functions (from efst.c and
	sll.c) into new efuncs.h file that is designed to permit
	inlining.

	* Various cosmetic changes to efst.c (e.g., re-indenting, EQ
	instead of ==, etc.) so that it conforms more closely to the
	coding conventions used in the rest of the package.

	* Modified efst.h to include a dynamic epsilon value, the point
	set mean, the BSD argument to the SLL heuristic, and the new
	greedy heuristic.

	* Modified init_empty_rectangles() routine (in emptyr.c) so that
	the "successor array" parameter can be NULL.  In this case, the
	routine computes its own successor array internally by
	heap-sorting the given point set by X and Y coordinates.

	* Modified emst.c to get rid of its local copies of the
	mst_edge_list() and sort_edge_list() routines.  It now uses the
	common copies in the new mst.c file.  Renamed the build_edges()
	routine to build_euclidean_edges() to distinguish it as the one
	that builds the list of potential MST edges for the Euclidean
	metric.  Deleted the "at_least"	parameter to
	build_euclidean_edges() -- this was a cut-and-paste feature from
	the rectilinear version that was only needed to support the
	Kahng-Robins heuristic, and is not needed for the Euclidean case.
	Also modified build_euclidean_edges() to just build the complete
	graph for N < 10 points.  Now freeing up the data allocated by the
	triangle package.

	* Fixed bugs in emst.c that occur when duplicate points exist in
	the input.

	* Replaced old "redg" with new "fst2graph" program (fst2graph.c).
	Whereas "regd" handled only rectilinear problems, "fst2graph"
	handles both rectilinear and Euclidean problems by taking the
	union of the FST edge graphs of all FSTs.  The default behavior
	for rectilinear problems is to compute the reduced "grid" graph
	just like "redg" did.  The FST edge graph can be requested instead
	by giving the -e switch.  The "fst2graph" program now produces an
	instance of the Steiner problem in graphs: in OR-library format by
	default, but the -s switch requests SteinLib format instead.  With
	rectilinear FSTs, the edge lengths will be scaled up to integer
	values unless the -u switch is given (which causes unscaled data
	to be emitted).

	* Modified calling convention of define_Plot_Terminals() and
	draw_segment() (in genps.c) to include the scaling information in
	"struct scale *" form.

	* Added new plot_subtour() routine (in genps.c) to display only
	the (fractional) FSTs involved with a given subtour.  The vertices
	of the subtour are printed black, and all other vertices are
	printed light gray so that the subtour can be easily identified
	visually.

	* Modified define_coordinate_axes() (in genps.c) to unscale the
	coordinates AFTER finding the min/max x/y coordinates.  Also
	modified to always generate square plots having equal scales on
	both the X and Y axes.  The old version would sometimes use
	different scales for the two axes, which distorted the 120 degree
	angles you would expect to see in a Euclidean Steiner tree.

	* Increased size of title buffer in plot_full_sets(), and also the
	coordinate buffers in draw_rfst().  (genps.c)

	* Fixed incorrect printf format in the non-geometric case of
	plot_lp_solution (in genps.c).

	* Added new greedy heuristic (greedy.c) for use by the Euclidean
	FST generator.  This upper bound is used instead of
	Smith-Lee-Liebman when the -g switch is given to efst.  It is more
	expensive than Smith-Lee-Liebman (sll.c), but tends to give better
	solutions -- resulting in fewer eq-points generated.

	* Major rework of input parsing, conversion and scaling mechanisms
	(in io.c, steiner.h and all callers).  The "struct numlist" now
	represents input lengths/coordinates in a semi-converted numeric
	form rather than in textual form.  All scaling information is now
	encapsulated in the new "struct scale_info", which holds both
	scaling / unscaling info and output formatting info.  Globals
	(e.g., Data_Num_Decimal_Places and min_precision) are no longer
	used to hold onto the output formatting info -- the scale_info is
	now explicitly passed to all places that need to format numbers
	for output.  Introduced a new UNSCALE macro to do all unscaling --
	it multiplies and divides by two pre-computed integral powers of
	ten -- one (or both!) of which will always be 1.  The routines
	coord_to_string(), dist_to_string(), get_points(),
	init_output_conversion(), and read_numlist() now take the
	encapsulated "struct scale_info *" as an explicit argument.  The
	new routines compute_scaling_factor() and set_scale_info() support
	all these changes.  The parse_one_number() routine now handles
	numbers in scientific notation and/or with leading '+' signs.  The
	dist_to_string() routine now correctly handles negative scale
	factors (i.e., where internal numbers are smaller than external
	numbers by a factor that is a power of ten).

	* Fixed a bug compute_basic_incompat (in p1read.c) wherein it left
	some elements of the incompat array uninitialized if compatibility
	information was present.

	* Modified read_version_0() (in p1read.c) to handle new "struct
	numlist", which now encodes input numbers numerically, rather than
	textually.  Also modified read_version_0() and read_version_2() to
	use the new scaling machinery.  Made init_term_trees() and
	compute_basic_incompat() non-static so that they can be called
	from other programs (e.g., prunefst).

	* Modified free_phase_1_data() (in p1read.c) to free up
	everything.  The hyperedges, sizes, costs, tflags and term_trees
	were being leaked.

	* Fixed a minor bug in print_version_2() (in p1write.c) that
	sometimes caused a line containing only a single tab to be
	emitted.  Although this causes no grief when reading the FSTs back
	in, it is a minor violation of our own formatting conventions.

	* Modified print_version_2() to prevent pruned edges from being
	listed as incompatible to any other.  This reduces the size of the
	incompatible lists.  (p1write.c)

	* Modified print_version_2() (in p1write.c) to eliminate a blank
	line (containing only a single TAB character) that occurred for
	FSTs having no incompatible FSTs.

	* Renamed old "fsplot" program to be "plotfst".  Added the -p
	switch to display only the point set, no FSTs.  It is a small
	pity that if all you want is a plot of the terminals, you must
	first generate FSTs...  (plotfst.c)

	* Added new "prunefst" program to do FST pruning (new file
	prunefst.c).  It works for both rectilinear and Euclidean FSTs,
	using the method of F\"ossmeier and Kaufmann implemented using
	ideas from Althaus.  This version uses VERY strong upper bounds
	that are computed by calling the entire branch-and-cut.  On very
	small subproblem instances, it is faster to use a simple backtrack
	search (new files btsearch.c and btsearch.h) than to invoke the
	higher overhead branch_and_cut.

	* Modified rand_points.c to conform to all command line argument
	processing in the standard way -- using a decode_params().  Also
	added a usage() routine for when crud is given.

	* Add -k option (in rfst.c) to permit a maximum FST size to be
	specified.

	* Removed unused "GREEDY_HEURISTIC" from rfst.c.  Added a new
	NOSPLIT_CORNER_FLIPPED test that removes RFSTs whose
	corner-flipped versions have terminals of degree two or more
	(i.e., Steiner points coincident with a terminal).  These cannot
	be easily recognized during generation, but once an RFST is done
	and the corner-flipped topology is available, the test is quite
	easy.  Added fatal error if any RFST edge has length zero.

	* Added code to disconnect the RFSTs from the hash table so that
	we can free up the hash table without leaving invalid pointers
	lying around in the RFSTs.

	* Removed some memory leaks from rfst.c, including the hash table,
	BSD info, successor arrays, arrays for the various bounds.  Fixed
	other memory leaks in compute_zt() -- the "offset[]" array and the
	"struct ibuf" list.  Free up the "rlists" in build_fst_list().

	* Removed unused variables from rfst.c: "dirp" and "ub0" in
	compute_ub1(); "s" in grow_RFST(); "l", "r" and "t" in
	test_and_save_fst(); "n" in renumber_terminals(); "j" in
	add_zero_length_fsts().

	* Added a call to memset() to completely initialize the new point
	set in remove_duplicates() (in rfst.c) to eliminate "reference to
	uninitialized memory" warnings from purify.  Initialize lrindex[]
	for the very same reason.

	* Split the sort_edge_list() and mst_edge_list() routines off from
	rmst.c into the new mst.c file.  mst.c now contains the generic
	MST routines that apply Kruskal's algorithm to an arbitrary list
	of weighted 2-edges.  The Euclidean and rectilinear MST routines
	now just build their metric-dependent edge lists and call the
	common copy of mst_edge_list in mst.c.

	* Renamed the build_edges() routine (in rmst.c) to be
	build_rect_edges(), to distinguish it as the one that builds the
	rectilinear edge list.  Also added a memset() call in kr_main() to
	eliminate "read of uninitialize memory" warnings from purify.

	* Added some debugging code (currently disabled) to the
	sec_flow_separator() to display the subtour violation as either
	component or "real" vertex numbers.  (sec2.c)

	* Changed the calling convention of check_component_subtour() to
	take a "struct bbinfo *" instead of a "struct cinfo *" (sec_comp.c
	and callers).

	* The original bi-connected components algorithm was WRONG!  It
	was incorrectly adapted from the standard strongly-connected
	components algorithm, (using only a "back" array) instead of the
	classical bi-connected components (which uses both a "low" and a
	"parent" array).  The incorrect version never broke a real BCC
	apart, but there were cases where it yielded components that could
	and should have been further reduced.  Corrected this in
	sec_comp.c and all other places this algorithm was used (e.g., in
	prunefst.c).

	* Added new routine add_component_subtour() to centralize the
	process of translating a component subtour back into a "real" one
	and check for duplicates (and violations) before emitting it
	(sec_comp.c).

	* Changed terminology in sec2.c, sec_comp.c and sec_heur.c to
	consistently use "vertex" and "edge" instead of "terminal" and
	"full set".  All comments were changed, as were local variable
	and routine names.

	* Replaced the "tmasks" and "kverts" field of "struct comp" with
	the "rverts" field.  Whereas "tmasks" was an array indexed by
	component vertex containing an N-bits bitmask of vertices (where N
	is the number of vertices in the ORIGINAL problem), the new
	"rverts" is an array indexed by component vertex giving a LIST of
	original vertex numbers.  Since these lists are virtually always 1
	element long (the exception being merged chains), this will be
	much more compact -- especially when dealing with small components
	of very large problems.  Should also reduce the processing time
	needed to initialize the data structure.

	* Renamed several members of "struct comp" to favor "vertex" over
	"terminal", and "edge" over "full set":  num_terms ==> num_verts,
	num_fsets ==> num_edges, fsterms ==> everts, tfsets ==> vedges,
	tmap ==> vert_mask, fset_mask ==> edge_mask.  (sec_comp.h and lots