From 4fabbd29d54d4db97b205fa25e7efe3f9e24259a Mon Sep 17 00:00:00 2001 From: erg Date: Thu, 28 May 2009 03:40:02 +0000 Subject: [PATCH] Add nested node layout --- lib/Makefile.am | 2 +- lib/osage/Makefile.am | 26 ++ lib/osage/osage.h | 31 ++ lib/osage/osageinit.c | 404 ++++++++++++++++++++ plugin/neato_layout/Makefile.am | 1 + plugin/neato_layout/gvlayout_neato_layout.c | 9 + 6 files changed, 472 insertions(+), 1 deletion(-) create mode 100644 lib/osage/Makefile.am create mode 100644 lib/osage/osage.h create mode 100644 lib/osage/osageinit.c diff --git a/lib/Makefile.am b/lib/Makefile.am index 25c87518c..92c981e7a 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -4,6 +4,6 @@ SUBDIRS = cdt graph cgraph gd pathplan sfio vmalloc ast \ vpsc rbtree ortho sparse patchwork expr common \ pack gvc xdot ingraphs topfish glcomp \ - circogen dotgen fdpgen neatogen twopigen sfdpgen + circogen dotgen fdpgen neatogen twopigen sfdpgen osage EXTRA_DIST = Makefile.old gvc.vcproj gvc.def diff --git a/lib/osage/Makefile.am b/lib/osage/Makefile.am new file mode 100644 index 000000000..94dd0a81f --- /dev/null +++ b/lib/osage/Makefile.am @@ -0,0 +1,26 @@ +# $Id$Revision$ +## Process this file with automake to produce Makefile.in + +if WITH_CGRAPH +GRAPH = cgraph +else +GRAPH = graph +endif + +AM_CPPFLAGS = \ + -I$(top_srcdir) \ + -I$(top_srcdir)/lib/common \ + -I$(top_srcdir)/lib/gvc \ + -I$(top_srcdir)/lib/neatogen \ + -I$(top_srcdir)/lib/fdpgen \ + -I$(top_srcdir)/lib/pack \ + -I$(top_srcdir)/lib/pathplan \ + -I$(top_srcdir)/lib/sparse \ + -I$(top_srcdir)/lib/$(GRAPH) \ + -I$(top_srcdir)/lib/cdt + +noinst_HEADERS = osage.h +noinst_LTLIBRARIES = libosage_C.la + +libosage_C_la_SOURCES = osageinit.c + diff --git a/lib/osage/osage.h b/lib/osage/osage.h new file mode 100644 index 000000000..066d45938 --- /dev/null +++ b/lib/osage/osage.h @@ -0,0 +1,31 @@ +/* vim:set shiftwidth=4 ts=8: */ + +/********************************************************** +* This software is part of the graphviz package * +* http://www.graphviz.org/ * +* * +* Copyright (c) 1994-2004 AT&T Corp. * +* and is licensed under the * +* Common Public License, Version 1.0 * +* by AT&T Corp. * +* * +* Information and Software Systems Research * +* AT&T Research, Florham Park NJ * +**********************************************************/ + +#ifndef CLUSTER_H +#define CLUSTER_H + +#include "render.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern void cluster_layout(Agraph_t * g); +extern void cluster_cleanup(Agraph_t * g); + +#ifdef __cplusplus +} +#endif +#endif diff --git a/lib/osage/osageinit.c b/lib/osage/osageinit.c new file mode 100644 index 000000000..1e2df4c8c --- /dev/null +++ b/lib/osage/osageinit.c @@ -0,0 +1,404 @@ +/* vim:set shiftwidth=4 ts=8: */ + +/********************************************************** +* This software is part of the graphviz package * +* http://www.graphviz.org/ * +* * +* Copyright (c) 1994-2004 AT&T Corp. * +* and is licensed under the * +* Common Public License, Version 1.0 * +* by AT&T Corp. * +* * +* Information and Software Systems Research * +* AT&T Research, Florham Park NJ * +**********************************************************/ + + +/* FIX: handle cluster labels */ +/* + * Written by Emden R. Gansner + */ + +#include "osage.h" +#include "neatoprocs.h" +#include "pack.h" + +#define CL_CHUNK 10 +#define DFLT_SZ 18 +#define PARENT(n) ((Agraph_t*)ND_alg(n)) + +static void +indent (int i) +{ + for (; i > 0; i--) + fputs (" ", stderr); +} + +typedef struct { + Agraph_t** cl; + int sz; + int cnt; +} clist_t; + +static void initCList(clist_t * clist) +{ + clist->cl = 0; + clist->sz = 0; + clist->cnt = 0; +} + +/* addCluster: + * Append a new cluster to the list. + * NOTE: cl[0] is empty. The clusters are in cl[1..cnt]. + * Normally, we increase the array when cnt == sz. + * The test for cnt > sz is necessary for the first time. + */ +static void addCluster(clist_t * clist, graph_t * subg) +{ + clist->cnt++; + if (clist->cnt >= clist->sz) { + clist->sz += CL_CHUNK; + clist->cl = RALLOC(clist->sz, clist->cl, graph_t *); + } + clist->cl[clist->cnt] = subg; +} + +static void cluster_init_graph(graph_t * g) +{ + Agnode_t *n; + Agedge_t *e; + + setEdgeType (g, ET_LINE); + Ndim = GD_ndim(g)=2; /* The algorithm only makes sense in 2D */ + + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + neato_init_node (n); + } + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + common_init_edge(e); + } + } +} + +/* layout: + */ +static void +layout (Agraph_t* g, int depth) +{ + int i, j, total, nv; + int nvs = 0; /* no. of nodes in subclusters */ + Agnode_t* n; + Agraph_t* subg; + boxf* gs; + point* pts; + boxf bb, rootbb; + pointf p; + pack_info pinfo; + pack_mode pmode; + double margin; + void** children; + Agsym_t* cattr = NULL; + Agsym_t* vattr = NULL; + Agraph_t* root = g->root; + + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "layout %s\n", g->name); + } + + /* Lay out subclusters */ + for (i = 1; i <= GD_n_cluster(g); i++) { + subg = GD_clust(g)[i]; + layout (subg, depth+1); + nvs += agnnodes (subg); + } + + nv = agnnodes(g); + total = (nv - nvs) + GD_n_cluster(g); + + if ((total == 0) && (GD_label(g) == NULL)) { + GD_bb(g).LL.x = GD_bb(g).LL.y = 0; + GD_bb(g).UR.x = GD_bb(g).UR.y = DFLT_SZ; + return; + } + + pmode = getPackInfo(g, l_array, DFLT_MARGIN, &pinfo); + if (pmode < l_graph) pinfo.mode = l_graph; + + /* add user sort values if necessary */ + if ((pinfo.mode == l_array) && (pinfo.flags & PK_USER_VALS)) { + cattr = agfindattr(root, "sortv"); + vattr = agfindattr(root->proto->n, "sortv"); + if (cattr || vattr) + pinfo.vals = N_NEW(total, unsigned char); + else + agerr (AGWARN, "Graph %s has array packing with user values but no \"sortv\" attributes are defined.", + g->name); + } + + gs = N_NEW(total, boxf); + children = N_NEW(total, void*); + j = 0; + for (i = 1; i <= GD_n_cluster(g); i++) { + subg = GD_clust(g)[i]; + gs[j] = GD_bb(subg); + if (pinfo.vals && cattr) { + pinfo.vals[j] = late_int (subg, cattr, 0, 0); + } + children[j++] = subg; + } + + if (nv-nvs > 0) { + for (n = agfstnode (g); n; n = agnxtnode (g,n)) { + if (ND_alg(n)) continue; + ND_alg(n) = g; + bb.LL.y = bb.LL.x = 0; + bb.UR.x = ND_xsize(n); + bb.UR.y = ND_ysize(n); + gs[j] = bb; + if (pinfo.vals && vattr) { + pinfo.vals[j] = late_int (n, vattr, 0, 0); + } + children[j++] = n; + } + } + + /* pack rectangles */ + pts = putRects (total, gs, &pinfo); + if (pinfo.vals) { + free (pinfo.vals); + } + + rootbb.LL = pointfof(INT_MAX, INT_MAX); + rootbb.UR = pointfof(-INT_MAX, -INT_MAX); + + /* reposition children relative to GD_bb(g) */ + for (j = 0; j < total; j++) { + P2PF(pts[j],p); + bb = gs[j]; + bb.LL.x += p.x; + bb.UR.x += p.x; + bb.LL.y += p.y; + bb.UR.y += p.y; + EXPANDBB(rootbb, bb); + if (j < GD_n_cluster(g)) { + subg = (Agraph_t*)children[j]; + GD_bb(subg) = bb; + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f %f %f\n", subg->name, bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y); + } + } + else { + n = (Agnode_t*)children[j]; + ND_coord(n) = mid_pointf (bb.LL, bb.UR); + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f\n", n->name, ND_coord(n).x, ND_coord(n).y); + } + } + } + + if (GD_label(g)) { + pointf p; + double d; + + p = GD_label(g)->dimen; + if (total == 0) { + rootbb.LL.x = 0; + rootbb.LL.y = 0; + rootbb.UR.x = p.x; + rootbb.UR.y = p.y; + + } + d = p.x - (rootbb.UR.x - rootbb.LL.x); + if (d > 0) { /* height of label is added below */ + d /= 2; + rootbb.LL.x -= d; + rootbb.UR.x += d; + } + } + + if (depth > 0) + margin = pinfo.margin/2.0; + else + margin = 0; + rootbb.LL.x -= margin; + rootbb.UR.x += margin; + rootbb.LL.y -= (margin + GD_border(g)[BOTTOM_IX].y); + rootbb.UR.y += (margin + GD_border(g)[TOP_IX].y); + + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f %f %f\n", g->name, rootbb.LL.x, rootbb.LL.y, rootbb.UR.x, rootbb.UR.y); + } + + /* Translate so that rootbb.LL is origin. + * This makes the repositioning simpler; we just translate the clusters and nodes in g by + * the final bb.ll of g. + */ + for (j = 0; j < total; j++) { + if (j < GD_n_cluster(g)) { + subg = (Agraph_t*)children[j]; + bb = GD_bb(subg); + bb.LL = sub_pointf(bb.LL, rootbb.LL); + bb.UR = sub_pointf(bb.UR, rootbb.LL); + GD_bb(subg) = bb; + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f %f %f\n", subg->name, bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y); + } + } + else { + n = (Agnode_t*)children[j]; + ND_coord(n) = sub_pointf (ND_coord(n), rootbb.LL); + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f\n", n->name, ND_coord(n).x, ND_coord(n).y); + } + } + } + + rootbb.UR = sub_pointf(rootbb.UR, rootbb.LL); + rootbb.LL = sub_pointf(rootbb.LL, rootbb.LL); + GD_bb(g) = rootbb; + + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f %f %f\n", g->name, rootbb.LL.x, rootbb.LL.y, rootbb.UR.x, rootbb.UR.y); + } + + free (gs); + free (children); + free (pts); +} + +static void +reposition (Agraph_t* g, int depth) +{ + boxf sbb, bb = GD_bb(g); + Agnode_t* n; + Agraph_t* subg; + int i; + + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "reposition %s\n", g->name); + } + + /* translate nodes in g but not in a subcluster */ + if (depth) { + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + if (PARENT(n) != g) + continue; + ND_coord(n).x += bb.LL.x; + ND_coord(n).y += bb.LL.y; + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f\n", n->name, ND_coord(n).x, ND_coord(n).y); + } + } + } + + /* translate top-level clusters and recurse */ + for (i = 1; i <= GD_n_cluster(g); i++) { + subg = GD_clust(g)[i]; + if (depth) { + sbb = GD_bb(subg); + sbb.LL.x += bb.LL.x; + sbb.LL.y += bb.LL.y; + sbb.UR.x += bb.LL.x; + sbb.UR.y += bb.LL.y; + if (Verbose > 1) { + indent (depth); + fprintf (stderr, "%s : %f %f %f %f\n", subg->name, sbb.LL.x, sbb.LL.y, sbb.UR.x, sbb.UR.y); + } + GD_bb(subg) = sbb; + } + reposition (subg, depth+1); + } + +} + +static void +mkClusters (Agraph_t* g, clist_t* pclist, Agraph_t* parent) +{ + node_t* mn; + edge_t* me; + graph_t* mg; + graph_t* subg; + clist_t list; + clist_t* clist; + + if (pclist == NULL) { + clist = &list; + initCList(clist); + } + else + clist = pclist; + + mg = g->meta_node->graph; + for (me = agfstout(mg, g->meta_node); me; me = agnxtout(mg, me)) { + mn = me->head; + subg = agusergraph(mn); + if (!strncmp(subg->name, "cluster", 7)) { + do_graph_label (subg); + addCluster(clist, subg); + mkClusters(subg, NULL, subg); + } + else { + mkClusters(subg, clist, parent); + } + } + if (pclist == NULL) { + GD_n_cluster(g) = list.cnt; + if (list.cnt) + GD_clust(g) = RALLOC(list.cnt + 1, list.cl, graph_t*); + } +} + +void osage_layout(Agraph_t *g) +{ + cluster_init_graph(g); + mkClusters(g, NULL, g); + layout(g, 0); + reposition (g, 0); + + if (GD_drawing(g)->ratio_kind) { + Agnode_t* n; + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + ND_pos(n)[0] = PS2INCH(ND_coord(n).x); + ND_pos(n)[1] = PS2INCH(ND_coord(n).y); + } + spline_edges0(g); + } + else { + int et = EDGE_TYPE (g); + if (et != ET_NONE) spline_edges1(g, et); + } + dotneato_postprocess(g); +} + +static void cleanup_graphs (Agraph_t *g) +{ + graph_t *subg; + int i; + + for (i = 1; i <= GD_n_cluster(g); i++) { + subg = GD_clust(g)[i]; + free_label(GD_label(subg)); + cleanup_graphs (subg); + } + free (GD_clust(g)); +} + +void osage_cleanup(Agraph_t *g) +{ + node_t *n; + + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + gv_cleanup_node(n); + } + cleanup_graphs(g); +} diff --git a/plugin/neato_layout/Makefile.am b/plugin/neato_layout/Makefile.am index 746caf822..ceb4b522e 100644 --- a/plugin/neato_layout/Makefile.am +++ b/plugin/neato_layout/Makefile.am @@ -31,6 +31,7 @@ libgvplugin_neato_layout_C_la_LIBADD = \ $(top_builddir)/lib/neatogen/libneatogen_C.la \ $(top_builddir)/lib/twopigen/libtwopigen_C.la \ $(top_builddir)/lib/patchwork/libpatchwork_C.la \ + $(top_builddir)/lib/osage/libosage_C.la \ $(top_builddir)/lib/fdpgen/libfdpgen_C.la \ $(top_builddir)/lib/sparse/libsparse_C.la \ $(top_builddir)/lib/rbtree/librbtree_C.la \ diff --git a/plugin/neato_layout/gvlayout_neato_layout.c b/plugin/neato_layout/gvlayout_neato_layout.c index f6dcc00b3..074f9d510 100644 --- a/plugin/neato_layout/gvlayout_neato_layout.c +++ b/plugin/neato_layout/gvlayout_neato_layout.c @@ -37,6 +37,7 @@ typedef enum { LAYOUT_NEATO, LAYOUT_TWOPI, LAYOUT_CIRCO, LAYOUT_PATCHWORK, + LAYOUT_CLUSTER, LAYOUT_NOP1, LAYOUT_NOP2, } layout_type; @@ -47,6 +48,7 @@ extern void sfdp_layout(graph_t * g); extern void twopi_layout(graph_t * g); extern void circo_layout(graph_t * g); extern void patchwork_layout(graph_t * g); +extern void osage_layout(graph_t * g); extern void neato_cleanup(graph_t * g); extern void fdp_cleanup(graph_t * g); @@ -54,6 +56,7 @@ extern void sfdp_cleanup(graph_t * g); extern void twopi_cleanup(graph_t * g); extern void circo_cleanup(graph_t * g); extern void patchwork_cleanup(graph_t * g); +extern void osage_cleanup(graph_t * g); static void nop1_layout(graph_t * g) { @@ -109,6 +112,11 @@ gvlayout_engine_t patchwork_engine = { patchwork_cleanup, }; +gvlayout_engine_t osage_engine = { + osage_layout, + osage_cleanup, +}; + gvlayout_features_t neatogen_features = { 0, }; @@ -122,6 +130,7 @@ gvplugin_installed_t gvlayout_neato_types[] = { {LAYOUT_TWOPI, "twopi", 0, &twopigen_engine, &neatogen_features}, {LAYOUT_CIRCO, "circo", 0, &circogen_engine, &neatogen_features}, {LAYOUT_PATCHWORK, "patchwork", 0, &patchwork_engine, &neatogen_features}, + {LAYOUT_CLUSTER, "osage", 0, &osage_engine, &neatogen_features}, {LAYOUT_NOP1, "nop", 0, &nop1gen_engine, &neatogen_features}, {LAYOUT_NOP1, "nop1", 0, &nop1gen_engine, &neatogen_features}, {LAYOUT_NOP1, "nop2", 0, &nop2gen_engine, &neatogen_features}, -- 2.40.0