SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/mincover.c
ViewVC logotype

Annotation of /pkg/src/Metis/mincover.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
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 2003/12/31 21:32:30 bates 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 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge