pair.c

主要进行大规模的电路综合

		cube.num_binary_vars = xnum_binary_vars;
		cube.num_vars = xnum_vars;
		cube.part_size = xpart_size;
		cube_setup();

		/* restore the original cover(s) -- free the new ones */
		sf_free(PLA->F);
		sf_free(PLA->D);
		sf_free(PLA->R);
		PLA->F = Fsave;
		PLA->D = Dsave;
		PLA->R = Rsave;
	    }
	}
    }

    pair_free(PLA->pair);
    PLA->pair = NULL;
    return cost_array;
}

static int best_cost;
static int **cost_array;
static ppair best_pair;
static pset best_phase;
static pPLA global_PLA;
static pcover best_F, best_D, best_R;
static int pair_minim_strategy;


print_pair(pair)
ppair pair;
{
    int i;

    (void) printf("pair is");
    for(i = 0; i < pair->cnt; i++)
	(void) printf (" (%d %d)", pair->var1[i], pair->var2[i]);
    (void) printf("\n");
}


int greedy_best_cost(cost_array_local, pair_p)
int **cost_array_local;
ppair *pair_p;
{
    int i, j, besti, bestj, maxcost, total_cost;
    pset cand;
    ppair pair;

    pair = pair_new(cube.num_binary_vars);
    cand = set_full(cube.num_binary_vars);
    total_cost = 0;

    while (set_ord(cand) >= 2) {
	maxcost = -1;
	for(i = 0; i < cube.num_binary_vars; i++) {
	    if (is_in_set(cand, i)) {
		for(j = i+1; j < cube.num_binary_vars; j++) {
		    if (is_in_set(cand, j)) {
			if (cost_array_local[i][j] > maxcost) {
			    maxcost = cost_array_local[i][j];
			    besti = i;
			    bestj = j;
			}
		    }
		}
	    }
	}
	pair->var1[pair->cnt] = besti+1;
	pair->var2[pair->cnt] = bestj+1;
	pair->cnt++;
	set_remove(cand, besti);
	set_remove(cand, bestj);
	total_cost += maxcost;
    }
    set_free(cand);
    *pair_p = pair;
    return total_cost;
}


ppair pair_best_cost(cost_array_local)
int **cost_array_local;
{
    ppair pair;
    pset candidate;

    best_cost = -1;
    best_pair = NULL;
    cost_array = cost_array_local;

    pair = pair_new(cube.num_binary_vars);
    candidate = set_full(cube.num_binary_vars);
    generate_all_pairs(pair, cube.num_binary_vars, candidate, find_best_cost);
    pair_free(pair);
    set_free(candidate);
    return best_pair;
}


int find_best_cost(pair)
register ppair pair;
{
    register int i, cost;

    cost = 0;
    for(i = 0; i < pair->cnt; i++)
	cost += cost_array[pair->var1[i]-1][pair->var2[i]-1];
    if (cost > best_cost) {
	best_cost = cost;
	best_pair = pair_save(pair, pair->cnt);
    }
    if ((debug & MINCOV) && trace) {
	(void) printf("cost is %d ", cost);
	print_pair(pair);
    }
}

/*
    pair_all: brute-force approach to try all possible pairings

    pair_strategy is:
	2) for espresso
	3) for minimize_exact
	4) for phase assignment
*/

pair_all(PLA, pair_strategy)
pPLA PLA;
int pair_strategy;
{
    ppair pair;
    pset candidate;

    global_PLA = PLA;
    pair_minim_strategy = pair_strategy;
    best_cost = PLA->F->count + 1;
    best_pair = NULL;
    best_phase = NULL;
    best_F = best_D = best_R = NULL;
    pair = pair_new(cube.num_binary_vars);
    candidate = set_fill(set_new(cube.num_binary_vars), cube.num_binary_vars);

    generate_all_pairs(pair, cube.num_binary_vars, candidate, minimize_pair);

    pair_free(pair);
    set_free(candidate);

    PLA->pair = best_pair;
    PLA->phase = best_phase;
/* not really necessary
    if (phase != NULL)
	(void) set_phase(PLA->phase);
*/
    set_pair(PLA);
    (void) printf("# ");
    print_pair(PLA->pair);

    sf_free(PLA->F);
    sf_free(PLA->D);
    sf_free(PLA->R);
    PLA->F = best_F;
    PLA->D = best_D;
    PLA->R = best_R;
}


/*
 *  minimize_pair -- called as each pair is generated
 */
int minimize_pair(pair)
ppair pair;
{
    pcover Fsave, Dsave, Rsave;
    int i, xnum_binary_vars, xnum_vars, *xpart_size;

    /* save the original covers */
    Fsave = sf_save(global_PLA->F);
    Dsave = sf_save(global_PLA->D);
    Rsave = sf_save(global_PLA->R);

    /* save the original cube structure */
    xnum_binary_vars = cube.num_binary_vars;
    xnum_vars = cube.num_vars;
    xpart_size = ALLOC(int, cube.num_vars);
    for(i = 0; i < cube.num_vars; i++)
	xpart_size[i] = cube.part_size[i];

    /* setup the paired variables */
    global_PLA->pair = pair;
    set_pair1(global_PLA, /* adjust_labels */ FALSE);

    /* call the minimizer */
    if (summary)
	print_pair(pair);
    switch(pair_minim_strategy) {
	case 2:
	    EXEC_S(phase_assignment(global_PLA,0), "OPO       ", global_PLA->F);
	    if (summary)
		(void) printf("# phase is %s\n", pc1(global_PLA->phase));
	    break;
	case 1:
	    EXEC_S(global_PLA->F = minimize_exact(global_PLA->F, global_PLA->D,
		global_PLA->R, 1), "EXACT     ", global_PLA->F);
	    break;
	case 0:
	    EXEC_S(global_PLA->F = espresso(global_PLA->F, global_PLA->D,
		global_PLA->R), "ESPRESSO  ", global_PLA->F);
	    break;
	default:
	    break;
    }

    /* see if we have a new best solution */
    if (global_PLA->F->count < best_cost) {
	best_cost = global_PLA->F->count;
	best_pair = pair_save(pair, pair->cnt);
	best_phase = global_PLA->phase!=NULL?set_save(global_PLA->phase):NULL;
	if (best_F != NULL) sf_free(best_F);
	if (best_D != NULL) sf_free(best_D);
	if (best_R != NULL) sf_free(best_R);
	best_F = sf_save(global_PLA->F);
	best_D = sf_save(global_PLA->D);
	best_R = sf_save(global_PLA->R);
    }

    /* restore the original cube structure -- free the new ones */
    setdown_cube();
    FREE(cube.part_size);
    cube.num_binary_vars = xnum_binary_vars;
    cube.num_vars = xnum_vars;
    cube.part_size = xpart_size;
    cube_setup();

    /* restore the original cover(s) -- free the new ones */
    sf_free(global_PLA->F);
    sf_free(global_PLA->D);
    sf_free(global_PLA->R);
    global_PLA->F = Fsave;
    global_PLA->D = Dsave;
    global_PLA->R = Rsave;
    global_PLA->pair = NULL;
    global_PLA->phase = NULL;
}

generate_all_pairs(pair, n, candidate, action)
ppair pair;
int n;
pset candidate;
int (*action)();
{
    int i, j;
    pset recur_candidate;
    ppair recur_pair;

    if (set_ord(candidate) < 2) {
	(*action)(pair);
	return;
    }

    recur_pair = pair_save(pair, n);
    recur_candidate = set_save(candidate);

    /* Find first variable still in the candidate set */
    for(i = 0; i < n; i++)
	if (is_in_set(candidate, i))
	    break;

    /* Try all pairs of i with other variables */
    for(j = i+1; j < n; j++)
	if (is_in_set(candidate, j)) {
	    /* pair (i j) -- remove from candidate set for future pairings */
	    set_remove(recur_candidate, i);
	    set_remove(recur_candidate, j);

	    /* add to the pair array */
	    recur_pair->var1[recur_pair->cnt] = i+1;
	    recur_pair->var2[recur_pair->cnt] = j+1;
	    recur_pair->cnt++;

	    /* recur looking for the end ... */
	    generate_all_pairs(recur_pair, n, recur_candidate, action);

	    /* now break this pair, and restore candidate set */
	    recur_pair->cnt--;
	    set_insert(recur_candidate, i);
	    set_insert(recur_candidate, j);
	}

    /* if odd, generate all pairs which do NOT include i */
    if ((set_ord(candidate) % 2) == 1) {
	set_remove(recur_candidate, i);
	generate_all_pairs(recur_pair, n, recur_candidate, action);
    }

    pair_free(recur_pair);
    set_free(recur_candidate);
}

ppair pair_new(n)
register int n;
{
    register ppair pair1;

    pair1 = ALLOC(pair_t, 1);
    pair1->cnt = 0;
    pair1->var1 = ALLOC(int, n);
    pair1->var2 = ALLOC(int, n);
    return pair1;
}


ppair pair_save(pair, n)
register ppair pair;
register int n;
{
    register int k;
    register ppair pair1;

    pair1 = pair_new(n);
    pair1->cnt = pair->cnt;
    for(k = 0; k < pair->cnt; k++) {
	pair1->var1[k] = pair->var1[k];
	pair1->var2[k] = pair->var2[k];
    }
    return pair1;
}


int pair_free(pair)
register ppair pair;
{
    FREE(pair->var1);
    FREE(pair->var2);
    FREE(pair);
}