Graphviz  2.41.20170921.2350
blocktree.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 "blocktree.h"
16 
17 static void addNode(block_t * bp, Agnode_t * n)
18 {
19  agsubnode(bp->sub_graph, n,1);
20  BLOCK(n) = bp;
21 }
22 
23 static 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 
34 static 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 
42 typedef struct {
44  int sz;
45 } estack;
46 
47 static void
48 push (estack* s, Agedge_t* e)
49 {
50  ENEXT(e) = s->top;
51  s->top = e;
52  s->sz += 1;
53 }
54 
55 static Agedge_t*
56 pop (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  */
86 static 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  */
146 static 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  */
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 
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
238 static void indent(int i)
239 {
240  while (i--)
241  fputs(" ", stderr);
242 }
243 
244 void 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
void appendBlock(blocklist_t *bl, block_t *bp)
Definition: block.c:67
#define MIN(a, b)
Definition: arith.h:35
#define LOWVAL(n)
Definition: circular.h:93
#define SMALLBUF
Definition: const.h:17
attrsym_t * N_root
Definition: circular.h:25
void initBlocklist(blocklist_t *bl)
Definition: block.c:20
#define assert(x)
Definition: cghdr.h:47
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
int sz
Definition: blocktree.c:44
#define parent(i)
Definition: closest.c:88
int blockCount
Definition: circular.h:23
#define CHILD(b)
Definition: block.h:55
block_t * createBlocktree(Agraph_t *g, circ_state *state)
Definition: blocktree.c:181
#define PARENT(n)
Definition: circular.h:89
Agedge_t * top
Definition: blocktree.c:43
int orderCount
Definition: circular.h:22
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
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
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
Agraph_t * sub_graph
Definition: block.h:33
void insertBlock(blocklist_t *bl, block_t *bp)
Definition: block.c:82
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
char * rootname
Definition: circular.h:26
int blockSize(block_t *sp)
Definition: block.c:59
block_t * first
Definition: block.h:26
block_t * mkBlock(Agraph_t *g)
Definition: block.c:41
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
#define BLOCK(n)
Definition: circular.h:90
Definition: block.h:30
#define push(s, x)
Definition: closest.c:63
#define agfindnode(g, n)
Definition: types.h:611
blocklist_t bl
Definition: circular.h:21
#define NULL
Definition: logic.h:39
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
void freeBlocktree(block_t *bp)
Definition: blocktree.c:224
block_t * next
Definition: block.h:32
#define VAL(n)
Definition: circular.h:92
EXTERN unsigned char Verbose
Definition: globals.h:64
#define top(sp)
Definition: stack.h:35
#define ENEXT(e)
Definition: circular.h:82
void freeBlock(block_t *sp)
Definition: block.c:51
#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
#define SET_PARENT(n)
Definition: circular.h:117
#define EDGEORDER(e)
Definition: circular.h:83
blocklist_t children
Definition: block.h:37
#define pop(s, x)
Definition: closest.c:71
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
boolean late_bool(void *obj, attrsym_t *attr, int def)
Definition: utils.c:137
#define TRUE
Definition: cgraph.h:38