Automatic input generator

Question

I am developing Dijkstra’s minimum path calculation algorithm using the C language, I am doing several solutions to the same problem and then testing which is the most efficient.

For this I needed to generate several inputs, including gigantic entries! I wanted to know if there is an input generator or something, otherwise I will have to write an algorithm to generate directed and connected graphs and store them in a txt

Is there anything like?

Answer 1

I’m assuming you search for random entries, right? In this Wikipedia article about random graphs several different algorithms are cited to generate a graph, each with distinct properties (and distinct implementation complexity). See in "models" in the informational box on the right, in Wikipedia in English there are some other.

I don’t know of any ready implementation, but maybe you find something like this in the library LEMON (part of the project Boost) - for C++ however, not C. And anyway, you’d have to "translate" the output of any ready-made tool into the format you’re using to represent, so I don’t know what would take more work: using a ready-made tool, or implementing yourself...

Should you decide to implement yourself, the Model Erdõs-Rényi seems to be the simplest. In one of its two variants:

1. Choose a probability p between zero and one (zero: no edges; a: fully connected graph);
2. Create a graph with n us;
3. For each pair of us (a,b), whether or not to create an edge between them with probability p.

Other models produce graphs with distinct characteristics (e.g.: the Barabási-Albert generates graphs that resemble "various natural and artificial systems, including the internet, citation networks and on some social networks." Watts e Strogatz generates graphs with "short medium path and high clustering"; etc). Think about what type of input you want, and see which model fits the most (i.e. don’t try to invent an algorithm from scratch in your head, as it will hardly come out the way you want it to).

Just one more tip: if you’re using one pseudo-random number generator (PRNG) to create your graphs, you don’t need to save the entire graph to txt to reuse it after: simply store the seed of the PRNG! Thus, by saving a single number (as well as other generation parameters such as graph size, desired density, etc.) you can recreate a gigantic graph without having to store it all.

• Care: As pointed out by @pmg, it is important that you use a PRNG routine/library that remains stable in the face of updates, and not simply use what your environment/OS offers you unless your algorithm is precisely specified. The previously mentioned LEMON library, for example, has its own implementation of a PRNG, but the documentation clearly states that "this implementation specializes for both 32-bit and 64-bit architectures. The generators differ slightly in the generation and startup phase, so they produce two completely different sequences".

  That is, if you need your results to be reproducible on different platforms and Sos, it is important to seek/implement a PRNG that does not have these limitations/that offers this kind of stability.