Graphviz 13.1.3~dev.20250831.0023
Loading...
Searching...
No Matches
blocktree.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/blocktree.h>
12#include <stdbool.h>
13#include <util/agxbuf.h>
14#include <util/debug.h>
15#include <util/gv_math.h>
16#include <util/list.h>
17
18static void addNode(block_t * bp, Agnode_t * n)
19{
20 agsubnode(bp->sub_graph, n,1);
21 BLOCK(n) = bp;
22}
23
25{
26 agxbuf name = {0};
27
28 agxbprint(&name, "_block_%d", state->blockCount++);
29 Agraph_t *subg = agsubg(g, agxbuse(&name), 1);
30 agxbfree(&name);
31 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true); //node custom data
32 return subg;
33}
34
35static block_t *makeBlock(Agraph_t * g, circ_state * state)
36{
37 Agraph_t *subg = makeBlockGraph(g, state);
38 block_t *bp = mkBlock(subg);
39
40 return bp;
41}
42
43typedef LIST(Agedge_t *) estack_t;
44
45/* Current scheme adds articulation point to first non-trivial child
46 * block. If none exists, it will be added to its parent's block, if
47 * non-trivial, or else given its own block.
48 *
49 * FIX:
50 * This should be modified to:
51 * - allow user to specify which block gets a node, perhaps on per-node basis.
52 * - if an articulation point is not used in one of its non-trivial blocks,
53 * dummy edges should be added to preserve biconnectivity
54 * - turn on user-supplied blocks.
55 * - Post-process to move articulation point to largest block
56 */
57static void dfs(Agraph_t *g, Agnode_t *u, circ_state *state, bool isRoot,
58 estack_t *stk) {
59 LOWVAL(u) = VAL(u) = state->orderCount++;
60 for (Agedge_t *e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) {
61 Agnode_t *v = aghead (e);
62 if (v == u) {
63 v = agtail(e);
64 if (!EDGEORDER(e)) EDGEORDER(e) = -1;
65 }
66 else {
67 if (!EDGEORDER(e)) EDGEORDER(e) = 1;
68 }
69
70 if (VAL(v) == 0) { /* Since VAL(root) == 0, it gets treated as artificial cut point */
71 PARENT(v) = u;
72 LIST_PUSH_BACK(stk, e);
73 dfs(g, v, state, false, stk);
74 LOWVAL(u) = imin(LOWVAL(u), LOWVAL(v));
75 if (LOWVAL(v) >= VAL(u)) { /* u is an articulation point */
77 Agnode_t *np;
78 Agedge_t *ep;
79 do {
80 ep = LIST_POP_BACK(stk);
81 if (EDGEORDER(ep) == 1)
82 np = aghead (ep);
83 else
84 np = agtail (ep);
85 if (!BLOCK(np)) {
86 if (!block)
87 block = makeBlock(g, state);
88 addNode(block, np);
89 }
90 } while (ep != e);
91 if (block) { /* If block != NULL, it's not empty */
92 if (!BLOCK(u) && blockSize (block) > 1)
93 addNode(block, u);
94 if (isRoot && BLOCK(u) == block)
95 insertBlock(&state->bl, block);
96 else
97 appendBlock(&state->bl, block);
98 }
99 }
100 } else if (PARENT(u) != v) {
101 LOWVAL(u) = imin(LOWVAL(u), VAL(v));
102 }
103 }
104 if (isRoot && !BLOCK(u)) {
105 block_t *block = makeBlock(g, state);
106 addNode(block, u);
107 insertBlock(&state->bl, block);
108 }
109}
110
111static void find_blocks(Agraph_t * g, circ_state * state)
112{
113 Agnode_t *root = NULL;
114
115 /* check to see if there is a node which is set to be the root
116 */
117 if (state->rootname) {
118 root = agfindnode(g, state->rootname);
119 }
120 if (!root && state->N_root) {
121 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
122 if (late_bool(ORIGN(n), state->N_root, false)) {
123 root = n;
124 break;
125 }
126 }
127 }
128
129 if (!root)
130 root = agfstnode(g);
131 GV_DEBUG("root = %s", agnameof(root));
132 estack_t stk = {0};
133 dfs(g, root, state, true, &stk);
134 LIST_FREE(&stk);
135}
136
137/* Construct block tree by peeling nodes from block list in state.
138 * When done, return root. The block list is empty
139 * FIX: use largest block as root
140 */
142{
143 block_t *next;
144
145 find_blocks(g, state);
146
147 block_t *bp = state->bl.first; // if root chosen, will be first
148 /* Otherwise, just pick first as root */
149 block_t *root = bp;
150
151 /* Find node with minimum VAL value to find parent block */
152 /* FIX: Should be some way to avoid search below. */
153 for (bp = bp->next; bp; bp = next) {
154 Agnode_t *n;
156 Agnode_t *child;
157 Agraph_t *subg = bp->sub_graph;
158
159 child = n = agfstnode(subg);
160
161 int min = VAL(n);
162 parent = PARENT(n);
163 for (n = agnxtnode(subg, n); n; n = agnxtnode(subg, n)) {
164 if (VAL(n) < min) {
165 child = n;
166 min = VAL(n);
167 parent = PARENT(n);
168 }
169 }
171 CHILD(bp) = child;
172 next = bp->next; /* save next since list insertion destroys it */
173 appendBlock(&BLOCK(parent)->children, bp);
174 }
175 initBlocklist(&state->bl); /* zero out list */
176 return root;
177}
178
180{
181 for (block_t *child = bp->children.first, *next; child; child = next) {
182 next = child->next;
183 freeBlocktree(child);
184 }
185
186 freeBlock(bp);
187}
188
189#ifdef DEBUG
190static void indent(int i)
191{
192 while (i--)
193 fputs(" ", stderr);
194}
195
196void print_blocktree(block_t * sn, int depth)
197{
198 indent(depth);
199 Agraph_t *g = sn->sub_graph;
200 fprintf(stderr, "%s:", agnameof(g));
201 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
202 fprintf(stderr, " %s", agnameof(n));
203 }
204 fputs("\n", stderr);
205
206 depth++;
207 for (block_t *child = sn->children.first; child; child = child->next) {
208 print_blocktree(child, depth);
209 }
210}
211
212#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
static void dfs(Agraph_t *g, Agnode_t *u, bcstate *stp, Agnode_t *parent)
Definition bcomps.c:153
static Agraph_t * mkBlock(Agraph_t *g, bcstate *stp)
Definition bcomps.c:138
void insertBlock(blocklist_t *bl, block_t *bp)
add block at beginning
Definition block.c:59
int blockSize(block_t *sp)
Definition block.c:40
void freeBlock(block_t *sp)
Definition block.c:32
void initBlocklist(blocklist_t *bl)
Definition block.c:18
void appendBlock(blocklist_t *bl, block_t *bp)
add block at end
Definition block.c:46
static void find_blocks(Agraph_t *g, circ_state *state)
Definition blocktree.c:111
static block_t * makeBlock(Agraph_t *g, circ_state *state)
Definition blocktree.c:35
block_t * createBlocktree(Agraph_t *g, circ_state *state)
Definition blocktree.c:141
static Agraph_t * makeBlockGraph(Agraph_t *g, circ_state *state)
Definition blocktree.c:24
void freeBlocktree(block_t *bp)
Definition blocktree.c:179
static void addNode(block_t *bp, Agnode_t *n)
Definition blocktree.c:18
#define CHILD(b)
Definition block.h:50
#define BLOCK(n)
Definition circular.h:85
#define LOWVAL(n)
Definition circular.h:88
#define EDGEORDER(e)
Definition circular.h:78
#define SET_PARENT(n)
Definition circular.h:112
#define ORIGN(n)
Definition circular.h:82
#define PARENT(n)
Definition circular.h:84
#define VAL(n)
Definition circular.h:87
#define parent(i)
Definition closest.c:81
bool late_bool(void *obj, attrsym_t *attr, bool defaultValue)
Definition utils.c:94
helpers for verbose/debug printing
#define GV_DEBUG(...)
Definition debug.h:39
node NULL
Definition grammar.y:181
#define agtail(e)
Definition cgraph.h:988
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 * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
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 agfindnode(g, n)
Definition types.h:611
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
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
static void indent(int ix)
Definition gv2gml.c:94
Arithmetic helper functions.
static int imin(int a, int b)
minimum of two integers
Definition gv_math.h:29
type-generic dynamically expanding list
#define LIST(type)
Definition list.h:55
#define LIST_FREE(list)
Definition list.h:379
#define LIST_POP_BACK(list)
Definition list.h:416
#define LIST_PUSH_BACK(list, item)
Definition list.h:393
graph or subgraph
Definition cgraph.h:424
Definition block.h:26
blocklist_t children
Definition block.h:33
Agraph_t * sub_graph
Definition block.h:29
block_t * next
Definition block.h:28
block_t * first
Definition block.h:22
int orderCount
Definition circular.h:18
char * rootname
Definition circular.h:23
int blockCount
Definition circular.h:19
attrsym_t * N_root
Definition circular.h:22
blocklist_t bl
Definition circular.h:17