Graph canonical labeling and automorphism group computation

https://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.

Version: 2.8.8

## General Commands | |

dreadnaut | command line interface to nauty graph isomorphism library |

nauty-NRswitchg | complement vertex edges |

nauty-addedgeg | add an edge in each possible way |

nauty-addptg | add additional vertices in various ways |

nauty-amtog | read graphs in matrix format |

nauty-ancestorg | removes a specified number of final vertices |

nauty-assembleg | manual page for nauty-assembleg |

nauty-biplabg | label bipartite graphs so the colour classes are contiguous |

nauty-bliss2dre | convert files of graphs in Bliss/DIMACS format to stdout in sparse6 format |

nauty-catg | concatenate files of graphs |

nauty-checks6 | check a file of graphs and optionally perform corrections |

nauty-complg | complement graphs |

nauty-converseg | converse digraphs |

nauty-copyg | convert format and select subset |

nauty-countg | count graphs according to a variety of properties |

nauty-countneg | count graphs by number of edges and/or vertices |

nauty-cubhamg | find hamiltonian cycles in subcubic graphs |

nauty-deledgeg | delete an edge in each possible way |

nauty-delptg | delete vertices |

nauty-dimacs2g | convert files of graphs in DIMACS format to stdout in sparse6 format |

nauty-directg | generate small digraphs with given underlying graph |

nauty-dretodot | read graphs and initial coloring in dreadnaut format and write in dot format |

nauty-dretog | read graphs in dreadnaut format |

nauty-edgetransg | select undirected graphs according to group action on vertices, edges and arcs |

nauty-genbg | generate small bicoloured graphs |

nauty-genbgL | generate small bicoloured graphs (L1 flavour) |

nauty-geng | generate small graphs |

nauty-gengL | generate small graphs (L1 flavour) |

nauty-genktreeg | generate k-trees |

nauty-genposetg | generate posets |

nauty-genquarticg | generate quartic graphs |

nauty-genrang | generate random graphs |

nauty-genspecialg | generate special graphs |

nauty-gentourng | generate small tournaments |

nauty-gentreeg | generate trees |

nauty-hamheuristic | try to find hamiltonian cycles in any graphs |

nauty-labelg | canonically label graphs |

nauty-linegraphg | compute the linegraphs of a file of graphs |

nauty-listg | display graphs in a variety of forms |

nauty-multig | generate small multigraphs with given underlying graph |

nauty-nbrhoodg | extract neighbourhoods of vertices |

nauty-newedgeg | create new edges from pairs of non-adjacent edges in each possible way |

nauty-pickg | select graphs according to a variety of properties |

nauty-planarg | test graphs for planarity and find embeddings or obstructions |

nauty-productg | product of two graphs (such as Cartesian product) |

nauty-ranlabg | randomly relabel graphs |

nauty-ransubg | extract random graph/digraph from a file of graphs |

nauty-shortg | remove isomorphs from a file of graphs |

nauty-showg | display graphs in a variety of forms (stand-alone subset of listg) |

nauty-subdivideg | compute the subdivision graphs of a file of graphs |

nauty-sumlines | sum lines matching specified graph formats |

nauty-twohamg | split quartic graphs into two hamiltonian cycles |

nauty-underlyingg | take the underlying undirected graphs of a file of graphs |

nauty-vcolg | colour the vertices of graphs in all distinct ways |

nauty-watercluster2 | generate small digraphs with given underlying graph (faster alternative to directg) |