readme

生成直角Steiner树的程序包

machine.c       (Utility)
	Routines for obtaining a string that describes the machine
	running the program.

mst.c		(Utility)
	Routines to compute Minimum Spanning Trees.

p1io.h		(Utility)
	Declarations pertaining to the routines used for reading and
	writing FST data files (the so-called "phase 1 data format").

p1read.c	(Utility)
	Routines for reading FST data files (the so-called "phase 1
	data") from stdin.  Automatically recognizes the various
	versions of the FST data.

p1write.c	(Utility)
	Routines for writing FST data files (the so-called "phase 1
	data") to stdout.  The data can be written in any of several
	formats distinguished by version numbers.

plotfst.c	(Main program)
	Main routine for a program to plot full sets in various ways.

prunefst.c	(Main program)
	Main program for pruning of Euclidean and rectilinear FSTs.

rand_points.c	(Main program)
	A stand-alone program for generating random point sets.

rfst.c		(Main program)
	Main routine for the rectilinear FST generator.  The bulk of the
	RFST generation algorithm resides in this file.

rfst.h		(Rectilinear FST generator)
	Data structures and function prototypes pertaining to the
	rectilinear FST generator.

rmst.c		(Rectilinear FST generator)
	This file contains the minimum spanning tree algorithm, and also
	a brute-force implementation of the 1-Steiner heuristic of Kahng
	and Robins.

sec2.c		(Branch-and-cut)
	The deterministic separation procedure for SEC's that uses a
	network flow formulation.

sec2.h		(Branch-and-cut)
	Data structures and functions prototypes pertaining to the
	deterministic SEC separation routines.

sec_comp.c	(Branch-and-cut)
	Decomposition and reduction routines for SEC separation.
	Contains a routine to reduce the size of an SEC separation
	problem and perhaps split it up into disjoint components that
	can be individually separated.  A number of reduction and
	decomposition techniques are used.

sec_comp.h	(Branch-and-cut)
	Data structures and function prototypes pertaining to the SEC
	decomposition logic.

sec_heur.c	(Branch-and-cut)
	A collection of heuristic methods for separating subtour
	elimination constraints.  The methods include exhaustive
	(exhausting?) enumeration, enumeration of small-cardinality
	subsets, and a network flow heuristic based on the method of
	Padberg.

sec_heur.h	(Branch-and-cut)
	Data structures and function prototypes for the heuristic SEC
	separation routines.

sll.c		(Euclidean FST generator)
	A heuristic Euclidean SMT routine based on that of Smith, Lee
	and Liebman (Networks 11, 23-29, 1981).

sortints.c	(Utility)
	Routine to efficiently sort an array of integers.

steiner.h	(Utility)
	The "main" include file.  Fundamental types, constants and data
	structures are defined here.

triangle.c	(Euclidean FST generator)
	The `triangle' package by Jonathan Shewchuk.  Used to compute
	Delaunay triangulations for the Euclidean metric.

triangle.h	(Euclidean FST generator)
	Data structures and function prototypes defining the external
	interfaces to Jonathan Shewchuk's `triangle' package.

ub.c		(Branch-and-cut)
	This file contains a subroutine whose purpose is to obtain good
	heuristic Steiner trees by perturbing a fractional LP solution
	slightly.  Such "feasible integer solutions" serve as upper
	bounds in the backtrack search process.

ub.h		(Branch-and-cut)
	Data structures and function prototypes pertaining to the upper
	bound heuristic routines.

utils.c		(Utility)
	A collection of utility routines, including: the memory
	allocator "new()", the crash-and-die routine "fatal()", and a
	few other miscellaneous odds and ends.


FST Data File Formats
=====================

The FST generators produce output called FST data files.  (They are
sometimes called "phase 1 data files", since FST generation is the first
phase of the two-phase process for computing Steiner trees.

FST data files come in three different formats, distinguished by version
numbers.  Currently there are three such formats corresponding to
versions 0, 2 and 3 of the FST data format.  (Version 1 is very
obsolete, and no longer supported.)


			Version 0
			---------

Version 0 is used to represent an abstract MST or Steiner tree in graph
or hypergraph problem instance.  It is essentially the same format as
used in Beasley's "OR-library" -- but extended slightly to handle
hypergraph instances as well as graph instances.  The OR-library format
is as follows:

<Number of vertices N> <Number of edges M>
For each edge:
    <Vertex 1> <Vertex 2> <Edge cost>
<Number of terminal vertices K>
    <Terminal 1> <Terminal 2> ... <Terminal K>

Vertices are numbered 1 through N.  Each <Terminal i> is the vertex
number of a vertex that is a terminal (i.e., must be connected).
The <Edge cost>'s are real numbers.

We extend this format slightly by permitting each edge to have two OR
MORE vertices.  In exchange for this flexibility, we require the entire
description of each edge to reside on a single line of the data file.
Therefore, the final number on each line represents the hyperedge cost,
and all preceding numbers on the line represent the vertices of the
hyperedge.


			Version 2
			---------

Version 2 is used primarily to represent geometric FSTs (Euclidean or
rectilinear), although it can also handle non-geometric (graph)
instances.  It is unable, however, to represent Steiner tree in
hypergraph problems, because it assumes every vertex is a terminal.

In the following description, fields enclosed in <<...>> are omitted
when the Metric is Graph.  The format is as follows:

<Version Number: literally "V2">
<Instance description (free text)>
<Metric: 1 = Rectilinear, 2 = Euclidean, 3 = Graph>
<Number of terminals (N)>
<<Decimal length of MST>> <<Hex length of MST>>
<<Number of duplicate terminal groups (ndg)>>
<Coordinate/length scaling factor>
<Machine description (free text)>
<Front-end CPU-time (1/100s of a second, rounded to the nearest integer>
<Number of hyperedges/FSTs (M)>
For each terminal:
    <<Decimal X-coord>> <<Decimal Y-coord>> <<Hex X-coord>> <<Hex Y-coord>>
For each duplicate terminal group:
    <<Number of duplicate terminals>>
    <<Terminal indices (1..N), on one line separated by spaces>>
For each hyperedge/FST:
    <Number of terminals (Ni)>
    <Terminal indices (1..N), on one line separated by spaces>
    <Decimal length of hyperedge/FST> <Hex length of hyperedge/FST>
    <<Number of Steiner points (Mi)>>
    For each Steiner point:
       <<Decimal X-coord>> <<Decimal Y-coord>> <<Hex X-coord>> <<Hex Y-coord>>
    <<Number of FST edges (Ki)>>
    For each FST edge:
       <<endpoint-1>> <<endpoint-2>>
    <FST status: 0 = never needed, 1 = maybe needed, 2 = always needed>
    <Number of incompatible FSTs>
    <Incompatible FST indices (1..M), on one line separated by spaces>
    <Number of concatenation terminals>
    <Concatenation terminals indices (1..N), on one line separated by spaces>


			Version 3
			---------

Version 3 is the default format, and represents geometric FSTs
(Euclidean or rectilinear) as well as graph instances.  Since it
separately specifies each vertex to be either a terminal or Steiner
vertex, it can also represent Steiner problems in graphs/hypergraphs.
A number of obsolete fields from version 2 are omitted, however.

In the following description, fields enclosed in <<...>> are omitted
when the Metric is Graph.  The format is as follows:

<Version Number: literally "V3">
<Instance description (free text)>
<Metric: 1 = Rectilinear, 2 = Euclidean, 3 = Graph>
<Number of terminals (N)>
<<Decimal length of MST>> <<Hex length of MST>>
<Coordinate/length scaling factor>
<Decimal Integrality delta> <Hex Integrality delta>
<Machine description (free text)>
<Front-end CPU-time (1/100s of a second, rounded to the nearest integer>
<Number of hyperedges/FSTs (M)>
For each terminal:
    <<Decimal X-coord>> <<Decimal Y-coord>> <<Hex X-coord>> <<Hex Y-coord>>
For each terminal:
    <Terminal/Steiner flag: 0=Steiner, 1=Terminal>
For each hyperedge/FST:
    <Number of terminals (Ni)>
    <Terminal indices (1..N), on one line separated by spaces>
    <Decimal length of hyperedge/FST> <Hex length of hyperedge/FST>
    <<Number of Steiner points (Mi)>>
    For each Steiner point:
       <<Decimal X-coord>> <<Decimal Y-coord>> <<Hex X-coord>> <<Hex Y-coord>>
    <<Number of FST edges (Ki)>>
    For each FST edge:
       <<endpoint-1>> <<endpoint-2>>
    <FST status: 0 = never needed, 1 = maybe needed, 2 = always needed>
    <Number of incompatible FSTs>
    <Incompatible FST indices (1..M), on one line separated by spaces>


The following conventions are observed in versions 2 and 3 of the FST
data file format:

- Data input routines require only that the individual data fields be
  separated by one or more white-space characters (space, tab, newline,
  vertical tab, and form-feed are the white-space characters of ANSI C).

- Data output routines shall align items according to the schema above:
    - Schema fields that appear on separate lines shall be written on
      separate lines.
    - Schema fields that are all on one line shall be written all on one
      line.
    - The data shall be indented as shown by the schema.
    - Each indentation level shall be one "tab stop".
    - The implementor may freely choose the width of this "tab stop".

- The <Instance description (free text)> and
  <Machine description (free text)> fields shall each be a sequence of
  0 to 79 characters.  Each character in the sequence may be any
  printable ASCII character except newline.

- The <on one line separated by spaces> fields are permitted to span
  several lines, so long as the additional lines are each indented an
  additional "tab stop".  The intent of this splitting is to fully pack
  lines without exceeding some column limit (e.g., 80 columns).
  If no data is to appear then the line is removed completely.

- All decimal fields shall be UNSCALED -- just as in the original
  terminal coordinate input data.

- The hexadecimal fields shall be SCALED.  For example suppose that
  the <Coordinate scaling factor> is K.  Then the following
  relationship is implied:

        <Decimal X-coord> = <Hex X-coord> / 10**K

  where the equal sign is meant to imply "is within epsilon of".
  Scaling of data shall be at the discretion of the FST generator.  For
  example the FST generator is permitted to always specify a scaling
  factor of zero -- thereby disabling the scaling feature.  Programs
  that read FST data files should not assume that the hex-values (scaled
  or otherwise) are all integral without first verifying the actual data
  values.

- The <Decimal Integrality delta> (<Hex Integrality delta>) fields
  represent an UNSCALED (SCALED) lower bound on the amount by which two
  solutions of different lengths must differ.  For Euclidean FSTs, this
  must always be 0.  For rectilinear FSTs scaled to integer lengths this
  would be 1 (scaled value).  For graphs with integer weights, this can
  also be 1.  The branch-and-cut can use this to provide earlier cutoff
  of nodes that cannot reduce the upper bound.

- Let fields <endpoint-1> and <endpoint-2>, occur within an FST
  containing Ni terminals and Mi Steiner points.  Let the field value be
  J.  Then the interpretation of the endpoint field is as follows:

        1 <= J <= Ni    ==> endpoint is the Jth terminal in the FST's
                            list of terminals.

        -Mi <= J <= -1  ==> endpoint is the -Jth Steiner point in the
                            FST's list of Steiner points.

- Duplicate terminal groups (DTGs) identify subsets of the vertices
  having identical coordinates:
    - The size of each DTG shall be at least 2.
    - Each terminal may be listed in at most one DTG.
    - The terminal indices listed in a single DTG must be distinct.
    - The first terminal in each duplicate terminal group shall be
      referenced by at least one FST (having FST status <> 0).
    - The remaining terminals in each duplicate terminal group shall NOT
      be referenced by any FST (having FST status <> 0).

- If an FST has "never needed" status then the FST generator may output
  ANY incompatibility and concatenation terminal information, including
  no information at all (such information is redundant).

- The incompatible information shall NOT include the FST itself.

- The incompatible information need not include FSTs which are "never
  needed".

- The incompatible information need not include FSTs which share two or
  more terminals.  It is assumed that programs that read FST data files
  are smart enough to know about such basic incompatibilities already.
  Omitting such incompatibilities can significantly reduce the size of
  the data file.

- The FST-graph for rectilinear FSTs must always be a "left-most" and
  "top-most" Hwang topology.  If not, such FSTs will not appear to be
  Hwang topologies when plotted.

- A simple top-down traversal of each Euclidean FST-graph starting from
  the first terminal must yield the recursive equilateral-point
  structure of the FST.  In this way, programs that read Euclidean FST
  data files are able to correctly compute the exact length of each FST
  in terms of algebraic numbers, if desired.

NOTE!  The version 0 and 3 data formats can be used to describe Steiner
tree in graph (or hypergraph) instances.  However, GeoSteiner version
3.1 cannot solve such problems!  It blindly assumes all vertices are
terminals.  If given such an instance, GeoSteiner will produce the MST!
(i.e., the minimum tree spanning *all* vertices, be they terminals,
Steiner vertices, or any mixture thereof.)