It is a command-line program, so you should run under command prompt. It takes four parameters, only the first of which is required: the number of vertices.
rndgraph 16 minimal valid command
The generator outputs lines containing integers. The first line contains the
number of vertices in the graph; each successive line will consist of a pair of
numbers, representing an edge between those two vertices. To save random graph
data, redirect the output to a file, like this:
rndgraph 16 > graph16a
rndgraph 16 > graph16b
rndgraph 35 > graph35
The file graph16a will then contain random graph data for a 16 node graph,
graph16b will contain a different 16 node graph, and graph35 will hold a 35 node
graph. Alternatively, you may be able to "pipe" its output directly into your
program:
rndgraph 16 | mybiconnectedcomponentsmasterpiece
rndgraph 16 | mybiconnectedcomponentsmasterpiece
will run your program on two different 16 node graphs.
The optional parameters provide additional control over the generated graphs,
which may be useful for your debugging and for your timing study. In more
detail, the 4 parameters are:
1. n: Number of vertices. Integer 1. Required.
2. d: The expected degree of the graph (average number of edges connected
to each vertex). Integer 0. Optional; if zero or omitted, defaults to 5. You
may want to set it to a smaller number for initial debugging, and you definitely
need to set it to a range of larger values, up to about n, for your timing
study.
3. seed: Seed for the pseudo-random number generator. Integer between 1
and 2^32. Optional; if zero or omitted, defaults to the system time-of-day
clock. Computers (hopefully!) never generate random numbers, but they can
generate sequences that appear random for most practical purposes. You get a
different sequence for each seed, and successive numbers in the sequence will
appear unrelated, but if you restart with the same seed, you'll get the same
sequence. Why does it matter? Debugging! If your program is crashing on some
rare graph, it is important to be able to regenerate exactly the same graph,
which is practically impossible with the default. After you get your program
debugged, using the default is a great way to generate lots of different
examples for your timing study, but until then I strongly recommend that you use
explicit seeds, e.g.:
rndgraph 16 0 42 | mybiconnectedcomponentsmasterpiece
rndgraph 16 0 42 | mybiconnectedcomponentsmasterpiece
rndgraph 16 0 0 | mybiconnectedcomponentsmasterpiece
rndgraph 16 0 0 | mybiconnectedcomponentsmasterpiece
will run your program on the same 16 node graph twice, then on two different
(and basically unrepeatable) ones.
4. shuffle: A flag indicating whether vertex numbers should be
randomized. Integer 0 or 1. Optional; if omitted, defaults to 1 (meaning "Yes,
randomize"). If 0, the generator uses consecutive numbers for most vertices in
the same biconnected component. If 1, node numbers are (pseudo-) randomly
assigned. Using 0 may be convenient for your initial debugging, but your later
testing and timing runs should use 1 (the default).
Thus, the following command:
rndgraph 99 50 42 1 > savegraph-99-50-42-1
will generate (and save to a file) a graph with 99 vertices and average degree
of 50, with shuffled node numbers, all based on the specific pseudo-random
sequence with seed 42. The sample graph shown near the top of this page was
produced by
rndgraph 8 2 3 0
8 nodes, degree about 2, no label shuffle, seed 3. Try it; you should get the
same graph with those parameters, namely:
8
0 1
0 2
1 2
2 7
3 4
3 7
4 5
4 6
5 6
5 7
6 7