rav.gupta's blog

How to make a lot of random graphs (can be disconnected) for stress testing ?
By rav.gupta, history, 4 years ago, In English

I watched a video of Errichto about stress testing [Youtube link (https://www.youtube.com/watch?v=JXTVOyQpSGM) It is very helpful if you want to stress test your solution but it lacks making random graphs(can be connected or disconnected) so you can check your graph theory solutions before submitting. Does anyone knows how to do it ?

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Got one solution of

Start with 1 node. Add a node and link it randomly to one or more nodes that are there already. (This ensures connected) and explicitly add an extra edge between two connected nodes to make one cycle, (repeat last part for more cycles).

And if you want more than one connected component you can call it more than once

→ Reply
»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Check this and learn to use google.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Thanks and I will but I asked for an algorithm and this requires using a library that I can't use in on-site contests

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Generate a tree: generate 1 node, then repeatedly generate next node and random parent. permute nodes (cyclic shift) so that we do not have small nodes on top.

generate a connected graph: generate a tree and randomly add edges

generate a disconnected graph: add a bunch if random sized connected graphs

caution: if making teatdata u also need more handcrafted testcase (line star etc)

→ Reply