45 idxtype *mate, *queue, *flag, *level, *lst;
46 int fptr, rptr, lstptr;
47 int row, maxlevel, col;
49 mate =
idxsmalloc(bsize, -1,
"MinCover: mate");
50 flag =
idxmalloc(bsize,
"MinCover: flag");
51 level =
idxmalloc(bsize,
"MinCover: level");
52 queue =
idxmalloc(bsize,
"MinCover: queue");
56 for (i=0; i<asize; i++) {
57 for (j=xadj[i]; j<xadj[i+1]; j++) {
58 if (mate[adjncy[j]] == -1) {
71 for (i=0; i<bsize; i++) {
78 for (i=0; i<asize; i++)
85 while (fptr != rptr) {
87 if (level[row] < maxlevel) {
89 for (j=xadj[row]; j<xadj[row+1]; j++) {
93 if (mate[col] == -1) {
94 maxlevel = level[row];
99 printf(
"\nSomething wrong, flag[%d] is 1",mate[col]);
100 queue[rptr++] = mate[col];
101 level[mate[col]] = level[row] + 1;
112 for (i=0; i<lstptr; i++)
133 for (i=xadj[col]; i<xadj[col+1]; i++) {
136 if (flag[row] == 1) {
137 if (level[row] == maxlevel) {
140 status =
MinCover_Augment(xadj, adjncy, mate[row], mate, flag, level, maxlevel-1);
169 where =
idxmalloc(bsize,
"MinCover_Decompose: where");
173 for (i=0; i<asize; i++)
178 for (i=0; i<asize; i++)
185 for (i=0; i<bsize; i++)
189 if (abs(card[
VC]+card[
SC]-card[
HR]) < abs(card[
VC]-card[
SR]-card[HR])) {
191 for (i=0; i<bsize; i++)
192 if (where[i] ==
VC || where[i] ==
SC || where[i] == HR)
197 for (i=0; i<bsize; i++)
198 if (where[i] ==
VC || where[i] ==
SR || where[i] == HR)
217 if (where[root] ==
HC)
220 for (i=xadj[root]; i<xadj[root+1]; i++)
224 if (where[root] ==
HR)
227 if (mate[root] != -1)
242 if (where[root] ==
VR)
245 for (i=xadj[root]; i<xadj[root+1]; i++)
249 if (where[root] ==
VC)
252 if (mate[root] != -1)
#define MinCover_Decompose
void GKfree(void **ptr1,...)