Graphviz 13.1.3~dev.20250905.1412
Loading...
Searching...
No Matches
blockpath.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 <circogen/blockpath.h>
12#include <circogen/circular.h>
13#include <circogen/edgelist.h>
14#include <stddef.h>
15#include <stdbool.h>
16#include <util/agxbuf.h>
17#include <util/alloc.h>
18#include <util/list.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 * @param state Context containing a counter to use for graph copy naming
32 */
33static Agraph_t *clone_graph(Agraph_t *ing, Agraph_t **xg, circ_state *state) {
34 Agraph_t *clone;
35 Agraph_t *xclone;
36 Agnode_t *n;
37 Agnode_t *xn;
38 Agnode_t *xh;
39 Agedge_t *e;
40 Agedge_t *xe;
41 agxbuf gname = {0};
42
43 agxbprint(&gname, "_clone_%d", state->graphCopyCount++);
44 clone = agsubg(ing, agxbuse(&gname), 1);
45 agbindrec(clone, "Agraphinfo_t", sizeof(Agraphinfo_t), true); //node custom data
46 agxbprint(&gname, "_clone_%d", state->graphCopyCount++);
47 xclone = agopen(agxbuse(&gname), ing->desc, NULL);
49 for (n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
50 agsubnode(clone,n,1);
51 xn = agnode(xclone, agnameof(n),1);
52 agbindrec(xn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true); //node custom data
53 CLONE(n) = xn;
54 }
55
56 for (n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
57 xn = CLONE(n);
58 for (e = agfstout(ing, n); e; e = agnxtout(ing, e)) {
59 agsubedge(clone,e,1);
60 xh = CLONE(aghead(e));
61 xe = agedge(xclone, xn, xh, NULL, 1);
62 agbindrec(xe, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true); //node custom data
63 ORIGE(xe) = e;
64 DEGREE(xn) += 1;
65 DEGREE(xh) += 1;
66 }
67 }
68 *xg = xclone;
69 return clone;
70}
71
72typedef LIST(Agnode_t *) deglist_t;
73
75static int cmpDegree(const void *x, const void *y) {
76 Agnode_t *const *a = x;
77 Agnode_t *const *b = y;
78 if (DEGREE(*a) < DEGREE(*b)) {
79 return 1;
80 }
81 if (DEGREE(*a) > DEGREE(*b)) {
82 return -1;
83 }
84 return 0;
85}
86
88static deglist_t getList(Agraph_t *g) {
89 deglist_t dl = {0};
90 Agnode_t *n;
91
92 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
93 LIST_APPEND(&dl, n);
94 }
95 LIST_SORT(&dl, cmpDegree);
96 return dl;
97}
98
99static void find_pair_edges(Agraph_t * g, Agnode_t * n, Agraph_t * outg)
100{
101 Agedge_t *e;
102 Agedge_t *ep;
103 Agedge_t *ex;
104 Agnode_t *n1;
105 Agnode_t *n2;
106 int has_pair_edge;
107 int diff;
108 int has_pair_count = 0;
109 int no_pair_count = 0;
110 int node_degree;
111 int edge_cnt = 0;
112
113 node_degree = DEGREE(n);
114 Agnode_t **neighbors_with = gv_calloc(node_degree, sizeof(Agnode_t*));
115 Agnode_t **neighbors_without = gv_calloc(node_degree, sizeof(Agnode_t*));
116
117 for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
118 n1 = aghead(e);
119 if (n1 == n)
120 n1 = agtail(e);
121 has_pair_edge = 0;
122 for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
123 if (ep == e)
124 continue;
125 n2 = aghead(ep);
126 if (n2 == n)
127 n2 = agtail(ep);
128 ex = agfindedge(g, n1, n2);
129 if (ex) {
130 has_pair_edge = 1;
131 if (n1 < n2) { /* count edge only once */
132 edge_cnt++;
133 if (ORIGE(ex)) {
134 agdelete(outg, ORIGE(ex));
135 ORIGE(ex) = 0; /* delete only once */
136 }
137 }
138 }
139 }
140 if (has_pair_edge) {
141 neighbors_with[has_pair_count] = n1;
142 has_pair_count++;
143 } else {
144 neighbors_without[no_pair_count] = n1;
145 no_pair_count++;
146 }
147 }
148
149 diff = node_degree - 1 - edge_cnt;
150 if (diff > 0) {
151 int mark;
152 Agnode_t *hp;
153 Agnode_t *tp;
154
155 if (diff < no_pair_count) {
156 for (mark = 0; mark < no_pair_count; mark += 2) {
157 if ((mark + 1) >= no_pair_count)
158 break;
159 tp = neighbors_without[mark];
160 hp = neighbors_without[mark + 1];
161 agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), true); // edge custom data
162 DEGREE(tp)++;
163 DEGREE(hp)++;
164 diff--;
165 }
166
167 mark = 2;
168 while (diff > 0) {
169 tp = neighbors_without[0];
170 hp = neighbors_without[mark];
171 agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), true); // edge custom data
172 DEGREE(tp)++;
173 DEGREE(hp)++;
174 mark++;
175 diff--;
176 }
177 }
178
179 else if (diff == no_pair_count) {
180 tp = neighbors_with[0];
181 for (mark = 0; mark < no_pair_count; mark++) {
182 hp = neighbors_without[mark];
183 agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), true); //node custom data
184 DEGREE(tp)++;
185 DEGREE(hp)++;
186 }
187 }
188 }
189
190 free(neighbors_without);
191 free(neighbors_with);
192}
193
198 int counter = 0;
199 int nodeCount;
200 Agraph_t *outg;
201 Agraph_t *g;
202 Agnode_t *currnode, *adjNode;
203 Agedge_t *e;
204
205 outg = clone_graph(ing, &g, state);
206 nodeCount = agnnodes(g);
207 deglist_t dl = getList(g);
208
209 while (counter < nodeCount - 3) {
210 currnode = LIST_IS_EMPTY(&dl) ? NULL : LIST_POP_BACK(&dl);
211
212 /* Remove all adjacent nodes since they have to be reinserted */
213 for (e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
214 adjNode = aghead(e);
215 if (currnode == adjNode)
216 adjNode = agtail(e);
217 LIST_REMOVE(&dl, adjNode);
218 }
219
220 find_pair_edges(g, currnode, outg);
221
222 for (e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
223 adjNode = aghead(e);
224 if (currnode == adjNode)
225 adjNode = agtail(e);
226
227 DEGREE(adjNode)--;
228 LIST_APPEND(&dl, adjNode);
229 }
230 LIST_SORT(&dl, cmpDegree);
231
232 agdelete(g, currnode);
233
234 counter++;
235 }
236
237 agclose(g);
238 LIST_FREE(&dl);
239 return outg;
240}
241
242static void
244 Agnode_t * change)
245{
247
248 parent = TPARENT(ancestor);
249 if (parent == NULL)
250 return;
251
252 dist++;
253
254 /* check parent to see if it has other leaf paths at greater distance
255 than the context node.
256 set the path/distance of the leaf at this ancestor node */
257
258 if (DISTONE(parent) == 0) {
259 LEAFONE(parent) = n;
261 } else if (dist > DISTONE(parent)) {
262 if (LEAFONE(parent) != change) {
263 if (!DISTTWO(parent) || LEAFTWO(parent) != change)
264 change = LEAFONE(parent);
267 }
268 LEAFONE(parent) = n;
270 } else if (dist > DISTTWO(parent)) {
271 LEAFTWO(parent) = n;
273 return;
274 } else
275 return;
276
277 measure_distance(n, parent, dist, change);
278}
279
281static nodelist_t find_longest_path(Agraph_t *tree) {
282 Agnode_t *n;
283 Agedge_t *e;
284 Agnode_t *common = 0;
285 int maxlength = 0;
286 int length;
287
288 if (agnnodes(tree) == 1) {
289 nodelist_t beginPath = {0};
290 n = agfstnode(tree);
291 LIST_APPEND(&beginPath, n);
292 SET_ONPATH(n);
293 return beginPath;
294 }
295
296 for (n = agfstnode(tree); n; n = agnxtnode(tree, n)) {
297 int count = 0;
298 for (e = agfstedge(tree, n); e; e = agnxtedge(tree, e, n)) {
299 count++;
300 }
301 if (count == 1)
302 measure_distance(n, n, 0, NULL);
303 }
304
305 /* find the branch node rooted at the longest path */
306 for (n = agfstnode(tree); n; n = agnxtnode(tree, n)) {
307 length = DISTONE(n) + DISTTWO(n);
308 if (length > maxlength) {
309 common = n;
310 maxlength = length;
311 }
312 }
313
314 nodelist_t beginPath = {0};
315 for (n = LEAFONE(common); n != common; n = TPARENT(n)) {
316 LIST_APPEND(&beginPath, n);
317 SET_ONPATH(n);
318 }
319 LIST_APPEND(&beginPath, common);
320 SET_ONPATH(common);
321
322 if (DISTTWO(common)) { /* 2nd path might be empty */
323 nodelist_t endPath = {0};
324 for (n = LEAFTWO(common); n != common; n = TPARENT(n)) {
325 LIST_APPEND(&endPath, n);
326 SET_ONPATH(n);
327 }
328 reverseAppend(&beginPath, &endPath);
329 }
330
331 return beginPath;
332}
333
335static void dfs(Agraph_t * g, Agnode_t * n, Agraph_t * tree)
336{
337 Agedge_t *e;
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
359 Agnode_t *n;
360 Agraph_t *tree;
361 agxbuf gname = {0};
362
363 agxbprint(&gname, "_span_%d", state->spanningTreeCount++);
364 tree = agsubg(g, agxbuse(&gname), 1);
365 agxbfree(&gname);
366 agbindrec(tree, "Agraphinfo_t", sizeof(Agraphinfo_t), true); //node custom data
367
368 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
369 agsubnode(tree,n,1);
370 DISTONE(n) = 0;
371 DISTTWO(n) = 0;
372 UNSET_VISITED(n);
373 }
374
375 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
376 if (!VISITED(n)) {
377 TPARENT(n) = NULL;
378 dfs(g, n, tree);
379 }
380 }
381
382 return tree;
383}
384
386static void block_graph(Agraph_t * g, block_t * sn)
387{
388 Agnode_t *n;
389 Agedge_t *e;
390 Agraph_t *subg = sn->sub_graph;
391
392 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
393 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
394 if (BLOCK(aghead(e)) == sn)
395 agsubedge(subg,e,1);
396 }
397 }
398}
399
400static int count_all_crossings(nodelist_t * list, Agraph_t * subg)
401{
402 edgelist *openEdgeList = init_edgelist();
403 Agnode_t *n;
404 Agedge_t *e;
405 int crossings = 0;
406 int order = 1;
407
408 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
409 for (e = agfstout(subg, n); e; e = agnxtout(subg, e)) {
410 EDGEORDER(e) = 0;
411 }
412 }
413
414 for (size_t item = 0; item < LIST_SIZE(list); ++item) {
415 n = LIST_GET(list, item);
416
417 for (e = agfstedge(subg, n); e; e = agnxtedge(subg, e, n)) {
418 if (EDGEORDER(e) > 0) {
419 edgelistitem *eitem;
420 Agedge_t *ep;
421
422 for (eitem = dtfirst(openEdgeList); eitem;
423 eitem = dtnext(openEdgeList, eitem)) {
424 ep = eitem->edge;
425 if (EDGEORDER(ep) > EDGEORDER(e)) {
426 if (aghead(ep) != n && agtail(ep) != n)
427 crossings++;
428 }
429 }
430 remove_edge(openEdgeList, e);
431 }
432 }
433
434 for (e = agfstedge(subg, n); e; e = agnxtedge(subg, e, n)) {
435 if (EDGEORDER(e) == 0) {
436 EDGEORDER(e) = order;
437 add_edge(openEdgeList, e);
438 }
439 }
440 order++;
441 }
442
443 free_edgelist(openEdgeList);
444 return crossings;
445}
446
447#define CROSS_ITER 10
448
449/* Attempt to reduce edge crossings by moving nodes.
450 * Original crossing count is in cnt; final count is returned there.
451 * list is the original list; return the best list found.
452 */
453static nodelist_t reduce(nodelist_t list, Agraph_t *subg, int *cnt) {
454 Agnode_t *curnode;
455 Agedge_t *e;
457 int crossings, j, newCrossings;
458
459 crossings = *cnt;
460 for (curnode = agfstnode(subg); curnode;
461 curnode = agnxtnode(subg, curnode)) {
462 /* move curnode next to its neighbors */
463 for (e = agfstedge(subg, curnode); e;
464 e = agnxtedge(subg, e, curnode)) {
465 neighbor = agtail(e);
466 if (neighbor == curnode)
467 neighbor = aghead(e);
468
469 for (j = 0; j < 2; j++) {
470 nodelist_t listCopy;
471 LIST_COPY(&listCopy, &list);
472 insertNodelist(&list, curnode, neighbor, j);
473 newCrossings = count_all_crossings(&list, subg);
474 if (newCrossings < crossings) {
475 crossings = newCrossings;
476 LIST_FREE(&listCopy);
477 if (crossings == 0) {
478 *cnt = 0;
479 return list;
480 }
481 } else {
482 LIST_FREE(&list);
483 list = listCopy;
484 }
485 }
486 }
487 }
488 *cnt = crossings;
489 return list;
490}
491
492static nodelist_t reduce_edge_crossings(nodelist_t list, Agraph_t *subg) {
493 int i, crossings, origCrossings;
494
495 crossings = count_all_crossings(&list, subg);
496 if (crossings == 0)
497 return list;
498
499 for (i = 0; i < CROSS_ITER; i++) {
500 origCrossings = crossings;
501 list = reduce(list, subg, &crossings);
502 /* return if no crossings or no improvement */
503 if (origCrossings == crossings || crossings == 0)
504 return list;
505 }
506 return list;
507}
508
510static double largest_nodesize(nodelist_t * list)
511{
512 double size = 0;
513
514 for (size_t item = 0; item < LIST_SIZE(list); ++item) {
515 Agnode_t *n = ORIGN(LIST_GET(list, item));
516 if (ND_width(n) > size)
517 size = ND_width(n);
518 if (ND_height(n) > size)
519 size = ND_height(n);
520 }
521 return size;
522}
523
525static void place_node(Agraph_t * g, Agnode_t * n, nodelist_t * list)
526{
527 Agedge_t *e;
528 bool placed = false;
529 nodelist_t neighbors = {0};
530
531 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
532 LIST_APPEND(&neighbors, aghead(e));
534 }
535 for (e = agfstin(g, n); e; e = agnxtin(g, e)) {
536 LIST_APPEND(&neighbors, agtail(e));
538 }
539
540 /* Look for 2 neighbors consecutive on list */
541 if (LIST_SIZE(&neighbors) >= 2) {
542 for (size_t one = 0; one < LIST_SIZE(list); ++one) {
543 const size_t two = (one + 1) % LIST_SIZE(list);
544
545 if (NEIGHBOR(LIST_GET(list, one)) && NEIGHBOR(LIST_GET(list, two))) {
546 appendNodelist(list, one + 1, n);
547 placed = true;
548 break;
549 }
550 }
551 }
552
553 /* Find any neighbor on list */
554 if (!placed && !LIST_IS_EMPTY(&neighbors)) {
555 for (size_t one = 0; one < LIST_SIZE(list); ++one) {
556 if (NEIGHBOR(LIST_GET(list, one))) {
557 appendNodelist(list, one + 1, n);
558 placed = true;
559 break;
560 }
561 }
562 }
563
564 if (!placed)
565 LIST_APPEND(list, n);
566
567 for (size_t one = 0; one < LIST_SIZE(&neighbors); ++one)
568 UNSET_NEIGHBOR(LIST_GET(&neighbors, one));
569 LIST_FREE(&neighbors);
570}
571
573static void place_residual_nodes(Agraph_t * g, nodelist_t * list)
574{
575 Agnode_t *n;
576
577 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
578 if (!ONPATH(n))
579 place_node(g, n, list);
580 }
581}
582
584nodelist_t layout_block(Agraph_t *g, block_t *sn, double min_dist,
585 circ_state *state) {
586 Agraph_t *copyG, *tree, *subg;
587 int k;
588 double theta, radius, largest_node;
589 largest_node = 0;
590
591 subg = sn->sub_graph;
592 block_graph(g, sn); /* add induced edges */
593
594 copyG = remove_pair_edges(subg, state);
595
596 tree = spanning_tree(copyG, state);
597 nodelist_t longest_path = find_longest_path(tree);
598 place_residual_nodes(subg, &longest_path);
599 /* at this point, longest_path is a list of all nodes in the block */
600
601 /* apply crossing reduction algorithms here */
602 longest_path = reduce_edge_crossings(longest_path, subg);
603
604 size_t N = LIST_SIZE(&longest_path);
605 largest_node = largest_nodesize(&longest_path);
606 /* N*(min_dist+largest_node) is roughly circumference of required circle */
607 if (N == 1)
608 radius = 0;
609 else
610 radius = (double)N * (min_dist + largest_node) / (2 * M_PI);
611
612 for (size_t item = 0; item < LIST_SIZE(&longest_path); ++item) {
613 Agnode_t *n = LIST_GET(&longest_path, item);
614 if (ISPARENT(n)) {
615 /* QUESTION: Why is only one parent realigned? */
616 realignNodelist(&longest_path, item);
617 break;
618 }
619 }
620
621 k = 0;
622 for (size_t item = 0; item < LIST_SIZE(&longest_path); ++item) {
623 Agnode_t *n = LIST_GET(&longest_path, item);
624 POSITION(n) = k;
625 PSI(n) = 0.0;
626 theta = k * (2.0 * M_PI / (double)N);
627
628 ND_pos(n)[0] = radius * cos(theta);
629 ND_pos(n)[1] = radius * sin(theta);
630
631 k++;
632 }
633
634 if (N == 1)
635 sn->radius = largest_node / 2;
636 else
637 sn->radius = radius;
638 sn->rad0 = sn->radius;
639
640 /* initialize parent pos */
641 sn->parent_pos = -1;
642
643 agclose(copyG);
644 return longest_path;
645}
646
647#ifdef DEBUG
648void prTree(Agraph_t * g)
649{
650 Agnode_t *n;
651
652 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
653 if (TPARENT(n)) {
654 fprintf(stderr, "%s ", agnameof(n));
655 fprintf(stderr, "-> %s\n", agnameof(TPARENT(n)));
656 }
657 }
658}
659#endif
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:77
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:233
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:306
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define M_PI
Definition arith.h:41
#define N(n)
Definition bcomps.c:58
static int count_all_crossings(nodelist_t *list, Agraph_t *subg)
Definition blockpath.c:400
static void place_node(Agraph_t *g, Agnode_t *n, nodelist_t *list)
Add n to list. By construction, n is not in list at start.
Definition blockpath.c:525
static nodelist_t find_longest_path(Agraph_t *tree)
Find and return longest path in tree.
Definition blockpath.c:281
static void block_graph(Agraph_t *g, block_t *sn)
Add induced edges.
Definition blockpath.c:386
static nodelist_t reduce(nodelist_t list, Agraph_t *subg, int *cnt)
Definition blockpath.c:453
static void place_residual_nodes(Agraph_t *g, nodelist_t *list)
Add nodes not in list to list.
Definition blockpath.c:573
static void dfs(Agraph_t *g, Agnode_t *n, Agraph_t *tree)
Simple depth first search, adding traversed edges to tree.
Definition blockpath.c:335
static double largest_nodesize(nodelist_t *list)
Return max dimension of nodes on list.
Definition blockpath.c:510
#define CROSS_ITER
Definition blockpath.c:447
static Agraph_t * spanning_tree(Agraph_t *g, circ_state *state)
Definition blockpath.c:358
static void find_pair_edges(Agraph_t *g, Agnode_t *n, Agraph_t *outg)
Definition blockpath.c:99
static void measure_distance(Agnode_t *n, Agnode_t *ancestor, int dist, Agnode_t *change)
Definition blockpath.c:243
static Agraph_t * clone_graph(Agraph_t *ing, Agraph_t **xg, circ_state *state)
Definition blockpath.c:33
static Agraph_t * remove_pair_edges(Agraph_t *ing, circ_state *state)
Definition blockpath.c:197
static deglist_t getList(Agraph_t *g)
Add nodes to deg_list, storing them by descending degree.
Definition blockpath.c:88
nodelist_t layout_block(Agraph_t *g, block_t *sn, double min_dist, circ_state *state)
Definition blockpath.c:584
static nodelist_t reduce_edge_crossings(nodelist_t list, Agraph_t *subg)
Definition blockpath.c:492
#define ORIGE(e)
Definition blockpath.c:24
#define dtnext(d, o)
Definition cdt.h:180
#define dtfirst(d)
Definition cdt.h:179
#define BLOCK(n)
Definition circular.h:85
#define DEGREE(n)
Definition circular.h:120
#define SET_ONPATH(n)
Definition circular.h:113
#define VISITED(n)
Definition circular.h:104
#define EDGEORDER(e)
Definition circular.h:78
#define LEAFONE(n)
Definition circular.h:91
#define UNSET_NEIGHBOR(n)
Definition circular.h:118
#define POSITION(n)
Definition circular.h:95
#define CLONE(n)
Definition circular.h:89
#define SET_VISITED(n)
Definition circular.h:110
#define UNSET_VISITED(n)
Definition circular.h:116
#define ORIGN(n)
Definition circular.h:82
#define ISPARENT(n)
Definition circular.h:106
#define NEIGHBOR(n)
Definition circular.h:108
#define DISTONE(n)
Definition circular.h:93
#define SET_NEIGHBOR(n)
Definition circular.h:114
#define PSI(n)
Definition circular.h:96
#define DISTTWO(n)
Definition circular.h:94
#define ONPATH(n)
Definition circular.h:107
#define TPARENT(n)
Definition circular.h:90
#define LEAFTWO(n)
Definition circular.h:92
#define parent(i)
Definition closest.c:81
static Extype_t length(Exid_t *rhs, Exdisc_t *disc)
Definition compile.c:1606
void add_edge(edgelist *list, Agedge_t *e)
Definition edgelist.c:57
edgelist * init_edgelist(void)
Definition edgelist.c:46
void free_edgelist(edgelist *list)
Definition edgelist.c:52
void remove_edge(edgelist *list, Agedge_t *e)
Definition edgelist.c:65
static void endPath(bezier_path_t *polypath)
Definition ellipse.c:194
static double dist(int dim, double *x, double *y)
static char * gname
Definition gml2gv.c:25
void free(void *)
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
int agnnodes(Agraph_t *g)
Definition graph.c:155
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition edge.c:253
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition edge.c:348
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition edge.c:71
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:988
#define agfindedge(g, t, h)
Definition types.h:609
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:96
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition edge.c:57
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:95
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Definition graph.c:42
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition node.c:141
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition node.c:252
#define ND_height(n)
Definition types.h:498
#define ND_width(n)
Definition types.h:536
#define ND_pos(n)
Definition types.h:520
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
int agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
Definition obj.c:20
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:89
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition subg.c:53
@ tree
Definition gvgen.c:34
static void mark(const stk_t *stk, Agnode_t *n)
set a mark on n
Definition ccomps.c:36
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_POP_BACK(list)
Definition list.h:416
#define LIST_SORT(list, cmp)
Definition list.h:347
#define LIST_IS_EMPTY(list)
Definition list.h:90
#define LIST_COPY(dst, src)
Definition list.h:295
#define LIST_REMOVE(list, item)
Definition list.h:227
#define LIST_GET(list, index)
Definition list.h:165
#define neighbor(t, i, edim, elist)
Definition make_map.h:41
void realignNodelist(nodelist_t *list, size_t np)
Make np new front of list, with current last hooked to current first.
Definition nodelist.c:36
void insertNodelist(nodelist_t *list, Agnode_t *cn, Agnode_t *neighbor, int pos)
Definition nodelist.c:46
void reverseAppend(nodelist_t *l1, nodelist_t *l2)
Create l1 @ (rev l2) Destroys and frees l2.
Definition nodelist.c:72
void appendNodelist(nodelist_t *list, size_t one, Agnode_t *n)
Add node after one.
Definition nodelist.c:19
#define node_degree(i)
graph or subgraph
Definition cgraph.h:424
Agdesc_t desc
Definition cgraph.h:426
Definition block.h:26
double radius
Definition block.h:30
Agraph_t * sub_graph
Definition block.h:29
double parent_pos
Definition block.h:34
double rad0
Definition block.h:31
int graphCopyCount
how many cloned graphs have we created?
Definition circular.h:20
int spanningTreeCount
how many spanning trees have we created?
Definition circular.h:21
Definition cdt.h:100
Agedge_t * edge
Definition edgelist.h:21
Definition utils.c:751