Gábor Csárdi

The code on that page is not too useful, actually, it is just sampling the bottom vertices with replacement, individually for each top vertex. So it potentially generates multiple edges.

But we can do a similar thing, only sampling without replacement.

Well, no, it is actually somewhat more difficult, but it can still be done, of course. One needs two partial prefix sum trees, one for bottom, one for top nodes....

This is probably not uniform sampling, though......

This is useful: http://www.uvm.edu/~pdodds/files/papers/others/1997/kannan1997.pdf

1. There are constants in the standard C lib, in `limits.h`: `INT_MAX`, `UINT_MAX`, etc. But these are not very useful for checking integer overflow, because no int can be bigger...

Yeah, that would work I think. Maybe it is a double to avoid the overflow, and the issue is older?

We can also deal with this if it comes up, I guess?

Btw. another common way to check for integer overflow for an A + B sum is to check the sum is smaller than A. If it is, that's an overflow.

The software from the paper: - Anasazi, part of a big software package - Blklan, not sure how this is relevant, but seems symmetric only - Blopex, symmetric only -...