Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
mincover.c
Go to the documentation of this file.
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,v 1.1 1998/11/27 17:59:22 karypis Exp $
12  */
13 
14 #include <metis.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 **************************************************************************/
42 void MinCover(idxtype *xadj, idxtype *adjncy, int asize, int bsize, idxtype *cover, int *csize)
43 {
44  int i, j;
45  idxtype *mate, *queue, *flag, *level, *lst;
46  int fptr, rptr, lstptr;
47  int row, maxlevel, col;
48 
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");
53  lst = idxmalloc(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[%d] 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  GKfree(&mate, &flag, &level, &queue, &lst, LTERM);
119 
120 }
121 
122 
123 /*************************************************************************
124 * This function perfoms a restricted DFS and augments matchings
125 **************************************************************************/
126 int MinCover_Augment(idxtype *xadj, idxtype *adjncy, int col, idxtype *mate, idxtype *flag, idxtype *level, int maxlevel)
127 {
128  int i;
129  int row = -1;
130  int 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 **************************************************************************/
163 void MinCover_Decompose(idxtype *xadj, idxtype *adjncy, int asize, int bsize, idxtype *mate, idxtype *cover, int *csize)
164 {
165  int i, k;
166  idxtype *where;
167  int card[10];
168 
169  where = idxmalloc(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 (abs(card[VC]+card[SC]-card[HR]) < abs(card[VC]-card[SR]-card[HR])) { /* S = VC+SC+HR */
190  /* printf("%d %d ",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("%d %d ",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  free(where);
204 
205 }
206 
207 
208 /*************************************************************************
209 * This function perfoms a dfs starting from an unmatched col node
210 * forming alternate paths
211 **************************************************************************/
212 void MinCover_ColDFS(idxtype *xadj, idxtype *adjncy, int root, idxtype *mate, idxtype *where, int flag)
213 {
214  int 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 **************************************************************************/
237 void MinCover_RowDFS(idxtype *xadj, idxtype *adjncy, int root, idxtype *mate, idxtype *where, int flag)
238 {
239  int 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 
#define SR
Definition: mincover.c:25
#define MinCover_RowDFS
Definition: rename.h:200
#define INROW
Definition: mincover.c:20
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define VC
Definition: mincover.c:21
#define INCOL
Definition: mincover.c:19
#define MinCover_Decompose
Definition: rename.h:198
#define SC
Definition: mincover.c:22
#define idxsmalloc
Definition: rename.h:386
#define MinCover_ColDFS
Definition: rename.h:199
#define VR
Definition: mincover.c:24
void GKfree(void **ptr1,...)
Definition: util.c:121
#define MinCover
Definition: rename.h:196
#define HR
Definition: mincover.c:26
#define idxmalloc
Definition: rename.h:383
#define MinCover_Augment
Definition: rename.h:197
#define HC
Definition: mincover.c:23