Unfortunately I don’t have great suggestions for a work around. To compound matters, the problem actually exists under Linux as well but is latent. I.e. a future change in Linux could expose the same issue there.
The underlying problem is a classic treating-pointer-values-as-numbers situation, which affects iteration order. The values you get from heap-allocated pointers are not the same across executions due to things like ASLR. On Linux (and in particular under Glibc) things mostly work out because heap pointers are generally increasing for sequential allocations. We actually fixed the problem previously but the fix caused a regression in a Graphviz tool fdp and we had to revert it. I have not had a chance to debug the fdp breakage but the code looked pretty hairy.
“Why is Graphviz designed that way?” Well at the time this code was written, things like ASLR did not yet exist. Memory was precious and promiscuously passing values between pointer and int types was a common practice pre-ISO-C. One of the more senior maintainers may be able to provide further details.
Anyway, that was probably more information than you wanted to know and not particularly helpful to you. Deterministic execution is a fairly baseline property, and I’m sorry we’ve ended up in this situation where Graphviz lacks it. You may be able to achieve some determinism by disabling ASLR and friends, but be aware there are security implications to this.