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.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | adamant | 164 |
2 | awoo | 164 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
7 | SecondThread | 150 |
9 | orz | 146 |
10 | pajenegod | 145 |
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.
Name |
---|
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.
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.
thanks
By the way, there exists extrimely convinient library jngen for these needs and similar.
SPOJ also has a useful test case generator.