I have published the implementation now HAMT and StencilArrays, maybe you can take a look at it and play around with it to see whether you can use it for your use-case.
I think it also might make sense to come up with a minimal api, that describes the inputs, building and the operations that are done on the built data structure, to basically create a benchmark where people can plugin their solution to your use-case. Maybe we could even turn it into a challenge topic.
I think doing that may have the potential that somebody finds a whole other way to approach the problem. While the gaddag seems clever, I am not completely convinced that it is actually a data structure that is well suited to how the hardware operates, but this is just a hunch that that algorithm may be a local maximum, that distracts from seeing a solution that is way better. But it is difficult for me to say whether there is anything to that hunch, would require some more in-depth research and that might just end up with no answer. So far I haven’t spent a whole lot of time on graph related problems.