From c5d2508663a0df50fbb183e76077c45cb55019cc Mon Sep 17 00:00:00 2001 From: erg Date: Tue, 1 Feb 2011 22:29:03 +0000 Subject: [PATCH] Support ordering attribute on a per node basis --- lib/common/globals.h | 4 +- lib/common/input.c | 3 ++ lib/dotgen/mincross.c | 99 ++++++++++++++++++++++++++++--------------- lib/dotgen/rank.c | 6 +++ 4 files changed, 77 insertions(+), 35 deletions(-) diff --git a/lib/common/globals.h b/lib/common/globals.h index 0620123f1..679ad25d6 100644 --- a/lib/common/globals.h +++ b/lib/common/globals.h @@ -94,7 +94,7 @@ extern "C" { *G_selectedpencolor, *G_selectedfillcolor, *G_visitedpencolor, *G_visitedfillcolor, *G_deletedpencolor, *G_deletedfillcolor, - *G_peripheries, *G_penwidth; + *G_ordering, *G_peripheries, *G_penwidth; EXTERN attrsym_t *N_height, *N_width, *N_shape, *N_color, *N_fillcolor, *N_activepencolor, *N_activefillcolor, @@ -103,7 +103,7 @@ extern "C" { *N_deletedpencolor, *N_deletedfillcolor, *N_fontsize, *N_fontname, *N_fontcolor, *N_label, *N_xlabel, *N_nojustify, *N_style, *N_showboxes, - *N_sides, *N_peripheries, *N_orientation, + *N_sides, *N_peripheries, *N_ordering, *N_orientation, *N_skew, *N_distortion, *N_fixed, *N_imagescale, *N_layer, *N_group, *N_comment, *N_vertices, *N_z, *N_penwidth; diff --git a/lib/common/input.c b/lib/common/input.c index bf2ce61dd..8c4e23ce3 100644 --- a/lib/common/input.c +++ b/lib/common/input.c @@ -770,6 +770,8 @@ void graph_init(graph_t * g, boolean use_rankdir) Initial_dist = MYHUGE; + G_ordering = agfindgraphattr(g, "ordering"); + /* initialize nodes */ N_height = agfindnodeattr(g, "height"); N_width = agfindnodeattr(g, "width"); @@ -784,6 +786,7 @@ void graph_init(graph_t * g, boolean use_rankdir) N_xlabel = agfindnodeattr(g, "xlabel"); N_showboxes = agfindnodeattr(g, "showboxes"); N_penwidth = agfindnodeattr(g, "penwidth"); + N_ordering = agfindnodeattr(g, "ordering"); /* attribs for polygon shapes */ N_sides = agfindnodeattr(g, "sides"); N_peripheries = agfindnodeattr(g, "peripheries"); diff --git a/lib/dotgen/mincross.c b/lib/dotgen/mincross.c index 3bd144574..eb551a05c 100644 --- a/lib/dotgen/mincross.c +++ b/lib/dotgen/mincross.c @@ -144,57 +144,89 @@ static int betweenclust(edge_t * e) return (ND_clust(agtail(e)) != ND_clust(aghead(e))); } -static void do_ordering(graph_t * g, int outflag) +static void do_ordering_node (graph_t * g, node_t* n, int outflag) { int i, ne; - node_t *n, *u, *v; + node_t *u, *v; edge_t *e, *f, *fe; edge_t **sortlist = TE_list; - for (n = agfstnode(g); n; n = agnxtnode(g, n)) { - if (ND_clust(n)) - continue; + if (ND_clust(n)) + return; + if (outflag) { + for (i = ne = 0; (e = ND_out(n).list[i]); i++) + if (!betweenclust(e)) + sortlist[ne++] = e; + } else { + for (i = ne = 0; (e = ND_in(n).list[i]); i++) + if (!betweenclust(e)) + sortlist[ne++] = e; + } + if (ne <= 1) + return; + /* write null terminator at end of list. + requires +1 in TE_list alloccation */ + sortlist[ne] = 0; + qsort(sortlist, ne, sizeof(sortlist[0]), (qsort_cmpf) edgeidcmpf); + for (ne = 1; (f = sortlist[ne]); ne++) { + e = sortlist[ne - 1]; if (outflag) { - for (i = ne = 0; (e = ND_out(n).list[i]); i++) - if (!betweenclust(e)) - sortlist[ne++] = e; + u = aghead(e); + v = aghead(f); } else { - for (i = ne = 0; (e = ND_in(n).list[i]); i++) - if (!betweenclust(e)) - sortlist[ne++] = e; + u = agtail(e); + v = agtail(f); } - if (ne <= 1) - continue; - /* write null terminator at end of list. - requires +1 in TE_list alloccation */ - sortlist[ne] = 0; - qsort(sortlist, ne, sizeof(sortlist[0]), (qsort_cmpf) edgeidcmpf); - for (ne = 1; (f = sortlist[ne]); ne++) { - e = sortlist[ne - 1]; - if (outflag) { - u = aghead(e); - v = aghead(f); - } else { - u = agtail(e); - v = agtail(f); - } - if (find_flat_edge(u, v)) - continue; - fe = new_virtual_edge(u, v, NULL); - ED_edge_type(fe) = FLATORDER; - flat_edge(g, fe); + if (find_flat_edge(u, v)) + return; + fe = new_virtual_edge(u, v, NULL); + ED_edge_type(fe) = FLATORDER; + flat_edge(g, fe); + } +} + +static void do_ordering(graph_t * g, int outflag) +{ + /* Order all nodes in graph */ + node_t *n; + + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + do_ordering_node (g, n, outflag); + } +} + +static void do_ordering_for_nodes(graph_t * g) +{ + /* Order nodes which have the "ordered" attribute */ + node_t *n; + const char *ordering; + + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + if ((ordering = late_string(n, N_ordering, NULL))) { + if (streq(ordering, "out")) + do_ordering_node(g, n, TRUE); + else if (streq(ordering, "in")) + do_ordering_node(g, n, FALSE); + else if (ordering[0]) + agerr(AGERR, "ordering '%s' not recognized for node '%s'.\n", ordering, agnameof(n)); } } } /* ordered_edges: * handle case where graph specifies edge ordering + * If the graph does not have an ordering attribute, we then + * check for nodes having the attribute. + * Note that, in this implementation, the value of G_ordering + * dominates the value of N_ordering. */ static void ordered_edges(graph_t * g) { char *ordering; - if ((ordering = agget(g, "ordering"))) { + if (!G_ordering && !N_ordering) + return; + if ((ordering = late_string(g, G_ordering, NULL))) { if (streq(ordering, "out")) do_ordering(g, TRUE); else if (streq(ordering, "in")) @@ -204,8 +236,9 @@ static void ordered_edges(graph_t * g) } else { - /* search meta-graph to find subgraphs that may be ordered */ + if (N_ordering) do_ordering_for_nodes (g); #ifndef WITH_CGRAPH + /* search meta-graph to find subgraphs that may be ordered */ graph_t *mg, *subg; node_t *mm, *mn; edge_t *me; diff --git a/lib/dotgen/rank.c b/lib/dotgen/rank.c index 146ce7b27..6cf5d812d 100644 --- a/lib/dotgen/rank.c +++ b/lib/dotgen/rank.c @@ -272,7 +272,9 @@ collapse_sets(graph_t *rg, graph_t *g) { int c; graph_t *subg; +#ifdef OBSOLETE node_t *n; +#endif #ifndef WITH_CGRAPH graph_t *mg; @@ -294,10 +296,14 @@ collapse_sets(graph_t *rg, graph_t *g) } else collapse_sets(rg, subg); +#ifdef OBSOLETE + Collapsing leaves is currently obsolete + /* mark nodes with ordered edges so their leaves are not collapsed */ if (agget(subg, "ordering")) for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) ND_order(n) = 1; +#endif } } -- 2.40.0