genps.c

生成直角Steiner树的程序包

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

	File:	genps.c
	Rev:	b-1
	Date:	02/28/2001

	Copyright (c) 1993, 2001 by David M. Warme

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

	Routines for outputting stuff.

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

	Modification Log:

	a-1:	04/18/93	warme
		: Created.  Moved most output stuff into this file
		:  from other places.
	b-1:	02/28/2001	warme
		: Changes for 3.1 release.  Pass scaling info
		:  explicitly to these routines.  Added plot_subtour.
		:  Always define X and Y scales to be equal.
		:  Fix format in non-geometric case of plot_lp_solution.

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


/*
 * Global Routines
 */

void		begin_plot (enum plot_size);
void		define_Plot_Terminals (struct pset *, struct scale_info *);
void		draw_segment (struct point *,
			      struct point *,
			      struct scale_info *);
void		end_plot (char *);
void		overlay_plot_subset (char *,
				     bitmap_t *,
				     struct cinfo *,
				     enum plot_size);
void		plot_full_sets (bitmap_t *, struct cinfo *, enum plot_size);
void		plot_full_sets_grouped (bitmap_t *,
					struct cinfo *,
					enum plot_size);
void		plot_lp_solution (char *,
				  double *,
				  struct cinfo *,
				  enum plot_size);
void		plot_subtour (char *,
			      double *,
			      struct cinfo *,
			      bitmap_t *,
			      enum plot_size);


/*
 * External References
 */

	/* none */


/*
 * Local Equates
 */

#define	SMALL_PLOTS_PER_PAGE	12


/*
 * Local Routines
 */

static void		announce_new_page (void);
static void		define_coordinate_axes (struct pset *,
						struct scale_info *);
static void		draw_efst (struct full_set *, struct cinfo *);
static void		draw_fst (struct full_set *, struct cinfo *);
static void		draw_rfst (struct full_set *, struct cinfo *);
static void		draw_fractional_fst (struct full_set *,
					     double,
					     struct cinfo *);
static void		fst_comment (struct full_set *);
static double		get_limit (double);
static void		page_break (void);


/*
 * Local Variables
 */

static int		current_page = 0;
static enum plot_size	current_plot_size;
static int		small_plots_on_page = 0;

/*
 * This routine emits Postscript that defines the coordinates of
 * all the terminals.  The "N DefineTerminals" procedure causes space
 * to be allocated for N terminals.  We then emit the terminals, one
 * per line with "X Y DT" procedure calls.  The "DT" procedure simply
 * stuffs the given X,Y coordinates into the next slot in the TermX and
 * TermY arrays.
 *
 * Once the terminals are defined, the X,Y coordinates of a terminal (e.g.,
 * terminal 57) can be pushed onto the Postscript stack using "57 T".
 */

	void
define_Plot_Terminals (

struct pset *		pts,		/* IN - terminals to plot */
struct scale_info *	sip		/* IN - problem scaling info */
)
{
int			i;
int			n;
struct point *		p1;
char			buf1 [32];
char			buf2 [32];

	if (pts EQ NULL) return;

	n = pts -> n;

	printf ("\n%%%%BeginSetup\n");

	define_coordinate_axes (pts, sip);

	printf ("\n%d DefineTerminals\n", n);

	p1 = &(pts -> a [0]);
	for (i = 0; i < n; i++, p1++) {
		coord_to_string (buf1, p1 -> x, sip);
		coord_to_string (buf2, p1 -> y, sip);
		(void) printf ("\t%s\t%s\tDT\n", buf1, buf2);
	}
	printf ("\n%%%%EndSetup\n\n");
}

/*
 * This routine determines appropriate ranges for the X and Y coordinate
 * axes, and emits the corresponding Postscript definitions for the
 * MinX, MaxX, MinY and MaxY variables.
 */

	static
	void
define_coordinate_axes (

struct pset *		pts,		/* IN - terminals to plot */
struct scale_info *	sip		/* IN - problem scaling info */
)
{
int			i;
int			n;
struct point *		p1;
double			x, y;
double			minxcoord, maxxcoord;
double			minycoord, maxycoord;
double			xspan, yspan, span;
double			axmin, axmax;
double			aymin, aymax;

	n = pts -> n;

	if (n < 1) {
		printf ("\n0 1 0 1 SetAxes\n");
		return;
	}

	p1 = &(pts -> a [0]);

	minxcoord = maxxcoord = p1 -> x;
	minycoord = maxycoord = p1 -> y;
	++p1;

	for (i = 1; i < n; i++, p1++) {
		x = p1 -> x;
		y = p1 -> y;
		if (x < minxcoord) {
			minxcoord = x;
		}
		else if (x > maxxcoord) {
			maxxcoord = x;
		}
		if (y < minycoord) {
			minycoord = y;
		}
		else if (y > maxycoord) {
			maxycoord = y;
		}
	}

	minxcoord = UNSCALE (minxcoord, sip);
	maxxcoord = UNSCALE (maxxcoord, sip);
	minycoord = UNSCALE (minycoord, sip);
	maxycoord = UNSCALE (maxycoord, sip);

	/* We only generate square plots having equal scales on both	*/
	/* axes.  Determine the "span" of the plot, i.e., the length of	*/
	/* each axis in the plot.					*/

	xspan = maxxcoord - minxcoord;
	yspan = maxycoord - minycoord;

	if (xspan EQ 0.0) {
		if (yspan EQ 0.0) {
			/* Single point. */
			if (maxxcoord NE 0.0) {
				if (fabs (maxxcoord) >= fabs (maxycoord)) {
					span = 2.0 * fabs (maxxcoord);
				}
				else {
					span = 2.0 * fabs (maxycoord);
				}
			}
			else if (maxycoord NE 0.0) {
				span = 2.0 * fabs (maxycoord);
			}
			else {
				/* Single point at the origin. */
				span = 2.0;
			}
		}
		else {
			span = get_limit (yspan);
		}
	}
	else if (yspan EQ 0.0) {
		span = get_limit (xspan);
	}
	else if (xspan >= yspan) {
		span = get_limit (xspan);
	}
	else {
		span = get_limit (yspan);
	}

	/* Determine the minimum x axis value. */

	if (xspan EQ 0.0) {
		goto center_x;
	}
	else if ((0.0 <= minxcoord) AND (maxxcoord <= span)) {
		axmin = 0.0;
	}
	else if ((-span <= minxcoord) AND (maxxcoord <= 0.0)) {
		axmin = -span;
	}
	else if ((-0.5 * span <= minxcoord) AND (maxxcoord <= 0.5 * span)) {
		axmin = -0.5 * span;
	}
	else {
center_x:
		/* Center the x coordinates. */
		axmin = 0.5 * (minxcoord + maxxcoord - span);
	}
	axmax = axmin + span;

	/* Determine the minimum y axis value. */

	if (yspan EQ 0.0) {
		goto center_y;
	}
	else if ((0.0 <= minycoord) AND (maxycoord <= span)) {
		aymin = 0.0;
	}
	else if ((-span <= minycoord) AND (maxycoord <= 0.0)) {
		aymin = -span;
	}
	else if ((-0.5 * span <= minycoord) AND (maxycoord <= 0.5 * span)) {
		aymin = -0.5 * span;
	}
	else {
center_y:
		/* Center the y coordinates */
		aymin = 0.5 * (minycoord + maxycoord - span);
	}
	aymax = aymin + span;

	/* Good enough for now... */
	printf ("\n%g %g %g %g SetAxes\n", axmin, axmax, aymin, aymax);
}

/*
 * This routine returns a reasonable scale limit for the given quantity.
 * These are always 1, 2 or 5 times a power of 10.
 */

	static
	double
get_limit (

double		value		/* IN - value to get scale limit for */
)
{
int		i;
double		limit;

	if (value >= 1.0) {
		limit = 1.0;
		for (i = 0; i <= 20; i++) {
			if (limit >= value) return (limit);
			if (2.0 * limit >= value) return (2.0 * limit);
			if (5.0 * limit >= value) return (5.0 * limit);
			limit *= 10.0;
		}
		return (value);
	}

	limit = 1.0;
	for (i = 0; i <= 20; i++) {
		if (0.5 < value * limit) return (1.0 / limit);
		limit *= 10.0;
		if (2.0 < value * limit) return (5.0 / limit);
		if (1.0 < value * limit) return (2.0 / limit);
	}
	return (value);
}

/*
 * This routine generates some Postscript commands to plot each full-set
 * in the given mask.
 */

	void
plot_full_sets (

bitmap_t *		fset_mask,	/* IN - subset of full-sets to plot */
struct cinfo *		cip,		/* IN - compatibility info */
enum plot_size		plot_size	/* IN - size of plot to produce */
)
{
int			i;
int			n;
struct full_set *	fsp;
int *			vp1;
int *			vp2;
char			title [256];
char			buf1 [32];

	n = cip -> num_edges;

	if ((cip -> pts NE NULL) AND (cip -> full_trees NE NULL)) {
		/* Draw the FSTs with postscript. */
		for (i = 0; i < n; i++) {
			if (NOT BITON (fset_mask, i)) continue;
			fsp = cip -> full_trees [i];
			begin_plot (plot_size);
			(void) printf ("\tPlot_Terminals\n");
			fst_comment (fsp);
			draw_fst (fsp, cip);
			dist_to_string (buf1,
					cip -> cost [i],
					&(cip -> scale));
			(void) sprintf (title, "FST %lu,  Length = %s",
					(int32u) i, buf1);
			end_plot (title);
		}
		page_break ();
	}
	else {
		/* Just print the hyperedges */
		for (i = 0; i < n; i++) {
			if (NOT BITON (fset_mask, i)) continue;
			printf ("Edge %d: ", i);
			vp1 = cip -> edge [i];
			vp2 = cip -> edge [i + 1];
			while (vp1 < vp2) {
				printf ("%d ", *vp1++);
			}
			dist_to_string (buf1,
					cip -> cost [i],
					&(cip -> scale));
			printf ("%s\n", buf1);
		}
	}
}

/*
 * This routine generates some Postscript commands to plot each full-set
 * in the given mask.  Note that we "group" as many mutually-disjoint
 * full sets as possible on each plot so as to minimize the amount of
 * paper we spew...
 */

	void
plot_full_sets_grouped (

bitmap_t *		fset_mask,	/* IN - subset of full-sets to plot */
struct cinfo *		cip,		/* IN - compatibility info */
enum plot_size		plot_size	/* IN - size of plot to produce */
)
{
int			i;
int			j;
int			n;
int			nleft;
int			kmasks;
int			nmasks;
int			nplot;
bitmap_t *		left;
bitmap_t *		tmask;
int *			plist;
struct full_set *	fsp;
struct pset *		pts;
char *			cp1;
char *			cp2;
char			fsnums [110];
char			fsnum [8];
char			title [120];

	n = cip -> num_edges;
	nmasks = cip -> num_edge_masks;
	kmasks = cip -> num_vert_masks;

	left = NEWA (nmasks, bitmap_t);
	tmask = NEWA (kmasks, bitmap_t);
	plist = NEWA (n, int);

	/* Make a local copy of all full sets left to plot. */
	for (i = 0; i < nmasks; i++) {
		left [i] = fset_mask [i];
	}
	nleft = n;

	while (nleft > 0) {
		begin_plot (plot_size);

		for (i = 0; i < kmasks; i++) {
			tmask [i] = 0;
		}

		nplot = 0;
		cp1 = &fsnums [sizeof (fsnums)];
		*--cp1 = '\0';

		for (i = n - 1; i >= 0; i--) {
			if (NOT BITON (left, i)) continue;

			/* Skip full set "i" if not disjoint	*/
			/* with all others in this plot...	*/
			fsp = cip -> full_trees [i];
			pts = fsp -> terminals;
			for (j = 0; j < pts -> n; j++) {
				if (BITON (tmask, pts -> a [j].pnum)) break;
			}
			if (j < pts -> n) continue;

			(void) sprintf (fsnum, "%lu", (int32u) i);
			for (cp2 = fsnum; *cp2 NE '\0'; cp2++) {
			}

			/* Stop if label does not fit! */
			if ((cp2 - fsnum) + 2 > (cp1 - fsnums)) break;

			while (cp2 > fsnum) {
				*--cp1 = *--cp2;
			}
			*--cp1 = ' ';
			*--cp1 = ',';

			plist [nplot++] = i;
			CLRBIT (left, i);
			--nleft;

			fsp = cip -> full_trees [i];
			fst_comment (fsp);
			draw_fst (fsp, cip);

			pts = fsp -> terminals;
			for (j = 0; j < pts -> n; j++) {
				SETBIT (tmask, pts -> a [j].pnum);
			}
		}

		(void) printf ("\tPlot_Terminals\n");
		(void) sprintf (title,
				"FST%s %s.",
				(nplot > 1) ? "s" : "",
				cp1 + 2);
		end_plot (title);
	}

	page_break ();

	free ((char *) plist);
	free ((char *) tmask);
	free ((char *) left);
}

/*
 * This routine generates some Postscript commands to plot a SUBSET of
 * the given full-sets in overlaid fashion.
 */

	void
overlay_plot_subset (

char *			title,		/* IN - title to display with. */
bitmap_t *		fset_mask,	/* IN - subset of full-sets to plot */
struct cinfo *		cip,		/* IN - compatibility info */
enum plot_size		plot_size	/* IN - size of plot to produce */
)
{
int			i;
int			n;
int *			vp1;
int *			vp2;
struct full_set *	fsp;
char			buf1 [32];

	n = cip -> num_edges;

	if ((cip -> pts NE NULL) AND (cip -> full_trees NE NULL)) {
		/* Draw the FSTs with postscript. */
		begin_plot (plot_size);
		(void) printf ("\tPlot_Terminals\n");

		for (i = 0; i < n; i++) {
			if (NOT BITON (fset_mask, i)) continue;