gvtool_tred.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 Stephen North
 * Updated by Emden Gansner
 * Adapted to gvToolTred(g) by John Ellson
 */
 
/*
 * performs an inplace transitive reduction on a graph
 */
 
#include "config.h"
#include <stdio.h>
#include <cgraph/cgraph.h>
#include <gvc/gvc.h>
 
typedef struct {
    Agrec_t h;
    int mark;
} Agmarknodeinfo_t;
 
#define MARK(n)  (((Agmarknodeinfo_t*)(n->base.data))->mark)
 
#define agrootof(n) ((n)->root)
 
static int dfs(Agnode_t * n, Agedge_t * link, int warn)
{
    Agedge_t *e;
    Agedge_t *f;
    Agraph_t *g = agrootof(n);
 
    MARK(n) = 1;
 
    for (e = agfstin(g, n); e; e = f) {
        f = agnxtin(g, e);
        if (e == link)
            continue;
        if (MARK(agtail(e)))
            agdelete(g, e);
    }
 
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
        if (MARK(aghead(e))) {
            if (!warn) {
                warn++;
                fprintf(stderr,
                        "warning: %s has cycle(s), transitive reduction not unique\n",
                        agnameof(g));
                fprintf(stderr, "cycle involves edge %s -> %s\n",
                        agnameof(agtail(e)), agnameof(aghead(e)));
            }
        } else
            warn = dfs(aghead(e), AGOUT2IN(e), warn);
    }
 
    MARK(n) = 0;
    return warn;
}
 
int gvToolTred(Agraph_t * g)
{
    Agnode_t *n;
    int warn = 0;
 
    if (agisdirected(g)) {
        aginit(g, AGNODE, "info", sizeof(Agmarknodeinfo_t), true);
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
            warn = dfs(n, NULL, warn);
        }
        agclean(g, AGNODE, "info");
    } else {
        fprintf(stderr, "warning: %s is not a directed graph, not attempting tred\n",
                        agnameof(g));
    }
    return 0;    // FIXME - return proper errors
}