Graphviz  2.41.20170921.2350
blockpath.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 #include "blockpath.h"
16 #include "edgelist.h"
17 #include "nodeset.h"
18 #include "deglist.h"
19 
20 /* The code below lays out a single block on a circle.
21  */
22 
23 /* We use the unused fields order and to_orig in cloned nodes and edges */
24 #define ORIGE(e) (ED_to_orig(e))
25 
26 /* clone_graph:
27  * Create two copies of the argument graph
28  * One is a subgraph, the other is an actual copy since we will be
29  * adding edges to it.
30  */
31 static Agraph_t *clone_graph(Agraph_t * ing, Agraph_t ** xg)
32 {
33  Agraph_t *clone;
34  Agraph_t *xclone;
35  Agnode_t *n;
36  Agnode_t *xn;
37  Agnode_t *xh;
38  Agedge_t *e;
39  Agedge_t *xe;
40  char gname[SMALLBUF];
41  static int id = 0;
42 
43  sprintf(gname, "_clone_%d", id++);
44  clone = agsubg(ing, gname,1);
45  agbindrec(clone, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
46  sprintf(gname, "_clone_%d", id++);
47  xclone = agopen(gname, ing->desc,NIL(Agdisc_t *));
48  for (n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
49  agsubnode(clone,n,1);
50  xn = agnode(xclone, agnameof(n),1);
51  agbindrec(xn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
52  CLONE(n) = xn;
53  }
54 
55  for (n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
56  xn = CLONE(n);
57  for (e = agfstout(ing, n); e; e = agnxtout(ing, e)) {
58  agsubedge(clone,e,1);
59  xh = CLONE(aghead(e));
60  xe = agedge(xclone, xn, xh, NULL, 1);
61  agbindrec(xe, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
62  ORIGE(xe) = e;
63  DEGREE(xn) += 1;
64  DEGREE(xh) += 1;
65  }
66  }
67  *xg = xclone;
68  return clone;
69 }
70 
71 /* fillList:
72  * Add nodes to deg_list, which stores them by degree.
73  */
74 static deglist_t *getList(Agraph_t * g)
75 {
76  deglist_t *dl = mkDeglist();
77  Agnode_t *n;
78 
79  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
80  insertDeglist(dl, n);
81  }
82  return dl;
83 }
84 
85 /* find_pair_edges:
86  */
87 static void find_pair_edges(Agraph_t * g, Agnode_t * n, Agraph_t * outg)
88 {
89  Agnode_t **neighbors_with;
90  Agnode_t **neighbors_without;
91 
92  Agedge_t *e;
93  Agedge_t *ep;
94  Agedge_t *ex;
95  Agnode_t *n1;
96  Agnode_t *n2;
97  int has_pair_edge;
98  int diff;
99  int has_pair_count = 0;
100  int no_pair_count = 0;
101  int node_degree;
102  int edge_cnt = 0;
103 
104  node_degree = DEGREE(n);
105  neighbors_with = N_GNEW(node_degree, Agnode_t *);
106  neighbors_without = N_GNEW(node_degree, Agnode_t *);
107 
108  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
109  n1 = aghead(e);
110  if (n1 == n)
111  n1 = agtail(e);
112  has_pair_edge = 0;
113  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
114  if (ep == e)
115  continue;
116  n2 = aghead(ep);
117  if (n2 == n)
118  n2 = agtail(ep);
119  ex = agfindedge(g, n1, n2);
120  if (ex) {
121  has_pair_edge = 1;
122  if (n1 < n2) { /* count edge only once */
123  edge_cnt++;
124  if (ORIGE(ex)) {
125  agdelete(outg, ORIGE(ex));
126  ORIGE(ex) = 0; /* delete only once */
127  }
128  }
129  }
130  }
131  if (has_pair_edge) {
132  neighbors_with[has_pair_count] = n1;
133  has_pair_count++;
134  } else {
135  neighbors_without[no_pair_count] = n1;
136  no_pair_count++;
137  }
138  }
139 
140  diff = node_degree - 1 - edge_cnt;
141  if (diff > 0) {
142  int mark;
143  Agnode_t *hp;
144  Agnode_t *tp;
145 
146  if (diff < no_pair_count) {
147  for (mark = 0; mark < no_pair_count; mark += 2) {
148  if ((mark + 1) >= no_pair_count)
149  break;
150  tp = neighbors_without[mark];
151  hp = neighbors_without[mark + 1];
152  agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); // edge custom data
153  DEGREE(tp)++;
154  DEGREE(hp)++;
155  diff--;
156  }
157 
158  mark = 2;
159  while (diff > 0) {
160  tp = neighbors_without[0];
161  hp = neighbors_without[mark];
162  agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); // edge custom data
163  DEGREE(tp)++;
164  DEGREE(hp)++;
165  mark++;
166  diff--;
167  }
168  }
169 
170  else if (diff == no_pair_count) {
171  tp = neighbors_with[0];
172  for (mark = 0; mark < no_pair_count; mark++) {
173  hp = neighbors_without[mark];
174  agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
175  DEGREE(tp)++;
176  DEGREE(hp)++;
177  }
178  }
179  }
180 
181  free(neighbors_without);
182  free(neighbors_with);
183 }
184 
185 /* remove_pair_edges:
186  * Create layout skeleton of ing.
187  * Why is returned graph connected?
188  */
189 static Agraph_t *remove_pair_edges(Agraph_t * ing)
190 {
191  int counter = 0;
192  int nodeCount;
193  Agraph_t *outg;
194  Agraph_t *g;
195  deglist_t *dl;
196  Agnode_t *currnode, *adjNode;
197  Agedge_t *e;
198 
199  outg = clone_graph(ing, &g);
200  nodeCount = agnnodes(g);
201  dl = getList(g);
202 
203  while (counter < (nodeCount - 3)) {
204  currnode = firstDeglist(dl);
205 
206  /* Remove all adjacent nodes since they have to be reinserted */
207  for (e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
208  adjNode = aghead(e);
209  if (currnode == adjNode)
210  adjNode = agtail(e);
211  removeDeglist(dl, adjNode);
212  }
213 
214  find_pair_edges(g, currnode, outg);
215 
216  for (e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
217  adjNode = aghead(e);
218  if (currnode == adjNode)
219  adjNode = agtail(e);
220 
221  DEGREE(adjNode)--;
222  insertDeglist(dl, adjNode);
223  }
224 
225  agdelete(g, currnode);
226 
227  counter++;
228  }
229 
230  agclose(g);
231  freeDeglist(dl);
232  return outg;
233 }
234 
235 static void
236 measure_distance(Agnode_t * n, Agnode_t * ancestor, int dist,
237  Agnode_t * change)
238 {
239  Agnode_t *parent;
240 
241  parent = TPARENT(ancestor);
242  if (parent == NULL)
243  return;
244 
245  dist++;
246 
247  /* check parent to see if it has other leaf paths at greater distance
248  than the context node.
249  set the path/distance of the leaf at this ancestor node */
250 
251  if (DISTONE(parent) == 0) {
252  LEAFONE(parent) = n;
253  DISTONE(parent) = dist;
254  } else if (dist > DISTONE(parent)) {
255  if (LEAFONE(parent) != change) {
256  if (!DISTTWO(parent) || (LEAFTWO(parent) != change))
257  change = LEAFONE(parent);
258  LEAFTWO(parent) = LEAFONE(parent);
259  DISTTWO(parent) = DISTONE(parent);
260  }
261  LEAFONE(parent) = n;
262  DISTONE(parent) = dist;
263  } else if (dist > DISTTWO(parent)) {
264  LEAFTWO(parent) = n;
265  DISTTWO(parent) = dist;
266  return;
267  } else
268  return;
269 
270  measure_distance(n, parent, dist, change);
271 }
272 
273 /* find_longest_path:
274  * Find and return longest path in tree.
275  */
276 static nodelist_t *find_longest_path(Agraph_t * tree)
277 {
278  Agnode_t *n;
279  Agedge_t *e;
280  Agnode_t *common = 0;
281  nodelist_t *path;
282  nodelist_t *endPath;
283  int maxlength = 0;
284  int length;
285 
286  if (agnnodes(tree) == 1) {
287  path = mkNodelist();
288  n = agfstnode(tree);
289  appendNodelist(path, NULL, n);
290  SET_ONPATH(n);
291  return path;
292  }
293 
294  for (n = agfstnode(tree); n; n = agnxtnode(tree, n)) {
295  int count = 0;
296  for (e = agfstedge(tree, n); e; e = agnxtedge(tree, e, n)) {
297  count++;
298  }
299  if (count == 1)
300  measure_distance(n, n, 0, NULL);
301  }
302 
303  /* find the branch node rooted at the longest path */
304  for (n = agfstnode(tree); n; n = agnxtnode(tree, n)) {
305  length = DISTONE(n) + DISTTWO(n);
306  if (length > maxlength) {
307  common = n;
308  maxlength = length;
309  }
310  }
311 
312  path = mkNodelist();
313  for (n = LEAFONE(common); n != common; n = TPARENT(n)) {
314  appendNodelist(path, NULL, n);
315  SET_ONPATH(n);
316  }
317  appendNodelist(path, NULL, common);
318  SET_ONPATH(common);
319 
320  if (DISTTWO(common)) { /* 2nd path might be empty */
321  endPath = mkNodelist();
322  for (n = LEAFTWO(common); n != common; n = TPARENT(n)) {
323  appendNodelist(endPath, NULL, n);
324  SET_ONPATH(n);
325  }
326  reverseAppend(path, endPath);
327  }
328 
329  return path;
330 }
331 
332 /* dfs:
333  * Simple depth first search, adding traversed edges to tree.
334  */
335 static void dfs(Agraph_t * g, Agnode_t * n, Agraph_t * tree)
336 {
337  Agedge_t *e;
338  Agnode_t *neighbor;
339 
340  SET_VISITED(n);
341  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
342  neighbor = aghead(e);
343  if (neighbor == n)
344  neighbor = agtail(e);
345 
346  if (!VISITED(neighbor)) {
347  /* add the edge to the dfs tree */
348  agsubedge(tree,e,1);
349  TPARENT(neighbor) = n;
350  dfs(g, neighbor, tree);
351  }
352  }
353 }
354 
355 /* spanning_tree:
356  * Construct spanning forest of g as subgraph
357  */
358 static Agraph_t *spanning_tree(Agraph_t * g)
359 {
360  Agnode_t *n;
361  Agraph_t *tree;
362  char gname[SMALLBUF];
363  static int id = 0;
364 
365  sprintf(gname, "_span_%d", id++);
366  tree = agsubg(g, gname,1);
367  agbindrec(tree, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
368 
369  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
370  agsubnode(tree,n,1);
371  DISTONE(n) = 0;
372  DISTTWO(n) = 0;
373  UNSET_VISITED(n);
374  }
375 
376  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
377  if (!VISITED(n)) {
378  TPARENT(n) = NULL;
379  dfs(g, n, tree);
380  }
381  }
382 
383  return tree;
384 }
385 
386 /* block_graph:
387  * Add induced edges.
388  */
389 static void block_graph(Agraph_t * g, block_t * sn)
390 {
391  Agnode_t *n;
392  Agedge_t *e;
393  Agraph_t *subg = sn->sub_graph;
394 
395  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
396  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
397  if (BLOCK(aghead(e)) == sn)
398  agsubedge(subg,e,1);
399  }
400  }
401 }
402 
403 static int count_all_crossings(nodelist_t * list, Agraph_t * subg)
404 {
406  edgelist *openEdgeList = init_edgelist();
407  Agnode_t *n;
408  Agedge_t *e;
409  int crossings = 0;
410  int order = 1;
411 
412  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
413  for (e = agfstout(subg, n); e; e = agnxtout(subg, e)) {
414  EDGEORDER(e) = 0;
415  }
416  }
417 
418  for (item = list->first; item; item = item->next) {
419  n = item->curr;
420 
421  for (e = agfstedge(subg, n); e; e = agnxtedge(subg, e, n)) {
422  if (EDGEORDER(e) > 0) {
423  edgelistitem *eitem;
424  Agedge_t *ep;
425 
426  for (eitem = (edgelistitem *) dtfirst(openEdgeList); eitem;
427  eitem =
428  (edgelistitem *) dtnext(openEdgeList, eitem)) {
429  ep = eitem->edge;
430  if (EDGEORDER(ep) > EDGEORDER(e)) {
431  if ((aghead(ep) != n) && (agtail(ep) != n))
432  crossings++;
433  }
434  }
435  remove_edge(openEdgeList, e);
436  }
437  }
438 
439  for (e = agfstedge(subg, n); e; e = agnxtedge(subg, e, n)) {
440  if (EDGEORDER(e) == 0) {
441  EDGEORDER(e) = order;
442  add_edge(openEdgeList, e);
443  }
444  }
445  order++;
446  }
447 
448  free_edgelist(openEdgeList);
449  return crossings;
450 }
451 
452 #define CROSS_ITER 10
453 
454 /* reduce:
455  * Attempt to reduce edge crossings by moving nodes.
456  * Original crossing count is in cnt; final count is returned there.
457  * list is the original list; return the best list found.
458  */
459 static nodelist_t *reduce(nodelist_t * list, Agraph_t * subg, int *cnt)
460 {
461  Agnode_t *curnode;
462  Agedge_t *e;
463  Agnode_t *neighbor;
464  nodelist_t *listCopy;
465  int crossings, j, newCrossings;
466 
467  crossings = *cnt;
468  for (curnode = agfstnode(subg); curnode;
469  curnode = agnxtnode(subg, curnode)) {
470  /* move curnode next to its neighbors */
471  for (e = agfstedge(subg, curnode); e;
472  e = agnxtedge(subg, e, curnode)) {
473  neighbor = agtail(e);
474  if (neighbor == curnode)
475  neighbor = aghead(e);
476 
477  for (j = 0; j < 2; j++) {
478  listCopy = cloneNodelist(list);
479  insertNodelist(list, curnode, neighbor, j);
480  newCrossings = count_all_crossings(list, subg);
481  if (newCrossings < crossings) {
482  crossings = newCrossings;
483  freeNodelist(listCopy);
484  if (crossings == 0) {
485  *cnt = 0;
486  return list;
487  }
488  } else {
489  freeNodelist(list);
490  list = listCopy;
491  }
492  }
493  }
494  }
495  *cnt = crossings;
496  return list;
497 }
498 
499 static nodelist_t *reduce_edge_crossings(nodelist_t * list,
500  Agraph_t * subg)
501 {
502  int i, crossings, origCrossings;
503 
504  crossings = count_all_crossings(list, subg);
505  if (crossings == 0)
506  return list;
507 
508  for (i = 0; i < CROSS_ITER; i++) {
509  origCrossings = crossings;
510  list = reduce(list, subg, &crossings);
511  /* return if no crossings or no improvement */
512  if ((origCrossings == crossings) || (crossings == 0))
513  return list;
514  }
515  return list;
516 }
517 
518 /* largest_nodesize:
519  * Return max dimension of nodes on list
520  */
521 static double largest_nodesize(nodelist_t * list)
522 {
523  Agnode_t *n;
525  double size = 0;
526 
527  for (item = list->first; item; item = item->next) {
528  n = ORIGN(item->curr);
529  if (ND_width(n) > size)
530  size = ND_width(n);
531  if (ND_height(n) > size)
532  size = ND_height(n);
533  }
534  return size;
535 }
536 
537 /* place_node:
538  * Add n to list. By construction, n is not in list at start.
539  */
540 static void place_node(Agraph_t * g, Agnode_t * n, nodelist_t * list)
541 {
542  Agedge_t *e;
543  int placed = 0;
544  nodelist_t *neighbors = mkNodelist();
545  nodelistitem_t *one, *two;
546 
547  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
548  appendNodelist(neighbors, NULL, aghead(e));
549  SET_NEIGHBOR(aghead(e));
550  }
551  for (e = agfstin(g, n); e; e = agnxtin(g, e)) {
552  appendNodelist(neighbors, NULL, agtail(e));
553  SET_NEIGHBOR(agtail(e));
554  }
555 
556  /* Look for 2 neighbors consecutive on list */
557  if (sizeNodelist(neighbors) >= 2) {
558  for (one = list->first; one; one = one->next) {
559  if (one == list->last)
560  two = list->first;
561  else
562  two = one->next;
563 
564  if (NEIGHBOR(one->curr) && NEIGHBOR(two->curr)) {
565  appendNodelist(list, one, n);
566  placed = 1;
567  break;
568  }
569  }
570  }
571 
572  /* Find any neighbor on list */
573  if (!placed && sizeNodelist(neighbors) > 0) {
574  for (one = list->first; one; one = one->next) {
575  if (NEIGHBOR(one->curr)) {
576  appendNodelist(list, one, n);
577  placed = 1;
578  break;
579  }
580  }
581  }
582 
583  if (!placed)
584  appendNodelist(list, NULL, n);
585 
586  for (one = neighbors->first; one; one = one->next)
587  UNSET_NEIGHBOR(one->curr);
588  freeNodelist(neighbors);
589 }
590 
591 /* place_residual_nodes:
592  * Add nodes not in list to list.
593  */
594 static void place_residual_nodes(Agraph_t * g, nodelist_t * list)
595 {
596  Agnode_t *n;
597 
598  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
599  if (!ONPATH(n))
600  place_node(g, n, list);
601  }
602 }
603 
604 nodelist_t *layout_block(Agraph_t * g, block_t * sn, double min_dist)
605 {
606  Agnode_t *n;
607  Agraph_t *copyG, *tree, *subg;
608  nodelist_t *longest_path;
610  int N, k;
611  double theta, radius, largest_node;
612  largest_node = 0;
613 
614  subg = sn->sub_graph;
615  block_graph(g, sn); /* add induced edges */
616 
617  copyG = remove_pair_edges(subg);
618 
619  tree = spanning_tree(copyG);
620  longest_path = find_longest_path(tree);
621  place_residual_nodes(subg, longest_path);
622  /* at this point, longest_path is a list of all nodes in the block */
623 
624  /* apply crossing reduction algorithms here */
625  longest_path = reduce_edge_crossings(longest_path, subg);
626 
627  N = sizeNodelist(longest_path);
628  largest_node = largest_nodesize(longest_path);
629  /* N*(min_dist+largest_node) is roughly circumference of required circle */
630  if (N == 1)
631  radius = 0;
632  else
633  radius = (N * (min_dist + largest_node)) / (2 * M_PI);
634 
635  for (item = longest_path->first; item; item = item->next) {
636  n = item->curr;
637  if (ISPARENT(n)) {
638  /* QUESTION: Why is only one parent realigned? */
639  realignNodelist(longest_path, item);
640  break;
641  }
642  }
643 
644  k = 0;
645  for (item = longest_path->first; item; item = item->next) {
646  n = item->curr;
647  POSITION(n) = k;
648  PSI(n) = 0.0;
649  theta = k * ((2.0 * M_PI) / N);
650 
651  ND_pos(n)[0] = radius * cos(theta);
652  ND_pos(n)[1] = radius * sin(theta);
653 
654  k++;
655  }
656 
657  if (N == 1)
658  sn->radius = largest_node / 2;
659  else
660  sn->radius = radius;
661  sn->rad0 = sn->radius;
662 
663  /* initialize parent pos */
664  sn->parent_pos = -1;
665 
666  agclose(copyG);
667  return longest_path;
668 }
669 
670 #ifdef DEBUG
671 void prTree(Agraph_t * g)
672 {
673  Agnode_t *n;
674 
675  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
676  if (TPARENT(n)) {
677  fprintf(stderr, "%s ", agnameof(n));
678  fprintf(stderr, "-> %s\n", agnameof(TPARENT(n)));
679  }
680  }
681 }
682 #endif
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
CGRAPH_API Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
Agdesc_t desc
Definition: cgraph.h:241
#define SMALLBUF
Definition: const.h:17
CGRAPH_API Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition: edge.c:56
double parent_pos
Definition: block.h:38
nodelistitem_t * last
Definition: nodelist.h:33
void insertNodelist(nodelist_t *list, Agnode_t *cn, Agnode_t *neighbor, int pos)
Definition: nodelist.c:192
double radius
Definition: block.h:34
Agnode_t * firstDeglist(deglist_t *list)
Definition: deglist.c:129
#define dtfirst(d)
Definition: cdt.h:254
#define VISITED(n)
Definition: circular.h:109
#define UNSET_VISITED(n)
Definition: circular.h:121
#define ONPATH(n)
Definition: circular.h:112
Agedge_t * edge
Definition: edgelist.h:25
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
#define ND_pos(n)
Definition: types.h:526
#define ORIGE(e)
Definition: blockpath.c:24
#define parent(i)
Definition: closest.c:88
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
void insertDeglist(deglist_t *ns, Agnode_t *n)
Definition: deglist.c:84
#define TPARENT(n)
Definition: circular.h:95
void realignNodelist(nodelist_t *list, nodelistitem_t *np)
Definition: nodelist.c:152
void add_edge(edgelist *list, Agedge_t *e)
Definition: edgelist.c:65
#define DISTTWO(n)
Definition: circular.h:99
nodelist_t * cloneNodelist(nodelist_t *list)
Definition: nodelist.c:174
void freeDeglist(deglist_t *s)
Definition: deglist.c:75
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
struct path path
#define PSI(n)
Definition: circular.h:101
#define LEAFONE(n)
Definition: circular.h:96
nodelist_t * mkNodelist()
Definition: nodelist.c:26
void remove_edge(edgelist *list, Agedge_t *e)
Definition: edgelist.c:73
CGRAPH_API Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
#define NIL(t)
Definition: dthdr.h:13
#define SET_NEIGHBOR(n)
Definition: circular.h:119
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
double rad0
Definition: block.h:35
void reverseAppend(nodelist_t *l1, nodelist_t *l2)
Definition: nodelist.c:349
int sizeNodelist(nodelist_t *list)
Definition: nodelist.c:255
Agraph_t * sub_graph
Definition: block.h:33
#define SET_VISITED(n)
Definition: circular.h:115
void free_edgelist(edgelist *list)
Definition: edgelist.c:60
nodelistitem_t * first
Definition: nodelist.h:32
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ND_height(n)
Definition: types.h:504
#define dtnext(d, o)
Definition: cdt.h:255
void freeNodelist(nodelist_t *list)
Definition: nodelist.c:32
#define ISPARENT(n)
Definition: circular.h:111
CGRAPH_API Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition: edge.c:378
#define node_degree(i)
Definition: Multilevel.c:324
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define BLOCK(n)
Definition: circular.h:90
Definition: block.h:30
#define CLONE(n)
Definition: circular.h:94
nodelist_t * layout_block(Agraph_t *g, block_t *sn, double min_dist)
Definition: blockpath.c:604
#define ND_width(n)
Definition: types.h:542
#define DEGREE(n)
Definition: circular.h:125
void appendNodelist(nodelist_t *list, nodelistitem_t *one, Agnode_t *n)
Definition: nodelist.c:51
node_t * curr
Definition: nodelist.h:26
#define NULL
Definition: logic.h:39
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
struct item_s item
CGRAPH_API Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
#define ORIGN(n)
Definition: circular.h:87
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
#define SET_ONPATH(n)
Definition: circular.h:118
#define agfindedge(g, t, h)
Definition: types.h:610
Definition: cdt.h:99
#define M_PI
Definition: arith.h:77
#define EDGEORDER(e)
Definition: circular.h:83
#define UNSET_NEIGHBOR(n)
Definition: circular.h:123
#define LEAFTWO(n)
Definition: circular.h:97
double dist(Site *s, Site *t)
Definition: site.c:41
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define POSITION(n)
Definition: circular.h:100
#define DISTONE(n)
Definition: circular.h:98
void removeDeglist(deglist_t *list, Agnode_t *n)
Definition: deglist.c:98
#define CROSS_ITER
Definition: blockpath.c:452
#define NEIGHBOR(n)
Definition: circular.h:113
#define N_GNEW(n, t)
Definition: agxbuf.c:20
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
edgelist * init_edgelist()
Definition: edgelist.c:54
deglist_t * mkDeglist(void)
Definition: deglist.c:65
nodelistitem_t * next
Definition: nodelist.h:27
#define TRUE
Definition: cgraph.h:38