Generating graphs

Generating graphs: 

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



A Partial List of nauty Programs:

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 





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: 

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

I/O Redirection and Piping:

program1 < file1 

program1 > file1 

program1 >> file1 

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


Relevant papers: 

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:

4. The House of Graphs:

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