Macaulay2 » Documentation
Packages » Nauty :: Nauty
next | previous | forward | backward | up | index | toc

Nauty -- Interface to nauty

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 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 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 (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.

See also

Author

Certification a gold star

Version 1.4.1 of this package was accepted for publication in volume 3 of The Journal of Software for Algebra and Geometry: Macaulay2 on 2011-04-20, in the article Nauty in Macaulay2 (DOI: 10.2140/jsag.2011.3.1). That version can be obtained from the journal or from the Macaulay2 source code repository.

Version

This documentation describes version 1.4.3.1 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 (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 in the given polynomial ring
  • Methods
    • addEdges(Graph) -- see addEdges -- creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
    • addEdges(List) -- see addEdges -- creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
    • addEdges(String) -- see addEdges -- creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
    • areIsomorphic(Graph,Graph) -- see areIsomorphic -- determines whether two graphs are isomorphic
    • areIsomorphic(Graph,String) -- see areIsomorphic -- determines whether two graphs are isomorphic
    • areIsomorphic(String,Graph) -- see areIsomorphic -- determines whether two graphs are isomorphic
    • areIsomorphic(String,String) -- see areIsomorphic -- determines whether two graphs are isomorphic
    • Graph == Graph -- see areIsomorphic -- determines whether two graphs are isomorphic
    • Graph == String -- see areIsomorphic -- determines whether two graphs are isomorphic
    • String == Graph -- see areIsomorphic -- determines whether two graphs are isomorphic
    • buildGraphFilter(HashTable) -- see buildGraphFilter -- creates the appropriate filter string for use with filterGraphs and countGraphs
    • buildGraphFilter(List) -- see buildGraphFilter -- creates the appropriate filter string for use with filterGraphs and countGraphs
    • countGraphs(List,HashTable) -- see countGraphs -- counts the number of graphs in the list with given properties
    • countGraphs(List,List) -- see countGraphs -- counts the number of graphs in the list with given properties
    • countGraphs(List,String) -- see countGraphs -- counts the number of graphs in the list with given properties
    • filterGraphs(List,HashTable) -- see filterGraphs -- filters (i.e., selects) graphs in a list for given properties
    • filterGraphs(List,List) -- see filterGraphs -- filters (i.e., selects) graphs in a list for given properties
    • filterGraphs(List,String) -- see filterGraphs -- filters (i.e., selects) graphs in a list for given properties
    • generateBipartiteGraphs(PolynomialRing) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(PolynomialRing,ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(PolynomialRing,ZZ,ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(PolynomialRing,ZZ,ZZ,ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(ZZ,ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(ZZ,ZZ,ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateBipartiteGraphs(ZZ,ZZ,ZZ,ZZ) -- see generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
    • generateGraphs(PolynomialRing) -- see generateGraphs -- generates the graphs on a given number of vertices
    • generateGraphs(PolynomialRing,ZZ) -- see generateGraphs -- generates the graphs on a given number of vertices
    • generateGraphs(PolynomialRing,ZZ,ZZ) -- see generateGraphs -- generates the graphs on a given number of vertices
    • generateGraphs(ZZ) -- see generateGraphs -- generates the graphs on a given number of vertices
    • generateGraphs(ZZ,ZZ) -- see generateGraphs -- generates the graphs on a given number of vertices
    • generateGraphs(ZZ,ZZ,ZZ) -- see generateGraphs -- generates the graphs on a given number of vertices
    • generateRandomGraphs(PolynomialRing,ZZ) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(PolynomialRing,ZZ,QQ) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(PolynomialRing,ZZ,RR) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(PolynomialRing,ZZ,ZZ) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(ZZ,ZZ) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(ZZ,ZZ,QQ) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(ZZ,ZZ,RR) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomGraphs(ZZ,ZZ,ZZ) -- see generateRandomGraphs -- generates random graphs on a given number of vertices
    • generateRandomRegularGraphs(PolynomialRing,ZZ,ZZ) -- see generateRandomRegularGraphs -- generates random regular graphs on a given number of vertices
    • generateRandomRegularGraphs(ZZ,ZZ,ZZ) -- see generateRandomRegularGraphs -- generates random regular graphs on a given number of vertices
    • graph6ToSparse6(String) -- see graph6ToSparse6 -- converts a Graph6 string to a Sparse6 string
    • graphComplement(Graph) -- see graphComplement -- computes the complement of a graph
    • graphComplement(List) -- see graphComplement -- computes the complement of a graph
    • graphComplement(String) -- see graphComplement -- computes the complement of a graph
    • graphToString(Graph) -- see graphToString -- converts a graph to a string in the Graph6 format
    • graphToString(Ideal) -- see graphToString -- converts a graph to a string in the Graph6 format
    • graphToString(List,ZZ) -- see graphToString -- converts a graph to a string in the Graph6 format
    • graphToString(MonomialIdeal) -- see graphToString -- converts a graph to a string in the Graph6 format
    • graphToString(String) -- see graphToString -- converts a graph to a string in the Graph6 format
    • isPlanar(Graph) -- see isPlanar -- determines if a given graph is planar
    • isPlanar(String) -- see isPlanar -- determines if a given graph is planar
    • neighborhoodComplements(Graph) -- see neighborhoodComplements -- complements the neighborhood for each vertex, individually
    • neighborhoodComplements(List) -- see neighborhoodComplements -- complements the neighborhood for each vertex, individually
    • neighborhoodComplements(String) -- see neighborhoodComplements -- complements the neighborhood for each vertex, individually
    • newEdges(Graph,PolynomialRing) -- see newEdges -- replaces disjoint pairs of edges by disjoint pairs of two-chains
    • newEdges(List) -- see newEdges -- replaces disjoint pairs of edges by disjoint pairs of two-chains
    • newEdges(String) -- see newEdges -- replaces disjoint pairs of edges by disjoint pairs of two-chains
    • onlyPlanar(List) -- see onlyPlanar -- removes non-planar graphs from a list
    • onlyPlanar(List,Boolean) -- see onlyPlanar -- removes non-planar graphs from a list
    • relabelBipartite(Graph) -- see relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
    • relabelBipartite(List) -- see relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
    • relabelBipartite(String) -- see relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
    • relabelGraph(Graph) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(Graph,ZZ) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(Graph,ZZ,ZZ) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(List) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(List,ZZ) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(List,ZZ,ZZ) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(String) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(String,ZZ) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • relabelGraph(String,ZZ,ZZ) -- see relabelGraph -- applies a vertex invariant based refinement to a graph
    • removeEdges(Graph) -- see removeEdges -- creates a list of graphs obtained by removing one edge from the given graph in all possible ways
    • removeEdges(List) -- see removeEdges -- creates a list of graphs obtained by removing one edge from the given graph in all possible ways
    • removeEdges(String) -- see removeEdges -- creates a list of graphs obtained by removing one edge from the given graph in all possible ways
    • removeIsomorphs(List) -- see removeIsomorphs -- removes all isomorphs from a list of graphs
    • sparse6ToGraph6(String) -- see sparse6ToGraph6 -- converts a Sparse6 string to a Graph6 string
    • stringToEdgeIdeal(String,PolynomialRing) -- see stringToEdgeIdeal -- converts a Sparse6 or Graph6 String to an edge ideal in the given polynomial ring
    • stringToGraph(String,PolynomialRing) -- see stringToGraph -- converts a Sparse6 or Graph6 String to a Graph in the given polynomial ring
  • Symbols

For the programmer

The object Nauty is a package.