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

NautyGraphs -- Interface to nauty (Graphs fork)

Description

This package provides an interface from Macaulay2 to 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 Graphs 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 instances of the class Graph. (See Comparison of Graph6 and Sparse6 formats.)

It is recommended to work with graphs represented as strings while using nauty-provided methods and then converting the graphs to instances of the class Graph for further work.

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

See also

Author

Version

This documentation describes version 1.4.3.1 of NautyGraphs.

Source code

The source code from which this documentation is derived is in the file NautyGraphs.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 (i.e., selects) 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
    • onlyPlanar -- removes non-planar graphs from a list
    • relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
    • relabelGraph -- applies a vertex invariant based refinement 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
  • Symbols