text.mod/graphviz.mod/graphviz/cmd/tools/bcomps.c

/**
 * @file
 * @brief biconnected components filter for graphs
 */

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


/*
 * Generate biconnected components
 *
 * Written by Emden Gansner
 */
#include "config.h"

#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <getopt.h>

#include <stdlib.h>
#include <cgraph/cgraph.h>
#include <cgraph/gv_math.h>
#include <cgraph/ingraphs.h>
#include <cgraph/list.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/unreachable.h>

typedef struct {
    Agrec_t h;
    Agraph_t *next;
} Agraphinfo_t;

typedef struct {
    Agrec_t h;
} Agedgeinfo_t;

typedef struct {
    Agrec_t h;
    int low;
    int val;
    int isCut;
} Agnodeinfo_t;

#define Low(n)  (((Agnodeinfo_t*)(n->base.data))->low)
#define Cut(n)  (((Agnodeinfo_t*)(n->base.data))->isCut)
#define N(n)  (((Agnodeinfo_t*)(n->base.data))->val)
#define NEXTBLK(g)  (((Agraphinfo_t*)(g->base.data))->next)

char **Files;
int verbose;
int silent;
char *outfile = 0;
char *path = 0;
char *suffix = 0;
int external;			/* emit blocks as root graphs */
int doTree;			/* emit block-cutpoint tree */

DEFINE_LIST(edge_stack, Agedge_t *)

typedef struct {
    int count;
    int nComp;
    edge_stack_t stk;
    Agraph_t *blks;
} bcstate;

static char *blockName(agxbuf *xb, char *gname, int d) {
    if (*gname == '%') /* anonymous graph */
	agxbprint(xb, "_%s_bcc_%d", gname, d);
    else
	agxbprint(xb, "%s_bcc_%d", gname, d);
    return agxbuse(xb);
}

/* getName:
 * Generate name for output using input template.
 * Has form path_<g>_<i>.suffix, for ith write for the gth graph.
 * If isTree, use path_<g>_t.suffix.
 * If sufcnt is zero and graph 0, use outfile
 */
static char *getName(int ng, int nb)
{
    agxbuf name = {0};

    if (ng == 0 && nb == 0)
	agxbput(&name, outfile);
    else {
	if (suffix) {
	    if (nb < 0)
		agxbprint(&name, "%s_%d_T.%s", path, ng, suffix);
	    else
		agxbprint(&name, "%s_%d_%d.%s", path, ng, nb, suffix);
	} else {
	    if (nb < 0)
		agxbprint(&name, "%s_%d_T", path, ng);
	    else
		agxbprint(&name, "%s_%d_%d", path, ng, nb);
	}
    }
    return agxbdisown(&name);
}

static void gwrite(Agraph_t * g, int ng, int nb)
{
    FILE *outf;
    char *name;

    if (silent)
	return;
    if (!outfile) {
	agwrite(g, stdout);
	fflush(stdout);
    } else {
	name = getName(ng, nb);
	outf = fopen(name, "w");
	if (!outf) {
	    fprintf(stderr, "Could not open %s for writing\n", name);
	    perror("bcomps");
	    free(name);
	    graphviz_exit(1);
	}
	free(name);
	agwrite(g, outf);
	fclose(outf);
    }
}

static Agraph_t *mkBlock(Agraph_t * g, bcstate * stp)
{
    Agraph_t *sg;

    stp->nComp++;
    agxbuf xb = {0};
    sg = agsubg(g, blockName(&xb, agnameof(g), stp->nComp), 1);
    agxbfree(&xb);
    agbindrec(sg, "info", sizeof(Agraphinfo_t), true);
    NEXTBLK(sg) = stp->blks;
    stp->blks = sg;
    return sg;
}

static void
dfs(Agraph_t * g, Agnode_t * u, bcstate * stp, Agnode_t * parent)
{
    Agnode_t *v;
    Agedge_t *e;
    Agedge_t *ep;
    Agraph_t *sg;

    stp->count++;
    Low(u) = N(u) = stp->count;
    for (e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) {
	if ((v = aghead(e)) == u)
	    v = agtail(e);
	if (v == u)
	    continue;
	if (N(v) == 0) {
	    edge_stack_push_back(&stp->stk, e);
	    dfs(g, v, stp, u);
	    Low(u) = imin(Low(u), Low(v));
	    if (Low(v) >= N(u)) {	/* u is an articulation point */
		Cut(u) = 1;
		sg = mkBlock(g, stp);
		do {
		    ep = edge_stack_pop_back(&stp->stk);
		    agsubnode(sg, aghead(ep), 1);
		    agsubnode(sg, agtail(ep), 1);
		} while (ep != e);
	    }
	} else if (parent != v) {
	    Low(u) = imin(Low(u), N(v));
	    if (N(v) < N(u))
		edge_stack_push_back(&stp->stk, e);
	}
    }
}

static void addCutPts(Agraph_t * tree, Agraph_t * blk)
{
    Agnode_t *n;
    Agnode_t *bn;
    Agnode_t *cn;

    bn = agnode(tree, agnameof(blk), 1);
    for (n = agfstnode(blk); n; n = agnxtnode(blk, n)) {
	if (Cut(n)) {
	    cn = agnode(tree, agnameof(n), 1);
	    agedge(tree, bn, cn, 0, 1);
	}
    }
}

static int process(Agraph_t * g, int gcnt)
{
    Agnode_t *n;
    bcstate state;
    Agraph_t *blk;
    Agraph_t *tree;
    int bcnt;

    aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), true);
    aginit(g, AGEDGE, "info", sizeof(Agedgeinfo_t), true);
    aginit(g, AGRAPH, "info", sizeof(Agraphinfo_t), true);

    state.count = 0;
    state.nComp = 0;
    state.stk = (edge_stack_t){0};
    state.blks = 0;

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	if (N(n) == 0)
	    dfs(g, n, &state, 0);
    }
    for (blk = state.blks; blk; blk = NEXTBLK(blk)) {
	(void)graphviz_node_induce(blk, g);
    }
    if (external) {
	bcnt = 0;
	for (blk = state.blks; blk; blk = NEXTBLK(blk)) {
	    gwrite(blk, gcnt, bcnt++);
	}
    } else
	gwrite(g, gcnt, 0);
    if (doTree) {
	tree = agopen("blkcut_tree", Agstrictundirected, 0);
	for (blk = state.blks; blk; blk = NEXTBLK(blk))
	    addCutPts(tree, blk);
	gwrite(tree, gcnt, -1);
	agclose(tree);
    }
    if (verbose) {
	int cuts = 0;
	bcnt = 0;
	for (blk = state.blks; blk; blk = NEXTBLK(blk))
	    bcnt++;
	for (n = agfstnode(g); n; n = agnxtnode(g, n))
	    if (Cut(n))
		cuts++;
	fprintf(stderr, "%s: %d blocks %d cutpoints\n", agnameof(g), bcnt,
		cuts);
    }
    edge_stack_free(&state.stk);
    if (state.blks && NEXTBLK(state.blks))
	return 1;		/* >= 2 blocks */
    else
	return 0;
}

static char *useString =
    "Usage: bcomps [-stvx?] [-o<out template>] <files>\n\
  -o - output file template\n\
  -s - don't print components\n\
  -t - emit block-cutpoint tree\n\
  -v - verbose\n\
  -x - external\n\
  -? - print usage\n\
If no files are specified, stdin is used\n";

static void usage(int v)
{
    printf("%s",useString);
    graphviz_exit(v);
}

static void split(char *name)
{
    char *sfx = 0;

    sfx = strrchr(name, '.');
    if (sfx) {
	size_t size = (size_t)(sfx - name);
	suffix = sfx + 1;
	path = gv_strndup(name, size);
    } else {
	path = name;
    }
}

static void init(int argc, char *argv[])
{
    int c;

    opterr = 0;
    while ((c = getopt(argc, argv, ":o:xstv?")) != -1) {
	switch (c) {
	case 'o':
	    outfile = optarg;
	    split(outfile);
	    break;
	case 's':
	    verbose = 1;
	    silent = 1;
	    break;
	case 'v':
	    verbose = 1;
	    break;
	case 't':
	    doTree = 1;
	    break;
	case 'x':
	    external = 1;
	    break;
	case ':':
	    fprintf(stderr, "bcomps: option -%c missing argument - ignored\n", optopt);
	    break;
	case '?':
	    if (optopt == '\0' || optopt == '?')
		usage(0);
	    else {
		fprintf(stderr,
			"bcomps: option -%c unrecognized\n", optopt);
		usage(1);
	    }
	    break;
	default:
	    UNREACHABLE();
	}
    }
    argv += optind;
    argc -= optind;

    if (argc > 0)
	Files = argv;
}

int main(int argc, char *argv[])
{
    Agraph_t *g;
    ingraph_state ig;
    int r = 0;
    int gcnt = 0;

    init(argc, argv);
    newIngraph(&ig, Files);

    while ((g = nextGraph(&ig)) != 0) {
	r |= process(g, gcnt);
	agclose(g);
	gcnt++;
    }

    graphviz_exit(r);
}