sec_comp.c

生成直角Steiner树的程序包

 */

	static
	void
reduce_component_in_place (

struct comp *		comp		/* IN - component to reduce */
)
{
int			i;
int			j;
int			nverts;
int			nedges;
int			src;
int			dst;
int			new_num_verts;
int			new_num_edges;
int *			ip1;
int *			ip2;
int *			ip3;
int *			ip4;
int *			vert_renum;
int *			edge_renum;

	if ((comp -> vert_mask EQ NULL) AND (comp -> edge_mask EQ NULL)) {
		/* Already reduced... */
		return;
	}

	create_masks (comp);	/* in case one exists, but not the other... */

	nverts = comp -> num_verts;
	nedges = comp -> num_edges;

	if ((nverts <= 0) OR (nedges <= 0)) {
		comp -> num_verts = 0;
		comp -> num_edges = 0;
		free ((char *) (comp -> vert_mask));
		free ((char *) (comp -> edge_mask));
		comp -> vert_mask = NULL;
		comp -> edge_mask = NULL;
		return;
	}

	/* Get arrays used to renumber the vertices and edges... */
	vert_renum	= NEWA (nverts, int);
	edge_renum	= NEWA (nedges, int);

	/* Compute renumberings... */
	j = 0;
	for (i = 0; i < nverts; i++) {
		if (BITON (comp -> vert_mask, i)) {
			vert_renum [i] = j++;
		}
		else {
			vert_renum [i] = -1;
		}
	}
	new_num_verts = j;

	j = 0;
	for (i = 0; i < nedges; i++) {
		if (BITON (comp -> edge_mask, i)) {
			edge_renum [i] = j++;
		}
		else {
			edge_renum [i] = -1;
		}
	}
	new_num_edges = j;

	/* Remap/delete entries in the edge-to-vertices mapping... */
	dst = 0;
	ip1 = comp -> everts [0];
	for (src = 0; src < nedges; src++) {
		if (edge_renum [src] < 0) continue;
		ip2 = comp -> everts [src];
		ip3 = comp -> everts [src + 1];
		comp -> everts [dst] = ip1;
		while (ip2 < ip3) {
			j = *ip2++;
			j = vert_renum [j];
			if (j >= 0) {
				*ip1++ = j;
			}
		}
		comp -> x [dst] = comp -> x [src];
		++dst;
	}
	comp -> everts [dst] = ip1;
	if (dst NE new_num_edges) {
		fatal ("reduce_component_in_place: Bug 1.");
	}
	comp -> num_edges = new_num_edges;

	/* Remap/delete entries in the vertex-to-hyperedges mapping... */
	dst = 0;
	ip1 = comp -> vedges [0];
	ip4 = comp -> rverts [0];
	for (src = 0; src < nverts; src++) {
		if (vert_renum [src] < 0) continue;
		ip2 = comp -> vedges [src];
		ip3 = comp -> vedges [src + 1];
		comp -> vedges [dst] = ip1;
		while (ip2 < ip3) {
			j = *ip2++;
			j = edge_renum [j];
			if (j >= 0) {
				*ip1++ = j;
			}
		}
		comp -> tviol [dst] = comp -> tviol [src];
		ip2 = comp -> rverts [src];
		ip3 = comp -> rverts [src + 1];
		comp -> rverts [dst] = ip4;
		while (ip2 < ip3) {
			*ip4++ = *ip2++;
		}
		++dst;
	}
	comp -> rverts [dst] = ip4;
	comp -> vedges [dst] = ip1;
	if (dst NE new_num_verts) {
		fatal ("reduce_component_in_place: Bug 2.");
	}

	/* Component is now a different size... */
	comp -> num_verts	= new_num_verts;
	comp -> num_edges	= new_num_edges;

	free ((char *) edge_renum);
	free ((char *) vert_renum);

	/* Free the valid vertices and edges masks... */
	free ((char *) (comp -> edge_mask));
	free ((char *) (comp -> vert_mask));
	comp -> vert_mask	= NULL;
	comp -> edge_mask	= NULL;
}

/*
 * This routine determines whether or not the given component is
 * "vacuous" -- too small to contain a subtour violation.
 */

	static
	int
vacuous_component (

struct comp *		p		/* IN - component to test */
)
{
	if (p -> num_verts <= 0) return (TRUE);
	if (p -> num_edges <= 1) return (TRUE);
	if (p -> num_verts EQ 1) {
		/* Special check for exactly 1 vertex... */
		if (p -> tviol [0] > FUZZ) {
			/* We have a single vertex, but it is congested! */
			/* This is a valid component... */
			return (FALSE);
		}
		/* Only 1 vertex -- no congestion -- ignore this component */
		return (TRUE);
	}

	/* We have a component worth looking at for violated SEC's... */

	return (FALSE);
}

/*
 * This routine frees up the given congested component.
 */

	void
free_congested_component (

struct comp *		p	/* IN - component to free */
)
{
	if (p -> vert_mask NE NULL) {
		free ((char *) (p -> vert_mask));
	}
	if (p -> edge_mask NE NULL) {
		free ((char *) (p -> edge_mask));
	}
	free ((char *) (p -> vedges [0]));
	free ((char *) (p -> everts [0]));
	free ((char *) (p -> rverts [0]));
	free ((char *) (p -> rverts));
	free ((char *) (p -> tviol));
	free ((char *) (p -> vedges));
	free ((char *) (p -> everts));
	free ((char *) (p -> x));
	free ((char *) p);
}

/*
 * This routine deletes a specified vertex from the given congested
 * component and then does all possible further simplifications on what
 * is left.  Note that it is possible that the given component splits
 * into several when this is done...
 *
 * Also note that the given component may be MODIFIED -- even FREED!
 */

	struct comp *
delete_vertex_from_component (

int			t,		/* IN - vertex to delete */
struct comp *		comp		/* IN - component to delete from */
)
{
	if (t >= comp -> num_verts) {
		fatal ("delete_vertex_from_component: Bug 1.");
	}

	/* Create masks if not currently present... */
	create_masks (comp);

	if (t >= 0) {
		if (NOT BITON (comp -> vert_mask, t)) {
			/* Deleting a vertex that is not present. */
			fatal ("delete_vertex_from_component: Bug 2.");
		}

		/* Remove the vertex from the bit-mask... */
		CLRBIT (comp -> vert_mask, t);
	}
	else {
		/* Caller has deleted vertices.  Just clean up.	*/
	}

	/* Now that we have removed a vertex, we can no longer	*/
	/* be certain that the component is: fully congested,	*/
	/* connected, bi-connected, etc...			*/
	comp -> flags &= ~CFLG_ALL;

	comp = simplify_one_component (comp);

	return (comp);
}

/*
 * This routine adds the vertex and edge masks to the given
 * component, if they are NOT already present...
 */

	static
	void
create_masks (

struct comp *		p		/* IN - component to put masks on */
)
{
int		i;
int		n;
int		nmasks;
bitmap_t *	mask;

	if (p -> vert_mask EQ NULL) {
		/* Sprout a new vertex mask with all vertices present. */
		n = p -> num_verts;
		nmasks = BMAP_ELTS (n);
		if (nmasks < 1) {
			nmasks = 1;
		}
		mask = NEWA (nmasks, bitmap_t);
		for (i = 0; i < nmasks; i++) {
			mask [i] = 0;
		}
		for (i = 0; i < n; i++) {
			SETBIT (mask, i);
		}
		p -> vert_mask = mask;
	}

	if (p -> edge_mask EQ NULL) {
		/* Sprout a new edge mask with all edges present. */
		n = p -> num_edges;
		nmasks = BMAP_ELTS (n);
		if (nmasks < 1) {
			nmasks = 1;
		}
		mask = NEWA (nmasks, bitmap_t);
		for (i = 0; i < nmasks; i++) {
			mask [i] = 0;
		}
		for (i = 0; i < n; i++) {
			SETBIT (mask, i);
		}
		p -> edge_mask = mask;
	}
}

/*
 * This routine selects a vertex that is a member of the previous
 * solution S and has minimum weight.
 */

	int
find_least_congested_vertex (

bitmap_t *		S,	/* IN - previous separation solution */
struct comp *		comp	/* IN - congested component */
)
{
int			i;
int			j;
int			nverts;
int			nedges;
int *			ip1;
int *			ip2;
int			min_vert;
double			w;
double			min_weight;

	nverts	= comp -> num_verts;
	nedges	= comp -> num_edges;

	min_weight	= 2.0 * nedges;
	min_vert	= -1;

	for (i = 0; i < nverts; i++) {
		if ((S NE NULL) AND (NOT BITON (S, i))) continue;
		w = 0.0;
		ip1 = comp -> vedges [i];
		ip2 = comp -> vedges [i + 1];
		while (ip1 < ip2) {
			j = *ip1++;
			w += comp -> x [j];
		}
		if (w < min_weight) {
			min_weight = w;
			min_vert   = i;
		}
	}
	if (min_vert < 0) {
		/* Least congested vertex not found? */
		fatal ("find_least_congested_vertex: Bug 1.");
	}

	return (min_vert);
}

/*
 * This routine produces the proper constraints that are represented
 * by the given subset of the given component.  We try to "clean up"
 * the constraint by taking only the congested portion of the
 * vertices in it.  This can strengthen the constraints considerably.
 */

	struct constraint *
check_component_subtour (

bitmap_t *		S,		/* IN - subtour (set of vertices) */
struct comp *		comp,		/* IN - congested component */
struct constraint *	cp,		/* IN - existing constraints */
double *		x,		/* IN - LP solution vector */
bitmap_t *		edge_mask,	/* IN - set of valid hyperedges */
struct bbinfo *		bbip		/* IN - branch-and-bound info */
)
{
int			kmasks;
struct comp *		vcomps;
struct comp *		tmp;
struct constraint *	cp2;
struct cinfo *		cip;
bool			print_flag;
bitmap_t *		orig_stour;
bitmap_t *		stour;
bool			flag;

	cip = bbip -> cip;
	kmasks = cip -> num_vert_masks;

	orig_stour = NEWA (2 * kmasks, bitmap_t);
	stour	   = orig_stour + kmasks;

#if 1
	/* Construct a bitmask of the REAL vertices comprising	*/
	/* this subtour...					*/
	component_verts_to_real_verts (S, comp, orig_stour, kmasks);

#if 1
	/* Now that we have the subtour as "real" vertices,	*/
	/* emit the constraint...				*/
	cp = check_subtour (orig_stour, cp, x, edge_mask, cip);
#endif
#endif

	/* Take the violated subtour and "clean" it up by computing the	*/
	/* congested components for it.  This will get rid of some of	*/
	/* the cruft, and help to strengthen the generated constraints.	*/

#if 1
	print_flag = FALSE;
	vcomps = find_congested_components (x,
					    orig_stour,
					    edge_mask,
					    print_flag,
					    cip);
#else
	/* A more efficient alternative to starting all over! */
 {
 int		i, j, k;
 int		nmasks;
 bitmap_t *	sedges;
 int *		ip1;
 int *		ip2;

	/* Compute edges induced by the subtour vertices. */
	nmasks = BMAP_ELTS (comp -> num_edges);
	sedges = NEWA (nmasks, bitmap_t);
	for (i = 0; i < nmasks; i++) {
		sedges [i] = 0;
	}
	for (i = 0; i < comp -> num_edges; i++) {
		ip1 = comp -> everts [i];
		ip2 = comp -> everts [i + 1];
		k = 0;
		while (ip1 < ip2) {
			j = *ip1++;
			if (BITON (S, j)) {
				++k;
				if (k >= 2) {
					SETBIT (sedges, i);
					break;
				}
			}
		}
	}
	vcomps = copy_subcomponent (comp, S, sedges);
	vcomps = simplify_one_component (vcomps);
 }
#endif

	flag = FALSE;

#if 0
	{ int i = 0;
		for (tmp = vcomps; tmp NE NULL; tmp = tmp -> next) {
			++i;
		}
		if (i >= 3) {
			plot_lp_solution ("Full LP Solution",
					  x, cip, BIG_PLOT);
			plot_subtour ("Separated Subtour",
				      x, cip, orig_stour, BIG_PLOT);
			flag = TRUE;
		}
	}
#endif

#if 1
	for (tmp = vcomps; tmp NE NULL; tmp = tmp -> next) {
		cp2 = add_component_subtour (tmp, x, edge_mask, cip, cp, stour);
		if (flag AND (cp2 NE cp)) {
			plot_subtour ("Strengthed Subtour",
				      x, cip, cp2 -> mask, BIG_PLOT);
		}
		cp = cp2;
	}
#endif

	while (vcomps NE NULL) {
		tmp = vcomps -> next;
		vcomps -> next = NULL;
		free_congested_component (vcomps);
		vcomps = tmp;
	}

	free ((char *) orig_stour);

	return (cp);
}

/*
 * Routine to add the subtour constraint designated by the given component
 * to the list of constraints.
 */

	static
	struct constraint *
add_component_subtour (

struct comp *		comp,		/* IN - component to add subtour of */
double *		x,		/* IN - LP solution vector */
bitmap_t *		edge_mask,	/* IN - set of valid hyperedges */
struct cinfo *		cip,		/* IN - compatibility info */
struct constraint *	cp,		/* IN - existing constraints */
bitmap_t *		stour		/* IN - temporary bitmap buffer */
)
{
int			kmasks;
struct constraint *	cp2;

	kmasks = cip -> num_vert_masks;

	component_verts_to_real_verts (comp -> vert_mask, comp, stour, kmasks);

	/* See if this constraint is already present... */
	for (cp2 = cp; cp2 NE NULL; cp2 = cp2 -> next) {
		if (is_equal (stour, cp2 -> mask, kmasks)) {
			/* Already there... */
			return (cp);
		}
	}

	/* Add it to the list (if it is a violation) */
	cp = check_subtour (stour, cp, x, edge_mask, cip);

	return (cp);
}

/*
 * This routine converts a vertex subset within a given component
 * back into the corresponding subset of the original vertices.
 * Specifying a NULL pointer for comp_S is a convenient way to specify
 * that the entire component is to be translated back out.
 */

	static
	void
component_verts_to_real_verts (

bitmap_t *		comp_S,	/* IN - subset of vertices in component */
struct comp *		comp,	/* IN - component those vertices are in */
bitmap_t *		real_S,	/* OUT - real set of vertices */
int			kmasks	/* IN - size of real_S */
)
{
int			i;
int			j;
int *			ip1;
int *			ip2;

	/* Zero out entire set of real vertices... */
	for (i = 0; i < kmasks; i++) {
		real_S [i] = 0;
	}

	/* Set the "real" vertex number bits for each component vertex. */
	for (i = 0; i < comp -> num_verts; i++) {
		if ((comp_S NE NULL) AND (NOT BITON (comp_S, i))) continue;
		ip1 = comp -> rverts [i];
		ip2 = comp -> rverts [i + 1];
		while (ip1 < ip2) {
			j = *ip1++;
			SETBIT (real_S, j);
		}
	}
}