From dd091aaa14c6057125bf752e6a2ed3d717710a19 Mon Sep 17 00:00:00 2001 From: John Ellson Date: Fri, 16 Dec 2016 22:39:39 -0500 Subject: [PATCH] adding a builtin tred to langs bindings --- .gitignore | 1 + cmd/tools/Makefile.am | 11 ++++- cmd/tools/tred2.c | 102 ++++++++++++++++++++++++++++++++++++++++++ lib/common/types.h | 3 +- lib/gvc/Makefile.am | 2 +- lib/gvc/gvc.h | 6 ++- lib/gvc/gvtool_tred.c | 79 ++++++++++++++++++++++++++++++++ tclpkg/gv/gv.cpp | 11 +++++ tclpkg/gv/gv.i | 3 ++ 9 files changed, 213 insertions(+), 5 deletions(-) create mode 100644 cmd/tools/tred2.c create mode 100644 lib/gvc/gvtool_tred.c diff --git a/.gitignore b/.gitignore index a93fdb273..7a3e26980 100644 --- a/.gitignore +++ b/.gitignore @@ -191,6 +191,7 @@ cmd/tools/mm2gv cmd/tools/nop cmd/tools/sccmap cmd/tools/tred +cmd/tools/tred2 cmd/tools/unflatten contrib/diffimg/diffimg contrib/prune/prune diff --git a/cmd/tools/Makefile.am b/cmd/tools/Makefile.am index cf98872df..4c87ab057 100644 --- a/cmd/tools/Makefile.am +++ b/cmd/tools/Makefile.am @@ -19,10 +19,10 @@ pdfdir = $(pkgdatadir)/doc/pdf noinst_HEADERS = colortbl.h convert.h mmio.h matrix_market.h \ graph_generator.h gml2gv.h gmlparse.h if ENABLE_STATIC -bin_PROGRAMS = gc gvcolor gxl2gv acyclic nop ccomps sccmap tred \ +bin_PROGRAMS = gc gvcolor gxl2gv acyclic nop ccomps sccmap tred tred2\ unflatten gvpack gvpack_static dijkstra bcomps mm2gv gvgen gml2gv gv2gml graphml2gv else -bin_PROGRAMS = gc gvcolor gxl2gv acyclic nop ccomps sccmap tred \ +bin_PROGRAMS = gc gvcolor gxl2gv acyclic nop ccomps sccmap tred tred2\ unflatten gvpack dijkstra bcomps mm2gv gvgen gml2gv gv2gml graphml2gv endif @@ -79,6 +79,13 @@ ccomps_LDADD = \ ccomps.1.pdf: $(srcdir)/ccomps.1 - @GROFF@ -Tps -man $(srcdir)/ccomps.1 | @PS2PDF@ - - >ccomps.1.pdf +tred2_SOURCES = tred2.c + +tred2_LDADD = \ + $(top_builddir)/lib/ingraphs/libingraphs_C.la \ + $(top_builddir)/lib/cgraph/libcgraph.la \ + $(top_builddir)/lib/gvc/libgvc.la + tred_SOURCES = tred.c tred_LDADD = \ diff --git a/cmd/tools/tred2.c b/cmd/tools/tred2.c new file mode 100644 index 000000000..4a9a16f8d --- /dev/null +++ b/cmd/tools/tred2.c @@ -0,0 +1,102 @@ +/* $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/ + *************************************************************************/ + + +/* + * Written by Stephen North + * Updated by Emden Gansner + */ + +/* + * reads a sequence of graphs on stdin, and writes their + * transitive reduction on stdout + */ + +#include "config.h" + +#include "gvc.h" +#include "cgraph.h" +#include + +#ifdef HAVE_UNISTD_H +#include +#endif +#include "ingraphs.h" + +#include + +char **Files; +char *CmdName; + +#ifdef WIN32 //*dependencies + #pragma comment( lib, "cgraph.lib" ) + #pragma comment( lib, "ingraphs.lib" ) + #pragma comment( lib, "gvc.lib" ) +#endif + +static char *useString = "Usage: %s [-?] \n\ + -? - print usage\n\ +If no files are specified, stdin is used\n"; + +static void usage(int v) +{ + printf(useString, CmdName); + exit(v); +} + +static void init(int argc, char *argv[]) +{ + int c; + + CmdName = argv[0]; + opterr = 0; + while ((c = getopt(argc, argv, ":")) != -1) { + switch (c) { + case '?': + if (optopt == '?') + usage(0); + else + fprintf(stderr, "%s: option -%c unrecognized - ignored\n", + CmdName, optopt); + break; + } + } + argv += optind; + argc -= optind; + + if (argc) + Files = argv; +} + +static Agraph_t *gread(FILE * fp) +{ + return agread(fp, (Agdisc_t *) 0); +} + +int main(int argc, char **argv) +{ + Agraph_t *g; + ingraph_state ig; + + init(argc, argv); + newIngraph(&ig, Files, gread); + + while ((g = nextGraph(&ig)) != 0) { + if (agisdirected(g)) + gvToolTred(g); + agclose(g); + } + + return 0; +} + diff --git a/lib/common/types.h b/lib/common/types.h index 933af78cd..8c9e0a305 100644 --- a/lib/common/types.h +++ b/lib/common/types.h @@ -406,6 +406,7 @@ typedef enum {NATIVEFONTS,PSFONTS,SVGFONTS} fontname_kind; char state; unsigned char gui_state; /* Node state for GUI ops */ boolean clustnode; + int mark; /* for tools like tred */ #ifndef DOT_ONLY unsigned char pinned; @@ -419,7 +420,7 @@ typedef enum {NATIVEFONTS,PSFONTS,SVGFONTS} fontname_kind; node_t *set; /* fast graph */ - char node_type, mark, onstack; + char node_type, onstack; char ranktype, weight_class; node_t *next, *prev; elist in, out, flat_out, flat_in, other; diff --git a/lib/gvc/Makefile.am b/lib/gvc/Makefile.am index 841c42d80..0e05f5ad1 100644 --- a/lib/gvc/Makefile.am +++ b/lib/gvc/Makefile.am @@ -34,7 +34,7 @@ pdf_DATA = gvc.3.pdf libgvc_C_la_SOURCES = gvrender.c gvlayout.c gvdevice.c gvloadimage.c \ gvcontext.c gvjobs.c gvevent.c gvplugin.c gvconfig.c \ - gvtextlayout.c gvusershape.c gvc.c + gvtool_tred.c gvtextlayout.c gvusershape.c gvc.c # gvbuffstderr.c libgvc_C_la_LIBADD = \ diff --git a/lib/gvc/gvc.h b/lib/gvc/gvc.h index c1a08a488..24cdada15 100644 --- a/lib/gvc/gvc.h +++ b/lib/gvc/gvc.h @@ -111,9 +111,13 @@ extern char** gvPluginList (GVC_t *gvc, const char* kind, int* sz, char*); * @param gvc Graphviz context to add library to * @param lib library to add */ - extern void gvAddLibrary(GVC_t *gvc, gvplugin_library_t *lib); +/** Perform a Transitive Reduction on a graph + * @param g graph to be transformed. + */ +extern void gvToolTred(graph_t *g); + #undef extern #ifdef __cplusplus diff --git a/lib/gvc/gvtool_tred.c b/lib/gvc/gvtool_tred.c new file mode 100644 index 000000000..d53e289a9 --- /dev/null +++ b/lib/gvc/gvtool_tred.c @@ -0,0 +1,79 @@ +/* $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/ + *************************************************************************/ + + +/* + * 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 +#include "cgraph.h" +#include "gvc.h" + +#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); + + ND_mark(n) = 1; + + for (e = agfstin(g, n); e; e = f) { + f = agnxtin(g, e); + if (e == link) + continue; + if (ND_mark(agtail(e))) + agdelete(g, e); + } + + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + if (ND_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); + } + + ND_mark(n) = 0; + return warn; +} + +void gvToolTred(Agraph_t * g) +{ + Agnode_t *n; + int warn = 0; + + if (agisdirected(g)) { + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + warn = dfs(n, NULL, warn); + } + } else { + fprintf(stderr, "warning: %s is not a directed graph, not attempting tred\n", + agnameof(g)); + } +} diff --git a/tclpkg/gv/gv.cpp b/tclpkg/gv/gv.cpp index 9afa2f0c3..097fc5b6b 100644 --- a/tclpkg/gv/gv.cpp +++ b/tclpkg/gv/gv.cpp @@ -947,3 +947,14 @@ bool write(Agraph_t *g, const char *filename) fclose(f); return (! err); } + +bool tred(Agraph_t *g) +{ + int err = 0; + + if (!g) + return false; + gvToolTred(g); // FIXME - gvToolTred should rteturn errors code + return (! err); +} + diff --git a/tclpkg/gv/gv.i b/tclpkg/gv/gv.i index b364ef0a3..acaf5b92b 100644 --- a/tclpkg/gv/gv.i +++ b/tclpkg/gv/gv.i @@ -238,5 +238,8 @@ extern char* renderdata(Agraph_t *g, const char *format); extern bool write(Agraph_t *g, const char *filename); extern bool write(Agraph_t *g, FILE *f); +/*** Graph transformation tools */ +extern bool tred(Agraph_t *g); + %} -- 2.40.0