blockpath.c

Go to the documentation of this file.

/* $Id$ $Revision$ */
/* vim:set shiftwidth=4 ts=8: */

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: See CVS logs. Details at http://www.graphviz.org/
 *************************************************************************/


#include        "blockpath.h"
#include        "edgelist.h"
#include        "nodeset.h"
#include        "deglist.h"

/* The code below lays out a single block on a circle.
 */

/* We use the unused fields order and to_orig in cloned nodes and edges */
#define ORIGE(e)  (ED_to_orig(e))

/* clone_graph:
 * Create two copies of the argument graph
 * One is a subgraph, the other is an actual copy since we will be
 * adding edges to it.
 */
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,1);
    agbindrec(clone, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);       //node custom data
    sprintf(gname, "_clone_%d", id++);
    xclone = agopen(gname, ing->desc,NIL(Agdisc_t *));
    for (n = agfstnode(ing); n; n = agnxtnode(ing, n)) {
        agsubnode(clone,n,1);
        xn = agnode(xclone, agnameof(n),1);
        agbindrec(xn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);      //node custom data
        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)) {
            agsubedge(clone,e,1);
            xh = CLONE(aghead(e));
            xe = agedge(xclone, xn, xh, NULL, 1);
            agbindrec(xe, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);  //node custom data
            ORIGE(xe) = e;
            DEGREE(xn) += 1;
            DEGREE(xh) += 1;
        }
    }
    *xg = xclone;
    return clone;
}

/* fillList:
 * Add nodes to deg_list, which stores them by degree.
 */
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;
}

/* find_pair_edges:
 */
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 = aghead(e);
        if (n1 == n)
            n1 = agtail(e);
        has_pair_edge = 0;
        for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
            if (ep == e)
                continue;
            n2 = aghead(ep);
            if (n2 == n)
                n2 = agtail(ep);
            ex = agfindedge(g, n1, n2);
            if (ex) {
                has_pair_edge = 1;
                if (n1 < n2) {  /* count edge only once */
                    edge_cnt++;
                    if (ORIGE(ex)) {
                        agdelete(outg, ORIGE(ex));
                        ORIGE(ex) = 0;  /* delete only once */
                    }
                }
            }
        }
        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];
                agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);   // edge custom data
                DEGREE(tp)++;
                DEGREE(hp)++;
                diff--;
            }

            mark = 2;
            while (diff > 0) {
                tp = neighbors_without[0];
                hp = neighbors_without[mark];
                agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);   // edge custom data
                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];
                agbindrec(agedge(g, tp, hp, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);      //node custom data
                DEGREE(tp)++;
                DEGREE(hp)++;
            }
        }
    }

    free(neighbors_without);
    free(neighbors_with);
}

/* remove_pair_edges:
 * Create layout skeleton of ing.
 * Why is returned graph connected?
 */
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);

        /* Remove all adjacent nodes since they have to be reinserted */
        for (e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
            adjNode = aghead(e);
            if (currnode == adjNode)
                adjNode = agtail(e);
            removeDeglist(dl, adjNode);
        }

        find_pair_edges(g, currnode, outg);

        for (e = agfstedge(g, currnode); e; e = agnxtedge(g, e, currnode)) {
            adjNode = aghead(e);
            if (currnode == adjNode)
                adjNode = agtail(e);

            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++;

    /* check parent to see if it has other leaf paths at greater distance
       than the context node.
       set the path/distance of the leaf at this ancestor node */

    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);
}

/* find_longest_path:
 * Find and return longest path in tree.
 */
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);
    }

    /* find the branch node rooted at the longest path */
    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)) {      /* 2nd path might be empty */
        endPath = mkNodelist();
        for (n = LEAFTWO(common); n != common; n = TPARENT(n)) {
            appendNodelist(endPath, NULL, n);
            SET_ONPATH(n);
        }
        reverseAppend(path, endPath);
    }

    return path;
}

/* dfs:
 * Simple depth first search, adding traversed edges to tree.
 */
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 = aghead(e);
        if (neighbor == n)
            neighbor = agtail(e);

        if (!VISITED(neighbor)) {
            /* add the edge to the dfs tree */
            agsubedge(tree,e,1);
            TPARENT(neighbor) = n;
            dfs(g, neighbor, tree);
        }
    }
}

/* spanning_tree:
 * Construct spanning forest of g as subgraph
 */
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,1);
    agbindrec(tree, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);        //node custom data

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        agsubnode(tree,n,1);
        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;
}

/* block_graph:
 * Add induced edges.
 */
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(aghead(e)) == sn)
                agsubedge(subg,e,1);
        }
    }
}

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 ((aghead(ep) != n) && (agtail(ep) != 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

/* reduce:
 * Attempt to reduce edge crossings by moving nodes.
 * Original crossing count is in cnt; final count is returned there.
 * list is the original list; return the best list found.
 */
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)) {
        /*  move curnode next to its neighbors */
        for (e = agfstedge(subg, curnode); e;
             e = agnxtedge(subg, e, curnode)) {
            neighbor = agtail(e);
            if (neighbor == curnode)
                neighbor = aghead(e);

            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);
        /* return if no crossings or no improvement */
        if ((origCrossings == crossings) || (crossings == 0))
            return list;
    }
    return list;
}

/* largest_nodesize:
 * Return max dimension of nodes on 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;
}

/* place_node:
 * Add n to list. By construction, n is not in list at start.
 */
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, aghead(e));
        SET_NEIGHBOR(aghead(e));
    }
    for (e = agfstin(g, n); e; e = agnxtin(g, e)) {
        appendNodelist(neighbors, NULL, agtail(e));
        SET_NEIGHBOR(agtail(e));
    }

    /* Look for 2 neighbors consecutive on list */
    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;
            }
        }
    }

    /* Find any neighbor on list */
    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);
}

/* place_residual_nodes:
 * Add nodes not in list to list.
 */
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);         /* add induced edges */

    copyG = remove_pair_edges(subg);

    tree = spanning_tree(copyG);
    longest_path = find_longest_path(tree);
    place_residual_nodes(subg, longest_path);
    /* at this point, longest_path is a list of all nodes in the block */

    /* apply crossing reduction algorithms here */
    longest_path = reduce_edge_crossings(longest_path, subg);

    N = sizeNodelist(longest_path);
    largest_node = largest_nodesize(longest_path);
    /* N*(min_dist+largest_node) is roughly circumference of required circle */
    if (N == 1)
        radius = 0;
    else
        radius = (N * (min_dist + largest_node)) / (2 * M_PI);

    for (item = longest_path->first; item; item = item->next) {
        n = item->curr;
        if (ISPARENT(n)) {
            /* QUESTION: Why is only one parent realigned? */
            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 * M_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;

    /* initialize parent pos */
    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 ", agnameof(n));
                        fprintf(stderr, "-> %s\n", agnameof(TPARENT(n)));
                }
    }
}
#endif