#pragma prototyped
#include <blocktree.h>
static int
min_value(int x, int y)
{
if(x < y)
return x;
return y;
}
static void
addNode (block_t* bp, Agnode_t* n)
{
aginsert(bp->sub_graph, n);
SET_BCDONE(n);
BLOCK(n) = bp;
}
static Agraph_t*
makeBlockGraph (Agraph_t* g, circ_state* state)
{
char name[SMALLBUF];
Agraph_t* subg;
sprintf (name, "_block_%d", state->blockCount++);
subg = agsubg(g, name);
return subg;
}
static block_t*
makeBlock (Agraph_t* g, circ_state* state)
{
Agraph_t* subg = makeBlockGraph (g, state);
block_t* bp = mkBlock (subg);
return bp;
}
static void
dfs(Agraph_t* g, Agnode_t* n, circ_state* state, int isRoot)
{
Agedge_t* e;
Agnode_t* curtop;
LOWVAL(n) = VAL(n) = state->orderCount++;
stackPush(state->bcstack, n);
for(e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
Agnode_t* neighbor = e->head;
if(neighbor == n) neighbor = e->tail;
if(neighbor == PARENT(n)) continue;
if(VAL(neighbor)) {
LOWVAL(n) = min_value(LOWVAL(n), VAL(neighbor));
continue;
}
if(!stackCheck(state->bcstack, n)) {
stackPush(state->bcstack, n);
}
PARENT(neighbor) = n;
curtop = top (state->bcstack);
dfs(g, neighbor, state, 0);
LOWVAL(n) = min_value(LOWVAL(n), LOWVAL(neighbor));
if(LOWVAL(neighbor) >= VAL(n)) {
block_t* block = NULL;
Agnode_t* np;
if (top(state->bcstack) != curtop) do {
np = stackPop(state->bcstack);
if(!BCDONE(np)) {
if (!block) block = makeBlock (g, state);
addNode (block, np);
}
} while (np != n);
if (block) {
if (isRoot && (BLOCK(n) == block))
insertBlock(&state->bl, block);
else
appendBlock(&state->bl, block);
}
if ((LOWVAL(n) < VAL(n)) && (!stackCheck(state->bcstack, n))) {
stackPush(state->bcstack, n);
}
}
}
if((LOWVAL(n) == VAL(n)) && !BCDONE(n)) {
block_t* block = makeBlock (g, state);
stackPop(state->bcstack);
addNode(block, n);
if (isRoot)
insertBlock(&state->bl, block);
else
appendBlock(&state->bl, block);
}
}
#ifdef USER_BLOCKS
static Agnode_t*
findUnvisited (blocklist_t* blp)
{
Agnode_t* retn = NULL;
FIX : finish
Agnode_t* n;
Agnode_t* newn;
graph_t* clust_subg;
edge_t* e;
block_t* bp;
block_t* prev = NULL;
for (bp = blp->first; prev != blp->last; bp = bp->next)) {
prev = bp;
clust = bp->sub_graph;
if (DONE(bp)) continue;
if (PARTIAL(bp)) {
for(n = agfstnode(clust); n; n = agnxtnode(clust, n)) {
if (!VISITED(n)) {
for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
newn = e->head;
if (newn == n) newn = e->tail;
if ((BLOCK(newn) != bp)) {
retn = newn;
return;
}
}
}
}
}
else {
}
}
return retn;
}
#endif
static void
find_blocks(Agraph_t* g, circ_state* state)
{
Agnode_t* n;
Agnode_t* root = NULL;
block_t* rootBlock = NULL;
blocklist_t ublks;
#ifdef USER_BLOCKS
graph_t* clust_subg;
graph_t* mg;
edge_t* me;
node_t* mm;
int isRoot;
#endif
initBlocklist (&ublks);
if (state->rootname) {
root = agfindnode (g, state->rootname);
}
if (!root || state->N_root) {
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
if (late_bool (ORIGN(n), state->N_root, 0)) {
root = n;
break;
}
}
}
#ifdef USER_BLOCKS
mm = g->meta_node;
mg = mm->graph;
for (me = agfstout(mg, mm); me; me = agnxtout(mg, me)) {
block_t* block;
clust_subg = agusergraph(me->head);
isRoot = 0;
block = mkBlock (clust_subg);
for(n = agfstnode(clust_subg); n; n = agnxtnode(clust_subg, n)) {
if(!BCDONE(n)) {
SET_BCDONE(n);
BLOCK(n) = block;
if (n == root) isRoot = 1;
}
}
if (isRoot) {
rootBlock = block;
insertBlock (&state->bl, block);
}
else {
appendBlock (&state->bl, block);
}
}
ublks.first = state->bl.first;
ublks.last = state->bl.last;
#endif
if (!root) root = agfstnode(g);
dfs(g, root, state, !rootBlock);
#ifdef USER_BLOCKS
if (ublks.first) {
while (n = findUnvisited(&ublks)) {
dfs(g, n, state, 0);
}
}
#endif
}
block_t*
createBlocktree(Agraph_t* g, circ_state* state)
{
block_t* bp;
block_t* next;
block_t* root;
int min;
find_blocks(g, state);
bp = state->bl.first;
root = bp;
for (bp = bp->next; bp; bp = next) {
Agnode_t* n;
Agnode_t* parent;
Agnode_t* child;
Agraph_t* subg = bp->sub_graph;
child = n = agfstnode(subg);
min = VAL(n);
parent = PARENT(n);
for(n = agnxtnode(subg, n); n; n = agnxtnode(subg, n)) {
if(VAL(n) < min) {
child = n;
min = VAL(n);
parent = PARENT(n);
}
}
SET_PARENT(parent);
CHILD(bp) = child;
next = bp->next;
appendBlock(&(BLOCK(parent)->children), bp);
}
initBlocklist(&state->bl);
return root;
}
void
freeBlocktree(block_t* bp)
{
block_t* child;
block_t* next;
for (child = bp->children.first; child; child=next) {
next = child->next;
freeBlocktree (child);
}
freeBlock (bp);
}
#ifdef DEBUG
static void
indent (int i)
{
while (i--)
fputs(" ",stderr);
}
void
print_blocktree(block_t* sn, int depth)
{
block_t* child;
Agnode_t* n;
Agraph_t* g;
indent (depth);
g = sn->sub_graph;
fprintf (stderr, "%s:", g->name);
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
fprintf(stderr," %s", n->name);
}
fputs("\n",stderr);
depth++;
for(child = sn->children.first; child; child = child->next) {
print_blocktree(child, depth);
}
}
#endif