OmaeWaMouShenDeiru's blog

Graph random test case generation
By OmaeWaMouShenDeiru, history, 9 years ago, In English

Hey,

What is the concept behind graph problems test case generation.

How can I write a random test case generator ?

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

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You can use Spoj-Toolkit

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

Do you need connected graph?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

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".

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

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is fast and efficient https://test-case-generator.herokuapp.com/

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was a great help. I used it for years, but now it's gone. Any other tools like that?

    → Reply