fst2graph.c

生成直角Steiner树的程序包

sort_y_inc (

struct pset *		pts	/* IN/OUT - point set to sort. */
)
{
int		n;
int		h;
struct point	tmp;
coord_t		key;
struct point *	p1;
struct point *	p2;
struct point *	p3;
struct point *	p4;
struct point *	endp;

	n = pts -> n;

	endp = &(pts -> a [n]);

	for (h = 1; h <= n; h = 3*h+1) {
	}

	do {
		h = h / 3;
		p4 = &(pts -> a [h]);
		p1 = p4;
		while (p1 < endp) {
			tmp = *p1;
			key = tmp.y;
			p2 = p1;
			while (TRUE) {
				p3 = (p2 - h);
				if (p3 -> y <= key) break;
				*p2 = *p3;
				p2 = p3;
				if (p2 < p4) break;
			}
			*p2 = tmp;
			++p1;
		}
	} while (h > 1);
}

/*
 * This routine draws all valid FSTs onto the given grid in
 * an overlaid fashion.
 */

	static
	void
draw_full_sets_on_grid (

bitmap_t *	fset_mask,	/* IN - mask of valid FSTs */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int			i;
int			j;
int			u, v, ux, uy, vx, vy;
int			nt;
int			ns;
struct full_set *	fsp;
struct pset *		terms;
struct pset *		steins;
struct edge *		ep;
int *			xi;
int *			yi;

	xi = grid.xindex;
	yi = grid.yindex;
	for (i = 0; i < cip -> num_edges; i++) {
		if (NOT BITON (fset_mask, i)) continue;
		fsp = cip -> full_trees [i];

		ep = fsp -> edges;
		terms = fsp -> terminals;
		steins = fsp -> steiners;
		nt = terms -> n;
		ns = steins -> n;
		for (j = 0; j < fsp -> nedges; j++, ep++) {
			u = ep -> p1;
			if (u < 0) {
				fatal ("draw_full_sets_on_grid: Bug 1.");
			}
			if (u < nt) {
				u = terms -> a [u].pnum;
				ux = xi [u];
				uy = yi [u];
			}
			else {
				u -= nt;
				if (u >= ns) {
					fatal ("draw_full_sets_on_grid: Bug 2.");
				}
				ux = map_x (steins -> a [u].x);
				uy = map_y (steins -> a [u].y);
			}

			v = ep -> p2;
			if (v < 0) {
				fatal ("draw_full_sets_on_grid: Bug 3.");
			}
			if (v < nt) {
				v = terms -> a [v].pnum;
				vx = xi [v];
				vy = yi [v];
			}
			else {
				v -= nt;
				if (v >= ns) {
					fatal ("draw_full_sets_on_grid: Bug 4.");
				}
				vx = map_x (steins -> a [v].x);
				vy = map_y (steins -> a [v].y);
			}

			draw_bb_grid (ux, uy, vx, vy);
		}
	}
}

/*
 * This routine determines the grid index of the given X coordinate.
 */

	static
	int
map_x (

coord_t		x
)
{
int		i;

	for (i = 0; i < grid.nt; i++) {
		if (x EQ grid.x_coord [i]) return (i);
		if (x < grid.x_coord [i]) {
			fatal ("map_x: Bug 1.");
		}
	}

	fatal ("map_x: Bug 2.");
}

/*
 * This routine determines the grid index of the given Y coordinate.
 */

	static
	int
map_y (

coord_t		y
)
{
int		i;

	for (i = 0; i < grid.nt; i++) {
		if (y EQ grid.y_coord [i]) return (i);
		if (y < grid.y_coord [i]) {
			fatal ("map_y: Bug 1.");
		}
	}

	fatal ("map_y: Bug 2.");
}

/*
 * This routine is used to draw a backbone onto the grid.  A backbone
 * consists of a vertical line segment from the first point, and a
 * horizontal line from the second point.  Each segment consists only
 * of the points between the given points and the intersections of the
 * horizontal and vertical lines.
 */

	static
	void
draw_bb_grid (

int		x0,
int		y0,
int		x1,
int		y1
)
{
int		nt;

	nt = grid.nt;
	if ((x0 < 0) OR (x0 >= nt)) {
		fatal ("draw_bb_grid: Bug 1.");
	}
	if ((y0 < 0) OR (y0 >= nt)) {
		fatal ("draw_bb_grid: Bug 2.");
	}
	if ((x1 < 0) OR (x1 >= nt)) {
		fatal ("draw_bb_grid: Bug 3.");
	}
	if ((y1 < 0) OR (y1 >= nt)) {
		fatal ("draw_bb_grid: Bug 4.");
	}

	/* Assume RFSTs are left-most topologies.  Plot corner	*/
	/* segments so that the vertical segment is to the left	*/
	/* of the horizontal segment.				*/

	if (x0 < x1) {
		draw_bb_grid_vertical (x0, y0, y1);
		draw_bb_grid_horizontal (x1, y1, x0);
	}
	else {
		draw_bb_grid_vertical (x1, y1, y0);
		draw_bb_grid_horizontal (x0, y0, x1);
	}
}

/*
 * This routine draws a vertical line onto the grid.
 */

	static
	void
draw_bb_grid_vertical (

int		x0,
int		y0,
int		y1
)
{
int		i;
int		n;
int32u *	gridp;

	if (y0 > y1) {
		i = y0;
		y0 = y1;
		y1 = i;
	}

	n = grid.nt;

	if ((x0 < 0) OR (x0 >= n) OR (y0 < 0) OR (y1 > n)) {
		fatal ("draw_bb_grid_vertical: Bug 1.");
	}

	gridp = grid.gridp;
	gridp += (n * y0 + x0);
	while (y0 < y1) {
		*gridp |= UP_EDGE;
		gridp += n;
		++y0;
	}
}

/*
 * This routine draws a horizontal line onto the grid.
 */

	static
	void
draw_bb_grid_horizontal (

int		x0,
int		y0,
int		x1
)
{
int		i;
int		n;
int32u *	gridp;

	if (x0 > x1) {
		i = x0;
		x0 = x1;
		x1 = i;
	}

	n = grid.nt;

	if ((y0 < 0) OR (y0 >= n) OR (x0 < 0) OR (x1 > n)) {
		fatal ("draw_bb_grid_horizontal: Bug 1.");
	}

	gridp = grid.gridp;
	gridp += (n * y0 + x0);
	while (x0 < x1) {
		*gridp |= RIGHT_EDGE;
		++gridp;
		++x0;
	}
}

/*
 * This routine is used to identify the steiner points on the grid.
 */

	static
	void
identify_steiner_points (void)

{
int		i;
int		j;
int		nt;
int		ns;
int		code;
int32u *	gridp;

	nt = grid.nt;
	ns = 0;
	gridp = grid.gridp;
	for (i = 0; i < nt; i++) {
		for (j = 0; j < nt; j++, gridp++) {
			code = 0;
			if ((*gridp & RIGHT_EDGE) NE 0) {
				code |= 1;
			}
			if ((*gridp & UP_EDGE) NE 0) {
				code |= 0x02;
			}
			if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
				code |= 0x04;
			}
			if ((i > 0) AND ((gridp [-nt] & UP_EDGE) NE 0)) {
				code |= 0x08;
			}
			switch (code) {
			case 0x00:
				if ((*gridp & GMASK) NE 0) {
					/* Terminal with no connections! */
					fatal ("identify_steiner_points: Bug 1.");
				}
				break;

			case 0x01:
			case 0x02:
			case 0x04:
			case 0x08:
				if ((*gridp & GMASK) EQ 0) {
					/* degree 1 vertex must be terminal! */
					fatal ("identify_steiner_points: Bug 2.");
				}
				break;

			case 0x03:
			case 0x05:
			case 0x06:
			case 0x09:
			case 0x0A:
			case 0x0C:
				break;

			default:
				/* vertex has degree 3 or 4... */
				if ((*gridp & GMASK) EQ 0) {
					/* This is a new steiner point! */
					++ns;
					*gridp = (*gridp & ~GMASK) |
						 ((nt + ns) & GMASK);
				}
				break;
			}
		}
	}

	grid.ns = ns;
}

/*
 * This routine chases the grid-graph edge going RIGHT from position
 * I, J.  We traverse at least one grid element, but stop once we
 * discover a terminal or steiner node.
 */

	static
	void
edge_right (

int32u *	gridp,		/* IN - current grid element */
int		v1,		/* IN - first vertex of edge */
int		i,		/* IN - current Y index */
int		j,		/* IN - current X index */
dist_t		total,		/* IN - total length of edge so far */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int		nt;
int		v2;
int		code;

	nt = grid.nt;
	for (;;) {
		/* Step once to the right. */
		if ((j + 1) >= nt) {
			/* Ran off edge of grid! */
			fatal ("edge_right: Bug 1.");
		}
		total += (grid.x_coord [j+1] - grid.x_coord [j]);
		++j;
		++gridp;

		code = 0;
		if ((*gridp & RIGHT_EDGE) NE 0) {
			code |= 1;
		}
		if ((*gridp & UP_EDGE) NE 0) {
			code |= 0x02;
		}
		if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
			code |= 0x04;
		}
		if ((i > 0) AND ((gridp [-nt] & UP_EDGE) NE 0)) {
			code |= 0x08;
		}
		if ((code & 0x04) EQ 0) {
			/* No edge going out the way we came in! */
			fatal ("edge_right: Bug 2.");
		}
		v2 = (*gridp & GMASK);

		/* If we have stepped to a vertex, get out! */
		if (v2 > 0) break;

		/* Determine which direction to go... */
		switch (code) {
		case 0x05:	break;		/* keep on going... */
		case 0x06:
			edge_up (gridp, v1, i, j, total, cip);
			return;

		case 0x0C:
			edge_down (gridp, v1, i, j, total, cip);
			return;

		default:
			/* Bad type of intersection... */
			fatal ("edge_right: Bug 3.");
		}
	}

	if (v1 < v2) {
		/* We have an edge of the grid-graph! */
		output_edge (v1, v2, total, cip);
	}
}

/*
 * This routine chases the grid-graph edge going UP from position
 * I, J.  We traverse at least one grid element, but stop once we
 * discover a terminal or steiner node.
 */

	static
	void
edge_up (

int32u *	gridp,		/* IN - current grid element */
int		v1,		/* IN - first vertex of edge */
int		i,		/* IN - current Y index */
int		j,		/* IN - current X index */
dist_t		total,		/* IN - total length of edge so far */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int		nt;
int		v2;
int		code;

	nt = grid.nt;
	for (;;) {
		/* Step once upward. */
		if ((i + 1) >= nt) {
			/* Ran off edge of grid! */
			fatal ("edge_up: Bug 1.");
		}
		total += (grid.y_coord [i+1] - grid.y_coord [i]);
		++i;
		gridp += nt;

		code = 0;
		if ((*gridp & RIGHT_EDGE) NE 0) {
			code |= 1;
		}
		if ((*gridp & UP_EDGE) NE 0) {
			code |= 0x02;
		}
		if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
			code |= 0x04;
		}
		if ((i > 0) AND ((gridp [-nt] & UP_EDGE) NE 0)) {
			code |= 0x08;
		}
		if ((code & 0x08) EQ 0) {
			/* No edge going out the way we came in! */
			fatal ("edge_up: Bug 2.");
		}
		v2 = (*gridp & GMASK);

		/* If we have stepped to a vertex, get out! */
		if (v2 > 0) break;

		/* Determine which direction to go... */
		switch (code) {
		case 0x0A:	break;		/* keep on going... */
		case 0x09:
			edge_right (gridp, v1, i, j, total, cip);
			return;

		case 0x0C:
			edge_left (gridp, v1, i, j, total, cip);
			return;

		default:
			/* Bad type of intersection... */
			fatal ("edge_up: Bug 3.");
		}
	}

	if (v1 < v2) {
		/* We have an edge of the grid-graph! */
		output_edge (v1, v2, total, cip);
	}
}

/*
 * This routine chases the grid-graph edge going LEFT from position
 * I, J.  We traverse at least one grid element, but stop once we
 * discover a terminal or steiner node.
 */

	static
	void
edge_left (

int32u *	gridp,		/* IN - current grid element */
int		v1,		/* IN - first vertex of edge */
int		i,		/* IN - current Y index */
int		j,		/* IN - current X index */
dist_t		total,		/* IN - total length of edge so far */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int		nt;
int		v2;
int		code;

	nt = grid.nt;
	for (;;) {
		/* Step once to the left. */
		if (j <= 0) {
			/* Ran off edge of grid! */
			fatal ("edge_left: Bug 1.");
		}
		total += (grid.x_coord [j] - grid.x_coord [j-1]);
		--j;
		--gridp;

		code = 0;
		if ((*gridp & RIGHT_EDGE) NE 0) {
			code |= 1;
		}
		if ((*gridp & UP_EDGE) NE 0) {
			code |= 0x02;
		}
		if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
			code |= 0x04;
		}
		if ((i > 0) AND ((gridp [-nt] & UP_EDGE) NE 0)) {
			code |= 0x08;
		}
		if ((code & 0x01) EQ 0) {
			/* No edge going out the way we came in! */
			fatal ("edge_left: Bug 2.");
		}
		v2 = (*gridp & GMASK);

		/* If we have stepped to a vertex, get out! */
		if (v2 > 0) break;

		/* Determine which direction to go... */
		switch (code) {
		case 0x05:	break;		/* keep on going... */
		case 0x03:
			edge_up (gridp, v1, i, j, total, cip);
			return;

		case 0x09:
			edge_down (gridp, v1, i, j, total, cip);
			return;

		default:
			/* Bad type of intersection... */
			fatal ("edge_left: Bug 3.");
		}
	}

	if (v1 < v2) {
		/* We have an edge of the grid-graph! */
		output_edge (v1, v2, total, cip);
	}
}

/*
 * This routine chases the grid-graph edge going DOWN from position
 * I, J.  We traverse at least one grid element, but stop once we
 * discover a terminal or steiner node.
 */

	static
	void
edge_down (

int32u *	gridp,		/* IN - current grid element */
int		v1,		/* IN - first vertex of edge */
int		i,		/* IN - current Y index */
int		j,		/* IN - current X index */
dist_t		total,		/* IN - total length of edge so far */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int		nt;
int		v2;
int		code;

	nt = grid.nt;
	for (;;) {
		/* Step once downward. */
		if (i <= 0) {
			/* Ran off edge of grid! */
			fatal ("edge_down: Bug 1.");
		}
		total += (grid.y_coord [i] - grid.y_coord [i-1]);
		--i;
		gridp -= nt;

		code = 0;
		if ((*gridp & RIGHT_EDGE) NE 0) {
			code |= 1;
		}
		if ((*gridp & UP_EDGE) NE 0) {
			code |= 0x02;
		}
		if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
			code |= 0x04;
		}
		if ((i > 0) AND ((gridp [-nt] & UP_EDGE) NE 0)) {
			code |= 0x08;
		}
		if ((code & 0x02) EQ 0) {
			/* No edge going out the way we came in! */
			fatal ("edge_down: Bug 2.");
		}
		v2 = (*gridp & GMASK);

		/* If we have stepped to a vertex, get out! */
		if (v2 > 0) break;

		/* Determine which direction to go... */
		switch (code) {
		case 0x0A:	break;		/* keep on going... */
		case 0x03:
			edge_right (gridp, v1, i, j, total, cip);
			return;

		case 0x06:
			edge_left (gridp, v1, i, j, total, cip);
			return;

		default:
			/* Bad type of intersection... */
			fatal ("edge_down: Bug 3.");
		}
	}

	if (v1 < v2) {
		/* We have an edge of the grid-graph! */
		output_edge (v1, v2, total, cip);
	}
}

/*
 * This routine either outputs the edges, or counts them, as appropriate.
 */

	static
	void
output_edge (

int		v1,		/* IN - first vertex of edge */
int		v2,		/* IN - second vertex of edge */
dist_t		total,		/* IN - total length of edge */
struct cinfo *	cip		/* IN - compatibility info */
)
{
char		buf1 [128];

	if (count_edges) {
		++number_of_edges;
	}
	else {
		if (Print_SteinLib_Format) {
			printf ("E ");
		}

		dist_to_string (buf1, total, &(cip -> scale));
		printf ("%d %d %s\n", v1, v2, buf1);
	}
}