flat.c

Go to the documentation of this file.

/*************************************************************************
 * 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
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
#include "config.h"
 
#include        <assert.h>
#include        <dotgen/dot.h>
#include        <stdbool.h>
#include        <stddef.h>
#include        <util/alloc.h>
#include        <util/gv_math.h>
 
static node_t *make_vn_slot(graph_t * g, int r, int pos)
{
    int i;
    node_t *n;
 
    assert(GD_rank(g)[r].av == GD_rank(g)[r].v);
    GD_rank(g)[r].av = gv_recalloc(GD_rank(g)[r].av, GD_rank(g)[r].n + 1,
                                   GD_rank(g)[r].n + 2, sizeof(node_t *));
    GD_rank(g)[r].v = GD_rank(g)[r].av;
    node_t **const v = GD_rank(g)[r].v;
    for (i = GD_rank(g)[r].n; i > pos; i--) {
        v[i] = v[i - 1];
        ND_order(v[i])++;
    }
    n = v[pos] = virtual_node(g);
    ND_order(n) = pos;
    ND_rank(n) = r;
    v[++GD_rank(g)[r].n] = NULL;
    return v[pos];
}
 
#define         HLB     0       /* hard left bound */
#define         HRB             1       /* hard right bound */
#define         SLB             2       /* soft left bound */
#define         SRB             3       /* soft right bound */
 
static void findlr(node_t * u, node_t * v, int *lp, int *rp)
{
    int l, r;
    l = ND_order(u);
    r = ND_order(v);
    if (l > r) {
        SWAP(&l, &r);
    }
    *lp = l;
    *rp = r;
}
 
static void setbounds(node_t * v, int *bounds, int lpos, int rpos)
{
    int i, l, r, ord;
    edge_t *f;
 
    if (ND_node_type(v) == VIRTUAL) {
        ord = ND_order(v);
        if (ND_in(v).size == 0) {       /* flat */
            assert(ND_out(v).size == 2);
            findlr(aghead(ND_out(v).list[0]), aghead(ND_out(v).list[1]), &l,
                   &r);
            /* the other flat edge could be to the left or right */
            if (r <= lpos)
                bounds[SLB] = bounds[HLB] = ord;
            else if (l >= rpos)
                bounds[SRB] = bounds[HRB] = ord;
            /* could be spanning this one */
            else if (l < lpos && r > rpos); // ignore
            /* must have intersecting ranges */
            else {
                if (l < lpos || (l == lpos && r < rpos))
                    bounds[SLB] = ord;
                if (r > rpos || (r == rpos && l > lpos))
                    bounds[SRB] = ord;
            }
        } else {                /* forward */
            bool onleft, onright;
            onleft = onright = false;
            for (i = 0; (f = ND_out(v).list[i]); i++) {
                if (ND_order(aghead(f)) <= lpos) {
                    onleft = true;
                    continue;
                }
                if (ND_order(aghead(f)) >= rpos) {
                    onright = true;
                    continue;
                }
            }
            if (onleft && !onright)
                bounds[HLB] = ord + 1;
            if (onright && !onleft)
                bounds[HRB] = ord - 1;
        }
    }
}
 
static int flat_limits(graph_t * g, edge_t * e)
{
    int lnode, rnode, r, bounds[4], lpos, rpos, pos;
    node_t **rank;
 
    r = ND_rank(agtail(e)) - 1;
    rank = GD_rank(g)[r].v;
    lnode = 0;
    rnode = GD_rank(g)[r].n - 1;
    bounds[HLB] = bounds[SLB] = lnode - 1;
    bounds[HRB] = bounds[SRB] = rnode + 1;
    findlr(agtail(e), aghead(e), &lpos, &rpos);
    while (lnode <= rnode) {
        setbounds(rank[lnode], bounds, lpos, rpos);
        if (lnode != rnode)
            setbounds(rank[rnode], bounds, lpos, rpos);
        lnode++;
        rnode--;
        if (bounds[HRB] - bounds[HLB] <= 1)
            break;
    }
    if (bounds[HLB] <= bounds[HRB])
        pos = (bounds[HLB] + bounds[HRB] + 1) / 2;
    else
        pos = (bounds[SLB] + bounds[SRB] + 1) / 2;
    return pos;
}
 
/* Create virtual node representing edge label between
 * actual ends of edge e. 
 * This node is characterized by being virtual and having a non-NULL
 * ND_alg pointing to e.
 */
static void 
flat_node(edge_t * e)
{
    int r, place;
    double ypos, h2;
    graph_t *g;
    node_t *n, *vn;
    edge_t *ve;
    pointf dimen;
 
    if (ED_label(e) == NULL)
        return;
    g = dot_root(agtail(e));
    r = ND_rank(agtail(e));
 
    place = flat_limits(g, e);
    /* grab ypos = LL.y of label box before make_vn_slot() */
    if ((n = GD_rank(g)[r - 1].v[0]))
        ypos = ND_coord(n).y - GD_rank(g)[r - 1].ht1;
    else {
        n = GD_rank(g)[r].v[0];
        ypos = ND_coord(n).y + GD_rank(g)[r].ht2 + GD_ranksep(g);
    }
    vn = make_vn_slot(g, r - 1, place);
    dimen = ED_label(e)->dimen;
    if (GD_flip(g)) {
        SWAP(&dimen.x, &dimen.y);
    }
    ND_ht(vn) = dimen.y;
    h2 = ND_ht(vn) / 2;
    ND_lw(vn) = ND_rw(vn) = dimen.x / 2;
    ND_label(vn) = ED_label(e);
    ND_coord(vn).y = ypos + h2;
    ve = virtual_edge(vn, agtail(e), e);        /* was NULL? */
    ED_tail_port(ve).p.x = -ND_lw(vn);
    ED_head_port(ve).p.x = ND_rw(agtail(e));
    ED_edge_type(ve) = FLATORDER;
    ve = virtual_edge(vn, aghead(e), e);
    ED_tail_port(ve).p.x = ND_rw(vn);
    ED_head_port(ve).p.x = ND_lw(aghead(e));
    ED_edge_type(ve) = FLATORDER;
    /* another assumed symmetry of ht1/ht2 of a label node */
    if (GD_rank(g)[r - 1].ht1 < h2)
        GD_rank(g)[r - 1].ht1 = h2;
    if (GD_rank(g)[r - 1].ht2 < h2)
        GD_rank(g)[r - 1].ht2 = h2;
    ND_alg(vn) = e;
}
 
static void abomination(graph_t * g)
{
    int r;
 
    assert(GD_minrank(g) == 0);
    /* 3 = one for new rank, one for sentinel, one for off-by-one */
    r = GD_maxrank(g) + 3;
    rank_t *rptr = gv_recalloc(GD_rank(g), GD_maxrank(g) + 1, r,
                               sizeof(rank_t));
    GD_rank(g) = rptr + 1;
    for (r = GD_maxrank(g); r >= 0; r--)
        GD_rank(g)[r] = GD_rank(g)[r - 1];
    GD_rank(g)[r].n = GD_rank(g)[r].an = 0;
    GD_rank(g)[r].v = GD_rank(g)[r].av = gv_calloc(2, sizeof(node_t *));
    GD_rank(g)[r].flat = NULL;
    GD_rank(g)[r].ht1 = GD_rank(g)[r].ht2 = 1;
    GD_rank(g)[r].pht1 = GD_rank(g)[r].pht2 = 1;
    GD_minrank(g)--;
}
 
/* Check if tn and hn are adjacent. 
 * If so, set adjacent bit on all related edges.
 * Assume e is flat.
 */
static void
checkFlatAdjacent (edge_t* e)
{
    node_t* tn = agtail(e);
    node_t* hn = aghead(e);
    int i, lo, hi;
    node_t* n;
    rank_t *rank;
 
    if (ND_order(tn) < ND_order(hn)) {
        lo = ND_order(tn);
        hi = ND_order(hn);
    }
    else {
        lo = ND_order(hn);
        hi = ND_order(tn);
    }
    rank = &GD_rank(dot_root(tn))[ND_rank(tn)];
    for (i = lo + 1; i < hi; i++) {
        n = rank->v[i];
        if ((ND_node_type(n) == VIRTUAL && ND_label(n)) || 
             ND_node_type(n) == NORMAL)
            break;
    }
    if (i == hi) {  /* adjacent edge */
        do {
            ED_adjacent(e) = 1;
            e = ED_to_virt(e);
        } while (e); 
    }
}
 
/* Process flat edges.
 * First, mark flat edges as having adjacent endpoints or not.
 *
 * Second, if there are edge labels, nodes are placed on ranks 0,2,4,...
 * If we have a labeled flat edge on rank 0, add a rank -1.
 *
 * Finally, create label information. Add a virtual label node in the 
 * previous rank for each labeled, non-adjacent flat edge. If this is 
 * done for any edge, return true, so that main code will reset y coords.
 * For labeled adjacent flat edges, store label width in representative edge.
 * FIX: We should take into account any extra height needed for the latter
 * labels.
 * 
 * We leave equivalent flat edges in ND_other. Their ED_virt field should
 * still point to the class representative.
 */
int 
flat_edges(graph_t * g)
{
    int i;
    bool reset = false;
    node_t *n;
    edge_t *e;
 
    for (n = GD_nlist(g); n; n = ND_next(n)) {
        if (ND_flat_out(n).list) {
            for (size_t j = 0; (e = ND_flat_out(n).list[j]); j++) {
                checkFlatAdjacent (e);
            }
        }
        for (size_t j = 0; j < ND_other(n).size; j++) {
            e = ND_other(n).list[j];
            if (ND_rank(aghead(e)) == ND_rank(agtail(e)))
                checkFlatAdjacent (e);
        }
    }
 
    if (GD_rank(g)[0].flat || GD_n_cluster(g) > 0) {
        bool found = false;
        for (i = 0; (n = GD_rank(g)[0].v[i]); i++) {
            for (size_t j = 0; (e = ND_flat_in(n).list[j]); j++) {
                if (ED_label(e) && !ED_adjacent(e)) {
                    abomination(g);
                    found = true;
                    break;
                }
            }
            if (found)
                break;
        }
    }
 
    rec_save_vlists(g);
    for (n = GD_nlist(g); n; n = ND_next(n)) {
          /* if n is the tail of any flat edge, one will be in flat_out */
        if (ND_flat_out(n).list) {
            for (i = 0; (e = ND_flat_out(n).list[i]); i++) {
                if (ED_label(e)) {
                    if (ED_adjacent(e)) {
                        ED_dist(e) = GD_flip(g) ? ED_label(e)->dimen.y : ED_label(e)->dimen.x;
                    }
                    else {
                        reset = true;
                        flat_node(e);
                    }
                }
            }
                /* look for other flat edges with labels */
            for (size_t j = 0; j < ND_other(n).size; j++) {
                edge_t* le;
                e = ND_other(n).list[j];
                if (ND_rank(agtail(e)) != ND_rank(aghead(e))) continue;
                if (agtail(e) == aghead(e)) continue; /* skip loops */
                le = e;
                while (ED_to_virt(le)) le = ED_to_virt(le);
                ED_adjacent(e) = ED_adjacent(le); 
                if (ED_label(e)) {
                    if (ED_adjacent(e)) {
                        const double lw = GD_flip(g) ? ED_label(e)->dimen.y : ED_label(e)->dimen.x;
                        ED_dist(le) = MAX(lw,ED_dist(le));
                    }
                    else {
                        reset = true;
                        flat_node(e);
                    }
                }
            }
        }
    }
    if (reset) {
        checkLabelOrder(g);
        rec_reset_vlists(g);
    }
    return reset;
}