#pragma prototyped
#include "blockpath.h"
#include "edgelist.h"
#include "nodeset.h"
#include "deglist.h"
#define ORIGE(e) (ED_to_orig(e))
static Agraph_t*
clone_graph(Agraph_t* ing, Agraph_t** xg)
{
Agraph_t* clone;
Agraph_t* xclone;
Agnode_t* n;
Agnode_t* xn;
Agnode_t* xh;
Agedge_t* e;
Agedge_t* xe;
char gname[SMALLBUF];
static int id = 0;
sprintf (gname, "_clone_%d", id++);
clone = agsubg(ing, gname);
sprintf (gname, "_clone_%d", id++);
xclone = agopen(gname, ing->kind);
for(n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
aginsert (clone, n);
xn = agnode (xclone, n->name);
CLONE(n) = xn;
}
for(n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
xn = CLONE(n);
for(e = agfstout(ing, n); e; e = agnxtout(ing, e)) {
aginsert (clone, e);
xh = CLONE(e->head);
xe = agedge (xclone, xn, xh);
ORIGE(xe) = e;
DEGREE(xn) += 1;
DEGREE(xh) += 1;
}
}
*xg = xclone;
#ifdef OLD
clone = agopen("clone", root->kind);
for(n = agfstnode(root); n; n = agnxtnode(root, n)) {
cn = agnode(clone, n->name);
ND_alg(cn) = DATA(n);
BCDONE(cn) = 0;
}
for(n = agfstnode(root); n; n = agnxtnode(root, n)) {
Agnode_t *t = agnode(clone, n);
for(e = agfstout(root, n); e; e = agnxtout(root, e)) {
Agnode_t *h = agnode(clone, e->head->name);
agedge(clone, t, h);
}
}
#endif
return clone;
}
static deglist_t*
getList(Agraph_t* g)
{
deglist_t* dl = mkDeglist();
Agnode_t* n;
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
insertDeglist (dl, n);
}
return dl;
}
static void
find_pair_edges(Agraph_t* g, Agnode_t* n, Agraph_t* outg)
{
Agnode_t** neighbors_with;
Agnode_t** neighbors_without;
Agedge_t* e;
Agedge_t* ep;
Agedge_t* ex;
Agnode_t* n1;
Agnode_t* n2;
int has_pair_edge;
int diff;
int has_pair_count = 0;
int no_pair_count = 0;
int node_degree;
int edge_cnt = 0;
node_degree = DEGREE(n);
neighbors_with= N_GNEW(node_degree, Agnode_t*);
neighbors_without= N_GNEW(node_degree, Agnode_t*);
for (e = agfstedge (g, n); e; e = agnxtedge(g,e,n)) {
n1 = e->head;
if (n1 == n) n1 = e->tail;
has_pair_edge = 0;
for (ep = agfstedge(g,n); ep; ep = agnxtedge(g,ep,n)) {
if (ep == e) continue;
n2 = ep->head;
if (n2 == n) n2 = ep->tail;
ex = agfindedge(g, n1, n2);
if (ex) {
has_pair_edge = 1;
if (n1 < n2) {
edge_cnt++;
if (ORIGE(ex)) {
agdelete (outg, ORIGE(ex));
ORIGE(ex) = 0;
}
}
}
}
if(has_pair_edge) {
neighbors_with[has_pair_count] = n1;
has_pair_count++;
}
else {
neighbors_without[no_pair_count] = n1;
no_pair_count++;
}
}
diff = node_degree - 1 - edge_cnt;
if (diff > 0) {
int mark;
Agnode_t* hp;
Agnode_t* tp;
if(diff < no_pair_count) {
for(mark = 0; mark < no_pair_count; mark += 2) {
if((mark + 1) >= no_pair_count) break;
tp = neighbors_without[mark];
hp = neighbors_without[mark+1];
agedge(g, tp, hp);
DEGREE(tp)++;
DEGREE(hp)++;
diff--;
}
mark = 2;
while(diff > 0) {
tp = neighbors_without[0];
hp = neighbors_without[mark];
agedge(g, tp, hp);
DEGREE(tp)++;
DEGREE(hp)++;
mark++;
diff--;
}
}
else if(diff == no_pair_count) {
tp = neighbors_with[0];
for(mark = 0; mark < no_pair_count; mark++) {
hp = neighbors_without[mark];
agedge(g, tp, hp);
DEGREE(tp)++;
DEGREE(hp)++;
}
}
}
free(neighbors_without);
free(neighbors_with);
}
static Agraph_t*
remove_pair_edges(Agraph_t* ing)
{
int counter = 0;
int nodeCount;
Agraph_t* outg;
Agraph_t* g;
deglist_t* dl;
Agnode_t *currnode, *adjNode;
Agedge_t *e;
outg = clone_graph(ing, &g);
nodeCount = agnnodes(g);
dl = getList (g);
while(counter < (nodeCount - 3)) {
currnode = firstDeglist(dl);
for(e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
adjNode = e->head;
if(currnode == adjNode) adjNode = e->tail;
removeDeglist(dl, adjNode);
}
find_pair_edges(g, currnode, outg);
for(e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
adjNode = e->head;
if(currnode == adjNode) adjNode = e->tail;
DEGREE(adjNode)--;
insertDeglist(dl, adjNode);
}
agdelete(g, currnode);
counter++;
}
agclose(g);
freeDeglist(dl);
return outg;
}
static void
measure_distance(Agnode_t* n, Agnode_t* ancestor, int dist, Agnode_t* change)
{
Agnode_t* parent;
parent = TPARENT(ancestor);
if(parent == NULL) return;
dist++;
if(DISTONE(parent) == 0) {
LEAFONE(parent) = n;
DISTONE(parent) = dist;
}
else if(dist > DISTONE(parent)) {
if(LEAFONE(parent) != change) {
if (!DISTTWO(parent) || (LEAFTWO(parent) != change))
change = LEAFONE(parent);
LEAFTWO(parent) = LEAFONE(parent);
DISTTWO(parent) = DISTONE(parent);
}
LEAFONE(parent) = n;
DISTONE(parent) = dist;
}
else if (dist > DISTTWO(parent)) {
LEAFTWO(parent) = n;
DISTTWO(parent) = dist;
return;
}
else return;
measure_distance(n, parent, dist, change);
}
static nodelist_t*
find_longest_path(Agraph_t* tree)
{
Agnode_t* n;
Agedge_t* e;
Agnode_t* common = 0;
nodelist_t* path;
nodelist_t* endPath;
int maxlength = 0;
int length;
if (agnnodes(tree) == 1) {
path = mkNodelist();
n = agfstnode(tree);
appendNodelist(path, NULL, n);
SET_ONPATH(n);
return path;
}
for(n = agfstnode(tree); n; n = agnxtnode(tree, n)) {
int count = 0;
for(e = agfstedge(tree, n); e; e = agnxtedge(tree, e, n)) {
count++;
}
if(count == 1)
measure_distance(n, n, 0, NULL);
}
for(n = agfstnode(tree); n; n = agnxtnode(tree, n)) {
length = DISTONE(n) + DISTTWO(n);
if(length > maxlength) {
common = n;
maxlength = length;
}
}
path = mkNodelist();
for (n = LEAFONE(common); n != common; n = TPARENT(n)) {
appendNodelist(path, NULL, n);
SET_ONPATH(n);
}
appendNodelist(path, NULL, common);
SET_ONPATH(common);
if (DISTTWO(common)) {
endPath = mkNodelist();
for (n = LEAFTWO(common); n != common; n = TPARENT(n)) {
appendNodelist(endPath, NULL, n);
SET_ONPATH(n);
}
reverseAppend(path, endPath);
}
return path;
}
static void
dfs (Agraph_t* g, Agnode_t* n, Agraph_t* tree)
{
Agedge_t* e;
Agnode_t *neighbor;
SET_VISITED(n);
for(e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
neighbor = e->head;
if(neighbor == n) neighbor = e->tail;
if(!VISITED(neighbor)) {
aginsert(tree, e);
TPARENT(neighbor) = n;
dfs(g, neighbor, tree);
}
}
}
static Agraph_t*
spanning_tree(Agraph_t* g)
{
Agnode_t* n;
Agraph_t* tree;
char gname[SMALLBUF];
static int id = 0;
sprintf (gname, "_span_%d", id++);
tree = agsubg(g, gname);
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
aginsert(tree, n);
DISTONE(n) = 0;
DISTTWO(n) = 0;
UNSET_VISITED(n);
}
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
if(!VISITED(n)) {
TPARENT(n) = NULL;
dfs(g, n, tree);
}
}
return tree;
}
static void
block_graph(Agraph_t* g, block_t* sn)
{
Agnode_t* n;
Agedge_t* e;
Agraph_t* subg = sn->sub_graph;
for(n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
for(e = agfstout(g, n); e; e = agnxtout(g, e)) {
if (BLOCK(e->head) == sn)
aginsert (subg, e);
}
}
}
static int
count_all_crossings(nodelist_t* list, Agraph_t* subg)
{
nodelistitem_t* item;
edgelist* openEdgeList = init_edgelist();
Agnode_t* n;
Agedge_t* e;
int crossings = 0;
int order = 1;
for(n = agfstnode(subg); n; n= agnxtnode(subg, n)) {
for(e = agfstout(subg, n); e; e = agnxtout(subg, e)) {
EDGEORDER(e) = 0;
}
}
for (item = list->first; item; item = item->next) {
n = item->curr;
for(e = agfstedge(subg, n); e; e = agnxtedge(subg, e, n)) {
if(EDGEORDER(e) > 0) {
edgelistitem* eitem;
Agedge_t* ep;
for (eitem = (edgelistitem*)dtfirst(openEdgeList); eitem;
eitem = (edgelistitem*)dtnext(openEdgeList,eitem)) {
ep = eitem->edge;
if(EDGEORDER(ep) > EDGEORDER(e)) {
if((ep->head != n) && (ep->tail != n))
crossings++;
}
}
remove_edge(openEdgeList, e);
}
}
for(e = agfstedge(subg, n); e; e = agnxtedge(subg, e, n)) {
if(EDGEORDER(e) == 0) {
EDGEORDER(e) = order;
add_edge(openEdgeList, e);
}
}
order++;
}
free_edgelist(openEdgeList);
return crossings;
}
#define CROSS_ITER 10
static nodelist_t*
reduce(nodelist_t* list, Agraph_t* subg, int* cnt)
{
Agnode_t* curnode;
Agedge_t* e;
Agnode_t* neighbor;
nodelist_t* listCopy;
int crossings, j, newCrossings;
crossings = *cnt;
for(curnode = agfstnode(subg); curnode; curnode = agnxtnode(subg, curnode)) {
for(e = agfstedge(subg, curnode); e; e = agnxtedge(subg, e, curnode)) {
neighbor = e->tail;
if(neighbor == curnode)
neighbor = e->head;
for(j = 0; j < 2; j++) {
listCopy = cloneNodelist(list);
insertNodelist(list, curnode, neighbor, j);
newCrossings = count_all_crossings(list, subg);
if(newCrossings < crossings) {
crossings = newCrossings;
freeNodelist(listCopy);
if(crossings == 0) {
*cnt = 0;
return list;
}
}
else {
freeNodelist(list);
list = listCopy;
}
}
}
}
*cnt = crossings;
return list;
}
static nodelist_t*
reduce_edge_crossings(nodelist_t* list, Agraph_t* subg)
{
int i, crossings, origCrossings;
crossings = count_all_crossings(list, subg);
if(crossings == 0) return list;
for(i = 0; i < CROSS_ITER; i++) {
origCrossings = crossings;
list = reduce (list, subg, &crossings);
if ((origCrossings == crossings) || (crossings == 0))
return list;
}
return list;
}
static double
largest_nodesize(nodelist_t* list)
{
Agnode_t* n;
nodelistitem_t* item;
double size = 0;
for (item = list->first; item; item = item->next) {
n = ORIGN(item->curr);
if(ND_width(n) > size)
size = ND_width(n);
if(ND_height(n) > size)
size = ND_height(n);
}
return size;
}
static void
place_node(Agraph_t* g, Agnode_t* n, nodelist_t* list)
{
Agedge_t* e;
int placed = 0;
nodelist_t* neighbors = mkNodelist();
nodelistitem_t *one, *two;
for(e = agfstout(g, n); e; e = agnxtout(g, e)) {
appendNodelist(neighbors, NULL, e->head);
SET_NEIGHBOR(e->head);
}
for(e = agfstin(g, n); e; e = agnxtin(g, e)) {
appendNodelist(neighbors, NULL, e->tail);
SET_NEIGHBOR(e->tail);
}
if(sizeNodelist(neighbors) >= 2) {
for (one = list->first; one; one = one->next) {
if(one == list->last)
two = list->first;
else
two = one->next;
if(NEIGHBOR(one->curr) && NEIGHBOR(two->curr)) {
appendNodelist (list, one, n);
placed = 1;
break;
}
}
}
if(!placed && sizeNodelist(neighbors) > 0) {
for (one = list->first; one; one = one->next) {
if(NEIGHBOR(one->curr)) {
appendNodelist (list, one, n);
placed = 1;
break;
}
}
}
if (!placed) appendNodelist(list, NULL, n);
for (one = neighbors->first; one; one = one->next)
UNSET_NEIGHBOR(one->curr);
freeNodelist(neighbors);
}
static void
place_residual_nodes(Agraph_t* g, nodelist_t* list)
{
Agnode_t* n;
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
if(!ONPATH(n))
place_node(g, n, list);
}
}
nodelist_t*
layout_block(Agraph_t* g, block_t* sn, double min_dist)
{
Agnode_t* n;
Agraph_t *copyG, *tree, *subg;
nodelist_t* longest_path;
nodelistitem_t* item;
int N, k;
double theta, radius, largest_node;
largest_node = 0;
subg = sn->sub_graph;
block_graph(g, sn);
copyG = remove_pair_edges(subg);
tree = spanning_tree(copyG);
longest_path = find_longest_path(tree);
place_residual_nodes(subg, longest_path);
longest_path = reduce_edge_crossings(longest_path, subg);
N = sizeNodelist(longest_path);
largest_node = largest_nodesize(longest_path);
if(N == 1) radius = 0;
else radius = (N * (min_dist + largest_node))/(2 * PI);
for (item = longest_path->first; item; item = item->next) {
n = item->curr;
if(ISPARENT(n)) {
realignNodelist(longest_path, item);
break;
}
}
k = 0;
for (item = longest_path->first; item; item = item->next) {
n = item->curr;
POSITION(n) = k;
PSI(n) = 0.0;
theta = k * ((2.0 * PI)/N);
ND_pos(n)[0] = radius * cos(theta);
ND_pos(n)[1] = radius * sin(theta);
k++;
}
if(N == 1)
sn->radius = largest_node/2;
else
sn->radius = radius;
sn->rad0 = sn->radius;
sn->parent_pos = -1;
agclose(copyG);
return longest_path;
}
#ifdef DEBUG
void
prTree (Agraph_t* g)
{
Agnode_t* n;
for(n = agfstnode(g); n; n = agnxtnode(g, n)) {
if (TPARENT(n))
fprintf (stderr, "%s -> %s\n", n->name, TPARENT(n)->name);
}
}
#endif