Alfredo Braunstein

Is this what you proposed in https://github.com/JuliaGraphs/Graphs.jl/pull/150#issuecomment-1165968212 for n,p graphs, @simonschoelly ?

Can I do something to make this more easily reviewable? The code essentially * (undirected case) samples a $p$-sparse binary vector of size $\binom{N}{2}$ and then maps it into the...

> Sorry for the latency, and thanks for the contribution. @etiennedeg should we keep this one or #150? > > @abraunst what kind of tests can guarantee correctness despite the...

I've rebased

> When I benchmark against the implementation proposed by @simonschoelly in #150, I get this (only for undirected graph because simon's code seems broken for directed graphs): > > ```julia...

> > EDIT: the problem most likely is that SimpleGraphFromIterator is slow because it cannot preallocate memory for the adjacency lists and just push!es, requiring three or four allocations per...

> When removing the `SimpleGraphFromIterator` call (and replacing it by an empty graph), I get > > ``` > 1.550 ms (4314 allocations: 174.41 KiB) > 25.122 ms (64000 allocations:...

> The biggest advantage of Simon's is that the neighbors are already sorted, so it is much less costly to build the adjacency lists. No matter what, with this approach,...

> Simon's, but replacing the call to `_sample_with_replacement!` by `randsubseq!`, so does not improve. > > ``` > 217.053 μs (504 allocations: 77.73 KiB) > 3.721 ms (504 allocations: 1.02...

> There is a gotcha in your implementation, the adjacency lists are not sorted... (This is a requirement for `SimpleGraph`). So you indeed have to pay more to sort the...