TikZ graphdrawing differences between LuaTeX versions

What I will describe below is not yet a problem but will appear when TeX Live 2019 is released and LuaTeX will be upgraded to 1.09. MikTeX users might already experience this issue. It also affects users of Mac OS X, because the random number generator of their C standard library is different from the one of glibc.

When I typeset one of the graphdrawing examples from the TikZ manual, it appears mirrored between the LuaTeX versions 1.07 (TeX Live 2018) and 1.09 (TeX Live 2019). Why is that happening?

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{decorations.pathmorphing,graphs,graphdrawing}
\usegdlibrary{force}
\begin{document}
\tikz [spring electrical layout, node distance=1.3cm,
every edge/.style={
decoration={coil, aspect=-.5, post length=1mm,
segment length=1mm, pre length=2mm},
decorate, draw}]
{
\foreach \i in {1,...,6}
\node (node \i) [fill=blue!50, text=white, circle] {\i};

\draw (node 1) edge (node 2)
(node 2) edge (node 3)
edge (node 4)
(node 3) edge (node 4)
edge (node 5)
edge (node 6);
}
\end{document}


On the left is LuaTeX 1.07, on the right LuaTeX 1.09:

The problem with random numbers

The issue you are experiencing stems from the fact that the Lua version which is bundled with LuaTeX was upgraded. LuaTeX 1.07 uses Lua 5.2, whereas LuaTeX 1.09 uses Lua 5.3. This has some peculiar implications.

The force-based graphdrawing algorithms set up the vertices in a random configuration to start with. Then the system is annealed to find the optimal configuration of the nodes. To avoid getting stuck in a local minimum or at a saddle point, small random forces are added in each iteration.

As you may have noticed in the previous paragraph, the word “random” appears a couple of times. That means that the algorithm is quite sensitive to the choice of random numbers. However, between versions 5.2 and 5.3, Lua changed its default random number generator (RNG). While Lua 5.2 used the C standard library rand() function, Lua 5.3 uses the POSIX random() function. Therefore you get entirely different random numbers even with the same seed. I believe this issue is localized to POSIX-compatible platforms, like Linux or Mac OS X.

$lua5.2 -e "math.randomseed(42); print(math.random())" 0.32996420763897$ lua5.3 -e "math.randomseed(42); print(math.random())"
0.32996420748532


This does not mean that your graphs will be entirely different because the distribution of the random numbers stays the same (uniform distribution), only their sequence is different. That is also why the graphs still look so similar and only appear mirrored.

Luckily this issue is entirely localized to the spring electrical layout, because no other graph drawing algorithm uses random numbers.

Mitigations

Implementation of glibc's rand() in pure Lua

Another option would be to reimplement the Lua 5.2 random number generator in Lua 5.3. This is of course not a good option and should be avoided, but in principle it is possible.

The pure C and Lua implementations can be found in my GitHub Gist.

\documentclass{article}
\usepackage{luacode}
\begin{luacode*}

local ok, bit32 = pcall(require, "bit32")
if not ok then
ok, bit32 = pcall(require, "bit")
end
if not ok then
error("No bitwise operations available")
end

if _VERSION == "Lua 5.3" or type(jit) == "table" then
if (bit32.bxor(b,0x0) == 0) then
return a
end
end

local r = {}

local ffffffff = bit32.bnot(0x00000000)
local RAND_MAX = 2147483647

local i = 0
local rand = function()
i = i % 344 + 1
r[i] = add(r[(i - 32 + 344) % 344 + 1], r[(i - 4 + 344) % 344 + 1])
local r = bit32.rshift(bit32.band(r[i], ffffffff), 1)
return r
end

local srand = function(seed)
-- can't seed with 0
if seed == 0 then
seed = 1
end

r = seed
for i = 2, 31 do
--[[ (from stdlib/random_r.c) This does:
r[i] = (16807 * r[i - 1]) % 2147483647;
but avoids overflowing 31 bits. ]]
local hi = math.floor(r[i - 1] / 127773)
local lo = r[i - 1] % 127773
r[i] = bit32.band(16807 * lo - 2836 * hi, ffffffff)
end
for i = 32, 34 do
r[i] = r[i-31]
end
for i = 35, 344 do
end
end

function math.random(l,u)
local r = rand() / RAND_MAX
if l and u then -- lower and upper limits
assert(l <= u, "interval is empty")
return math.floor(r*(u-l+1)) + l
elseif l then -- only upper limit
assert(1.0 <= u, "interval is empty")
return math.floor(r*u) + 1.0
else -- no arguments
return r
end
end

function math.randomseed(seed)
if seed < 0 then
srand(math.floor(seed))
else
srand(math.ceil(seed))
end
rand() -- discard first value to avoid undesirable correlations
end

-- the default seed is 1
srand(1)
end

\end{luacode*}
\usepackage{tikz}
\usetikzlibrary{decorations.pathmorphing,graphs,graphdrawing}
\usegdlibrary{force}
\begin{document}
\tikz [spring electrical layout, node distance=1.3cm,
every edge/.style={
decoration={coil, aspect=-.5, post length=1mm,
segment length=1mm, pre length=2mm},
decorate, draw}]
{
\foreach \i in {1,...,6}
\node (node \i) [fill=blue!50, text=white, circle] {\i};

\draw (node 1) edge (node 2)
(node 2) edge (node 3)
edge (node 4)
(node 3) edge (node 4)
edge (node 5)
edge (node 6);
}
\end{document}


This image will still not be exactly the same. The coil between 3 and 4 will have a different number of windings but I have no idea where this comes from. These might be artifacts of numerical imprecision due to Lua 5.3 introducing an integer datatype.

Foreign Function Interface

Another alternative is to redefine the random number generator using the rand() and srand() functions by accessing them through the Foreign Function Interface (FFI). This however requires --shell-escape. To save some space I only present the chunk that would go in the luacode environment of the previous example instead.

local ffi = assert(require("ffi"))

ffi.cdef[[
int rand();
void srand(unsigned seed);
]]

if _VERSION == "Lua 5.3" then
local RAND_MAX = 2^31 - 1

function math.random(l,u)
local r = ffi.C.rand() / RAND_MAX
if l and u then -- lower and upper limits
assert(l <= u, "interval is empty")
return math.floor(r*(u-l+1)) + l
elseif l then -- only upper limit
assert(1.0 <= u, "interval is empty")
return math.floor(r*u) + 1.0
else -- no arguments
return r
end
end

function math.randomseed(seed)
if seed < 0 then
ffi.C.srand(math.floor(seed))
else
ffi.C.srand(math.ceil(seed))
end
ffi.C.rand() -- discard first value to avoid undesirable correlations
end
end


Twiddling the numbers

If you look at the source code for how Lua 5.2 and Lua 5.3 obtain the random numbers, you'll see that they look pretty similar:

// Lua 5.2
lua_Number r = (lua_Number)(rand()%RAND_MAX) / (lua_Number)RAND_MAX;
// Lua 5.3
double r = (double)l_rand() * (1.0 / ((double)L_RANDMAX + 1.0));


If rand() and l_rand() returned the same numbers, then the result would only differ by the factor they are multiplied by. In other words, you could obtain the result of Lua 5.2 from the one in Lua 5.3 by simple multiplication:

r52 = r53 * (RAND_MAX + 1.0) / RAND_MAX


Then we can simply hook into the math.random function and twiddle the numbers like that. To save some space I only present the chunk that would go in the luacode environment of the first example instead.

if _VERSION == "Lua 5.3" then
local RAND_MAX = 2^31 - 1
local random = math.random
function math.random(l,u)
local r = random() * (RAND_MAX + 1.0) / RAND_MAX
if l and u then -- lower and upper limits
assert(l <= u, "interval is empty")
return math.floor(r*(u-l+1)) + l
elseif l then -- only upper limit
assert(1.0 <= u, "interval is empty")
return math.floor(r*u) + 1.0
else -- no arguments
return r
end
end
end


On my platform this actually works because in glibc, rand() is only an alias for random(), but I don't think this can be relied on, especially on the BSDs.

• In lua 5.3, posix random() is used if defined LUA_USE_LINUX or defined LUA_USE_MACOSX. Otherwise rand() is used. Here on windows, I obtain LuaTeX 1.07 result in this example by LuaTeX 1.09 with lua-5.3. I changed an argument x in math.random as math.floor(x) to avoid an error in the present base package. – Akira Kakuto Jan 4 at 4:44
• @AkiraKakuto That's a good point. On the BSDs it will probably also look different because they implement a different rand() in the standard library. Here for example OpenBSD: github.com/openbsd/src/blob/… – Henri Menke Jan 4 at 5:02
• I have updated pgf today. I obtain luatex 1.09 result shown here in luatex 1.09 on windows, except that 5 and 6 are reversed. – Akira Kakuto Jan 5 at 23:23
• If I use on windows #define l_rand() genrand_int31() #define l_srand(x) init_genrand(abs(x-1)) #define L_RANDMAX 0x7fffffff by using mt19937ar.c in (math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html), the 1.09 result became the same as shown above. The tikz-feynman example also became OK. The change of seed was necessary to obtain desired figure for the tikz-feynman example. – Akira Kakuto Jan 6 at 5:22
• Now that XeTeX will support \(pdf)uniformdeviate primitive as other engines, it could be possible to use this RNG which certainly has smaller seed space than the one from glibc, but this does not seem very important here for graph drawing algorithms. LaTeX3 has a (int and float) wrapper which addresses some issues with the way the engine primitive produces random integers (based on Knuth MetaPost RNG) and xint has another wrapper for the same aim. As per xint, this is still WIP as I have not finalized my views on this. My algorithm for boosting the uniformity is not the same as Bruno's. – user4686 Jan 9 at 13:20