sec_comp.c

生成直角Steiner树的程序包

						e2 = *--sp;
#if 0
						tracef (" %d", e2);
#endif
						SETBIT (bcp -> edge_mask, e2);
						vp3 = comp -> everts [e2];
						vp4 = comp -> everts [e2 + 1];
						while (vp3 < vp4) {
							i = *vp3++;
							SETBIT (bcp -> vert_mask, i);
						}
					} while (e2 NE e);
					bcp -> sp = sp;
#if 0
					tracef ("\n");
					print_mask (" % bcc: cverts =",
						    bcp -> vert_mask,
						    comp -> num_verts);
#endif
					newp = copy_subcomponent (comp,
								  bcp -> vert_mask,
								  bcp -> edge_mask);
					newp -> flags |= CFLG_BCC;
					newp -> next = bcp -> list;
					bcp -> list = newp;
					++(bcp -> ncomps);
				}
				else if (bcp -> low [w] < bcp -> low [v]) {
					bcp -> low [v] = bcp -> low [w];
				}
			}
			else if ((w NE bcp -> parent [v]) AND
				 (bcp -> dfs [w] < bcp -> low [v])) {
				bcp -> low [v] = bcp -> dfs [w];
			}
		}
			
	}
}

/*
 * This routine looks for long chains of edges where each link Li in
 * the chain is a group of edges with the following properties:
 *
 *	- Every edge in Li has exactly two vertices A and B.
 *	- Every edge that includes A and B is in Li.
 *	- The sum of the weights of the edges in Li is 1.
 *
 * Let L0, L1, L2, ..., Lk be such a chain of maximal length.  Let Li
 * contain vertices i-1 and i for i=1..k.  Whenever k > 1 we merge
 * vertices 1, 2, ..., k-1 together -- leaving us with a shorter chain
 * containing 3 vertices and 2 links.
 */

	static
	void
merge_chains (

struct comp *		comp		/* IN - component to merge chains in */
)
{
int			i;
int			j;
int			k;
int			t1;
int			t2;
int			nverts;
int			nedges;
int			num_real_edges;
int			invalid_edge;
bool *			vmark;
int *			vcount;
int *			rvcount;
int *			elist;
int *			vlist;
int *			ep1;
int *			ep2;
int *			ep3;
int *			vp1;
int *			vp2;
int *			vp3;
int **			new_rverts;
int **			new_rptr;
int			merge_count;
bool			free_sets;
struct dsuf		sets;

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

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

	free_sets = FALSE;
	elist = NULL;
	vlist = NULL;
	vcount = NULL;
	rvcount = NULL;

	/* Mark each valid vertex having exactly 2 incident edges. */
	vmark = NEWA (nverts, bool);
	memset (vmark, FALSE, nverts * sizeof (bool));
	for (i = 0; i < nverts; i++) {
		if (NOT BITON (comp -> vert_mask, i)) continue;
		k = 0;
		ep1 = comp -> vedges [i];
		ep2 = comp -> vedges [i + 1];
		while (ep1 < ep2) {
			j = *ep1++;
			if (BITON (comp -> edge_mask, j)) {
				++k;
			}
		}
		if (k EQ 2) {
			vmark [i] = TRUE;
		}
	}

	/* Compute a list of edges that have weight 1 and cardinality 2. */
	/* At least one of the edge's two endpoints must be a vertex	 */
	/* residing in exactly 2 edges.					 */

	elist = NEWA (nedges, int);
	vlist = NEWA (2 * nedges, int);
	ep1 = elist;
	vp1 = vlist;
	num_real_edges = 0;
	for (i = 0; i < nedges; i++) {
		if (NOT BITON (comp -> edge_mask, i)) continue;
		++num_real_edges;
		if (comp -> x [i] < 1.0 - FUZZ) continue;
		vp2 = comp -> everts [i];
		vp3 = comp -> everts [i + 1];
		k = 0;
		t1 = t2 = 0;
		while (vp2 < vp3) {
			j = *vp2++;
			if (BITON (comp -> vert_mask, j)) {
				t1 = t2;
				t2 = j;
				++k;
			}
		}
		if (k NE 2) continue;

		/* Edge has cardinality 2.  Its endpoints are t1 and t2. */

		if ((NOT vmark [t1]) AND (NOT vmark [t2])) continue;

		/* At least one endpoint is incident to exactly 2 edges	  */
		/* (including this edge).  Record edge and its endpoints. */

		*ep1++ = i;
		*vp1++ = t1;
		*vp1++ = t2;
	}

	if (ep1 <= elist) {
		/* No suitable edges to contract.  Get out. */
#if 0
		tracef (" %% merge_chains: exit 1\n");
#endif
		goto all_done;
	}

	/* For each vertex, determine how many of our special edges are	*/
	/* incident.							*/
	vcount = NEWA (nverts, int);
	for (i = 0; i < nverts; i++) {
		vcount [i] = 0;
	}
	vp3 = vp1;
	vp1 = vlist;
	while (vp1 < vp3) {
		i = *vp1++;
		++(vcount [i]);
	}

	/* Now delete edges from the list that do not satisfy all of	*/
	/* the criteria for being contracted (merging their endpoints).	*/
	ep3 = ep1;
	ep1 = elist;
	ep2 = elist;
	vp1 = vlist;
	vp2 = vlist;
	while (ep2 < ep3) {
		i = *ep2++;
		t1 = *vp2++;
		t2 = *vp2++;
		if (NOT vmark [t1]) continue;
		if (NOT vmark [t2]) continue;
		if (vcount [t1] NE 2) continue;
		if (vcount [t2] NE 2) continue;

		*ep1++ = i;
		*vp1++ = t1;
		*vp1++ = t2;
	}

	if (ep1 <= elist) {
		/* No edges contracted.  Get out. */
#if 0
		tracef (" %% merge_chains: exit 2\n");
#endif
		goto all_done;
	}

	i = ep1 - elist;
	if (i >= num_real_edges) {
		/* Entire component is a cycle of 2-edges of weight 1! */
		if (i <= 3) {
#if 0
			tracef (" %% merge_chains: exit 3\n");
#endif
			goto all_done;
		}
		/* Remove any three edges list of edges to contract.	*/
		/* This will cause us to reduce the N-cycle down to a	*/
		/* 3-cycle.						*/
		ep1 -= 3;
		vp1 -= 6;
	}

	/* Remember an edge that will disappear... */
	invalid_edge = elist [0];

	/* Initialize a collection of disjoint sets, one per vertex. */
	dsuf_create (&sets, nverts);
	free_sets = TRUE;
	for (i = 0; i < nverts; i++) {
		dsuf_makeset (&sets, i);
	}

	merge_count = 0;
	ep3 = ep1;
	vp3 = vp1;
	ep1 = elist;
	vp1 = vlist;
	while (ep1 < ep3) {
		i = *ep1++;
		t1 = *vp1++;
		t2 = *vp1++;
		j = dsuf_find (&sets, t1);
		k = dsuf_find (&sets, t2);
		if (j EQ k) {
			fatal ("merge_chains: Bug 1.");
		}
		/* Contract edge i, merging vertices t1 and t2. */
		dsuf_unite (&sets, j, k);
		CLRBIT (comp -> edge_mask, i);
		++merge_count;
	}

	if (merge_count <= 0) {
		/* No edges contracted.  Get out. */
#if 0
		tracef (" %% merge_chains: exit 4\n");
#endif
		goto all_done;
	}

	/* Count the number of "real" vertices for each component vertex. */
	rvcount = NEWA (nverts, int);
	k = 0;
	for (i = 0; i < nverts; i++) {
		j = 0;
		if (BITON (comp -> vert_mask, i)) {
			j = comp -> rverts [i + 1] - comp -> rverts [i];
		}
		rvcount [i] = j;
		k += j;
	}

	/* Update "real vertex" counts to consider effects of merging... */
	for (i = 0; i < nverts; i++) {
		j = dsuf_find (&sets, i);
		if (i NE j) {
			/* Vertex i will be donating to vertex j... */
			rvcount [j] += rvcount [i];
			rvcount [i] = 0;
		}
	}

	/* Create a new "real vertex" list to fill in. */
	new_rverts = NEWA (nverts + 1, int *);
	new_rptr   = NEWA (nverts, int *);
	vp1	   = NEWA (k, int);
	for (i = 0; i < nverts; i++) {
		new_rverts [i]	= vp1;
		new_rptr [i]	= vp1;
		vp1 += rvcount [i];
	}
	new_rverts [i] = vp1;

	/* Retain only the canonical member of each set of vertices. */
	for (i = 0; i < nverts; i++) {
		vcount [i] = 0;
		vmark [i] = FALSE;
	}
	for (i = 0; i < nverts; i++) {
		j = dsuf_find (&sets, i);
		if (i NE j) {
			/* Vertex j remains, vertex i disappears... */
			vmark [j] = TRUE;
			CLRBIT (comp -> vert_mask, i);
		}
		/* Copy i's "real" vertices into j's new bucket. */
		vp1 = comp -> rverts [i];
		vp2 = comp -> rverts [i + 1];
		vp3 = new_rptr [j];
		while (vp1 < vp2) {
			*vp3++ = *vp1++;
		}
		new_rptr [j] = vp3;
	}

	/* Get rid of old "real" vertices, keep the new... */
	free ((char *) (comp -> rverts [0]));
	free ((char *) (comp -> rverts));
	comp -> rverts = new_rverts;
	free ((char *) new_rptr);

	/* Fill edge list for each canonical vertex with edges that	*/
	/* disappeared...						*/
	for (i = 0; i < nverts; i++) {
		if (NOT vmark [i]) continue;
		ep1 = comp -> vedges [i];
		ep2 = comp -> vedges [i + 1];
		while (ep1 < ep2) {
			*ep1++ = invalid_edge;
		}
	}
	/* Renumber the vertices in each edge. */
	for (i = 0; i < nedges; i++) {
		if (NOT BITON (comp -> edge_mask, i)) continue;
		vp1 = comp -> everts [i];
		vp2 = comp -> everts [i + 1];
		while (vp1 < vp2) {
			j = *vp1;
			k = dsuf_find (&sets, j);
			*vp1 = k;
			if (vmark [k]) {
				/* Update vertex to edge mapping. */
				j = vcount [k]++;
				comp -> vedges [k] [j] = i;
			}
			++vp1;
		}
	}

#if 0
	tracef (" %% merge_chains: reduced from %d vertices to %d\n",
		comp -> num_verts + merge_count, comp -> num_verts);
#endif

all_done:
	if (rvcount NE NULL) {
		free ((char *) rvcount);
	}
	if (free_sets) {
		dsuf_destroy (&sets);
	}
	if (vcount NE NULL) {
		free ((char *) vcount);
	}
	if (vlist NE NULL) {
		free ((char *) vlist);
	}
	if (elist NE NULL) {
		free ((char *) elist);
	}
	free ((char *) vmark);

	comp -> flags |= CFLG_CHAIN;
}

/*
 * This routine copies off a specified SUBSET of the given component
 * into a new, freshly created component that is returned.
 */

	static
	struct comp *
copy_subcomponent (

struct comp *		comp,		/* IN - component to copy from */
bitmap_t *		vert_mask,	/* IN - vertices to copy */
bitmap_t *		edge_mask	/* IN - hyperedges to copy */
)
{
int			i;
int			j;
int			k;
int			nverts;
int			nedges;
int			src;
int			dst;
int			new_num_verts;
int			new_num_edges;
int			rvcount;
struct comp *		newp;
int *			ip1;
int *			ip2;
int *			ip3;
int *			ip4;
int *			vert_renum;
int *			edge_renum;
int *			vlist;
int *			elist;
int *			rvlist;
bitmap_t *		bp1;
bitmap_t *		bp2;
bitmap_t *		bp3;

	/* Force masks to be present... */
	create_masks (comp);

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

	/* 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 (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 (edge_mask, i)) {
			edge_renum [i] = j++;
		}
		else {
			edge_renum [i] = -1;
		}
	}
	new_num_edges = j;

	/* Compute size of new edge-to-vertices list... */
	k = 0;
	for (i = 0; i < nedges; i++) {
		if (NOT BITON (edge_mask, i)) continue;
		ip1 = comp -> everts [i];
		ip2 = comp -> everts [i + 1];
		while (ip1 < ip2) {
			j = *ip1++;
			if (NOT BITON (vert_mask, j)) continue;
			++k;
		}
	}

	/* Compute size of new "real vertices" list... */
	rvcount = 0;
	for (i = 0; i < nverts; i++) {
		if (BITON (vert_mask, i)) {
			ip1 = comp -> rverts [i];
			ip2 = comp -> rverts [i + 1];
			rvcount += (ip2 - ip1);
		}
	}

	/* Create the new component... */
	newp = NEW (struct comp);

	vlist  = NEWA (k, int);
	elist = NEWA (k, int);
	rvlist = NEWA (rvcount, int);

	newp -> next		= NULL;
	newp -> num_verts	= new_num_verts;
	newp -> num_edges	= new_num_edges;
	newp -> flags		= comp -> flags;
	newp -> x		= NEWA (new_num_edges, double);
	newp -> everts		= NEWA (new_num_edges + 1, int *);
	newp -> vedges		= NEWA (new_num_verts + 1, int *);
	newp -> tviol		= NEWA (new_num_verts, double);
	newp -> rverts		= NEWA (new_num_verts + 1, int *);
	newp -> vert_mask	= NULL;
	newp -> edge_mask	= NULL;
	newp -> cp		= NULL;

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

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

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

	return (newp);
}

/*
 * This routine reduces the given component in-place by re-numbering
 * all of the verticess and edges so that the ones that are not
 * marked in the vertex and edge masks are gone.
 *
 * This functions as a kind of garbage-compaction effect, but we do
 * NOT actually re-allocate ourselves into smaller memory...