xref: /dports/graphics/graphviz/graphviz-2.44.1/lib/dotgen/fastgr.c

/* $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 "dot.h"


/*
 * operations on the fast internal graph.
 */

static edge_t *ffe(node_t * u, elist uL, node_t * v, elist vL)
{
    int i;
    edge_t *e;

    if ((uL.size > 0) && (vL.size > 0)) {
	if (uL.size < vL.size) {
	    for (i = 0; (e = uL.list[i]); i++)
		if (aghead(e) == v)
		    break;
	} else {
	    for (i = 0; (e = vL.list[i]); i++)
		if (agtail(e) == u)
		    break;
	}
    } else
	e = 0;
    return e;
}

edge_t *find_fast_edge(node_t * u, node_t * v)
{
    return ffe(u, ND_out(u), v, ND_in(v));
}

static node_t*
find_fast_node(graph_t * g, node_t * n)
{
    node_t *v;
    for (v = GD_nlist(g); v; v = ND_next(v))
	if (v == n)
	    break;
    return v;
}

edge_t *find_flat_edge(node_t * u, node_t * v)
{
    return ffe(u, ND_flat_out(u), v, ND_flat_in(v));
}

/* safe_list_append - append e to list L only if e not already a member */
static void
safe_list_append(edge_t * e, elist * L)
{
    int i;

    for (i = 0; i < L->size; i++)
	if (e == L->list[i])
	    return;
    elist_append(e, (*L));
}

edge_t *fast_edge(edge_t * e)
{
#ifdef DEBUG
    int i;
    edge_t *f;
    for (i = 0; (f = ND_out(agtail(e)).list[i]); i++) {
	if (e == f) {
	    fprintf(stderr, "duplicate fast edge\n");
	    return 0;
	}
	assert(aghead(e) != aghead(f));
    }
    for (i = 0; (f = ND_in(aghead(e)).list[i]); i++) {
	if (e == f) {
	    fprintf(stderr, "duplicate fast edge\n");
	    return 0;
	}
	assert(agtail(e) != agtail(f));
    }
#endif
    elist_append(e, ND_out(agtail(e)));
    elist_append(e, ND_in(aghead(e)));
    return e;
}

/* zapinlist - remove e from list and fill hole with last member of list */
void zapinlist(elist * L, edge_t * e)
{
    int i;

    for (i = 0; i < L->size; i++) {
	if (L->list[i] == e) {
	    L->size--;
	    L->list[i] = L->list[L->size];
	    L->list[L->size] = NULL;
	    break;
	}
    }
}

/* disconnects e from graph */
void delete_fast_edge(edge_t * e)
{
    assert(e != NULL);
    zapinlist(&(ND_out(agtail(e))), e);
    zapinlist(&(ND_in(aghead(e))), e);
}

static void
safe_delete_fast_edge(edge_t * e)
{
    int i;
    edge_t *f;

    assert(e != NULL);
    for (i = 0; (f = ND_out(agtail(e)).list[i]); i++)
	if (f == e)
	    zapinlist(&(ND_out(agtail(e))), e);
    for (i = 0; (f = ND_in(aghead(e)).list[i]); i++)
	if (f == e)
	    zapinlist(&(ND_in(aghead(e))), e);
}

void other_edge(edge_t * e)
{
    elist_append(e, ND_other(agtail(e)));
}

void safe_other_edge(edge_t * e)
{
    safe_list_append(e, &(ND_other(agtail(e))));
}

#ifdef OBSOLETE
void
delete_other_edge(edge_t * e)
{
    assert(e != NULL);
    zapinlist(&(ND_other(agtail(e))), e);
}
#endif

/* new_virtual_edge:
 * Create and return a new virtual edge e attached to orig.
 * ED_to_orig(e) = orig
 * ED_to_virt(orig) = e if e is the first virtual edge attached.
 * orig might be an input edge, reverse of an input edge, or virtual edge
 */
edge_t *new_virtual_edge(node_t * u, node_t * v, edge_t * orig)
{
    edge_t *e;

    Agedgepair_t* e2 = NEW(Agedgepair_t);
    AGTYPE(&(e2->in)) = AGINEDGE;
    AGTYPE(&(e2->out)) = AGOUTEDGE;
    e2->out.base.data = (Agrec_t*)NEW(Agedgeinfo_t);
    e = &(e2->out);
    agtail(e) = u;
    aghead(e) = v;
    ED_edge_type(e) = VIRTUAL;

    if (orig) {
	AGSEQ(e) = AGSEQ(orig);
	AGSEQ(&(e2->in)) = AGSEQ(orig);
	ED_count(e) = ED_count(orig);
	ED_xpenalty(e) = ED_xpenalty(orig);
	ED_weight(e) = ED_weight(orig);
	ED_minlen(e) = ED_minlen(orig);
	if (agtail(e) == agtail(orig))
	    ED_tail_port(e) = ED_tail_port(orig);
	else if (agtail(e) == aghead(orig))
	    ED_tail_port(e) = ED_head_port(orig);
	if (aghead(e) == aghead(orig))
	    ED_head_port(e) = ED_head_port(orig);
	else if (aghead(e) == agtail(orig))
	    ED_head_port(e) = ED_tail_port(orig);

	if (ED_to_virt(orig) == NULL)
	    ED_to_virt(orig) = e;
	ED_to_orig(e) = orig;
    } else
	ED_minlen(e) = ED_count(e) = ED_xpenalty(e) = ED_weight(e) = 1;
    return e;
}

edge_t *virtual_edge(node_t * u, node_t * v, edge_t * orig)
{
    return fast_edge(new_virtual_edge(u, v, orig));
}

void fast_node(graph_t * g, Agnode_t * n)
{

#ifdef DEBUG
    assert(find_fast_node(g, n) == NULL);
#endif
    ND_next(n) = GD_nlist(g);
    if (ND_next(n))
	ND_prev(ND_next(n)) = n;
    GD_nlist(g) = n;
    ND_prev(n) = NULL;
    assert(n != ND_next(n));
}

void fast_nodeapp(node_t * u, node_t * v)
{
    assert(u != v);
    assert(ND_next(v) == NULL);
    ND_next(v) = ND_next(u);
    if (ND_next(u))
	ND_prev(ND_next(u)) = v;
    ND_prev(v) = u;
    ND_next(u) = v;
}

void delete_fast_node(graph_t * g, node_t * n)
{
    assert(find_fast_node(g, n));
    if (ND_next(n))
	ND_prev(ND_next(n)) = ND_prev(n);
    if (ND_prev(n))
	ND_next(ND_prev(n)) = ND_next(n);
    else
	GD_nlist(g) = ND_next(n);
}

static node_t *named_virtual_node(graph_t * g, char *s)
{
    node_t *n;

    n = NEW(node_t);
    AGTYPE(n) = AGNODE;
    n->base.data = (Agrec_t*)NEW(Agnodeinfo_t);
    n->root = agroot(g);
    ND_node_type(n) = VIRTUAL;
    ND_lw(n) = ND_rw(n) = 1;
    ND_ht(n) = 1;
    ND_UF_size(n) = 1;
    if (s) ND_alg(n) = s;
    alloc_elist(4, ND_in(n));
    alloc_elist(4, ND_out(n));
    fast_node(g, n);
    GD_n_nodes(g)++;
    return n;
}

node_t *virtual_node(graph_t * g)
{
  return named_virtual_node(g,0);
}

void flat_edge(graph_t * g, edge_t * e)
{
    elist_append(e, ND_flat_out(agtail(e)));
    elist_append(e, ND_flat_in(aghead(e)));
    GD_has_flat_edges(dot_root(g)) = GD_has_flat_edges(g) = TRUE;
}

void delete_flat_edge(edge_t * e)
{
    assert(e != NULL);
    if (ED_to_orig(e) && ED_to_virt(ED_to_orig(e)) == e)
	ED_to_virt(ED_to_orig(e)) = NULL;
    zapinlist(&(ND_flat_out(agtail(e))), e);
    zapinlist(&(ND_flat_in(aghead(e))), e);
}

#ifdef DEBUG
static char *NAME(node_t * n)
{
    static char buf[20];
    if (ND_node_type(n) == NORMAL)
	return agnameof(n);
    sprintf(buf, "V%p", n);
    return buf;
}

void fastgr(graph_t * g)
{
    int i, j;
    node_t *n, *w;
    edge_t *e, *f;

    for (n = GD_nlist(g); n; n = ND_next(n)) {
	fprintf(stderr, "%s %d: (", NAME(n), ND_rank(n));
	for (i = 0; (e = ND_out(n).list[i]); i++) {
	    fprintf(stderr, " %s:%d", NAME(aghead(e)), ED_count(e));
	    w = aghead(e);
	    if (g == agroot(g)) {
		for (j = 0; (f = ND_in(w).list[j]); j++)
		    if (e == f)
			break;
		assert(f != NULL);
	    }
	}
	fprintf(stderr, " ) (");
	for (i = 0; (e = ND_in(n).list[i]); i++) {
	    fprintf(stderr, " %s:%d", NAME(agtail(e)), ED_count(e));
	    w = agtail(e);
	    if (g == agroot(g)) {
		for (j = 0; (f = ND_out(w).list[j]); j++)
		    if (e == f)
			break;
		assert(f != NULL);
	    }
	}
	fprintf(stderr, " )\n");
    }
}
#endif

static void
basic_merge(edge_t * e, edge_t * rep)
{
    if (ED_minlen(rep) < ED_minlen(e))
	ED_minlen(rep) = ED_minlen(e);
    while (rep) {
	ED_count(rep) += ED_count(e);
	ED_xpenalty(rep) += ED_xpenalty(e);
	ED_weight(rep) += ED_weight(e);
	rep = ED_to_virt(rep);
    }
}

void
merge_oneway(edge_t * e, edge_t * rep)
{
    if (rep == ED_to_virt(e) || e == ED_to_virt(rep)) {
	agerr(AGWARN, "merge_oneway glitch\n");
	return;
    }
    assert(ED_to_virt(e) == NULL);
    ED_to_virt(e) = rep;
    basic_merge(e, rep);
}

static void
unrep(edge_t * rep, edge_t * e)
{
    ED_count(rep) -= ED_count(e);
    ED_xpenalty(rep) -= ED_xpenalty(e);
    ED_weight(rep) -= ED_weight(e);
}

void unmerge_oneway(edge_t * e)
{
    edge_t *rep, *nextrep;
    for (rep = ED_to_virt(e); rep; rep = nextrep) {
	unrep(rep, e);
	nextrep = ED_to_virt(rep);
	if (ED_count(rep) == 0)
	    safe_delete_fast_edge(rep);	/* free(rep)? */

	/* unmerge from a virtual edge chain */
	while ((ED_edge_type(rep) == VIRTUAL)
	       && (ND_node_type(aghead(rep)) == VIRTUAL)
	       && (ND_out(aghead(rep)).size == 1)) {
	    rep = ND_out(aghead(rep)).list[0];
	    unrep(rep, e);
	}
    }
    ED_to_virt(e) = NULL;
}

#ifdef OBSOLETET
static int
is_fast_node(graph_t * g, node_t * v)
{
    node_t *n;

    for (n = GD_nlist(g); n; n = ND_next(n))
	if (v == n)
	    return TRUE;
    return FALSE;
}
#endif