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

Автор OmaeWaMouShenDeiru, история, 9 лет назад, По-английски

Hey,

What is the concept behind graph problems test case generation.

How can I write a random test case generator ?

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

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

You can use Spoj-Toolkit

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

Do you need connected graph?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Well, what is a graph? It's a set vertices with a set of pairs of these vertices.
Once the number of vertices and the number of edges are fixed you need just to generate several random pairs. That's it.
However, the resulting graph might be not so good for a specific problem so you may need to specialize this generation algorithm. For instance, if you need a connected graph one possible way is to generate a tree first and then add some more edges (you can see how tree can be generated in testlib examples).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you all.

    Im not looking for specific type of graphs, I want to learn a concept so I become able to generate any type of graphs any time needed.

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

Why spoj-toolkit is taking too much time to generate string/tree of size 100000,and still not generating. At bottom , it's showing "connecting to server".

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

Well, I first build a random tree using Prufer Code and then simply add random edges to that tree to convert it into Graph. Since I first built the tree using Prufer Code, the graph finally built is connected.

I don't know if this is the proper method of building graph, but for generating random trees, Prufer Code is the proper method.

More on Prufer Code.

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