graph formats

graph6 and sparse6 are formats for storing undirected graphs in a compact manner, using only printable ASCII characters. Files in these formats have text type and contain one line per graph.

graph6 is suitable for small graphs, or large dense graphs. sparse6 is more space-efficient for large sparse graphs.

digraph6 is a similar format for directed graphs.

If you really want the formal definition of these formats, the details are available here.

Using files in graph6, sparse6 or digraph6 format

The gtools package that comes with nauty contains many programs for manipulating graphs in these formats. However, there is also a stand-alone reader showg which can convert them into many other formats, including some good for human consumption.

showg is available as a program written in a portable subset of C: showg.c.
We also provide some ready-made executables. Note that a command line interface is required for showg to be used properly.
Linux 32-bit
Linux 64-bit
Macintosh 64-bit (see below)
Windows 32-bit (doesn't know digraphs)
Windows 64-bit
If you can help to make more of these, please contact me.

Mac notes: Depending on how you downloaded showg_mac64 you will probably need to run chmod +x showg_mac64. If you then get a message like "cannot be opened because the developer cannot be verified", try this: xattr -d -r com.apple.quarantine showg_mac64.

Using showg

Brief instructions for using showg can be obtained by entering showg -help:

Usage: showg [-p#:#l#o#Ftq] [-a|-A|-c|-d|-e] [infile [outfile]]

 Write graphs in human-readable format.

   infile is the input file in graph6, sparse6 or digraph6 format
     This program does not support incremental sparse6 files; use listg.
   outfile is the output file
   Defaults are standard input and standard output.

    -p#, -p#:#, -p#-# : only display one graph or a sequence of
          graphs.  The first graph is number 1.  A second number
          which is empty or zero means infinity.

    -a  : write the adjacency matrix
    -A  : same as -a with a space between entries
    -d  : write output to satisfy dreadnaut
    -c  : write compact dreadnaut form with minimal line-breaks
    -e  : write a list of edges, preceded by the order and the
          number of edges

    -o# : specify number of first vertex (default is 0)
    -t  : write upper triangle only (affects -a, -A, -d and default)
    -F  : write a form-feed after each graph except the last
    -l# : specify screen width limit (default 78, 0 means no limit)
          This is not currently implemented with -a or -A.
    -q  : suppress auxiliary output

    -a, -A, -c, -d and -e are incompatible.

We will give an example. The regular graphs of order 8 and degree 2 look like this in graph6 format:

G?r@`_
G?qa`_
GCQR@O

Suppose you have them in a file called reg82.g6 (right click to download). Here are some of your options:
List of neighbours: showg reg82.g6  output
List of edges: showg -e reg82.g6  output
The same starting the numbering at 1: showg -eo1 reg82.g6  output
Adjacency matrix: showg -a reg82.g6  output
Only the upper triangle: showg -ta reg82.g6  output
The same, less verbosely: showg -taq reg82.g6  output
The same, just the first two graphs: showg -tap1:2 reg82.g6  output

The options can be concatenated as in the examples, or given separately.
"-tap1:2" is the same as "-t -a -p1:2".

Other information

In these graph formats, each graph occupies one text line. Therefore you can manipulate them using any of your system tools for text files, such as sorting, concatenating, etc.. However, one gotcha exists for operations that use comparison between lines, such as sorting. Modern sort programs usually compare characters according to local collation rules. In Unix-like systems this is called the locale and you can get unexpected results that are even as strange as having two different lines comparing equal. To avoid this, specify the "C" locale, which will request character comparison by binary value. In bash, this can be done using export LC_COLLATE=C. However, note that if the variable LC_ALL is defined, it takes precedence over LC_COLLATE.

 


Page Master: Brendan McKay, brendan.mckay@anu.edu.au