text.mod/graphviz.mod/graphviz/lib/dotgen/class2.c

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


/* classify edges for mincross/nodepos/splines, using given ranks */

#include <dotgen/dot.h>
#include <stdbool.h>
#include <stdlib.h>
#include <util/alloc.h>

static node_t*
label_vnode(graph_t * g, edge_t * orig)
{
    node_t *v;
    pointf dimen;

    dimen = ED_label(orig)->dimen;
    v = virtual_node(g);
    ND_label(v) = ED_label(orig);
    ND_lw(v) = GD_nodesep(agroot(v));
    if (!ED_label_ontop(orig)) {
	if (GD_flip(agroot(g))) {
	    ND_ht(v) = dimen.x;
	    ND_rw(v) = dimen.y;
	} else {
	    ND_ht(v) = dimen.y;
	    ND_rw(v) = dimen.x;
	}
    }
    return v;
}

static void 
incr_width(graph_t * g, node_t * v)
{
    int width = GD_nodesep(g) / 2;
    ND_lw(v) += width;
    ND_rw(v) += width;
}

static node_t *plain_vnode(graph_t *g) {
    node_t *v;
    v = virtual_node(g);
    incr_width(g, v);
    return v;
}

static node_t *leader_of(node_t * v) {
    graph_t *clust;
    node_t *rv;

    if (ND_ranktype(v) != CLUSTER) {
	rv = UF_find(v);
    } else {
	clust = ND_clust(v);
	rv = GD_rankleader(clust)[ND_rank(v)];
    }
    return rv;
}

/* make_chain:
 * Create chain of dummy nodes for edge orig.
 */
static void 
make_chain(graph_t * g, node_t * from, node_t * to, edge_t * orig)
{
    int r, label_rank;
    node_t *u, *v;
    edge_t *e;

    u = from;
    if (ED_label(orig))
	label_rank = (ND_rank(from) + ND_rank(to)) / 2;
    else
	label_rank = -1;
    assert(ED_to_virt(orig) == NULL);
    for (r = ND_rank(from) + 1; r <= ND_rank(to); r++) {
	if (r < ND_rank(to)) {
	    if (r == label_rank)
		v = label_vnode(g, orig);
	    else
		v = plain_vnode(g);
	    ND_rank(v) = r;
	} else
	    v = to;
	e = virtual_edge(u, v, orig);
	virtual_weight(e);
	u = v;
    }
    assert(ED_to_virt(orig) != NULL);
}

static void 
interclrep(graph_t * g, edge_t * e)
{
    node_t *t, *h;
    edge_t *ve;

    t = leader_of(agtail(e));
    h = leader_of(aghead(e));
    if (ND_rank(t) > ND_rank(h)) {
	node_t *t0 = t;
	t = h;
	h = t0;
    }
    if (ND_clust(t) != ND_clust(h)) {
	if ((ve = find_fast_edge(t, h))) {
	    merge_chain(g, e, ve, true);
	    return;
	}
	if (ND_rank(t) == ND_rank(h))
	    return;
	make_chain(g, t, h, e);

	/* mark as cluster edge */
	for (ve = ED_to_virt(e); ve && ND_rank(aghead(ve)) <= ND_rank(h);
	     ve = ND_out(aghead(ve)).list[0])
	    ED_edge_type(ve) = CLUSTER_EDGE;
    }
    /* else ignore intra-cluster edges at this point */
}

static bool is_cluster_edge(edge_t *e) {
  return ND_ranktype(agtail(e)) == CLUSTER || ND_ranktype(aghead(e)) == CLUSTER;
}

void merge_chain(graph_t *g, edge_t *e, edge_t *f, bool update_count) {
    edge_t *rep;
    int lastrank = MAX(ND_rank(agtail(e)), ND_rank(aghead(e)));

    assert(ED_to_virt(e) == NULL);
    ED_to_virt(e) = f;
    rep = f;
    do {
	/* interclust multi-edges are not counted now */
	if (update_count)
	    ED_count(rep) += ED_count(e);
	ED_xpenalty(rep) += ED_xpenalty(e);
	ED_weight(rep) += ED_weight(e);
	if (ND_rank(aghead(rep)) == lastrank)
	    break;
	incr_width(g, aghead(rep));
	rep = ND_out(aghead(rep)).list[0];
    } while (rep);
}

bool mergeable(edge_t *e, edge_t *f) {
  return e && f && agtail(e) == agtail(f) && aghead(e) == aghead(f) &&
         ED_label(e) == ED_label(f) && ports_eq(e, f);
}

void class2(graph_t * g)
{
    int c;
    node_t *n, *t, *h;
    edge_t *e, *prev, *opp;

    GD_nlist(g) = NULL;

    mark_clusters(g);
    for (c = 1; c <= GD_n_cluster(g); c++)
	build_skeleton(g, GD_clust(g)[c]);
    for (n = agfstnode(g); n; n = agnxtnode(g, n))
	for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
	    if (ND_weight_class(aghead(e)) <= 2)
		ND_weight_class(aghead(e))++;
	    if (ND_weight_class(agtail(e)) <= 2)
		ND_weight_class(agtail(e))++;
	}

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	if (ND_clust(n) == NULL && n == UF_find(n)) {
	    fast_node(g, n);
	}
	prev = NULL;
	for (e = agfstout(g, n); e; e = agnxtout(g, e)) {

	    /* already processed */
	    if (ED_to_virt(e)) {
		prev = e;
		continue;
	    }

	    /* edges involving sub-clusters of g */
	    if (is_cluster_edge(e)) {
		/* following is new cluster multi-edge code */
		if (mergeable(prev, e)) {
		    if (ED_to_virt(prev)) {
			merge_chain(g, e, ED_to_virt(prev), false);
			other_edge(e);
		    } else if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
			merge_oneway(e, prev);
			other_edge(e);
		    }
		    /* else is an intra-cluster edge */
		    continue;
		}
		interclrep(g, e);
		prev = e;
		continue;
	    }
	    /* merge multi-edges */
	    if (prev && agtail(e) == agtail(prev) && aghead(e) == aghead(prev)) {
		if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
		    merge_oneway(e, prev);
		    other_edge(e);
		    continue;
		}
		if (ED_label(e) == NULL && ED_label(prev) == NULL
		    && ports_eq(e, prev)) {
		    if (Concentrate)
			ED_edge_type(e) = IGNORED;
		    else {
			merge_chain(g, e, ED_to_virt(prev), true);
			other_edge(e);
		    }
		    continue;
		}
		/* parallel edges with different labels fall through here */
	    }

	    /* self edges */
	    if (agtail(e) == aghead(e)) {
		other_edge(e);
		prev = e;
		continue;
	    }

	    t = UF_find(agtail(e));
	    h = UF_find(aghead(e));

	    /* non-leader leaf nodes */
	    if (agtail(e) != t || aghead(e) != h) {
		/* FIX need to merge stuff */
		continue;
	    }


	    /* flat edges */
	    if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
		flat_edge(g, e);
		prev = e;
		continue;
	    }

	    /* forward edges */
	    if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
		make_chain(g, agtail(e), aghead(e), e);
		prev = e;
		continue;
	    }

	    /* backward edges */
	    else {
		/* avoid when opp==e in undirected graph */
		for (opp = agfstout(g, aghead(e)); opp != NULL; opp = agnxtout(g, opp)) {
		    if (aghead(opp) != agtail(e) || aghead(opp) == aghead(e) ||
		        ED_edge_type(opp) == IGNORED) {
			continue;
		    }
		    /* shadows a forward edge */
		    if (ED_to_virt(opp) == NULL)
			make_chain(g, agtail(opp), aghead(opp), opp);
		    if (ED_label(e) == NULL && ED_label(opp) == NULL
			&& ports_eq(e, opp)) {
			if (Concentrate) {
			    ED_edge_type(e) = IGNORED;
			    ED_conc_opp_flag(opp) = true;
			} else {	/* see above.  this is getting out of hand */
			    other_edge(e);
			    merge_chain(g, e, ED_to_virt(opp), true);
			}
			break;
		    }
		}
		if (opp != NULL) {
		    continue;
		}
		make_chain(g, aghead(e), agtail(e), e);
		prev = e;
	    }
	}
    }
    /* since decompose() is not called on subgraphs */
    if (g != dot_root(g)) {
	free(GD_comp(g).list);
	GD_comp(g).list = gv_alloc(sizeof(node_t *));
	GD_comp(g).list[0] = GD_nlist(g);
    }
}