sec_heur.c

生成直角Steiner树的程序包

bitmap_t *		emark,		/* IN - edges on stack */
bitmap_t *		vmark,		/* IN - vertices on stack */
bitmap_t *		stour,		/* IN - temporary vertex mask */
bitmap_t *		cc_verts,	/* OUT - vertices of connected comp */
bitmap_t *		cc_edges,	/* OUT - edges of connected comp */
int *			stack,		/* IN - base of vertex stack */
int *			sp,		/* IN - top of vertex stack */
int *			num_cycles,	/* IN/OUT - number of cycles found */
struct constraint *	cp,		/* IN - list of constraints */
struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			j;
int			v;
int			e2;
int			kmasks;
struct constraint *	tmp;
struct constraint *	newp;
int *			ep1;
int *			ep2;
int *			vp1;
int *			vp2;
int *			vp3;

	/* Stop nearly-infinite loops on highly cyclic stuff... */
	if (*num_cycles >= CYCLE_LIMIT) return (cp);

	if (BITON (emark, e)) {
		/* We have visited this edge before (higher up on	*/
		/* the stack).  We also know it was not the immediately	*/
		/* preceeding edge.  Therefore we have a cycle.  Read	*/
		/* the intervening vertices off the stack...		*/
		kmasks = cip -> num_vert_masks;
		for (i = 0; i < kmasks; i++) {
			stour [i] = 0;
		}
		if (sp < &stack [4]) {
			/* Stack too short for this! */
			fatal ("cwalk: Bug 1.");
		}
		for (;;) {
			if (sp < &stack [2]) {
				/* Cycle edge not found on stack! */
				fatal ("cwalk: Bug 2.");
			}
			sp -= 2;
			SETBIT (stour, sp [1]);
			if (sp [0] EQ e) break;
		}
		/* We should see every cycle twice.  Check if we have	*/
		/* seen this one before...				*/
		tmp = check_unique_subtour (stour, kmasks, cp);
#if 0
		if (tmp NE cp) {
			++(*num_cycles);
		}
#else
		/* Count duplicates too!  We don't want to	*/
		/* spend much time doing this...		*/
		++(*num_cycles);
#endif
		return (tmp);
	}

	/* This edge does NOT currently appear on the	*/
	/* stack.  Push it onto the stack now...	*/
	sp [0] = e;
	SETBIT (emark, e);
	SETBIT (cc_edges, e);

	/* Mark this edge as being traversed AT LEAST once... */
	CLRBIT (edges_left, e);

	/* Now walk to all OTHER vertices in this edge -- all except	*/
	/* for the one (if any) by which we entered this edge.		*/
	vp1 = cip -> edge [e];
	vp2 = cip -> edge [e + 1];
	while (vp1 < vp2) {
		v = *vp1++;
		if (v EQ vertex) continue;

		if (BITON (vmark, v)) {
			/* We have visited this vertex before (higher	*/
			/* up on the stack).  We also know it was not	*/
			/* the immediately preceeding vertex.		*/
			/* Therefore we have a cycle.  Read it off the	*/
			/* stack...					*/
			kmasks = cip -> num_vert_masks;
			for (j = 0; j < kmasks; j++) {
				stour [j] = 0;
			}
			SETBIT (stour, v);
			vp3 = sp;
			for (;;) {
				if (vp3 <= stack) {
					/* cycle vertex not found on	*/
					/* stack!			*/
					fatal ("cwalk: Bug 3.");
				}
				vp3 -= 2;
				j = vp3 [1];
				if (j EQ v) break;
				SETBIT (stour, j);
			}

			tmp = check_unique_subtour (stour, kmasks, cp);
#if 0
			if (tmp NE cp) {
				++(*num_cycles);
			}
#else
			/* Count duplicates too!  We don't want to	*/
			/* spend much time doing this...		*/
			++(*num_cycles);
#endif
			cp = tmp;
			continue;
		}

		/* This vertex does NOT currently appear on the	*/
		/* stack.  Push it onto the stack now...	*/
		sp [1] = v;
		SETBIT (vmark, v);

		/* This vertex is part of the connected component... */
		SETBIT (cc_verts, v);

		/* Traverse every valid edge going out of vertex v,	*/
		/* (except the one via which we entered vertex v)...	*/
		ep1 = cip -> term_trees [v];
		ep2 = cip -> term_trees [v + 1];
		while (ep1 < ep2) {
			e2 = *ep1++;
			if (NOT BITON (edge_mask, e2)) continue;
			if (e2 EQ e) continue;
			/* Recursively walk subtree looking for cycles... */
			cp = cwalk (e2,
				    v,
				    edge_mask,
				    edges_left,
				    emark,
				    vmark,
				    stour,
				    cc_verts,
				    cc_edges,
				    stack,
				    sp + 2,
				    num_cycles,
				    cp,
				    cip);
			if (*num_cycles >= CYCLE_LIMIT) break;
		}
		CLRBIT (vmark, v);	/* Taking vertex v off the stack */
		if (*num_cycles >= CYCLE_LIMIT) break;
	}

	CLRBIT (emark, e);

	return (cp);
}

/*
 * This routine looks for "almost integer" cycles.  We are given an
 * acyclic connected component consisting of integral edges.  We are
 * also given a list of all of the fractional edges.  Each fractional
 * edge that shares two or more vertices in common with the integral
 * connected component therefore represents an SEC violation.  Given that
 * they intersect at vertices A and B there is a unique path from A to B
 * in the connected component.  We use a brute force DFS to recover the
 * actual vertices of the cycle.
 */

	static
	struct constraint *
find_almost_integer_cycles (

int			num_frac,	/* IN - number of fractional edges */
int *			frac_enums,	/* IN - list of fractional edges */
bitmap_t *		cc_verts,	/* IN - vertices of connected comp */
bitmap_t *		cc_edges,	/* IN - edges of connected comp */
bitmap_t *		stour,		/* IN - scratch vertex map */
struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			j;
int			k;
int			kmasks;
int			e;
int			t1;
int			t2;
int *			vp1;
int *			vp2;
int *			vp3;
struct constraint *	cp;
bool			found;

	kmasks = cip -> num_vert_masks;

	cp = NULL;

	while (num_frac > 0) {
		e = *frac_enums++;
		--num_frac;

		/* Find each vertex pair (if any) in the CC... */
		vp1 = cip -> edge [e];
		vp3 = cip -> edge [e + 1];
		while (vp1 < vp3) {
			t1 = *vp1++;
			if (NOT BITON (cc_verts, t1)) continue;
			vp2 = vp1;
			while (vp2 < vp3) {
				t2 = *vp2++;
				if (NOT BITON (cc_verts, t2)) continue;

				/* We have a new cycle!  Now identify it... */
				for (k = 0; k < kmasks; k++) {
					stour [k] = 0;
				}
				found = fwalk (t1,
					       t2,
					       cc_edges,
					       stour,
					       cip);
				if (NOT found) {
					fatal ("find_almost_integer_cycle: Bug 1.");
				}

				/* Could have seen this same cycle before... */
				cp = check_unique_subtour (stour, kmasks, cp);
			}
		}
	}

	return (cp);
}

/*
 * This routine recursively finds a path from vertex t1 to vertex
 * t2 in the given (acyclic) connected component.  It returns TRUE
 * when the path has been found.
 */

	static
	bool
fwalk (

int			t1,		/* IN - first vertex */
int			t2,		/* IN - last vertex */
bitmap_t *		cc_edges,	/* IN - edges of connected comp */
bitmap_t *		path,		/* OUT - vertices along path */
struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			e;
int			t3;
int *			ep1;
int *			ep2;
int *			vp1;
int *			vp2;
bool			found;

	if (BITON (path, t1)) {
		/* We've been here before... */
		return (FALSE);
	}

	SETBIT (path, t1);

	if (t1 EQ t2) return (TRUE);

	ep1 = cip -> term_trees [t1];
	ep2 = cip -> term_trees [t1 + 1];
	while (ep1 < ep2) {
		e = *ep1++;
		if (NOT BITON (cc_edges, e)) continue;

		CLRBIT (cc_edges, e);
		found = FALSE;
		vp1 = cip -> edge [e];
		vp2 = cip -> edge [e + 1];
		while (vp1 < vp2) {
			t3 = *vp1++;
			found = fwalk (t3, t2, cc_edges, path, cip);
			if (found) break;
		}
		SETBIT (cc_edges, e);
		if (found) return (TRUE);
	}

	CLRBIT (path, t1);

	return (FALSE);
}

/*
 * This routine checks the given subtour to see if it is unique.  If so
 * a new constraint is added to the given list.  Otherwise, the given
 * constraint list is returned unchanged.
 */

	struct constraint *
check_unique_subtour (

bitmap_t *		stour,		/* IN - subtour to check */
int			kmasks,		/* IN - number of vertex masks */
struct constraint *	cp		/* IN - current constraint list */
)
{
struct constraint *	p;
bitmap_t *		bp1;
bitmap_t *		bp2;
bitmap_t *		bp3;

	for (p = cp; p NE NULL; p = p -> next) {
		if (is_equal (stour, p -> mask, kmasks)) {
			/* Already seen this subtour... */
			return (cp);
		}
	}

#if 0
	print_mask (" % Integral cycle:", stour, kmasks * BPW);
#endif

	/* Not seen before -- record it. */
	p = NEW (struct constraint);
	bp1 = NEWA (kmasks, bitmap_t);

	p -> next	= cp;
	p -> iteration	= 0;
	p -> type	= CT_SUBTOUR;
	p -> mask	= bp1;
	bp2 = stour;
	bp3 = bp2 + kmasks;
	while (bp2 < bp3) {
		*bp1++ = *bp2++;
	}
	return (p);
}

/*
 * This routine returns TRUE if-and-only-if the two bit-masks
 * are identical.
 */

	bool
is_equal (

bitmap_t *	bp1,		/* IN - first set. */
bitmap_t *	bp2,		/* IN - second set. */
int		nmasks		/* IN - number of masks in set. */
)
{
int		i;

	for (i = 0; i < nmasks; i++) {
		if (*bp1 NE *bp2) return (FALSE);
		++bp1;
		++bp2;
	}

	return (TRUE);
}

/*
 * This routine finds violated SEC's by exhaustively enumerating all
 * subsets of size 2 or more.  We return a list of the constraints that
 * were found.
 */

#ifdef	OLD_ENUMERATION

	struct constraint *
enumerate_all_subtours (

struct comp *		comp,		/* IN - component to check. */
struct constraint *	cp,		/* IN - existing list of constraints */
struct bbinfo *		bbip		/* IN - branch-and-bound info */
)
{
int			i;
int			k;
int			nverts;
double			rhs;
bitmap_t *		chosen;
int *			clist;

	nverts = comp -> num_verts;

	k = BMAP_ELTS (nverts);

	clist  = NEWA (nverts, int);
	chosen = NEWA (k, bitmap_t);

	for (i = 0; i < k; i++) {
		chosen [i] = 0;
	}

#if 0
	tracef (" %% Exhaustively enumerating %d congested vertices.\n", nverts);
#endif


	for (i = 2; i <= nverts; i++) {
		/* Look for subtours of size "i". */
		rhs = ((double) (i - 1)) + FUZZ;
		cp = enumerate_subtours (i,
					 0,
					 rhs,
					 chosen,
					 &clist [0],
					 &clist [0],
					 comp,
					 cp,
					 bbip);
	}

	free ((char *) chosen);
	free ((char *) clist);

	return (cp);
}

/*
 * This routine finds violated SEC's by explicitly enumerating subsets
 * of increasing cardinality.  Only the vertices of the given congested
 * component are examined.  We return a list of the constraints that
 * were found.
 */

	struct constraint *
find_small_subtours (

struct comp *		comp,		/* IN - component to check. */
struct constraint *	cp,		/* IN - existing list of constraints */
struct bbinfo *		bbip		/* IN - branch-and-bound info */
)
{
int			i;
int			k;
int			nverts;
int			klimit;
int			ticks_limit;
cpu_time_t		t0;
cpu_time_t		t1;
bitmap_t *		chosen;
int *			clist;
double			est;
double			rhs;
char			tbuf [32];

	nverts = comp -> num_verts;

	k = BMAP_ELTS (nverts);

	clist  = NEWA (nverts, int);
	chosen = NEWA (k, bitmap_t);

	for (i = 0; i < k; i++) {
		chosen [i] = 0;
	}

	tracef (" %% Enumerating %d congested vertices.\n", nverts);

	t0 = get_cpu_time ();

	/* Determine cardinality limit for partial enumeration. */

	if (nverts <= SEC_ENUM_LIMIT) {
		klimit = nverts;
	}
	else if (nverts <= 2 * SEC_ENUM_LIMIT) {
		klimit = 5;
	}
	else if (nverts <= 3 * SEC_ENUM_LIMIT) {
		klimit = 3;
	}
	else {
		klimit = 2;
	}

	/* Establish time limit for each cardinality. */
	ticks_limit = nverts * TICKS_PER_SEC;

	/* Don't need to check 2-vertex subtours if they are	*/
	/* already present in the constraint pool!		*/
	i = Seed_Pool_With_2SECs ? 3 : 2;

	for (; i <= klimit; i++) {
#if 0
		tracef (" %% Checking %d subtours\n", i);
#endif

		/* Look for subtours of size "i". */
		rhs = ((double) (i - 1)) + FUZZ;
		cp = enumerate_subtours (i,
					 0,
					 rhs,
					 chosen,
					 &clist [0],
					 &clist [0],
					 comp,
					 cp,
					 bbip);

		/* Determine how long this took... */
		t1 = get_cpu_time ();
#if 0
		convert_cpu_time (t1 - t0, tbuf);
		(void) tracef (" %%	%s seconds\n", tbuf);
#endif

		/* if we found any violations, get out! */
		if (cp NE NULL) break;

		/* Estimate how long the next pass will take... */
		est = ((double) (nverts - i)) / ((double) (i + 1));
		est *= (t1 - t0);
		if (est > ticks_limit) {
			/* Do not take more than specified	*/
			/* number of ticks...			*/
			break;
		}
		t0 = t1;
	}

	free ((char *) chosen);
	free ((char *) clist);

	return (cp);
}

/*
 * This routine recursively enumerates subsets of size k of the
 * congested vertices.
 */

	static
	struct constraint *
enumerate_subtours (

int			k,		/* IN - size of subset to choose */
int			t,		/* IN - next vertex to take/omit */
double			rhs,		/* IN - required right-hand-side */
bitmap_t *		chosen,		/* IN - component vertices taken */
int *			start,		/* IN - start of chosen vertices */
int *			end,		/* IN - end of chosen vertices */
struct comp *		comp,		/* IN - component to enumerate */
struct constraint *	cp,		/* IN - existing constraints */
struct bbinfo *		bbip		/* IN - branch-and-bound info */
)