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 "blocktree.h"
16
17static void addNode(block_t * bp, Agnode_t * n)
18{
19 agsubnode(bp->sub_graph, n,1);
20 BLOCK(n) = bp;
21}
22
23static Agraph_t *makeBlockGraph(Agraph_t * g, circ_state * state)
24{
25 char name[SMALLBUF];
26 Agraph_t *subg;
27
28 sprintf(name, "_block_%d", state->blockCount++);
29 subg = agsubg(g, name,1);
30 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
31 return subg;
32}
33
34static block_t *makeBlock(Agraph_t * g, circ_state * state)
35{
36 Agraph_t *subg = makeBlockGraph(g, state);
37 block_t *bp = mkBlock(subg);
38
39 return bp;
40}
41
42typedef struct {
43 Agedge_t *top;
44 int sz;
45} estack;
46
47static void
48push (estack* s, Agedge_t* e)
49{
50 ENEXT(e) = s->top;
51 s->top = e;
52 s->sz += 1;
53}
54
55static Agedge_t*
56pop (estack* s)
57{
58 Agedge_t *top = s->top;
59
60 if (top) {
61 assert(s->sz > 0);
62 s->top = ENEXT(top);
63 s->sz -= 1;
64 } else {
65 assert(0);
66 }
67
68 return top;
69}
70
71
72/* dfs:
73 *
74 * Current scheme adds articulation point to first non-trivial child
75 * block. If none exists, it will be added to its parent's block, if
76 * non-trivial, or else given its own block.
77 *
78 * FIX:
79 * This should be modified to:
80 * - allow user to specify which block gets a node, perhaps on per-node basis.
81 * - if an articulation point is not used in one of its non-trivial blocks,
82 * dummy edges should be added to preserve biconnectivity
83 * - turn on user-supplied blocks.
84 * - Post-process to move articulation point to largest block
85 */
86static void dfs(Agraph_t * g, Agnode_t * u, circ_state * state, int isRoot, estack* stk)
87{
88 Agedge_t *e;
89 Agnode_t *v;
90
91 LOWVAL(u) = VAL(u) = state->orderCount++;
92 for (e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) {
93 v = aghead (e);
94 if (v == u) {
95 v = agtail(e);
96 if (!EDGEORDER(e)) EDGEORDER(e) = -1;
97 }
98 else {
99 if (!EDGEORDER(e)) EDGEORDER(e) = 1;
100 }
101
102 if (VAL(v) == 0) { /* Since VAL(root) == 0, it gets treated as artificial cut point */
103 PARENT(v) = u;
104 push(stk, e);
105 dfs(g, v, state, 0, stk);
106 LOWVAL(u) = MIN(LOWVAL(u), LOWVAL(v));
107 if (LOWVAL(v) >= VAL(u)) { /* u is an articulation point */
108 block_t *block = NULL;
109 Agnode_t *np;
110 Agedge_t *ep;
111 do {
112 ep = pop(stk);
113 if (EDGEORDER(ep) == 1)
114 np = aghead (ep);
115 else
116 np = agtail (ep);
117 if (!BLOCK(np)) {
118 if (!block)
119 block = makeBlock(g, state);
120 addNode(block, np);
121 }
122 } while (ep != e);
123 if (block) { /* If block != NULL, it's not empty */
124 if (!BLOCK(u) && blockSize (block) > 1)
125 addNode(block, u);
126 if (isRoot && (BLOCK(u) == block))
127 insertBlock(&state->bl, block);
128 else
129 appendBlock(&state->bl, block);
130 }
131 }
132 } else if (PARENT(u) != v) {
133 LOWVAL(u) = MIN(LOWVAL(u), VAL(v));
134 }
135 }
136 if (isRoot && !BLOCK(u)) {
137 block_t *block = makeBlock(g, state);
138 addNode(block, u);
139 insertBlock(&state->bl, block);
140 }
141}
142
143
144/* find_blocks:
145 */
146static void find_blocks(Agraph_t * g, circ_state * state)
147{
148 Agnode_t *n;
149 Agnode_t *root = NULL;
150 estack stk;
151
152 /* check to see if there is a node which is set to be the root
153 */
154 if (state->rootname) {
155 root = agfindnode(g, state->rootname);
156 }
157 if (!root && state->N_root) {
158 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
159 if (late_bool(ORIGN(n), state->N_root, 0)) {
160 root = n;
161 break;
162 }
163 }
164 }
165
166 if (!root)
167 root = agfstnode(g);
168 if (Verbose)
169 fprintf (stderr, "root = %s\n", agnameof(root));
170 stk.sz = 0;
171 stk.top = NULL;
172 dfs(g, root, state, 1, &stk);
173
174}
175
176/* create_block_tree:
177 * Construct block tree by peeling nodes from block list in state.
178 * When done, return root. The block list is empty
179 * FIX: use largest block as root
180 */
181block_t *createBlocktree(Agraph_t * g, circ_state * state)
182{
183 block_t *bp;
184 block_t *next;
185 block_t *root;
186 int min;
187 /* int ordercnt; */
188
189 find_blocks(g, state);
190
191 bp = state->bl.first; /* if root chosen, will be first */
192 /* Otherwise, just pick first as root */
193 root = bp;
194
195 /* Find node with minimum VAL value to find parent block */
196 /* FIX: Should be some way to avoid search below. */
197 /* ordercnt = state->orderCount; */
198 for (bp = bp->next; bp; bp = next) {
199 Agnode_t *n;
200 Agnode_t *parent;
201 Agnode_t *child;
202 Agraph_t *subg = bp->sub_graph;
203
204 child = n = agfstnode(subg);
205
206 min = VAL(n);
207 parent = PARENT(n);
208 for (n = agnxtnode(subg, n); n; n = agnxtnode(subg, n)) {
209 if (VAL(n) < min) {
210 child = n;
211 min = VAL(n);
212 parent = PARENT(n);
213 }
214 }
215 SET_PARENT(parent);
216 CHILD(bp) = child;
217 next = bp->next; /* save next since list insertion destroys it */
218 appendBlock(&(BLOCK(parent)->children), bp);
219 }
220 initBlocklist(&state->bl); /* zero out list */
221 return root;
222}
223
224void freeBlocktree(block_t * bp)
225{
226 block_t *child;
227 block_t *next;
228
229 for (child = bp->children.first; child; child = next) {
230 next = child->next;
231 freeBlocktree(child);
232 }
233
234 freeBlock(bp);
235}
236
237#ifdef DEBUG
238static void indent(int i)
239{
240 while (i--)
241 fputs(" ", stderr);
242}
243
244void print_blocktree(block_t * sn, int depth)
245{
246 block_t *child;
247 Agnode_t *n;
248 Agraph_t *g;
249
250 indent(depth);
251 g = sn->sub_graph;
252 fprintf(stderr, "%s:", agnameof(g));
253 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
254 fprintf(stderr, " %s", agnameof(n));
255 }
256 fputs("\n", stderr);
257
258 depth++;
259 for (child = sn->children.first; child; child = child->next) {
260 print_blocktree(child, depth);
261 }
262}
263
264#endif
265