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 */
31static 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 */
74static 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 */
87static 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 */
189static 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
235static void
236measure_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 */
276static 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 */
335static 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 */
358static 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 */
389static 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
403static int count_all_crossings(nodelist_t * list, Agraph_t * subg)
404{
405 nodelistitem_t *item;
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 */
459static 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
499static 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 */
521static double largest_nodesize(nodelist_t * list)
522{
523 Agnode_t *n;
524 nodelistitem_t *item;
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 */
540static 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 */
594static 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
604nodelist_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;
609 nodelistitem_t *item;
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
671void 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
683