diff options
| author | Florian Fischer <florian.fl.fischer@fau.de> | 2020-05-06 16:56:32 +0200 |
|---|---|---|
| committer | Florian Fischer <florian.fl.fischer@fau.de> | 2020-06-02 11:18:47 +0200 |
| commit | 8174a918ea3b7cb216bf7ea98cfdc10661b5c37d (patch) | |
| tree | 0747ec3ccb9f8d7eeccfac35977fc17855ca3bbb /src/benchmarks/espresso/indep.c | |
| parent | 8f52e8fc02dd235582f5961941bcd564e9a681cd (diff) | |
| download | allocbench-8174a918ea3b7cb216bf7ea98cfdc10661b5c37d.tar.gz allocbench-8174a918ea3b7cb216bf7ea98cfdc10661b5c37d.zip | |
make the whole project more python idiomatic
* rename src directory to allocbench
* make global variable names UPPERCASE
* format a lot of code using yapf
* use lowercase ld_preload and ld_library_path as Allocator members
* name expected Errors 'err' and don't raise a new Exception
* disable some pylint messages
Diffstat (limited to 'src/benchmarks/espresso/indep.c')
| -rw-r--r-- | src/benchmarks/espresso/indep.c | 126 |
1 files changed, 0 insertions, 126 deletions
diff --git a/src/benchmarks/espresso/indep.c b/src/benchmarks/espresso/indep.c deleted file mode 100644 index c462988..0000000 --- a/src/benchmarks/espresso/indep.c +++ /dev/null @@ -1,126 +0,0 @@ -#include "espresso.h" -#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; -} |
