fst2graph.c

生成直角Steiner树的程序包

/***********************************************************************

	File:	fst2graph.c
	Rev:	b-1
	Date:	01/19/2001

	Copyright (c) 1995, 2001 by David M. Warme & Martin Zachariasen

************************************************************************

	The main routine to generate ordinary graphs from FSTs.
	There are two possibilities:
	1. Reduced grid-graph for rectilinear problem,
	2. Graph with all terminals and Steiner points as nodes
	   and all line segments as edges (Euclidean and rectilinear
	   problem).

************************************************************************

	Modification Log:

	a-1:	05/18/95	warme
		: Created.
	b-1:	01/19/2001	martinz
		: Changed int16u to int32u in order to be able to handle
		:  bigger instances (also changed macros).
		: Changed name from redg.c to fst2graph.c
		: Support for OR-Library format and SteinLib format
		:  (made old format obsolete).
		: Added non-grid graph generation.

************************************************************************/

#include "p1io.h"
#include "steiner.h"


/*
 * Global Routines
 */

int			main (int, char **);


/*
 * External References
 */

	/* none */

/*
 * Local Equates
 */

#define	UP_EDGE		0x80000000	/* edge exits point and goes up */
#define	RIGHT_EDGE	0x40000000	/* edge exits point and goes right */
#define	GMASK		0x3FFFFFFF	/* mask of other bits */


/*
 * Local Types
 */

struct grid {
	int		nt;
	int		ns;
	coord_t *	x_coord;
	coord_t *	y_coord;
	int *		xindex;
	int *		yindex;
	int32u *	gridp;
};


/*
 * Local Routines
 */

static void		compute_edge_graph (bitmap_t *, bitmap_t *,
					    struct cinfo *);
static void		compute_grid_graph (bitmap_t *, bitmap_t *,
					    struct cinfo *);
static void		decode_params (int, char **);
static void		draw_bb_grid (int, int, int, int);
static void		draw_bb_grid_horizontal (int, int, int);
static void		draw_bb_grid_vertical (int, int, int);
static void		draw_full_sets_on_grid (bitmap_t *, struct cinfo *);
static void		edge_down (int32u *, int, int, int, dist_t,
				   struct cinfo *);
static void		edge_left (int32u *, int, int, int, dist_t,
				   struct cinfo *);
static void		edge_right (int32u *, int, int, int, dist_t,
				    struct cinfo *);
static void		edge_up (int32u *, int, int, int, dist_t,
				 struct cinfo *);
static void		identify_steiner_points (void);
static int		map_x (coord_t);
static int		map_y (coord_t);
static void		output_edge (int, int, dist_t, struct cinfo *);
static void		sort_x_inc (struct pset *);
static void		sort_y_inc (struct pset *);
static void		usage (void);


/*
 * Local Variables
 */

static bool		count_edges;
static struct grid	grid;
static char *		me;
static int		number_of_edges;
static bool		Print_Grid_Graph	= TRUE;
static bool		Print_ORLibrary_Format	= TRUE;
static bool		Print_SteinLib_Format	= FALSE;
static bool		Print_Unscaled = FALSE;
static char *		description = NULL;

/*
 * This is the main routine for computing Reduced Grid-Graphs.
 */

	int
main (

int		argc,
char **		argv
)
{
int			fpsave;
bitmap_t *		vert_mask;
bitmap_t *		edge_mask;
struct cinfo		cinfo;

	fpsave = set_floating_point_double_precision ();

	setbuf (stdout, NULL);

	decode_params (argc, argv);

	init_tables ();

	read_phase_1_data (&cinfo);
	if (description NE NULL) {
		free ((char *) cinfo.description);
		cinfo.description = gst_strdup (description);
	}

	if ((cinfo.metric NE RECTILINEAR) AND (cinfo.metric NE EUCLIDEAN)) {
		fprintf (stderr, "This only be done for geometric (Euclidean or rectilinear) FSTs\n");
		exit (1);
	}

	vert_mask	= cinfo.initial_vert_mask;
	edge_mask	= cinfo.initial_edge_mask;

	if ((cinfo.metric EQ RECTILINEAR) AND (NOT Print_Unscaled)) {
		/* Force printing of integer data. */
		cinfo.scale.min_precision = 0;
		if (cinfo.scale.scale > 0) {
			cinfo.scale.scale = 0;
		}
	}

	if ((cinfo.metric EQ EUCLIDEAN) OR (!Print_Grid_Graph)) {
		compute_edge_graph (vert_mask, edge_mask, &cinfo);
	}
	else {
		compute_grid_graph (vert_mask, edge_mask, &cinfo);
	}

	free_phase_1_data (&cinfo);

	restore_floating_point_precision (fpsave);

	exit (0);
}

/*
 * This routine decodes the various command-line arguments.
 */

	static
	void
decode_params (

int		argc,
char **		argv
)
{
char *		ap;
char		c;

	--argc;
	me = *argv++;
	while (argc > 0) {
		ap = *argv++;
		if (*ap NE '-') {
			usage ();
		}
		++ap;
		while ((c = *ap++) NE '\0') {
			switch (c) {
			case 'd':
				if (*ap EQ '\0') {
					if (argc <= 0) {
						usage ();
					}
					ap = *argv++;
					--argc;
				}
				if (strlen (ap) >= 80) {
					fprintf (stderr,
						"Description must be less"
						" than 80 characters.\n");
					usage ();
				}
				description = ap;
				/* Change newlines to spaces... */
				for (;;) {
					ap = strchr (ap, '\n');
					if (ap EQ NULL) break;
					*ap++ = ' ';
				}
				ap = "";
				break;

			case 'e':
				Print_Grid_Graph	= FALSE;
				break;

			case 's':
				Print_ORLibrary_Format	= FALSE;
				Print_SteinLib_Format	= TRUE;
				break;

			case 'u':
				Print_Unscaled = TRUE;
				break;

			default:
				usage ();
				break;
			}
		}
		--argc;
	}
}

/*
 * This routine prints out the proper usage and exits.
 */

static char *	arg_doc [] = {
	"",
	"Reads FST info from stdin. Produces an ordinary graph",
	"on stdout which is either:",
	" - graph of all line segments in all FSTs (default for Euclidean problem)",
	" - reduced grid graph (default for rectilinear problem)",
	"Output data is printed in OR-Library format.",
	"Distances in the rectilinear problem are scaled to integers."
	"",
	"\t-d txt\tDescription of problem instance.",
	"\t-s\tPrints data in SteinLib format.",
	"\t-e\tGenerate edge graph for the rectilinear problem.",
	"\t-u\tOutput unscaled (fractional) data.",
	"",
	NULL
};

	static
	void
usage (void)

{
char **		pp;
char *		p;

	(void) fprintf (stderr, "\nUsage: %s [-seu] [-d description]\n", me);
	pp = &arg_doc [0];
	while ((p = *pp++) NE NULL) {
		(void) fprintf (stderr, "%s\n", p);
	}
	exit (1);
}

/*
 * This routine computes the edge-graph obtained by taking the union
 * of all of all line segments in all FSTs
 */

	static
	void
compute_edge_graph (

bitmap_t *	tmap,		/* IN - valid set of terminals */
bitmap_t *	fset_mask,	/* IN - valid FSTs */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int			i, j, i1, i2;
int			sp_index;
int			sp_total;
int			n2edges;
int			nedges;
struct full_set *	fsp;
struct pset *		terms;
struct point *		p1;
struct point *		p2;
dist_t			d = 0.0;
char			buf1 [128];
char			buf2 [128];

	/* Total number of Steiner points and ordinary edges */
	nedges = cip -> num_edges;
	sp_total = 0;
	n2edges	 = 0;
	for (i = 0; i < nedges; i++) {
		if (NOT BITON (fset_mask, i)) continue;
		sp_total += cip -> full_trees [i] -> steiners -> n;
		n2edges	 += cip -> full_trees [i] -> nedges;
	}

	/* Write header */
	if (Print_ORLibrary_Format) {
		printf ("%d %d\n", cip -> num_verts + sp_total, n2edges);
	}

	if (Print_SteinLib_Format) {
		printf ("33d32945 STP File, STP Format Version 1.00\n"
			"Section Comment\n"
			"Name    \"%s\"\n"
			"Creator \"GeoSteiner\"\n"
			"Remark  \"Reduced graph from FST generator\"\n"
			"End\n\n"
			"Section Graph\n"
			"Nodes %d\n"
			"Edges %d\n",
			cip -> description, cip -> num_verts + sp_total, n2edges);
	}

	/* Write (ordinary) graph edges */
	sp_index = cip -> num_verts;
	for (i = 0; i < nedges; i++) {
		if (NOT BITON (fset_mask, i)) continue;
		fsp = cip -> full_trees [i];
		terms = fsp -> terminals;
		for (j = 0; j < fsp -> nedges; j++) {

			/* Compute length of this edge */
			p1 = (fsp -> edges[j].p1 < terms -> n)
				? &(terms -> a[ fsp -> edges[j].p1 ])
				: &(fsp -> steiners -> a [fsp -> edges[j].p1 - terms -> n]);
			p2 = (fsp -> edges[j].p2 < terms -> n)
				? &(terms -> a[ fsp -> edges[j].p2 ])
				: &(fsp -> steiners -> a [fsp -> edges[j].p2 - terms -> n]);

			i1 = (fsp -> edges[j].p1 < terms -> n)
				? terms -> a[ fsp -> edges[j].p1 ].pnum + 1
				: fsp -> edges[j].p1 - terms -> n + sp_index + 1;
			i2 = (fsp -> edges[j].p2 < terms -> n)
				? terms -> a[ fsp -> edges[j].p2 ].pnum + 1
				: fsp -> edges[j].p2 - terms -> n + sp_index + 1;

			if (Print_SteinLib_Format) {
				printf ("E ");
			}

			if (cip -> metric EQ EUCLIDEAN) {
				d = EDIST(p1, p2);
			}
			else {
				d = RDIST(p1, p2);
			}
			dist_to_string (buf1, d, &(cip -> scale));
			printf ("%d %d %s\n", i1, i2, buf1);
		}
		if (fsp -> steiners NE NULL) {
			sp_index += fsp -> steiners -> n;
		}
	}

	/* Write terminals (and coordinates in STP-format) */
	if (Print_ORLibrary_Format) {
		printf ("%d\n", cip -> num_verts);
		for (i = 0; i < cip -> num_verts; i++) {
			printf ("%d\n", i+1);
		}
	}

	if (Print_SteinLib_Format) {
		printf ("End\n\n"
			"Section Terminals\n"
			"Terminals %d\n",
			cip -> num_verts);
		for (i = 0; i < cip -> num_verts; i++) {
			printf ("T %d\n", i+1);
		}
		printf ("End\n\n"
			"Section Coordinates\n");
		for (i = 0; i < cip -> num_verts; i++) { /* terminals */
			dist_to_string (buf1,
					cip -> pts -> a[i].x,
					&(cip -> scale));
			dist_to_string (buf2,
					cip -> pts -> a[i].y,
					&(cip -> scale));
			printf ("DD %d %s %s\n", i+1, buf1, buf2);
		}
		sp_index = cip -> num_verts + 1;
		for (i = 0; i < nedges; i++) { /* Steiner points */
			fsp = cip -> full_trees [i];
			for (j = 0; j < fsp -> steiners -> n; j++) {
				dist_to_string (buf1,
						fsp -> steiners -> a[j].x,
						&(cip -> scale));
				dist_to_string (buf2,
						fsp -> steiners -> a[j].y,
						&(cip -> scale));
				printf ("DD %d %s %s\n", sp_index++, buf1, buf2);
			}
		}
		printf ("End\n\n"
			"EOF\n");
	}
}

/*
 * This routine computes the grid-graph obtained by taking the union
 * of all FSTs
 */

	static
	void
compute_grid_graph (

bitmap_t *	tmap,		/* IN - valid set of terminals */
bitmap_t *	fset_mask,	/* IN - valid FSTs */
struct cinfo *	cip		/* IN - compatibility info */
)
{
int		i;
int		j;
int		k;
int		nverts;
int		nverts2;
int		v1;
int		spi;
int32u *	gridp;
coord_t		coord;
dist_t		prev_coord;
int		prev_index;
struct pset *	tmp;
char		buf1 [128];
char		buf2 [128];

	nverts = cip -> num_verts;

	grid.nt		= nverts;
	grid.ns		= 0;
	grid.x_coord	= NEWA (nverts, coord_t);
	grid.y_coord	= NEWA (nverts, coord_t);
	grid.xindex	= NEWA (nverts, int);
	grid.yindex	= NEWA (nverts, int);

	/* Compute map giving index of each terminal in sequence when	*/
	/* sorted by increasing X coordinate.				*/
	tmp = NEW_PSET (nverts);
	tmp -> n = nverts;
	for (i = 0; i < nverts; i++) {
		tmp -> a [i] = cip -> pts -> a [i];
	}
	sort_x_inc (tmp);
	prev_coord = INF_DISTANCE;
	prev_index = -1;
	for (i = 0; i < nverts; i++) {
		coord = tmp -> a [i].x;
		grid.x_coord [i] = coord;
		j = tmp -> a [i].pnum;
		if (coord NE prev_coord) {
			prev_index = i;
		}
		grid.xindex [j] = prev_index;
		prev_coord = coord;
	}

	/* Compute map giving index of each terminal in sequence when	*/
	/* sorted by increasing Y coordinate.				*/
	tmp -> n = nverts;
	for (i = 0; i < nverts; i++) {
		tmp -> a [i] = cip -> pts -> a [i];
	}
	sort_y_inc (tmp);
	prev_coord = INF_DISTANCE;
	prev_index = -1;
	for (i = 0; i < nverts; i++) {
		coord = tmp -> a [i].y;
		grid.y_coord [i] = tmp -> a [i].y;
		j = tmp -> a [i].pnum;
		if (coord NE prev_coord) {
			prev_index = i;
		}
		grid.yindex [j] = prev_index;
		prev_coord = coord;
	}

	free ((char *) tmp);

	/* Allocate and zero matrix to hold the grid... */
	nverts2 = (nverts + 1) * nverts;
	grid.gridp = NEWA (nverts2, int32u);
	for (i = 0; i < nverts2; i++) {
		grid.gridp [i] = 0;
	}
	grid.gridp += nverts;

	/* Set vertex number for each terminal in the grid... */
	for (i = 0; i < nverts; i++) {
		if (NOT BITON (tmap, i)) {
			/* Should not have any duplicate terminals! */
			fatal ("compute_grid_graph: Bug 1.");
		}
		j = grid.xindex [i];
		k = grid.yindex [i];
		grid.gridp [k * nverts + j] = i + 1;
	}

	draw_full_sets_on_grid (fset_mask, cip);

	identify_steiner_points ();

	/* Count every edge... */
	count_edges = TRUE;
	number_of_edges = 0;
	gridp = grid.gridp;
	for (i = 0; i < nverts; i++) {
		for (j = 0; j < nverts; j++, gridp++) {
			v1 = (*gridp & GMASK);
			if (v1 EQ 0) continue;
			if ((*gridp & RIGHT_EDGE) NE 0) {
				edge_right (gridp, v1, i, j, 0, cip);
			}
			if ((*gridp & UP_EDGE) NE 0) {
				edge_up (gridp, v1, i, j, 0, cip);
			}
			if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
				edge_left (gridp, v1, i, j, 0, cip);
			}
			if ((i > 0) AND ((gridp [-nverts] & UP_EDGE) NE 0)) {
				edge_down (gridp, v1, i, j, 0, cip);
			}
		}
	}

	/* Output total number of vertices, plus number of terminals. */
	if (Print_ORLibrary_Format) {
		printf ("%d %d\n", nverts + grid.ns, number_of_edges);
	}

	if (Print_SteinLib_Format) {
		printf ("33d32945 STP File, STP Format Version 1.00\n"
			"Section Comment\n"
			"Name    \"%s\"\n"
			"Creator \"GeoSteiner\"\n"
			"Remark  \"Reduced graph from FST generator\"\n"
			"End\n\n"
			"Section Graph\n"
			"Nodes %d\n"
			"Edges %d\n",
			cip -> description, nverts + grid.ns, number_of_edges);
	}

	/* Output every edge... */
	count_edges = FALSE;
	gridp = grid.gridp;
	for (i = 0; i < nverts; i++) {
		for (j = 0; j < nverts; j++, gridp++) {
			v1 = (*gridp & GMASK);
			if (v1 EQ 0) continue;
			if ((*gridp & RIGHT_EDGE) NE 0) {
				edge_right (gridp, v1, i, j, 0, cip);
			}
			if ((*gridp & UP_EDGE) NE 0) {
				edge_up (gridp, v1, i, j, 0, cip);
			}
			if ((j > 0) AND ((gridp [-1] & RIGHT_EDGE) NE 0)) {
				edge_left (gridp, v1, i, j, 0, cip);
			}
			if ((i > 0) AND ((gridp [-nverts] & UP_EDGE) NE 0)) {
				edge_down (gridp, v1, i, j, 0, cip);
			}
		}
	}

	/* Write terminals (and coordinates in STP-format) */
	if (Print_ORLibrary_Format) {
		printf ("%d\n", nverts);
		for (i = 0; i < nverts; i++) {
			printf ("%d\n", i+1);
		}
	}

	if (Print_SteinLib_Format) {
		printf ("End\n\n"
			"Section Terminals\n"
			"Terminals %d\n",
			nverts);
		for (i = 0; i < nverts; i++) {
			printf ("T %d\n", i+1);
		}
		printf ("End\n\n"
			"Section Coordinates\n");

		/* Output coordinates of each terminal... */
		for (i = 0; i < nverts; i++) {
			coord_to_string (buf1,
					 cip -> pts -> a [i].x,
					 &(cip -> scale));
			coord_to_string (buf2,
					 cip -> pts -> a [i].y,
					 &(cip -> scale));
			printf ("DD %d %s %s\n", i+1, buf1, buf2);
		}

		/* Output coordinates of each steiner point... */
		spi = nverts+1;
		gridp = grid.gridp;
		for (i = 0; i < nverts; i++) {
			for (j = 0; j < nverts; j++, gridp++) {
				if ((*gridp & GMASK) > nverts) {
					coord_to_string (buf1,
							 grid.x_coord [j],
							 &(cip -> scale));
					coord_to_string (buf2,
							 grid.y_coord [i],
							 &(cip -> scale));
					printf ("DD %d %s %s\n",
						spi, buf1, buf2);
					spi++;
				}
			}
		}
		printf ("End\n\n"
			"EOF\n");
	}


	free ((char *) (grid.gridp - nverts));
	free ((char *) grid.yindex);
	free ((char *) grid.xindex);
	free ((char *) grid.y_coord);
	free ((char *) grid.x_coord);
}

/*
 * This routine sorts the given point set in order by INCREASING X coord.
 */

	static
	void
sort_x_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.x;
			p2 = p1;
			while (TRUE) {
				p3 = (p2 - h);
				if (p3 -> x <= key) break;
				*p2 = *p3;
				p2 = p3;
				if (p2 < p4) break;
			}
			*p2 = tmp;
			++p1;
		}
	} while (h > 1);
}

/*
 * This routine sorts the given point set in order by INCREASING Y coord.
 */

	void