SCM

SCM Repository

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

Annotation of /pkg/src/Metis/fm.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 :     * fm.c
5 :     *
6 :     * This file contains code that implements the edge-based FM refinement
7 :     *
8 :     * Started 7/23/97
9 :     * George
10 :     *
11 :     * $Id: fm.c,v 1.1 2003/12/31 21:32:30 bates Exp $
12 :     */
13 :    
14 :     #include <metis.h>
15 :    
16 :    
17 :     /*************************************************************************
18 :     * This function performs an edge-based FM refinement
19 :     **************************************************************************/
20 :     void FM_2WayEdgeRefine(CtrlType *ctrl, GraphType *graph, int *tpwgts, int npasses)
21 :     {
22 :     int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;
23 :     idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
24 :     idxtype *moved, *swaps, *perm;
25 :     PQueueType parts[2];
26 :     int higain, oldgain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;
27 :    
28 :     nvtxs = graph->nvtxs;
29 :     xadj = graph->xadj;
30 :     vwgt = graph->vwgt;
31 :     adjncy = graph->adjncy;
32 :     adjwgt = graph->adjwgt;
33 :     where = graph->where;
34 :     id = graph->id;
35 :     ed = graph->ed;
36 :     pwgts = graph->pwgts;
37 :     bndptr = graph->bndptr;
38 :     bndind = graph->bndind;
39 :    
40 :     moved = idxwspacemalloc(ctrl, nvtxs);
41 :     swaps = idxwspacemalloc(ctrl, nvtxs);
42 :     perm = idxwspacemalloc(ctrl, nvtxs);
43 :    
44 :     limit = amin(amax(0.01*nvtxs, 15), 100);
45 :     avgvwgt = amin((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);
46 :    
47 :     tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];
48 :     PQueueInit(ctrl, &parts[0], nvtxs, tmp);
49 :     PQueueInit(ctrl, &parts[1], nvtxs, tmp);
50 :    
51 :     IFSET(ctrl->dbglvl, DBG_REFINE,
52 :     printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d\n",
53 :     pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
54 :    
55 :     origdiff = abs(tpwgts[0]-pwgts[0]);
56 :     idxset(nvtxs, -1, moved);
57 :     for (pass=0; pass<npasses; pass++) { /* Do a number of passes */
58 :     PQueueReset(&parts[0]);
59 :     PQueueReset(&parts[1]);
60 :    
61 :     mincutorder = -1;
62 :     newcut = mincut = initcut = graph->mincut;
63 :     mindiff = abs(tpwgts[0]-pwgts[0]);
64 :    
65 :     ASSERT(ComputeCut(graph, where) == graph->mincut);
66 :     ASSERT(CheckBnd(graph));
67 :    
68 :     /* Insert boundary nodes in the priority queues */
69 :     nbnd = graph->nbnd;
70 :     RandomPermute(nbnd, perm, 1);
71 :     for (ii=0; ii<nbnd; ii++) {
72 :     i = perm[ii];
73 :     ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
74 :     ASSERT(bndptr[bndind[i]] != -1);
75 :     PQueueInsert(&parts[where[bndind[i]]], bndind[i], ed[bndind[i]]-id[bndind[i]]);
76 :     }
77 :    
78 :     for (nswaps=0; nswaps<nvtxs; nswaps++) {
79 :     from = (tpwgts[0]-pwgts[0] < tpwgts[1]-pwgts[1] ? 0 : 1);
80 :     to = (from+1)%2;
81 :    
82 :     if ((higain = PQueueGetMax(&parts[from])) == -1)
83 :     break;
84 :     ASSERT(bndptr[higain] != -1);
85 :    
86 :     newcut -= (ed[higain]-id[higain]);
87 :     INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
88 :    
89 :     if ((newcut < mincut && abs(tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) ||
90 :     (newcut == mincut && abs(tpwgts[0]-pwgts[0]) < mindiff)) {
91 :     mincut = newcut;
92 :     mindiff = abs(tpwgts[0]-pwgts[0]);
93 :     mincutorder = nswaps;
94 :     }
95 :     else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
96 :     newcut += (ed[higain]-id[higain]);
97 :     INC_DEC(pwgts[from], pwgts[to], vwgt[higain]);
98 :     break;
99 :     }
100 :    
101 :     where[higain] = to;
102 :     moved[higain] = nswaps;
103 :     swaps[nswaps] = higain;
104 :    
105 :     IFSET(ctrl->dbglvl, DBG_MOVEINFO,
106 :     printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-id[higain], vwgt[higain], newcut, pwgts[0], pwgts[1]));
107 :    
108 :     /**************************************************************
109 :     * Update the id[i]/ed[i] values of the affected nodes
110 :     ***************************************************************/
111 :     SWAP(id[higain], ed[higain], tmp);
112 :     if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
113 :     BNDDelete(nbnd, bndind, bndptr, higain);
114 :    
115 :     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
116 :     k = adjncy[j];
117 :     oldgain = ed[k]-id[k];
118 :    
119 :     kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
120 :     INC_DEC(id[k], ed[k], kwgt);
121 :    
122 :     /* Update its boundary information and queue position */
123 :     if (bndptr[k] != -1) { /* If k was a boundary vertex */
124 :     if (ed[k] == 0) { /* Not a boundary vertex any more */
125 :     BNDDelete(nbnd, bndind, bndptr, k);
126 :     if (moved[k] == -1) /* Remove it if in the queues */
127 :     PQueueDelete(&parts[where[k]], k, oldgain);
128 :     }
129 :     else { /* If it has not been moved, update its position in the queue */
130 :     if (moved[k] == -1)
131 :     PQueueUpdate(&parts[where[k]], k, oldgain, ed[k]-id[k]);
132 :     }
133 :     }
134 :     else {
135 :     if (ed[k] > 0) { /* It will now become a boundary vertex */
136 :     BNDInsert(nbnd, bndind, bndptr, k);
137 :     if (moved[k] == -1)
138 :     PQueueInsert(&parts[where[k]], k, ed[k]-id[k]);
139 :     }
140 :     }
141 :     }
142 :    
143 :     }
144 :    
145 :    
146 :     /****************************************************************
147 :     * Roll back computations
148 :     *****************************************************************/
149 :     for (i=0; i<nswaps; i++)
150 :     moved[swaps[i]] = -1; /* reset moved array */
151 :     for (nswaps--; nswaps>mincutorder; nswaps--) {
152 :     higain = swaps[nswaps];
153 :    
154 :     to = where[higain] = (where[higain]+1)%2;
155 :     SWAP(id[higain], ed[higain], tmp);
156 :     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
157 :     BNDDelete(nbnd, bndind, bndptr, higain);
158 :     else if (ed[higain] > 0 && bndptr[higain] == -1)
159 :     BNDInsert(nbnd, bndind, bndptr, higain);
160 :    
161 :     INC_DEC(pwgts[to], pwgts[(to+1)%2], vwgt[higain]);
162 :     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
163 :     k = adjncy[j];
164 :    
165 :     kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
166 :     INC_DEC(id[k], ed[k], kwgt);
167 :    
168 :     if (bndptr[k] != -1 && ed[k] == 0)
169 :     BNDDelete(nbnd, bndind, bndptr, k);
170 :     if (bndptr[k] == -1 && ed[k] > 0)
171 :     BNDInsert(nbnd, bndind, bndptr, k);
172 :     }
173 :     }
174 :    
175 :     IFSET(ctrl->dbglvl, DBG_REFINE,
176 :     printf("\tMinimum cut: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
177 :    
178 :     graph->mincut = mincut;
179 :     graph->nbnd = nbnd;
180 :    
181 :     if (mincutorder == -1 || mincut == initcut)
182 :     break;
183 :     }
184 :    
185 :     PQueueFree(ctrl, &parts[0]);
186 :     PQueueFree(ctrl, &parts[1]);
187 :    
188 :     idxwspacefree(ctrl, nvtxs);
189 :     idxwspacefree(ctrl, nvtxs);
190 :     idxwspacefree(ctrl, nvtxs);
191 :    
192 :     }
193 :    
194 :    

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