genps.c

生成直角Steiner树的程序包

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

		end_plot (title);
	}
	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 draws a single full Steiner tree.
 */

	static
	void
draw_fst (

struct full_set *	fsp,		/* IN - FST to draw */
struct cinfo *		cip		/* IN - compatibility info */
)
{
	switch (cip -> metric) {
	case RECTILINEAR:
		draw_rfst (fsp, cip);
		break;

	case EUCLIDEAN:
		draw_efst (fsp, cip);
		break;

	default:
		fatal ("draw_fst: Bug 1.");
		break;
	}
}

/*
 * This routine draws a single rectilinear FST.
 *
 * NOTE:  We ASSUME that the given FST graph represents a left-most Hwang
 * topology!  (Beyond this, we don't really care about the ordering of
 * terminals, edges or Steiner points.)  If we therefore draw all
 * "diagonal" (i.e., neither vertical nor horizontal) edges in left-most
 * fashion (vertical segment to left of the horizontal segment), then the
 * FST will be correctly drawn as a left-most Hwang topology.
 */

	static
	void
draw_rfst (

struct full_set *	fsp,		/* IN - full set to draw */
struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			nt;
struct point *		p1;
struct point *		p2;
struct pset *		terms;
struct pset *		steins;
struct edge *		ep;
char			cbufx [32];
char			cbufy [32];
char			buf1 [256];
char			buf2 [256];

	terms = fsp -> terminals;
	steins = fsp -> steiners;

	nt = terms -> n;

	ep = fsp -> edges;
	for (i = 0; i < fsp -> nedges; i++, ep++) {
		if (ep -> p1 < nt) {
			p1 = &(terms -> a [ep -> p1]);
			(void) sprintf (buf1, "%d T", p1 -> pnum);
		}
		else {
			p1 = &(steins -> a [ep -> p1 - nt]);
			coord_to_string (cbufx, p1 -> x, &(cip -> scale));
			coord_to_string (cbufy, p1 -> y, &(cip -> scale));
			(void) sprintf (buf1, "%s\t%s", cbufx, cbufy);
		}

		if (ep -> p2 < nt) {
			p2 = &(terms -> a [ep -> p2]);
			(void) sprintf (buf2, "%d T", p2 -> pnum);
		}
		else {
			p2 = &(steins -> a [ep -> p2 - nt]);
			coord_to_string (cbufx, p2 -> x, &(cip -> scale));
			coord_to_string (cbufy, p2 -> y, &(cip -> scale));
			(void) sprintf (buf2, "%s\t%s", cbufx, cbufy);
		}

		if ((p1 -> x EQ p2 -> x) OR (p1 -> y EQ p2 -> y)) {
			(void) printf ("\t%s\t%s\tS\n",
				       buf1,
				       buf2);
		}
		else if (p1 -> x < p2 -> x) {
			(void) printf ("\t%s\t%s\tC\n",
				       buf1,
				       buf2);
		}
		else {
			(void) printf ("\t%s\t%s\tC\n",
				       buf2,
				       buf1);
		}
	}
}

/*
 * This routine draws a single Euclidean FST.
 */

	static
	void
draw_efst (

struct full_set *	fsp,		/* IN - FST to draw */
struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			j;
int			nt;
struct point *		p1;
struct pset *		terms;
struct pset *		steins;
struct edge *		ep;
char			buf1 [32];
char			buf2 [32];

	terms = fsp -> terminals;
	steins = fsp -> steiners;

	nt = terms -> n;

	ep = fsp -> edges;
	for (i = 0; i < fsp -> nedges; i++, ep++) {
		j = ep -> p1;
		if (j < nt) {
			p1 = &(terms -> a [j]);
			(void) printf ("\t%d T", p1 -> pnum);
		}
		else {
			p1 = &(steins -> a [j - nt]);
			coord_to_string (buf1, p1 -> x, &(cip -> scale));
			coord_to_string (buf2, p1 -> y, &(cip -> scale));
			(void) printf ("\t%s\t%s", buf1, buf2);
		}
		j = ep -> p2;
		if (j < nt) {
			p1 = &(terms -> a [j]);
			(void) printf ("\t%d T\tS\n", p1 -> pnum);
		}
		else {
			p1 = &(steins -> a [j - nt]);
			coord_to_string (buf1, p1 -> x, &(cip -> scale));
			coord_to_string (buf2, p1 -> y, &(cip -> scale));
			(void) printf ("\t%s\t%s\tS\n", buf1, buf2);
		}
	}
}

/*
 * This routine plots an LP solution.  This is a set of full sets in which
 * full set i has weight Wi, where 0 <= Wi <= 1.  The full sets with
 * weight of 1 are drawn normally.  The fractional ones are drawn as
 * gray-scale "stars" emanating from the center of mass of the terminals.
 */

	void
plot_lp_solution (

char *		title,		/* IN - title for plot. */
double *	weights,	/* IN - weight of each full set. */
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;

	n = cip -> num_edges;

	if ((cip -> pts NE NULL) AND (cip -> full_trees NE NULL)) {
		/* Draw the FSTs with postscript. */
		begin_plot (plot_size);

		for (i = 0; i < n; i++) {
			if (weights [i] <= 0.000001) continue;
			fsp = cip -> full_trees [i];
			draw_fractional_fst (fsp, weights [i], cip);
		}

		(void) printf ("\tPlot_Terminals\n");

		end_plot (title);
	}
	else {
		/* Just output the weighted hyperedges. */
		printf ("\n");
		for (i = 0; i < n; i++) {
			if (weights [i] <= 0.000001) continue;
			printf ("x^%d = %10.8g\t", i, weights [i]);
			vp1 = cip -> edge [i];
			vp2 = cip -> edge [i + 1];
			while (vp1 < vp2) {
				printf (" %d", *vp1++);
			}
			printf ("\n");
		}
	}
}

/*
 * This routine plots a particular subtour violation S within an LP solution.
 * Only FSTs having at least 2 vertices in the subtour S are displayed.
 * The full sets with weight of 1 are drawn normally.  The fractional ones
 * are drawn as gray-scale "stars" emanating from the center of mass of the
 * terminals.
 */

	void
plot_subtour (

char *		title,		/* IN - title for plot. */
double *	weights,	/* IN - weight of each full set. */
struct cinfo *	cip,		/* IN - compatibility info. */
bitmap_t *	S,		/* IN - subtour to plot. */
enum plot_size	plot_size	/* IN - size of plot to produce. */
)
{
int			i;
int			j;
int			k;
int			n;
struct full_set *	fsp;
int *			vp1;
int *			vp2;

	n = cip -> num_edges;

	if ((cip -> pts NE NULL) AND (cip -> full_trees NE NULL)) {
		/* Draw the FSTs with postscript. */
		begin_plot (plot_size);

		for (i = 0; i < n; i++) {
			if (weights [i] <= 0.000001) continue;
			k = 0;
			vp1 = cip -> edge [i];
			vp2 = cip -> edge [i + 1];
			while (vp1 < vp2) {
				j = *vp1++;
				if (BITON (S, j)) {
					++k;
				}
			}
			if (k < 2) continue;
			fsp = cip -> full_trees [i];
			draw_fractional_fst (fsp, weights [i], cip);
		}

		(void) printf ("\t0.75 setgray\n");
		(void) printf ("\tPlot_Terminals\n");
		(void) printf ("\t0 setgray\n");

		for (j = 0; j < cip -> num_verts; j++) {
			if (NOT BITON (S, j)) continue;
			printf ("\t%d\tPT\n", j);
		}

		end_plot (title);
	}
	else {
		/* Just output the weighted hyperedges. */
		printf ("\n");
		for (i = 0; i < n; i++) {
			if (weights [i] <= 0.000001) continue;
			printf ("x^%d = %10.8g\t", i, weights [i]);
			vp1 = cip -> edge [i];
			vp2 = cip -> edge [i + 1];
			while (vp1 < vp2) {
				printf (" %d", *vp1++);
			}
			printf ("\n");
		}
	}
}

/*
 * This routine draws a single fractional-weight full set.  We draw these
 * as a "star" using the center-of-mass of the terminals as the hub.  The
 * weight is used to determine the darkness of the lines.
 */

	static
	void
draw_fractional_fst (

struct full_set *	fsp,		/* IN - full set to draw */
double			weight,		/* IN - weight for full set */
struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			n;
coord_t			cx;
coord_t			cy;
struct pset *		terms;
struct point *		p1;
char			buf1 [32];
char			buf2 [32];

	terms = fsp -> terminals;

	if (weight + 0.000001 >= 1.0) {
		/* Draw integral full sets "normally"... */
		fst_comment (fsp);
		(void) printf ("\t0 setgray\n");
		draw_fst (fsp, cip);
		return;
	}

	fst_comment (fsp);

	n = terms -> n;

	/* Determine the coordinates of the "hub". */
	p1 = &(terms -> a [0]);
	cx = 0.0;
	cy = 0.0;
	for (i = 0; i < n; p1++, i++) {
		cx += p1 -> x;
		cy += p1 -> y;
	}
	cx /= n;
	cy /= n;
	coord_to_string (buf1, cx, &(cip -> scale));
	coord_to_string (buf2, cy, &(cip -> scale));

	(void) printf ("\t%f setgray\n", 1.0 - weight);

	p1 = &(terms -> a [0]);
	for (i = 0; i < n; p1++, i++) {
		(void) printf ("\t%d T\t%s\t%s\tS\n",
			       p1 -> pnum, buf1, buf2);
	}
}

/*
 * This routine emits a Postscript comment describing the FST.
 */

	static
	void
fst_comment (

struct full_set *	fsp		/* IN - full set to describe */
)
{
int			i;
int			n;
struct pset *		terms;
struct point *		p1;

	terms = fsp -> terminals;

	(void) printf (" %% fs%d:", fsp -> tree_num);
	n = terms -> n;
	p1 = &(terms -> a [0]);
	for (i = 0; i < n; p1++, i++) {
		(void) printf (" %lu", (int32u) (p1 -> pnum));
	}
	(void) printf ("\n");
}

/*
 * This routine draws a line segment between two points.
 */

	void
draw_segment (

struct point *		p1,	/* IN - first point */
struct point *		p2,	/* IN - second point */
struct scale_info *	sip	/* IN - problem scaling info */
)
{
char		buf1 [32];
char		buf2 [32];
char		buf3 [32];
char		buf4 [32];

	coord_to_string (buf1, p1 -> x, sip);
	coord_to_string (buf2, p1 -> y, sip);
	coord_to_string (buf3, p2 -> x, sip);
	coord_to_string (buf4, p2 -> y, sip);

	(void) printf ("	%s	%s	%s	%s	S\n",
		       buf1, buf2, buf3, buf4);
}

/*
 * This routine emits appropriate Postscript code to begin a plot of
 * the given size.  If this is the first plot on a page, then we also
 * emit DSC comments for the page number.  This helps out ghostview and
 * other Postscript previewers.
 */

	void
begin_plot (

enum plot_size		size		/* IN - size of plot to begin */
)
{
	current_plot_size = size;
	switch (size) {
	case BIG_PLOT:
		page_break ();
		announce_new_page ();
		(void) printf ("BeginPlot\n");
		break;

	case SMALL_PLOT:
		if (small_plots_on_page EQ 0) {
			announce_new_page ();
		}
		(void) printf ("BeginSmallPlot\n");
		break;

	default:
		fatal ("begin_plot: Bug 1.");
		break;
	}
}

/*
 * This routine emits appropriate Postscript code to end the plot that
 * is currently in progress.  We also track the number of finished
 * plots per page here.
 */

	void
end_plot (

char *			title		/* IN - title for plot */
)
{
	(void) printf ("  (%s)\n", title);
	switch (current_plot_size) {
	case BIG_PLOT:
		(void) printf ("EndPlot\n\n");
		break;

	case SMALL_PLOT:
		(void) printf ("EndSmallPlot2\n\n");
		++small_plots_on_page;
		if (small_plots_on_page >= SMALL_PLOTS_PER_PAGE) {
			small_plots_on_page = 0;
		}
		break;

	default:
		fatal ("end_plot: Bug 1.");
		break;
	}
}

/*
 * This routine puts a %%Page: comment into the output to mark a page
 * boundary.  This is for the benefit of Ghostview and other Postscript
 * previewers.
 */

	static
	void
announce_new_page (void)

{
	++current_page;
	(void) printf ("%%%%Page: %lu %lu\n",
		       (int32u) current_page,
		       (int32u) current_page);
}

/*
 * This routine introduces a page break.  This is needed when doing
 * small plots, and the page has not yet filled up.
 */

	static
	void
page_break (void)

{
	if (small_plots_on_page NE 0) {
		(void) printf ("FlushSmallPlot\n");
		small_plots_on_page = 0;
	}
}