Блог пользователя zeldris

Generator of graphs
Автор zeldris, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    thanks

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить