1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * mincover.c
5 *
6 * This file implements the minimum cover algorithm
7 *
8 * Started 8/1/97
9 * George
10 *
11 * $Id: mincover.c 9942 2011-05-17 22:09:52Z karypis $
12 */
13
14 #include "metislib.h"
15
16 /*************************************************************************
17 * Constants used by mincover algorithm
18 **************************************************************************/
19 #define INCOL 10
20 #define INROW 20
21 #define VC 1
22 #define SC 2
23 #define HC 3
24 #define VR 4
25 #define SR 5
26 #define HR 6
27
28
29 /*************************************************************************
30 * This function returns the min-cover of a bipartite graph.
31 * The algorithm used is due to Hopcroft and Karp as modified by Duff etal
32 * adj: the adjacency list of the bipartite graph
33 * asize: the number of vertices in the first part of the bipartite graph
34 * bsize-asize: the number of vertices in the second part
35 * 0..(asize-1) > A vertices
36 * asize..bsize > B vertices
37 *
38 * Returns:
39 * cover : the actual cover (array)
40 * csize : the size of the cover
41 **************************************************************************/
MinCover(idx_t * xadj,idx_t * adjncy,idx_t asize,idx_t bsize,idx_t * cover,idx_t * csize)42 void MinCover(idx_t *xadj, idx_t *adjncy, idx_t asize, idx_t bsize, idx_t *cover, idx_t *csize)
43 {
44 idx_t i, j;
45 idx_t *mate, *queue, *flag, *level, *lst;
46 idx_t fptr, rptr, lstptr;
47 idx_t row, maxlevel, col;
48
49 mate = ismalloc(bsize, -1, "MinCover: mate");
50 flag = imalloc(bsize, "MinCover: flag");
51 level = imalloc(bsize, "MinCover: level");
52 queue = imalloc(bsize, "MinCover: queue");
53 lst = imalloc(bsize, "MinCover: lst");
54
55 /* Get a cheap matching */
56 for (i=0; i<asize; i++) {
57 for (j=xadj[i]; j<xadj[i+1]; j++) {
58 if (mate[adjncy[j]] == -1) {
59 mate[i] = adjncy[j];
60 mate[adjncy[j]] = i;
61 break;
62 }
63 }
64 }
65
66 /* Get into the main loop */
67 while (1) {
68 /* Initialization */
69 fptr = rptr = 0; /* Empty Queue */
70 lstptr = 0; /* Empty List */
71 for (i=0; i<bsize; i++) {
72 level[i] = -1;
73 flag[i] = 0;
74 }
75 maxlevel = bsize;
76
77 /* Insert free nodes into the queue */
78 for (i=0; i<asize; i++)
79 if (mate[i] == -1) {
80 queue[rptr++] = i;
81 level[i] = 0;
82 }
83
84 /* Perform the BFS */
85 while (fptr != rptr) {
86 row = queue[fptr++];
87 if (level[row] < maxlevel) {
88 flag[row] = 1;
89 for (j=xadj[row]; j<xadj[row+1]; j++) {
90 col = adjncy[j];
91 if (!flag[col]) { /* If this column has not been accessed yet */
92 flag[col] = 1;
93 if (mate[col] == -1) { /* Free column node was found */
94 maxlevel = level[row];
95 lst[lstptr++] = col;
96 }
97 else { /* This column node is matched */
98 if (flag[mate[col]])
99 printf("\nSomething wrong, flag[%"PRIDX"] is 1",mate[col]);
100 queue[rptr++] = mate[col];
101 level[mate[col]] = level[row] + 1;
102 }
103 }
104 }
105 }
106 }
107
108 if (lstptr == 0)
109 break; /* No free columns can be reached */
110
111 /* Perform restricted DFS from the free column nodes */
112 for (i=0; i<lstptr; i++)
113 MinCover_Augment(xadj, adjncy, lst[i], mate, flag, level, maxlevel);
114 }
115
116 MinCover_Decompose(xadj, adjncy, asize, bsize, mate, cover, csize);
117
118 gk_free((void **)&mate, &flag, &level, &queue, &lst, LTERM);
119
120 }
121
122
123 /*************************************************************************
124 * This function perfoms a restricted DFS and augments matchings
125 **************************************************************************/
MinCover_Augment(idx_t * xadj,idx_t * adjncy,idx_t col,idx_t * mate,idx_t * flag,idx_t * level,idx_t maxlevel)126 idx_t MinCover_Augment(idx_t *xadj, idx_t *adjncy, idx_t col, idx_t *mate, idx_t *flag, idx_t *level, idx_t maxlevel)
127 {
128 idx_t i;
129 idx_t row = -1;
130 idx_t status;
131
132 flag[col] = 2;
133 for (i=xadj[col]; i<xadj[col+1]; i++) {
134 row = adjncy[i];
135
136 if (flag[row] == 1) { /* First time through this row node */
137 if (level[row] == maxlevel) { /* (col, row) is an edge of the G^T */
138 flag[row] = 2; /* Mark this node as being visited */
139 if (maxlevel != 0)
140 status = MinCover_Augment(xadj, adjncy, mate[row], mate, flag, level, maxlevel-1);
141 else
142 status = 1;
143
144 if (status) {
145 mate[col] = row;
146 mate[row] = col;
147 return 1;
148 }
149 }
150 }
151 }
152
153 return 0;
154 }
155
156
157
158 /*************************************************************************
159 * This function performs a coarse decomposition and determines the
160 * min-cover.
161 * REF: Pothen ACMTrans. on Amth Software
162 **************************************************************************/
MinCover_Decompose(idx_t * xadj,idx_t * adjncy,idx_t asize,idx_t bsize,idx_t * mate,idx_t * cover,idx_t * csize)163 void MinCover_Decompose(idx_t *xadj, idx_t *adjncy, idx_t asize, idx_t bsize, idx_t *mate, idx_t *cover, idx_t *csize)
164 {
165 idx_t i, k;
166 idx_t *where;
167 idx_t card[10];
168
169 where = imalloc(bsize, "MinCover_Decompose: where");
170 for (i=0; i<10; i++)
171 card[i] = 0;
172
173 for (i=0; i<asize; i++)
174 where[i] = SC;
175 for (; i<bsize; i++)
176 where[i] = SR;
177
178 for (i=0; i<asize; i++)
179 if (mate[i] == -1)
180 MinCover_ColDFS(xadj, adjncy, i, mate, where, INCOL);
181 for (; i<bsize; i++)
182 if (mate[i] == -1)
183 MinCover_RowDFS(xadj, adjncy, i, mate, where, INROW);
184
185 for (i=0; i<bsize; i++)
186 card[where[i]]++;
187
188 k = 0;
189 if (iabs(card[VC]+card[SC]-card[HR]) < iabs(card[VC]-card[SR]-card[HR])) { /* S = VC+SC+HR */
190 /* printf("%"PRIDX" %"PRIDX" ",vc+sc, hr); */
191 for (i=0; i<bsize; i++)
192 if (where[i] == VC || where[i] == SC || where[i] == HR)
193 cover[k++] = i;
194 }
195 else { /* S = VC+SR+HR */
196 /* printf("%"PRIDX" %"PRIDX" ",vc, hr+sr); */
197 for (i=0; i<bsize; i++)
198 if (where[i] == VC || where[i] == SR || where[i] == HR)
199 cover[k++] = i;
200 }
201
202 *csize = k;
203 gk_free((void **)&where, LTERM);
204
205 }
206
207
208 /*************************************************************************
209 * This function perfoms a dfs starting from an unmatched col node
210 * forming alternate paths
211 **************************************************************************/
MinCover_ColDFS(idx_t * xadj,idx_t * adjncy,idx_t root,idx_t * mate,idx_t * where,idx_t flag)212 void MinCover_ColDFS(idx_t *xadj, idx_t *adjncy, idx_t root, idx_t *mate, idx_t *where, idx_t flag)
213 {
214 idx_t i;
215
216 if (flag == INCOL) {
217 if (where[root] == HC)
218 return;
219 where[root] = HC;
220 for (i=xadj[root]; i<xadj[root+1]; i++)
221 MinCover_ColDFS(xadj, adjncy, adjncy[i], mate, where, INROW);
222 }
223 else {
224 if (where[root] == HR)
225 return;
226 where[root] = HR;
227 if (mate[root] != -1)
228 MinCover_ColDFS(xadj, adjncy, mate[root], mate, where, INCOL);
229 }
230
231 }
232
233 /*************************************************************************
234 * This function perfoms a dfs starting from an unmatched col node
235 * forming alternate paths
236 **************************************************************************/
MinCover_RowDFS(idx_t * xadj,idx_t * adjncy,idx_t root,idx_t * mate,idx_t * where,idx_t flag)237 void MinCover_RowDFS(idx_t *xadj, idx_t *adjncy, idx_t root, idx_t *mate, idx_t *where, idx_t flag)
238 {
239 idx_t i;
240
241 if (flag == INROW) {
242 if (where[root] == VR)
243 return;
244 where[root] = VR;
245 for (i=xadj[root]; i<xadj[root+1]; i++)
246 MinCover_RowDFS(xadj, adjncy, adjncy[i], mate, where, INCOL);
247 }
248 else {
249 if (where[root] == VC)
250 return;
251 where[root] = VC;
252 if (mate[root] != -1)
253 MinCover_RowDFS(xadj, adjncy, mate[root], mate, where, INROW);
254 }
255
256 }
257
258
259
260