Graphviz 13.1.3~dev.20250831.0023
Loading...
Searching...
No Matches
mq.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11/* Modularity Quality definition:
12
13 We assume undirected graph. Directed graph should be converted by summing edge weights.
14
15 Given a partition P of V into k clusters.
16
17 Let E(i,j) be the set of edges between cluster i and j.
18 Let |E(i,j)| be the sum of edge weights of edges in E(i,j).
19
20 Let E(i,i) be the set of edges within cluster i, but excluding self-edges.
21 Let |E(i,i)| be the sum of edge weights of edges in E(i,i).
22
23 Let V(i) be the sets of vertices in i
24
25 The intra-cluster edges concentration for a cluster i is
26 (the denominator could be |V(i)|*(|V(i)-1)/2 strictly speaking as we exclude self-edges):
27
28 |E(i,i)|
29 -----------
30 (|V(i)|^2/2)
31
32 The inter-cluster edges concentration between cluster i and j is
33
34 |E(i,j)|
35 ------------
36 |V(i)|*|V(j)|
37
38 So the cluster index is defined as the average intra cluster edge concentration, minus
39 the inter-cluster edge concentration:
40
41 . |E(i,i)| |E(i,j)|
42 MQ(P) = (1/k) * \sum_{i=1...k} ------------ - (1/(k*(k-1)/2)) * \sum_{i<j} ------------------- = mq_in/k - mq_out/(k*(k-1)/2)
43 . (|V(i)|^2/2) |V(i)|*|V(j)|
44
45 or
46
47 . |E(i,i)| |E(i,j)|
48 MQ(P)/2 = (1/k) * \sum_{i=1...k} ------------ - (1/(k*(k-1))) * \sum_{i<j} ------------------ = mq_in/k - mq_out/(k*(k-1))
49 . |V(i)|^2 |V(i)|*|V(j)|
50
51 Notice that if we assume the graph is unweights (edge weights = 1), then 0<= MQ <= 1.
52 For weighted graph, MQ may not be within 0 to 1. We could normalized it, but
53 for comparing clustering quality of the same graph but different partitioning, this
54 unnormalized quantity is not a problem.
55
56*/
57
58#define STANDALONE
59#include <limits.h>
60#include <sparse/general.h>
61#include <sparse/SparseMatrix.h>
62#include <sparse/mq.h>
63#include <stdbool.h>
64#include <string.h>
65#include <util/alloc.h>
66#include <util/list.h>
67
68static double get_mq(SparseMatrix A, int *assignment, int *ncluster0, double *mq_in0, double *mq_out0, double **dout0){
69 /* given a symmetric matrix representation of a graph and an assignment of nodes into clusters, calculate the modularity quality.
70 assignment: assignment[i] gives the cluster assignment of node i. 0 <= assignment[i] < ncluster.
71 ncluster: number of clusters
72 mq_in: the part of MQ to do with intra-cluster edges, before divide by 1/k
73 mq_out: the part of MQ to do with inter-cluster edges, before divide by 1/(k*(k-1))
74 mq = 2*(mq_in/k - mq_out/(k*(k-1)));
75 */
76 int ncluster = 0;
77 int n = A->m;
78 bool test_pattern_symmetry_only = false;
79 int *counts, *ia = A->ia, *ja = A->ja, k, i, j, jj;
80 double mq_in = 0, mq_out = 0, *a = NULL, Vi, Vj;
81 int c;
82 double *dout;
83
84
85 assert(SparseMatrix_is_symmetric(A, test_pattern_symmetry_only));
86 (void)test_pattern_symmetry_only;
87 assert(A->n == n);
88 if (A->type == MATRIX_TYPE_REAL) a = A->a;
89
90 counts = gv_calloc(n, sizeof(int));
91
92 for (i = 0; i < n; i++){
93 assert(assignment[i] >= 0 && assignment[i] < n);
94 if (counts[assignment[i]] == 0) ncluster++;
95 counts[assignment[i]]++;
96 }
97 k = ncluster;
98 assert(ncluster <= n);
99
100 for (i = 0; i < n; i++){
101 assert(assignment[i] < ncluster);
102 c = assignment[i];
103 Vi = counts[c];
104 for (j = ia[i] ; j < ia[i+1]; j++){
105 /* ASSUME UNDIRECTED */
106 jj = ja[j];
107 if (jj >= i) continue;
108 assert(assignment[jj] < ncluster);
109 Vj = counts[assignment[jj]];
110 if (assignment[jj] == c){
111 if (a) {
112 mq_in += a[j]/(Vi*Vi);
113 } else {
114 mq_in += 1./(Vi*Vi);
115 }
116 } else {
117 if (a) {
118 mq_out += a[j]/(Vi*Vj);
119 } else {
120 mq_out += 1./(Vi*Vj);
121 }
122 }
123
124 }
125 }
126
127 /* calculate scaled out degree */
128 dout = gv_calloc(n, sizeof(double));
129 for (i = 0; i < n; i++){
130 for (j = ia[i]; j < ia[i+1]; j++){
131 jj = ja[j];
132 if (jj == i) continue;
133 if (a){
134 dout[i] += a[j]/(double) counts[assignment[jj]];
135 } else {
136 dout[i] += 1./(double) counts[assignment[jj]];
137 }
138 }
139 }
140
141 *ncluster0 = k;
142 *mq_in0 = mq_in;
143 *mq_out0 = mq_out;
144 *dout0 = dout;
145 free(counts);
146
147 if (k > 1){
148 return 2*(mq_in/k - mq_out/(k*(k-1)));
149 } else {
150 return 2*mq_in;
151 }
152}
153
156 int n = A->n, i;
157 int *matching;
158
159 assert(A->type == MATRIX_TYPE_REAL);
160 assert(SparseMatrix_is_symmetric(A, false));
161
162 if (!A) return NULL;
163 assert(A->m == n);
165 grid->level = level;
166 grid->n = n;
167 grid->A = A;
168 grid->P = NULL;
169 grid->next = NULL;
170 grid->prev = NULL;
171 grid->delete_top_level_A = false;
172 matching = grid->matching = gv_calloc(n, sizeof(double));
173 grid->deg_intra = NULL;
174 grid->dout = NULL;
175 grid->wgt = NULL;
176
177 if (level == 0){
178 double mq = 0, mq_in, mq_out;
179 int ncluster;
180 double *deg_intra, *wgt, *dout;
181
182 grid->deg_intra = gv_calloc(n, sizeof(double));
183 deg_intra = grid->deg_intra;
184
185 grid->wgt = gv_calloc(n, sizeof(double));
186 wgt = grid->wgt;
187
188 for (i = 0; i < n; i++){
189 deg_intra[i] = 0;
190 wgt[i] = 1.;
191 }
192 for (i = 0; i < n; i++) matching[i] = i;
193 mq = get_mq(A, matching, &ncluster, &mq_in, &mq_out, &dout);
194 fprintf(stderr,"ncluster = %d, mq = %f\n", ncluster, mq);
195 grid->mq = mq;
196 grid->mq_in = mq_in;
197 grid->mq_out = mq_out;
198 grid->dout = dout;
199 grid->ncluster = ncluster;
200
201 }
202
203
204 return grid;
205}
206
208 if (!grid) return;
209 if (grid->A){
210 if (grid->level == 0) {
211 if (grid->delete_top_level_A) SparseMatrix_delete(grid->A);
212 } else {
214 }
215 }
217 free(grid->matching);
218 free(grid->deg_intra);
219 free(grid->dout);
220 free(grid->wgt);
222 free(grid);
223}
224
226 int *matching = grid->matching;
227 SparseMatrix A = grid->A;
228 int n = grid->n, level = grid->level, nc = 0, nclusters = n;
229 double mq = 0, mq_in = 0, mq_out = 0, mq_new, mq_in_new, mq_out_new, mq_max = 0, mq_in_max = 0, mq_out_max = 0;
230 int *ia = A->ia, *ja = A->ja;
231 double amax = 0;
232 double *deg_intra = grid->deg_intra, *wgt = grid->wgt;
233 int i, j, k, jj, jc, jmax;
234 double gain = 0, *dout = grid->dout, deg_in_i, deg_in_j, wgt_i, wgt_j, a_ij, dout_i, dout_j, dout_max = 0, wgt_jmax = 0;
235 double maxgain = 0;
236 double total_gain = 0;
237
238 LIST(int) *neighbors = gv_calloc(n, sizeof(neighbors[0]));
239
240 mq = grid->mq;
241 mq_in = grid->mq_in;
242 mq_out = grid->mq_out;
243
244 double *deg_intra_new = gv_calloc(n, sizeof(double));
245 double *wgt_new = gv_calloc(n, sizeof(double));
246 double *deg_inter = gv_calloc(n, sizeof(double));
247 int *mask = gv_calloc(n, sizeof(int));
248 double *dout_new = gv_calloc(n, sizeof(double));
249 for (i = 0; i < n; i++) mask[i] = -1;
250
251 assert(n == A->n);
252 for (i = 0; i < n; i++) matching[i] = UNMATCHED;
253
254 /* gain in merging node A into cluster B is
255 mq_in_new = mq_in - |E(A,A)|/(V(A))^2 - |E(B,B)|/(V(B))^2 + (|E(A,A)|+|E(B,B)|+|E(A,B)|)/(|V(A)|+|V(B)|)^2
256 . = mq_in - deg_intra(A)/|A|^2 - deg_intra(B)/|B|^2 + (deg_intra(A)+deg_intra(B)+a(A,B))/(|A|+|B|)^2
257
258 mq_out_new = mq_out - |E(A,B)|/(|V(A)|*V(B)|)-\sum_{C and A connected, C!=B} |E(A,C)|/(|V(A)|*|V(C)|)-\sum_{C and B connected,C!=B} |E(B,C)|/(|V(B)|*|V(C)|)
259 . + \sum_{C connected to A or B, C!=A, C!=B} (|E(A,C)|+|E(B,C)|)/(|V(C)|*(|V(A)|+|V(B)|)
260 . = mq_out + a(A,B)/(|A|*|B|)-\sum_{C and A connected} a(A,C)/(|A|*|C|)-\sum_{C and B connected} a(B,C)/(|B|*|C|)
261 . + \sum_{C connected to A or B, C!=A, C!=B} (a(A,C)+a(B,C))/(|C|*(|A|+|B|))
262 Denote:
263 dout(i) = \sum_{j -- i} a(i,j)/|j|
264 then
265
266 mq_out_new = mq_out - |E(A,B)|/(|V(A)|*V(B)|)-\sum_{C and A connected, C!=B} |E(A,C)|/(|V(A)|*|V(C)|)-\sum_{C and B connected,C!=B} |E(B,C)|/(|V(B)|*|V(C)|)
267 . + \sum_{C connected to A or B, C!=A, C!=B} (|E(A,C)|+|E(B,C)|)/(|V(C)|*(|V(A)|+|V(B)|)
268 . = mq_out + a(A,B)/(|A|*|B|)-dout(A)/|A| - dout(B)/|B|
269 . + (dout(A)+dout(B))/(|A|+|B|) - (a(A,B)/|A|+a(A,B)/|B|)/(|A|+|B|)
270 . = mq_out -dout(A)/|A| - dout(B)/|B| + (dout(A)+dout(B))/(|A|+|B|)
271 after merging A and B into cluster AB,
272 dout(AB) = dout(A) + dout(B);
273 dout(C) := dout(C) - a(A,C)/|A| - a(B,C)/|B| + a(A,C)/(|A|+|B|) + a(B, C)/(|A|+|B|)
274
275 mq_new = mq_in_new/(k-1) - mq_out_new/((k-1)*(k-2))
276 gain = mq_new - mq
277 */
278 double *a = A->a;
279 for (i = 0; i < n; i++){
280 if (matching[i] != UNMATCHED) continue;
281 /* accumulate connections between i and clusters */
282 for (j = ia[i]; j < ia[i+1]; j++){
283 jj = ja[j];
284 if (jj == i) continue;
285 if ((jc=matching[jj]) != UNMATCHED){
286 if (mask[jc] != i) {
287 mask[jc] = i;
288 deg_inter[jc] = a[j];
289 } else {
290 deg_inter[jc] += a[j];
291 }
292 }
293 }
294 deg_in_i = deg_intra[i];
295 wgt_i = wgt[i];
296 dout_i = dout[i];
297
298 maxgain = 0;
299 jmax = -1;
300 for (j = ia[i]; j < ia[i+1]; j++){
301 jj = ja[j];
302 if (jj == i) continue;
303 jc = matching[jj];
304 if (jc == UNMATCHED){
305 a_ij = a[j];
306 wgt_j = wgt[jj];
307 deg_in_j = deg_intra[jj];
308 dout_j = dout[jj];
309 } else if (deg_inter[jc] < 0){
310 continue;
311 } else {
312 a_ij = deg_inter[jc];
313 wgt_j = wgt_new[jc];
314 deg_inter[jc] = -1; // so that we do not redo the calculation when we hit another neighbor in cluster jc
315 deg_in_j = deg_intra_new[jc];
316 dout_j = dout_new[jc];
317 }
318
319 mq_in_new = mq_in - deg_in_i/pow(wgt_i, 2) - deg_in_j/pow(wgt_j,2)
320 + (deg_in_i + deg_in_j + a_ij)/pow(wgt_i + wgt_j,2);
321
322 mq_out_new = mq_out - dout_i/wgt_i - dout_j/wgt_j + (dout_i + dout_j)/(wgt_i + wgt_j);
323
324 if (nclusters > 2){
325 mq_new = 2*(mq_in_new/(nclusters - 1) - mq_out_new/((nclusters - 1)*(nclusters - 2)));
326 } else {
327 mq_new = 2*mq_in_new/(nclusters - 1);
328 }
329
330#ifdef DEBUG
331 {int ncluster;
332 double mq2, mq_in2, mq_out2, *dout2;
333 int nc2 = nc;
334 int *matching2 = gv_calloc(A->m, sizeof(int));
335 memcpy(matching2, matching, sizeof(double)*A->m);
336 if (jc != UNMATCHED) {
337 matching2[i] = jc;
338 } else {
339 matching2[i] = nc2;
340 matching2[jj] = nc2;
341 nc2++;
342 }
343 for (k = 0; k < n; k++) if (matching2[k] == UNMATCHED) matching2[k] =nc2++;
344 mq2 = get_mq(A, matching2, &ncluster, &mq_in2, &mq_out2, &dout2);
345 fprintf(stderr," {dout_i, dout_j}={%f,%f}, {predicted, calculated}: mq = {%f, %f}, mq_in ={%f,%f}, mq_out = {%f,%f}\n",dout_i, dout_j, mq_new, mq2, mq_in_new, mq_in2, mq_out_new, mq_out2);
346
347 mq_new = mq2;
348
349 }
350#endif
351
352 gain = mq_new - mq;
353 if (Verbose) fprintf(stderr,"gain in merging node %d with node %d = %f-%f = %f\n", i, jj, mq, mq_new, gain);
354 if (j == ia[i] || gain > maxgain){
355 maxgain = gain;
356 jmax = jj;
357 amax = a_ij;
358 dout_max = dout_j;
359 wgt_jmax = wgt_j;
360 mq_max = mq_new;
361 mq_in_max = mq_in_new;
362 mq_out_max = mq_out_new;
363 }
364
365 }
366
367 /* now merge i and jmax */
368 if (maxgain > 0 || (nc >= 1 && nc > maxcluster)){
369 total_gain += maxgain;
370 jc = matching[jmax];
371 if (jc == UNMATCHED){
372 fprintf(stderr, "maxgain=%f, merge %d, %d\n",maxgain, i, jmax);
373 LIST_APPEND(&neighbors[nc], jmax);
374 LIST_APPEND(&neighbors[nc], i);
375 dout_new[nc] = dout_i + dout_max;
376 matching[i] = matching[jmax] = nc;
377 wgt_new[nc] = wgt[i] + wgt[jmax];
378 deg_intra_new[nc] = deg_intra[i] + deg_intra[jmax] + amax;
379 nc++;
380 } else {
381 fprintf(stderr,"maxgain=%f, merge with existing cluster %d, %d\n",maxgain, i, jc);
382 LIST_APPEND(&neighbors[jc], i);
383 dout_new[jc] = dout_i + dout_max;
384 wgt_new[jc] += wgt[i];
385 matching[i] = jc;
386 deg_intra_new[jc] += deg_intra[i] + amax;
387 }
388 mq = mq_max;
389 mq_in = mq_in_max;
390 mq_out = mq_out_max;
391 nclusters--;
392 } else {
393 fprintf(stderr,"gain: %f -- no gain, skip merging node %d\n", maxgain, i);
394 assert(maxgain <= 0);
395 LIST_APPEND(&neighbors[nc], i);
396 matching[i] = nc;
397 deg_intra_new[nc] = deg_intra[i];
398 wgt_new[nc] = wgt[i];
399 nc++;
400 }
401
402
403 /* update scaled outdegree of neighbors of i and its merged node/cluster jmax */
404 jc = matching[i];
405 for (size_t l = LIST_SIZE(&neighbors[jc]) - 1; l != SIZE_MAX; --l) {
406 mask[LIST_GET(&neighbors[jc], l)] = n + i;
407 }
408
409 for (size_t l = LIST_SIZE(&neighbors[jc]) - 1; l != SIZE_MAX; --l) {
410 k = LIST_GET(&neighbors[jc], l);
411 for (j = ia[k]; j < ia[k+1]; j++){
412 jj = ja[j];
413 if (mask[jj] == n+i) continue;/* link to within cluster */
414 if ((jc = matching[jj]) == UNMATCHED){
415 if (k == i){
416 dout[jj] += -a[j]/wgt_i + a[j]/(wgt_i + wgt_jmax);
417 } else {
418 dout[jj] += -a[j]/wgt_jmax + a[j]/(wgt_i + wgt_jmax);
419 }
420 } else {
421 if (k == i){
422 dout_new[jc] += -a[j]/wgt_i + a[j]/(wgt_i + wgt_jmax);
423 } else {
424 dout_new[jc] += -a[j]/wgt_jmax + a[j]/(wgt_i + wgt_jmax);
425 }
426 }
427 }
428 }
429
430 }
431
432 fprintf(stderr,"verbose=%d\n",Verbose);
433 if (Verbose) fprintf(stderr,"mq = %f new mq = %f level = %d, n = %d, nc = %d, gain = %g, mq_in = %f, mq_out = %f\n", mq, mq + total_gain,
434 level, n, nc, total_gain, mq_in, mq_out);
435
436#ifdef DEBUG
437 {int ncluster;
438
439 mq = get_mq(A, matching, &ncluster, &mq_in, &mq_out, &dout);
440 fprintf(stderr," mq = %f\n",mq);
441
442 }
443#endif
444
445 if (nc >= 1 && (total_gain > 0 || nc < n)){
446 /* now set up restriction and prolongation operator */
447 SparseMatrix P, R, R0, B, cA;
448 double one = 1.;
450
452 for (i = 0; i < n; i++){
453 jj = matching[i];
455 }
461 if (!B) {
462 free(deg_intra_new);
463 free(wgt_new);
464 free(dout_new);
465 goto RETURN;
466 }
467 cA = SparseMatrix_multiply(B, P);
469 if (!cA) {
470 free(deg_intra_new);
471 free(wgt_new);
472 free(dout_new);
473 goto RETURN;
474 }
475 grid->P = P;
476 level++;
477 cgrid = Multilevel_MQ_Clustering_init(cA, level);
478 deg_intra_new = gv_recalloc(deg_intra_new, n, nc, sizeof(double));
479 wgt_new = gv_recalloc(wgt_new, n, nc, sizeof(double));
480 cgrid->deg_intra = deg_intra_new;
481 cgrid->mq = grid->mq + total_gain;
482 cgrid->wgt = wgt_new;
483 dout_new = gv_recalloc(dout_new, n, nc, sizeof(double));
484 cgrid->dout = dout_new;
485
486 cgrid = Multilevel_MQ_Clustering_establish(cgrid, maxcluster);
487
488 grid->next = cgrid;
489 cgrid->prev = grid;
490 } else {
491 /* no more improvement, stop and final clustering found */
492 for (i = 0; i < n; i++) matching[i] = i;
493
494 free(deg_intra_new);
495 free(wgt_new);
496 free(dout_new);
497 }
498
499 RETURN:
500 for (i = 0; i < n; i++) LIST_FREE(&neighbors[i]);
501 free(neighbors);
502
503 free(deg_inter);
504 free(mask);
505 return grid;
506}
507
509 /* maxcluster is used to specify the maximum number of cluster desired, e.g., maxcluster=10 means that a maximum of 10 clusters
510 is desired. this may not always be realized, and mq may be low when this is specified. Default: maxcluster = 0 */
512 SparseMatrix A = A0;
513
514 if (maxcluster <= 0) maxcluster = A->m;
515 if (!SparseMatrix_is_symmetric(A, false) || A->type != MATRIX_TYPE_REAL){
517 }
519
521
522 if (A != A0) grid->delete_top_level_A = true; // be sure to clean up later
523 return grid;
524}
525
526
527static void hierachical_mq_clustering(SparseMatrix A, int maxcluster,
528 int *nclusters, int **assignment, double *mq){
529 /* find a clustering of vertices by maximize mq
530 A: symmetric square matrix n x n. If real value, value will be used as edges weights, otherwise edge weights are considered as 1.
531 maxcluster: used to specify the maximum number of cluster desired, e.g., maxcluster=10 means that a maximum of 10 clusters
532 . is desired. this may not always be realized, and mq may be low when this is specified. Default: maxcluster = 0
533 nclusters: on output the number of clusters
534 assignment: dimension n. Node i is assigned to cluster "assignment[i]". 0 <= assignment < nclusters
535 */
536
538 int *matching, i;
539 SparseMatrix P;
540 assert(A->m == A->n);
541
542 *mq = 0.;
543
544 grid = Multilevel_MQ_Clustering_new(A, maxcluster);
545
546 /* find coarsest */
547 cgrid = grid;
548 while (cgrid->next){
549 cgrid = cgrid->next;
550 }
551
552 /* project clustering up */
553 double *u = gv_calloc(cgrid->n, sizeof(double));
554 for (i = 0; i < cgrid->n; i++) u[i] = (double) (cgrid->matching)[i];
555 *nclusters = cgrid->n;
556 *mq = cgrid->mq;
557
558 while (cgrid->prev){
559 double *v = NULL;
560 P = cgrid->prev->P;
562 free(u);
563 u = v;
564 cgrid = cgrid->prev;
565 }
566
567 if (*assignment){
568 matching = *assignment;
569 } else {
570 matching = gv_calloc(grid->n, sizeof(int));
571 *assignment = matching;
572 }
573 for (i = 0; i < grid->n; i++) (matching)[i] = (int) u[i];
574 free(u);
575
577}
578
579
580
581void mq_clustering(SparseMatrix A, int maxcluster,
582 int *nclusters, int **assignment, double *mq){
583 /* find a clustering of vertices by maximize mq
584 A: symmetric square matrix n x n. If real value, value will be used as edges weights, otherwise edge weights are considered as 1.
585 maxcluster: used to specify the maximum number of cluster desired, e.g., maxcluster=10 means that a maximum of 10 clusters
586 . is desired. this may not always be realized, and mq may be low when this is specified. Default: maxcluster = 0
587 nclusters: on output the number of clusters
588 assignment: dimension n. Node i is assigned to cluster "assignment[i]". 0 <= assignment < nclusters
589 */
591
592 assert(A->m == A->n);
593
594 B = SparseMatrix_symmetrize(A, false);
595
596 if (B == A) {
598 }
599
601
603
604 hierachical_mq_clustering(B, maxcluster, nclusters, assignment, mq);
605
606 if (B != A) SparseMatrix_delete(B);
607
608}
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
SparseMatrix SparseMatrix_transpose(SparseMatrix A)
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
SparseMatrix SparseMatrix_coordinate_form_add_entry(SparseMatrix A, int irn, int jcn, const void *val)
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
void SparseMatrix_multiply_vector(SparseMatrix A, double *v, double **res)
SparseMatrix SparseMatrix_multiply(SparseMatrix A, SparseMatrix B)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_copy(SparseMatrix A)
SparseMatrix SparseMatrix_set_entries_to_real_one(SparseMatrix A)
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
@ MATRIX_TYPE_REAL
@ FORMAT_COORD
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define A(n, t)
Definition expr.h:76
@ UNMATCHED
Definition general.h:77
static bool Verbose
Definition gml2gv.c:24
void free(void *)
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:181
@ grid
Definition gvgen.c:33
#define B
Definition hierarchy.c:118
type-generic dynamically expanding list
#define LIST(type)
Definition list.h:55
#define LIST_SIZE(list)
Definition list.h:80
#define LIST_APPEND(list, item)
Definition list.h:132
#define LIST_FREE(list)
Definition list.h:379
#define LIST_GET(list, index)
Definition list.h:165
void mq_clustering(SparseMatrix A, int maxcluster, int *nclusters, int **assignment, double *mq)
Definition mq.c:581
static Multilevel_MQ_Clustering Multilevel_MQ_Clustering_init(SparseMatrix A, int level)
Definition mq.c:154
static void hierachical_mq_clustering(SparseMatrix A, int maxcluster, int *nclusters, int **assignment, double *mq)
Definition mq.c:527
static Multilevel_MQ_Clustering Multilevel_MQ_Clustering_new(SparseMatrix A0, int maxcluster)
Definition mq.c:508
static void Multilevel_MQ_Clustering_delete(Multilevel_MQ_Clustering grid)
Definition mq.c:207
static double get_mq(SparseMatrix A, int *assignment, int *ncluster0, double *mq_in0, double *mq_out0, double **dout0)
Definition mq.c:68
static Multilevel_MQ_Clustering Multilevel_MQ_Clustering_establish(Multilevel_MQ_Clustering grid, int maxcluster)
Definition mq.c:225
#define RETURN(v)
Definition strmatch.c:144
Multilevel_MQ_Clustering prev
Definition mq.h:27
Multilevel_MQ_Clustering next
Definition mq.h:26