Hi Tiago, Of course I showed the impossible graph example on purpose just to see whether all the vertices are added at once or one by one. If I try to generate other graphs, the verbose changes so quickly that the only line I see is "Added 10 vertices" etc. So okay, it checks the maximum degree before proceeding. This was not immediately obvious to me from your previous message although I was expecting that. But now I have the same question: since in the initial placement the algorithm checks whether all the degrees are less than maximum possible, how is this done? For my impossible graph, would it be that the first degree sequence would be 11, 11, ..., 11, and then it would throw away the whole degree sequence and generate new one (obviously it would again generate all 11, and would never be able to build the graph)? Or would it simply generate degree for the first vertex, and unless it is less than max-possible, it would keep attempting to change it? I think it does the later (that is why verbose says "added 1 vertex"). If so, can we say that the initial degree sequence is drawn from a specified distribution? Thanks and regards, SS ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Saturday, September 5, 2020 12:56 AM, Tiago de Paula Peixoto <tiago@skewed.de> wrote:
Am 04.09.20 um 19:01 schrieb Snehal Shekatkar:
Thanks Tiago for the reply. Here is a script for generating a random regular graph as an example: def generate_rrg(n, k):
g = gt.random_graph(n, deg_sampler = lambda : k, directed = False, verbose = True, n_iter = 1000)
return g
Since verbose is True, this prints what is happening. Now when I run generate_rrg(n = 10, k = 11), the following is printed and script never stops: adding vertices: 1 of 10 (10%) This is giving me impression that the algorithm is adding one vertex at a time. Since every time added vertex has degree 11 in this case, the algorithm is not moving ahead because that will lead to multi/self edges (if my interpretation is right). The verbose message looks difficult to explain using your description. Am I missing something obvious?
In the initial placement it does indeed test if each degree is below the maximum possible before continuing. This a necessary but not sufficient condition being able to build a graph. After the initial degrees have been sampled, it proceeds as I had explained.
You're attempting to generate an impossible graph, so I don't understand what you were expecting would happen.
Best, Tiago
Tiago de Paula Peixoto tiago@skewed.de
graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool