The GAP package BlissInterface provides a low level interface to the software bliss: A Tool for Computing Automorphism Groups and Canonical Labelings of Graphs, written by Tommi Junttila and Petteri Kaski [JK07].
The only interest of this package is the computation of the group of colour preserving automorphisms of coloured graphs. The graphs can be directed or undirected, bipartite or not. Duplicate edges between vertices are ignored but try to avoid introducing them in the first place as they are not ignored immediately but will consume memory and computation resources for a while.
For more specialized algorithms and methods of the theory of graphs, we recommend the packages Digraphs [DBJM+19] and GRAPE [Soi19]. To compute graph automorphisms see also the software nauty by Brendan McKay and Adolfo Piperno [MP14].
Download the package from https://github.com/gap-packages/BlissInterface.
Unzip/untar the file, this should create a directory called BlissInterface*.
Locate the pkg directory of your GAP directory, which contains the directories lib, doc and so on. Move the directory BlissInterface* into the pkg directory.
Alternatively, you can use your pkg directory. Make sure it is in your GAP root path.
It is necessary to compile the BlissInterface package. Inside the pkg/BlissInterface* directory, type
./configure make
Start GAP in the usual way (i.e. type gap at the command line).
Type LoadPackage("blissinterface");
For questions, remarks and issues please use the issue tracker.
This section will describe the two functions of BlissInterface, and their nonchecking counterparts.
‣ BlissGraphCanonicalLabeling( n, outneigh, colours, isdirected ) | ( 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 labeling of G, and hash is an integer valued hash of the permuted graph.
The coloured graph G has vertices [1..n]. If isdirected is true the G is directed. 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.
If colours is a list of length n then its elements are used to define a vertex colouring of G, otherwise all vertices have colour 0.
This function has a nonchecking version BLISS_GRAPH_CANONICAL_LABELING with the same parameters. Clearly, the nonchecking version is slightly faster but it must be used with extreme care. Bad parameters may result in unpredictable behaviour.
‣ BlissBipartiteCanonicalLabeling( n, m, outneigh, ucolours, lcolours ) | ( function ) |
Returns: The triple [gens,cl,hash] as GAP object, where gens is a list of generators for Aut(G), cl is a canonical labeling of G, and hash is an integer valued hash of the permuted graph.
The coloured, directed, bipartite graph G has vertices [1..n+m]. Upper vertices are [1..n], lower vertices are [n+1..n+m]. Edges point bottom up. The edges of G are given by outneigh, which is a list [N_1,...,N_m], such that N_i is the list of outneighbors of the lower vertex n+i. Duplicate edges between vertices and loops are ignored.
If ucolours is a list of length n then its elements are used to define a colouring of the upper vertices, otherwise all upper vertices have colour 0. Similarly, if lcolours is a list of length m then it defines a colouring of the lower vertices.
This function has a nonchecking version BLISS_BIPARTITE_CANONICAL_LABELING with the same parameters. Clearly, the nonchecking version is slightly faster but it must be used with extreme care. Bad parameters may result in unpredictable behaviour.
Using the point-line graph \(\Gamma\) of the Fano plane \(PG(2,2)\), we can compute its collineation group \(PSL(3,2)\). By colouring the vertices of \(\Gamma\), we get stabilizers of points and/or line.
gap> LoadPackage( "BlissInterface", false ); true gap> gap> fano:=Set([[1,2,4],[2,3,5],[3,4,6],[4,5,7], > [5,6,1],[6,7,2],[7,1,3]],Set); [ [ 1, 2, 4 ], [ 1, 3, 7 ], [ 1, 5, 6 ], [ 2, 3, 5 ], [ 2, 6, 7 ], [ 3, 4, 6 ], [ 4, 5, 7 ] ] gap> gap> bl1:=BlissBipartiteCanonicalLabeling(7, 7, fano, 0, 0); [ [ (3,5)(6,7)(9,10)(13,14), (3,6)(5,7)(9,10)(11,12), (2,3)(4,7)(8,9)(12,13), (1,2)(5,7)(9,11)(10,12) ], (1,7,3,4,5,2,6)(8,14)(9,13)(10,12), 1847000447 ] gap> g1:=Group(bl1[1]); Group([ (3,5)(6,7)(9,10)(13,14), (3,6)(5,7)(9,10)(11,12), (2,3)(4,7) (8,9)(12,13), (1,2)(5,7)(9,11)(10,12) ]) gap> Print(StructureDescription(g1),"\n"); PSL(3,2) gap> OrbitLength(g1,fano,OnSetsSets); 1 gap> gap> bl1c:=BlissBipartiteCanonicalLabeling(7, 7, fano, > [0,0,1,0,1,1,1], 0); [ [ (3,5)(6,7)(9,10)(13,14), (3,7)(5,6)(11,12)(13,14), (2,4)(5,6)(11,13)(12,14), (1,2)(5,7)(9,11)(10,12) ], (1,3,14,5,12,4)(6,11,7,13)(8,10), 2515557588 ] gap> g1c:=Group(bl1c[1]); Group([ (3,5)(6,7)(9,10)(13,14), (3,7)(5,6)(11,12)(13,14), (2,4)(5,6) (11,13)(12,14), (1,2)(5,7)(9,11)(10,12) ]) gap> Print(StructureDescription(g1c),"\n"); S4 gap> Orbits(g1c,[1..14]); [ [ 1, 4, 2 ], [ 3, 6, 5, 7 ], [ 8 ], [ 9, 13, 10, 11, 14, 12 ] ] gap> gap> bl1cc:=BlissBipartiteCanonicalLabeling(7, 7, fano, 0, > [0,1,1,1,1,1,1]); [ [ (3,5)(6,7)(9,10)(13,14), (3,7)(5,6)(11,12)(13,14), (2,4)(5,6)(11,13)(12,14), (1,2)(5,7)(9,11)(10,12) ], (1,7,3,4,5,2,6)(9,14)(10,13)(11,12), 1330424485 ] gap> g1cc:=Group(bl1cc[1]); Group([ (3,5)(6,7)(9,10)(13,14), (3,7)(5,6)(11,12)(13,14), (2,4)(5,6) (11,13)(12,14), (1,2)(5,7)(9,11)(10,12) ]) gap> Print(StructureDescription(g1cc),"\n"); S4 gap> Orbits(g1cc,[1..14]); [ [ 1, 4, 2 ], [ 3, 6, 5, 7 ], [ 8 ], [ 9, 13, 10, 11, 14, 12 ] ]
The automorphism group of the Petersen graphy is isomorphic to \(S_5\). The automorphisms preserving two disjoint 5-cycles form a dihedral group of order 10.
gap> petersen:=[[2,5,6],[1,3,7],[2,4,8],[3,5,9],[1,4,10], > [1,8,9],[2,9,10],[3,6,10],[4,6,7],[5,7,8]]; [ [ 2, 5, 6 ], [ 1, 3, 7 ], [ 2, 4, 8 ], [ 3, 5, 9 ], [ 1, 4, 10 ], [ 1, 8, 9 ], [ 2, 9, 10 ], [ 3, 6, 10 ], [ 4, 6, 7 ], [ 5, 7, 8 ] ] gap> bl2:=BlissGraphCanonicalLabeling(10, petersen, false, false); [ [ (4,8)(5,6)(9,10), (2,5,6)(3,4,9,7,10,8), (1,2,3,4,9,6)(5,7,8) ], (1,10)(2,9)(3,6,8,4,5,7), 3430842650 ] gap> g2:=Group(bl2[1]); Group([ (4,8)(5,6)(9,10), (2,5,6)(3,4,9,7,10,8), (1,2,3,4,9,6)(5,7,8) ]) gap> Print(StructureDescription(g2),"\n"); S5 gap> gap> bl2c:=BlissGraphCanonicalLabeling(10, petersen, > [1,1,1,1,1,2,2,2,2,2], false); [ [ (2,5)(3,4)(7,10)(8,9), (1,2,3,4,5)(6,7,8,9,10) ], (1,5,3,2,4)(6,10,7)(8,9), 2440551578 ] gap> g2c:=Group(bl2c[1]); Group([ (2,5)(3,4)(7,10)(8,9), (1,2,3,4,5)(6,7,8,9,10) ]) gap> Print(StructureDescription(g2c),"\n"); D10
Let \(\Gamma\) be the direct product of two oriented cycles of size 3. Then \(Aut(\Gamma)\) is isomorphic to \((C_3 \times C_3).C_2\).
gap> dir_edges:=[ > [1,2],[2,3],[3,1],[4,5],[5,6],[6,4],[7,8],[8,9],[9,7], > [1,4],[4,7],[7,1],[2,5],[5,8],[8,2],[3,6],[6,9],[9,3] > ]; [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ], [ 4, 5 ], [ 5, 6 ], [ 6, 4 ], [ 7, 8 ], [ 8, 9 ], [ 9, 7 ], [ 1, 4 ], [ 4, 7 ], [ 7, 1 ], [ 2, 5 ], [ 5, 8 ], [ 8, 2 ], [ 3, 6 ], [ 6, 9 ], [ 9, 3 ] ] gap> dg:=List([1..9],i->Filtered([1..9],j->[i,j] in dir_edges)); [ [ 2, 4 ], [ 3, 5 ], [ 1, 6 ], [ 5, 7 ], [ 6, 8 ], [ 4, 9 ], [ 1, 8 ], [ 2, 9 ], [ 3, 7 ] ] gap> bl3:=BlissGraphCanonicalLabeling(9, dg, false, true); [ [ (2,4)(3,7)(6,8), (1,2,3)(4,5,6)(7,8,9) ], (1,9)(2,7,5,4,8)(3,6), 895877481 ] gap> g3:=Group(bl3[1]); Group([ (2,4)(3,7)(6,8), (1,2,3)(4,5,6)(7,8,9) ]) gap> Print(StructureDescription(g3),"\n"); C3 x S3
The last example shows that the same set of edges may define both directed and undirected graphs.
gap> path:=[[2],[3],[]]; [ [ 2 ], [ 3 ], [ ] ] gap> BlissGraphCanonicalLabeling(3, path, false, true); [ [ ], (1,2,3), 1876527224 ] gap> BlissGraphCanonicalLabeling(3, path, false, false); [ [ (1,3) ], (1,2,3), 4110465937 ]
generated by GAPDoc2HTML