btsearch.c

生成直角Steiner树的程序包

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

	File:	btsearch.c
	Rev:	a-1
	Date:	11/30/2000

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

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

	Routines to perform the backtrack search for a solution.

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

	Modification Log:

	a-1:	11/30/2000	warme
		: Created.

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


/*
 * Global Routines
 */

double			backtrack_search (struct cinfo *, bitmap_t *);
void			initialize_btsearch (void);

#if 0
struct full_set *	sort_full_trees (struct full_set *);
#endif


/*
 * External References
 */

	/* none */


/*
 * Local Constants
 */

#define	MAX_TERMINALS	32


/*
 * Local Types
 */

struct sinfo {
	struct cinfo *		cip;

	/* the best solution so far... */
	dist_t			best_length;
	int			best_count;
	bitmap_t		best_solution;
	bool			found;

	/* Current partial solution... */
	bitmap_t		solution;

	/* arrays accessed in stack fashion during backtrack... */
	bitmap_t *		terms_left;
	bitmap_t *		compat;
	bitmap_t *		incompat;

	/* New ones we have to initialize */
	bitmap_t *		edge_vmasks;
	bitmap_t *		vert_emasks;
	bitmap_t *		cmasks;
	bitmap_t *		incmasks;
};


/*
 * Local Routines
 */

static void			allocate_search_stacks (struct sinfo *);
static bool			find_inaccessible_terminal (struct sinfo *,
							    int);
static pnum_t			find_starting_point (struct cinfo *);
static void			free_search_stacks (struct sinfo *);
static void			init_compat_incompat_masks (struct sinfo *);
static void			init_edge_vmasks (struct sinfo *);
static void			init_vert_emasks (struct sinfo *);
static bool			perform_search (struct sinfo *, bitmap_t *);
static void			search_recurse (struct sinfo *,
						int, int, dist_t);


/*
 * Local Variables
 */

static int8u *		one_bits_in_byte [256 + 1];
static int8u		one_bits_in_byte_array [1024];

/*
 * Perform all initialization for the backtrack search that only needs
 * to be done once -- no matter how many times the search is called.
 *
 * Currently all we need to do is initialize the "one-bits-in-byte" table.
 */

	void
initialize_btsearch (void)

{
int		i;
int		j;
int		byte;
int8u *		p;

	p = &one_bits_in_byte_array [0];
	for (i = 0; i < 256; i++) {
		one_bits_in_byte [i] = p;
		byte = i;
		j = 0;
		while (byte > 0) {
			if ((byte & 0x01) NE 0) {
				*p++ = j;
			}
			++j;
			byte >>= 1;
		}
	}

	/* Terminate last table entry. */
	one_bits_in_byte [i] = p;
}

/*
 * This routine performs a backtrack search for a Steiner Minimal Tree of
 * the given point set.  It composes a minimum-length solution from some
 * combination of the given full-sets.
 */

	double
backtrack_search (

struct cinfo *		cip,		/* IN - compatibility info */
bitmap_t *		smt_mask	/* OUT - SMT as a set of full-sets */
)
{
bool			failed;
struct sinfo		sinfo;

	if ((cip -> num_vert_masks NE 1) OR (cip -> num_edge_masks NE 1)) {
		fatal ("backtrack_search: Bug 1.");
	}

	/* First, zero out the result bit-mask... */
	smt_mask [0] = 0;

	/* Create and initialize a search-context structure containing	*/
	/* worst-case memory allocations...				*/
	sinfo.cip = cip;
	allocate_search_stacks (&sinfo);

	init_edge_vmasks (&sinfo);
	init_vert_emasks (&sinfo);
	init_compat_incompat_masks (&sinfo);

	failed = perform_search (&sinfo, smt_mask);

	if (failed) {
		fatal ("backtrack_search: Bug 2.");
	}

	free ((char *) (sinfo.incmasks));
	free ((char *) (sinfo.cmasks));
	free ((char *) (sinfo.vert_emasks));
	free ((char *) (sinfo.edge_vmasks));

	/* Free up the search stacks. */
	free_search_stacks (&sinfo);

	return (sinfo.best_length);
}

/*
 * Initialize an array containing one mask per edge.  The mask indicates
 * which vertices the edge contains.
 */

	static
	void
init_edge_vmasks (

struct sinfo *	sip		/* IN/OUT - search/compatibility info */
)
{
int			i;
int			j;
int			nedges;
struct cinfo *		cip;
int *			vp1;
int *			vp2;
bitmap_t *		array;
bitmap_t		mask;

	cip = sip -> cip;

	nedges	= cip -> num_edges;

	array = NEWA (nedges, bitmap_t);

	for (i = 0; i < nedges; i++) {
		mask = 0;
		vp1 = cip -> edge [i];
		vp2 = cip -> edge [i + 1];
		while (vp1 < vp2) {
			j = *vp1++;
			mask |= (1 << j);
		}
		array [i] = mask;
	}

	sip -> edge_vmasks = array;
}

/*
 * Initialize an array containing one mask per vertex.  The mask indicates
 * which edges the vertex is incident to.
 */

	static
	void
init_vert_emasks (

struct sinfo *	sip		/* IN/OUT - search/compatibility info */
)
{
int			i;
int			j;
int			nverts;
struct cinfo *		cip;
int *			ep1;
int *			ep2;
bitmap_t *		array;
bitmap_t		mask;

	cip = sip -> cip;

	nverts	= cip -> num_verts;

	array = NEWA (nverts, bitmap_t);

	for (i = 0; i < nverts; i++) {
		mask = 0;
		ep1 = cip -> term_trees [i];
		ep2 = cip -> term_trees [i + 1];
		while (ep1 < ep2) {
			j = *ep1++;
			mask |= (1 << j);
		}
		array [i] = mask;
	}

	sip -> vert_emasks = array;
}

/*
 * Initialize an array containing one mask per edge.  The mask indicates
 * which edges are COMPATIBLE with the given edge.  In this case we
 * assume two edges are compatible if they share exactly 1 vertex.
 */

	static
	void
init_compat_incompat_masks (

struct sinfo *	sip		/* IN/OUT - search/compatibility info */
)
{
int			j;
int			k;
int			e1;
int			e2;
int			nedges;
struct cinfo *		cip;
int *			vp1;
int *			vp2;
int *			ep1;
int *			ep2;
bitmap_t *		carray;
bitmap_t *		iarray;
bitmap_t		edges_seen;
bitmap_t		e1_vmask;
bitmap_t		cmask;
bitmap_t		imask;
bitmap_t		mask;
bitmap_t *		vmasks;

	cip = sip -> cip;

	nedges	= cip -> num_edges;

	carray = NEWA (nedges, bitmap_t);
	iarray = NEWA (nedges, bitmap_t);

	vmasks = sip -> edge_vmasks;

	for (e1 = 0; e1 < nedges; e1++) {
		imask = 0;
		cmask = 0;
		edges_seen = 0;
		e1_vmask = vmasks [e1];
		vp1 = cip -> edge [e1];
		vp2 = cip -> edge [e1 + 1];
		while (vp1 < vp2) {
			j = *vp1++;
			ep1 = cip -> term_trees [j];
			ep2 = cip -> term_trees [j + 1];
			while (ep1 < ep2) {
				e2 = *ep1++;
				if ((edges_seen & (1 << e2)) NE 0) continue;
				edges_seen |= (1 << e2);
				mask = e1_vmask & vmasks [e2];
				k = NBITSON (mask);
				if (k EQ 1) {
					cmask |= (1 << e2);
				}
				else {
					/* k should be > 1 here! */
					imask |= (1 << e2);
				}
			}
		}
		carray [e1] = cmask;
		iarray [e1] = imask;
	}

	sip -> cmasks	= carray;
	sip -> incmasks	= iarray;
}

/*
 * This routine pre-sorts the list of full-sets and re-numbers them so that
 * at each node in the search tree, we select candidate sub-trees in an
 * order that heuristically puts the most likely solutions first.  This has
 * a tendency to reduce the search space by producing earlier length cutoffs
 * on the later sub-trees.
 */

#if 0

	struct full_set *
sort_full_trees (

struct full_set *	fsp		/* IN - full-trees to sort. */
)
{
int			i;
int			n;
int			h;
struct full_set *	tmp;
struct full_set **	trees;
struct full_set **	endp;
struct full_set **	p1;
struct full_set **	p2;
struct full_set **	p3;
struct full_set **	p4;
dist_t			dist_1;
dist_t			dist_2;
int			n_1;
int			n_2;
struct full_set *	root;
struct full_set **	hookp;

	trees = put_trees_in_array (fsp, &n);

	endp = trees + n;

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

	do {
		h = h / 3;
		p4 = trees + h;
		p1 = p4;
		while (p1 < endp) {
			tmp = *p1;
			dist_1 = tmp -> tree_len;
			n_1	= tmp -> terminals -> n - 1;
			p2 = p1;
			while (TRUE) {
				p3 = (p2 - h);
				dist_2	= (*p3) -> tree_len;
				n_2	= (*p3) -> terminals -> n - 1;
				if ((dist_2 * n_1) <= (dist_1 * n_2)) break;
				*p2 = *p3;
				p2 = p3;
				if (p2 < p4) break;
			}
			*p2 = tmp;
			++p1;
		}
	} while (h > 1);

	i = 0;
	root = NULL;
	hookp = &root;
	p1 = trees;