Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] acoa_v1_0.gz(8 Kbytes)
Manuscript Title: Computer generation of connected graphs.
Authors: D.C. Rapaport
Program title: GRAFFITI
Catalogue identifier: ACOA_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 8(1974)320
Programming language: Fortran.
Computer: IBM 360/50.
Operating system: HASP/OS/MFT.
RAM: 20K words
Word size: 32
Peripherals: disc.
Keywords: General purpose, Statistical mechanics, Cluster expansions, Cooperative phenomena, Critical exponents, Diagramatic expansions, Ferromagnetism, Series expansions, Ising model, Lattice statistics, Perturbation theory, Phase transitions.
Classification: 4.4.

Nature of problem:
The most successful technique currently used in studying the behaviour of magnetic spin models (e.g. the Ising model) near their phase transitions is the series expansion method. Generation of the coefficients of these expansions requires the availability of a list of suitable graphs, the type of graph required depending on the quantity being expanded. The computer program described here generates the connected graphs used in a study of the Ising model with impurities. Graphs required for other kinds of perturbation expansion in statistical mechanics, quantum electro-dynamics, or many-body theory, can either be obtained from this list of connected graphs, or generated directly using appropriately modified versions of the program.

Solution method:
Graphs are generated iteratively in order of increasing edge and vertex numbers by adding additional edges to already existing graphs. The problem is to do this efficiently and, because most graphs can be generated in more than one way, to ensure that the graph in the final list are all distinct. The degree of overgeneration is reduced by taking into account the graph symmetry, and the problem of determining whether or not graphs are distinct is overcome by developing a canonical labelling scheme for the graphs.

The maximum graph size is set by the array dimensions and the scheme used in packing the graph adjacency matrices. Both are easily altered. The real limitation is execution time due to the rapid increase in graph numbers as more edges are added.

Running time:
709 graphs with 7 vertices and 6 to 13 edges were generated in approx. 500 s, and 834 graphs with 8 vertices and 7 to 10 edges in approx. 1000 s on the IBM 360/50 computer.