A question about generating simple graphs in graph-tool

graph-tool
1

Dear Tiago,

I happened to be looking at the code for random graph generation
(graph_generation.hh). The code checks whether a generated degree
sequence is Graphic or not using Erdos-Gallai condition. If the
condition is not satisfied, the code seems to randomly choose a vertex
and re-generate its degree. This is logical in most cases.

However, if any of the degree value is greater than "n-1", the size of
the graph, clearly a simple graph cannot be generated from such
sequence, and it should be immediately changed by re-generating degrees
for such vertices. This happens a lot when the degrees are sampled from
a right-skewed distribution. But I don't see anything like this in the
code. My question is, isn't it inefficient to keep randomly choosing
vertices one at a time and change their degrees until the vertices with
degree greater than n-1 are reassigned degrees? Is it being done for
correctly sampling from a given degree distribution? Or am I missing
something? Thank you.

Best regards,
SMS

2

I would highly appreciate if Tiago or anyone else in this list has an
answer to my question in the trailing e-mail. Thank you.

3

This can be implemented in a trivial way simply by rejecting these large
numbers already in the `deg_sampler` function that you supply to
random_graph().