rank.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/
 *************************************************************************/


/*
 * Rank the nodes of a directed graph, subject to user-defined
 * sets of nodes to be kept on the same, min, or max rank.
 * The temporary acyclic fast graph is constructed and ranked
 * by a network-simplex technique.  Then ranks are propagated
 * to non-leader nodes and temporary edges are deleted.
 * Leaf nodes and top-level clusters are left collapsed, though.
 * Assigns global minrank and maxrank of graph and all clusters.
 *
 * TODO: safety code.  must not be in two clusters at same level.
 *  must not be in same/min/max/rank and a cluster at the same time.
 *  watch out for interactions between leaves and clusters.
 */

#include        "dot.h"

static void dot1_rank(graph_t * g, aspect_t* asp);
static void dot2_rank(graph_t * g, aspect_t* asp);

static void 
renewlist(elist * L)
{
    int i;
    for (i = L->size; i >= 0; i--)
        L->list[i] = NULL;
    L->size = 0;
}

static void 
cleanup1(graph_t * g)
{
    node_t *n;
    edge_t *e, *f;
    int c;

    for (c = 0; c < GD_comp(g).size; c++) {
        GD_nlist(g) = GD_comp(g).list[c];
        for (n = GD_nlist(g); n; n = ND_next(n)) {
            renewlist(&ND_in(n));
            renewlist(&ND_out(n));
            ND_mark(n) = FALSE;
        }
    }
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
            f = ED_to_virt(e);
            /* Null out any other references to f to make sure we don't 
             * handle it a second time. For example, parallel multiedges 
             * share a virtual edge.
             */
            if (f && (e == ED_to_orig(f))) {
                edge_t *e1, *f1;
                node_t *n1;
                for (n1 = agfstnode(g); n1; n1 = agnxtnode(g, n1)) {
                    for (e1 = agfstout(g, n1); e1; e1 = agnxtout(g, e1)) {
                        if (e != e1) {
                            f1 = ED_to_virt(e1);
                            if (f1 && (f == f1)) {
                                ED_to_virt(e1) = NULL;
                            }
                        }
                    }
                }
                free(f->base.data);
                free(f);
            }
            ED_to_virt(e) = NULL;
        }
    }
    free(GD_comp(g).list);
    GD_comp(g).list = NULL;
    GD_comp(g).size = 0;
}

/* When there are edge labels, extra ranks are reserved here for the virtual
 * nodes of the labels.  This is done by doubling the input edge lengths.
 * The input rank separation is adjusted to compensate.
 */
static void 
edgelabel_ranks(graph_t * g)
{
    node_t *n;
    edge_t *e;

    if (GD_has_labels(g->root) & EDGE_LABEL) {
        for (n = agfstnode(g); n; n = agnxtnode(g, n))
            for (e = agfstout(g, n); e; e = agnxtout(g, e))
                ED_minlen(e) *= 2;
        GD_ranksep(g) = (GD_ranksep(g) + 1) / 2;
    }
}

/* Merge the nodes of a min, max, or same rank set. */
static void 
collapse_rankset(graph_t * g, graph_t * subg, int kind)
{
    node_t *u, *v;

    u = v = agfstnode(subg);
    if (u) {
        ND_ranktype(u) = kind;
        while ((v = agnxtnode(subg, v))) {
            UF_union(u, v);
            ND_ranktype(v) = ND_ranktype(u);
        }
        switch (kind) {
        case MINRANK:
        case SOURCERANK:
            if (GD_minset(g) == NULL)
                GD_minset(g) = u;
            else
                GD_minset(g) = UF_union(GD_minset(g), u);
            break;
        case MAXRANK:
        case SINKRANK:
            if (GD_maxset(g) == NULL)
                GD_maxset(g) = u;
            else
                GD_maxset(g) = UF_union(GD_maxset(g), u);
            break;
        }
        switch (kind) {
        case SOURCERANK:
            ND_ranktype(GD_minset(g)) = kind;
            break;
        case SINKRANK:
            ND_ranktype(GD_maxset(g)) = kind;
            break;
        }
    }
}

static int 
rank_set_class(graph_t * g)
{
    static char *name[] = { "same", "min", "source", "max", "sink", NULL };
    static int class[] =
        { SAMERANK, MINRANK, SOURCERANK, MAXRANK, SINKRANK, 0 };
    int val;

    if (is_cluster(g))
        return CLUSTER;
    val = maptoken(agget(g, "rank"), name, class);
    GD_set_type(g) = val;
    return val;
}

static int 
make_new_cluster(graph_t * g, graph_t * subg)
{
    int cno;
    cno = ++(GD_n_cluster(g));
    GD_clust(g) = ZALLOC(cno + 1, GD_clust(g), graph_t *, GD_n_cluster(g));
    GD_clust(g)[cno] = subg;
    do_graph_label(subg);
    return cno;
}

static void 
node_induce(graph_t * par, graph_t * g)
{
    node_t *n, *nn;
    edge_t *e;
    int i;

    /* enforce that a node is in at most one cluster at this level */
    for (n = agfstnode(g); n; n = nn) {
        nn = agnxtnode(g, n);
        if (ND_ranktype(n)) {
            agdelete(g, n);
            continue;
        }
        for (i = 1; i < GD_n_cluster(par); i++)
            if (agcontains(GD_clust(par)[i], n))
                break;
        if (i < GD_n_cluster(par))
            agdelete(g, n);
        ND_clust(n) = NULL;
    }

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        for (e = agfstout(dot_root(g), n); e; e = agnxtout(dot_root(g), e)) {
            if (agcontains(g, aghead(e)))
                agsubedge(g,e,1);
        }
    }
}

void 
dot_scan_ranks(graph_t * g)
{
    node_t *n, *leader = NULL;
    GD_minrank(g) = MAXSHORT;
    GD_maxrank(g) = -1;
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        if (GD_maxrank(g) < ND_rank(n))
            GD_maxrank(g) = ND_rank(n);
        if (GD_minrank(g) > ND_rank(n))
            GD_minrank(g) = ND_rank(n);
        if (leader == NULL)
            leader = n;
        else {
            if (ND_rank(n) < ND_rank(leader))
                leader = n;
        }
    }
    GD_leader(g) = leader;
}

static void
cluster_leader(graph_t * clust)
{
    node_t *leader, *n;
    int maxrank = 0;

    /* find number of ranks and select a leader */
    leader = NULL;
    for (n = GD_nlist(clust); n; n = ND_next(n)) {
        if ((ND_rank(n) == 0) && (ND_node_type(n) == NORMAL))
            leader = n;
        if (maxrank < ND_rank(n))
            maxrank = ND_rank(n);
    }
    assert(leader != NULL);
    GD_leader(clust) = leader;

    for (n = agfstnode(clust); n; n = agnxtnode(clust, n)) {
        assert((ND_UF_size(n) <= 1) || (n == leader));
        UF_union(n, leader);
        ND_ranktype(n) = CLUSTER;
    }
}

/*
 * A cluster is collapsed in three steps.
 * 1) The nodes of the cluster are ranked locally.
 * 2) The cluster is collapsed into one node on the least rank.
 * 3) In class1(), any inter-cluster edges are converted using
 *    the "virtual node + 2 edges" trick.
 */
static void 
collapse_cluster(graph_t * g, graph_t * subg)
{
    if (GD_parent(subg)) {
        return;
    }
    GD_parent(subg) = g;
    node_induce(g, subg);
    if (agfstnode(subg) == NULL)
        return;
    make_new_cluster(g, subg);
    if (CL_type == LOCAL) {
        dot1_rank(subg, 0);
        cluster_leader(subg);
    } else
        dot_scan_ranks(subg);
}

/* Execute union commands for "same rank" subgraphs and clusters. */
static void 
collapse_sets(graph_t *rg, graph_t *g)
{
    int c;
    graph_t  *subg;
#ifdef OBSOLETE
    node_t *n;
#endif

    for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
        c = rank_set_class(subg);
        if (c) {
            if ((c == CLUSTER) && CL_type == LOCAL)
                collapse_cluster(rg, subg);
            else
                collapse_rankset(rg, subg, c);
        }
        else collapse_sets(rg, subg);

#ifdef OBSOLETE
 Collapsing leaves is currently obsolete

        /* mark nodes with ordered edges so their leaves are not collapsed */
        if (agget(subg, "ordering"))
            for (n = agfstnode(subg); n; n = agnxtnode(subg, n))
                ND_order(n) = 1;
#endif
    }
}

static void 
find_clusters(graph_t * g)
{
    graph_t *subg;
    for (subg = agfstsubg(dot_root(g)); subg; subg = agnxtsubg(subg)) {
        if (GD_set_type(subg) == CLUSTER)
            collapse_cluster(g, subg);
    }
}

static void 
set_minmax(graph_t * g)
{
    int c;

    GD_minrank(g) += ND_rank(GD_leader(g));
    GD_maxrank(g) += ND_rank(GD_leader(g));
    for (c = 1; c <= GD_n_cluster(g); c++)
        set_minmax(GD_clust(g)[c]);
}

/* To ensure that min and max rank nodes always have the intended rank
 * assignment, reverse any incompatible edges.
 */
static point 
minmax_edges(graph_t * g)
{
    node_t *n;
    edge_t *e;
    point  slen;

    slen.x = slen.y = 0;
    if ((GD_maxset(g) == NULL) && (GD_minset(g) == NULL))
        return slen;
    if (GD_minset(g) != NULL)
        GD_minset(g) = UF_find(GD_minset(g));
    if (GD_maxset(g) != NULL)
        GD_maxset(g) = UF_find(GD_maxset(g));

    if ((n = GD_maxset(g))) {
        slen.y = (ND_ranktype(GD_maxset(g)) == SINKRANK);
        while ((e = ND_out(n).list[0])) {
            assert(aghead(e) == UF_find(aghead(e)));
            reverse_edge(e);
        }
    }
    if ((n = GD_minset(g))) {
        slen.x = (ND_ranktype(GD_minset(g)) == SOURCERANK);
        while ((e = ND_in(n).list[0])) {
            assert(agtail(e) == UF_find(agtail(e)));
            reverse_edge(e);
        }
    }
    return slen;
}
    
static int 
minmax_edges2(graph_t * g, point slen)
{
    node_t *n;
    edge_t *e = 0;

    if ((GD_maxset(g)) || (GD_minset(g))) {
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
            if (n != UF_find(n))
                continue;
            if ((ND_out(n).size == 0) && GD_maxset(g) && (n != GD_maxset(g))) {
                e = virtual_edge(n, GD_maxset(g), NULL);
                ED_minlen(e) = slen.y;
                ED_weight(e) = 0;
            }
            if ((ND_in(n).size == 0) && GD_minset(g) && (n != GD_minset(g))) {
                e = virtual_edge(GD_minset(g), n, NULL);
                ED_minlen(e) = slen.x;
                ED_weight(e) = 0;
            }
        }
    }
    return (e != 0);
}

/* Run the network simplex algorithm on each component. */
void rank1(graph_t * g)
{
    int maxiter = INT_MAX;
    int c;
    char *s;

    if ((s = agget(g, "nslimit1")))
        maxiter = atof(s) * agnnodes(g);
    for (c = 0; c < GD_comp(g).size; c++) {
        GD_nlist(g) = GD_comp(g).list[c];
        rank(g, (GD_n_cluster(g) == 0 ? 1 : 0), maxiter);       /* TB balance */
    }
}

/* 
 * Assigns ranks of non-leader nodes.
 * Expands same, min, max rank sets.
 * Leaf sets and clusters remain merged.
 * Sets minrank and maxrank appropriately.
 */
static void expand_ranksets(graph_t * g, aspect_t* asp)
{
    int c;
    node_t *n, *leader;

    if ((n = agfstnode(g))) {
        GD_minrank(g) = MAXSHORT;
        GD_maxrank(g) = -1;
        while (n) {
            leader = UF_find(n);
            /* The following works because ND_rank(n) == 0 if n is not in a
             * cluster, and ND_rank(n) = the local rank offset if n is in
             * a cluster. */
            if ((leader != n) && (!asp || (ND_rank(n) == 0)))
                ND_rank(n) += ND_rank(leader);

            if (GD_maxrank(g) < ND_rank(n))
                GD_maxrank(g) = ND_rank(n);
            if (GD_minrank(g) > ND_rank(n))
                GD_minrank(g) = ND_rank(n);

            if (ND_ranktype(n) && (ND_ranktype(n) != LEAFSET))
                UF_singleton(n);
            n = agnxtnode(g, n);
        }
        if (g == dot_root(g)) {
            if (CL_type == LOCAL) {
                for (c = 1; c <= GD_n_cluster(g); c++)
                    set_minmax(GD_clust(g)[c]);
            } else {
                find_clusters(g);
            }
        }
    } else {
        GD_minrank(g) = GD_maxrank(g) = 0;
    }
}

#ifdef ALLOW_LEVELS
void
setRanks (graph_t* g, attrsym_t* lsym)
{
    node_t* n;
    char*   s;
    char*   ep;
    long    v;

    for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
        s = agxget (n, lsym);
        v = strtol (s, &ep, 10);
        if (ep == s)
            agerr(AGWARN, "no level attribute for node \"%s\"\n", agnameof(n));
        ND_rank(n) = v;
    }
}
#endif

#ifdef UNUSED
static node_t **virtualEdgeHeadList = NULL;
static node_t **virtualEdgeTailList = NULL;
static int nVirtualEdges = 0;

static void
saveVirtualEdges(graph_t *g)
{
    edge_t *e;
    node_t *n;
    int cnt = 0;
    int lc;
    
    if (virtualEdgeHeadList != NULL) {
        free(virtualEdgeHeadList);
    }
    if (virtualEdgeTailList != NULL) {
        free(virtualEdgeTailList);
    }

  /* allocate memory */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        for (lc = 0; lc < ND_in(n).size; lc++) {
            e = ND_in(n).list[lc];
            if (ED_edge_type(e) == VIRTUAL) cnt++;
        }
    }

    nVirtualEdges = cnt;
    virtualEdgeHeadList = N_GNEW(cnt, node_t*);
    virtualEdgeTailList = N_GNEW(cnt, node_t*);

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        for (lc = 0, cnt = 0; lc < ND_in(n).size; lc++) {
            e = ND_in(n).list[lc];
            if (ED_edge_type(e) == VIRTUAL) {
                virtualEdgeHeadList[cnt] = e->head;
                virtualEdgeTailList[cnt] = e->tail;
                if (Verbose)
                    printf("saved virtual edge: %s->%s\n", 
                        virtualEdgeTailList[cnt]->name, 
                        virtualEdgeHeadList[cnt]->name);            
                cnt++;
            }
        }
    }
}

static void
restoreVirtualEdges(graph_t *g)
{
    int i;
    edge_t e;

    for (i = 0; i < nVirtualEdges; i++) {
        if (virtualEdgeTailList[i] && virtualEdgeHeadList[i]) {
            if (Verbose)
                printf("restoring virtual edge: %s->%s\n", 
                    virtualEdgeTailList[i]->name, virtualEdgeHeadList[i]->name);
            virtual_edge(virtualEdgeTailList[i], virtualEdgeHeadList[i], NULL);
        }
    }
    if (Verbose)
        printf("restored %d virt edges\n", nVirtualEdges);
}
#endif

/* dot1_rank:
 * asp != NULL => g is root
 */
static void dot1_rank(graph_t * g, aspect_t* asp)
{
    point p;
#ifdef ALLOW_LEVELS
    attrsym_t* N_level;
#endif
    edgelabel_ranks(g);

    if (asp) {
        init_UF_size(g);
        initEdgeTypes(g);
    }

    collapse_sets(g,g);
    /*collapse_leaves(g); */
    class1(g);
    p = minmax_edges(g);
    decompose(g, 0);
    if (asp && ((GD_comp(g).size > 1)||(GD_n_cluster(g) > 0))) {
        asp->badGraph = 1;
        asp = NULL;
    }
    acyclic(g);
    if (minmax_edges2(g, p))
        decompose(g, 0);
#ifdef ALLOW_LEVELS
    if ((N_level = agattr(g,AGNODE,"level",NULL)))
        setRanks(g, N_level);
    else
#endif

    if (asp)
        rank3(g, asp);
    else
        rank1(g);

    expand_ranksets(g, asp);
    cleanup1(g);
}

void dot_rank(graph_t * g, aspect_t* asp)
{
    if (agget (g, "newrank")) {
        GD_flags(g) |= NEW_RANK;
        dot2_rank (g, asp);
    }
    else
        dot1_rank (g, asp);
    if (Verbose)
        fprintf (stderr, "Maxrank = %d, minrank = %d\n", GD_maxrank(g), GD_minrank(g));
}

int is_cluster(graph_t * g)
{
    return (strncmp(agnameof(g), "cluster", 7) == 0);
}

#ifdef OBSOLETE
static node_t*
merge_leaves(graph_t * g, node_t * cur, node_t * new)
{
    node_t *rv;

    if (cur == NULL)
        rv = new;
    else {
        rv = UF_union(cur, new);
        ND_ht(rv) = MAX(ND_ht(cur), ND_ht(new));
        ND_lw(rv) = ND_lw(cur) + ND_lw(new) + GD_nodesep(g) / 2;
        ND_rw(rv) = ND_rw(cur) + ND_rw(new) + GD_nodesep(g) / 2;
    }
    return rv;
}

static void 
potential_leaf(graph_t * g, edge_t * e, node_t * leaf)
{
    node_t *par;

    if ((ED_tail_port(e).p.x) || (ED_head_port(e).p.x))
        return;
    if ((ED_minlen(e) != 1) || (ND_order(agtail(e)) > 0))
        return;
    par = ((leaf != aghead(e)) ? aghead(e) : agtail(e));
    ND_ranktype(leaf) = LEAFSET;
    if (par == agtail(e))
        GD_outleaf(par) = merge_leaves(g, GD_outleaf(par), leaf);
    else
        GD_inleaf(par) = merge_leaves(g, GD_inleaf(par), leaf);
}

static void 
collapse_leaves(graph_t * g)
{
    node_t *n;
    edge_t *e;

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {

        /* consider n as a potential leaf of some other node. */
        if ((ND_ranktype(n) != NOCMD) || (ND_order(n)))
            continue;
        if (agfstout(g, n) == NULL) {
            if ((e = agfstin(g, n)) && (agnxtin(g, e) == NULL)) {
                potential_leaf(g, AGMKOUT(e), n);
                continue;
            }
        }
        if (agfstin(g, n) == NULL) {
            if ((e = agfstout(g, n)) && (agnxtout(g, e) == NULL)) {
                potential_leaf(g, e, n);
                continue;
            }
        }
    }
}
#endif

/* new ranking code:
 * Allows more constraints
 * Copy of level.c in dotgen2
 * Many of the utility functions are simpler or gone with
 * cgraph library.
 */
#define BACKWARD_PENALTY        1000
#define STRONG_CLUSTER_WEIGHT   1000
#define NORANK          6
#define ROOT    "\177root"
#define TOPNODE     "\177top"
#define BOTNODE     "\177bot"

/* hops is not used in dot, so we overload it to 
 * contain the index of the connected component
 */
#define ND_comp(n)  ND_hops(n)   

extern int rank2(Agraph_t *, int, int, int);

static void set_parent(graph_t* g, graph_t* p) 
{
    GD_parent(g) = p;
    make_new_cluster(p, g);
    node_induce(p, g);
}

static int is_empty(graph_t * g)
{
    return (!agfstnode(g));
}

static int is_a_strong_cluster(graph_t * g)
{
    int rv;
    char *str = agget(g, "compact");
    /* rv = mapBool((str), TRUE); */
    rv = mapBool((str), FALSE);
    return rv;
}

static int rankset_kind(graph_t * g)
{
    char *str = agget(g, "rank");

    if (str && str[0]) {
        if (!strcmp(str, "min"))
            return MINRANK;
        if (!strcmp(str, "source"))
            return SOURCERANK;
        if (!strcmp(str, "max"))
            return MAXRANK;
        if (!strcmp(str, "sink"))
            return SINKRANK;
        if (!strcmp(str, "same"))
            return SAMERANK;
    }
    return NORANK;
}

static int is_nonconstraint(edge_t * e)
{
    char *constr;

    if (E_constr && (constr = agxget(e, E_constr))) {
        if (constr[0] && mapbool(constr) == FALSE)
            return TRUE;
    }
    return FALSE;
}

static node_t *find(node_t * n)
{
    node_t *set;
    if ((set = ND_set(n))) {
        if (set != n)
            set = ND_set(n) = find(set);
    } else
        set = ND_set(n) = n;
    return set;
}

static node_t *union_one(node_t * leader, node_t * n)
{
    if (n)
        return (ND_set(find(n)) = find(leader));
    else
        return leader;
}

static node_t *union_all(graph_t * g)
{
    node_t *n, *leader;

    n = agfstnode(g);
    if (!n)
        return n;
    leader = find(n);
    while ((n = agnxtnode(g, n)))
        union_one(leader, n);
    return leader;
}

static void compile_samerank(graph_t * ug, graph_t * parent_clust)
{
    graph_t *s;                 /* subgraph being scanned */
    graph_t *clust;             /* cluster that contains the rankset */
    node_t *n, *leader;

    if (is_empty(ug))
        return;
    if (is_a_cluster(ug)) {
        clust = ug;
        if (parent_clust) {
            GD_level(ug) = GD_level(parent_clust) + 1;
            set_parent(ug, parent_clust);
        }
        else
            GD_level(ug) = 0;
    } else
        clust = parent_clust;

    /* process subgraphs of this subgraph */
    for (s = agfstsubg(ug); s; s = agnxtsubg(s))
        compile_samerank(s, clust);

    /* process this subgraph as a cluster */
    if (is_a_cluster(ug)) {
        for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
            if (ND_clust(n) == 0)
                ND_clust(n) = ug;
#ifdef DEBUG
            fprintf(stderr, "(%s) %s  %p\n", agnameof(ug), agnameof(n),
                    ND_clust(n));
#endif
        }
    }

    /* process this subgraph as a rankset */
    switch (rankset_kind(ug)) {
    case SOURCERANK:
        GD_has_sourcerank(clust) = TRUE;        /* fall through */
    case MINRANK:
        leader = union_all(ug);
        GD_minrep(clust) = union_one(leader, GD_minrep(clust));
        break;
    case SINKRANK:
        GD_has_sinkrank(clust) = TRUE;  /* fall through */
    case MAXRANK:
        leader = union_all(ug);
        GD_maxrep(clust) = union_one(leader, GD_maxrep(clust));
        break;
    case SAMERANK:
        leader = union_all(ug);
        /* do we need to record these ranksets? */
        break;
    case NORANK:
        break;
    default:                    /* unrecognized - warn and do nothing */
        agerr(AGWARN, "%s has unrecognized rank=%s", agnameof(ug),
              agget(ug, "rank"));
    }

    /* a cluster may become degenerate */
    if (is_a_cluster(ug) && GD_minrep(ug)) {
        if (GD_minrep(ug) == GD_maxrep(ug)) {
            node_t *up = union_all(ug);
            GD_minrep(ug) = up;
            GD_maxrep(ug) = up;
        }
    }
}

static graph_t *dot_lca(graph_t * c0, graph_t * c1)
{
    while (c0 != c1) {
        if (GD_level(c0) >= GD_level(c1))
            c0 = GD_parent(c0);
        else
            c1 = GD_parent(c1);
    }
    return c0;
}

static int is_internal_to_cluster(edge_t * e)
{
    graph_t *par, *ct, *ch;
    ct = ND_clust(agtail(e));
    ch = ND_clust(aghead(e));
    if (ct == ch)
        return TRUE;
    par = dot_lca(ct, ch);
    /* if (par == agroot(par)) */
        /* return FALSE; */
    if ((par == ct) || (par == ch))
        return TRUE;
    return FALSE;
}

static node_t* Last_node;
static node_t* makeXnode (graph_t* G, char* name)
{
    node_t *n = agnode(G, name, 1);
    alloc_elist(4, ND_in(n));
    alloc_elist(4, ND_out(n));
    if (Last_node) {
        ND_prev(n) = Last_node;
        ND_next(Last_node) = n;
    } else {
        ND_prev(n) = NULL;
        GD_nlist(G) = n;
    }
    Last_node = n;
    ND_next(n) = NULL;
    
    return n;
}

static void compile_nodes(graph_t * g, graph_t * Xg)
{
    /* build variables */
    node_t *n;

    Last_node = NULL;
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        if (find(n) == n)
            ND_rep(n) = makeXnode (Xg, agnameof(n));
    }
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        if (ND_rep(n) == 0)
            ND_rep(n) = ND_rep(find(n));
    }
}

static void merge(edge_t * e, int minlen, int weight)
{
    ED_minlen(e) = MAX(ED_minlen(e), minlen);
    ED_weight(e) += weight;
}

static void strong(graph_t * g, node_t * t, node_t * h, edge_t * orig)
{
    edge_t *e;
    if ((e = agfindedge(g, t, h)) ||
        (e = agfindedge(g, h, t)) || (e = agedge(g, t, h, 0, 1)))
        merge(e, ED_minlen(orig), ED_weight(orig));
    else
        agerr(AGERR, "ranking: failure to create strong constraint edge between nodes %s and %s\n", 
            agnameof(t), agnameof(h));
}

static void weak(graph_t * g, node_t * t, node_t * h, edge_t * orig)
{
    node_t *v;
    edge_t *e, *f;
    static int id;
    char buf[100];

    for (e = agfstin(g, t); e; e = agnxtin(g, e)) {
        /* merge with existing weak edge (e,f) */
        v = agtail(e);
        if ((f = agfstout(g, v)) && (aghead(f) == h)) {
            return;
        }
    }
    if (!e) {
        sprintf (buf, "_weak_%d", id++);
        v = makeXnode(g, buf);
        e = agedge(g, v, t, 0, 1);
        f = agedge(g, v, h, 0, 1);
    }
    ED_minlen(e) = MAX(ED_minlen(e), 0);        /* effectively a nop */
    ED_weight(e) += ED_weight(orig) * BACKWARD_PENALTY;
    ED_minlen(f) = MAX(ED_minlen(f), ED_minlen(orig));
    ED_weight(f) += ED_weight(orig);
}

static void compile_edges(graph_t * ug, graph_t * Xg)
{
    node_t *n;
    edge_t *e;
    node_t *Xt, *Xh;
    graph_t *tc, *hc;

    /* build edge constraints */
    for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
        Xt = ND_rep(n);
        for (e = agfstout(ug, n); e; e = agnxtout(ug, e)) {
            if (is_nonconstraint(e))
                continue;
            Xh = ND_rep(find(aghead(e)));
            if (Xt == Xh)
                continue;

            tc = ND_clust(agtail(e));
            hc = ND_clust(aghead(e));

            if (is_internal_to_cluster(e)) {
                /* determine if graph requires reversed edge */
                if ((find(agtail(e)) == GD_maxrep(ND_clust(agtail(e))))
                    || (find(aghead(e)) == GD_minrep(ND_clust(aghead(e))))) {
                    node_t *temp = Xt;
                    Xt = Xh;
                    Xh = temp;
                }
                strong(Xg, Xt, Xh, e);
            } else {
                if (is_a_strong_cluster(tc) || is_a_strong_cluster(hc))
                    weak(Xg, Xt, Xh, e);
                else
                    strong(Xg, Xt, Xh, e);
            }
        }
    }
}

static void compile_clusters(graph_t* g, graph_t* Xg, node_t* top, node_t* bot)
{
    node_t *n;
    node_t *rep;
    edge_t *e;
    graph_t *sub;

    if (is_a_cluster(g) && is_a_strong_cluster(g)) {
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
            if (agfstin(g, n) == 0) {
                rep = ND_rep(find(n));
                if (!top) top = makeXnode(Xg,TOPNODE);
                agedge(Xg, top, rep, 0, 1);
            }
            if (agfstout(g, n) == 0) {
                rep = ND_rep(find(n));
                if (!bot)  bot = makeXnode(Xg,BOTNODE);
                agedge(Xg, rep, bot, 0, 1);
            }
        }
        if (top && bot) {
            e = agedge(Xg, top, bot, 0, 1);
            merge(e, 0, STRONG_CLUSTER_WEIGHT);
        }
    }
    for (sub = agfstsubg(g); sub; sub = agnxtsubg(sub))
        compile_clusters(sub, Xg, top, bot);
}

static void reverse_edge2(graph_t * g, edge_t * e)
{
    edge_t *rev;

    rev = agfindedge(g, aghead(e), agtail(e));
    if (!rev)
        rev = agedge(g, aghead(e), agtail(e), 0, 1);
    merge(rev, ED_minlen(e), ED_weight(e));
    agdelete(g, e);
}

static void dfs(graph_t * g, node_t * v)
{
    edge_t *e, *f;
    node_t *w;

    if (ND_mark(v))
        return;
    ND_mark(v) = TRUE;
    ND_onstack(v) = TRUE;
    for (e = agfstout(g, v); e; e = f) {
        f = agnxtout(g, e);
        w = aghead(e);
        if (ND_onstack(w))
            reverse_edge2(g, e);
        else {
            if (ND_mark(w) == FALSE)
                dfs(g, w);
        }
    }
    ND_onstack(v) = FALSE;
}

static void break_cycles(graph_t * g)
{
    node_t *n;

    for (n = agfstnode(g); n; n = agnxtnode(g, n))
        ND_mark(n) = ND_onstack(n) = FALSE;
    for (n = agfstnode(g); n; n = agnxtnode(g, n))
        dfs(g, n);
}
/* setMinMax:
 * This will only be called with the root graph or a cluster
 * which are guaranteed to contain nodes. Thus, leader will be
 * set.
 */
static void setMinMax (graph_t* g, int doRoot)
{
    int c, v;
    node_t *n;
    node_t* leader = NULL;

      /* Do child clusters */
    for (c = 1; c <= GD_n_cluster(g); c++)
            setMinMax(GD_clust(g)[c], 0);

    if (!GD_parent(g) && !doRoot) // root graph
        return;

    GD_minrank(g) = MAXSHORT;
    GD_maxrank(g) = -1;
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        v = ND_rank(n);
        if (GD_maxrank(g) < v)
            GD_maxrank(g) = v;
        if (GD_minrank(g) > v) {
            GD_minrank(g) = v;
            leader = n;
        }
    }
    GD_leader(g) = leader;
}

/* readout_levels:
 * Store node rank information in original graph.
 * Set rank bounds in graph and clusters
 * Free added data structures.
 *
 * rank2 is called with balance=1, which ensures that minrank=0
 */
static void readout_levels(graph_t * g, graph_t * Xg, int ncc)
{
    node_t *n;
    node_t *xn;
    int* minrk = NULL;
    int doRoot = 0;

    GD_minrank(g) = MAXSHORT;
    GD_maxrank(g) = -1;
    if (ncc > 1) {
        int i;
        minrk = N_NEW(ncc+1,int);
        for (i = 1; i <= ncc; i++)
            minrk[i] = MAXSHORT;
    }
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        xn = ND_rep(find(n));
        ND_rank(n) = ND_rank(xn);
        if (GD_maxrank(g) < ND_rank(n))
            GD_maxrank(g) = ND_rank(n);
        if (GD_minrank(g) > ND_rank(n))
            GD_minrank(g) = ND_rank(n);
        if (minrk) {
            ND_comp(n) = ND_comp(xn);
            minrk[ND_comp(n)] = MIN(minrk[ND_comp(n)],ND_rank(n));
        }
    }
    if (minrk) {
        for (n = agfstnode(g); n; n = agnxtnode(g, n))
            ND_rank(n) -= minrk[ND_comp(n)];
        /* Non-uniform shifting, so recompute maxrank/minrank of root graph */
        doRoot = 1;
    }
    else if (GD_minrank(g) > 0) {  /* should never happen */
        int delta = GD_minrank(g);
        for (n = agfstnode(g); n; n = agnxtnode(g, n))
            ND_rank(n) -= delta;
        GD_minrank(g) -= delta;
        GD_maxrank(g) -= delta;
    }

    setMinMax(g, doRoot);

    /* release fastgraph memory from Xg */
    for (n = agfstnode(Xg); n; n = agnxtnode(Xg, n)) {
        free_list(ND_in(n));
        free_list(ND_out(n));
    }

    free(ND_alg(agfstnode(g)));
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        ND_alg(n) = NULL;
    }
    if (minrk)
        free (minrk);
}

static void dfscc(graph_t * g, node_t * n, int cc)
{
    edge_t *e;
    if (ND_comp(n) == 0) {
        ND_comp(n) = cc;
        for (e = agfstout(g, n); e; e = agnxtout(g, e))
            dfscc(g, aghead(e), cc);
        for (e = agfstin(g, n); e; e = agnxtin(g, e))
            dfscc(g, agtail(e), cc);
    }
}

static int connect_components(graph_t * g)
{
    int cc = 0;
    node_t *n;

    for (n = agfstnode(g); n; n = agnxtnode(g, n))
        ND_comp(n) = 0;
    for (n = agfstnode(g); n; n = agnxtnode(g, n))
        if (ND_comp(n) == 0)
            dfscc(g, n, ++cc);
    if (cc > 1) {
        node_t *root = makeXnode(g, ROOT);
        int ncc = 1;
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
            if (ND_comp(n) == ncc) {
                (void) agedge(g, root, n, 0, 1);
                ncc++;
            }
        }
    }
    return (cc);
}

static void add_fast_edges (graph_t * g)
{
    node_t *n;
    edge_t *e;
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
            elist_append(e, ND_out(n));
            elist_append(e, ND_in(aghead(e)));
        }
    }
}

static void my_init_graph(Agraph_t *g, Agobj_t *graph, void *arg)
{ int *sz = arg; agbindrec(graph,"level graph rec",sz[0],TRUE); }
static void my_init_node(Agraph_t *g, Agobj_t *node, void *arg)
{ int *sz = arg; agbindrec(node,"level node rec",sz[1],TRUE); }
static void my_init_edge(Agraph_t *g, Agobj_t *edge, void *arg)
{ int *sz = arg; agbindrec(edge,"level edge rec",sz[2],TRUE); }
static Agcbdisc_t mydisc = { {my_init_graph,0,0}, {my_init_node,0,0}, {my_init_edge,0,0} };

int infosizes[] = {
    sizeof(Agraphinfo_t), 
    sizeof(Agnodeinfo_t),
    sizeof(Agedgeinfo_t)
};

void dot2_rank(graph_t * g, aspect_t* asp)
{
    int ssize;
    int ncc, maxiter = INT_MAX;
    char *s;
    graph_t *Xg;

    Last_node = NULL;
    Xg = agopen("level assignment constraints", Agstrictdirected, 0);
    agbindrec(Xg,"level graph rec",sizeof(Agraphinfo_t),TRUE);
    agpushdisc(Xg,&mydisc,infosizes);

    edgelabel_ranks(g);

    if ((s = agget(g, "nslimit1")))
        maxiter = atof(s) * agnnodes(g);
    else
        maxiter = INT_MAX;

    compile_samerank(g, 0);
    compile_nodes(g, Xg);
    compile_edges(g, Xg);
    compile_clusters(g, Xg, 0, 0);
    break_cycles(Xg);
    ncc = connect_components(Xg);
    add_fast_edges (Xg);

    if (asp) {
        init_UF_size(Xg);
        initEdgeTypes(Xg);
    }

    if ((s = agget(g, "searchsize")))
        ssize = atoi(s);
    else
        ssize = -1;
    rank2(Xg, 1, maxiter, ssize);
/* fastgr(Xg); */
    readout_levels(g, Xg, ncc);
#ifdef DEBUG
    fprintf (stderr, "Xg %d nodes %d edges\n", agnnodes(Xg), agnedges(Xg));
#endif
    agclose(Xg);
}