image University of Washington Computer Science & Engineering
  CSE 421,  Su '07:  Assignment #2: Random Graph Generator
  CSE Home   About Us    Search    Contact Info 

Downloads

Here is the random graph generator for use in this assignmentssignment:

Instructions

The program generates (somewhat) random graphs in such a way as to produce (hopefully) interesting examples for the project. You can see samples here. It is a command-line program, and takes four parameters, only the first of which is required: the number of vertices.

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 about 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

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX