sec_comp.c

生成直角Steiner树的程序包

	if (comp EQ NULL) {
		fatal ("simplify_one_component: Bug 1.");
	}

	/* Disconnect this component from any others after it... */
	rest = comp -> next;

	p = comp;		/* one-and-only pending node... */
	p -> next  = NULL;
	done	   = NULL;	/* nothing completed yet... */
	done_hookp = &done;

	while (p NE NULL) {
		/* Process next pending component... */

		/* Create vertex and edge masks if necessary... */
		create_masks (p);

		if ((p -> flags & CFLG_CONG) EQ 0) {
			/* Reduce down to congested minimum by removing	*/
			/* all uncongested vertices...			*/
			strip_uncongested_vertices (p);
		}
		else if ((p -> flags & CFLG_CC) EQ 0) {
			/* Break off connected components... */
			split_connected_components (p);
		}
		else if ((p -> flags & CFLG_BCC) EQ 0) {
			/* Break off biconnected components... */
			 p = split_biconnected_components (p);
		}
		else if ((p -> flags & CFLG_CHAIN) EQ 0) {
			/* Shrink down long chains of		*/
			/* two-vertex edges of weight 1.	*/
			merge_chains (p);
		}
		else {
			/* Component is now fully simplified.	*/
			/* Reduce/renumber it...		*/
			reduce_component_in_place (p);
			if (vacuous_component (p)) {
				/* Component disolved into nothing! */
				temp = p -> next;
				free_congested_component (p);
				p = temp;
			}
			else {
				/* Component is DONE.  Move it off	*/
				/* to the "done" list...		*/
				*done_hookp = p;
				done_hookp = &(p -> next);
				p = p -> next;
				*done_hookp = NULL;
			}
		}
	}

	/* Concatenate the completed nodes onto the rest we started with. */
	*done_hookp = rest;

	return (done);
}

/*
 * This routine iteratively strips away all vertices t with delta(t) <= 1
 * until we are left with a "core" of congested vertices.
 */

	static
	void
strip_uncongested_vertices (

struct comp *		comp		/* IN - component to strip */
)
{
int			i;
int			j;
int			k;
int			e;
int			t;
int			nedges;
int			nverts;
int *			ep1;
int *			ep2;
int *			vp1;
int *			vp2;
double			sum;
int *			vleft;
int *			sp;
bitmap_t *		verts_stacked;
int *			stack;
double *		B;
bool			changed;

	changed = FALSE;

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

	k = BMAP_ELTS (nverts);
	verts_stacked = NEWA (k, bitmap_t);

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

	/* Compute a count of valid vertices for each edge. */
	vleft = NEWA (nedges, int);
	for (i = 0; i < nedges; i++) {
		vleft [i] = 0;
		if (NOT BITON (comp -> edge_mask, i)) continue;

		if (comp -> x [i] <= FUZZ) {
			/* Edge not really present... */
			CLRBIT (comp -> edge_mask, i);
			changed = TRUE;
			continue;
		}
		vp1 = comp -> everts [i];
		vp2 = comp -> everts [i + 1];
		k = 0;
		while (vp1 < vp2) {
			j = *vp1++;
			if (BITON (comp -> vert_mask, j)) {
				++k;
			}
		}
		if (k < 2) {
			/* Edge not really there any more... */
			CLRBIT (comp -> edge_mask, i);
			changed = TRUE;
			continue;
		}
		vleft [i] = k;
	}

	/* Compute the congestion level Bi of each vertex i. */
	B = NEWA (nverts, double);
	for (i = 0; i < nverts; i++) {
		/* Start with any weight inherent in the vertex itself... */
		sum = comp -> tviol [i];
		if (BITON (comp -> vert_mask, i)) {
			ep1 = comp -> vedges [i];
			ep2 = comp -> vedges [i + 1];
			while (ep1 < ep2) {
				e = *ep1++;
				/* Include weight only from edges with	*/
				/* at least one other valid vertex...	*/
				if (vleft [e] < 2) continue;
				sum += comp -> x [e];
			}
		}
		B [i] = sum;
	}

	/* Add every vertex with weight <= 1 to a list of vertices	*/
	/* to be deleted...						*/
	stack = NEWA (nverts, int);
	sp = &stack [0];
	for (i = 0; i < nverts; i++) {
		if (NOT BITON (comp -> vert_mask, i)) {
			/* Pretend this vertex has already been		*/
			/* stacked and deleted (already has weight 0).	*/
			SETBIT (verts_stacked, i);
		}
		else if (B [i] <= (1.0 + FUZZ)) {
			/* Schedule this vertex for deletion! */
			*sp++ = i;
			SETBIT (verts_stacked, i);
		}
	}

	/* Iteratively pop and delete vertices until stack is empty.	*/
	while (sp > stack) {
		t = *--sp;

		/* Prune vertex "t" from the remaining structure... */
		CLRBIT (comp -> vert_mask, t);
		B [t] = 0.0;
		changed = TRUE;

		/* Drop one vertex from every remaining edge that	*/
		/* contains vertex "t"...				*/
		ep1 = comp -> vedges [t];
		ep2 = comp -> vedges [t + 1];
		while (ep1 < ep2) {
			e = *ep1++;
			if (vleft [e] < 2) continue;
			--(vleft [e]);
			if (vleft [e] >= 2) continue;
			/* This edge now has fewer than 2 valid		*/
			/* vertices left.  The edge must now go	away --	*/
			/* but first we must find its last valid	*/
			/* vertex and subtract our weight from it...	*/
			CLRBIT (comp -> edge_mask, e);
			vp1 = comp -> everts [e];
			vp2 = comp -> everts [e + 1];
			for (;;) {
				if (vp1 >= vp2) {
					fatal ("strip_uncongested_vertices: Bug 1.");
				}
				j = *vp1++;
				if (BITON (comp -> vert_mask, j)) break;
			}
			B [j] -= comp -> x [e];

			if ((B [j] <= 1.0 + FUZZ) AND
			    (NOT BITON (verts_stacked, j))) {
				/* Schedule this vertex for deletion... */
				*sp++ = j;
				SETBIT (verts_stacked, j);
			}
		}
	}

	free ((char *) stack);
	free ((char *) B);
	free ((char *) vleft);
	free ((char *) verts_stacked);

	/* This component now contains only congested vertices... */
	comp -> flags |= CFLG_CONG;

#if 1
	if (changed) {
		/* Need to look for CC/BCC's again... */
		comp -> flags &= ~(CFLG_CC | CFLG_BCC);
	}
#endif
}

/*
 * This routine determines the number of connected components within the
 * given component.  If there is only one, it is marked as connected.
 * Otherwise, one connected component is split off from this one.
 */

	static
	void
split_connected_components (

struct comp *		comp		/* IN - component to split */
)
{
int			i;
int			k;
int			t;
int			e;
int			nverts;
int			nedges;
int			num_vert_masks;
int			num_edge_masks;
int *			sp;
int *			ep1;
int *			ep2;
int *			vp1;
int *			vp2;
bitmap_t *		cc_edge_mask;
struct comp *		p2;
bitmap_t *		cc_vert_mask;
int *			stack;

	/* Get the masks, just in case... */
	create_masks (comp);

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

	num_vert_masks	= BMAP_ELTS (nverts);
	num_edge_masks	= BMAP_ELTS (nedges);

	/* Make masks of vertices and edges in the connected	*/
	/* component...						*/
	cc_vert_mask = NEWA (num_vert_masks, bitmap_t);
	for (i = 0; i < num_vert_masks; i++) {
		cc_vert_mask [i] = 0;
	}
	cc_edge_mask = NEWA (num_edge_masks, bitmap_t);
	for (i = 0; i < num_edge_masks; i++) {
		cc_edge_mask [i] = 0;
	}

	/* Find a vertex to include in the connected component... */
	for (i = 0; ; i++) {
		if (i >= nverts) {
			/* This component has no vertices!  There is	*/
			/* definitely NOT more than one connected	*/
			/* component!  Reduce this guy, mark him as a	*/
			/* connected component, and get out.		*/
			reduce_component_in_place (comp);
			comp -> flags |= CFLG_CC;
			free ((char *) cc_edge_mask);
			free ((char *) cc_vert_mask);
			return;
		}
		if (BITON (comp -> vert_mask, i)) break;
	}

	/* This is the first vertex in the component.  Stack	*/
	/* initially contains this one vertex...		*/
	SETBIT (cc_vert_mask, i);

	stack = NEWA (nverts, int);
	sp = &stack [0];
	*sp++ = i;

	/* Scan all vertices reachable from this one via valid edges. */
	while (sp > &stack [0]) {
		t = *--sp;
		ep1 = comp -> vedges [t];
		ep2 = comp -> vedges [t + 1];
		while (ep1 < ep2) {
			e = *ep1++;
			if (NOT BITON (comp -> edge_mask, e)) continue;
			if (BITON (cc_edge_mask, e)) continue;
			SETBIT (cc_edge_mask, e);
			vp1 = comp -> everts [e];
			vp2 = comp -> everts [e + 1];
			while (vp1 < vp2) {
				i = *vp1++;
				if (NOT BITON (comp -> vert_mask, i)) continue;
				if (BITON (cc_vert_mask, i)) continue;
				SETBIT (cc_vert_mask, i);
				*sp++ = i;
			}
		}
	}

	/* The cc_vert_mask and cc_edge_mask now define a connected	*/
	/* component.  See if this is the entire component...		*/
	for (i = 0; ; i++) {
		if (i >= num_vert_masks) {
			/* This component is fully connected as-is. */
			comp -> flags |= CFLG_CC;
			free ((char *) stack);
			free ((char *) cc_edge_mask);
			free ((char *) cc_vert_mask);
			return;
		}
		if (cc_vert_mask [i] NE comp -> vert_mask [i]) break;
	}

	/* We have identified one of at least TWO connected components.	*/
	/* Copy off the one we identified, and remove it from the	*/
	/* current one...						*/
	p2 = copy_subcomponent (comp, cc_vert_mask, cc_edge_mask);
	p2 -> flags |= CFLG_CC;

	/* Insert new component right after this one... */
	p2 -> next = comp -> next;
	comp -> next = p2;

	/* Remove split-off vertices and edges from this component. */
	for (i = 0; i < num_vert_masks; i++) {
		comp -> vert_mask [i] &= ~cc_vert_mask [i];
	}
	for (i = 0; i < num_edge_masks; i++) {
		comp -> edge_mask [i] &= ~cc_edge_mask [i];
	}

	free ((char *) stack);
	free ((char *) cc_edge_mask);
	free ((char *) cc_vert_mask);
}

/*
 * This routine splits the given component into its bi-connected-components,
 * assuming that each hyperedge of n vertices is replaced with the complete
 * graph Kn.  It is essentially the standard algorithm for BCC, but modified
 * to work on a hypergraph -- hyperedges of degree 3 or more are assumed to
 * be inherently bi-connected.
 */

	static
	struct comp *
split_biconnected_components (

struct comp *		comp		/* IN - component to split up */
)
{
int			i;
int			nverts;
int			nedges;
int			max_stack;
struct comp *		p;
struct bc		bc;

	/* First reduce the component.  This takes care of two issues	*/
	/* at the same time: we won't have to worry about vertex or	*/
	/* edge masks, and we can allocate smaller stacks when there	*/
	/* are no extraneous things lying around.			*/

	reduce_component_in_place (comp);

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

	if ((nverts <= 2) OR (nedges <= 1)) {
		/* Component is already bi-connected. */
		comp -> flags |= CFLG_BCC;
		return (comp);
	}

#if 0
	tracef (" %% split_biconnected_components: nverts=%d, nedges=%d\n",
		nverts, nedges);
#endif

	/* We will consume (and dispose of) this component, and		*/
	/* produce a sequence of other sub-components that we prepend	*/
	/* onto the front of the list in place of this one.		*/
	bc.list		= comp -> next;
	bc.comp		= comp;
	comp -> next = NULL;

	bc.dfs		= NEWA (nverts, int);
	bc.low		= NEWA (nverts, int);
	bc.parent	= NEWA (nverts, int);

	for (i = 0; i < nverts; i++) {
		bc.dfs  [i] = 0;
		bc.low [i] = 0;
		bc.parent [i] = -1;
	}

	bc.max_stack	= nedges;
	bc.stack	= NEWA (bc.max_stack, int);
	bc.sp		= bc.stack;
	bc.counter	= 0;

	bc.nvmasks	= BMAP_ELTS (nverts);
	bc.nemasks	= BMAP_ELTS (nedges);

	bc.vert_mask	= NEWA (bc.nvmasks, bitmap_t);
	bc.edge_mask	= NEWA (bc.nemasks, bitmap_t);
	bc.edges_seen	= NEWA (bc.nemasks, bitmap_t);
	bc.ncomps	= 0;

	for (i = 0; i < bc.nemasks; i++) {
		bc.edges_seen [i] = 0;
	}

	/* Traverse component starting with vertex 0, splitting off	*/
	/* the bi-connected components as we go...			*/
	bcc (&bc, 0);

	if (bc.ncomps > 1) {
		/* Since we broke stuff apart, it is possible that	*/
		/* some vertices that were previously congested have	*/
		/* now lost this property...  Clear the flag on each	*/
		/* generated BCC so that the congested test gets re-run	*/
		/* on them...						*/
		p = bc.list;
		for (i = 0; i < bc.ncomps; i++) {
			p -> flags &= ~CFLG_CONG;
			p = p -> next;
		}
	}

	free ((char *) bc.edges_seen);
	free ((char *) bc.edge_mask);
	free ((char *) bc.vert_mask);
	free ((char *) bc.stack);
	free ((char *) bc.parent);
	free ((char *) bc.low);
	free ((char *) bc.dfs);

	free_congested_component (comp);

	return (bc.list);
}

/*
 * This is the recursive part of the bi-connected-components algorithm.  It
 * is the standard method, with a few tweaks to work on hypergraphs instead.
 */

	static
	void
bcc (

struct bc *		bcp,		/* IN - global BCC data */
int			v		/* IN - current DFS vertex */
)
{
int			i;
int			e;
int			e2;
int			w;
int *			ep1;
int *			ep2;
int *			vp1;
int *			vp2;
int *			vp3;
int *			vp4;
int *			sp;
int *			stack;
int *			stack_endp;
struct comp *		comp;
struct comp *		newp;

	comp = bcp -> comp;

	if ((v < 0) OR (v >= comp -> num_verts)) {
		fatal ("bcc:  Bug 1.");
	}

	++(bcp -> counter);
	bcp -> dfs [v] = bcp -> counter;
	bcp -> low [v] = bcp -> counter;
	ep1 = comp -> vedges [v];
	ep2 = comp -> vedges [v + 1];
	while (ep1 < ep2) {
		e = *ep1++;
		if ((e < 0) OR (e >= comp -> num_edges)) {
			fatal ("bcc: Bug 2.");
		}
		if (NOT BITON (bcp -> edges_seen, e)) {
			/* We haven't seen this edge before.  Push	*/
			/* it onto the stack...				*/
			stack_endp = &(bcp -> stack [bcp -> max_stack]);
			if ((bcp -> sp < bcp -> stack) OR
			    (bcp -> sp >= stack_endp)) {
				fatal ("bcc: Bug 3.");
			}
			*(bcp -> sp)++ = e;
			SETBIT (bcp -> edges_seen, e);
		}
		/* Scan the vertices and process them... */
		vp1 = comp -> everts [e];
		vp2 = comp -> everts [e + 1];
		while (vp1 < vp2) {
			w = *vp1++;
			if ((w < 0) OR (w >= comp -> num_verts)) {
				fatal ("bcc: Bug 4.");
			}
			if (bcp -> dfs [w] EQ 0) {
				bcp -> parent [w] = v;
				bcc (bcp, w);
				if (bcp -> low [w] >= bcp -> dfs [v]) {
					/* We have a new BCC! */
					for (i = 0; i < bcp -> nvmasks; i++) {
						bcp -> vert_mask [i] = 0;
					}
					for (i = 0; i < bcp -> nemasks; i++) {
						bcp -> edge_mask [i] = 0;
					}
#if 0
					tracef (" %% bcc: popping edges");
#endif
					stack	= bcp -> stack;
					sp	= bcp -> sp;
					do {
						if (sp <= stack) {
							fatal ("bcc: Bug 5.");
						}