ACloudViewer  3.9.4
A Modern Library for 3D Data Processing
wkkm.c
Go to the documentation of this file.
1 /*
2  * Copyright 2005, Yuqiang Guan
3  *
4  * wkkm.c
5  *
6  * This file contains weighted kernel k-means and refinement.
7  *
8  * Started 12/04
9  * Yuqiang Guan
10  *
11  *
12  */
13 
14 #include "metisLib/metis.h"
15 #include <float.h>
16 
17 extern int cutType, memory_saving, boundary_points;
18 
19 void Compute_Weights(CtrlType *ctrl, GraphType *graph, idxtype *w)
20  /* compute the weights for WKKM; for the time, only Ncut. w is zero-initialized */
21 {
22  int nvtxs, i, j;
23  idxtype *xadj, *adjwgt;
24 
25  nvtxs = graph->nvtxs;
26  xadj = graph->xadj;
27  adjwgt = graph->adjwgt;
28 
29  if ((cutType == RASSO) || (cutType == RCUT))
30  for (i=0; i<nvtxs; i++)
31  w[i] = 1;
32  else
33  if (adjwgt == NULL)
34  for (i=0; i<nvtxs; i++)
35  for (j=xadj[i]; j<xadj[i+1]; j++)
36  w[i] ++;
37  else
38  for (i=0; i<nvtxs; i++)
39  for (j=xadj[i]; j<xadj[i+1]; j++)
40  w[i] += adjwgt[j];
41 }
42 
43 void transform_matrix(CtrlType *ctrl, GraphType *graph, idxtype *w, float *m_adjwgt)
44  /* normalized the adjacency matrix for Ncut only*/
45 {
46  int nvtxs, i, j;
47  idxtype *xadj, *adjncy, *adjwgt, *where;
48 
49  nvtxs = graph->nvtxs;
50  xadj = graph->xadj;
51  adjncy = graph->adjncy;
52  adjwgt = graph->adjwgt;
53 
54  if (cutType == RASSO){ // ratio asso.
55  if (adjwgt == NULL)
56  for (i=0; i<nvtxs; i++)
57  for (j=xadj[i]; j<xadj[i+1]; j++)
58  m_adjwgt[j] =1;
59  else
60  for (i=0; i<nvtxs; i++)
61  for (j=xadj[i]; j<xadj[i+1]; j++)
62  m_adjwgt[j] = adjwgt[j];
63  }
64  else{ //normalize rows and columns
65  if (adjwgt == NULL){
66  for (i=0; i<nvtxs; i++)
67  for (j=xadj[i]; j<xadj[i+1]; j++)
68  if (w[i]>0)
69  m_adjwgt[j] = 1.0/w[i];
70  for (i=0; i<nvtxs; i++)
71  for (j=xadj[i]; j<xadj[i+1]; j++)
72  if (w[i]>0)
73  m_adjwgt[j] /= w[adjncy[j]];
74  }
75  else{
76  for (i=0; i<nvtxs; i++)
77  for (j=xadj[i]; j<xadj[i+1]; j++)
78  if (w[i]>0)
79  m_adjwgt[j] = adjwgt[j] *1.0/w[i];
80  else
81  m_adjwgt[j] = 0;
82  for (i=0; i<nvtxs; i++)
83  for (j=xadj[i]; j<xadj[i+1]; j++)
84  if (w[i]>0)
85  m_adjwgt[j] /= w[adjncy[j]];
86  }
87  }
88 }
89 
90 void transform_matrix_half(CtrlType *ctrl, GraphType *graph, idxtype *w, float *m_adjwgt)
91  /* normalized the adjacency matrix for Ncut only, D^-.5*A*D^-.5*/
92 {
93  int nvtxs, i, j;
94  idxtype *xadj, *adjncy, *adjwgt, *where;
95 
96  nvtxs = graph->nvtxs;
97  xadj = graph->xadj;
98  adjncy = graph->adjncy;
99  adjwgt = graph->adjwgt;
100 
101  if (cutType == RASSO){ // ratio asso.
102  if (adjwgt == NULL)
103  for (i=0; i<nvtxs; i++)
104  for (j=xadj[i]; j<xadj[i+1]; j++)
105  m_adjwgt[j] =1;
106  else
107  for (i=0; i<nvtxs; i++)
108  for (j=xadj[i]; j<xadj[i+1]; j++)
109  m_adjwgt[j] = adjwgt[j];
110  }
111  else{ //normalize rows and columns
112  if (adjwgt == NULL){
113  for (i=0; i<nvtxs; i++)
114  for (j=xadj[i]; j<xadj[i+1]; j++)
115  if (w[i]>0)
116  m_adjwgt[j] = 1.0/sqrt(w[i]);
117  for (i=0; i<nvtxs; i++)
118  for (j=xadj[i]; j<xadj[i+1]; j++)
119  if (w[adjncy[j]]>0)
120  m_adjwgt[j] /= sqrt(w[adjncy[j]]);
121  }
122  else{
123  for (i=0; i<nvtxs; i++)
124  for (j=xadj[i]; j<xadj[i+1]; j++)
125  if (w[i]>0)
126  m_adjwgt[j] = adjwgt[j] *1.0/sqrt(w[i]);
127  else
128  m_adjwgt[j] = 0;
129  for (i=0; i<nvtxs; i++)
130  for (j=xadj[i]; j<xadj[i+1]; j++)
131  if (w[adjncy[j]]>0)
132  m_adjwgt[j] /= sqrt(w[adjncy[j]]);
133  }
134  }
135 }
136 
137 
138 void pingpong(CtrlType *ctrl, GraphType *graph, int nparts, int chain_length, float *tpwgts, float ubfactor, int toplevel)
139  // do batch-local search; chain_length is the search length
140 {
141 
142  int nvtxs, nedges, moves, iter;
143  idxtype *w;
144  //float *m_adjwgt;
145 
146  nedges = graph->nedges;
147  nvtxs = graph->nvtxs;
148 
149  w = idxsmalloc(nvtxs, 0, "pingpong: weight");
150  Compute_Weights(ctrl, graph, w);
151  //m_adjwgt = fmalloc(nedges, "pingpong: normalized matrix");
152  //transform_matrix(ctrl, graph, w, m_adjwgt);
153 
154  //printf("Chain length is %d.\n", chain_length);
155 
156  moves =0;
157  iter =0;
158 
159  //printf("Number of boundary points is %d\n", graph->nbnd);
160  do{
161  //Weighted_kernel_k_means(ctrl, graph, nparts, w, m_adjwgt, tpwgts, ubfactor);
162  Weighted_kernel_k_means(ctrl, graph, nparts, w, tpwgts, ubfactor);
163  if (chain_length>0){
164 
165  //moves = local_search(ctrl, graph, nparts, chain_length, w, m_adjwgt, tpwgts, ubfactor);
166  moves = local_search(ctrl, graph, nparts, chain_length, w, tpwgts, ubfactor);
167  //printf("Number of local search moves is %d\n", moves);
168  //printf("Number of boundary points is %d\n", graph->nbnd);
169  }
170  iter ++;
171  if (iter > MAXITERATIONS)
172  break;
173  }while(moves >0) ;
174  if(memory_saving ==0){
175  remove_empty_clusters_l1(ctrl, graph, nparts, w, tpwgts, ubfactor);
176  if(toplevel>0)
177  remove_empty_clusters_l2(ctrl, graph, nparts, w, tpwgts, ubfactor);
178  }
179  free(w);
180  //free(m_adjwgt);
181 }
182 
183 void Weighted_kernel_k_means(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor){
184  // w is the weights
185 
186 
187  int nvtxs, nbnd, nedges, me, i, j;
188  idxtype *squared_sum, *sum, *xadj, *adjncy, *adjwgt, *where, *new_where, *bndptr, *bndind;
189  float obj, old_obj, epsilon, *inv_sum, *squared_inv_sum;
190  int change;
191  idxtype *linearTerm, ii;
192  int loopend, currit=0;
193 
194  nedges = graph->nedges;
195  nvtxs = graph->nvtxs;
196  nbnd = graph-> nbnd;
197  xadj = graph->xadj;
198  adjncy = graph->adjncy;
199  adjwgt = graph->adjwgt;
200  where = graph->where;
201  bndptr = graph->bndptr;
202  bndind = graph->bndind;
203 
204  // we need new_where because in kernel k-means distance is based on cluster label
205  // if we change a label, distance to that cluster will change
206  new_where = idxmalloc(nvtxs, "Weighted_kernel_k_means: new_where");
207  for (i=0; i<nvtxs; i++)
208  new_where[i] = where[i];
209 
210  sum = idxsmalloc(nparts,0, "Weighted_kernel_k_means: weight sum");
211  inv_sum = fmalloc(nparts, "Weighted_kernel_k_means: sum inverse");
212  squared_inv_sum = fmalloc(nparts, "Weighted_kernel_k_means: squared sum inverse");
213  squared_sum = idxsmalloc(nparts,0, "Weighted_kernel_k_means: weight squared sum");
214 
215  //initialization
216 
217  obj = old_obj = 0;
218  for (i=0; i<nvtxs; i++)
219  sum[where[i]] += w[i];
220  for (i=0; i<nparts; i++)
221  if(sum[i] >0){
222  inv_sum[i] = 1.0/sum[i];
223  squared_inv_sum[i] = inv_sum[i]*inv_sum[i];
224  }
225  else
226  inv_sum[i] = squared_inv_sum[i] = 0;
227 
228  /*
229  if (adjwgt == NULL) //if graph has uniform edge weights
230  for (i=0; i<nvtxs; i++){
231  me = where[i];
232  for (j=xadj[i]; j<xadj[i+1]; j++)
233  if (where[adjncy[j]] == me)
234  squared_sum[me] ++;
235  }
236  else*/
237  for (i=0; i<nvtxs; i++){
238  me = where[i];
239  for (j=xadj[i]; j<xadj[i+1]; j++)
240  if (where[adjncy[j]] == me)
241  squared_sum[me] += adjwgt[j];
242  }
243 
244  //note the obj here is not obj. fun. of wkkm, just the second trace value to be maximized
245  for (i=0; i<nparts; i++)
246  if (sum[i] >0)
247  obj += squared_sum[i]*1.0/sum[i];
248 
249  epsilon =.00001;
250  linearTerm = idxmalloc(nparts, "Weighted_kernel_k_means: new_where");
251 
252  do{
253  float min_dist, dist;
254  int min_ind, k;
255  change =0;
256  old_obj = obj;
257  currit++;
258  /*
259  if (adjwgt == NULL) // if graph has uniform edge weights
260  for (i=0; i<nvtxs; i++){ // compute linear term in distance from point i to all centers
261  min_ind = me = where[i];
262 
263  for (k=0; k<nparts; k++)
264  linearTerm[k] =0;
265  for (j=xadj[i]; j<xadj[i+1]; j++)
266  linearTerm[where[adjncy[j]]] ++; // this line is the only difference between if and else
267  for (k=0; k<nparts; k++)
268  printf("U%f ", linearTerm[k]*1.0/w[i]);
269  printf("\n");
270  min_dist = squared_sum[me]*w[i]-2*linearTerm[me]*sum[me];
271 
272  for (k=0; k<me; k++){
273  dist = squared_sum[k]*w[i] - 2*linearTerm[k]*sum[k];
274  if(dist*sum[min_ind]*sum[min_ind] < min_dist*sum[k]*sum[k]){
275  min_dist = dist;
276  min_ind = k;
277  }
278  }
279  for (k=me+1; k<nparts; k++){
280  dist = squared_sum[k]*w[i] - 2*linearTerm[k]*sum[k];
281  if(dist*sum[min_ind]*sum[min_ind] < min_dist*sum[k]*sum[k]){
282  min_dist = dist;
283  min_ind = k;
284  }
285  }
286 
287  if(me != min_ind){
288  new_where[i] = min_ind; // note here we can not change where; otherwise we change the center
289  change ++;
290  }
291  }
292  else // if graph weight is various
293  */
294  //printf("iteration of weighted kernel k-means...\n");
295  if(boundary_points == 1)
296  loopend = nbnd;
297  else
298  loopend = nvtxs;
299  //for (i=0; i<nvtxs; i++){ // compute linear term in distance from point i to all centers
300  for (ii=0; ii<loopend; ii++){
301  if(boundary_points == 1)
302  i = bndind[ii];
303  else
304  i = ii;
305  if(w[i] >0){
306  float inv_wi=1.0/w[i];
307  for (k=0; k<nparts; k++)
308  linearTerm[k] =0;
309  for (j=xadj[i]; j<xadj[i+1]; j++)
310  linearTerm[where[adjncy[j]]] += adjwgt[j]; //only difference between if and else
311 
312  min_ind = me = where[i];
313  min_dist = squared_sum[me]*squared_inv_sum[me] - 2*inv_wi*linearTerm[me]*inv_sum[me];
314  /*if (sum[me] >0)
315  min_dist = squared_sum[me]*1.0/(1.0*sum[me]*sum[me])-2.0*linearTerm[me]/(sum[me]*w[i]);
316  */
317  for (k=0; k<me; k++){
318  dist = squared_sum[k]*squared_inv_sum[k] -2*inv_wi*linearTerm[k]*inv_sum[k];
319  /*
320  dist = 0;
321  if (sum[k] >0)
322  dist = squared_sum[k]*1.0/(1.0*sum[k]*sum[k])-2.0*linearTerm[k]/(sum[k]*w[i]);
323  */
324  if(dist < min_dist){
325  //if(dist < min_dist){
326  min_dist = dist;
327  min_ind = k;
328  }
329  }
330  for (k=me+1; k<nparts; k++){
331  dist = squared_sum[k]*squared_inv_sum[k] -2*inv_wi*linearTerm[k]*inv_sum[k];
332  /*
333  dist = 0;
334  if (sum[k] >0)
335  dist = squared_sum[k]*1.0/(1.0*sum[k]*sum[k])-2.0*linearTerm[k]/(sum[k]*w[i]);
336  */
337  if(dist < min_dist){
338  //if(dist < min_dist){
339  min_dist = dist;
340  min_ind = k;
341  }
342  }
343 
344  if(me != min_ind){
345  new_where[i] = min_ind; // note here we can not change where; otherwise we change the center
346  change ++;
347  }
348  //if(i==0)
349  //printf("%d(%d->%d), sum=(%d, %d), linear=(%f, %f), square=(%d, %d), dis=(%f-%f, %f-%f)\n",i, me, min_ind, sum[me], sum[min_ind], linearTerm[me]*1.0/w[i],linearTerm[min_ind]*1.0/w[i],squared_sum[me], squared_sum[min_ind], squared_sum[me]*1.0/(1.0*sum[me]*sum[me]), 2.0*linearTerm[me]/(sum[me]*w[i]), squared_sum[min_ind]*1.0/(1.0*sum[min_ind]*sum[min_ind]), 2.0*linearTerm[min_ind]/(sum[min_ind]*w[i]));
350  }
351  }
352 
353  // update sum and squared_sum
354  for (i=0; i<nparts; i++)
355  sum[i] = squared_sum[i] = 0;
356  for (i=0; i<nvtxs; i++)
357  sum[new_where[i]] += w[i];
358  for (i=0; i<nparts; i++)
359  if(sum[i] >0){
360  inv_sum[i] = 1.0/sum[i];
361  squared_inv_sum[i] = inv_sum[i]*inv_sum[i];
362  }
363  else
364  inv_sum[i] = squared_inv_sum[i] = 0;
365  /*
366  if (adjwgt == NULL)
367  for (i=0; i<nvtxs; i++){
368  me = new_where[i];
369  for (j=xadj[i]; j<xadj[i+1]; j++)
370  if (new_where[adjncy[j]] == me)
371  squared_sum[me] ++;
372  }
373  else
374  */
375  for (i=0; i<nvtxs; i++){
376  me = new_where[i];
377  for (j=xadj[i]; j<xadj[i+1]; j++)
378  if (new_where[adjncy[j]] == me)
379  squared_sum[me] += adjwgt[j];
380  }
381 
382  //update objective function (trace maximizatin)
383  obj=0;
384  for (i=0; i<nparts; i++)
385  if (sum[i] >0)
386  obj += squared_sum[i]*1.0/sum[i];
387  //if matrix is not positive definite
388  if (obj > old_obj)
389  {
390  if(boundary_points == 1)
391  loopend = nbnd;
392  else
393  loopend = nvtxs;
394  //for (i=0; i<nvtxs; i++){
395  for (ii=0; ii<loopend; ii++){
396  if(boundary_points == 1)
397  i = bndind[ii];
398  else
399  i = ii;
400  where[i] = new_where[i];
401  }
402  }
403  //printf("Obj: %6.6f, Old_obj: %6.6f, abs(obj-old_obj) = %6.6f\n", obj, old_obj, fabs(obj-old_obj));
404  }while((obj - old_obj) > epsilon*obj && currit < MAXITERATIONS);
405  free(sum); free(squared_sum); free(new_where); free(linearTerm); free(inv_sum); free(squared_inv_sum);
406 }
407 
408 
409 int local_search(CtrlType *ctrl, GraphType *graph, int nparts, int chain_length, idxtype *w, float *tpwgts, float ubfactor)
410  //return # of points moved
411 {
412  int nvtxs, nedges, nbnd, me, i, j, k, s, ii;
413  idxtype *sum, *squared_sum, *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
414  float change, obj, epsilon, **kDist, *accum_change;
415  int moves, actual_length, *mark, fidx, loopend;
416  Chains *chain;
417 
418  nedges = graph->nedges;
419  nvtxs = graph->nvtxs;
420  xadj = graph->xadj;
421  adjncy = graph->adjncy;
422  adjwgt = graph->adjwgt;
423  where = graph->where;
424  nbnd = graph->nbnd;
425  bndind = graph->bndind;
426  bndptr = graph->bndptr;
427 
428  if(boundary_points == 1)
429  loopend = nbnd;
430  else
431  loopend = nvtxs;
432 
433  chain = chainmalloc(chain_length, "Local_search: local search chain");
434  mark = ismalloc(loopend, 0 , "Local_search: mark");
435  sum = idxsmalloc(nparts,0, "Local_search: weight sum");
436  squared_sum = idxsmalloc(nparts,0,"Local_search: weight squared sum");
437  kDist = f2malloc(loopend, nparts, "Local_search: distance matrix");
438  accum_change = fmalloc(chain_length+1,"Local_search: accumulated change");
439 
440  //initialization
441  for (i = 0; i<nparts; i++)
442  sum[i] = squared_sum[i] = 0;
443  for (i = 0; i<loopend; i++)
444  for (j = 0; j<nparts; j++)
445  kDist[i][j] = 0;
446  for (i = 0; i<chain_length+1; i++)
447  accum_change[i] = 0;
448  obj = 0;
449  moves = 0;
450  epsilon =.0001;
451  actual_length = chain_length;
452 
453  for (i=0; i<nvtxs; i++)
454  sum[where[i]] += w[i];
455  for (i=0; i<nvtxs; i++){
456  me = where[i];
457  for (j=xadj[i]; j<xadj[i+1]; j++)
458  if (where[adjncy[j]] == me)
459  squared_sum[me] += adjwgt[j];
460  }
461 
462  //the diagonal entries won't affect the result so diagonal's assumed zero
463  //for (i=0; i<nvtxs; i++)
464  for (ii=0; ii<loopend; ii++){
465  if (boundary_points == 1)
466  i = bndind[ii];
467  else
468  i = ii;
469  for (j=xadj[i]; j<xadj[i+1]; j++)
470  //kDist[i][where[adjncy[j]]] += 1.0*adjwgt[j]/w[i];
471  kDist[ii][where[adjncy[j]]] += 1.0*adjwgt[j]/w[i];
472  }
473  for (k=0; k<nparts; k++)
474  if (sum[k] >0)
475  //for (i=0; i<nvtxs; i++)
476  for (ii=0; ii<loopend; ii++)
477  //kDist[i][k] = squared_sum[k]/(1.0*sum[k]*sum[k]) - 2*kDist[i][k]/sum[k];
478  kDist[ii][k] = squared_sum[k]/(1.0*sum[k]*sum[k]) - 2*kDist[ii][k]/sum[k];
479 
480  for (i=0; i<nparts; i++)
481  if (sum[i] >0)
482  obj += squared_sum[i]*1.0/sum[i];
483  for (i=0; i<chain_length; i++)
484  {
485  float tempMinChange, tempchange, temp_q;
486  int tempid, tempMoveTo, from, to, tempbndind;
487 
488  tempMinChange = obj;
489  tempchange =0;
490  tempid =0;
491  tempMoveTo = where[tempid];
492  tempbndind =0;
493 
494  //for (j=0; j<nvtxs; j++)
495  for (ii=0; ii<loopend; ii++){
496  if (boundary_points == 1)
497  j = bndind[ii];
498  else
499  j = ii;
500  if (mark[ii] ==0){
501  me = where[j];
502  if (sum[me] > w[j]) // if this cluster where j belongs is not a singleton
503  for (k=0; k<nparts; k++)
504  if (k != me){
505  //tempchange = -kDist[j][me]*sum[me]*w[j]/(sum[me]-w[j]) + kDist[j][k]*sum[k]*w[j]/(sum[k]+w[j]);
506  tempchange = -kDist[ii][me]*sum[me]*w[j]/(sum[me]-w[j]) + kDist[ii][k]*sum[k]*w[j]/(sum[k]+w[j]);
507  if (tempchange < tempMinChange){
508  tempMinChange = tempchange;
509  tempid = j;
510  tempbndind = ii;
511  tempMoveTo = k;
512  }
513  }
514  }
515  }
516  if ((tempMoveTo == where[tempid]) || (mark[tempbndind] >0)){
517  actual_length = i;
518  break;
519  }
520  else{
521  // record which point is moved from its original cluster to new cluster
522  chain[i].point = tempid;
523  chain[i].from = where[tempid];
524  chain[i].to = tempMoveTo;
525  chain[i].change = tempMinChange;
526  //mark the point moved
527  mark[tempbndind] = 1;
528  // update info
529  accum_change[i+1] = accum_change[i] + tempMinChange;
530  from = chain[i].from;
531  to = chain[i].to;
532  where[tempid] = to;
533  sum[from] -= w[tempid];
534  sum[to] += w[tempid];
535 
536  for (j=xadj[tempid]; j<xadj[tempid+1]; j++)
537  if (where[adjncy[j]] == from)
538  squared_sum[from] -= 2*adjwgt[j];
539  //for (s=0; s<nvtxs; s++){
540  for (ii=0; ii<loopend; ii++){
541  //kDist[s][from] = 0;
542  kDist[ii][from] = 0;
543  if(boundary_points == 1)
544  s = bndind[ii];
545  else
546  s = ii;
547  for (j=xadj[s]; j<xadj[s+1]; j++)
548  if (where[adjncy[j]] == from)
549  //kDist[s][from] += adjwgt[j]*1.0/w[s];
550  kDist[ii][from] += adjwgt[j]*1.0/w[s];
551  }
552  temp_q = squared_sum[from]/(1.0*sum[from]*sum[from]);
553 
554  //for (s=0; s<nvtxs; s++)
555  for (ii=0; ii<loopend; ii++)
556  kDist[ii][from] = temp_q - 2*kDist[ii][from]/sum[from];
557 
558  for (j=xadj[tempid]; j<xadj[tempid+1]; j++)
559  if (where[adjncy[j]] == to)
560  squared_sum[to] += 2*adjwgt[j];
561 
562  //for (s=0; s<nvtxs; s++){
563  for (ii=0; ii<loopend; ii++){
564  //kDist[s][to] = 0;
565  kDist[ii][to] = 0;
566  if(boundary_points == 1)
567  s = bndind[ii];
568  else
569  s = ii;
570  for (j=xadj[s]; j<xadj[s+1]; j++)
571  if (where[adjncy[j]] == to)
572  //kDist[s][to] += adjwgt[j]*1.0/w[s];
573  kDist[ii][to] += adjwgt[j]*1.0/w[s];
574  }
575  temp_q = squared_sum[to]/(1.0*sum[to]*sum[to]);
576 
577  //for (s=0; s<nvtxs; s++)
578  for (ii=0; ii<loopend; ii++)
579  //kDist[s][to] = temp_q - 2*kDist[s][to]/sum[to];
580  kDist[ii][to] = temp_q - 2*kDist[ii][to]/sum[to];
581  }
582  }
583  fidx = samin(actual_length, accum_change);
584  if (accum_change[fidx] < -epsilon * obj){
585  for (i= fidx+1; i<=actual_length; i++)
586  where[chain[i-1].point] = chain[i-1].from;
587  moves = fidx;
588  change = accum_change[fidx];
589  }
590  else{
591  for (i= 0; i<actual_length; i++)
592  where[chain[i].point] = chain[i].from;
593  moves = 0;
594  change = 0;
595  }
596 
597  free(sum); free(squared_sum);free(accum_change); free(chain); free(mark);
598 
599  //for (i= 0; i<nvtxs; i++)
600  for (i= 0; i<loopend; i++)
601  free(kDist[i]);
602  free(kDist);
603 
604  return moves;
605 }
606 
607 
608 float onePoint_move(GraphType *graph, int nparts, idxtype *sum, idxtype *squared_sum, idxtype *w, idxtype *self_sim, int **linearTerm, int ii){
609 
610  int k, j, s, i, nbnd, temp, q1, q2, minchange_id, new_squared_sum1, new_squared_sum2, me, nedges, nvtxs, loopend;
611  float tempchange, minchange, obj, cut;
612  idxtype *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
613 
614  nedges = graph->nedges;
615  nvtxs = graph->nvtxs;
616  xadj = graph->xadj;
617  adjncy = graph->adjncy;
618  adjwgt = graph->adjwgt;
619  where = graph->where;
620  nbnd = graph->nbnd;
621  bndind = graph->bndind;
622  bndptr = graph->bndptr;
623 
624  if (boundary_points == 1)
625  {
626  s = bndind[ii];
627  loopend = nbnd;
628  }
629  else
630  {
631  s = ii;
632  loopend = nvtxs;
633  }
634  me= where[s];
635  minchange_id = me;
636  minchange = 0;
637  new_squared_sum1= new_squared_sum2= squared_sum[me];
638 
639  if (sum[me] > w[s]){ // if this cluster where j belongs is not a singleton
640  float inv_sum1 = 1.0/sum[me], inv_sum2 = 1.0/(sum[me]-w[s]);
641 
642  for(k= 0; k<me; k++){
643  q1 = squared_sum[me] - linearTerm[ii][me]*2 + self_sim[ii];
644  q2 = squared_sum[k] + linearTerm[ii][k] *2 - self_sim[ii];
645  if(sum[k] >0)
646  tempchange = squared_sum[me]*inv_sum1 + squared_sum[k]*1.0/sum[k] - q1*inv_sum2- q2*1.0/(sum[k]+w[s]);
647  else if(w[s]>0) // if sum[k] ==0 but w[s] >0
648  tempchange = squared_sum[me]*inv_sum1 - q1*inv_sum2 - q2*1.0/(sum[k]+w[s]);
649  else // if sum[k] == 0 and w[s] ==0
650  tempchange = squared_sum[me]*inv_sum1 - q1*inv_sum2;
651 
652  if(tempchange < minchange){
653  minchange = tempchange;
654  minchange_id = k;
655  new_squared_sum1 = q1;
656  new_squared_sum2 = q2;
657  }
658  }
659  for(k= me+1; k<nparts; k++){
660  q1 = squared_sum[me] - linearTerm[ii][me]*2 +self_sim[ii];
661  q2 = squared_sum[k] + linearTerm[ii][k]*2 - self_sim[ii];
662  if(sum[k] >0)
663  tempchange = squared_sum[me]*inv_sum1 + squared_sum[k]*1.0/sum[k] - q1*inv_sum2- q2*1.0/(sum[k]+w[s]);
664  else if(w[s]>0) // if sum[k] ==0 but w[s] >0
665  tempchange = squared_sum[me]*inv_sum1 - q1*inv_sum2 - q2*1.0/(sum[k]+w[s]);
666  else // if sum[k] == 0 and w[s] ==0
667  tempchange = squared_sum[me]*inv_sum1 - q1*inv_sum2;
668 
669  if(tempchange < minchange){
670  minchange = tempchange;
671  minchange_id = k;
672  new_squared_sum1 = q1;
673  new_squared_sum2 = q2;
674  }
675  }
676  if (minchange < 0){
677  where[s] = minchange_id;
678  sum[me] -= w[s];
679  sum[minchange_id] += w[s];
680  /*
681  for (ii = 0; ii<nbnd; ii++)
682  for (j = 0; j<nparts; j++)
683  linearTerm[ii][j] = 0;
684  */
685 
686  /* This is what was here before for linear term! */
687 // for (j=xadj[s]; j<xadj[s+1]; j++){
688 // int boundary, adj_temp;
689 // adj_temp = adjncy[j];
690 // boundary = bndptr[adj_temp];
691 // if(boundary >-1) {
692 // //if (where[adj_temp] == me){
693 // //linearTerm[ii][me] -= adjwgt[j];
694 // linearTerm[boundary][me] -= adjwgt[j];
695 // //}
696 // //if (where[adj_temp] == minchange_id){
697 // //linearTerm[ii][minchange_id] += adjwgt[j];
698 // linearTerm[boundary][minchange_id] += adjwgt[j];
699 // //}
700 // }
701 // }
702 
703  /* New hack for linear term----NOT EFFICIENT!!! */
704  for (ii = 0; ii<loopend; ii++)
705  for (j = 0; j<nparts; j++)
706  linearTerm[ii][j] = 0;
707  for (ii =0; ii<loopend; ii++){
708  if(boundary_points == 1)
709  s = bndind[ii];
710  else
711  s = ii;
712  for (j=xadj[s]; j<xadj[s+1]; j++){
713  //kDist[i][where[adjncy[j]]] += 1.0*adjwgt[j]/w[i];
714  linearTerm[ii][where[adjncy[j]]] += adjwgt[j];
715  if (adjncy[j] == s)
716  self_sim[ii] = adjwgt[j];
717  }
718  }
719 
720  /*
721  for (ii =0; ii<nbnd; ii++){
722  i = bndind[ii];
723  for (j=xadj[i]; j<xadj[i+1]; j++)
724  linearTerm[ii][where[adjncy[j]]] += adjwgt[j];
725  }
726  */
727 
728 
729  squared_sum[me] = new_squared_sum1;
730  squared_sum[minchange_id] = new_squared_sum2;
731  }
732  }
733  return minchange;
734 }
735 
736 void move1Point2EmptyCluster(GraphType *graph, int nparts, idxtype *sum, idxtype *squared_sum, idxtype *w, idxtype *self_sim, int **linearTerm, int k){
737  int j, s, ii, nbnd, q1, q2, minchange_id, new_squared_sum1, new_squared_sum2, me, nvtxs, loopend;
738  float tempchange, minchange;
739  idxtype *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
740 
741  nvtxs = graph->nvtxs;
742  xadj = graph->xadj;
743  adjncy = graph->adjncy;
744  adjwgt = graph->adjwgt;
745  where = graph->where;
746  nbnd = graph->nbnd;
747  bndind = graph->bndind;
748  bndptr = graph->bndptr;
749  minchange_id = bndind[0];
750  minchange = FLT_MAX;
751 
752  if(boundary_points == 1)
753  loopend = nbnd;
754  else
755  loopend = nvtxs;
756 
757  for(ii=0; ii<loopend; ii++){
758  if(boundary_points == 1)
759  s = bndind[ii];
760  else
761  s = ii;
762  me= where[s];
763  new_squared_sum1= new_squared_sum2= squared_sum[me];
764 
765  if (sum[me] > w[s]){ // if this cluster where j belongs is not a singleton
766  float inv_sum1 = 1.0/sum[me], inv_sum2 = 1.0/(sum[me]-w[s]);
767 
768  q1 = squared_sum[me] - linearTerm[ii][me]*2 + self_sim[ii];
769  q2 = squared_sum[k] + linearTerm[ii][k] *2 + self_sim[ii];
770  if(w[s]>0) // note that sum[k] ==0; if w[s] >0
771  tempchange = squared_sum[me]*inv_sum1 - q1*inv_sum2 - q2*1.0/(sum[k]+w[s]);
772  else // if sum[k] == 0 and w[s] ==0
773  tempchange = squared_sum[me]*inv_sum1 - q1*inv_sum2;
774 
775  if(tempchange < minchange){
776  minchange = tempchange;
777  minchange_id = s;
778  new_squared_sum1 = q1;
779  new_squared_sum2 = q2;
780  }
781  }
782  }
783 
784  where[minchange_id] = k;
785  sum[me] -= w[minchange_id];
786  sum[k] += w[minchange_id];
787 
788  /* This is what was here before!*/
789 // for (j=xadj[minchange_id]; j<xadj[minchange_id+1]; j++){
790 // int boundary, adj_temp;
791 // adj_temp = adjncy[j];
792 // boundary = bndptr[adj_temp];
793 // if(boundary >-1) {
794 // linearTerm[boundary][me] -= adjwgt[j];
795 // linearTerm[boundary][k] += adjwgt[j];
796 // }
797 // squared_sum[me] = new_squared_sum1;
798 // squared_sum[k] = new_squared_sum2;
799 // }
800 
801  /* New hack---NOT EFFICIENT!!!! */
802  for (ii = 0; ii<loopend; ii++)
803  for (j = 0; j<nparts; j++)
804  linearTerm[ii][j] = 0;
805  for (ii =0; ii<loopend; ii++){
806  if(boundary_points == 1)
807  s = bndind[ii];
808  else
809  s = ii;
810  for (j=xadj[s]; j<xadj[s+1]; j++){
811  //kDist[i][where[adjncy[j]]] += 1.0*adjwgt[j]/w[i];
812  linearTerm[ii][where[adjncy[j]]] += adjwgt[j];
813  if (adjncy[j] == s)
814  self_sim[ii] = adjwgt[j];
815  }
816  }
817 }
818 
819 /*
820 int local_search(CtrlType *ctrl, GraphType *graph, int nparts, int chain_length, idxtype *w, float *tpwgts, float ubfactor)
821  //return # of points moved
822 {
823  int nvtxs, nedges, nbnd, me, i, j, k, s, ii;
824  idxtype *sum, *squared_sum, *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind, *self_sim;
825  float change, obj, epsilon, accum_change, minchange;
826  int moves, loopTimes, **linearTerm, loopend;
827 
828  nedges = graph->nedges;
829  nvtxs = graph->nvtxs;
830  xadj = graph->xadj;
831  adjncy = graph->adjncy;
832  adjwgt = graph->adjwgt;
833  where = graph->where;
834  nbnd = graph->nbnd;
835  bndind = graph->bndind;
836  bndptr = graph->bndptr;
837  if(boundary_points == 1)
838  loopend = nbnd;
839  else
840  loopend = nvtxs;
841 
842  sum = idxsmalloc(nparts,0, "Local_search: weight sum");
843  squared_sum = idxsmalloc(nparts,0,"Local_search: weight squared sum");
844  self_sim = idxsmalloc(loopend, 0, "Local_search: self similarity");
845  linearTerm = i2malloc(loopend, nparts, "Local_search: linear term");
846 
847  moves = 0;
848  epsilon =.00001;
849 
850  for (i=0; i<nvtxs; i++)
851  sum[where[i]] += w[i];
852  for (i=0; i<nvtxs; i++){
853  me = where[i];
854  for (j=xadj[i]; j<xadj[i+1]; j++)
855  if (where[adjncy[j]] == me)
856  squared_sum[me] += adjwgt[j];
857  }
858 
859  for (ii = 0; ii<loopend; ii++)
860  for (j = 0; j<nparts; j++)
861  linearTerm[ii][j] = 0;
862  for (ii =0; ii<loopend; ii++){
863  if(boundary_points == 1)
864  s = bndind[ii];
865  else
866  s = ii;
867  for (j=xadj[s]; j<xadj[s+1]; j++){
868  //kDist[i][where[adjncy[j]]] += 1.0*adjwgt[j]/w[i];
869  linearTerm[ii][where[adjncy[j]]] += adjwgt[j];
870  if (adjncy[j] == s)
871  self_sim[ii] = adjwgt[j];
872  }
873  }
874 
875  //the diagonal entries won't affect the result so diagonal's assumed zero
876  obj = 0;
877  for (i=0; i<nparts; i++)
878  if (sum[i] >0)
879  obj += squared_sum[i]*1.0/sum[i];
880 
881  srand(time(NULL));
882  //temperature = DEFAULT_TEMP;
883  loopTimes = 0;
884 
885  while (loopTimes < chain_length){
886  accum_change =0;
887  //for (j=0; j<nvtxs; j++){
888  for (ii=0; ii<loopend; ii++){
889  minchange = onePoint_move(graph, nparts, sum, squared_sum, w, self_sim, linearTerm, ii);
890  accum_change += minchange;
891  }
892  //printf("Accum change = %6.6f\n", accum_change);
893  if (accum_change > -epsilon * obj){
894  break;
895  }
896  moves ++;
897  loopTimes ++;
898  }
899 
900  free(sum); free(squared_sum); free(self_sim);
901 
902  //for (i= 0; i<nvtxs; i++)
903  for (i= 0; i<loopend; i++)
904  free(linearTerm[i]);
905  free(linearTerm);
906 
907  //printf("moves = %d\n", moves);
908  return moves;
909 }
910 */
911 
912 void remove_empty_clusters_l1(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor){
913  int *clustersize=imalloc(nparts, "remove_empty_clusters: clusterSize");
914  int number_of_empty_cluster=0, i, s;
915 
916  for(i=0; i<nparts; i++)
917  clustersize[i] =0;
918  clusterSize(graph, clustersize);
919  for(i=0; i<nparts; i++)
920  if(clustersize[i] ==0)
921  number_of_empty_cluster ++;
922 
923  if(number_of_empty_cluster>0)
924  local_search(ctrl, graph, nparts, 1, w, tpwgts, ubfactor);
925 
926  free(clustersize);
927 }
928 
929 void remove_empty_clusters_l2(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor){
930  int *clustersize=imalloc(nparts, "remove_empty_clusters: clusterSize");
931  int number_of_empty_cluster=0, i, s, loopend;
932 
933  for(i=0; i<nparts; i++)
934  clustersize[i] =0;
935  clusterSize(graph, clustersize);
936  for(i=0; i<nparts; i++)
937  if(clustersize[i] ==0)
938  number_of_empty_cluster ++;
939  //printf("%d empty clusters; ", number_of_empty_cluster);
940 
941  if(number_of_empty_cluster>0){
942  int nvtxs, me, j, k, ii;
943  idxtype *sum, *squared_sum, *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind, *self_sim, nbnd;
944  int **linearTerm;
945 
946  nvtxs = graph->nvtxs;
947  xadj = graph->xadj;
948  adjncy = graph->adjncy;
949  adjwgt = graph->adjwgt;
950  where = graph->where;
951  nbnd = graph->nbnd;
952  bndind = graph->bndind;
953  bndptr = graph->bndptr;
954 
955  if(boundary_points == 1)
956  loopend = nbnd;
957  else
958  loopend = nvtxs;
959 
960  sum = idxsmalloc(nparts,0, "Local_search: weight sum");
961  squared_sum = idxsmalloc(nparts,0,"Local_search: weight squared sum");
962  self_sim = idxsmalloc(loopend, 0, "Local_search: self similarity");
963  linearTerm = i2malloc(loopend, nparts, "Local_search: linear term");
964 
965  for (i=0; i<nvtxs; i++)
966  sum[where[i]] += w[i];
967  for (i=0; i<nvtxs; i++){
968  me = where[i];
969  for (j=xadj[i]; j<xadj[i+1]; j++)
970  if (where[adjncy[j]] == me)
971  squared_sum[me] += adjwgt[j];
972  }
973 
974  for (ii = 0; ii<loopend; ii++)
975  for (j = 0; j<nparts; j++)
976  linearTerm[ii][j] = 0;
977  for (ii =0; ii<loopend; ii++){
978  if (boundary_points == 1)
979  s = bndind[ii];
980  else
981  s = ii;
982  for (j=xadj[s]; j<xadj[s+1]; j++){
983  linearTerm[ii][where[adjncy[j]]] += adjwgt[j];
984  if (adjncy[j] == s)
985  self_sim[ii] = adjwgt[j];
986  }
987  }
988  for(k=0; k<nparts; k++)
989  if(clustersize[k] ==0){
990  move1Point2EmptyCluster(graph, nparts, sum, squared_sum, w, self_sim, linearTerm, k);
991  }
992  free(sum); free(squared_sum); free(self_sim);
993 
994  //for (i= 0; i<nvtxs; i++)
995  for (i= 0; i<loopend; i++)
996  free(linearTerm[i]);
997  free(linearTerm);
998  }
999  /*
1000  for(i=0; i<nparts; i++)
1001  clustersize[i] =0;
1002  number_of_empty_cluster=0;
1003  clusterSize(graph, clustersize);
1004  for(i=0; i<nparts; i++)
1005  if(clustersize[i] ==0)
1006  number_of_empty_cluster ++;
1007  printf("%d empty clusters\n", number_of_empty_cluster);
1008  */
1009  free(clustersize);
1010 }
1011 
1012 void MLKKMRefine(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, int chain_length, float *tpwgts, float ubfactor)
1013 {
1014  int i, nlevels, mustfree=0, temp_cl;
1015  GraphType *ptr;
1016 
1017  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
1018 
1019  /* Compute the parameters of the coarsest graph */
1020  ComputeKWayPartitionParams(ctrl, graph, nparts);
1021  temp_cl = chain_length;
1022 
1023  /* Determine how many levels are there */
1024  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
1025  //printf("Number of levels is %d\n", nlevels);
1026 
1027  for (i=0; ;i++) {
1028  timer tmr;
1029  float result;
1030 
1031  cleartimer(tmr);
1032  starttimer(tmr);
1033 
1034  //pingpong(ctrl, graph, nparts, chain_length, tpwgts, ubfactor);
1035  //chain_length /= 1.5;
1036  //printf("Level: %d\n", i+1);
1037 
1038  if (graph == orggraph){
1039  //chain_length = chain_length>0 ? chain_length : 1;
1040  pingpong(ctrl, graph, nparts, chain_length, tpwgts, ubfactor, 1);
1041  break;
1042  }
1043  else{
1044  //pingpong(ctrl, graph, nparts, 0, tpwgts, ubfactor, 0);
1045  pingpong(ctrl, graph, nparts, chain_length, tpwgts, ubfactor, 0);
1046  //chain_length /= 2;
1047  }
1048 
1049 
1050  //pingpong(ctrl, graph, nparts, chain_length, tpwgts, ubfactor);
1051 
1052  // /* for time and quality each level
1053 
1054  stoptimer(tmr);
1055  //printf("Level %d: %7.3f", i+1, tmr);
1056  if (cutType == NCUT){
1057  result = ComputeNCut(graph, graph->where, nparts);
1058  //printf(" %7f", result);
1059  }
1060  else{
1061  result = ComputeRAsso(graph, graph->where, nparts);
1062  //printf(" %7f", result);
1063  }
1064  //printf(" (%d)\n\n", graph->nvtxs);
1065  //ends here*/
1066 
1067  if (graph == orggraph)
1068  break;
1069  /*
1070  if(i>1)
1071  chain_length /= 10;
1072  */
1073 
1074  GKfree((void **) &graph->gdata, LTERM); /* Deallocate the graph related arrays */
1075  graph = graph->finer;
1076  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
1077  if (graph->vwgt == NULL) {
1078  graph->vwgt = idxsmalloc(graph->nvtxs, 1, "RefineKWay: graph->vwgt");
1079  graph->adjwgt = idxsmalloc(graph->nedges, 1, "RefineKWay: graph->adjwgt");
1080  mustfree = 1;
1081  }
1082  ProjectKWayPartition(ctrl, graph, nparts);
1083  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
1084  }
1085 
1086  if (mustfree)
1087  GKfree((void **) &graph->vwgt, (void **) &graph->adjwgt, LTERM);
1088 
1089  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
1090 }
NULL
#define NULL
Definition: UVUnwrapping.cpp:40
result
core::Tensor result
Definition: VtkUtils.cpp:76
ComputeRAsso
float ComputeRAsso(GraphType *graph, idxtype *where, int npart)
Definition: debug.c:20
ComputeNCut
float ComputeNCut(GraphType *graph, idxtype *where, int npart)
Definition: debug.c:67
RCUT
#define RCUT
Definition: defs.h:38
NCUT
#define NCUT
Definition: defs.h:36
MAXITERATIONS
#define MAXITERATIONS
Definition: defs.h:42
LTERM
#define LTERM
Definition: defs.h:23
RASSO
#define RASSO
Definition: defs.h:37
DBG_TIME
#define DBG_TIME
Definition: defs.h:174
dist
static double dist(double x1, double y1, double x2, double y2)
Definition: lsd.c:207
stoptimer
#define stoptimer(tmr)
Definition: macros.h:49
cleartimer
#define cleartimer(tmr)
Definition: macros.h:47
IFSET
#define IFSET(a, flag, cmd)
Definition: macros.h:56
starttimer
#define starttimer(tmr)
Definition: macros.h:48
chainmalloc
Chains * chainmalloc(int n, char *msg)
Definition: util.c:121
i2malloc
int ** i2malloc(int, int, char *)
Definition: util.c:148
clusterSize
void clusterSize(GraphType *graph, int *clustersize)
Definition: util.c:33
f2malloc
float ** f2malloc(int n, int m, char *msg)
Definition: util.c:132
idxsmalloc
#define idxsmalloc
Definition: rename.h:386
GKfree
#define GKfree
Definition: rename.h:380
ComputeKWayPartitionParams
#define ComputeKWayPartitionParams
Definition: rename.h:108
fmalloc
#define fmalloc
Definition: rename.h:384
samin
#define samin
Definition: rename.h:398
idxmalloc
#define idxmalloc
Definition: rename.h:383
ProjectKWayPartition
#define ProjectKWayPartition
Definition: rename.h:109
imalloc
#define imalloc
Definition: rename.h:382
ismalloc
#define ismalloc
Definition: rename.h:385
ChainType::point
int point
Definition: struct.h:25
ChainType::from
int from
Definition: struct.h:26
ChainType::change
float change
Definition: struct.h:28
ChainType::to
int to
Definition: struct.h:27
idxtype
int idxtype
Definition: struct.h:17
timer
double timer
Definition: struct.h:215
controldef::dbglvl
int dbglvl
Definition: struct.h:224
controldef::ProjectTmr
timer ProjectTmr
Definition: struct.h:239
controldef::UncoarsenTmr
timer UncoarsenTmr
Definition: struct.h:238
graphdef::nbnd
int nbnd
Definition: struct.h:184
graphdef::adjncy
idxtype * adjncy
Definition: struct.h:172
graphdef::bndind
idxtype * bndind
Definition: struct.h:185
graphdef::where
idxtype * where
Definition: struct.h:183
graphdef::nvtxs
int nvtxs
Definition: struct.h:168
graphdef::gdata
idxtype * gdata
Definition: struct.h:164
graphdef::vwgt
idxtype * vwgt
Definition: struct.h:170
graphdef::finer
struct graphdef * finer
Definition: struct.h:205
graphdef::nedges
int nedges
Definition: struct.h:168
graphdef::adjwgt
idxtype * adjwgt
Definition: struct.h:173
graphdef::bndptr
idxtype * bndptr
Definition: struct.h:185
graphdef::xadj
idxtype * xadj
Definition: struct.h:169
point
Definition: lsd.c:149
local_search
int local_search(CtrlType *ctrl, GraphType *graph, int nparts, int chain_length, idxtype *w, float *tpwgts, float ubfactor)
Definition: wkkm.c:409
memory_saving
int memory_saving
Definition: wkkm.c:17
boundary_points
int boundary_points
Definition: wkkm.c:17
move1Point2EmptyCluster
void move1Point2EmptyCluster(GraphType *graph, int nparts, idxtype *sum, idxtype *squared_sum, idxtype *w, idxtype *self_sim, int **linearTerm, int k)
Definition: wkkm.c:736
Weighted_kernel_k_means
void Weighted_kernel_k_means(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor)
Definition: wkkm.c:183
Compute_Weights
void Compute_Weights(CtrlType *ctrl, GraphType *graph, idxtype *w)
Definition: wkkm.c:19
remove_empty_clusters_l2
void remove_empty_clusters_l2(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor)
Definition: wkkm.c:929
onePoint_move
float onePoint_move(GraphType *graph, int nparts, idxtype *sum, idxtype *squared_sum, idxtype *w, idxtype *self_sim, int **linearTerm, int ii)
Definition: wkkm.c:608
remove_empty_clusters_l1
void remove_empty_clusters_l1(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor)
Definition: wkkm.c:912
transform_matrix
void transform_matrix(CtrlType *ctrl, GraphType *graph, idxtype *w, float *m_adjwgt)
Definition: wkkm.c:43
pingpong
void pingpong(CtrlType *ctrl, GraphType *graph, int nparts, int chain_length, float *tpwgts, float ubfactor, int toplevel)
Definition: wkkm.c:138
cutType
int cutType
Definition: metis.c:3
MLKKMRefine
void MLKKMRefine(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, int chain_length, float *tpwgts, float ubfactor)
Definition: wkkm.c:1012
transform_matrix_half
void transform_matrix_half(CtrlType *ctrl, GraphType *graph, idxtype *w, float *m_adjwgt)
Definition: wkkm.c:90