Hey,

What is the concept behind graph problems test case generation.

How can I write a random test case generator ?

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | fateice | 3337 |

3 | Um_nik | 3292 |

4 | OO0OOO00O0OOO0O0…O | 3280 |

5 | Syloviaely | 3274 |

6 | Petr | 3223 |

7 | Swistakk | 3105 |

8 | mnbvmar | 3096 |

9 | yosupo | 3091 |

10 | dotorya | 3081 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 163 |

2 | tourist | 160 |

3 | csacademy | 152 |

4 | Petr | 151 |

5 | Swistakk | 148 |

6 | Um_nik | 144 |

7 | Nickolas | 142 |

7 | Vovuh | 142 |

9 | BledDest | 138 |

9 | PikMike | 138 |

9 | matthew99 | 138 |

Hey,

What is the concept behind graph problems test case generation.

How can I write a random test case generator ?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2018 20:41:51 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

You can use Spoj-Toolkit

Do you need connected graph?

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

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.

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

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.