| #include "mincov_int.h" |
| |
| static sm_matrix *build_intersection_matrix(); |
| |
| |
| #if 0 |
| /* |
| * verify that all rows in 'indep' are actually independent ! |
| */ |
| static int |
| verify_indep_set(A, indep) |
| sm_matrix *A; |
| sm_row *indep; |
| { |
| register sm_row *prow, *prow1; |
| register sm_element *p, *p1; |
| |
| for(p = indep->first_col; p != 0; p = p->next_col) { |
| prow = sm_get_row(A, p->col_num); |
| for(p1 = p->next_col; p1 != 0; p1 = p1->next_col) { |
| prow1 = sm_get_row(A, p1->col_num); |
| if (sm_row_intersects(prow, prow1)) { |
| return 0; |
| } |
| } |
| } |
| return 1; |
| } |
| #endif |
| |
| solution_t * |
| sm_maximal_independent_set(A, weight) |
| sm_matrix *A; |
| int *weight; |
| { |
| register sm_row *best_row, *prow; |
| register sm_element *p; |
| int least_weight; |
| sm_row *save; |
| sm_matrix *B; |
| solution_t *indep; |
| |
| indep = solution_alloc(); |
| B = build_intersection_matrix(A); |
| |
| while (B->nrows > 0) { |
| /* Find the row which is disjoint from a maximum number of rows */ |
| best_row = B->first_row; |
| for(prow = B->first_row->next_row; prow != 0; prow = prow->next_row) { |
| if (prow->length < best_row->length) { |
| best_row = prow; |
| } |
| } |
| |
| /* Find which element in this row has least weight */ |
| if (weight == NIL(int)) { |
| least_weight = 1; |
| } else { |
| prow = sm_get_row(A, best_row->row_num); |
| least_weight = weight[prow->first_col->col_num]; |
| for(p = prow->first_col->next_col; p != 0; p = p->next_col) { |
| if (weight[p->col_num] < least_weight) { |
| least_weight = weight[p->col_num]; |
| } |
| } |
| } |
| indep->cost += least_weight; |
| (void) sm_row_insert(indep->row, best_row->row_num); |
| |
| /* Discard the rows which intersect this row */ |
| save = sm_row_dup(best_row); |
| for(p = save->first_col; p != 0; p = p->next_col) { |
| sm_delrow(B, p->col_num); |
| sm_delcol(B, p->col_num); |
| } |
| sm_row_free(save); |
| } |
| |
| sm_free(B); |
| |
| /* |
| if (! verify_indep_set(A, indep->row)) { |
| fail("sm_maximal_independent_set: row set is not independent"); |
| } |
| */ |
| return indep; |
| } |
| |
| static sm_matrix * |
| build_intersection_matrix(A) |
| sm_matrix *A; |
| { |
| register sm_row *prow, *prow1; |
| register sm_element *p, *p1; |
| register sm_col *pcol; |
| sm_matrix *B; |
| |
| /* Build row-intersection matrix */ |
| B = sm_alloc(); |
| for(prow = A->first_row; prow != 0; prow = prow->next_row) { |
| |
| /* Clear flags on all rows we can reach from row 'prow' */ |
| for(p = prow->first_col; p != 0; p = p->next_col) { |
| pcol = sm_get_col(A, p->col_num); |
| for(p1 = pcol->first_row; p1 != 0; p1 = p1->next_row) { |
| prow1 = sm_get_row(A, p1->row_num); |
| prow1->flag = 0; |
| } |
| } |
| |
| /* Now record which rows can be reached */ |
| for(p = prow->first_col; p != 0; p = p->next_col) { |
| pcol = sm_get_col(A, p->col_num); |
| for(p1 = pcol->first_row; p1 != 0; p1 = p1->next_row) { |
| prow1 = sm_get_row(A, p1->row_num); |
| if (! prow1->flag) { |
| prow1->flag = 1; |
| (void) sm_insert(B, prow->row_num, prow1->row_num); |
| } |
| } |
| } |
| } |
| |
| return B; |
| } |