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


/* comp.c:
 * Written by Emden R. Gansner
 *
 * Support for "connected components". Components are either connected
 * or have a port node or have a pinned node.
 *
 */

/* use PRIVATE interface */
#define FDP_PRIVATE 1

#include <cgraph/cgraph.h>
#include <fdpgen/fdp.h>
#include <fdpgen/comp.h>
#include <pack/pack.h>
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/bitarray.h>
#include <util/prisize_t.h>

static void dfs(Agraph_t *g, Agnode_t *n, Agraph_t *out, bitarray_t *marks) {
    Agedge_t *e;
    Agnode_t *other;

    bitarray_set(marks, ND_id(n), true);
    agsubnode(out,n,1);
    for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
	if ((other = agtail(e)) == n)
	    other = aghead(e);
	if (!bitarray_get(*marks, ND_id(other)))
	    dfs(g, other, out, marks);
    }
}

/* findCComp:
 * Finds generalized connected components of graph g.
 * This merges all components containing a port node or a pinned node.
 * Assumes nodes have unique id's in range [0,agnnodes(g)-1].
 * Components are stored as subgraphs of g, with name sg_<i>.
 * Returns 0-terminated array of components.
 * If cnt is non-0, count of components is stored there.
 * If pinned is non-0, *pinned is set to 1 if there are pinned nodes.
 * Note that if ports and/or pinned nodes exists, they will all be
 * in the first component returned by findCComp.
 */
static size_t C_cnt = 0;
graph_t **findCComp(graph_t *g, size_t *cnt, int *pinned) {
    node_t *n;
    graph_t *subg;
    agxbuf name = {0};
    size_t c_cnt = 0;
    bport_t *pp;
    graph_t **comps;
    graph_t **cp;
    int pinflag = 0;

    assert(agnnodes(g) >= 0);
    bitarray_t marks = bitarray_new((size_t)agnnodes(g));

    /* Create component based on port nodes */
    subg = 0;
    if ((pp = PORTS(g))) {
	agxbprint(&name, "cc%s_%" PRISIZE_T, agnameof(g), c_cnt++ + C_cnt);
	subg = agsubg(g, agxbuse(&name), 1);
	agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
	GD_alg(subg) = gv_alloc(sizeof(gdata));
	PORTS(subg) = pp;
	NPORTS(subg) = NPORTS(g);
	for (; pp->n; pp++) {
	    if (bitarray_get(marks, ND_id(pp->n)))
		continue;
	    dfs(g, pp->n, subg, &marks);
	}
    }

    /* Create/extend component based on pinned nodes */
    /* Note that ports cannot be pinned */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	if (bitarray_get(marks, ND_id(n)))
	    continue;
	if (ND_pinned(n) != P_PIN)
	    continue;
	if (!subg) {
	    agxbprint(&name, "cc%s_%" PRISIZE_T, agnameof(g), c_cnt++ + C_cnt);
	    subg = agsubg(g, agxbuse(&name), 1);
		agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
	    GD_alg(subg) = gv_alloc(sizeof(gdata));
	}
	pinflag = 1;
	dfs(g, n, subg, &marks);
    }
    if (subg)
	(void)graphviz_node_induce(subg, NULL);

    /* Pick up remaining components */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	if (bitarray_get(marks, ND_id(n)))
	    continue;
	agxbprint(&name, "cc%s+%" PRISIZE_T, agnameof(g), c_cnt++ + C_cnt);
	subg = agsubg(g, agxbuse(&name), 1);
	agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);	//node custom data
	GD_alg(subg) = gv_alloc(sizeof(gdata));
	dfs(g, n, subg, &marks);
	(void)graphviz_node_induce(subg, NULL);
    }
    bitarray_reset(&marks);
    agxbfree(&name);
    C_cnt += c_cnt;

    if (cnt)
	*cnt = c_cnt;
    if (pinned)
	*pinned = pinflag;
    /* freed in layout */
    comps = cp = gv_calloc(c_cnt + 1, sizeof(graph_t*));
    for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
	*cp++ = subg;
	c_cnt--;
    }
    assert(c_cnt == 0);
    *cp = 0;

    return comps;
}