1 /* This software was developed by Bruce Hendrickson and Robert Leland *
2 * at Sandia National Laboratories under US Department of Energy *
3 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
4
5 /* Despite the formal disclaimer above, this routine is modified from
6 code provided by Ed Rothberg at SGI. */
7
8 #include <stdio.h>
9
10 #define TRUE 1
11 #define FALSE 0
12
13 /*
14 The following code takes a bipartite graph as input (with
15 n_left+n_right nodes, where node 'i' is adjacent to nodes
16 'indices[pointers[i]]' through 'indices[pointers[i+1]-1]', all
17 0-based) and returns a minimum size edge cover (in sep_nodes[]).
18
19 */
20
21 static void bpmatching(), reachability(), augment();
22 static int touch(), touch2();
23
24
bpcover(n_left,n_right,pointers,indices,sep_size,sep_nodes)25 void bpcover(n_left, n_right, pointers, indices,
26 sep_size, sep_nodes)
27 int n_left; /* number of vertices on left side */
28 int n_right; /* number of vertices on right side */
29 int *pointers; /* start/stop of adjacency lists */
30 int *indices; /* adjacency list for each vertex */
31 int *sep_size; /* returned size of separator */
32 int *sep_nodes; /* list of separator nodes */
33 {
34 extern int DEBUG_COVER; /* controls debugging output in this routine */
35 int *matching; /* array to encode matching */
36 int *touched; /* flags for each vertex */
37 int i; /* loop counter */
38 double *smalloc();
39 int sfree();
40 void confirm_match();
41
42 if (DEBUG_COVER) {
43 printf("-> Entering bpcover, nleft = %d, nright = %d, 2*nedges = %d\n",
44 n_left, n_right, pointers[n_left+n_right]-pointers[0]);
45 }
46
47 matching = (int *) smalloc((unsigned) (n_left + n_right) * sizeof(int));
48 touched = (int *) smalloc((unsigned) (n_left + n_right) * sizeof(int));
49
50 bpmatching(n_left, n_right, pointers, indices, matching, touched);
51
52 reachability(n_left, n_right, pointers, indices, matching, touched);
53
54
55 /* Separator includes untouched nodes on left, touched on right. */
56 /* Left separator nodes if unconnected to unmatched left node via */
57 /* augmenting path, right separator nodes otherwise. */
58
59 *sep_size = 0;
60 for (i = 0; i < n_left; i++) {
61 if (!touched[i]) {
62 sep_nodes[(*sep_size)++] = i;
63 }
64 }
65 for (i = n_left; i < n_left + n_right; i++) {
66 if (touched[i]) {
67 sep_nodes[(*sep_size)++] = i;
68 }
69 }
70
71 sep_nodes[(*sep_size)] = 0;
72
73 if (DEBUG_COVER) {
74 confirm_match(n_left, n_right, pointers, indices, matching, *sep_size, sep_nodes);
75 }
76
77
78 sfree((char *) touched);
79 sfree((char *) matching);
80 }
81
82
bpmatching(n_left,n_right,pointers,indices,matching,touched)83 static void bpmatching(n_left, n_right, pointers, indices, matching, touched)
84 int n_left; /* number of vertices on left side */
85 int n_right; /* number of vertices on right side */
86 int *pointers; /* start/stop of adjacency lists */
87 int *indices; /* adjacency list for each vertex */
88 int *matching; /* array to encode matching */
89 int *touched; /* flags for each vertex */
90 {
91 int *seen; /* space for list of encountered vertices */
92 int i, j; /* loop counters */
93 double *smalloc();
94 int sfree();
95
96 /* First mark all the vertices as unmatched & untouched. */
97 for (i = 0; i < n_left + n_right; i++) {
98 matching[i] = -1;
99 touched[i] = FALSE;
100 }
101
102 /* Now generate a fast, greedy matching to start. */
103 for (i = n_left; i < n_left + n_right; i++) {
104 for (j = pointers[i]; j < pointers[i + 1]; j++) {
105 if (matching[indices[j]] == -1) {
106 /* Node not already matched. */
107 matching[i] = indices[j];
108 matching[indices[j]] = i;
109 break;
110 }
111 }
112 }
113
114 /* Now try to enlarge it via augmenting paths. */
115
116 seen = (int *) smalloc((unsigned) (n_left + n_right) * sizeof(int));
117
118 /* Look for an augmenting path. */
119 for (i = 0; i < n_left; i++) {
120 if (matching[i] == -1) {
121 augment(i, pointers, indices, matching, touched, seen);
122 }
123 }
124
125 sfree((char *) seen);
126 }
127
128
augment(node,pointers,indices,matching,touched,seen)129 static void augment(node, pointers, indices, matching, touched, seen)
130 int node; /* start node in augmenting path */
131 int *pointers; /* start/stop of adjacency lists */
132 int *indices; /* adjacency list for each vertex */
133 int *matching; /* array to encode matching */
134 int *touched; /* flags for each vertex */
135 int *seen; /* keeps list of vertices encountered */
136 {
137 int nseen; /* number of vertices encountered */
138 int enlarged; /* was matching enlarged? */
139 int i; /* loop counter */
140
141 /* Look for augmenting path in graph. */
142
143 nseen = 0;
144 enlarged = touch(node, pointers, indices, matching, touched, seen, &nseen);
145
146 if (enlarged) { /* Found an augmenting path! */
147 /* Free all the vertices encountered in search. */
148 /* Otherwise, they can't be involved in augmentation, */
149 /* so leave them touched. */
150 for (i = 0; i < nseen; i++) {
151 touched[*seen++] = FALSE;
152 }
153 }
154 }
155
156
157 /* Mark everybody in my alternating path tree, and recursively update */
158 /* matching if augmenting path found. */
touch(node,pointers,indices,matching,touched,seen,nseen)159 static int touch(node, pointers, indices, matching, touched, seen, nseen)
160 int node;
161 int *pointers; /* start/stop of adjacency lists */
162 int *indices; /* adjacency list for each vertex */
163 int *matching; /* array to encode matching */
164 int *touched; /* flags for each vertex */
165 int *seen; /* list of vertices encountered */
166 int *nseen; /* number of vertices encountered */
167 {
168 int neighbor; /* neighbor of a vertex */
169 int result; /* return node number (or -1) */
170 int j; /* loop counter */
171
172 touched[node] = TRUE;
173 seen[(*nseen)++] = node;
174
175 for (j = pointers[node]; j < pointers[node + 1]; j++) {
176 neighbor = indices[j];
177 if (!touched[neighbor]) {
178 touched[neighbor] = TRUE;
179 seen[(*nseen)++] = neighbor;
180 if (matching[neighbor] == -1) { /* Found augmenting path! */
181 matching[neighbor] = node;
182 matching[node] = neighbor;
183 return (TRUE);
184 }
185 else {
186 result = touch(matching[neighbor], pointers, indices, matching, touched,
187 seen, nseen);
188 if (result) {
189 matching[neighbor] = node;
190 matching[node] = neighbor;
191 return (TRUE);
192 }
193 }
194 }
195 }
196 return (FALSE);
197 }
198
199
reachability(n_left,n_right,pointers,indices,matching,touched)200 static void reachability(n_left, n_right, pointers, indices, matching, touched)
201 int n_left; /* number of vertices on left side */
202 int n_right; /* number of vertices on right side */
203 int *pointers; /* start/stop of adjacency lists */
204 int *indices; /* adjacency list for each vertex */
205 int *matching; /* array to encode matching */
206 int *touched; /* flags for each vertex */
207 {
208 int i; /* loop counter */
209
210 /* Initialize all the vertices to be untouched */
211 for (i = 0; i < n_left + n_right; i++)
212 touched[i] = 0;
213
214 for (i = 0; i < n_left; i++)
215 if (!touched[i] && matching[i] == -1)
216 touch2(i, pointers, indices, matching, touched);
217 }
218
219
220 /* Mark everybody in my alternating path tree, and return vertex at */
221 /* end of augmenting path if found. */
touch2(node,pointers,indices,matching,touched)222 static int touch2(node, pointers, indices, matching, touched)
223 int node;
224 int *pointers; /* start/stop of adjacency lists */
225 int *indices; /* adjacency list for each vertex */
226 int *matching; /* array to encode matching */
227 int *touched; /* flags for each vertex */
228 {
229 int neighbor; /* neighbor of a vertex */
230 int result; /* return node number (or -1) */
231 int j; /* loop counter */
232
233 touched[node] = TRUE;
234 for (j = pointers[node]; j < pointers[node + 1]; j++) {
235 neighbor = indices[j];
236 if (!touched[neighbor]) {
237 touched[neighbor] = TRUE;
238 if (matching[neighbor] == -1) {
239 return (TRUE);
240 }
241 else {
242 result = touch2(matching[neighbor], pointers, indices, matching, touched);
243 if (result) {
244 return (TRUE);
245 }
246 }
247 }
248 }
249 return (FALSE);
250 }
251
252
confirm_match(n_left,n_right,pointers,indices,matching,sep_size,sep_nodes)253 void confirm_match(n_left, n_right, pointers, indices, matching, sep_size, sep_nodes)
254 int n_left; /* number of vertices on left side */
255 int n_right; /* number of vertices on right side */
256 int *pointers; /* start/stop of adjacency lists */
257 int *indices; /* adjacency list for each vertex */
258 int *matching; /* array to encode matching */
259 int sep_size; /* returned size of separator */
260 int *sep_nodes; /* list of separator nodes */
261 {
262 int *marked;
263 int neighbor;
264 int i, j; /* loop counter */
265 int match_size();
266 double *smalloc();
267 int sfree();
268
269 marked = (int *) smalloc((unsigned) (n_left + n_right) * sizeof(int));
270
271 for (i = 0; i < n_left + n_right; i++) {
272 marked[i] = FALSE;
273 }
274
275 for (i = 0; i < sep_size; i++) {
276 marked[sep_nodes[i]] = TRUE;
277 }
278
279 for (i = 0; i < n_left; i++) {
280 if (!marked[i]) {
281 for (j = pointers[i]; j < pointers[i + 1]; j++) {
282 neighbor = indices[j];
283 if (!marked[neighbor]) {
284 printf("Edge (%d, %d) not covered\n", i, neighbor);
285 }
286 }
287 }
288 }
289
290 sfree((char *) marked);
291
292 i = match_size(matching, n_left);
293 if (sep_size != i) {
294 printf("ERROR: sep_size = %d, but match_size = %d\n", sep_size, i);
295 }
296
297 for (i = 0; i < n_left + n_right; i++) {
298 if (matching[i] != -1 && matching[matching[i]] != i) {
299 printf("ERROR: matching[%d] = %d, but matching[%d] = %d\n",
300 i, matching[i], matching[i], matching[matching[i]]);
301 }
302 }
303 }
304
305
match_size(matching,nleft)306 int match_size(matching, nleft)
307 int *matching, nleft;
308 {
309 int i, nmatch;
310
311 nmatch = 0;
312 for (i = 0; i < nleft; i++) {
313 if (matching[i] != -1) ++nmatch;
314 }
315 return(nmatch);
316 }
317