zeldris's blog

By zeldris, history, 4 weeks ago, In English,

Hello,

I need to build a connected graph with 1e5 vertices and 4e5 edges, but when I try to create using rand () I can not get such a graph. can anybody help me?

P.S. the edges must be different.

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Maybe you can build a tree first: for i=2 to n link(i,rand()%(i-1)+1) (1-index) and then use another permutation of [1,n] to replace the original index.

After building the tree,add some arbitary edges. if you do not want to get repeated edges,use hash or map to check.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    Getting all graphs with the same probability (that is, getting the uniform distribution) could be desirable. I guess you can use Prüfer codes if you just want a random tree on n vertices. Even in this case, Wilson's algorithm for generating a spanning tree of a graph G uniformly at random is reasonably efficient.

    Example: What should be the probability of getting a 4-vertex star (that is, a tree with 3 leaves and a vertex of degree 3)? There are nn - 2 labeled trees (Cayley), and n of those are stars because you can only choose the central vertex, so for n = 4 the correct probability is 4 / 44 - 2 = 1 / 4.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thanks

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

By the way, there exists extrimely convinient library jngen for these needs and similar.