33static const double C = 0.2;
40static const double bh = 0.6;
44static const double tol = 0.001;
46static const double cool = 0.90;
72 "NONE",
"STRESS_MAJORIZATION_GRAPH_DIST",
"STRESS_MAJORIZATION_AVG_DIST",
"STRESS_MAJORIZATION_POWER_DIST",
"SPRING",
"TRIANGLE",
"RNG"
76 "NONE",
"NORMAL",
"FAST",
"HYBRID"
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,
84 fprintf (stderr,
" K : %.03f C : %.03f\n", ctrl.
K,
C);
85 fprintf (stderr,
" max levels %d\n", ctrl.
multilevels);
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,
90 fprintf (stderr,
" beautify_leaves %d node weights %d rotation %.03f\n",
92 fprintf (stderr,
" smoothing %s overlap %d initial_scaling %.03f do_shrinking %d\n",
136 if (opt->
work[i] < opt->
work[i+1] && opt->
i > 0){
137 opt->
i =
MAX(0, opt->
i-1);
152 int *ia =
A->ia, *ja =
A->ja, i, j, k;
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++){
159 for (k = 0; k <
dim; k++){
165 return dist/ia[
A->m];
168static double update_step(
bool adaptive_cooling,
double step,
double Fnorm,
171 if (!adaptive_cooling) {
174 if (Fnorm >= Fnorm0){
176 }
else if (Fnorm > 0.95*Fnorm0){
179 step = 0.99*step/
cool;
185#define node_degree(i) (ia[(i)+1] - ia[(i)])
193 int m =
A->m, i, j, *ia =
A->ia, *ja =
A->ja;
202 for (i = 0; i < m; i++){
203 if (ia[i+1] - ia[i] != 1)
continue;
209 LIST(
int) leaves = {0};
210 for (j = ia[p]; j < ia[p+1]; j++){
220 double ang2 = 2 *
M_PI;
221 const double pad = 0.1;
225 assert(ang2 >= ang1);
228 for (
size_t k = 0; k <
LIST_SIZE(&leaves); k++) {
241 double *x,
int *flag) {
246 double p = ctrl->
p, K = ctrl->
K, CRK, maxiter = ctrl->
maxiter, step = ctrl->
step, KP;
248 double *f =
NULL,
dist,
F, Fnorm = 0, Fnorm0;
251 double counts[4], *force =
NULL;
253 clock_t start, end, start0;
254 double qtree_cpu = 0, qtree_new_cpu = 0;
255 double total_cpu = 0;
260 if (!
A || maxiter <= 0)
return;
263 if (n <= 0 ||
dim <= 0)
return;
279 for (i = 0; i <
dim*n; i++) x[i] =
drand();
284 if (p >= 0) ctrl->
p = p = -1;
286 CRK = pow(
C, (2.-p)/3.)/K;
303 qtree_new_cpu += (double)(clock() - start) / CLOCKS_PER_SEC;
315 qtree_cpu += (double)(end - start) / CLOCKS_PER_SEC;
319 for (i = 0; i < n; i++){
321 for (j = ia[i]; j < ia[i+1]; j++){
322 if (ja[j] == i)
continue;
324 for (k = 0; k <
dim; k++){
325 f[k] -= CRK*(x[i*
dim+k] - x[ja[j]*
dim+k])*
dist;
332 for (i = 0; i < n; i++){
335 for (k = 0; k <
dim; k++)
F += f[k]*f[k];
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];
351 qtree_new_cpu += (double)(end - start) / CLOCKS_PER_SEC;
355 counts[0] + 0.85 * counts[1] + 3.3 * counts[2]);
358 fprintf(stderr,
"\r iter = %d, step = %f Fnorm = %f nz = %d K = %f ",iter, step, Fnorm,
A->nz,K);
362 step =
update_step(adaptive_cooling, step, Fnorm, Fnorm0);
363 }
while (step >
tol && iter < maxiter);
367 fprintf(stderr,
"\n iter = %d, step = %f Fnorm = %f nz = %d K = %f ",iter, step, Fnorm,
A->nz, K);
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);
388 double *x,
int *flag) {
394 double p = ctrl->
p, K = ctrl->
K, CRK, maxiter = ctrl->
maxiter, step = ctrl->
step, KP;
396 double *f =
NULL,
dist,
F, Fnorm = 0, Fnorm0;
401 clock_t start, end, start0, start2;
402 double total_cpu = 0;
406 fprintf(stderr,
"spring_electrical_embedding_slow");
407 if (!
A || maxiter <= 0)
return;
410 if (n <= 0 ||
dim <= 0)
return;
425 for (i = 0; i <
dim*n; i++) x[i] =
drand();
430 if (p >= 0) ctrl->
p = p = -1;
432 CRK = pow(
C, (2.-p)/3.)/K;
436 for (i = 0; i <
dim*n; i++) force[i] = 0;
447 for (i = 0; i < n; i++){
448 for (k = 0; k <
dim; k++) f[k] = 0.;
450 for (j = 0; j < n; j++){
451 if (j == i)
continue;
453 for (k = 0; k <
dim; k++){
454 f[k] += KP*(x[i*
dim+k] - x[j*
dim+k])/pow(
dist, 1.- p);
457 for (k = 0; k <
dim; k++) force[i*
dim+k] += f[k];
462 for (i = 0; i < n; i++){
463 for (k = 0; k <
dim; k++) f[k] = 0.;
465 for (j = ia[i]; j < ia[i+1]; j++){
466 if (ja[j] == i)
continue;
468 for (k = 0; k <
dim; k++){
469 f[k] -= CRK*(x[i*
dim+k] - x[ja[j]*
dim+k])*
dist;
472 for (k = 0; k <
dim; k++) force[i*
dim+k] += f[k];
477 for (i = 0; i < n; i++){
479 for (k = 0; k <
dim; k++) f[k] = force[i*
dim+k];
482 for (k = 0; k <
dim; k++)
F += f[k]*f[k];
486 if (
F > 0)
for (k = 0; k <
dim; k++) f[k] /=
F;
488 for (k = 0; k <
dim; k++) x[i*
dim+k] += step*f[k];
492 step =
update_step(adaptive_cooling, step, Fnorm, Fnorm0);
493 }
while (step >
tol && iter < maxiter);
497 fprintf(stderr,
"iter = %d, step = %f Fnorm = %f nsuper = 0 nz = %d K = %f ",iter, step, Fnorm,
A->nz,K);
504 total_cpu += (double)(clock() - start0) / CLOCKS_PER_SEC;
505 if (
Verbose) fprintf(stderr,
"time for supernode = 0, total cpu = %f\n", total_cpu);
521 double p = ctrl->
p, K = ctrl->
K, CRK, maxiter = ctrl->
maxiter, step = ctrl->
step, KP;
523 double *f =
NULL,
dist,
F, Fnorm = 0, Fnorm0;
527 int nsuper = 0, nsupermax = 10;
528 double *
center =
NULL, *supernode_wgts =
NULL, *distances =
NULL, nsuper_avg, counts = 0, counts_avg = 0;
530 clock_t start, end, start0, start2;
531 double qtree_cpu = 0;
532 double total_cpu = 0;
538 if (!
A || maxiter <= 0)
return;
541 if (n <= 0 ||
dim <= 0)
return;
547 supernode_wgts =
gv_calloc(nsupermax,
sizeof(
double));
548 distances =
gv_calloc(nsupermax,
sizeof(
double));
562 for (i = 0; i <
dim*n; i++) x[i] =
drand();
567 if (p >= 0) ctrl->
p = p = -1;
569 CRK = pow(
C, (2.-p)/3.)/K;
592 for (i = 0; i < n; i++){
593 for (k = 0; k <
dim; k++) f[k] = 0.;
595 for (j = ia[i]; j < ia[i+1]; j++){
596 if (ja[j] == i)
continue;
598 for (k = 0; k <
dim; k++){
599 f[k] -= CRK*(x[i*
dim+k] - x[ja[j]*
dim+k])*
dist;
609 &
center, &supernode_wgts, &distances, &counts);
613 qtree_cpu += (double)(end - start) / CLOCKS_PER_SEC;
615 counts_avg += counts;
616 nsuper_avg += nsuper;
617 for (j = 0; j < nsuper; j++){
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);
624 for (j = 0; j < n; j++){
625 if (j == i)
continue;
627 for (k = 0; k <
dim; k++){
628 f[k] += KP*(x[i*
dim+k] - x[j*
dim+k])/pow(
dist, 1.- p);
635 for (k = 0; k <
dim; k++)
F += f[k]*f[k];
639 if (
F > 0)
for (k = 0; k <
dim; k++) f[k] /=
F;
641 for (k = 0; k <
dim; k++) x[i*
dim+k] += step*f[k];
652 step =
update_step(adaptive_cooling, step, Fnorm, Fnorm0);
653 }
while (step >
tol && iter < maxiter);
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);
660 fprintf(stderr,
"iter = %d, step = %f Fnorm = %f nsuper = %d nz = %d K = %f ",iter, step, Fnorm, (
int) nsuper_avg,
A->nz,K);
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);
679 free(supernode_wgts);
685 double *x,
int *flag) {
692 double p = ctrl->
p, K = ctrl->
K, CRK, maxiter = ctrl->
maxiter, step = ctrl->
step, KP;
697 double *f =
NULL,
dist,
F, Fnorm = 0, Fnorm0;
701 int nsuper = 0, nsupermax = 10;
703 int max_qtree_level = 10;
705 if (!
A || maxiter <= 0)
return;
707 if (n <= 0 ||
dim <= 0)
return;
712 supernode_wgts =
gv_calloc(nsupermax,
sizeof(
double));
713 distances =
gv_calloc(nsupermax,
sizeof(
double));
730 for (i = 0; i <
dim*n; i++) x[i] =
drand();
735 if (p >= 0) ctrl->
p = p = -1;
737 CRK = pow(
C, (2.-p)/3.)/K;
743 memcpy(xold, x,
sizeof(
double)*
dim*n);
752 for (i = 0; i < n; i++){
753 for (k = 0; k <
dim; k++) f[k] = 0.;
756 for (j = ia[i]; j < ia[i+1]; j++){
757 if (ja[j] == i)
continue;
759 for (k = 0; k <
dim; k++){
760 f[k] -= CRK*(x[i*
dim+k] - x[ja[j]*
dim+k])*
dist;
764 for (j =
id[i]; j <
id[i+1]; j++){
765 if (jd[j] == i)
continue;
767 for (k = 0; k <
dim; k++){
780 &
center, &supernode_wgts, &distances, &counts);
781 for (j = 0; j < nsuper; j++){
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);
788 for (j = 0; j < n; j++){
789 if (j == i)
continue;
791 for (k = 0; k <
dim; k++){
792 f[k] += KP*(x[i*
dim+k] - x[j*
dim+k])/pow(
dist, 1.- p);
799 for (k = 0; k <
dim; k++)
F += f[k]*f[k];
803 if (
F > 0)
for (k = 0; k <
dim; k++) f[k] /=
F;
805 for (k = 0; k <
dim; k++) x[i*
dim+k] += step*f[k];
811 step =
update_step(adaptive_cooling, step, Fnorm, Fnorm0);
812 }
while (step >
tol && iter < maxiter);
821 free(supernode_wgts);
826 int i, j, k, *ia =
A->ia, *ja =
A->ja, nz;
827 double alpha = 0.5, beta;
830 for (i = 0; i <
A->m; i++){
831 for (k = 0; k <
dim; k++) y[k] = 0;
833 for (j = ia[i]; j < ia[i+1]; j++){
834 if (ja[j] == i)
continue;
836 for (k = 0; k <
dim; k++){
837 y[k] += x[ja[j]*
dim + k];
842 for (k = 0; k <
dim; k++) x[i*
dim+k] =
alpha*x[i*
dim+k] + beta*y[k];
849 int nc, *ia, *ja, i, j, k;
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++){
866 int m, max = 0, i, *ia =
A->ia, *ja =
A->ja, j, deg;
869 int *mask =
gv_calloc(m + 1,
sizeof(
int));
871 for (i = 0; i < m + 1; i++){
875 for (i = 0; i < m; i++){
877 for (j = ia[i]; j < ia[i+1]; j++){
878 if (i == ja[j])
continue;
882 max =
MAX(max, mask[deg]);
884 if (mask[1] > 0.8*max && mask[1] > 0.3*m) res =
true;
891 double y[4], axis[2],
center[2],
dist, x0, x1;
894 for (i = 0; i <
dim*
dim; i++) y[i] = 0;
896 for (i = 0; i < n; i++){
897 for (k = 0; k <
dim; k++){
901 for (i = 0; i <
dim; i++)
center[i] /= n;
902 for (i = 0; i < n; i++){
903 for (k = 0; k <
dim; k++){
908 for (i = 0; i < n; i++){
909 for (k = 0; k <
dim; k++){
910 for (l = 0; l <
dim; l++){
916 axis[0] = 0; axis[1] = 1;
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]);
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];
941static void rotate(
int n,
int dim,
double *x,
double angle){
943 double axis[2],
center[2], x0, x1;
944 double radian = 3.14159/180;
948 for (i = 0; i < n; i++){
949 for (k = 0; k <
dim; k++){
953 for (i = 0; i <
dim; i++)
center[i] /= n;
954 for (i = 0; i < n; i++){
955 for (k = 0; k <
dim; k++){
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];
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;
983 for (i = 0; i <
A->m; i++) {
984 if (mask[i] >= 0) mask[i] = nnodes++;
988 for (i = 0; i <
A->m; i++){
990 for (k = 0; k <
dim; k++) x[i*
dim+k] = x2[mask[i]*
dim+k];
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];
998 assert(mask[ii] < 0);
999 for (k = 0; k <
dim; k++) {
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];
1007 for (k = 0; k <
dim; k++) {
1016 int i,
id = 0, nz, j, jj, ii;
1017 int *ia =
A->
ia, *ja =
A->ja, *irn =
NULL, *jcn =
NULL;
1022 for (i = 0; i <
A->m; i++) mask[i] = 1;
1024 for (i = 0; i < n_edge_label_nodes; i++){
1025 mask[edge_label_nodes[i]] = -1;
1028 for (i = 0; i <
A->m; i++) {
1029 if (mask[i] > 0) mask[i] =
id++;
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) {
1041 for (jj = ia[ii]; jj < ia[ii+1]; jj++){
1042 if (ja[jj] != i && mask[ja[jj]] >= 0) nz++;
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) {
1058 jcn[nz++] = mask[ja[j]];
1062 for (jj = ia[ii]; jj < ia[ii+1]; jj++){
1063 if (ja[jj] != i && mask[ja[jj]] >= 0) {
1065 jcn[nz++] = mask[ja[jj]];
1082 double *label_sizes,
double *x,
1083 int n_edge_label_nodes,
1084 int *edge_label_nodes,
int *flag) {
1103 if (n <= 0 ||
dim <= 0)
return;
1113 && n_edge_label_nodes > 0){
1144 if (plg) ctrl->
p = -1.8;
1152 fprintf(stderr,
"coarsest level -- %d, n = %d\n",
grid->level,
grid->n);
1154 fprintf(stderr,
"level -- %d, n = %d\n",
grid->level,
grid->n);
1162 fprintf(stderr,
"QUAD_TREE_HYBRID, size larger than %d, switch to fast quadtree",
QUAD_TREE_HYBRID_SIZE);
1184 ctrl->
K = ctrl->
K * 0.75;
1191 fprintf(stderr,
"layout time %f\n", (
double)(clock() - cpu) / CLOCKS_PER_SEC);
1197 if (
Verbose) fprintf(stderr,
"ctrl->overlap=%d\n",ctrl->
overlap);
void print_padding(int n)
Multilevel Multilevel_get_coarsest(Multilevel grid)
void Multilevel_delete(Multilevel grid)
Multilevel Multilevel_new(SparseMatrix A0, const Multilevel_control ctrl)
#define Multilevel_is_coarsest(grid)
#define Multilevel_is_finest(grid)
void QuadTree_get_repulsive_force(QuadTree qt, double *force, double *x, double bh, double p, double KP, double *counts)
QuadTree QuadTree_new_from_point_list(int dim, int n, int max_level, double *coord)
void QuadTree_delete(QuadTree q)
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)
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)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
API for compacted arrays of booleans.
static bitarray_t bitarray_new(size_t size_bits)
create an array of the given element length
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
static void bitarray_set(bitarray_t *self, size_t index, bool value)
set or clear the value of the given element
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
static double dist(int dim, double *x, double *y)
double distance(double *x, int dim, int i, int j)
double distance_cropped(double *x, int dim, int i, int j)
static double len(glCompPoint p)
type-generic dynamically expanding list
#define LIST_APPEND(list, item)
#define LIST_IS_EMPTY(list)
#define LIST_GET(list, index)
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)
@ ELSCHEME_STRAIGHTLINE_PENALTY2
@ ELSCHEME_STRAIGHTLINE_PENALTY
void post_process_smoothing(int dim, SparseMatrix A, spring_electrical_control ctrl, double *x)
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 void attach_edge_label_coordinates(int dim, SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes, double *x, double *x2)
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 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)
static void interpolate_coord(int dim, SparseMatrix A, double *x)
@ ERROR_NOT_SQUARE_MATRIX
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