| #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; | |
| } |