From 9c773513d5f99538b7ad7ddc83e174ddcc134937 Mon Sep 17 00:00:00 2001 From: Emden Gansner Date: Thu, 10 Nov 2011 15:19:23 -0500 Subject: [PATCH] Supply code to use the new ranking algorithm. This is only available via cgraph. At present, it is conditional on setting the graph attribute newrank=true. --- lib/dotgen/cluster.c | 3 +- lib/dotgen/dotinit.c | 48 +++++++++++++++++++++++++++++++- lib/dotgen/mincross.c | 64 ++++++++++++++++++++++++++++++++++++++++++- lib/dotgen/rank.c | 10 ++----- 4 files changed, 115 insertions(+), 10 deletions(-) diff --git a/lib/dotgen/cluster.c b/lib/dotgen/cluster.c index d2f2155f7..84021a20f 100644 --- a/lib/dotgen/cluster.c +++ b/lib/dotgen/cluster.c @@ -231,7 +231,8 @@ void interclexp(graph_t * subg) continue; } -#ifndef WITH_NEW_RANK +/* This assertion is still valid if the new ranking is not used */ +#ifndef WITH_CGRAPH assert(ED_to_virt(e) != NULL); #endif diff --git a/lib/dotgen/dotinit.c b/lib/dotgen/dotinit.c index b891b5ff1..85e845506 100644 --- a/lib/dotgen/dotinit.c +++ b/lib/dotgen/dotinit.c @@ -280,6 +280,49 @@ setAspect (Agraph_t * g, aspect_t* adata) return adata; } +static void +remove_from_rank (Agraph_t * g, Agnode_t* n) +{ + Agnode_t* v = NULL; + int j, rk = ND_rank(n); + + for (j = 0; j < GD_rank(g)[rk].n; j++) { + v = GD_rank(g)[rk].v[j]; + if (v == n) { + for (j++; j < GD_rank(g)[rk].n; j++) { + GD_rank(g)[rk].v[j-1] = GD_rank(g)[rk].v[j]; + } + GD_rank(g)[rk].n--; + break; + } + } + assert (v == n); /* if found */ +} + +/* removeFill: + * This removes all of the fill nodes added in mincross. + * It appears to be sufficient to remove them only from the + * rank array and fast node list of the root graph. + */ +static void +removeFill (Agraph_t * g) +{ + Agnode_t* n; + Agnode_t* nxt; + Agraph_t* sg = agsubg (g, "_new_rank", 0); + + if (!sg) return; + for (n = agfstnode(sg); n; n = nxt) { + nxt = agnxtnode(sg, n); + delete_fast_node (g, n); + remove_from_rank (g, n); + dot_cleanup_node (n); + agdelnode(g, n); + } + agdelsubg (g, sg); + +} + void dot_layout(Agraph_t * g) { aspect_t aspect; @@ -305,7 +348,10 @@ void dot_layout(Agraph_t * g) dot_position(g, asp); aspect.nPasses--; } while (aspect.nextIter && aspect.nPasses); - +#ifdef WITH_CGRAPH + if (GD_flags(g) & NEW_RANK) + removeFill (g); +#endif dot_sameports(g); dot_splines(g); if (mapbool(agget(g, "compound"))) diff --git a/lib/dotgen/mincross.c b/lib/dotgen/mincross.c index 3d9327c31..421c340af 100644 --- a/lib/dotgen/mincross.c +++ b/lib/dotgen/mincross.c @@ -39,7 +39,6 @@ static void init_mccomp(graph_t * g, int c); static void cleanup2(graph_t * g, int nc); static int mincross_clust(graph_t * par, graph_t * g, int); static int mincross(graph_t * g, int startpass, int endpass, int); -static void init_mincross(graph_t * g); static void mincross_step(graph_t * g, int pass); static void mincross_options(graph_t * g); static void save_best(graph_t * g); @@ -857,6 +856,67 @@ void rec_reset_vlists(graph_t * g) } } +/* realFillRanks: + * The structures in crossing minimization and positioning require + * that clusters have some node on each rank. This function recursively + * guarantees this property. It takes into account nodes and edges in + * a cluster, the latter causing dummy nodes for intervening ranks. + * For any rank without node, we create a real node of small size. This + * is stored in the subgraph sg, for easy removal later. + * + * I believe it is not necessary to do this for the root graph, as these + * are laid out one component at a time and these will necessarily have a + * node on each rank from source to sink levels. + */ +static Agraph_t* +realFillRanks (Agraph_t* g, int rnks[], int rnks_sz, Agraph_t* sg) +{ + int i, c; + Agedge_t* e; + Agnode_t* n; + + for (c = 1; c <= GD_n_cluster(g); c++) + sg = realFillRanks (GD_clust(g)[c], rnks, rnks_sz, sg); + + if (agroot(g) == g) + return sg; + memset (rnks, 0, sizeof(int)*rnks_sz); + for (n = agfstnode(g); n; n = agnxtnode(g,n)) { + rnks[ND_rank(n)] = 1; + for (e = agfstout(g,n); e; e = agnxtout(g,e)) { + for (i = ND_rank(n)+1; i <= ND_rank(aghead(e)); i++) + rnks[i] = 1; + } + } + for (i = GD_minrank(g); i <= GD_maxrank(g); i++) { + if (rnks[i] == 0) { + if (!sg) { + sg = agsubg (agroot(g), "_new_rank", 1); + } + n = agnode (sg, NULL, 1); + agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); + ND_rank(n) = i; + ND_lw(n) = ND_rw(n) = 0.5; + ND_ht(n) = 1; + ND_UF_size(n) = 1; + alloc_elist(4, ND_in(n)); + alloc_elist(4, ND_out(n)); + agsubnode (g, n, 1); + } + } + return sg; +} + +static void +fillRanks (Agraph_t* g) +{ + Agraph_t* sg; + int rnks_sz = GD_maxrank(g) + 2; + int* rnks = N_NEW(rnks_sz, int); + sg = realFillRanks (g, rnks, rnks_sz, NULL); + free (rnks); +} + static void init_mincross(graph_t * g) { int size; @@ -873,6 +933,8 @@ static void init_mincross(graph_t * g) TE_list = N_NEW(size, edge_t *); TI_list = N_NEW(size, int); mincross_options(g); + if (GD_flags(g) & NEW_RANK) + fillRanks (g); class2(g); decompose(g, 1); allocate_ranks(g); diff --git a/lib/dotgen/rank.c b/lib/dotgen/rank.c index 6b289c508..796ae8f57 100644 --- a/lib/dotgen/rank.c +++ b/lib/dotgen/rank.c @@ -29,9 +29,7 @@ #include "dot.h" static void dot1_rank(graph_t * g, aspect_t* asp); -#ifdef WITH_NEW_RANK static void dot2_rank(graph_t * g, aspect_t* asp); -#endif static void renewlist(elist * L) @@ -607,11 +605,11 @@ static void dot1_rank(graph_t * g, aspect_t* asp) void dot_rank(graph_t * g, aspect_t* asp) { -#ifdef WITH_NEW_RANK - if (agget (g, "newrank")) + if (agget (g, "newrank")) { + GD_flags(g) |= NEW_RANK; dot2_rank (g, asp); + } else -#endif dot1_rank (g, asp); } @@ -685,7 +683,6 @@ collapse_leaves(graph_t * g) } #endif -#ifdef WITH_NEW_RANK /* new ranking code: * Allows more constraints * Copy of level.c in dotgen2 @@ -1247,4 +1244,3 @@ void dot2_rank(graph_t * g, aspect_t* asp) /* end of new ranking code */ -#endif /* WITH_NEW_RANK */ -- 2.40.0