From 580fa88477fa59aca01e405c986c686ceee21b5f Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Thu, 1 Apr 2021 17:02:19 -0700 Subject: [PATCH] fix computation of minimum graph rank on large graphs This code was using MAXSHORT as the maximum (unrealistically large) rank. That is, start out with this value and assume all nodes will rank below this so we can progressively step down. This was likely correct when the code was first written. However, 97cb5fffdcaa97eadb76a9b82a026d084a6a94d9 altered the type used for storing ranks from short to int to support larger graphs. That is, nodes in a graph are now anticipated to have ranks in excess of 32767 (on e.g. x86). This change did not update these algorithms to compensate. The effect of this is that any graph whose nodes were all ranked >32767 would be incorrectly judged to have a minimum rank of 32767. The present change fixes this by realigning this to the limit of the new ranking type. Note that this removes the last use MAXSHORT in the code base. Unfortunately we cannot easily remove its definition without breaking API because the containing header lib/common/arith.h is shipped. --- CHANGELOG.md | 1 + lib/dotgen/rank.c | 11 ++++++----- 2 files changed, 7 insertions(+), 5 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 0ca5e1b8c..164bf50f1 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -21,6 +21,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - reference counted strings put the HTML bit in the middle of the reference count #1984 - &amp; escape disappearing #797 +- miscalculation of minimum rank on large graphs ## [2.47.0] - 2021-03-15 diff --git a/lib/dotgen/rank.c b/lib/dotgen/rank.c index 9ab55d545..d10dfa8ee 100644 --- a/lib/dotgen/rank.c +++ b/lib/dotgen/rank.c @@ -24,6 +24,7 @@ */ #include +#include static void dot1_rank(graph_t * g, aspect_t* asp); static void dot2_rank(graph_t * g, aspect_t* asp); @@ -197,7 +198,7 @@ void dot_scan_ranks(graph_t * g) { node_t *n, *leader = NULL; - GD_minrank(g) = MAXSHORT; + GD_minrank(g) = INT_MAX; GD_maxrank(g) = -1; for (n = agfstnode(g); n; n = agnxtnode(g, n)) { if (GD_maxrank(g) < ND_rank(n)) @@ -402,7 +403,7 @@ static void expand_ranksets(graph_t * g, aspect_t* asp) node_t *n, *leader; if ((n = agfstnode(g))) { - GD_minrank(g) = MAXSHORT; + GD_minrank(g) = INT_MAX; GD_maxrank(g) = -1; while (n) { leader = UF_find(n); @@ -986,7 +987,7 @@ static void setMinMax (graph_t* g, int doRoot) if (!GD_parent(g) && !doRoot) // root graph return; - GD_minrank(g) = MAXSHORT; + GD_minrank(g) = INT_MAX; GD_maxrank(g) = -1; for (n = agfstnode(g); n; n = agnxtnode(g, n)) { v = ND_rank(n); @@ -1014,13 +1015,13 @@ static void readout_levels(graph_t * g, graph_t * Xg, int ncc) int* minrk = NULL; int doRoot = 0; - GD_minrank(g) = MAXSHORT; + GD_minrank(g) = INT_MAX; GD_maxrank(g) = -1; if (ncc > 1) { int i; minrk = N_NEW(ncc+1,int); for (i = 1; i <= ncc; i++) - minrk[i] = MAXSHORT; + minrk[i] = INT_MAX; } for (n = agfstnode(g); n; n = agnxtnode(g, n)) { xn = ND_rep(find(n)); -- 2.40.0