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 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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 
#define iabs
#define SR
Definition: mincover.c:25
void MinCover_Decompose(idx_t *xadj, idx_t *adjncy, idx_t asize, idx_t bsize, idx_t *mate, idx_t *cover, idx_t *csize)
Definition: mincover.c:163
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)
Definition: mincover.c:126
#define imalloc
Definition: gklib_rename.h:42
#define ismalloc
Definition: gklib_rename.h:68
idx_t idx_t * xadj
void MinCover_RowDFS(idx_t *xadj, idx_t *adjncy, idx_t root, idx_t *mate, idx_t *where, idx_t flag)
Definition: mincover.c:237
void MinCover_ColDFS(idx_t *xadj, idx_t *adjncy, idx_t root, idx_t *mate, idx_t *where, idx_t flag)
Definition: mincover.c:212
#define INROW
Definition: mincover.c:20
#define PRIDX
#define VC
Definition: mincover.c:21
#define INCOL
Definition: mincover.c:19
#define SC
Definition: mincover.c:22
m row(1)
int32_t idx_t
#define VR
Definition: mincover.c:24
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t idx_t idx_t idx_t * where
idx_t idx_t idx_t * adjncy
#define HR
Definition: mincover.c:26
m col(1)
void MinCover(idx_t *xadj, idx_t *adjncy, idx_t asize, idx_t bsize, idx_t *cover, idx_t *csize)
Definition: mincover.c:42
std::ptrdiff_t j
#define HC
Definition: mincover.c:23
#define LTERM
Definition: gk_defs.h:14


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:55