Graphviz 13.0.0~dev.20250607.1528
Loading...
Searching...
No Matches
spring_electrical.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#include "config.h"
12#include <sparse/SparseMatrix.h>
14#include <sparse/QuadTree.h>
15#include <sfdpgen/Multilevel.h>
17#include <neatogen/overlap.h>
18#include <common/types.h>
19#include <common/arith.h>
20#include <math.h>
21#include <common/globals.h>
22#include <stdbool.h>
23#include <stddef.h>
24#include <string.h>
25#include <time.h>
26#include <util/agxbuf.h>
27#include <util/alloc.h>
28#include <util/bitarray.h>
29#include <util/list.h>
30
33static const double C = 0.2;
34
36static const int quadtree_size = 45;
37
40static const double bh = 0.6;
41
44static const double tol = 0.001;
45
46static const double cool = 0.90;
47
50 ctrl.p = AUTOP;/*a negativve number default to -1. repulsive force = dist^p */
51 ctrl.random_start = true; // whether to apply SE from a random layout, or from existing layout
52 ctrl.K = -1;/* the natural distance. If K < 0, K will be set to the average distance of an edge */
53 ctrl.multilevels = 0;/* if <=1, single level */
54
55 ctrl.max_qtree_level = 10;/* max level of quadtree */
56 ctrl.maxiter = 500;
57 ctrl.step = 0.1;
58 ctrl.adaptive_cooling = true;
59 ctrl.random_seed = 123;
60 ctrl.beautify_leaves = false;
62 ctrl.overlap = 0;
63 ctrl.do_shrinking = true;
65 ctrl.initial_scaling = -4;
66 ctrl.rotation = 0.;
67 ctrl.edge_labeling_scheme = 0;
68 return ctrl;
69}
70
71static char* smoothings[] = {
72 "NONE", "STRESS_MAJORIZATION_GRAPH_DIST", "STRESS_MAJORIZATION_AVG_DIST", "STRESS_MAJORIZATION_POWER_DIST", "SPRING", "TRIANGLE", "RNG"
73};
74
75static char* tschemes[] = {
76 "NONE", "NORMAL", "FAST", "HYBRID"
77};
78
80 fprintf (stderr, "spring_electrical_control:\n");
81 fprintf (stderr, " repulsive exponent: %.03f\n", ctrl.p);
82 fprintf(stderr, " random start %d seed %d\n", (int)ctrl.random_start,
83 ctrl.random_seed);
84 fprintf (stderr, " K : %.03f C : %.03f\n", ctrl.K, C);
85 fprintf (stderr, " max levels %d\n", ctrl.multilevels);
86 fprintf (stderr, " quadtree size %d max_level %d\n", quadtree_size, ctrl.max_qtree_level);
87 fprintf (stderr, " Barnes-Hutt constant %.03f tolerance %.03f maxiter %d\n", bh, tol, ctrl.maxiter);
88 fprintf(stderr, " cooling %.03f step size %.03f adaptive %d\n", cool,
89 ctrl.step, (int)ctrl.adaptive_cooling);
90 fprintf (stderr, " beautify_leaves %d node weights %d rotation %.03f\n",
91 (int)ctrl.beautify_leaves, 0, ctrl.rotation);
92 fprintf (stderr, " smoothing %s overlap %d initial_scaling %.03f do_shrinking %d\n",
93 smoothings[ctrl.smoothing], ctrl.overlap, ctrl.initial_scaling, (int)ctrl.do_shrinking);
94 fprintf (stderr, " octree scheme %s\n", tschemes[ctrl.tscheme]);
95 fprintf (stderr, " edge_labeling_scheme %d\n", ctrl.edge_labeling_scheme);
96}
97
98enum { MAX_I = 20, OPT_UP = 1, OPT_DOWN = -1, OPT_INIT = 0 };
99
100typedef struct {
101 int i;
102 double work[MAX_I + 1];
105
107 oned_optimizer opt = {0};
108 opt.i = i;
109 opt.direction = OPT_INIT;
110 return opt;
111}
112
113static void oned_optimizer_train(oned_optimizer *opt, double work) {
114 int i = opt->i;
115
116 assert(i >= 0);
117 opt->work[i] = work;
118 if (opt->direction == OPT_INIT){
119 if (opt->i == MAX_I){
120 opt->direction = OPT_DOWN;
121 opt->i = opt->i - 1;
122 } else {
123 opt->direction = OPT_UP;
124 opt->i = MIN(MAX_I, opt->i + 1);
125 }
126 } else if (opt->direction == OPT_UP){
127 assert(i >= 1);
128 if (opt->work[i] < opt->work[i-1] && opt->i < MAX_I){
129 opt->i = MIN(MAX_I, opt->i + 1);
130 } else {
131 opt->i--;
132 opt->direction = OPT_DOWN;
133 }
134 } else {
135 assert(i < MAX_I);
136 if (opt->work[i] < opt->work[i+1] && opt->i > 0){
137 opt->i = MAX(0, opt->i-1);
138 } else {
139 opt->i++;
140 opt->direction = OPT_UP;
141 }
142 }
143}
144
145static int oned_optimizer_get(const oned_optimizer opt) {
146 return opt.i;
147}
148
149
151 double dist = 0, d;
152 int *ia = A->ia, *ja = A->ja, i, j, k;
153 assert(SparseMatrix_is_symmetric(A, true));
154
155 if (ia[A->m] == 0) return 1;
156 for (i = 0; i < A->m; i++){
157 for (j = ia[i]; j < ia[i+1]; j++){
158 d = 0;
159 for (k = 0; k < dim; k++){
160 d += (coord[dim*i+k] - coord[dim*ja[j]])*(coord[dim*i+k] - coord[dim*ja[j]]);
161 }
162 dist += sqrt(d);
163 }
164 }
165 return dist/ia[A->m];
166}
167
168static double update_step(bool adaptive_cooling, double step, double Fnorm,
169 double Fnorm0) {
170
171 if (!adaptive_cooling) {
172 return cool*step;
173 }
174 if (Fnorm >= Fnorm0){
175 step = cool*step;
176 } else if (Fnorm > 0.95*Fnorm0){
177 // step = step;
178 } else {
179 step = 0.99*step/cool;
180 }
181 return step;
182}
183
184
185#define node_degree(i) (ia[(i)+1] - ia[(i)])
186
187static void set_leaves(double *x, int dim, double dist, double ang, int i, int j){
188 x[dim*j] = cos(ang)*dist + x[dim*i];
189 x[dim*j+1] = sin(ang)*dist + x[dim*i+1];
190}
191
192DEFINE_LIST(ints, int)
193
194static void beautify_leaves(int dim, SparseMatrix A, double *x){
195 int m = A->m, i, j, *ia = A->ia, *ja = A->ja;
196 int p;
197 double dist;
198 double step;
199
201
202 bitarray_t checked = bitarray_new(m);
203
204 for (i = 0; i < m; i++){
205 if (ia[i+1] - ia[i] != 1) continue;
206 if (bitarray_get(checked, i)) continue;
207 p = ja[ia[i]];
208 if (!bitarray_get(checked, p)) {
209 bitarray_set(&checked, p, true);
210 dist = 0;
211 ints_t leaves = {0};
212 for (j = ia[p]; j < ia[p+1]; j++){
213 if (node_degree(ja[j]) == 1){
214 bitarray_set(&checked, ja[j], true);
215 dist += distance(x, dim, p, ja[j]);
216 ints_append(&leaves, ja[j]);
217 }
218 }
219 assert(!ints_is_empty(&leaves));
220 dist /= (double)ints_size(&leaves);
221 double ang1 = 0;
222 double ang2 = 2 * M_PI;
223 const double pad = 0.1; // fudge factor to account for the size and
224 // placement of the nodes themselves
225 ang1 += pad;
226 ang2 -= pad;
227 assert(ang2 >= ang1);
228 step = 0.;
229 if (ints_size(&leaves) > 1) step = (ang2 - ang1) / (double)ints_size(&leaves);
230 for (size_t k = 0; k < ints_size(&leaves); k++) {
231 set_leaves(x, dim, dist, ang1, p, ints_get(&leaves, k));
232 ang1 += step;
233 }
234 ints_free(&leaves);
235 }
236 }
237
238 bitarray_reset(&checked);
239}
240
243 double *x, int *flag) {
244 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. */
245 SparseMatrix A = A0;
246 int m, n;
247 int i, j, k;
248 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
249 int *ia = NULL, *ja = NULL;
250 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
251 int iter = 0;
252 const bool adaptive_cooling = ctrl->adaptive_cooling;
253 double counts[4], *force = NULL;
254#ifdef TIME
255 clock_t start, end, start0;
256 double qtree_cpu = 0, qtree_new_cpu = 0;
257 double total_cpu = 0;
258 start0 = clock();
259#endif
260 int max_qtree_level = ctrl->max_qtree_level;
261
262 if (!A || maxiter <= 0) return;
263
264 m = A->m, n = A->n;
265 if (n <= 0 || dim <= 0) return;
266
267 oned_optimizer qtree_level_optimizer = oned_optimizer_new(max_qtree_level);
268
269 *flag = 0;
270 if (m != n) {
272 goto RETURN;
273 }
274 assert(A->format == FORMAT_CSR);
275 A = SparseMatrix_symmetrize(A, true);
276 ia = A->ia;
277 ja = A->ja;
278
279 if (ctrl->random_start){
280 srand(ctrl->random_seed);
281 for (i = 0; i < dim*n; i++) x[i] = drand();
282 }
283 if (K < 0){
284 ctrl->K = K = average_edge_length(A, dim, x);
285 }
286 if (p >= 0) ctrl->p = p = -1;
287 KP = pow(K, 1 - p);
288 CRK = pow(C, (2.-p)/3.)/K;
289
290 force = gv_calloc(dim * n, sizeof(double));
291
292 do {
293 iter++;
294 Fnorm0 = Fnorm;
295 Fnorm = 0.;
296
297 max_qtree_level = oned_optimizer_get(qtree_level_optimizer);
298
299#ifdef TIME
300 start = clock();
301#endif
302 QuadTree qt = QuadTree_new_from_point_list(dim, n, max_qtree_level, x);
303
304#ifdef TIME
305 qtree_new_cpu += (double)(clock() - start) / CLOCKS_PER_SEC;
306#endif
307
308 /* repulsive force */
309#ifdef TIME
310 start = clock();
311#endif
312
313 QuadTree_get_repulsive_force(qt, force, x, bh, p, KP, counts);
314
315#ifdef TIME
316 end = clock();
317 qtree_cpu += (double)(end - start) / CLOCKS_PER_SEC;
318#endif
319
320 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
321 for (i = 0; i < n; i++){
322 f = &(force[i*dim]);
323 for (j = ia[i]; j < ia[i+1]; j++){
324 if (ja[j] == i) continue;
325 dist = distance(x, dim, i, ja[j]);
326 for (k = 0; k < dim; k++){
327 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
328 }
329 }
330 }
331
332
333 /* move */
334 for (i = 0; i < n; i++){
335 f = &force[i*dim];
336 F = 0.;
337 for (k = 0; k < dim; k++) F += f[k]*f[k];
338 F = sqrt(F);
339 Fnorm += F;
340 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
341 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
342 }/* done vertex i */
343
344
345
346 if (qt) {
347#ifdef TIME
348 start = clock();
349#endif
350 QuadTree_delete(qt);
351#ifdef TIME
352 end = clock();
353 qtree_new_cpu += (double)(end - start) / CLOCKS_PER_SEC;
354#endif
355
356 oned_optimizer_train(&qtree_level_optimizer,
357 counts[0] + 0.85 * counts[1] + 3.3 * counts[2]);
358 } else {
359 if (Verbose) {
360 fprintf(stderr, "\r iter = %d, step = %f Fnorm = %f nz = %d K = %f ",iter, step, Fnorm, A->nz,K);
361 }
362 }
363
364 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
365 } while (step > tol && iter < maxiter);
366
367#ifdef DEBUG_PRINT
368 if (Verbose) {
369 fprintf(stderr, "\n iter = %d, step = %f Fnorm = %f nz = %d K = %f ",iter, step, Fnorm, A->nz, K);
370 }
371#endif
372
373 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
374
375#ifdef TIME
376 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
377 if (Verbose) fprintf(stderr, "\n time for qtree = %f, qtree_force = %f, total cpu = %f\n",qtree_new_cpu, qtree_cpu, total_cpu);
378#endif
379
380
381 RETURN:
382 ctrl->max_qtree_level = max_qtree_level;
383
384 if (A != A0) SparseMatrix_delete(A);
385 free(force);
386}
387
390 double *x, int *flag) {
391 /* a version that does vertex moves in one go, instead of one at a time, use for debugging the fast version. Quadtree is not used. */
392 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. */
393 SparseMatrix A = A0;
394 int m, n;
395 int i, j, k;
396 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
397 int *ia = NULL, *ja = NULL;
398 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
399 int iter = 0;
400 const bool adaptive_cooling = ctrl->adaptive_cooling;
401 double *force;
402#ifdef TIME
403 clock_t start, end, start0, start2;
404 double total_cpu = 0;
405 start0 = clock();
406#endif
407
408 fprintf(stderr,"spring_electrical_embedding_slow");
409 if (!A || maxiter <= 0) return;
410
411 m = A->m, n = A->n;
412 if (n <= 0 || dim <= 0) return;
413 force = gv_calloc(n *dim, sizeof(double));
414
415 *flag = 0;
416 if (m != n) {
418 goto RETURN;
419 }
420 assert(A->format == FORMAT_CSR);
421 A = SparseMatrix_symmetrize(A, true);
422 ia = A->ia;
423 ja = A->ja;
424
425 if (ctrl->random_start){
426 srand(ctrl->random_seed);
427 for (i = 0; i < dim*n; i++) x[i] = drand();
428 }
429 if (K < 0){
430 ctrl->K = K = average_edge_length(A, dim, x);
431 }
432 if (p >= 0) ctrl->p = p = -1;
433 KP = pow(K, 1 - p);
434 CRK = pow(C, (2.-p)/3.)/K;
435
436 f = gv_calloc(dim, sizeof(double));
437 do {
438 for (i = 0; i < dim*n; i++) force[i] = 0;
439
440 iter++;
441 Fnorm0 = Fnorm;
442 Fnorm = 0.;
443
444#ifdef TIME
445 start2 = clock();
446#endif
447
448
449 for (i = 0; i < n; i++){
450 for (k = 0; k < dim; k++) f[k] = 0.;
451 /* repulsive force K^(1 - p)/||x_i-x_j||^(1 - p) (x_i - x_j) */
452 for (j = 0; j < n; j++){
453 if (j == i) continue;
454 dist = distance_cropped(x, dim, i, j);
455 for (k = 0; k < dim; k++){
456 f[k] += KP*(x[i*dim+k] - x[j*dim+k])/pow(dist, 1.- p);
457 }
458 }
459 for (k = 0; k < dim; k++) force[i*dim+k] += f[k];
460 }
461
462
463
464 for (i = 0; i < n; i++){
465 for (k = 0; k < dim; k++) f[k] = 0.;
466 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
467 for (j = ia[i]; j < ia[i+1]; j++){
468 if (ja[j] == i) continue;
469 dist = distance(x, dim, i, ja[j]);
470 for (k = 0; k < dim; k++){
471 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
472 }
473 }
474 for (k = 0; k < dim; k++) force[i*dim+k] += f[k];
475 }
476
477
478
479 for (i = 0; i < n; i++){
480 /* normalize force */
481 for (k = 0; k < dim; k++) f[k] = force[i*dim+k];
482
483 F = 0.;
484 for (k = 0; k < dim; k++) F += f[k]*f[k];
485 F = sqrt(F);
486 Fnorm += F;
487
488 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
489
490 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
491
492 }/* done vertex i */
493
494 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
495 } while (step > tol && iter < maxiter);
496
497#ifdef DEBUG_PRINT
498 if (Verbose) {
499 fprintf(stderr, "iter = %d, step = %f Fnorm = %f nsuper = 0 nz = %d K = %f ",iter, step, Fnorm, A->nz,K);
500 }
501#endif
502
503 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
504
505#ifdef TIME
506 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
507 if (Verbose) fprintf(stderr, "time for supernode = 0, total cpu = %f\n", total_cpu);
508#endif
509
510 RETURN:
511 if (A != A0) SparseMatrix_delete(A);
512 free(f);
513 free(force);
514}
515
517 spring_electrical_control *ctrl, double *x,
518 int *flag) {
519 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. */
520 SparseMatrix A = A0;
521 int m, n;
522 int i, j, k;
523 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
524 int *ia = NULL, *ja = NULL;
525 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
526 int iter = 0;
527 const bool adaptive_cooling = ctrl->adaptive_cooling;
528 bool USE_QT = false;
529 int nsuper = 0, nsupermax = 10;
530 double *center = NULL, *supernode_wgts = NULL, *distances = NULL, nsuper_avg, counts = 0, counts_avg = 0;
531#ifdef TIME
532 clock_t start, end, start0, start2;
533 double qtree_cpu = 0;
534 double total_cpu = 0;
535 start0 = clock();
536#endif
537 int max_qtree_level = ctrl->max_qtree_level;
538 oned_optimizer qtree_level_optimizer = {0};
539
540 if (!A || maxiter <= 0) return;
541
542 m = A->m, n = A->n;
543 if (n <= 0 || dim <= 0) return;
544
545 if (n >= quadtree_size) {
546 USE_QT = true;
547 qtree_level_optimizer = oned_optimizer_new(max_qtree_level);
548 center = gv_calloc(nsupermax * dim, sizeof(double));
549 supernode_wgts = gv_calloc(nsupermax, sizeof(double));
550 distances = gv_calloc(nsupermax, sizeof(double));
551 }
552 *flag = 0;
553 if (m != n) {
555 goto RETURN;
556 }
557 assert(A->format == FORMAT_CSR);
558 A = SparseMatrix_symmetrize(A, true);
559 ia = A->ia;
560 ja = A->ja;
561
562 if (ctrl->random_start){
563 srand(ctrl->random_seed);
564 for (i = 0; i < dim*n; i++) x[i] = drand();
565 }
566 if (K < 0){
567 ctrl->K = K = average_edge_length(A, dim, x);
568 }
569 if (p >= 0) ctrl->p = p = -1;
570 KP = pow(K, 1 - p);
571 CRK = pow(C, (2.-p)/3.)/K;
572
573 f = gv_calloc(dim, sizeof(double));
574 do {
575
576 iter++;
577 Fnorm0 = Fnorm;
578 Fnorm = 0.;
579 nsuper_avg = 0;
580 counts_avg = 0;
581
582 QuadTree qt = NULL;
583 if (USE_QT) {
584
585 max_qtree_level = oned_optimizer_get(qtree_level_optimizer);
586 qt = QuadTree_new_from_point_list(dim, n, max_qtree_level, x);
587
588
589 }
590#ifdef TIME
591 start2 = clock();
592#endif
593
594 for (i = 0; i < n; i++){
595 for (k = 0; k < dim; k++) f[k] = 0.;
596 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
597 for (j = ia[i]; j < ia[i+1]; j++){
598 if (ja[j] == i) continue;
599 dist = distance(x, dim, i, ja[j]);
600 for (k = 0; k < dim; k++){
601 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
602 }
603 }
604
605 /* repulsive force K^(1 - p)/||x_i-x_j||^(1 - p) (x_i - x_j) */
606 if (USE_QT){
607#ifdef TIME
608 start = clock();
609#endif
610 QuadTree_get_supernodes(qt, bh, &(x[dim*i]), i, &nsuper, &nsupermax,
611 &center, &supernode_wgts, &distances, &counts);
612
613#ifdef TIME
614 end = clock();
615 qtree_cpu += (double)(end - start) / CLOCKS_PER_SEC;
616#endif
617 counts_avg += counts;
618 nsuper_avg += nsuper;
619 for (j = 0; j < nsuper; j++){
620 dist = MAX(distances[j], MINDIST);
621 for (k = 0; k < dim; k++){
622 f[k] += supernode_wgts[j]*KP*(x[i*dim+k] - center[j*dim+k])/pow(dist, 1.- p);
623 }
624 }
625 } else {
626 for (j = 0; j < n; j++){
627 if (j == i) continue;
628 dist = distance_cropped(x, dim, i, j);
629 for (k = 0; k < dim; k++){
630 f[k] += KP*(x[i*dim+k] - x[j*dim+k])/pow(dist, 1.- p);
631 }
632 }
633 }
634
635 /* normalize force */
636 F = 0.;
637 for (k = 0; k < dim; k++) F += f[k]*f[k];
638 F = sqrt(F);
639 Fnorm += F;
640
641 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
642
643 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
644
645 }/* done vertex i */
646
647 if (qt) {
648 QuadTree_delete(qt);
649 nsuper_avg /= n;
650 counts_avg /= n;
651 oned_optimizer_train(&qtree_level_optimizer, 5 * nsuper_avg + counts_avg);
652 }
653
654 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
655 } while (step > tol && iter < maxiter);
656
657#ifdef DEBUG_PRINT
658 if (Verbose) {
659 if (USE_QT){
660 fprintf(stderr, "iter = %d, step = %f Fnorm = %f qt_level = %d nsuper = %d nz = %d K = %f ",iter, step, Fnorm, max_qtree_level, (int) nsuper_avg,A->nz,K);
661 } else {
662 fprintf(stderr, "iter = %d, step = %f Fnorm = %f nsuper = %d nz = %d K = %f ",iter, step, Fnorm, (int) nsuper_avg,A->nz,K);
663 }
664 }
665#endif
666
667 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
668
669#ifdef TIME
670 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
671 if (Verbose) fprintf(stderr, "time for supernode = %f, total cpu = %f\n",qtree_cpu, total_cpu);
672#endif
673
674 RETURN:
675 if (USE_QT) {
676 ctrl->max_qtree_level = max_qtree_level;
677 }
678 if (A != A0) SparseMatrix_delete(A);
679 free(f);
680 free(center);
681 free(supernode_wgts);
682 free(distances);
683}
684
687 double *x, int *flag) {
688 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. Same as the spring-electrical except we also
689 introduce force due to spring length
690 */
691 SparseMatrix A = A0;
692 int m, n;
693 int i, j, k;
694 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
695 int *ia = NULL, *ja = NULL;
696 int *id = NULL, *jd = NULL;
697 double *d;
698 double *xold = NULL;
699 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
700 int iter = 0;
701 const bool adaptive_cooling = ctrl->adaptive_cooling;
702 bool USE_QT = false;
703 int nsuper = 0, nsupermax = 10;
704 double *center = NULL, *supernode_wgts = NULL, *distances = NULL, counts = 0;
705 int max_qtree_level = 10;
706
707 if (!A || maxiter <= 0) return;
708 m = A->m, n = A->n;
709 if (n <= 0 || dim <= 0) return;
710
711 if (n >= quadtree_size) {
712 USE_QT = true;
713 center = gv_calloc(nsupermax * dim, sizeof(double));
714 supernode_wgts = gv_calloc(nsupermax, sizeof(double));
715 distances = gv_calloc(nsupermax, sizeof(double));
716 }
717 *flag = 0;
718 if (m != n) {
720 goto RETURN;
721 }
722 assert(A->format == FORMAT_CSR);
723 A = SparseMatrix_symmetrize(A, true);
724 ia = A->ia;
725 ja = A->ja;
726 id = D->ia;
727 jd = D->ja;
728 d = D->a;
729
730 if (ctrl->random_start){
731 srand(ctrl->random_seed);
732 for (i = 0; i < dim*n; i++) x[i] = drand();
733 }
734 if (K < 0){
735 ctrl->K = K = average_edge_length(A, dim, x);
736 }
737 if (p >= 0) ctrl->p = p = -1;
738 KP = pow(K, 1 - p);
739 CRK = pow(C, (2.-p)/3.)/K;
740
741 f = gv_calloc(dim, sizeof(double));
742 xold = gv_calloc(dim * n, sizeof(double));
743 do {
744 iter++;
745 memcpy(xold, x, sizeof(double)*dim*n);
746 Fnorm0 = Fnorm;
747 Fnorm = 0.;
748
749 QuadTree qt = NULL;
750 if (USE_QT) {
751 qt = QuadTree_new_from_point_list(dim, n, max_qtree_level, x);
752 }
753
754 for (i = 0; i < n; i++){
755 for (k = 0; k < dim; k++) f[k] = 0.;
756 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
757
758 for (j = ia[i]; j < ia[i+1]; j++){
759 if (ja[j] == i) continue;
760 dist = distance(x, dim, i, ja[j]);
761 for (k = 0; k < dim; k++){
762 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
763 }
764 }
765
766 for (j = id[i]; j < id[i+1]; j++){
767 if (jd[j] == i) continue;
768 dist = distance_cropped(x, dim, i, jd[j]);
769 for (k = 0; k < dim; k++){
770 if (dist < d[j]){
771 f[k] += 0.2*CRK*(x[i*dim+k] - x[jd[j]*dim+k])*(dist - d[j])*(dist - d[j])/dist;
772 } else {
773 f[k] -= 0.2*CRK*(x[i*dim+k] - x[jd[j]*dim+k])*(dist - d[j])*(dist - d[j])/dist;
774 }
775 /* f[k] -= 0.2*CRK*(x[i*dim+k] - x[jd[j]*dim+k])*(dist - d[j]);*/
776 }
777 }
778
779 /* repulsive force K^(1 - p)/||x_i-x_j||^(1 - p) (x_i - x_j) */
780 if (USE_QT){
781 QuadTree_get_supernodes(qt, bh, &x[dim * i], i, &nsuper, &nsupermax,
782 &center, &supernode_wgts, &distances, &counts);
783 for (j = 0; j < nsuper; j++){
784 dist = MAX(distances[j], MINDIST);
785 for (k = 0; k < dim; k++){
786 f[k] += supernode_wgts[j]*KP*(x[i*dim+k] - center[j*dim+k])/pow(dist, 1.- p);
787 }
788 }
789 } else {
790 for (j = 0; j < n; j++){
791 if (j == i) continue;
792 dist = distance_cropped(x, dim, i, j);
793 for (k = 0; k < dim; k++){
794 f[k] += KP*(x[i*dim+k] - x[j*dim+k])/pow(dist, 1.- p);
795 }
796 }
797 }
798
799 /* normalize force */
800 F = 0.;
801 for (k = 0; k < dim; k++) F += f[k]*f[k];
802 F = sqrt(F);
803 Fnorm += F;
804
805 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
806
807 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
808
809 }/* done vertex i */
810
811 if (qt) QuadTree_delete(qt);
812
813 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
814 } while (step > tol && iter < maxiter);
815
816 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
817
818 RETURN:
819 free(xold);
820 if (A != A0) SparseMatrix_delete(A);
821 free(f);
822 free(center);
823 free(supernode_wgts);
824 free(distances);
825}
826
827static void interpolate_coord(int dim, SparseMatrix A, double *x) {
828 int i, j, k, *ia = A->ia, *ja = A->ja, nz;
829 double alpha = 0.5, beta;
830
831 double *y = gv_calloc(dim, sizeof(double));
832 for (i = 0; i < A->m; i++){
833 for (k = 0; k < dim; k++) y[k] = 0;
834 nz = 0;
835 for (j = ia[i]; j < ia[i+1]; j++){
836 if (ja[j] == i) continue;
837 nz++;
838 for (k = 0; k < dim; k++){
839 y[k] += x[ja[j]*dim + k];
840 }
841 }
842 if (nz > 0){
843 beta = (1-alpha)/nz;
844 for (k = 0; k < dim; k++) x[i*dim+k] = alpha*x[i*dim+k] + beta*y[k];
845 }
846 }
847
848 free(y);
849}
850static void prolongate(int dim, SparseMatrix A, SparseMatrix P, SparseMatrix R, double *x, double *y, double delta){
851 int nc, *ia, *ja, i, j, k;
853
855 nc = R->m;
856 ia = R->ia;
857 ja = R->ja;
858 for (i = 0; i < nc; i++){
859 for (j = ia[i]+1; j < ia[i+1]; j++){
860 for (k = 0; k < dim; k++){
861 y[ja[j]*dim + k] += delta*(drand() - 0.5);
862 }
863 }
864 }
865}
866
868 int m, max = 0, i, *ia = A->ia, *ja = A->ja, j, deg;
869 bool res = false;
870 m = A->m;
871 int *mask = gv_calloc(m + 1, sizeof(int));
872
873 for (i = 0; i < m + 1; i++){
874 mask[i] = 0;
875 }
876
877 for (i = 0; i < m; i++){
878 deg = 0;
879 for (j = ia[i]; j < ia[i+1]; j++){
880 if (i == ja[j]) continue;
881 deg++;
882 }
883 mask[deg]++;
884 max = MAX(max, mask[deg]);
885 }
886 if (mask[1] > 0.8*max && mask[1] > 0.3*m) res = true;
887 free(mask);
888 return res;
889}
890
891void pcp_rotate(int n, int dim, double *x){
892 int i, k,l;
893 double y[4], axis[2], center[2], dist, x0, x1;
894
895 assert(dim == 2);
896 for (i = 0; i < dim*dim; i++) y[i] = 0;
897 for (i = 0; i < dim; i++) center[i] = 0;
898 for (i = 0; i < n; i++){
899 for (k = 0; k < dim; k++){
900 center[k] += x[i*dim+k];
901 }
902 }
903 for (i = 0; i < dim; i++) center[i] /= n;
904 for (i = 0; i < n; i++){
905 for (k = 0; k < dim; k++){
906 x[dim*i+k] = x[dim*i+k] - center[k];
907 }
908 }
909
910 for (i = 0; i < n; i++){
911 for (k = 0; k < dim; k++){
912 for (l = 0; l < dim; l++){
913 y[dim*k+l] += x[i*dim+k]*x[i*dim+l];
914 }
915 }
916 }
917 if (y[1] == 0) {
918 axis[0] = 0; axis[1] = 1;
919 } else {
920 /* Eigensystem[{{x0, x1}, {x1, x3}}] =
921 {{(x0 + x3 - Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/2,
922 (x0 + x3 + Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/2},
923 {{-(-x0 + x3 + Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/(2*x1), 1},
924 {-(-x0 + x3 - Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/(2*x1), 1}}}
925 */
926 axis[0] = -(-y[0] + y[3] - sqrt(y[0]*y[0]+4*y[1]*y[1]-2*y[0]*y[3]+y[3]*y[3]))/(2*y[1]);
927 axis[1] = 1;
928 }
929 dist = sqrt(1+axis[0]*axis[0]);
930 axis[0] = axis[0]/dist;
931 axis[1] = axis[1]/dist;
932 for (i = 0; i < n; i++){
933 x0 = x[dim*i]*axis[0]+x[dim*i+1]*axis[1];
934 x1 = -x[dim*i]*axis[1]+x[dim*i+1]*axis[0];
935 x[dim*i] = x0;
936 x[dim*i + 1] = x1;
937
938 }
939
940
941}
942
943static void rotate(int n, int dim, double *x, double angle){
944 int i, k;
945 double axis[2], center[2], x0, x1;
946 double radian = 3.14159/180;
947
948 assert(dim == 2);
949 for (i = 0; i < dim; i++) center[i] = 0;
950 for (i = 0; i < n; i++){
951 for (k = 0; k < dim; k++){
952 center[k] += x[i*dim+k];
953 }
954 }
955 for (i = 0; i < dim; i++) center[i] /= n;
956 for (i = 0; i < n; i++){
957 for (k = 0; k < dim; k++){
958 x[dim*i+k] = x[dim*i+k] - center[k];
959 }
960 }
961 axis[0] = cos(-angle*radian);
962 axis[1] = sin(-angle*radian);
963 for (i = 0; i < n; i++){
964 x0 = x[dim*i]*axis[0]+x[dim*i+1]*axis[1];
965 x1 = -x[dim*i]*axis[1]+x[dim*i+1]*axis[0];
966 x[dim*i] = x0;
967 x[dim*i + 1] = x1;
968 }
969
970
971}
972
973static void attach_edge_label_coordinates(int dim, SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes, double *x, double *x2){
974 int i, ii, j, k;
975 int nnodes = 0;
976 double len;
977
978 int *mask = gv_calloc(A->m, sizeof(int));
979
980 for (i = 0; i < A->m; i++) mask[i] = 1;
981 for (i = 0; i < n_edge_label_nodes; i++) {
982 if (edge_label_nodes[i] >= 0 && edge_label_nodes[i] < A->m) mask[edge_label_nodes[i]] = -1;
983 }
984
985 for (i = 0; i < A->m; i++) {
986 if (mask[i] >= 0) mask[i] = nnodes++;
987 }
988
989
990 for (i = 0; i < A->m; i++){
991 if (mask[i] >= 0){
992 for (k = 0; k < dim; k++) x[i*dim+k] = x2[mask[i]*dim+k];
993 }
994 }
995
996 for (i = 0; i < n_edge_label_nodes; i++){
997 ii = edge_label_nodes[i];
998 len = A->ia[ii+1] - A->ia[ii];
999 assert(len >= 2); /* should just be 2 */
1000 assert(mask[ii] < 0);
1001 for (k = 0; k < dim; k++) {
1002 x[ii*dim+k] = 0;
1003 }
1004 for (j = A->ia[ii]; j < A->ia[ii+1]; j++){
1005 for (k = 0; k < dim; k++){
1006 x[ii * dim + k] += x[A->ja[j] * dim + k];
1007 }
1008 }
1009 for (k = 0; k < dim; k++) {
1010 x[ii*dim+k] /= len;
1011 }
1012 }
1013
1014 free(mask);
1015}
1016
1017static SparseMatrix shorting_edge_label_nodes(SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes){
1018 int i, id = 0, nz, j, jj, ii;
1019 int *ia = A->ia, *ja = A->ja, *irn = NULL, *jcn = NULL;
1021
1022 int *mask = gv_calloc(A->m, sizeof(int));
1023
1024 for (i = 0; i < A->m; i++) mask[i] = 1;
1025
1026 for (i = 0; i < n_edge_label_nodes; i++){
1027 mask[edge_label_nodes[i]] = -1;
1028 }
1029
1030 for (i = 0; i < A->m; i++) {
1031 if (mask[i] > 0) mask[i] = id++;
1032 }
1033
1034 nz = 0;
1035 for (i = 0; i < A->m; i++){
1036 if (mask[i] < 0) continue;
1037 for (j = ia[i]; j < ia[i+1]; j++){
1038 if (mask[ja[j]] >= 0) {
1039 nz++;
1040 continue;
1041 }
1042 ii = ja[j];
1043 for (jj = ia[ii]; jj < ia[ii+1]; jj++){
1044 if (ja[jj] != i && mask[ja[jj]] >= 0) nz++;
1045 }
1046 }
1047 }
1048
1049 if (nz > 0) {
1050 irn = gv_calloc(nz, sizeof(int));
1051 jcn = gv_calloc(nz, sizeof(int));
1052 }
1053
1054 nz = 0;
1055 for (i = 0; i < A->m; i++){
1056 if (mask[i] < 0) continue;
1057 for (j = ia[i]; j < ia[i+1]; j++){
1058 if (mask[ja[j]] >= 0) {
1059 irn[nz] = mask[i];
1060 jcn[nz++] = mask[ja[j]];
1061 continue;
1062 }
1063 ii = ja[j];
1064 for (jj = ia[ii]; jj < ia[ii+1]; jj++){
1065 if (ja[jj] != i && mask[ja[jj]] >= 0) {
1066 irn[nz] = mask[i];
1067 jcn[nz++] = mask[ja[jj]];
1068 }
1069 }
1070 }
1071 }
1072
1073 B = SparseMatrix_from_coordinate_arrays(nz, id, id, irn, jcn, NULL, MATRIX_TYPE_PATTERN, sizeof(double));
1074
1075 free(irn);
1076 free(jcn);
1077 free(mask);
1078 return B;
1079
1080}
1081
1084 double *label_sizes, double *x,
1085 int n_edge_label_nodes,
1086 int *edge_label_nodes, int *flag) {
1087
1088 int n;
1089 SparseMatrix A = A0, P = NULL;
1090 Multilevel grid, grid0;
1091 double *xc = NULL, *xf = NULL;
1092#ifdef TIME
1093 clock_t cpu;
1094#endif
1095
1096 const spring_electrical_control ctrl0 = *ctrl;
1097
1098#ifdef TIME
1099 cpu = clock();
1100#endif
1101
1102 *flag = 0;
1103 if (!A) return;
1104 n = A->n;
1105 if (n <= 0 || dim <= 0) return;
1106
1107 if (!SparseMatrix_is_symmetric(A, false) || A->type != MATRIX_TYPE_REAL){
1109 } else {
1111 }
1112
1113 /* we first generate a layout discarding (shorting) the edge labels nodes, then assign the edge label nodes at the average of their neighbors */
1115 && n_edge_label_nodes > 0){
1116 SparseMatrix A2;
1117
1118 double *x2 = gv_calloc(A->m * dim, sizeof(double));
1119 A2 = shorting_edge_label_nodes(A, n_edge_label_nodes, edge_label_nodes);
1120 multilevel_spring_electrical_embedding(dim, A2, ctrl, NULL, x2, 0, NULL, flag);
1121
1122 assert(!*flag);
1123 attach_edge_label_coordinates(dim, A, n_edge_label_nodes, edge_label_nodes, x, x2);
1124 remove_overlap(dim, A, x, label_sizes, ctrl->overlap, ctrl->initial_scaling,
1125 ctrl->edge_labeling_scheme, n_edge_label_nodes, edge_label_nodes, A, ctrl->do_shrinking);
1127 free(x2);
1128 if (A != A0) SparseMatrix_delete(A);
1129
1130 return;
1131 }
1132
1133 Multilevel_control mctrl = {.maxlevel = ctrl->multilevels};
1134 grid0 = Multilevel_new(A, mctrl);
1135
1138 xc = x;
1139 } else {
1140 xc = gv_calloc(grid->n * dim, sizeof(double));
1141 }
1142
1143 const bool plg = power_law_graph(A);
1144 if (ctrl->p == AUTOP){
1145 ctrl->p = -1;
1146 if (plg) ctrl->p = -1.8;
1147 }
1148
1149 do {
1150#ifdef DEBUG_PRINT
1151 if (Verbose) {
1152 print_padding(grid->level);
1154 fprintf(stderr, "coarsest level -- %d, n = %d\n", grid->level, grid->n);
1155 } else {
1156 fprintf(stderr, "level -- %d, n = %d\n", grid->level, grid->n);
1157 }
1158 }
1159#endif
1160 if (ctrl->tscheme == QUAD_TREE_NONE){
1161 spring_electrical_embedding_slow(dim, grid->A, ctrl, xc, flag);
1162 } else if (ctrl->tscheme == QUAD_TREE_FAST || (ctrl->tscheme == QUAD_TREE_HYBRID && grid->A->m > QUAD_TREE_HYBRID_SIZE)){
1163 if (ctrl->tscheme == QUAD_TREE_HYBRID && grid->A->m > 10 && Verbose){
1164 fprintf(stderr, "QUAD_TREE_HYBRID, size larger than %d, switch to fast quadtree", QUAD_TREE_HYBRID_SIZE);
1165 }
1166 spring_electrical_embedding_fast(dim, grid->A, ctrl, xc, flag);
1167 } else {
1168 spring_electrical_embedding(dim, grid->A, ctrl, xc, flag);
1169 }
1170 if (Multilevel_is_finest(grid)) break;
1171 if (*flag) {
1172 free(xc);
1173 goto RETURN;
1174 }
1175 P = grid->P;
1176 grid = grid->prev;
1178 xf = x;
1179 } else {
1180 xf = gv_calloc(grid->n * dim, sizeof(double));
1181 }
1182 prolongate(dim, grid->A, P, grid->R, xc, xf, ctrl->K * 0.001);
1183 free(xc);
1184 xc = xf;
1185 ctrl->random_start = false;
1186 ctrl->K = ctrl->K * 0.75;
1187 ctrl->adaptive_cooling = false;
1188 ctrl->step = .1;
1189 } while (grid);
1190
1191#ifdef TIME
1192 if (Verbose)
1193 fprintf(stderr, "layout time %f\n", (double)(clock() - cpu) / CLOCKS_PER_SEC);
1194 cpu = clock();
1195#endif
1196
1197 post_process_smoothing(dim, A, *ctrl, x);
1198
1199 if (Verbose) fprintf(stderr, "ctrl->overlap=%d\n",ctrl->overlap);
1200
1201 /* rotation has to be done before overlap removal, since rotation could induce overlaps */
1202 if (dim == 2){
1203 pcp_rotate(n, dim, x);
1204 }
1205 if (ctrl->rotation != 0) rotate(n, dim, x, ctrl->rotation);
1206
1207
1208 remove_overlap(dim, A, x, label_sizes, ctrl->overlap, ctrl->initial_scaling,
1209 ctrl->edge_labeling_scheme, n_edge_label_nodes, edge_label_nodes, A, ctrl->do_shrinking);
1210
1211 RETURN:
1212 *ctrl = ctrl0;
1213 if (A != A0) SparseMatrix_delete(A);
1214 Multilevel_delete(grid0);
1215 }
void print_padding(int n)
Definition Multilevel.c:241
Multilevel Multilevel_get_coarsest(Multilevel grid)
Definition Multilevel.c:298
void Multilevel_delete(Multilevel grid)
Definition Multilevel.c:37
Multilevel Multilevel_new(SparseMatrix A0, const Multilevel_control ctrl)
Definition Multilevel.c:282
#define Multilevel_is_coarsest(grid)
Definition Multilevel.h:44
#define Multilevel_is_finest(grid)
Definition Multilevel.h:43
void QuadTree_get_repulsive_force(QuadTree qt, double *force, double *x, double bh, double p, double KP, double *counts)
Definition QuadTree.c:281
QuadTree QuadTree_new_from_point_list(int dim, int n, int max_level, double *coord)
Definition QuadTree.c:309
void QuadTree_delete(QuadTree q)
Definition QuadTree.c:375
void QuadTree_get_supernodes(QuadTree qt, double bh, double *pt, int nodeid, int *nsuper, int *nsupermax, double **center, double **supernode_wgts, double **distances, double *counts)
Definition QuadTree.c:93
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
void SparseMatrix_multiply_dense(SparseMatrix A, const double *v, double *res, int dim)
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
SparseMatrix SparseMatrix_from_coordinate_arrays(int nz, int m, int n, int *irn, int *jcn, void *val0, int type, size_t sz)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
bool SparseMatrix_has_diagonal(SparseMatrix A)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
@ FORMAT_CSR
@ MATRIX_TYPE_REAL
@ MATRIX_TYPE_PATTERN
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define MIN(a, b)
Definition arith.h:28
#define M_PI
Definition arith.h:41
API for compacted arrays of booleans.
static bitarray_t bitarray_new(size_t size_bits)
create an array of the given element length
Definition bitarray.h:46
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
Definition bitarray.h:64
static void bitarray_set(bitarray_t *self, size_t index, bool value)
set or clear the value of the given element
Definition bitarray.h:79
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
Definition bitarray.h:98
#define MINDIST
Definition circular.c:16
#define A(n, t)
Definition expr.h:76
#define F
Definition expr.h:70
static double dist(int dim, double *x, double *y)
double drand(void)
Definition general.c:22
double distance(double *x, int dim, int i, int j)
Definition general.c:121
double distance_cropped(double *x, int dim, int i, int j)
Definition general.c:116
static double len(glCompPoint p)
Definition glutils.c:150
static bool Verbose
Definition gml2gv.c:23
void free(void *)
node NULL
Definition grammar.y:180
@ grid
Definition gvgen.c:33
#define B
Definition hierarchy.c:118
#define D
Definition hierarchy.c:120
#define DEFINE_LIST(name, type)
Definition list.h:22
#define delta
Definition maze.c:136
static const int dim
void remove_overlap(int dim, SparseMatrix A, double *x, double *label_sizes, int ntry, double initial_scaling, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, bool do_shrinking)
Definition overlap.c:586
@ ELSCHEME_STRAIGHTLINE_PENALTY2
Definition overlap.h:29
@ ELSCHEME_STRAIGHTLINE_PENALTY
Definition overlap.h:29
void post_process_smoothing(int dim, SparseMatrix A, spring_electrical_control ctrl, double *x)
pointf coord(node_t *n)
Definition utils.c:152
#define alpha
Definition shapes.c:4058
static bool power_law_graph(SparseMatrix A)
void spring_electrical_embedding(int dim, SparseMatrix A0, spring_electrical_control *ctrl, double *x, int *flag)
@ OPT_INIT
@ OPT_DOWN
@ OPT_UP
@ MAX_I
void spring_electrical_embedding_fast(int dim, SparseMatrix A0, spring_electrical_control *ctrl, double *x, int *flag)
static char * smoothings[]
void spring_electrical_control_print(spring_electrical_control ctrl)
void multilevel_spring_electrical_embedding(int dim, SparseMatrix A0, spring_electrical_control *ctrl, double *label_sizes, double *x, int n_edge_label_nodes, int *edge_label_nodes, int *flag)
static double update_step(bool adaptive_cooling, double step, double Fnorm, double Fnorm0)
spring_electrical_control spring_electrical_control_new(void)
static const int quadtree_size
cut off size above which quadtree approximation is used
static SparseMatrix shorting_edge_label_nodes(SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes)
static int oned_optimizer_get(const oned_optimizer opt)
static void prolongate(int dim, SparseMatrix A, SparseMatrix P, SparseMatrix R, double *x, double *y, double delta)
static void beautify_leaves(int dim, SparseMatrix A, double *x)
static oned_optimizer oned_optimizer_new(int i)
static char * tschemes[]
static void attach_edge_label_coordinates(int dim, SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes, double *x, double *x2)
static const double tol
static const double cool
static const double C
double average_edge_length(SparseMatrix A, int dim, double *coord)
static void oned_optimizer_train(oned_optimizer *opt, double work)
void pcp_rotate(int n, int dim, double *x)
static const double bh
static void rotate(int n, int dim, double *x, double angle)
void spring_electrical_spring_embedding(int dim, SparseMatrix A0, SparseMatrix D, spring_electrical_control *ctrl, double *x, int *flag)
static void set_leaves(double *x, int dim, double dist, double ang, int i, int j)
static void spring_electrical_embedding_slow(int dim, SparseMatrix A0, spring_electrical_control *ctrl, double *x, int *flag)
#define node_degree(i)
static void interpolate_coord(int dim, SparseMatrix A, double *x)
@ SMOOTHING_NONE
@ QUAD_TREE_FAST
@ QUAD_TREE_HYBRID
@ QUAD_TREE_NONE
#define AUTOP
@ ERROR_NOT_SQUARE_MATRIX
@ QUAD_TREE_HYBRID_SIZE
#define RETURN(v)
Definition strmatch.c:144
double work[MAX_I+1]
bool random_start
whether to apply SE from a random layout, or from exisiting layout
static point center(point vertex[], size_t n)
graphs, nodes and edges info: Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t
#define MAX(a, b)
Definition write.c:31