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
127
128
129
130
131
132
133
134
135
136
137
138
139
|
/*
* Revision Control Information
*
* $Source$
* $Author$
* $Revision$
* $Date$
*
*/
#include "mincov_int.h"
ABC_NAMESPACE_IMPL_START
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;
}
ABC_NAMESPACE_IMPL_END
|
