Full API

AutomorphismGroup

The automorphism group of a graph, as reported by automorphism_group or nauty.

Read it through order, orbits, orbit_partition and generators.

DenseNautyGraph{D,W}

Memory-efficient graph format compatible with nauty. Can be directed (D = true) or undirected (D = false). This graph format stores the adjacency matrix in bit vector form. W is the underlying unsigned integer type that holds the individual bits of the graph's adjacency matrix (defaults to UInt).

DenseNautyGraph{D}(A::AbstractMatrix; [vertex_labels]) where {D}

Construct a DenseNautyGraph{D} from the adjacency matrix A. If A[i][j] != 0, an edge (i, j) is inserted. A must be a square matrix. The graph can be directed (D = true) or undirected (D = false). If D = false, A must be symmetric. Vertex labels can optionally be specified.

DenseNautyGraph{D}(n::Integer; [vertex_labels]) where {D}

Construct a DenseNautyGraph on n vertices and 0 edges. Can be directed (D = true) or undirected (D = false). Vertex labels can optionally be specified.

DenseNautyGraph{D}(edge_list::Vector{<:AbstractEdge}; [vertex_labels]) where {D}

Construct a DenseNautyGraph from a vector of edges. The number of vertices is the highest that is used in an edge in edge_list. The graph can be directed (D = true) or undirected (D = false). Vertex labels can optionally be specified.

DenseNautyGraph{D}(; vertex_labels) where {D}

Construct a vertex-labeled DenseNautyGraph on length(vertex_labels) vertices and 0 edges. Can be directed (D = true) or undirected (D = false).

Graphset{W}

A graphset is a special bit matrix used to represent the adjacency matrix of a nauty graph in dense format. For a graph on n vertices, the graphset contains n*m "words", i.e. unsigned integers that contain the bits of the adjacency matrix, where m is the number of words per vertex.

The organization of words is as follows:

   ------------ m words per vertex ----->  
   | 0x00000000, 0x00000000, 0x00000000, ...  
 n | 0x00000000, 0x00000000, 0x00000000, ...  
   | 0x00000000, 0x00000000, 0x00000000, ...  
   v

NautyBuffer

The working memory of a nauty run: everything nauty is handed to write into, namely the lab, ptn and orbits arrays, the canonical graph canong, and the NautyStatistics.

Every function that runs nauty allocates one of these unless it is given a buffer to use instead, so passing one keeps a loop over many graphs from allocating.

Examples

buffer = NautyBuffer(first(graphs))
ids = [canonical_id(g; buffer) for g in graphs]

NautyBuffer(g::AbstractNautyGraph)

Build a buffer for running nauty on g. It grows to fit whatever graph it is later used with, so one buffer serves graphs of any size, as long as they have the same type as g.

NautyDiGraph <: AbstractNautyGraph{Int}

Memory-efficient directed graph format compatible with nauty, which represents the graph as an adjacency matrix in bit vector form. Alias for DenseNautyGraph{true}.

See also NautyGraph, SpNautyGraph, and SpNautyDiGraph for other nauty-compatible graph formats.

NautyGraph <: AbstractNautyGraph{Int}

Memory-efficient undirected graph format compatible with nauty, which represents the graph as an adjacency matrix in bit vector form. Alias for DenseNautyGraph{false}.

See also NautyDiGraph, SpNautyGraph, and SpNautyDiGraph for other nauty-compatible graph formats.

NautyOptions

Records all options that affect nauty's execution. Mirrors nauty's optionblk, see the nauty manual for details.

NautyOptions(options::NautyOptions; kwargs...)

Copy options, overriding the given fields.

generators and exact_order are named as in NautyOptions(::AbstractNautyGraph) rather than after the fields they set.

NautyOptions(g::AbstractNautyGraph; digraph_or_loops=true, ignorelabels=false,
             generators=false, exact_order=false)

Build the options for running nauty on graph g.

Keyword arguments

• digraph_or_loops: must be true if g is directed or has loops. Setting it to false for a simple undirected graph is faster, but changes the canonical form.
• ignorelabels: if true, all vertices are treated as having the same label, so g's vertex labels are ignored.
• generators: if true, collect the generators of the automorphism group.
• exact_order: if true, collect the subgroup indices needed to report the automorphism group's order as an exact integer rather than a Float64.

NautyStatistics

Records the statistics nauty reports about a run. Mirrors nauty's statsblk, see the nauty manual for details.

NautyStatistics()

Build a zeroed set of statistics for nauty to write into.

SpNautyDiGraph

Sparse directed graph format compatible with nauty, which represents the graph via an edgelist. Repeated modifications to a SpNautyGraph may result in suboptimal memory usage. Alias for SparseNautyGraph{true}.

See also NautyGraph, NautyDiGraph, and SpNautyGraph for other nauty-compatible graph formats.

SpNautyGraph

Sparse undirected graph format compatible with nauty, which represents the graph via an edgelist. Repeated modifications to a SpNautyGraph may result in suboptimal memory usage. Alias for SparseNautyGraph{false}.

See also NautyGraph, NautyDiGraph, and SpNautyDiGraph for other nauty-compatible graph formats.

SparseNautyGraph{D}

Sparse graph format compatible with nauty. Can be directed (D = true) or undirected (D = false). This graph format stores the adjacency matrix as an edgelist. Repeated modifications to the graph may result in suboptimal memory usage.

SparseNautyGraph{D}(A::AbstractMatrix; [vertex_labels]) where {D}

Construct a SparseNautyGraph{D} from the adjacency matrix A. If A[i][j] != 0, an edge (i, j) is inserted. A must be a square matrix. The graph can be directed (D = true) or undirected (D = false). If D = false, A must be symmetric. Vertex labels can optionally be specified.

SparseNautyGraph{D}(n::Integer; [vertex_labels, ne=n]) where {D}

Construct a SparseNautyGraph on n vertices and 0 edges. Can be directed (D = true) or undirected (D = false). Vertex labels can optionally be specified. If ne is provided, enough memory for ne optimally packed edges is allocated.

SparseNautyGraph{D}(edge_list::Vector{<:AbstractEdge}; [vertex_labels]) where {D}

Construct a SparseNautyGraph from a vector of edges. The number of vertices is the highest that is used in an edge in edge_list. The graph can be directed (D = true) or undirected (D = false). Vertex labels can optionally be specified. To achieve optimal memory efficiency, it is recommended to sort the edge list beforehand.

SparseNautyGraph{D}(; vertex_labels) where {D}

Construct a vertex-labeled SparseNautyGraph on length(vertex_labels) vertices and 0 edges. Can be directed (D = true) or undirected (D = false).

automorphism_group(g::AbstractNautyGraph; buffer=NautyBuffer(g))

Return the AutomorphismGroup of g, containing the exact order, vertex orbits, and generators.

Use nauty instead to also get the canonical permutation, or to skip the parts of the computation you do not need. Pass a NautyBuffer to reuse the working memory across calls.

canonical(g::AbstractNautyGraph; buffer=NautyBuffer(g))

Return a canonized copy of g and the canonical permutation.

Pass a NautyBuffer to reuse the working memory across calls.

See also canonize!, which canonizes in place and returns only the permutation.

canonical_id(g::AbstractNautyGraph; buffer=NautyBuffer(g))

Hash the canonical version of g, using the first 128 bits returned by the SHA256 algorithm.

is_isomorphic(g1, g2) implies canonical_id(g1) == canonical_id(g2), so differing ids prove that g1 and g2 are not isomorphic. Equal ids imply isomorphism only up to hash collisions.

Pass a NautyBuffer to reuse the working memory across calls.

canonical_permutation(g::AbstractNautyGraph; buffer=NautyBuffer(g))

Return the permutation p needed to canonize g, meaning that g[p] is canonical.

Pass a NautyBuffer to reuse the working memory across calls.

See also nauty and canonize! for other tools related to canonization.

canonize!(g::AbstractNautyGraph; buffer=NautyBuffer(g))

Reorder g's vertices into canonical order and return the permutation used.

Pass a NautyBuffer to reuse the working memory across calls.

See also nauty and canonical_permutation for other tools related to canonization.

generators(autg::AutomorphismGroup)

Return the generating permutations of autg. Generator p maps vertex i to p[i].

The identity belongs to every automorphism group and is never listed as a generator, so a graph with no symmetry has an empty generating set rather than a single identity permutation.

The generators are only available if the group was computed with generators=true.

is_isomorphic(g::AbstractNautyGraph, h::AbstractNautyGraph;
              buffers=(NautyBuffer(g), NautyBuffer(h)))

Check whether two graphs g and h are isomorphic to each other by comparing their canonical forms.

Pass two NautyBuffers to reuse the working memory across calls.

iscanon(g::AbstractNautyGraph)

Return true if g has previously been canonized.

iscanon(g) == false does not necessarily imply that g is not in canonical form, it just means g has never been explicitly canonized. This function should be considered internal and may be removed in future versions.

label(g::AbstractNautyGraph, i::Integer)

Return the label of vertex i of g.

labels(g::AbstractNautyGraph)

Return the vertex labels of g.

Do not modify the vector of labels returned. Use setlabels! or setlabel! instead.

nauty(g::AbstractNautyGraph; canonize=false, buffer=NautyBuffer(g), options...)
nauty(g::AbstractNautyGraph, options::NautyOptions; canonize=false, buffer=NautyBuffer(g))

Compute a graph g's canonical permutation and AutomorphismGroup. If canonize=true, g will additionally be canonized in-place.

Every keyword other than canonize and buffer is passed on to NautyOptions, so generators, exact_order, digraph_or_loops and ignorelabels can all be set here. Pass a NautyBuffer to reuse the working memory across calls. Instead of the option keywords, you can also pass NautyOptions directly.

The orbits and an approximate group order come for free with every run. The generators and the exact group order each cost an extra callback into Julia, so they have to be requested.

See also automorphism_group for the automorphism group on its own, and canonize! and canonical_permutation for other functions related to canonization.

Lists all functions for which a NautyAlg method is defined

orbit_partition(autg::AutomorphismGroup)

Return the vertex orbits of autg as a vector of vertex vectors.

Both the orbits and the vertices within each orbit come out in increasing order. This allocates one vector per orbit, so prefer orbits when the labelling is enough.

orbits(autg::AutomorphismGroup)

Return the vertex orbits of autg, labeled by their smallest vertex.

Vertices i and j share an orbit exactly if orbits(autg)[i] == orbits(autg)[j]. See orbit_partition to get the orbits as separate vectors instead.

order(autg::AutomorphismGroup)

Return the order of autg, which is the number of group elements.

The result is an exact BigInt if the group was computed with exact_order=true. Otherwise it is a Float64, which carries about 16 significant digits, is exact up to roughly 10^12.

setlabel!(g::AbstractNautyGraph, i::Integer, vertex_label)

Set the label of vertex i of g equal to vertex_label.

setlabels!(g::AbstractNautyGraph, vertex_labels)

Set the vertex labels of g equal to vertex_labels.