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? Thanks and regards, SS Sent with ProtonMail Secure Email. ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Friday, September 4, 2020 12:44 PM, Tiago de Paula Peixoto <tiago@skewed.de> wrote:
Am 28.08.20 um 12:09 schrieb Snehal Shekatkar:
Hi Tiago, From the documentation of deg_sampler: "This function is called once per vertex, but may be called more times, if the degree sequence cannot be used to build a graph." Now suppose my deg_sampler sometimes returns values greater than N-1, and if I don't want to generate a graph with multi-edges and self-loops, such values will be discarded. But suppose for first few vertices, drawn values were less than N (and hence are accepted) and the next value is greater than N-1. Now will all the values generated so far discarded or only the last value? I feel that discarding only the last value will create a bias if I want to sample degrees from a particular probability distribution. Could you please clarify this?
What the algorithm does is to sample the degrees for all vertices first, and check if the final sequence is graphical. If it's not, then a random node is selected, and its degree is re-sampled, and the test is done again. This is repeated, until the sequence obtained is graphical.
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