# Generating graphs

# Generating graphs:

- Nauty and Traces:

Nauty and Traces are programs for computing automorphism groups of graphs and digraphs. They can also produce a canonical label. They are written in a portable subset of C, and run on a considerable number of different systems.There is a small suite of programs called gtools included in the package. For example, geng can generate non-isomorphic graphs very quickly. There are also generators for bipartite graphs, digraphs, and multigraphs, and programs for manipulating files of graphs in a compact format.

You can run it in Windows/Mac/Linux. For Windows users, you need to install Cygwin or MinGW / MSYS. For Mac users, you need to install Xcode.

### How to get it:

You can fetch version 2_8_6 of nauty, and version 2.2 of Traces, as a gzipped tar file (∼3.4 MB). The package uses the GNU autoconf installation system. You are advised to read the file README before compiling anything.

### Installation procedure:

tar xvzf nauty2_8_6.tar.gz

cd nauty2_8_6

./configure

make

A Partial List of nauty Programs:

geng - Generate all simple graphs of a specified class. Typing ./geng -help gives a list of usage options:

Usage: geng [-cCmtfbd\#D\#] [-uygsnh] [-lvq]} [-x\#X\#] n [mine[:maxe]] [res/mod] [file]

Generate all graphs of a specified class. n : the number of vertices

Typing ./geng 3 generates all simple graphs of order 3:

>A ./geng -d0D2 n=3 e=0-3

B?

BO

BW

Bw

Each graph generated is output on its own line in the not so human readable bit array format graph6. Lines beginning with a > character contain extra information and are printed to stderr. To view graphs in adjacency list or adjacency matrix format, we can pipe them to listg:

Graph 1, order 3.

0 : ;

1 : ;

2 : ;

Graph 2, order 3.

0 : 2;

1 : ;

2 : 0;

Also geng allows us to constrain graphs by a limited number of invariants:

./geng 5 -u - Count the graphs of order 5. No graph output.

./geng 5 0:6 - Generate all graphs of order 5 with 6 or fewer edges.

./geng 5 -c - Generate all connected graphs of order 5.

./geng 5 -b - Generate all bipartite graphs of order 5.

./geng 5 4:4 -c- Generate all trees of order 5.

./geng 6 -d3 -D3 - Generate all 3-regular graphs of order 6.

Piping geng output to pickg allows access to more invariants, like radius, diameter, and girth:

./geng 5 | ./pickg -g0 - Generate all forests.

./geng 6 | ./pickg -r - Generate all regular graphs of order 6.

./geng 5 | ./pickg -Z2 - Generate all diameter 2 graphs of order 5.

./geng 5 | ./pickg -E - Generate all Eulerian graphs of order 5.

genbg - Generate all simple bipartite graphs of a specified class.

gentourng - Generate all tournaments of a specified class.

genrang - Generate random graphs of a specified class.

labelg - Canonically label a file of graphs.

shortg - Remove isomorphs from a file of graphs.

listg and showg - Write graphs in human-readable format.

complg - Take the complements of a file of graphs.

catg - Concatenate files of graphs.

countg - Count graphs according to their properties.

pickg - Pick graphs according to their properties.

I/O Redirection and Piping:

Reading the input of a program from a file:

program1 < file1

Writing the output of a program to a file:

program1 > file1

Concatenating the output of a program to a file:

program1 >> file1

The output of a program to another program:

program1 | program2 The above operations may be combined: program1 < file1 | program2 | program3 > file2

Websites

http://cs.anu.edu.au/~bdm/nauty/

http://pallini.di.uniroma1.it/

Mailing list archives :http://dcsmail.anu.edu.au/pipermail/nauty-list/

Relevant papers:

Practical graph isomorphism I- http://cs.anu.edu.au/~bdm/nauty/pgi.pdf

Practical graph isomorphism, II - http://arxiv.org/pdf/1301.1493v1.pdf

## 2. Xcode:

Xcode is Apple’s integrated development environment. Xcode should be installed by default. To check if Xcode is installed, open the Terminal application from the Utilities folder, and type xcodebuild -version. If Xcode is not installed, you can install it from the App Store.

## 3. Cygwin:

Cygwin is not an emulator, but a collection of tools and a dll that provide Linux functionality in Windows. Installation instructions is easy as the following:

Download setup.exe from http://www.cygwin.com/.

Run setup.exe. The default settings are fine except for the Select Packages page.

On the Select Packages page, expand the Devel category, and set gcc, make, autoconf, and automake to Install.

Once installation is complete, open a Cygwn bash shell. This will create a home directory with our user name in C:\cygwin\home\.

Open the home folder in Windows and move nauty25.tar.gz there.

## 4. The House of Graphs:

It is a database of interesting graphs. You can access it via this link.