1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#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;
}
|
