Блог пользователя rav.gupta

How to make a lot of random graphs (can be disconnected) for stress testing ?
Автор rav.gupta, история, 4 года назад, По-английски

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 ?

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

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

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Check this and learn to use google.

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

    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

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

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)

→ Ответить