Graphviz 13.1.3~dev.20250831.0023
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;
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
192static void beautify_leaves(int dim, SparseMatrix A, double *x){
193 int m = A->m, i, j, *ia = A->ia, *ja = A->ja;
194 int p;
195 double dist;
196 double step;
197
199
200 bitarray_t checked = bitarray_new(m);
201
202 for (i = 0; i < m; i++){
203 if (ia[i+1] - ia[i] != 1) continue;
204 if (bitarray_get(checked, i)) continue;
205 p = ja[ia[i]];
206 if (!bitarray_get(checked, p)) {
207 bitarray_set(&checked, p, true);
208 dist = 0;
209 LIST(int) leaves = {0};
210 for (j = ia[p]; j < ia[p+1]; j++){
211 if (node_degree(ja[j]) == 1){
212 bitarray_set(&checked, ja[j], true);
213 dist += distance(x, dim, p, ja[j]);
214 LIST_APPEND(&leaves, ja[j]);
215 }
216 }
217 assert(!LIST_IS_EMPTY(&leaves));
218 dist /= (double)LIST_SIZE(&leaves);
219 double ang1 = 0;
220 double ang2 = 2 * M_PI;
221 const double pad = 0.1; // fudge factor to account for the size and
222 // placement of the nodes themselves
223 ang1 += pad;
224 ang2 -= pad;
225 assert(ang2 >= ang1);
226 step = 0.;
227 if (LIST_SIZE(&leaves) > 1) step = (ang2 - ang1) / (double)LIST_SIZE(&leaves);
228 for (size_t k = 0; k < LIST_SIZE(&leaves); k++) {
229 set_leaves(x, dim, dist, ang1, p, LIST_GET(&leaves, k));
230 ang1 += step;
231 }
232 LIST_FREE(&leaves);
233 }
234 }
235
236 bitarray_reset(&checked);
237}
238
241 double *x, int *flag) {
242 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. */
243 SparseMatrix A = A0;
244 int m, n;
245 int i, j, k;
246 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
247 int *ia = NULL, *ja = NULL;
248 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
249 int iter = 0;
250 const bool adaptive_cooling = ctrl->adaptive_cooling;
251 double counts[4], *force = NULL;
252#ifdef TIME
253 clock_t start, end, start0;
254 double qtree_cpu = 0, qtree_new_cpu = 0;
255 double total_cpu = 0;
256 start0 = clock();
257#endif
258 int max_qtree_level = ctrl->max_qtree_level;
259
260 if (!A || maxiter <= 0) return;
261
262 m = A->m, n = A->n;
263 if (n <= 0 || dim <= 0) return;
264
265 oned_optimizer qtree_level_optimizer = oned_optimizer_new(max_qtree_level);
266
267 *flag = 0;
268 if (m != n) {
270 goto RETURN;
271 }
272 assert(A->format == FORMAT_CSR);
273 A = SparseMatrix_symmetrize(A, true);
274 ia = A->ia;
275 ja = A->ja;
276
277 if (ctrl->random_start){
278 srand(ctrl->random_seed);
279 for (i = 0; i < dim*n; i++) x[i] = drand();
280 }
281 if (K < 0){
282 ctrl->K = K = average_edge_length(A, dim, x);
283 }
284 if (p >= 0) ctrl->p = p = -1;
285 KP = pow(K, 1 - p);
286 CRK = pow(C, (2.-p)/3.)/K;
287
288 force = gv_calloc(dim * n, sizeof(double));
289
290 do {
291 iter++;
292 Fnorm0 = Fnorm;
293 Fnorm = 0.;
294
295 max_qtree_level = oned_optimizer_get(qtree_level_optimizer);
296
297#ifdef TIME
298 start = clock();
299#endif
300 QuadTree qt = QuadTree_new_from_point_list(dim, n, max_qtree_level, x);
301
302#ifdef TIME
303 qtree_new_cpu += (double)(clock() - start) / CLOCKS_PER_SEC;
304#endif
305
306 /* repulsive force */
307#ifdef TIME
308 start = clock();
309#endif
310
311 QuadTree_get_repulsive_force(qt, force, x, bh, p, KP, counts);
312
313#ifdef TIME
314 end = clock();
315 qtree_cpu += (double)(end - start) / CLOCKS_PER_SEC;
316#endif
317
318 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
319 for (i = 0; i < n; i++){
320 f = &(force[i*dim]);
321 for (j = ia[i]; j < ia[i+1]; j++){
322 if (ja[j] == i) continue;
323 dist = distance(x, dim, i, ja[j]);
324 for (k = 0; k < dim; k++){
325 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
326 }
327 }
328 }
329
330
331 /* move */
332 for (i = 0; i < n; i++){
333 f = &force[i*dim];
334 F = 0.;
335 for (k = 0; k < dim; k++) F += f[k]*f[k];
336 F = sqrt(F);
337 Fnorm += F;
338 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
339 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
340 }/* done vertex i */
341
342
343
344 if (qt) {
345#ifdef TIME
346 start = clock();
347#endif
348 QuadTree_delete(qt);
349#ifdef TIME
350 end = clock();
351 qtree_new_cpu += (double)(end - start) / CLOCKS_PER_SEC;
352#endif
353
354 oned_optimizer_train(&qtree_level_optimizer,
355 counts[0] + 0.85 * counts[1] + 3.3 * counts[2]);
356 } else {
357 if (Verbose) {
358 fprintf(stderr, "\r iter = %d, step = %f Fnorm = %f nz = %d K = %f ",iter, step, Fnorm, A->nz,K);
359 }
360 }
361
362 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
363 } while (step > tol && iter < maxiter);
364
365#ifdef DEBUG_PRINT
366 if (Verbose) {
367 fprintf(stderr, "\n iter = %d, step = %f Fnorm = %f nz = %d K = %f ",iter, step, Fnorm, A->nz, K);
368 }
369#endif
370
371 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
372
373#ifdef TIME
374 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
375 if (Verbose) fprintf(stderr, "\n time for qtree = %f, qtree_force = %f, total cpu = %f\n",qtree_new_cpu, qtree_cpu, total_cpu);
376#endif
377
378
379 RETURN:
380 ctrl->max_qtree_level = max_qtree_level;
381
382 if (A != A0) SparseMatrix_delete(A);
383 free(force);
384}
385
388 double *x, int *flag) {
389 /* 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. */
390 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. */
391 SparseMatrix A = A0;
392 int m, n;
393 int i, j, k;
394 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
395 int *ia = NULL, *ja = NULL;
396 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
397 int iter = 0;
398 const bool adaptive_cooling = ctrl->adaptive_cooling;
399 double *force;
400#ifdef TIME
401 clock_t start, end, start0, start2;
402 double total_cpu = 0;
403 start0 = clock();
404#endif
405
406 fprintf(stderr,"spring_electrical_embedding_slow");
407 if (!A || maxiter <= 0) return;
408
409 m = A->m, n = A->n;
410 if (n <= 0 || dim <= 0) return;
411 force = gv_calloc(n *dim, sizeof(double));
412
413 *flag = 0;
414 if (m != n) {
416 goto RETURN;
417 }
418 assert(A->format == FORMAT_CSR);
419 A = SparseMatrix_symmetrize(A, true);
420 ia = A->ia;
421 ja = A->ja;
422
423 if (ctrl->random_start){
424 srand(ctrl->random_seed);
425 for (i = 0; i < dim*n; i++) x[i] = drand();
426 }
427 if (K < 0){
428 ctrl->K = K = average_edge_length(A, dim, x);
429 }
430 if (p >= 0) ctrl->p = p = -1;
431 KP = pow(K, 1 - p);
432 CRK = pow(C, (2.-p)/3.)/K;
433
434 f = gv_calloc(dim, sizeof(double));
435 do {
436 for (i = 0; i < dim*n; i++) force[i] = 0;
437
438 iter++;
439 Fnorm0 = Fnorm;
440 Fnorm = 0.;
441
442#ifdef TIME
443 start2 = clock();
444#endif
445
446
447 for (i = 0; i < n; i++){
448 for (k = 0; k < dim; k++) f[k] = 0.;
449 /* repulsive force K^(1 - p)/||x_i-x_j||^(1 - p) (x_i - x_j) */
450 for (j = 0; j < n; j++){
451 if (j == i) continue;
452 dist = distance_cropped(x, dim, i, j);
453 for (k = 0; k < dim; k++){
454 f[k] += KP*(x[i*dim+k] - x[j*dim+k])/pow(dist, 1.- p);
455 }
456 }
457 for (k = 0; k < dim; k++) force[i*dim+k] += f[k];
458 }
459
460
461
462 for (i = 0; i < n; i++){
463 for (k = 0; k < dim; k++) f[k] = 0.;
464 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
465 for (j = ia[i]; j < ia[i+1]; j++){
466 if (ja[j] == i) continue;
467 dist = distance(x, dim, i, ja[j]);
468 for (k = 0; k < dim; k++){
469 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
470 }
471 }
472 for (k = 0; k < dim; k++) force[i*dim+k] += f[k];
473 }
474
475
476
477 for (i = 0; i < n; i++){
478 /* normalize force */
479 for (k = 0; k < dim; k++) f[k] = force[i*dim+k];
480
481 F = 0.;
482 for (k = 0; k < dim; k++) F += f[k]*f[k];
483 F = sqrt(F);
484 Fnorm += F;
485
486 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
487
488 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
489
490 }/* done vertex i */
491
492 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
493 } while (step > tol && iter < maxiter);
494
495#ifdef DEBUG_PRINT
496 if (Verbose) {
497 fprintf(stderr, "iter = %d, step = %f Fnorm = %f nsuper = 0 nz = %d K = %f ",iter, step, Fnorm, A->nz,K);
498 }
499#endif
500
501 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
502
503#ifdef TIME
504 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
505 if (Verbose) fprintf(stderr, "time for supernode = 0, total cpu = %f\n", total_cpu);
506#endif
507
508 RETURN:
509 if (A != A0) SparseMatrix_delete(A);
510 free(f);
511 free(force);
512}
513
515 spring_electrical_control *ctrl, double *x,
516 int *flag) {
517 /* x is a point to a 1D array, x[i*dim+j] gives the coordinate of the i-th node at dimension j. */
518 SparseMatrix A = A0;
519 int m, n;
520 int i, j, k;
521 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
522 int *ia = NULL, *ja = NULL;
523 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
524 int iter = 0;
525 const bool adaptive_cooling = ctrl->adaptive_cooling;
526 bool USE_QT = false;
527 int nsuper = 0, nsupermax = 10;
528 double *center = NULL, *supernode_wgts = NULL, *distances = NULL, nsuper_avg, counts = 0, counts_avg = 0;
529#ifdef TIME
530 clock_t start, end, start0, start2;
531 double qtree_cpu = 0;
532 double total_cpu = 0;
533 start0 = clock();
534#endif
535 int max_qtree_level = ctrl->max_qtree_level;
536 oned_optimizer qtree_level_optimizer = {0};
537
538 if (!A || maxiter <= 0) return;
539
540 m = A->m, n = A->n;
541 if (n <= 0 || dim <= 0) return;
542
543 if (n >= quadtree_size) {
544 USE_QT = true;
545 qtree_level_optimizer = oned_optimizer_new(max_qtree_level);
546 center = gv_calloc(nsupermax * dim, sizeof(double));
547 supernode_wgts = gv_calloc(nsupermax, sizeof(double));
548 distances = gv_calloc(nsupermax, sizeof(double));
549 }
550 *flag = 0;
551 if (m != n) {
553 goto RETURN;
554 }
555 assert(A->format == FORMAT_CSR);
556 A = SparseMatrix_symmetrize(A, true);
557 ia = A->ia;
558 ja = A->ja;
559
560 if (ctrl->random_start){
561 srand(ctrl->random_seed);
562 for (i = 0; i < dim*n; i++) x[i] = drand();
563 }
564 if (K < 0){
565 ctrl->K = K = average_edge_length(A, dim, x);
566 }
567 if (p >= 0) ctrl->p = p = -1;
568 KP = pow(K, 1 - p);
569 CRK = pow(C, (2.-p)/3.)/K;
570
571 f = gv_calloc(dim, sizeof(double));
572 do {
573
574 iter++;
575 Fnorm0 = Fnorm;
576 Fnorm = 0.;
577 nsuper_avg = 0;
578 counts_avg = 0;
579
580 QuadTree qt = NULL;
581 if (USE_QT) {
582
583 max_qtree_level = oned_optimizer_get(qtree_level_optimizer);
584 qt = QuadTree_new_from_point_list(dim, n, max_qtree_level, x);
585
586
587 }
588#ifdef TIME
589 start2 = clock();
590#endif
591
592 for (i = 0; i < n; i++){
593 for (k = 0; k < dim; k++) f[k] = 0.;
594 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
595 for (j = ia[i]; j < ia[i+1]; j++){
596 if (ja[j] == i) continue;
597 dist = distance(x, dim, i, ja[j]);
598 for (k = 0; k < dim; k++){
599 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
600 }
601 }
602
603 /* repulsive force K^(1 - p)/||x_i-x_j||^(1 - p) (x_i - x_j) */
604 if (USE_QT){
605#ifdef TIME
606 start = clock();
607#endif
608 QuadTree_get_supernodes(qt, bh, &(x[dim*i]), i, &nsuper, &nsupermax,
609 &center, &supernode_wgts, &distances, &counts);
610
611#ifdef TIME
612 end = clock();
613 qtree_cpu += (double)(end - start) / CLOCKS_PER_SEC;
614#endif
615 counts_avg += counts;
616 nsuper_avg += nsuper;
617 for (j = 0; j < nsuper; j++){
618 dist = MAX(distances[j], MINDIST);
619 for (k = 0; k < dim; k++){
620 f[k] += supernode_wgts[j]*KP*(x[i*dim+k] - center[j*dim+k])/pow(dist, 1.- p);
621 }
622 }
623 } else {
624 for (j = 0; j < n; j++){
625 if (j == i) continue;
626 dist = distance_cropped(x, dim, i, j);
627 for (k = 0; k < dim; k++){
628 f[k] += KP*(x[i*dim+k] - x[j*dim+k])/pow(dist, 1.- p);
629 }
630 }
631 }
632
633 /* normalize force */
634 F = 0.;
635 for (k = 0; k < dim; k++) F += f[k]*f[k];
636 F = sqrt(F);
637 Fnorm += F;
638
639 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
640
641 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
642
643 }/* done vertex i */
644
645 if (qt) {
646 QuadTree_delete(qt);
647 nsuper_avg /= n;
648 counts_avg /= n;
649 oned_optimizer_train(&qtree_level_optimizer, 5 * nsuper_avg + counts_avg);
650 }
651
652 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
653 } while (step > tol && iter < maxiter);
654
655#ifdef DEBUG_PRINT
656 if (Verbose) {
657 if (USE_QT){
658 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);
659 } else {
660 fprintf(stderr, "iter = %d, step = %f Fnorm = %f nsuper = %d nz = %d K = %f ",iter, step, Fnorm, (int) nsuper_avg,A->nz,K);
661 }
662 }
663#endif
664
665 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
666
667#ifdef TIME
668 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
669 if (Verbose) fprintf(stderr, "time for supernode = %f, total cpu = %f\n",qtree_cpu, total_cpu);
670#endif
671
672 RETURN:
673 if (USE_QT) {
674 ctrl->max_qtree_level = max_qtree_level;
675 }
676 if (A != A0) SparseMatrix_delete(A);
677 free(f);
678 free(center);
679 free(supernode_wgts);
680 free(distances);
681}
682
685 double *x, int *flag) {
686 /* 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
687 introduce force due to spring length
688 */
689 SparseMatrix A = A0;
690 int m, n;
691 int i, j, k;
692 double p = ctrl->p, K = ctrl->K, CRK, maxiter = ctrl->maxiter, step = ctrl->step, KP;
693 int *ia = NULL, *ja = NULL;
694 int *id = NULL, *jd = NULL;
695 double *d;
696 double *xold = NULL;
697 double *f = NULL, dist, F, Fnorm = 0, Fnorm0;
698 int iter = 0;
699 const bool adaptive_cooling = ctrl->adaptive_cooling;
700 bool USE_QT = false;
701 int nsuper = 0, nsupermax = 10;
702 double *center = NULL, *supernode_wgts = NULL, *distances = NULL, counts = 0;
703 int max_qtree_level = 10;
704
705 if (!A || maxiter <= 0) return;
706 m = A->m, n = A->n;
707 if (n <= 0 || dim <= 0) return;
708
709 if (n >= quadtree_size) {
710 USE_QT = true;
711 center = gv_calloc(nsupermax * dim, sizeof(double));
712 supernode_wgts = gv_calloc(nsupermax, sizeof(double));
713 distances = gv_calloc(nsupermax, sizeof(double));
714 }
715 *flag = 0;
716 if (m != n) {
718 goto RETURN;
719 }
720 assert(A->format == FORMAT_CSR);
721 A = SparseMatrix_symmetrize(A, true);
722 ia = A->ia;
723 ja = A->ja;
724 id = D->ia;
725 jd = D->ja;
726 d = D->a;
727
728 if (ctrl->random_start){
729 srand(ctrl->random_seed);
730 for (i = 0; i < dim*n; i++) x[i] = drand();
731 }
732 if (K < 0){
733 ctrl->K = K = average_edge_length(A, dim, x);
734 }
735 if (p >= 0) ctrl->p = p = -1;
736 KP = pow(K, 1 - p);
737 CRK = pow(C, (2.-p)/3.)/K;
738
739 f = gv_calloc(dim, sizeof(double));
740 xold = gv_calloc(dim * n, sizeof(double));
741 do {
742 iter++;
743 memcpy(xold, x, sizeof(double)*dim*n);
744 Fnorm0 = Fnorm;
745 Fnorm = 0.;
746
747 QuadTree qt = NULL;
748 if (USE_QT) {
749 qt = QuadTree_new_from_point_list(dim, n, max_qtree_level, x);
750 }
751
752 for (i = 0; i < n; i++){
753 for (k = 0; k < dim; k++) f[k] = 0.;
754 /* attractive force C^((2-p)/3) ||x_i-x_j||/K * (x_j - x_i) */
755
756 for (j = ia[i]; j < ia[i+1]; j++){
757 if (ja[j] == i) continue;
758 dist = distance(x, dim, i, ja[j]);
759 for (k = 0; k < dim; k++){
760 f[k] -= CRK*(x[i*dim+k] - x[ja[j]*dim+k])*dist;
761 }
762 }
763
764 for (j = id[i]; j < id[i+1]; j++){
765 if (jd[j] == i) continue;
766 dist = distance_cropped(x, dim, i, jd[j]);
767 for (k = 0; k < dim; k++){
768 if (dist < d[j]){
769 f[k] += 0.2*CRK*(x[i*dim+k] - x[jd[j]*dim+k])*(dist - d[j])*(dist - d[j])/dist;
770 } else {
771 f[k] -= 0.2*CRK*(x[i*dim+k] - x[jd[j]*dim+k])*(dist - d[j])*(dist - d[j])/dist;
772 }
773 /* f[k] -= 0.2*CRK*(x[i*dim+k] - x[jd[j]*dim+k])*(dist - d[j]);*/
774 }
775 }
776
777 /* repulsive force K^(1 - p)/||x_i-x_j||^(1 - p) (x_i - x_j) */
778 if (USE_QT){
779 QuadTree_get_supernodes(qt, bh, &x[dim * i], i, &nsuper, &nsupermax,
780 &center, &supernode_wgts, &distances, &counts);
781 for (j = 0; j < nsuper; j++){
782 dist = MAX(distances[j], MINDIST);
783 for (k = 0; k < dim; k++){
784 f[k] += supernode_wgts[j]*KP*(x[i*dim+k] - center[j*dim+k])/pow(dist, 1.- p);
785 }
786 }
787 } else {
788 for (j = 0; j < n; j++){
789 if (j == i) continue;
790 dist = distance_cropped(x, dim, i, j);
791 for (k = 0; k < dim; k++){
792 f[k] += KP*(x[i*dim+k] - x[j*dim+k])/pow(dist, 1.- p);
793 }
794 }
795 }
796
797 /* normalize force */
798 F = 0.;
799 for (k = 0; k < dim; k++) F += f[k]*f[k];
800 F = sqrt(F);
801 Fnorm += F;
802
803 if (F > 0) for (k = 0; k < dim; k++) f[k] /= F;
804
805 for (k = 0; k < dim; k++) x[i*dim+k] += step*f[k];
806
807 }/* done vertex i */
808
809 if (qt) QuadTree_delete(qt);
810
811 step = update_step(adaptive_cooling, step, Fnorm, Fnorm0);
812 } while (step > tol && iter < maxiter);
813
814 if (ctrl->beautify_leaves) beautify_leaves(dim, A, x);
815
816 RETURN:
817 free(xold);
818 if (A != A0) SparseMatrix_delete(A);
819 free(f);
820 free(center);
821 free(supernode_wgts);
822 free(distances);
823}
824
825static void interpolate_coord(int dim, SparseMatrix A, double *x) {
826 int i, j, k, *ia = A->ia, *ja = A->ja, nz;
827 double alpha = 0.5, beta;
828
829 double *y = gv_calloc(dim, sizeof(double));
830 for (i = 0; i < A->m; i++){
831 for (k = 0; k < dim; k++) y[k] = 0;
832 nz = 0;
833 for (j = ia[i]; j < ia[i+1]; j++){
834 if (ja[j] == i) continue;
835 nz++;
836 for (k = 0; k < dim; k++){
837 y[k] += x[ja[j]*dim + k];
838 }
839 }
840 if (nz > 0){
841 beta = (1-alpha)/nz;
842 for (k = 0; k < dim; k++) x[i*dim+k] = alpha*x[i*dim+k] + beta*y[k];
843 }
844 }
845
846 free(y);
847}
848static void prolongate(int dim, SparseMatrix A, SparseMatrix P, SparseMatrix R, double *x, double *y, double delta){
849 int nc, *ia, *ja, i, j, k;
851
853 nc = R->m;
854 ia = R->ia;
855 ja = R->ja;
856 for (i = 0; i < nc; i++){
857 for (j = ia[i]+1; j < ia[i+1]; j++){
858 for (k = 0; k < dim; k++){
859 y[ja[j]*dim + k] += delta*(drand() - 0.5);
860 }
861 }
862 }
863}
864
866 int m, max = 0, i, *ia = A->ia, *ja = A->ja, j, deg;
867 bool res = false;
868 m = A->m;
869 int *mask = gv_calloc(m + 1, sizeof(int));
870
871 for (i = 0; i < m + 1; i++){
872 mask[i] = 0;
873 }
874
875 for (i = 0; i < m; i++){
876 deg = 0;
877 for (j = ia[i]; j < ia[i+1]; j++){
878 if (i == ja[j]) continue;
879 deg++;
880 }
881 mask[deg]++;
882 max = MAX(max, mask[deg]);
883 }
884 if (mask[1] > 0.8*max && mask[1] > 0.3*m) res = true;
885 free(mask);
886 return res;
887}
888
889void pcp_rotate(int n, int dim, double *x){
890 int i, k,l;
891 double y[4], axis[2], center[2], dist, x0, x1;
892
893 assert(dim == 2);
894 for (i = 0; i < dim*dim; i++) y[i] = 0;
895 for (i = 0; i < dim; i++) center[i] = 0;
896 for (i = 0; i < n; i++){
897 for (k = 0; k < dim; k++){
898 center[k] += x[i*dim+k];
899 }
900 }
901 for (i = 0; i < dim; i++) center[i] /= n;
902 for (i = 0; i < n; i++){
903 for (k = 0; k < dim; k++){
904 x[dim*i+k] = x[dim*i+k] - center[k];
905 }
906 }
907
908 for (i = 0; i < n; i++){
909 for (k = 0; k < dim; k++){
910 for (l = 0; l < dim; l++){
911 y[dim*k+l] += x[i*dim+k]*x[i*dim+l];
912 }
913 }
914 }
915 if (y[1] == 0) {
916 axis[0] = 0; axis[1] = 1;
917 } else {
918 /* Eigensystem[{{x0, x1}, {x1, x3}}] =
919 {{(x0 + x3 - Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/2,
920 (x0 + x3 + Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/2},
921 {{-(-x0 + x3 + Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/(2*x1), 1},
922 {-(-x0 + x3 - Sqrt[x0^2 + 4*x1^2 - 2*x0*x3 + x3^2])/(2*x1), 1}}}
923 */
924 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]);
925 axis[1] = 1;
926 }
927 dist = sqrt(1+axis[0]*axis[0]);
928 axis[0] = axis[0]/dist;
929 axis[1] = axis[1]/dist;
930 for (i = 0; i < n; i++){
931 x0 = x[dim*i]*axis[0]+x[dim*i+1]*axis[1];
932 x1 = -x[dim*i]*axis[1]+x[dim*i+1]*axis[0];
933 x[dim*i] = x0;
934 x[dim*i + 1] = x1;
935
936 }
937
938
939}
940
941static void rotate(int n, int dim, double *x, double angle){
942 int i, k;
943 double axis[2], center[2], x0, x1;
944 double radian = 3.14159/180;
945
946 assert(dim == 2);
947 for (i = 0; i < dim; i++) center[i] = 0;
948 for (i = 0; i < n; i++){
949 for (k = 0; k < dim; k++){
950 center[k] += x[i*dim+k];
951 }
952 }
953 for (i = 0; i < dim; i++) center[i] /= n;
954 for (i = 0; i < n; i++){
955 for (k = 0; k < dim; k++){
956 x[dim*i+k] = x[dim*i+k] - center[k];
957 }
958 }
959 axis[0] = cos(-angle*radian);
960 axis[1] = sin(-angle*radian);
961 for (i = 0; i < n; i++){
962 x0 = x[dim*i]*axis[0]+x[dim*i+1]*axis[1];
963 x1 = -x[dim*i]*axis[1]+x[dim*i+1]*axis[0];
964 x[dim*i] = x0;
965 x[dim*i + 1] = x1;
966 }
967
968
969}
970
971static void attach_edge_label_coordinates(int dim, SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes, double *x, double *x2){
972 int i, ii, j, k;
973 int nnodes = 0;
974 double len;
975
976 int *mask = gv_calloc(A->m, sizeof(int));
977
978 for (i = 0; i < A->m; i++) mask[i] = 1;
979 for (i = 0; i < n_edge_label_nodes; i++) {
980 if (edge_label_nodes[i] >= 0 && edge_label_nodes[i] < A->m) mask[edge_label_nodes[i]] = -1;
981 }
982
983 for (i = 0; i < A->m; i++) {
984 if (mask[i] >= 0) mask[i] = nnodes++;
985 }
986
987
988 for (i = 0; i < A->m; i++){
989 if (mask[i] >= 0){
990 for (k = 0; k < dim; k++) x[i*dim+k] = x2[mask[i]*dim+k];
991 }
992 }
993
994 for (i = 0; i < n_edge_label_nodes; i++){
995 ii = edge_label_nodes[i];
996 len = A->ia[ii+1] - A->ia[ii];
997 assert(len >= 2); /* should just be 2 */
998 assert(mask[ii] < 0);
999 for (k = 0; k < dim; k++) {
1000 x[ii*dim+k] = 0;
1001 }
1002 for (j = A->ia[ii]; j < A->ia[ii+1]; j++){
1003 for (k = 0; k < dim; k++){
1004 x[ii * dim + k] += x[A->ja[j] * dim + k];
1005 }
1006 }
1007 for (k = 0; k < dim; k++) {
1008 x[ii*dim+k] /= len;
1009 }
1010 }
1011
1012 free(mask);
1013}
1014
1015static SparseMatrix shorting_edge_label_nodes(SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes){
1016 int i, id = 0, nz, j, jj, ii;
1017 int *ia = A->ia, *ja = A->ja, *irn = NULL, *jcn = NULL;
1019
1020 int *mask = gv_calloc(A->m, sizeof(int));
1021
1022 for (i = 0; i < A->m; i++) mask[i] = 1;
1023
1024 for (i = 0; i < n_edge_label_nodes; i++){
1025 mask[edge_label_nodes[i]] = -1;
1026 }
1027
1028 for (i = 0; i < A->m; i++) {
1029 if (mask[i] > 0) mask[i] = id++;
1030 }
1031
1032 nz = 0;
1033 for (i = 0; i < A->m; i++){
1034 if (mask[i] < 0) continue;
1035 for (j = ia[i]; j < ia[i+1]; j++){
1036 if (mask[ja[j]] >= 0) {
1037 nz++;
1038 continue;
1039 }
1040 ii = ja[j];
1041 for (jj = ia[ii]; jj < ia[ii+1]; jj++){
1042 if (ja[jj] != i && mask[ja[jj]] >= 0) nz++;
1043 }
1044 }
1045 }
1046
1047 if (nz > 0) {
1048 irn = gv_calloc(nz, sizeof(int));
1049 jcn = gv_calloc(nz, sizeof(int));
1050 }
1051
1052 nz = 0;
1053 for (i = 0; i < A->m; i++){
1054 if (mask[i] < 0) continue;
1055 for (j = ia[i]; j < ia[i+1]; j++){
1056 if (mask[ja[j]] >= 0) {
1057 irn[nz] = mask[i];
1058 jcn[nz++] = mask[ja[j]];
1059 continue;
1060 }
1061 ii = ja[j];
1062 for (jj = ia[ii]; jj < ia[ii+1]; jj++){
1063 if (ja[jj] != i && mask[ja[jj]] >= 0) {
1064 irn[nz] = mask[i];
1065 jcn[nz++] = mask[ja[jj]];
1066 }
1067 }
1068 }
1069 }
1070
1071 B = SparseMatrix_from_coordinate_arrays(nz, id, id, irn, jcn, NULL, MATRIX_TYPE_PATTERN, sizeof(double));
1072
1073 free(irn);
1074 free(jcn);
1075 free(mask);
1076 return B;
1077
1078}
1079
1082 double *label_sizes, double *x,
1083 int n_edge_label_nodes,
1084 int *edge_label_nodes, int *flag) {
1085
1086 int n;
1087 SparseMatrix A = A0, P = NULL;
1088 Multilevel grid, grid0;
1089 double *xc = NULL, *xf = NULL;
1090#ifdef TIME
1091 clock_t cpu;
1092#endif
1093
1094 const spring_electrical_control ctrl0 = *ctrl;
1095
1096#ifdef TIME
1097 cpu = clock();
1098#endif
1099
1100 *flag = 0;
1101 if (!A) return;
1102 n = A->n;
1103 if (n <= 0 || dim <= 0) return;
1104
1105 if (!SparseMatrix_is_symmetric(A, false) || A->type != MATRIX_TYPE_REAL){
1107 } else {
1109 }
1110
1111 /* we first generate a layout discarding (shorting) the edge labels nodes, then assign the edge label nodes at the average of their neighbors */
1113 && n_edge_label_nodes > 0){
1114 SparseMatrix A2;
1115
1116 double *x2 = gv_calloc(A->m * dim, sizeof(double));
1117 A2 = shorting_edge_label_nodes(A, n_edge_label_nodes, edge_label_nodes);
1118 multilevel_spring_electrical_embedding(dim, A2, ctrl, NULL, x2, 0, NULL, flag);
1119
1120 assert(!*flag);
1121 attach_edge_label_coordinates(dim, A, n_edge_label_nodes, edge_label_nodes, x, x2);
1122 remove_overlap(dim, A, x, label_sizes, ctrl->overlap, ctrl->initial_scaling,
1123 ctrl->edge_labeling_scheme, n_edge_label_nodes, edge_label_nodes, A, ctrl->do_shrinking);
1125 free(x2);
1126 if (A != A0) SparseMatrix_delete(A);
1127
1128 return;
1129 }
1130
1131 Multilevel_control mctrl = {.maxlevel = ctrl->multilevels};
1132 grid0 = Multilevel_new(A, mctrl);
1133
1136 xc = x;
1137 } else {
1138 xc = gv_calloc(grid->n * dim, sizeof(double));
1139 }
1140
1141 const bool plg = power_law_graph(A);
1142 if (ctrl->p == AUTOP){
1143 ctrl->p = -1;
1144 if (plg) ctrl->p = -1.8;
1145 }
1146
1147 do {
1148#ifdef DEBUG_PRINT
1149 if (Verbose) {
1150 print_padding(grid->level);
1152 fprintf(stderr, "coarsest level -- %d, n = %d\n", grid->level, grid->n);
1153 } else {
1154 fprintf(stderr, "level -- %d, n = %d\n", grid->level, grid->n);
1155 }
1156 }
1157#endif
1158 if (ctrl->tscheme == QUAD_TREE_NONE){
1159 spring_electrical_embedding_slow(dim, grid->A, ctrl, xc, flag);
1160 } else if (ctrl->tscheme == QUAD_TREE_FAST || (ctrl->tscheme == QUAD_TREE_HYBRID && grid->A->m > QUAD_TREE_HYBRID_SIZE)){
1161 if (ctrl->tscheme == QUAD_TREE_HYBRID && grid->A->m > 10 && Verbose){
1162 fprintf(stderr, "QUAD_TREE_HYBRID, size larger than %d, switch to fast quadtree", QUAD_TREE_HYBRID_SIZE);
1163 }
1164 spring_electrical_embedding_fast(dim, grid->A, ctrl, xc, flag);
1165 } else {
1166 spring_electrical_embedding(dim, grid->A, ctrl, xc, flag);
1167 }
1168 if (Multilevel_is_finest(grid)) break;
1169 if (*flag) {
1170 free(xc);
1171 goto RETURN;
1172 }
1173 P = grid->P;
1174 grid = grid->prev;
1176 xf = x;
1177 } else {
1178 xf = gv_calloc(grid->n * dim, sizeof(double));
1179 }
1180 prolongate(dim, grid->A, P, grid->R, xc, xf, ctrl->K * 0.001);
1181 free(xc);
1182 xc = xf;
1183 ctrl->random_start = false;
1184 ctrl->K = ctrl->K * 0.75;
1185 ctrl->adaptive_cooling = false;
1186 ctrl->step = .1;
1187 } while (grid);
1188
1189#ifdef TIME
1190 if (Verbose)
1191 fprintf(stderr, "layout time %f\n", (double)(clock() - cpu) / CLOCKS_PER_SEC);
1192 cpu = clock();
1193#endif
1194
1195 post_process_smoothing(dim, A, *ctrl, x);
1196
1197 if (Verbose) fprintf(stderr, "ctrl->overlap=%d\n",ctrl->overlap);
1198
1199 /* rotation has to be done before overlap removal, since rotation could induce overlaps */
1200 if (dim == 2){
1201 pcp_rotate(n, dim, x);
1202 }
1203 if (ctrl->rotation != 0) rotate(n, dim, x, ctrl->rotation);
1204
1205
1206 remove_overlap(dim, A, x, label_sizes, ctrl->overlap, ctrl->initial_scaling,
1207 ctrl->edge_labeling_scheme, n_edge_label_nodes, edge_label_nodes, A, ctrl->do_shrinking);
1208
1209 RETURN:
1210 *ctrl = ctrl0;
1211 if (A != A0) SparseMatrix_delete(A);
1212 Multilevel_delete(grid0);
1213 }
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)
@ MATRIX_TYPE_REAL
@ MATRIX_TYPE_PATTERN
@ FORMAT_CSR
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:47
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
Definition bitarray.h:65
static void bitarray_set(bitarray_t *self, size_t index, bool value)
set or clear the value of the given element
Definition bitarray.h:80
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
Definition bitarray.h:114
#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:136
static bool Verbose
Definition gml2gv.c:24
void free(void *)
node NULL
Definition grammar.y:181
@ grid
Definition gvgen.c:33
#define B
Definition hierarchy.c:118
#define D
Definition hierarchy.c:120
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_IS_EMPTY(list)
Definition list.h:90
#define LIST_GET(list, index)
Definition list.h:165
#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:35
@ ELSCHEME_STRAIGHTLINE_PENALTY
Definition overlap.h:35
void post_process_smoothing(int dim, SparseMatrix A, spring_electrical_control ctrl, double *x)
pointf coord(node_t *n)
Definition utils.c:153
#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)
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)
@ OPT_INIT
@ OPT_DOWN
@ OPT_UP
@ MAX_I
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)
@ QUAD_TREE_HYBRID_SIZE
@ ERROR_NOT_SQUARE_MATRIX
@ QUAD_TREE_FAST
@ QUAD_TREE_HYBRID
@ QUAD_TREE_NONE
#define AUTOP
@ SMOOTHING_NONE
#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 existing layout
double p
a negative real number default to -1. repulsive force = distáµ–
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:32