The file mkgraph.c is compiled with gcc mkgraph.c -o mkgraph -lm The program is written in ANSI C. It compiles cleanly on my PC with Linux, SUN with SunOS, and DEC with Ultrix. This program creates a graph file consisting of random edge sets that conform to the options provided. The edge sets are pairs of 32-bit numbers representing nodes. This file is binary. If you request a 20 node graph that is 2% complete, you will get a 24-byte binary file that contains 3 edge sets. There is no delminator between edges in the file. The program supports three different component structures: star, chain, or random. It will also create hard graphs with the recursive function G(T,n,r). These graphs are multi-level graphs and are alternately dense and sparse on adjacent levels. There are several paragraphs describing the implementation of this function in the source code (look at function make_hard_graphs()) as comments. The program usage is: usage: mkgraph [-n nNodes] [-d Density] [-c nComponents] \ [-h DifficultyLevel] [-v VertexDegree] [-s Structure] -o File -n Number of Nodes in each Component -d Graph Density (% Complete) -c Number of Components -h DifficultyLevel (Hard): 0 <= hard <= 238 -s Structure of Graph == star | chain | random) -v Vertex Degree (for all nodes) -o Output File Defaults: nNodes: 16384 Density: 2% nComponents: 0 Hard: 0 Vertex Degree: 0 Structure: random These default values will yield 2684190 Edges. nComponents == 0 means the number of Components is undefined, but then nNodes is the number of nodes in the graph. Difficutly Level == 0 means the function G(T,n,r) is applied once. Difficutly Level > 0 represents the number of levels of recursive calls to the G(T,n,r) with each level making nComponents calls to the function G(T,n,r) as defined by Guy Blelloch. Example: mkgraph -n16384 -d2 -c0 -h0 -srandom -ograph_file Creates the default graph in the file graph_file PLEASE Note that the output files are quite large! The above default graph will be a 21Meg file. All edges are guaranteed to be unique and no self edges are generated. As you can see, the program allows setting the number of nodes, graph density, number of components, vertex (node) degree, and component structure. You can also select hard graphs, the default is easy graphs because hard graphs get large quickly.