Graphviz  2.39.20141219.0545
stuff.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #ifdef HAVE_CONFIG_H
16 #include "config.h"
17 #endif
18 
19 #include "neato.h"
20 #include "stress.h"
21 #include <time.h>
22 #ifndef WIN32
23 #include <unistd.h>
24 #endif
25 
26 static double Epsilon2;
27 
28 
29 double fpow32(double x)
30 {
31  x = sqrt(x);
32  return x * x * x;
33 }
34 
35 double distvec(double *p0, double *p1, double *vec)
36 {
37  int k;
38  double dist = 0.0;
39 
40  for (k = 0; k < Ndim; k++) {
41  vec[k] = p0[k] - p1[k];
42  dist += (vec[k] * vec[k]);
43  }
44  dist = sqrt(dist);
45  return dist;
46 }
47 
48 double **new_array(int m, int n, double ival)
49 {
50  double **rv;
51  double *mem;
52  int i, j;
53 
54  rv = N_NEW(m, double *);
55  mem = N_NEW(m * n, double);
56  for (i = 0; i < m; i++) {
57  rv[i] = mem;
58  mem = mem + n;
59  for (j = 0; j < n; j++)
60  rv[i][j] = ival;
61  }
62  return rv;
63 }
64 
65 void free_array(double **rv)
66 {
67  if (rv) {
68  free(rv[0]);
69  free(rv);
70  }
71 }
72 
73 
74 static double ***new_3array(int m, int n, int p, double ival)
75 {
76  double ***rv;
77  int i, j, k;
78 
79  rv = N_NEW(m + 1, double **);
80  for (i = 0; i < m; i++) {
81  rv[i] = N_NEW(n + 1, double *);
82  for (j = 0; j < n; j++) {
83  rv[i][j] = N_NEW(p, double);
84  for (k = 0; k < p; k++)
85  rv[i][j][k] = ival;
86  }
87  rv[i][j] = NULL; /* NULL terminate so we can clean up */
88  }
89  rv[i] = NULL;
90  return rv;
91 }
92 
93 static void free_3array(double ***rv)
94 {
95  int i, j;
96 
97  if (rv) {
98  for (i = 0; rv[i]; i++) {
99  for (j = 0; rv[i][j]; j++)
100  free(rv[i][j]);
101  free(rv[i]);
102  }
103  free(rv);
104  }
105 }
106 
107 
108 /* lenattr:
109  * Return 1 if attribute not defined
110  * Return 2 if attribute string bad
111  */
112 static int lenattr(edge_t* e, Agsym_t* index, double* val)
113 {
114  char* s;
115 
116  if (index == NULL)
117  return 1;
118 
119  s = agxget(e, index);
120  if (*s == '\0') return 1;
121 
122  if ((sscanf(s, "%lf", val) < 1) || (*val < 0) || ((*val == 0) && !Nop)) {
123  agerr(AGWARN, "bad edge len \"%s\"", s);
124  return 2;
125  }
126  else
127  return 0;
128 }
129 
130 
131 /* degreeKind;
132  * Returns degree of n ignoring loops and multiedges.
133  * Returns 0, 1 or many (2)
134  * For case of 1, returns other endpoint of edge.
135  */
136 static int degreeKind(graph_t * g, node_t * n, node_t ** op)
137 {
138  edge_t *ep;
139  int deg = 0;
140  node_t *other = NULL;
141 
142  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
143  if (aghead(ep) == agtail(ep))
144  continue; /* ignore loops */
145  if (deg == 1) {
146  if (((agtail(ep) == n) && (aghead(ep) == other)) || /* ignore multiedge */
147  ((agtail(ep) == other) && (aghead(ep) == n)))
148  continue;
149  return 2;
150  } else { /* deg == 0 */
151  if (agtail(ep) == n)
152  other = aghead(ep);
153  else
154  other = agtail(ep);
155  *op = other;
156  deg++;
157  }
158  }
159  return deg;
160 }
161 
162 
163 /* prune:
164  * np is at end of a chain. If its degree is 0, remove it.
165  * If its degree is 1, remove it and recurse.
166  * If its degree > 1, stop.
167  * The node next is the next node to be visited during iteration.
168  * If it is equal to a node being deleted, set it to next one.
169  * Delete from root graph, since G may be a connected component subgraph.
170  * Return next.
171  */
172 static node_t *prune(graph_t * G, node_t * np, node_t * next)
173 {
174  node_t *other;
175  int deg;
176 
177  while (np) {
178  deg = degreeKind(G, np, &other);
179  if (deg == 0) {
180  if (next == np)
181  next = agnxtnode(G, np);
182  agdelete(G->root, np);
183  np = 0;
184  } else if (deg == 1) {
185  if (next == np)
186  next = agnxtnode(G, np);
187  agdelete(G->root, np);
188  np = other;
189  } else
190  np = 0;
191 
192  }
193  return next;
194 }
195 
196 static double setEdgeLen(graph_t * G, node_t * np, Agsym_t* lenx, double dfltlen)
197 {
198  edge_t *ep;
199  double total_len = 0.0;
200  double len;
201  int err;
202 
203  for (ep = agfstout(G, np); ep; ep = agnxtout(G, ep)) {
204  if ((err = lenattr(ep, lenx, &len))) {
205  if (err == 2) agerr(AGPREV, " in %s - setting to %.02f\n", agnameof(G), dfltlen);
206  len = dfltlen;
207  }
208  ED_dist(ep) = len;
209  total_len += len;
210  }
211  return total_len;
212 }
213 
214 /* scan_graph_mode:
215  * Prepare the graph and data structures depending on the layout mode.
216  * If Reduce is true, eliminate singletons and trees. Since G may be a
217  * subgraph, we remove the nodes from the root graph.
218  * Return the number of nodes in the reduced graph.
219  */
220 int scan_graph_mode(graph_t * G, int mode)
221 {
222  int i, nV, nE, deg;
223  char *str;
224  node_t *np, *xp, *other;
225  double total_len = 0.0;
226  double dfltlen = 1.0;
227  Agsym_t* lenx;
228 
229  if (Verbose)
230  fprintf(stderr, "Scanning graph %s, %d nodes\n", agnameof(G),
231  agnnodes(G));
232 
233 
234  /* Eliminate singletons and trees */
235  if (Reduce) {
236  for (np = agfstnode(G); np; np = xp) {
237  xp = agnxtnode(G, np);
238  deg = degreeKind(G, np, &other);
239  if (deg == 0) { /* singleton node */
240  agdelete(G->root, np);
241  } else if (deg == 1) {
242  agdelete(G->root, np);
243  xp = prune(G, other, xp);
244  }
245  }
246  }
247 
248  nV = agnnodes(G);
249  nE = agnedges(G);
250 
251  lenx = agattr(G, AGEDGE, "len", 0);
252  if (mode == MODE_KK) {
253  Epsilon = .0001 * nV;
254  getdouble(G, "epsilon", &Epsilon);
255  if ((str = agget(G->root, "Damping")))
256  Damping = atof(str);
257  else
258  Damping = .99;
259  GD_neato_nlist(G) = N_NEW(nV + 1, node_t *);
260  for (i = 0, np = agfstnode(G); np; np = agnxtnode(G, np)) {
261  GD_neato_nlist(G)[i] = np;
262  ND_id(np) = i++;
263  ND_heapindex(np) = -1;
264  total_len += setEdgeLen(G, np, lenx, dfltlen);
265  }
266  } else {
268  getdouble(G, "epsilon", &Epsilon);
269  for (i = 0, np = agfstnode(G); np; np = agnxtnode(G, np)) {
270  ND_id(np) = i++;
271  total_len += setEdgeLen(G, np, lenx, dfltlen);
272  }
273  }
274 
275  str = agget(G, "defaultdist");
276  if (str && str[0])
277  Initial_dist = MAX(Epsilon, atof(str));
278  else
279  Initial_dist = total_len / (nE > 0 ? nE : 1) * sqrt(nV) + 1;
280 
281  if (!Nop && (mode == MODE_KK)) {
282  GD_dist(G) = new_array(nV, nV, Initial_dist);
283  GD_spring(G) = new_array(nV, nV, 1.0);
284  GD_sum_t(G) = new_array(nV, Ndim, 1.0);
285  GD_t(G) = new_3array(nV, nV, Ndim, 0.0);
286  }
287 
288  return nV;
289 }
290 
292 {
293  return scan_graph_mode(g, MODE_KK);
294 }
295 
297 {
298  free(GD_neato_nlist(g));
299  if (!Nop) {
300  free_array(GD_dist(g));
301  free_array(GD_spring(g));
302  free_array(GD_sum_t(g));
303  free_3array(GD_t(g));
304  GD_t(g) = NULL;
305  }
306 }
307 
308 void jitter_d(node_t * np, int nG, int n)
309 {
310  int k;
311  for (k = n; k < Ndim; k++)
312  ND_pos(np)[k] = nG * drand48();
313 }
314 
315 void jitter3d(node_t * np, int nG)
316 {
317  jitter_d(np, nG, 2);
318 }
319 
320 void randompos(node_t * np, int nG)
321 {
322  ND_pos(np)[0] = nG * drand48();
323  ND_pos(np)[1] = nG * drand48();
324  if (Ndim > 2)
325  jitter3d(np, nG);
326 }
327 
328 void initial_positions(graph_t * G, int nG)
329 {
330  int init, i;
331  node_t *np;
332  static int once = 0;
333 
334  if (Verbose)
335  fprintf(stderr, "Setting initial positions\n");
336 
337  init = checkStart(G, nG, INIT_RANDOM);
338  if (init == INIT_REGULAR)
339  return;
340  if ((init == INIT_SELF) && (once == 0)) {
341  agerr(AGWARN, "start=%s not supported with mode=self - ignored\n");
342  once = 1;
343  }
344 
345  for (i = 0; (np = GD_neato_nlist(G)[i]); i++) {
346  if (hasPos(np))
347  continue;
348  randompos(np, 1);
349  }
350 }
351 
352 void diffeq_model(graph_t * G, int nG)
353 {
354  int i, j, k;
355  double dist, **D, **K, del[MAXDIM], f;
356  node_t *vi, *vj;
357  edge_t *e;
358 
359  if (Verbose) {
360  fprintf(stderr, "Setting up spring model: ");
361  start_timer();
362  }
363  /* init springs */
364  K = GD_spring(G);
365  D = GD_dist(G);
366  for (i = 0; i < nG; i++) {
367  for (j = 0; j < i; j++) {
368  f = Spring_coeff / (D[i][j] * D[i][j]);
369  if ((e = agfindedge(G, GD_neato_nlist(G)[i], GD_neato_nlist(G)[j])))
370  f = f * ED_factor(e);
371  K[i][j] = K[j][i] = f;
372  }
373  }
374 
375  /* init differential equation solver */
376  for (i = 0; i < nG; i++)
377  for (k = 0; k < Ndim; k++)
378  GD_sum_t(G)[i][k] = 0.0;
379 
380  for (i = 0; (vi = GD_neato_nlist(G)[i]); i++) {
381  for (j = 0; j < nG; j++) {
382  if (i == j)
383  continue;
384  vj = GD_neato_nlist(G)[j];
385  dist = distvec(ND_pos(vi), ND_pos(vj), del);
386  for (k = 0; k < Ndim; k++) {
387  GD_t(G)[i][j][k] =
388  GD_spring(G)[i][j] * (del[k] -
389  GD_dist(G)[i][j] * del[k] /
390  dist);
391  GD_sum_t(G)[i][k] += GD_t(G)[i][j][k];
392  }
393  }
394  }
395  if (Verbose) {
396  fprintf(stderr, "%.2f sec\n", elapsed_sec());
397  }
398 }
399 
400 /* total_e:
401  * Return 2*energy of system.
402  */
403 static double total_e(graph_t * G, int nG)
404 {
405  int i, j, d;
406  double e = 0.0; /* 2*energy */
407  double t0; /* distance squared */
408  double t1;
409  node_t *ip, *jp;
410 
411  for (i = 0; i < nG - 1; i++) {
412  ip = GD_neato_nlist(G)[i];
413  for (j = i + 1; j < nG; j++) {
414  jp = GD_neato_nlist(G)[j];
415  for (t0 = 0.0, d = 0; d < Ndim; d++) {
416  t1 = (ND_pos(ip)[d] - ND_pos(jp)[d]);
417  t0 += t1 * t1;
418  }
419  e = e + GD_spring(G)[i][j] *
420  (t0 + GD_dist(G)[i][j] * GD_dist(G)[i][j]
421  - 2.0 * GD_dist(G)[i][j] * sqrt(t0));
422  }
423  }
424  return e;
425 }
426 
427 void solve_model(graph_t * G, int nG)
428 {
429  node_t *np;
430 
431  Epsilon2 = Epsilon * Epsilon;
432 
433  while ((np = choose_node(G, nG))) {
434  move_node(G, nG, np);
435  }
436  if (Verbose) {
437  fprintf(stderr, "\nfinal e = %f", total_e(G, nG));
438  fprintf(stderr, " %d%s iterations %.2f sec\n",
439  GD_move(G), (GD_move(G) == MaxIter ? "!" : ""),
440  elapsed_sec());
441  }
442  if (GD_move(G) == MaxIter)
443  agerr(AGWARN, "Max. iterations (%d) reached on graph %s\n",
444  MaxIter, agnameof(G));
445 }
446 
447 void update_arrays(graph_t * G, int nG, int i)
448 {
449  int j, k;
450  double del[MAXDIM], dist, old;
451  node_t *vi, *vj;
452 
453  vi = GD_neato_nlist(G)[i];
454  for (k = 0; k < Ndim; k++)
455  GD_sum_t(G)[i][k] = 0.0;
456  for (j = 0; j < nG; j++) {
457  if (i == j)
458  continue;
459  vj = GD_neato_nlist(G)[j];
460  dist = distvec(ND_pos(vi), ND_pos(vj), del);
461  for (k = 0; k < Ndim; k++) {
462  old = GD_t(G)[i][j][k];
463  GD_t(G)[i][j][k] =
464  GD_spring(G)[i][j] * (del[k] -
465  GD_dist(G)[i][j] * del[k] / dist);
466  GD_sum_t(G)[i][k] += GD_t(G)[i][j][k];
467  old = GD_t(G)[j][i][k];
468  GD_t(G)[j][i][k] = -GD_t(G)[i][j][k];
469  GD_sum_t(G)[j][k] += (GD_t(G)[j][i][k] - old);
470  }
471  }
472 }
473 
474 #define Msub(i,j) M[(i)*Ndim+(j)]
475 void D2E(graph_t * G, int nG, int n, double *M)
476 {
477  int i, l, k;
478  node_t *vi, *vn;
479  double scale, sq, t[MAXDIM];
480  double **K = GD_spring(G);
481  double **D = GD_dist(G);
482 
483  vn = GD_neato_nlist(G)[n];
484  for (l = 0; l < Ndim; l++)
485  for (k = 0; k < Ndim; k++)
486  Msub(l, k) = 0.0;
487  for (i = 0; i < nG; i++) {
488  if (n == i)
489  continue;
490  vi = GD_neato_nlist(G)[i];
491  sq = 0.0;
492  for (k = 0; k < Ndim; k++) {
493  t[k] = ND_pos(vn)[k] - ND_pos(vi)[k];
494  sq += (t[k] * t[k]);
495  }
496  scale = 1 / fpow32(sq);
497  for (k = 0; k < Ndim; k++) {
498  for (l = 0; l < k; l++)
499  Msub(l, k) += K[n][i] * D[n][i] * t[k] * t[l] * scale;
500  Msub(k, k) +=
501  K[n][i] * (1.0 - D[n][i] * (sq - (t[k] * t[k])) * scale);
502  }
503  }
504  for (k = 1; k < Ndim; k++)
505  for (l = 0; l < k; l++)
506  Msub(k, l) = Msub(l, k);
507 }
508 
509 void final_energy(graph_t * G, int nG)
510 {
511  fprintf(stderr, "iterations = %d final e = %f\n", GD_move(G),
512  total_e(G, nG));
513 }
514 
516 {
517  int i, k;
518  double m, max;
519  node_t *choice, *np;
520  static int cnt = 0;
521 #if 0
522  double e;
523  static double save_e = MAXDOUBLE;
524 #endif
525 
526  cnt++;
527  if (GD_move(G) >= MaxIter)
528  return NULL;
529 #if 0
530  if ((cnt % 100) == 0) {
531  e = total_e(G, nG);
532  if (e - save_e > 0)
533  return NULL;
534  save_e = e;
535  }
536 #endif
537  max = 0.0;
538  choice = NULL;
539  for (i = 0; i < nG; i++) {
540  np = GD_neato_nlist(G)[i];
541  if (ND_pinned(np) > P_SET)
542  continue;
543  for (m = 0.0, k = 0; k < Ndim; k++)
544  m += (GD_sum_t(G)[i][k] * GD_sum_t(G)[i][k]);
545  /* could set the color=energy of the node here */
546  if (m > max) {
547  choice = np;
548  max = m;
549  }
550  }
551  if (max < Epsilon2)
552  choice = NULL;
553  else {
554  if (Verbose && (cnt % 100 == 0)) {
555  fprintf(stderr, "%.3f ", sqrt(max));
556  if (cnt % 1000 == 0)
557  fprintf(stderr, "\n");
558  }
559 #if 0
560  e = total_e(G, nG);
561  if (fabs((e - save_e) / save_e) < 1e-5) {
562  choice = NULL;
563  }
564 #endif
565  }
566  return choice;
567 }
568 
569 void move_node(graph_t * G, int nG, node_t * n)
570 {
571  int i, m;
572  static double *a, b[MAXDIM], c[MAXDIM];
573 
574  m = ND_id(n);
575  a = ALLOC(Ndim * Ndim, a, double);
576  D2E(G, nG, m, a);
577  for (i = 0; i < Ndim; i++)
578  c[i] = -GD_sum_t(G)[m][i];
579  solve(a, b, c, Ndim);
580  for (i = 0; i < Ndim; i++) {
581  b[i] = (Damping + 2 * (1 - Damping) * drand48()) * b[i];
582  ND_pos(n)[i] += b[i];
583  }
584  GD_move(G)++;
585  update_arrays(G, nG, m);
586  if (test_toggle()) {
587  double sum = 0;
588  for (i = 0; i < Ndim; i++) {
589  sum += fabs(b[i]);
590  } /* Why not squared? */
591  sum = sqrt(sum);
592  fprintf(stderr, "%s %.3f\n", agnameof(n), sum);
593  }
594 }
595 
596 static node_t **Heap;
597 static int Heapsize;
598 static node_t *Src;
599 
600 void heapup(node_t * v)
601 {
602  int i, par;
603  node_t *u;
604 
605  for (i = ND_heapindex(v); i > 0; i = par) {
606  par = (i - 1) / 2;
607  u = Heap[par];
608  if (ND_dist(u) <= ND_dist(v))
609  break;
610  Heap[par] = v;
611  ND_heapindex(v) = par;
612  Heap[i] = u;
613  ND_heapindex(u) = i;
614  }
615 }
616 
617 void heapdown(node_t * v)
618 {
619  int i, left, right, c;
620  node_t *u;
621 
622  i = ND_heapindex(v);
623  while ((left = 2 * i + 1) < Heapsize) {
624  right = left + 1;
625  if ((right < Heapsize)
626  && (ND_dist(Heap[right]) < ND_dist(Heap[left])))
627  c = right;
628  else
629  c = left;
630  u = Heap[c];
631  if (ND_dist(v) <= ND_dist(u))
632  break;
633  Heap[c] = v;
634  ND_heapindex(v) = c;
635  Heap[i] = u;
636  ND_heapindex(u) = i;
637  i = c;
638  }
639 }
640 
642 {
643  int i;
644 
645  assert(ND_heapindex(v) < 0);
646  i = Heapsize++;
647  ND_heapindex(v) = i;
648  Heap[i] = v;
649  if (i > 0)
650  heapup(v);
651 }
652 
654 {
655  int i;
656  node_t *rv, *v;
657 
658  if (Heapsize == 0)
659  return NULL;
660  rv = Heap[0];
661  i = --Heapsize;
662  v = Heap[i];
663  Heap[0] = v;
664  ND_heapindex(v) = 0;
665  if (i > 1)
666  heapdown(v);
667  ND_heapindex(rv) = -1;
668  return rv;
669 }
670 
671 void shortest_path(graph_t * G, int nG)
672 {
673  node_t *v;
674 
675  Heap = N_NEW(nG + 1, node_t *);
676  if (Verbose) {
677  fprintf(stderr, "Calculating shortest paths: ");
678  start_timer();
679  }
680  for (v = agfstnode(G); v; v = agnxtnode(G, v))
681  s1(G, v);
682  if (Verbose) {
683  fprintf(stderr, "%.2f sec\n", elapsed_sec());
684  }
685  free(Heap);
686 }
687 
688 void s1(graph_t * G, node_t * node)
689 {
690  node_t *v, *u;
691  edge_t *e;
692  int t;
693  double f;
694 
695  for (t = 0; (v = GD_neato_nlist(G)[t]); t++)
696  ND_dist(v) = Initial_dist;
697  Src = node;
698  ND_dist(Src) = 0;
699  ND_hops(Src) = 0;
700  neato_enqueue(Src);
701 
702  while ((v = neato_dequeue())) {
703  if (v != Src)
704  make_spring(G, Src, v, ND_dist(v));
705  for (e = agfstedge(G, v); e; e = agnxtedge(G, e, v)) {
706  if ((u = agtail(e)) == v)
707  u = aghead(e);
708  f = ND_dist(v) + ED_dist(e);
709  if (ND_dist(u) > f) {
710  ND_dist(u) = f;
711  if (ND_heapindex(u) >= 0)
712  heapup(u);
713  else {
714  ND_hops(u) = ND_hops(v) + 1;
715  neato_enqueue(u);
716  }
717  }
718  }
719  }
720 }
721 
722 void make_spring(graph_t * G, node_t * u, node_t * v, double f)
723 {
724  int i, j;
725 
726  i = ND_id(u);
727  j = ND_id(v);
728  GD_dist(G)[i][j] = GD_dist(G)[j][i] = f;
729 }
730 
731 int allow_edits(int nsec)
732 {
733 #ifdef INTERACTIVE
734  static int onetime = TRUE;
735  static FILE *fp;
736  static fd_set fd;
737  static struct timeval tv;
738 
739  char buf[256], name[256];
740  double x, y;
741  node_t *np;
742 
743  if (onetime) {
744  fp = fopen("/dev/tty", "r");
745  if (fp == NULL)
746  exit(1);
747  setbuf(fp, NULL);
748  tv.tv_usec = 0;
749  onetime = FALSE;
750  }
751  tv.tv_sec = nsec;
752  FD_ZERO(&fd);
753  FD_SET(fileno(fp), &fd);
754  if (select(32, &fd, (fd_set *) 0, (fd_set *) 0, &tv) > 0) {
755  fgets(buf, sizeof(buf), fp);
756  switch (buf[0]) {
757  case 'm': /* move node */
758  if (sscanf(buf + 1, "%s %lf%lf", name, &x, &y) == 3) {
759  np = getnode(G, name);
760  if (np) {
761  NP_pos(np)[0] = x;
762  NP_pos(np)[1] = y;
763  diffeq_model();
764  }
765  }
766  break;
767  case 'q':
768  return FALSE;
769  default:
770  agerr(AGERR, "unknown command '%s', ignored\n", buf);
771  }
772  return TRUE;
773  }
774 #endif
775  return FALSE;
776 }
#define MAX(a, b)
Definition: agerror.c:17
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
Definition: cgraph.h:389
#define ND_pinned(n)
Definition: types.h:486
void start_timer(void)
Definition: timing.c:45
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define N_NEW(n, t)
Definition: memory.h:36
int scan_graph_mode(graph_t *G, int mode)
Definition: stuff.c:220
EXTERN double Epsilon
Definition: globals.h:86
int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
int agnedges(Agraph_t *g)
void free_scan_graph(graph_t *g)
Definition: stuff.c:296
#define ND_dist(n)
Definition: types.h:458
EXTERN int Nop
Definition: globals.h:79
#define ALLOC(size, ptr, type)
Definition: memory.h:41
void final_energy(graph_t *G, int nG)
Definition: stuff.c:509
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
#define DFLT_TOLERANCE
Definition: stress.h:28
double fpow32(double x)
Definition: stuff.c:29
#define hasPos(n)
Definition: macros.h:26
#define assert(x)
Definition: cghdr.h:48
#define GD_move(g)
Definition: types.h:375
void jitter3d(node_t *np, int nG)
Definition: stuff.c:315
void neato_enqueue(node_t *v)
Definition: stuff.c:641
#define GD_sum_t(g)
Definition: types.h:393
void getdouble(graph_t *g, char *name, double *result)
Definition: input.c:470
void solve(double *, double *, double *, int)
Definition: solve.c:23
EXTERN double Initial_dist
Definition: globals.h:91
EXTERN double Damping
Definition: globals.h:92
int agnnodes(Agraph_t *g)
void jitter_d(node_t *np, int nG, int n)
Definition: stuff.c:308
#define P_SET
Definition: const.h:282
#define ND_pos(n)
Definition: types.h:487
#define ND_hops(n)
Definition: types.h:466
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:142
void heapup(node_t *v)
Definition: stuff.c:600
void diffeq_model(graph_t *G, int nG)
Definition: stuff.c:352
#define Msub(i, j)
Definition: stuff.c:474
void solve_model(graph_t *G, int nG)
Definition: stuff.c:427
void D2E(graph_t *G, int nG, int n, double *M)
Definition: stuff.c:475
Definition: cgraph.h:389
#define INIT_REGULAR
Definition: neato.h:34
char * agget(void *obj, char *name)
Definition: attr.c:428
void update_arrays(graph_t *G, int nG, int i)
Definition: stuff.c:447
int scan_graph(graph_t *g)
Definition: stuff.c:291
void free()
int i
Definition: gvdevice.c:448
#define max(x, y)
Definition: stress.c:794
#define GD_dist(g)
Definition: types.h:340
#define ND_id(n)
Definition: types.h:450
int test_toggle()
Definition: utils.c:616
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
double distvec(double *p0, double *p1, double *vec)
Definition: stuff.c:35
double drand48(void)
Definition: utils.c:1965
#define INIT_SELF
Definition: neato.h:33
node_t * choose_node(graph_t *G, int nG)
Definition: stuff.c:515
void make_spring(graph_t *G, node_t *u, node_t *v, double f)
Definition: stuff.c:722
void heapdown(node_t *v)
Definition: stuff.c:617
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
void s1(graph_t *G, node_t *node)
Definition: stuff.c:688
EXTERN unsigned char Reduce
Definition: globals.h:74
void move_node(graph_t *G, int nG, node_t *n)
Definition: stuff.c:569
node_t * neato_dequeue(void)
Definition: stuff.c:653
#define ED_factor(e)
Definition: types.h:542
#define NULL
Definition: logic.h:50
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
double elapsed_sec(void)
Definition: timing.c:50
#define right(i)
Definition: closest.c:87
EXTERN unsigned char Verbose
Definition: globals.h:73
char * agnameof(void *)
Definition: id.c:143
Agnode_t * node(Agraph_t *g, char *name)
Definition: gv.cpp:103
double ** new_array(int m, int n, double ival)
Definition: stuff.c:48
void shortest_path(graph_t *G, int nG)
Definition: stuff.c:671
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
#define INIT_RANDOM
Definition: neato.h:35
void initial_positions(graph_t *G, int nG)
Definition: stuff.c:328
#define GD_t(g)
Definition: types.h:394
#define left
Definition: dthdr.h:23
#define agfindedge(g, t, h)
Definition: types.h:564
#define MAXDIM
Definition: const.h:177
agxbuf * str
Definition: htmlparse.c:85
Agraph_t * root
Definition: cgraph.h:241
int checkStart(graph_t *G, int nG, int dflt)
Definition: neatoinit.c:1025
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
double dist(Site *s, Site *t)
Definition: site.c:41
#define MODE_KK
Definition: neato.h:27
void free_array(double **rv)
Definition: stuff.c:65
#define AGEDGE
Definition: cgraph.h:91
void randompos(node_t *np, int nG)
Definition: stuff.c:320
#define ND_heapindex(n)
Definition: types.h:464
Definition: cgraph.h:389
int allow_edits(int nsec)
Definition: stuff.c:731
#define ED_dist(e)
Definition: types.h:559
#define Spring_coeff
Definition: const.h:175
#define GD_neato_nlist(g)
Definition: types.h:380
EXTERN int MaxIter
Definition: globals.h:87
#define FALSE
Definition: cgraph.h:24
#define MAXDOUBLE
Definition: arith.h:67
EXTERN int Ndim
Definition: globals.h:88
#define GD_spring(g)
Definition: types.h:392
#define TRUE
Definition: cgraph.h:27