]> granicus.if.org Git - graphviz/commit
fix computation of minimum graph rank on large graphs
authorMatthew Fernandez <matthew.fernandez@gmail.com>
Fri, 2 Apr 2021 00:02:19 +0000 (17:02 -0700)
committerMatthew Fernandez <matthew.fernandez@gmail.com>
Thu, 8 Apr 2021 00:42:25 +0000 (17:42 -0700)
commit580fa88477fa59aca01e405c986c686ceee21b5f
tree4ba2b595637788f7cc44d88b9968c405b99bc31f
parentd6075962c1c0338a19dbbf381ad17c1c8df504e7
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
lib/dotgen/rank.c