This section will describe the funtions of glabella, and their nonchecking counterparts.
Let \(\Gamma\) be a graph on the set \(\{1,\ldots,n\}\) of vertices. \(G\) may be directed or not; loops and duplicate edges are ignored. The graph is given by the list of its adjacencies \(N_1,\ldots,N_n\), where \(N_i\) is the set of (out)neighbors of the vertex \(i\). For an undirected simple graph, the list of adjacencies must be symmetric, that is, \(i \in N_j\) if and only if \(j\in N_i\).
A vertex colouring of \(\Gamma\) can be given in two different formats. The plain format is a list \(c_1,\ldots,c_n\) of integers; \(c_i\) being the colour of the vertex \(i\). The nauty format consists of two lists: \(u_1,\ldots,u_n\) is a permutation of \(\{1,\ldots,n\}\), and \(s_1,\ldots,s_n \in \{0,1\}\). The second list indicates the division of the vertices into colours: if \(s_i=0\), then a colour class ends at position \(i\). For example, the lists
\[u=[3,4,6,7,2,1,5,8,9], \quad s=[0,0,1,1,1,0,1,1,0]\]
represent the colour classes \(\{\{3\},\{4\},\{1,2,6,7\},\{5,8,9\}\}\). In plain format, the same colouring can be given by the list \(c=[1,1,2,3,4,1,1,4,4]\).
The solver programs (recently bliss 0.73, nauty 2.7R1) compute the generators of the automorphism group of the (coloured) graph \(\Gamma\). Moreover a canonical labelling of \(\Gamma\) is computed; this is a permutation of the vertices that brings the graph in a canonical format. Isomorphic graphs in canonical format are equal. Notice that canonical labellings can depend on the solver used, the version of the solver, the version of this packages, the version of GAP, parameter settings of the solver, and possibly even the compiler and computer used.
The solver programs also compute a 32-bit hash value of the graph. The same as above: this hash value is an isomorphy invariant that depends on your software and hardware environment. It also depends on the colouring in bliss, but not in nauty.
Our suggestion is to use bliss for directed graphs and Traces for undirected graphs. All solvers seem to perform better with undirected graphs.
Very efficient solver, written in C++. Works well for both directed and undirected graphs.
Written in C. Works for both directed and undirected graphs. Only recommended for small graphs.
Written in C. Works for both directed and undirected graphs. Not recommended for large graphs with few automorphisms.
Very efficient solver, written in C. It only works for undirected graphs.
This section will describe the funtions of glabella, and their nonchecking counterparts. The nonchecking versions are slightly faster but it must be used with extreme care. Bad parameters may result in unpredictable behaviour.
‣ GraphCanonicalLabelling@( n, outneigh, colouring[, isdirected[, solver]] ) | ( function ) |
‣ GraphCanonicalLabellingNC@( n, outneigh, colours, isdirected, solver ) | ( function ) |
Returns: The triple [gens,cl,hash] as GAP object, where gens is a list of generators for the group of colour preserving automorphisms of the graph G, cl is a canonical labelling of G, and hash is an integer valued 32-bit hash of the permuted graph.
The coloured graph G has vertices [1..n]. If isdirected is true then G is directed. (Default: false.) The edges of G are given by outneigh, which is a list [N_1,...,N_n], such that N_i is the list of (out)neighbors of the vertex i. Duplicate edges between vertices and loops are ignored.
For coloured graphs, colouring is either a list of length n (plain format), or a pair of two lists of length n (nauty format). For malformatted colourings, all vertices have colour 0.
The solver can be specified by the strings "bliss", "densenauty", "sparsenauty" or "traces". (Default: "bliss".)
GraphCanonicalLabellingNC is the operation that is called by the function GraphCanonicalLabelling, using the same arguments. Results are unpredictable if the parameters are not well-formed.
‣ InfoGlabella | ( info class ) |
An infoclass for the package. Its default value is \(0\).
generated by GAPDoc2HTML