cluster.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>
 
static node_t*
map_interclust_node(node_t * n)
{
    node_t *rv;
 
    if (ND_clust(n) == NULL || GD_expanded(ND_clust(n)))
        rv = n;
    else
        rv = GD_rankleader(ND_clust(n))[ND_rank(n)];
    return rv;
}
 
/* make d slots starting at position pos (where 1 already exists) */
static void 
make_slots(graph_t * root, int r, int pos, int d)
{
    int i;
    node_t *v, **vlist;
    vlist = GD_rank(root)[r].v;
    if (d <= 0) {
        for (i = pos - d + 1; i < GD_rank(root)[r].n; i++) {
            v = vlist[i];
            ND_order(v) = i + d - 1;
            vlist[ND_order(v)] = v;
        }
        for (i = GD_rank(root)[r].n + d - 1; i < GD_rank(root)[r].n; i++)
            vlist[i] = NULL;
    } else {
/*assert(ND_rank(root)[r].n + d - 1 <= ND_rank(root)[r].an);*/
        for (i = GD_rank(root)[r].n - 1; i > pos; i--) {
            v = vlist[i];
            ND_order(v) = i + d - 1;
            vlist[ND_order(v)] = v;
        }
        for (i = pos + 1; i < pos + d; i++)
            vlist[i] = NULL;
    }
    GD_rank(root)[r].n += d - 1;
}
 
static node_t* 
clone_vn(graph_t * g, node_t * vn)
{
    const int r = ND_rank(vn);
    make_slots(g, r, ND_order(vn), 2);
    node_t *const rv = virtual_node(g);
    ND_lw(rv) = ND_lw(vn);
    ND_rw(rv) = ND_rw(vn);
    ND_rank(rv) = ND_rank(vn);
    ND_order(rv) = ND_order(vn) + 1;
    GD_rank(g)[r].v[ND_order(rv)] = rv;
    return rv;
}
 
static void 
map_path(node_t * from, node_t * to, edge_t * orig, edge_t * ve, int type)
{
    int r;
    node_t *u, *v;
    edge_t *e;
 
    assert(ND_rank(from) < ND_rank(to));
 
    if (agtail(ve) == from && aghead(ve) == to)
        return;
 
    if (ED_count(ve) > 1) {
        ED_to_virt(orig) = NULL;
        if (ND_rank(to) - ND_rank(from) == 1) {
            if ((e = find_fast_edge(from, to)) && ports_eq(orig, e)) {
                merge_oneway(orig, e);
                if (ND_node_type(from) == NORMAL && ND_node_type(to) == NORMAL)
                    other_edge(orig);
                return;
            }
        }
        u = from;
        for (r = ND_rank(from); r < ND_rank(to); r++) {
            if (r < ND_rank(to) - 1)
                v = clone_vn(dot_root(from), aghead(ve));
            else
                v = to;
            e = virtual_edge(u, v, orig);
            ED_edge_type(e) = type;
            u = v;
            ED_count(ve)--;
            ve = ND_out(aghead(ve)).list[0];
        }
    } else {
        if (ND_rank(to) - ND_rank(from) == 1) {
            if ((ve = find_fast_edge(from, to)) && ports_eq(orig, ve)) {
                /*ED_to_orig(ve) = orig; */
                ED_to_virt(orig) = ve;
                ED_edge_type(ve) = type;
                ED_count(ve)++;
                if (ND_node_type(from) == NORMAL && ND_node_type(to) == NORMAL)
                    other_edge(orig);
            } else {
                ED_to_virt(orig) = NULL;
                ve = virtual_edge(from, to, orig);
                ED_edge_type(ve) = type;
            }
        }
        if (ND_rank(to) - ND_rank(from) > 1) {
            if (agtail(ve) != from) {
                ED_to_virt(orig) = NULL;
                e = ED_to_virt(orig) = virtual_edge(from, aghead(ve), orig);
                delete_fast_edge(ve);
            } else
                e = ve;
            while (ND_rank(aghead(e)) != ND_rank(to))
                e = ND_out(aghead(e)).list[0];
            if (aghead(e) != to) {
                ve = e;
                e = virtual_edge(agtail(e), to, orig);
                ED_edge_type(e) = type;
                delete_fast_edge(ve);
            }
        }
    }
}
 
static void make_interclust_chain(node_t * from, node_t * to, edge_t * orig) {
    int newtype;
    node_t *u, *v;
 
    u = map_interclust_node(from);
    v = map_interclust_node(to);
    if (u == from && v == to)
        newtype = VIRTUAL;
    else
        newtype = CLUSTER_EDGE;
    map_path(u, v, orig, ED_to_virt(orig), newtype);
}
 
/* 
 * attach and install edges between clusters.
 * essentially, class2() for interclust edges.
 */
static void interclexp(graph_t * subg)
{
    edge_t *next;
 
    graph_t *const g = dot_root(subg);
    for (node_t *n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
 
        /* N.B. n may be in a sub-cluster of subg */
        edge_t *prev = NULL;
        for (edge_t *e = agfstedge(g, n); e; e = next) {
            next = agnxtedge(g, e, n);
            if (agcontains(subg, e))
                continue;
 
            /* canonicalize edge */
            e = AGMKOUT(e);
            /* short/flat multi edges */
            if (mergeable(prev, e)) {
                if (ND_rank(agtail(e)) == ND_rank(aghead(e)))
                    ED_to_virt(e) = prev;
                else
                    ED_to_virt(e) = NULL;
                if (ED_to_virt(prev) == NULL)
                    continue;   /* internal edge */
                ED_to_virt(e) = NULL;
                merge_chain(subg, e, ED_to_virt(prev), false);
                safe_other_edge(e);
                continue;
            }
 
            /* flat edges */
            if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
                edge_t* fe;
                if ((fe = find_flat_edge(agtail(e), aghead(e))) == NULL) {
                    if (!ED_to_virt(e)) {
                        flat_edge(g, e);
                    }
                    prev = e;
                } else if (e != fe) {
                    safe_other_edge(e);
                    if (!ED_to_virt(e)) merge_oneway(e, fe);
                }
                continue;
            }
 
            /* forward edges */
            if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
                make_interclust_chain(agtail(e), aghead(e), e);
                prev = e;
                continue;
            }
 
            /* backward edges */
            make_interclust_chain(aghead(e), agtail(e), e);
            prev = e;
        }
    }
}
 
static void 
merge_ranks(graph_t * subg)
{
    int i, d, r, pos, ipos;
    node_t *v;
    graph_t *root;
 
    assert(GD_minrank(subg) <= GD_maxrank(subg) && "corrupted rank bounds");
 
    root = dot_root(subg);
    if (GD_minrank(subg) > 0)
        GD_rank(root)[GD_minrank(subg) - 1].valid = false;
    for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
        d = GD_rank(subg)[r].n;
        ipos = pos = ND_order(GD_rankleader(subg)[r]);
        make_slots(root, r, pos, d);
        for (i = 0; i < GD_rank(subg)[r].n; i++) {
            v = GD_rank(root)[r].v[pos] = GD_rank(subg)[r].v[i];
            ND_order(v) = pos++;
        /* real nodes automatically have v->root = root graph */
            if (ND_node_type(v) == VIRTUAL)
                v->root = agroot(root);
            delete_fast_node(subg, v);
            fast_node(root, v);
        }
        GD_rank(subg)[r].v = GD_rank(root)[r].v + ipos;
        GD_rank(root)[r].valid = false;
    }
    if (r < GD_maxrank(root))
        GD_rank(root)[r].valid = false;
    GD_expanded(subg) = true;
}
 
static void 
remove_rankleaders(graph_t * g)
{
    int r;
    node_t *v;
    edge_t *e;
 
    for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
        v = GD_rankleader(g)[r];
 
        /* remove the entire chain */
        while ((e = ND_out(v).list[0])) {
            delete_fast_edge(e);
            free(e->base.data);
            free(e);
        }
        while ((e = ND_in(v).list[0])) {
            delete_fast_edge(e);
            free(e);
        }
        delete_fast_node(dot_root(g), v);
        free(ND_in(v).list);
        free(ND_out(v).list);
        free(v->base.data);
        free(v);
        GD_rankleader(g)[r] = NULL;
    }
}
 
/* delete virtual nodes of a cluster, and install real nodes or sub-clusters */
int expand_cluster(graph_t *subg) {
    /* build internal structure of the cluster */
    class2(subg);
    GD_comp(subg).size = 1;
    GD_comp(subg).list[0] = GD_nlist(subg);
    allocate_ranks(subg);
    const int rc = build_ranks(subg, 0);
    if (rc != 0) {
        return rc;
    }
    merge_ranks(subg);
 
    /* build external structure of the cluster */
    interclexp(subg);
    remove_rankleaders(subg);
    return 0;
}
 
/* this function marks every node in <g> with its top-level cluster under <g> */
void mark_clusters(graph_t * g)
{
    int c;
    node_t *n, *nn, *vn;
    edge_t *orig, *e;
    graph_t *clust;
 
    /* remove sub-clusters below this level */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        if (ND_ranktype(n) == CLUSTER)
            UF_singleton(n);
        ND_clust(n) = NULL;
    }
 
    for (c = 1; c <= GD_n_cluster(g); c++) {
        clust = GD_clust(g)[c];
        for (n = agfstnode(clust); n; n = nn) {
                nn = agnxtnode(clust,n);
            if (ND_ranktype(n) != NORMAL) {
                agwarningf(
                      "%s was already in a rankset, deleted from cluster %s\n",
                      agnameof(n), agnameof(g));
                agdelete(clust,n);
                continue;
            }
            UF_setname(n, GD_leader(clust));
            ND_clust(n) = clust;
            ND_ranktype(n) = CLUSTER;
 
            /* here we mark the vnodes of edges in the cluster */
            for (orig = agfstout(clust, n); orig;
                 orig = agnxtout(clust, orig)) {
                if ((e = ED_to_virt(orig))) {
                    while (e && ND_node_type(vn =aghead(e)) == VIRTUAL) {
                        ND_clust(vn) = clust;
                        e = ND_out(aghead(e)).list[0];
                        /* trouble if concentrators and clusters are mixed */
                    }
                }
            }
        }
    }
}
 
void build_skeleton(graph_t * g, graph_t * subg)
{
    int r;
    node_t *v, *prev, *rl;
    edge_t *e;
 
    prev = NULL;
    GD_rankleader(subg) = gv_calloc(GD_maxrank(subg) + 2, sizeof(node_t*));
    for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
        v = GD_rankleader(subg)[r] = virtual_node(g);
        ND_rank(v) = r;
        ND_ranktype(v) = CLUSTER;
        ND_clust(v) = subg;
        if (prev) {
            e = virtual_edge(prev, v, NULL);
            ED_xpenalty(e) *= CL_CROSS;
        }
        prev = v;
    }
 
    /* set the counts on virtual edges of the cluster skeleton */
    for (v = agfstnode(subg); v; v = agnxtnode(subg, v)) {
        rl = GD_rankleader(subg)[ND_rank(v)];
        ND_UF_size(rl)++;
        for (e = agfstout(subg, v); e; e = agnxtout(subg, e)) {
            for (r = ND_rank(agtail(e)); r < ND_rank(aghead(e)); r++) {
                ED_count(ND_out(rl).list[0])++;
            }
        }
    }
    for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
        rl = GD_rankleader(subg)[r];
        if (ND_UF_size(rl) > 1)
            ND_UF_size(rl)--;
    }
}
 
int install_cluster(graph_t *g, node_t *n, int pass, node_queue_t *q) {
    int r;
    graph_t *clust;
 
    clust = ND_clust(n);
    if (GD_installed(clust) != pass + 1) {
        for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++) {
            const int rc = install_in_rank(g, GD_rankleader(clust)[r]);
            if (rc != 0) {
                return rc;
            }
        }
        for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++)
            enqueue_neighbors(q, GD_rankleader(clust)[r], pass);
        GD_installed(clust) = pass + 1;
    }
    return 0;
}
 
static void mark_lowcluster_basic(Agraph_t * g);
void mark_lowclusters(Agraph_t * root)
{
    Agnode_t *n, *vn;
    Agedge_t *orig, *e;
 
    /* first, zap any previous cluster labelings */
    for (n = agfstnode(root); n; n = agnxtnode(root, n)) {
        ND_clust(n) = NULL;
        for (orig = agfstout(root, n); orig; orig = agnxtout(root, orig)) {
            if ((e = ED_to_virt(orig))) {
                while (e && ND_node_type(vn = aghead(e)) == VIRTUAL) {
                    ND_clust(vn) = NULL;
                    e = ND_out(aghead(e)).list[0];
                }
            }
        }
    }
 
    /* do the recursion */
    mark_lowcluster_basic(root);
}
 
static void mark_lowcluster_basic(Agraph_t * g)
{
    Agraph_t *clust;
    Agnode_t *n, *vn;
    Agedge_t *orig, *e;
    int c;
 
    for (c = 1; c <= GD_n_cluster(g); c++) {
        clust = GD_clust(g)[c];
        mark_lowcluster_basic(clust);
    }
    /* see what belongs to this graph that wasn't already marked */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        if (ND_clust(n) == NULL)
            ND_clust(n) = g;
        for (orig = agfstout(g, n); orig; orig = agnxtout(g, orig)) {
            if ((e = ED_to_virt(orig))) {
                while (e && ND_node_type(vn = aghead(e)) == VIRTUAL) {
                    if (ND_clust(vn) == NULL)
                        ND_clust(vn) = g;
                    e = ND_out(aghead(e)).list[0];
                }
            }
        }
    }
}