Generating graphs: 

1. 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 

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.