Graph canonical labeling and automorphism group computation

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

Nauty and Traces are programs for computing automorphism groups of

graphs and digraphs. (At present, Traces does not accept 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.

nauty-addedgeg

For each edge nonedge e, output G+e if it satisfies certain conditions The output file has a header if and only if the input file does.

For each edge nonedge e, output G+e if it satisfies certain conditions The output file has a header if and only if the input file does.

nauty-biplabg

Label bipartite graphs so that the colour classes are contiguous. The first vertex of each component is assigned the first colour. Vertices in each colour class...

Label bipartite graphs so that the colour classes are contiguous. The first vertex of each component is assigned the first colour. Vertices in each colour class...

nauty-blisstog

Read files of graphs in Bliss (Dimacs) format and write them to stdout in sparse6 format.

Read files of graphs in Bliss (Dimacs) format and write them to stdout in sparse6 format.

nauty-checks6

Check a file of graphs, optionally write corrected version -p# -p#:#Specify range of input lines (first is 1)

Check a file of graphs, optionally write corrected version -p# -p#:#Specify range of input lines (first is 1)

nauty-complg

Take the complements of a file of graphs. The output file has a header if and only if the input file does. The output format is defined by the header or first...

Take the complements of a file of graphs. The output file has a header if and only if the input file does. The output format is defined by the header or first...

nauty-converseg

Take the converse digraphs of a file of graphs. The output file has a header if and only if the input file does. Undirected graphs are passed through without...

Take the converse digraphs of a file of graphs. The output file has a header if and only if the input file does. Undirected graphs are passed through without...

nauty-countg

countg : Count graphs according to their properties. pickg : Select graphs according to their properties. ifile, ofile : Input and output files. '-' and missing...

countg : Count graphs according to their properties. pickg : Select graphs according to their properties. ifile, ofile : Input and output files. '-' and missing...

nauty-cubhamg

Pick those inputs that are nonhamiltonian and have max degree <= 3. infile is the name of the input file in graph6/sparse6 format (default: stdin) outfile is...

Pick those inputs that are nonhamiltonian and have max degree <= 3. infile is the name of the input file in graph6/sparse6 format (default: stdin) outfile is...

nauty-deledgeg

For each edge e, output G-e The output file has a header if and only if the input file does.

For each edge e, output G-e The output file has a header if and only if the input file does.

nauty-delptg

Delete some vertices from a file of graphs. The output file has a header if and only if the input file does. No isomorph reduction is done.

Delete some vertices from a file of graphs. The output file has a header if and only if the input file does. No isomorph reduction is done.

nauty-directg

Read undirected graphs and orient their edges in all possible ways. Edges can be oriented in either or both directions (3 possibilities). Isomorphic directed...

Read undirected graphs and orient their edges in all possible ways. Edges can be oriented in either or both directions (3 possibilities). Isomorphic directed...

nauty-dretodot

Read graphs and initial coloring in dreadnaut format. Write graphs in dot format to outfile.dot. If outfile.dre is given, write the input graph and the...

Read graphs and initial coloring in dreadnaut format. Write graphs in dot format to outfile.dot. If outfile.dre is given, write the input graph and the...

nauty-genquarticg

generate all non-isomorphic quartic graphs of a given order n : the number of the vertices file : the name of the output file (default stdout) -u : do not...

generate all non-isomorphic quartic graphs of a given order n : the number of the vertices file : the name of the output file (default stdout) -u : do not...

nauty-hamheuristic

Apply a heuristic for finding hamiltonian cycles. Output those which are unsuccessful.

Apply a heuristic for finding hamiltonian cycles. Output those which are unsuccessful.

nauty-linegraphg

Take the linegraphs of a file of graphs. Input graphs with no edges produce only a warning message. The output file has a header if and only if the input file...

Take the linegraphs of a file of graphs. Input graphs with no edges produce only a warning message. The output file has a header if and only if the input file...

nauty-multig

[-m#] [-f#] [-D#|-r#|-l#] [infile [outfile]] Read undirected loop-free graphs and replace their edges with multiple edges in all possible ways (multiplicity at...

[-m#] [-f#] [-D#|-r#|-l#] [infile [outfile]] Read undirected loop-free graphs and replace their edges with multiple edges in all possible ways (multiplicity at...

nauty-newedgeg

For each pair of non-adjacent edges, output the graph obtained by subdividing the edges and joining the new vertices. The output file has a header if and only...

For each pair of non-adjacent edges, output the graph obtained by subdividing the edges and joining the new vertices. The output file has a header if and only...

nauty-NRswitchg

For each v, complement the edges from N(v) to V(G)-N(v)-v. The output file has a header if and only if the input file does.

For each v, complement the edges from N(v) to V(G)-N(v)-v. The output file has a header if and only if the input file does.

nauty-pickg

countg : Count graphs according to their properties. pickg : Select graphs according to their properties. ifile, ofile : Input and output files. '-' and missing...

countg : Count graphs according to their properties. pickg : Select graphs according to their properties. ifile, ofile : Input and output files. '-' and missing...

nauty-planarg

For each input, write to output if planar. The output file has a header if and only if the input file does.

For each input, write to output if planar. The output file has a header if and only if the input file does.

nauty-ranlabg

Randomly relabel graphs. The output file has a header if and only if the input file does. Each graph is written in the same format as it is read. -f# Don't...

Randomly relabel graphs. The output file has a header if and only if the input file does. Each graph is written in the same format as it is read. -f# Don't...

nauty-shortg

Remove isomorphs from a file of graphs. If outfile is omitted, it is taken to be the same as infile If both infile and outfile are omitted, input will be taken...

Remove isomorphs from a file of graphs. If outfile is omitted, it is taken to be the same as infile If both infile and outfile are omitted, input will be taken...

nauty-showg

Write graphs in human-readable format. infile is the input file in graph6 or sparse6 format outfile is the output file Defaults are standard input and standard...

Write graphs in human-readable format. infile is the input file in graph6 or sparse6 format outfile is the output file Defaults are standard input and standard...

nauty-twohamg

Partition quartic graphs into two hamiltonian cycles. Output those which cannot be partitioned.

Partition quartic graphs into two hamiltonian cycles. Output those which cannot be partitioned.

nauty-vcolg

Read undirected loop-free graphs and colour their vertices in in all possible ways with colours 0,1,2,... . Isomorphic graphs derived from the same input are...

Read undirected loop-free graphs and colour their vertices in in all possible ways with colours 0,1,2,... . Isomorphic graphs derived from the same input are...

nauty-watercluster2

Reads graphs in g6 code or multicode (optional) from stdin and directs them ix : the indegree of every vertex may be at most x. The default maximum indegree is...

Reads graphs in g6 code or multicode (optional) from stdin and directs them ix : the indegree of every vertex may be at most x. The default maximum indegree is...