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.

Command | Description |
---|---|

dreadnaut | command line interface to nauty graph isomorphism library |

nauty-NRswitchg | complement vertex edges |

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

nauty-amtog | read graphs in matrix format |

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

nauty-blisstog | convert files of graphs in bliss 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-cubhamg | find hamiltonian cycles in subcubic graphs |

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

nauty-delptg | delete vertices |

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-genbg | generate small bicoloured graphs |

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

nauty-geng | generate small graphs |

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-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-ranlabg | randomly relabel 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-vcolg | colour the vertices of graphs in all distinct ways |

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