gc.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
 *************************************************************************/
 
 
/*
 * Written by Emden Gansner
 */
 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#include <cgraph/cgraph.h>
#include <cgraph/cghdr.h>
#include <cgraph/ingraphs.h>
#include <cgraph/list.h>
#include <common/render.h>
#include <common/utils.h>
#include <util/exit.h>
 
typedef struct {
    Agrec_t h;
    int dfs_mark;
} nodeinfo_t;
 
#define ND_dfs_mark(n) (((nodeinfo_t*)(n->base.data))->dfs_mark)
 
#include <getopt.h>
 
#define NODES 1
#define EDGES 2
#define CC    4
#define CL    8
 
#define DIRECTED   1
#define UNDIRECTED 2
 
static int tot_edges;
static int tot_nodes;
static int tot_cc;
static int tot_cl;
static int n_graphs;
static int n_indent;
static int recurse;
static int silent;
static int verbose;
static int gtype;
static int flags;
static char *fname;
static char **Inputs;
static FILE *outfile;
 
static char *useString = "Usage: gc [-necCaDUrsv?] <files>\n\
  -n - print number of nodes\n\
  -e - print number of edges\n\
  -c - print number of connected components\n\
  -C - print number of clusters\n\
  -a - print all counts\n\
  -D - only directed graphs\n\
  -U - only undirected graphs\n\
  -r - recursively analyze subgraphs\n\
  -s - silent\n\
  -v - verbose\n\
  -? - print usage\n\
By default, gc prints nodes and edges\n\
If no files are specified, stdin is used\n";
 
static void usage(int v)
{
    printf("%s",useString);
    graphviz_exit(v);
}
 
static void init(int argc, char *argv[])
{
    int c;
 
    opterr = 0;
    while ((c = getopt(argc, argv, "necCaDUrsv?")) != -1) {
        switch (c) {
        case 'e':
            flags |= EDGES;
            break;
        case 'n':
            flags |= NODES;
            break;
        case 'c':
            flags |= CC;
            break;
        case 'C':
            flags |= CL;
            tot_cl = 0;
            break;
        case 'a':
            flags = NODES | EDGES | CC | CL;
            break;
        case 'r':
            recurse = 1;
            break;
        case 's':
            silent = 1;
            break;
        case 'v':
            verbose = 1;
            break;
        case 'D':
            gtype = DIRECTED;
            break;
        case 'U':
            gtype = UNDIRECTED;
            break;
        case '?':
            if (optopt == '\0' || optopt == '?')
                usage(0);
            else {
                fprintf(stderr, "gc: option -%c unrecognized\n",
                        optopt);
                usage(1);
            }
            break;
        default:
            fprintf(stderr, "gc: unexpected error\n");
            graphviz_exit(EXIT_FAILURE);
        }
    }
    argv += optind;
    argc -= optind;
 
    if (argc)
        Inputs = argv;
    if (flags == 0)
        flags = NODES | EDGES;
    if (gtype == 0)
        gtype = DIRECTED | UNDIRECTED;
    outfile = stdout;
}
 
DEFINE_LIST(node_stack, Agnode_t *)
static node_stack_t Stk;
 
static void push(Agnode_t * np)
{
    ND_dfs_mark(np) = -1;
    node_stack_push_back(&Stk, np);
}
 
static Agnode_t *pop(void)
{
    if (node_stack_is_empty(&Stk)) {
        return 0;
    }
    return node_stack_pop_back(&Stk);
}
 
static void cc_dfs(Agraph_t * g, Agnode_t * n)
{
    Agedge_t *e;
    Agnode_t *nxt;
 
    push(n);
    while ((n = pop())) {
        ND_dfs_mark(n) = 1;
        for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
            if (n == agtail(e))
                nxt = aghead(e);
            else
                nxt = agtail(e);
            if (ND_dfs_mark(nxt) == 0)
                push(nxt);
        }
    }
}
 
static void cntCluster(Agraph_t * g, Agobj_t * sg, void *arg)
{
    (void)g;
 
    if (AGTYPE(sg) == AGRAPH && is_a_cluster((Agraph_t *)sg))
        *(int *) (arg) += 1;
}
 
static int cc_decompose(Agraph_t * g)
{
    int c_cnt = 0;
    Agnode_t *n;
 
    c_cnt = 0;
    for (n = agfstnode(g); n; n = agnxtnode(g, n))
        ND_dfs_mark(n) = 0;
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        if (ND_dfs_mark(n))
            continue;
        c_cnt++;
        cc_dfs(g, n);
    }
 
    return c_cnt;
}
 
static void ipr(long num)
{
    printf(" %7ld", num);
}
 
static void
wcp(int nnodes, int nedges, int ncc, int ncl, char *gname, char *filename)
{
    int i;
 
    if (silent)
        return;
    for (i = 0; i < n_indent; i++)
        fputs("  ", outfile);
    if (flags & NODES)
        ipr(nnodes);
    if (flags & EDGES)
        ipr(nedges);
    if (flags & CC)
        ipr(ncc);
    if (flags & CL)
        ipr(ncl);
    if (fname)
        printf(" %s (%s)\n", gname, filename);
    else
        printf(" %s\n", gname);
}
 
static void emit(Agraph_t * g, int root, int cl_count)
{
    int n_edges = agnedges(g);
    int n_nodes = agnnodes(g);
    int n_cc = 0;
    int n_cl = 0;
    char *file = 0;
 
    if (flags & CC)
        n_cc = cc_decompose(g);
 
    if (flags & CL)
        n_cl = cl_count;
 
    if (root)
        file = fname;
    wcp(n_nodes, n_edges, n_cc, n_cl, agnameof(g), file);
 
    if (root) {
        n_graphs++;
        tot_edges += n_edges;
        tot_nodes += n_nodes;
        tot_cc += n_cc;
        tot_cl += n_cl;
    }
}
 
#define GTYPE(g) (agisdirected(g)?DIRECTED:UNDIRECTED)
 
static int eval(Agraph_t * g, int root)
{
    Agraph_t *subg;
    int cl_count = 0;
 
    if (root && !(GTYPE(g) & gtype))
        return 1;
 
    if (root) {
        aginit(g, AGNODE, "nodeinfo", sizeof(nodeinfo_t), true);
    }
 
    if ((flags & CL) && root)
        agapply(g, (Agobj_t *) g, cntCluster, &cl_count, false);
 
    emit(g, root, cl_count);
 
    if (recurse) {
        n_indent++;
        for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg))
            eval(subg, 0);
        n_indent--;
    }
    return 0;
}
 
int main(int argc, char *argv[])
{
    Agraph_t *g;
    Agraph_t *prev = NULL;
    ingraph_state ig;
    int rv = 0;
 
    init(argc, argv);
    newIngraph(&ig, Inputs);
 
    while ((g = nextGraph(&ig)) != 0) {
        if (prev)
            agclose(prev);
        prev = g;
        fname = fileName(&ig);
        if (verbose)
            fprintf(stderr, "Process graph %s in file %s\n", agnameof(g),
                    fname);
        rv |= eval(g, 1);
    }
 
    if (n_graphs > 1)
        wcp(tot_nodes, tot_edges, tot_cc, tot_cl, "total", 0);
 
    node_stack_free(&Stk);
 
    graphviz_exit(rv);
}