Full API

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

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.

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

canonical_id(g::AbstractNautyGraph)

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

The canonical id has the property that is_isomorphic(g1, g2) == true implies canonical_id(g1) == canonical_id(g2). The converse usually holds as well, but in very rare cases, hash collisions may cause non-isomorphic graphs to have the same canonical id.

canonical_permutation(g::AbstractNautyGraph)

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

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

canonize!(g::AbstractNautyGraph)

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

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

is_isomorphic(g::AbstractNautyGraph, h::AbstractNautyGraph)

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

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, [options::NautyOptions]; [canonize=false])

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

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

Lists all functions for which a NautyAlg method is defined

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.