rfst.c

生成直角Steiner树的程序包

#endif

#if NOSPLIT_CORNER_FLIPPED
	/* Test that corner flipped FST does not split into two or more */
	/* FSTs. Such FSTs are not needed.				*/

	d1 = DSTDIRP (&(pts -> a [terms [size-1]]),
		      &(pts -> a [terms [0]]),
		      dir);


	if (type EQ TYPE_1) {
		i = size - 3;
	}
	else {
		i = size - 4;
	}

	while (i > 0) {
		if (DSTDIRP (&(pts -> a [terms [i]]),
			     &(pts -> a [terms [0]]),
			     dir) <= d1) {
			return (length);
		}
		i -= 2;
	}
#endif

#if KAHNG_ROBINS_HEURISTIC
	if (size > 5) {
		struct pset * new_pts;
		new_pts = NEW_PSET (size);
		new_pts -> n = size;
		p1 = &(new_pts -> a [0]);
		for (i = 0; i < size; i++, p1++) {
			p2 = &(pts -> a [terms [i]]);
			p1 -> x		 = p2 -> x;
			p1 -> y		 = p2 -> y;
			p1 -> pnum	 = ((pnum_t) i);
		}
		d1 = kahng_robins_length (new_pts, length);
		free ((char *) new_pts);
		if (length > d1) return (d1);
	}
#endif

	/* General duplicate test.  We use a hash table, for speed.	*/
	/* For correctness, the hash function must not depend upon the	*/
	/* order of the terminals in the FST.  A simple checksum has	*/
	/* this property and tends to avoid favoring any one bucket.	*/

	/* Compute hash and prepare for rapid set comparison. */
	k = 0;
	for (i = 0; i < size; i++) {
		j = terms [i];
		rip -> term_check [j] = TRUE;
		k += j;
	}
	k %= pts -> n;

	hookp = &(rip -> hash [k]);
	for (;;) {
		rp = *hookp;
		if (rp EQ NULL) break;
		if (rp -> size EQ size) {
			p1 = &(rp -> fst -> terminals -> a [0]);
			for (i = 0; ; i++, p1++) {
				if (i >= size) goto found_rfst;
				if (NOT rip -> term_check [p1 -> pnum]) break;
			}
		}
		hookp = &(rp -> next);
	}

found_rfst:

	for (i = 0; i < size; i++) {
		rip -> term_check [terms [i]] = FALSE;
	}

	if (rp NE NULL) {
		/* An FST for these terminals already exists. */
		fsp = rp -> fst;
		if (fsp -> tree_len <= length) {
			return (fsp -> tree_len);
		}
		/* The new one is shorter!  Delete the old one. */
		*hookp = rp -> next;
		rp2 = rp -> forw;
		rp1 = rp -> back;
		rp2 -> back = rp1;
		rp1 -> forw = rp2;
		free ((char *) (fsp -> terminals));
		free ((char *) (fsp -> steiners));
		free ((char *) (fsp -> edges));
		free ((char *) fsp);
		free ((char *) rp);
	}

	/* Build FST graph in edge list form. */

	new_terms = NEW_PSET (size);
	new_terms -> n = size;
	for (i = 0; i < size; i++) {
		new_terms -> a [i] = pts -> a [terms [i]];
	}

	if (size <= 2) {
		nstein = 0;
		new_steiners = NULL;
		nedges = 1;
	}
	else if (type EQ CROSS) {
		nstein = 1;
		new_steiners = NEW_PSET (1);
		nedges = 4;
	}
	else {
		nstein = size - 2;
		new_steiners = NEW_PSET (nstein);
		nedges = 2 * size - 3;
	}

	edges = NEWA (nedges, struct edge);

	build_rfst_graph (rip,
			  size,
			  dir,
			  type,
			  new_terms,
			  new_steiners,
			  edges,
			  nedges);

	fsp = NEW (struct full_set);

	fsp -> next		= NULL;
	fsp -> tree_num		= 0;
	fsp -> tree_len		= length;
	fsp -> terminals	= new_terms;
	fsp -> steiners		= new_steiners;
	fsp -> nedges		= nedges;
	fsp -> edges		= edges;

	rp = NEW (struct rlist);

	rp2 = &(rip -> list);
	rp1 = rp2 -> back;
	rp -> back	= rp1;
	rp -> forw	= rp2;
	rp -> next	= rip -> hash [k];
	rp -> size	= size;
	rp -> fst	= fsp;

	rp1 -> forw	= rp;
	rp2 -> back	= rp;
	rip -> hash [k] = rp;

	return (length);
}

/*
 * Check that the diamond defined by two points is empty of terminals.
 */

	static
	bool
diamond_empty (

struct rinfo *		rip,		/* IN - global RFST info */
struct point *		p,		/* IN - first point */
struct point *		q,		/* IN - second point */
int			i,		/* IN - terminal to start scan from */
int			dir		/* IN - scan direction */
)
{
int			j;
int *			succ;
struct point *		r;
struct pset *		pts;
dstdiroff_t		dstdir_off;
dstdiroff_t		dstdirp_off;
dist_t			d;
dist_t			dstdir;
dist_t			dstdirp;

	pts = rip -> pts;
	succ = rip -> succ [dir];
	dstdir_off  = DSTDIR_GETOFFSET (dir);
	dstdirp_off = DSTDIR_GETOFFSET (dir + 1);

	d = RDIST (p, q);

	for (j = succ [i]; j >= 0; j = succ [j]) {
		r = &(pts -> a [j]);
		dstdir = DSTDIR_OFFSET (r, q, dstdir_off);
		if (dstdir > d) break;	/* finished in this direction */
		dstdirp = DSTDIR_OFFSET (r, q, dstdirp_off);
		if ((RDIST (r, p) < d) AND (dstdir + dstdirp < d)) {
			return (FALSE); /* found terminal in the diamond! */
		}
	}

	succ = rip -> succ [dir + 2];

	for (j = succ [i]; j >= 0; j = succ [j]) {
		r = &(pts -> a [j]);
		dstdir = DSTDIR_OFFSET (r, p, dstdir_off);
		if (dstdir > d) break;	/* finished in this direction */
		dstdirp = DSTDIR_OFFSET (r, p, dstdirp_off);
		if ((RDIST (r, q) < d) AND (dstdir + dstdirp < d)) {
			return (FALSE); /* found terminal in the diamond! */
		}
	}

	/* The diamond is empty! */
	return (TRUE);
}

/*
 * This routine constructs a graph of the RFST in edge list form.
 * We generate either the normal topology, or the "corner-flipped"
 * topology -- which ever yields a "left-most" and "top-most" topology.
 * This routine therefore also fills in the proper Steiner points.
 */

	static
	void
build_rfst_graph (

struct rinfo *		rip,
int			size,
int			dir,
int			type,
struct pset *		terms,
struct pset *		steins,
struct edge *		edges,
int			nedges
)
{
int			i, j, k;
struct point *		p1;
struct point *		p2;
struct point *		p3;
struct edge *		ep;

	ep = edges;

	p1 = &(terms -> a [0]);
	p2 = &(terms -> a [1]);

	if (size <= 2) {
		ep -> p1	= 0;
		ep -> p2	= 1;
		ep -> len	= RDIST (p1, p2);
		return;
	}

	if (type EQ CROSS) {
		steins -> n = 1;
		p1 = &(terms -> a [0]);
		p2 = &(terms -> a [1]);
		p3 = &(steins -> a [0]);
		SPOINT (p3, p1, p2, dir);
		p3 -> pnum = 0;
		for (i = 0; i < 4; i++) {
			ep -> p1 = i;
			ep -> p2 = 4;
			ep -> len = RDIST (&(terms -> a [i]),
					   &(steins -> a [0]));
			++ep;
		}
		return;
	}

	/* Decide whether to build a normal or corner-flipped topology. */
	/* This really only affects the Steiner point locations, not	*/
	/* the structure of the graph.					*/

	steins -> n = size - 2;

	k = size - 1;
	if (type EQ TYPE_2) {
		--k;
	}
	k = terms -> a [k].pnum;
	if ((dir EQ 1) AND
	    ((size <= 2) OR (rip -> lrindex [k] EQ 1))) {
		/* Build normal (unflipped) topology. */
		p1 = (type EQ TYPE_1) ? &(terms -> a [0])
				      : &(terms -> a [size-1]);
		p2 = &(terms -> a [size-2]);
		p3 = &(steins -> a [size - 3]);
		for (i = size - 3; i >= 0; i--) {
			SPOINT (p3, p1, p2, dir);
			p3 -> pnum = i;
			p1 = &(terms -> a [0]);
			--p2;
			--p3;
		}
	}
	else {
		/* Build corner-flipped topology. */
		if (type EQ TYPE_1) {
			k = ((size & 1) EQ 0) ? size-1 : 0;
		}
		else {
			k = ((size & 1) EQ 0) ? 0 : size-1;
		}
		p1 = &(terms -> a [k]);
		p2 = &(terms -> a [1]);
		p3 = &(steins -> a [0]);
		for (i = 0; i < size-2; i++) {
			SPOINT (p3, p1, p2, dir);
			p3 -> pnum = i;
			p1 = &(terms -> a [size - 1]);
			++p2;
			++p3;
		}
	}

	/* Now that the Steiner points are in the corrct places, build	*/
	/* the edges of the FST graph.	They have the same structure	*/
	/* regardless of whether the FST is type (i), type (ii),	*/
	/* flipped or unflipped.					*/

	j = 0;
	for (i = 0; i < size-2; i++) {
		ep -> p1	= j;
		j = size + i;
		ep -> p2	= j;
		++ep;
		ep -> p1	= j;
		ep -> p2	= i + 1;
		++ep;
	}
	ep -> p1 = j;
	ep -> p2 = i + 1;
	++ep;

	if (edges + nedges NE ep) {
		fatal ("build_rfst_graph: Bug 2.");
	}

	ep = edges;
	for (i = 0; i < nedges; i++, ep++) {
		j = ep -> p1;
		p1 = (j < size) ? &(terms -> a [j])
				: &(steins -> a [j - size]);
		k = ep -> p2;
		p2 = (k < size) ? &(terms -> a [k])
				: &(steins -> a [k - size]);
		ep -> len = RDIST (p1, p2);

		if (ep -> len EQ 0.0) {
			fatal ("build_rfst_graph: Bug 3.");
		}

	}
}

/*
 * Map all terminal numbers back to their original values.  (i.e., with
 * the duplicate terminals reinstated.	We must renumber the terminals
 * of each RFST also.
 */

	static
	void
renumber_terminals (

struct rinfo *		rip,		/* IN/OUT - global RFST info */
struct pset *		to_pts,		/* IN - point set to map to (orig) */
int *			rev_map		/* IN - map from new to old terms */
)
{
int			i;
int			j;
int			from_n;
int			to_n;
int			kmasks;
struct pset *		from_pts;
struct rlist *		rp1;
struct rlist *		rp2;
struct full_set *	fsp;
struct pset *		terms;
struct point *		p1;

	from_pts	= rip -> pts;
	from_n		= from_pts -> n;
	to_n		= to_pts -> n;

	kmasks = rip -> num_term_masks;

	/* Restore original set of terminals. */
	rip -> pts = to_pts;

	/* Renumber terminals in each FST. */
	rp2 = &(rip -> list);
	for (rp1 = rp2 -> forw; rp1 NE rp2; rp1 = rp1 -> forw) {
		fsp = rp1 -> fst;
		terms = fsp -> terminals;
		p1 = &(terms -> a [0]);
		for (i = 0; i < terms -> n; i++, p1++) {
			j = p1 -> pnum;
			if ((j < 0) OR (j >= from_n)) {
				fatal ("renumber_terminals: Bug 1.");
			}
			j = rev_map [j];
			if ((j < 0) OR (j >= to_n)) {
				fatal ("renumber_terminals: Bug 2.");
			}
			p1 -> pnum = j;
		}
	}
}

/*
 * Link all of the FSTs together into one long list and number them
 * each sequentially.  Free the doubly-linked rlists as we go.
 */

	static
	void
build_fst_list (

struct rinfo *		rip		/* IN - global RFST info */
)
{
int			i;
struct rlist *		rp1;
struct rlist *		rp2;
struct rlist *		rp3;
struct full_set *	fsp;
struct full_set **	hookp;

	hookp = &(rip -> full_sets);

	rp2 = &(rip -> list);
	i = 0;
	for (rp1 = rp2 -> forw; rp1 NE rp2; ) {
		fsp = rp1 -> fst;
		fsp -> tree_num = i++;
		*hookp = fsp;
		hookp = &(fsp -> next);
		rp3 = rp1;
		rp1 = rp1 -> forw;
		free ((char *) rp3);
	}
	*hookp = NULL;

	rip -> list.forw = rp2;
	rip -> list.back = rp2;

	/* Make it easy to add zero-length FSTs onto the end. */
	rip -> ntrees	= i;
	rip -> hookp	= hookp;
}

/*
 * This routine adds one RFST (of zero length) connecting the first
 * terminal of each duplicate terminal group to each terminal that
 * was deleted during the major processing.
 */

	static
	void
add_zero_length_fsts (

struct rinfo *		rip,		/* IN - global RFST info */
int			ndg,		/* IN - number of duplicate groups */
int **			list		/* IN - list of duplicate groups */
)
{
int			i;
int			t;
int			u;
int			kmasks;
int *			ip1;
int *			ip2;
struct pset *		pts;
struct pset *		terms;
struct edge *		edges;
struct full_set *	fsp;

	pts	= rip -> pts;
	kmasks	= rip -> num_term_masks;

	for (i = 0; i < ndg; i++) {
		ip1 = list [i];
		ip2 = list [i + 1];
		if (ip1 + 2 > ip2) {
			/* Group with fewer than two members! */
			fatal ("add_zero_length_fsts: Bug 1.");
		}
		t = *ip1++;
		while (ip1 < ip2) {
			u = *ip1++;

			terms = NEW_PSET (2);
			terms -> n = 2;
			terms -> a [0]	= pts -> a [t];
			terms -> a [1]	= pts -> a [u];

			edges = NEW (struct edge);
			edges -> p1	= 0;
			edges -> p2	= 1;
			edges -> len	= 0.0;

			fsp = NEW (struct full_set);

			fsp -> next	 = NULL;
			fsp -> tree_num	 = (rip -> ntrees)++;
			fsp -> tree_len	 = 0.0;
			fsp -> terminals = terms;
			fsp -> steiners	 = NULL;
			fsp -> nedges	 = 1;
			fsp -> edges	 = edges;

			*(rip -> hookp) = fsp;
			rip -> hookp	= &(fsp -> next);
		}
	}
}

/*
 * This routine allocates an array of pointers that lets us access a particular
 * tree number directly.
 */

	static
	struct full_set **
put_trees_in_array (

struct full_set *	fsp,		/* IN - list of full-trees. */
int *			acount		/* OUT - count of array elements. */
)
{
struct full_set **	ap;
struct full_set *	p;
int			count;
int			num;
struct full_set **	array;

	count = 0;
	for (p = fsp; p NE NULL; p = p -> next) {
		++count;
	}

	array = NEWA (count, struct full_set *);

	num = 0;
	ap = array;
	for (p = fsp; p NE NULL; p = p -> next) {
		*ap++ = p;
	}

	*acount = count;

	return (array);
}

/*
 * Routine to compute the X distance between two points.
 */

	static
	dist_t
delta_x_func (

struct point *		p1,		/* IN - point 1 */
struct point *		p2		/* IN - point 2 */
)
{
	return (fabs (p1 -> x - p2 -> x));
}


/*
 * Routine to compute the Y distance between two points.
 */

	static
	dist_t
delta_y_func (

struct point *		p1,		/* IN - point 1 */
struct point *		p2		/* IN - point 2 */
)
{
	return (fabs (p1 -> y - p2 -> y));
}

/*
 * Routines to compute whether a point Q is left or right of the ray
 * from P in a given direction.	 The index returned is 0 if Q is on
 * the left, and 1 otherwise.
 */

	static
	int
lrindex_dir_0 (

struct point *	p,
struct point *	q
)
{
	return (q -> y <= p -> y);
}

	static
	int
lrindex_dir_1 (

struct point *	p,
struct point *	q
)
{
	return (q -> x >= p -> x);
}

	static
	int
lrindex_dir_2 (

struct point *	p,
struct point *	q
)
{
	return (q -> y >= p -> y);
}

	static
	int
lrindex_dir_3 (

struct point *	p,
struct point *	q
)
{
	return (q -> x <= p -> x);
}

/*
 * Compute the CPU time used since the last time we called this routine.
 */

	static
	cpu_time_t
get_delta_cpu_time (void)

{
cpu_time_t		now;
cpu_time_t		delta;

	now = get_cpu_time ();

	delta = now - Tn;

	Tn = now;

	return (delta);
}


/*
 * Compute and format the CPU time used since the last time we called
 * this routine.
 */

	static
	void
convert_delta_cpu_time (

char *		buf		/* OUT - ASCII time string, CPU seconds */
)
{
cpu_time_t	delta;

	delta = get_delta_cpu_time ();
	convert_cpu_time (delta, buf);
}