next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Nauty :: Nauty

Nauty -- Interface to nauty

Description

This package interfaces many of the functions provided in the software nauty by Brendan D. McKay, available at http://cs.anu.edu.au/~bdm/nauty/. The nauty package provides very efficient methods for determining whether given graphs are isomorphic, generating all graphs with particular properties, generating random graphs, and more.

Most methods can handle graphs in either the Macaulay2 Graph type as provided by the EdgeIdeals package or as Graph6 and Sparse6 Strings as used by nauty. The purpose of this is that graphs stored as Strings are greatly more efficient than graphs stored as Graphs. It is recommended to work with Strings while using nauty provided methods and then converting to Graphs for further work (e.g., computing the chromatic number).

The theoretical underpinnings of nauty are in the paper: B. D. McKay, "Practical graph isomorphism," Congr. Numer. 30 (1981), 45--87.

Caveat

This package was designed for use with nauty version 2.4r2. It may or may not work with future versions.

The nauty software must be installed locally and the path should be known to Macaulay2, either by passing it as an argument when loading the package (e.g., loadPackage("Nauty", Configuration=>{"path"=>"/usr/local/bin/"}) ) or by editing the configuration file (~/.Macaulay2/init-Nauty.m2) to automatically include the path.

Author

Version

This documentation describes version 1.2 of Nauty.

Source code

The source code from which this documentation is derived is in the file Nauty.m2.

Exports

  • Functions and commands
    • addEdges -- creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
    • areIsomorphic -- determines whether two graphs are isomorphic
    • buildGraphFilter -- creates the appropriate filter string for use with filterGraphs and countGraphs
    • countGraphs -- counts the number of graphs in the list with given properties
    • filterGraphs -- filters graphs in a list for given properties
    • generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateGraphs -- generates the graphs on a given number of vertices
    • generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomRegularGraphs -- generates random regular graphs on a given number of vertices
    • graph6ToSparse6 -- converts a Graph6 string to a Sparse6 string
    • graphComplement -- computes the complement of a graph
    • graphToString -- converts a graph to a string in the Graph6 format
    • isPlanar -- determines if a given graph is planar
    • neighborhoodComplements -- complements the neighborhood for each vertex, individually
    • newEdges -- replaces disjoint pairs of edges by disjoint pairs of two-chains
    • relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
    • relabelGraph -- applies a canonical labeling to a graph
    • removeEdges -- creates a list of graphs obtained by removing one edge from the given graph in all possible ways
    • removeIsomorphs -- removes all isomorphs from a list of graphs
    • sparse6ToGraph6 -- converts a Sparse6 string to a Graph6 string
    • stringToEdgeIdeal -- converts a Sparse6 or Graph6 String to an edge ideal in the given polynomial ring
    • stringToGraph -- converts a Sparse6 or Graph6 String to a Graph in the given polynomial ring
  • Symbols