next up previous contents index CD CD Algorithms
Next: Calendrical Calculations Up: Combinatorial Problems Previous: Generating Partitions

Generating Graphs



Input description: Parameters describing the desired graph, such as the number of vertices n, the number of edges m, or the edge probability p.

Problem description: Generate (1) all or (2) a random or (3) the next graph satisfying the parameters.

Discussion: Graph generation typically arises in constructing test data for programs.   Perhaps you have two different programs that solve the same problem, and you want to see which one is faster or make sure that they always give the same answer.   Another application is experimental graph theory, verifying whether a particular property is true for all graphs or how often it is true.   It is much easier to conjecture the four-color theorem once you have demonstrated 4-colorings for all planar graphs on 15 vertices.

A different application of graph generation arises in network design.   Suppose you need to design a network linking ten machines using as few cables as possible, such that the network can survive up to two vertex failures. One approach is to test all the networks with a given number of edges until you find one that will work. For larger graphs, more heuristic approaches, like simulated annealing, will likely be necessary.

Many factors complicate the problem of generating graphs. First, make sure you know what you want to generate:

Which of these options best models your application? Probably none of them. Random graphs, by definition, have very little structure. In most applications, graphs are used to model relationships, which are often highly structured. Experiments conducted on random graphs, although interesting and easy to perform, often fail to capture what you are looking for.

An alternative to random graphs is to use ``organic'' graphs, graphs that reflect the relationships among real-world objects.     The Stanford GraphBase, discussed below, is an outstanding source of organic graphs. Further, there are many raw sources of relationships electronically available via the Internet that can be turned into interesting organic graphs with a little programming and imagination.   Consider the graph defined by a set of WWW pages, with any hyperlink between two pages defining an edge.   Or what about the graph implicit in railroad, subway, or airline networks, with vertices being stations and edges between two stations connected by direct service?   As a final example, every large computer program defines a call graph, where the vertices represent subroutines, and there is an edge (x,y) if x calls y.

Two special classes of graphs have generation algorithms that have proven particularly useful in practice:

Implementations: The Stanford GraphBase [Knu94]   is perhaps most useful as an instance generator for constructing a wide variety of graphs to serve as test data for other programs. It incorporates graphs derived from interactions of characters in famous novels, Roget's Thesaurus, the Mona Lisa, expander graphs, and the economy of the United States. It also contains routines for generating binary trees, graph products, line graphs, and other operations on basic graphs.   Finally, because of its machine-independent random number generators, it provides a way to construct random graphs such that they can be reconstructed elsewhere, thus making them perfect for experimental comparisons of algorithms. See Section gif for additional information.        

Combinatorica [Ski90] provides Mathematica generators for basic graphs such as stars, wheels, complete graphs, random graphs and trees, and graphs with a given degree sequence.     Further, it includes operations to construct more interesting graphs from these, including join, product, and line graph.   Graffiti [Faj87], a collection of almost 200 graphs of graph-theoretic interest, are available in Combinatorica format. See Section gif.

The graph isomorphism testing program nauty (see Section gif),     by Brendan D. McKay of the Australian National University, has been used to generate catalogs of all nonisomorphic graphs with up to 11 vertices.   This extension to nauty, named makeg, can be obtained by anonymous ftp from ( in the directory pub/nauty19.

Nijenhuis and Wilf [NW78] provide efficient Fortran routines to enumerate all labeled trees via Prüfer codes and to construct random unlabeled rooted trees. See Section gif.     A collection of generators for standard families of graphs is included with LEDA (see Section gif).

Notes: An extensive literature exists on generating graphs uniformly at random. Surveys include [Gol93, Tin90]. Closely related to the problem of generating classes of graphs is counting them.   Harary and Palmer [HP73] survey results in graphical enumeration.

Random graph theory is concerned with the properties of random graphs. Threshold laws in random graph theory define the edge density at which properties such as connectedness become highly likely to occur.   Expositions on random graph theory include [ES74, Pal85].

An integer partition is graphic if there exists a simple graph with that degree sequence.     Erdős and Gallai [EG60] proved that a degree sequence is graphic if and only if the sequence observes the following condition for each integer r < n:


The bijection between n-2 strings and labeled trees is due to Prüfer [Prü18].   Good expositions on this result include [Eve79a, NW78].

Related Problems: Generating permutations (see page gif), graph isomorphism (see page gif).    

next up previous contents index CD CD Algorithms
Next: Calendrical Calculations Up: Combinatorial Problems Previous: Generating Partitions

Mon Jun 2 23:33:50 EDT 1997