Vole.jl is a pure-Julia package implementing backtrack search algorithms in finite permutation groups. It is a Julia port of the Vole GAP package, with an idiomatic Julia API and native integration with GAP.jl.
- Subgroup and coset intersection
- Normaliser and centraliser computation
- Graph automorphism groups and canonical labellings
- Graph isomorphism testing
- Canonical images under arbitrary group actions (sets, tuples, sets-of-sets, sets-of-tuples, digraphs)
- Extensible constraint/refiner system for custom search problems
- Pure Julia — no compiled binary required
- Julia ≥ 1.10
- GAP.jl (≥ 0.10)
using Pkg
Pkg.add(url="https://github.com/peal/Vole.jl")After registration in the Julia General registry:
Pkg.add("Vole")using Vole, GAP
S5 = GAP.Globals.SymmetricGroup(5)
A5 = GAP.Globals.AlternatingGroup(5)
# Intersection of two groups
intersect(S5, A5) # => Group of order 60 (A5)
# Stabilizer of a set under on_sets
stabilizer(S5, [1, 2, 3], on_sets) # => Group of order 12
# Normalizer
normalizer(S5, A5) # => S5
# Canonical permutation (unique coset representative)
canonical_perm(S5, [2, 4], on_sets) # => a GAP permutation
# Canonical form: perm + image + automorphism group in one call
cf = canonical_form(S5, [2, 4], on_sets)
cf.perm # canonical permutation
cf.image # canonical image of [2,4]
cf.aut_group # setwise stabilizer of [2,4] in S5
# Digraph automorphism group and canonical labelling
D = GAP.Globals.CycleDigraph(5)
automorphism_group(D) # => cyclic group of order 5
digraph_canonical_labelling(D) # => canonical permutation
# Graph isomorphism
D2 = GAP.Globals.Digraph(GAP.GapObj([[4], [3], [1], [2]]))
is_isomorphic_digraph(D2, GAP.Globals.CycleDigraph(4)) # => trueActions are typed singletons — not symbols — for type safety and dispatch:
| Singleton | Meaning |
|---|---|
on_points |
act on individual points |
on_sets |
act on sets of points |
on_tuples |
act on ordered tuples of points |
on_sets_sets |
act on sets of sets |
on_sets_tuples |
act on sets of tuples |
on_digraphs |
relabel digraph vertices |
intersect(G, H, ...) # group/coset intersection
stabilizer(G, obj, action=on_points) # setwise stabilizer
normalizer(G, H) # normalizer
centralizer(G, x) # centralizer
is_conjugate(G, x, y) # conjugacy test
representative_action(G, x, y, action) # mapping element
two_closure(G) # two-closure
canonical_perm(G, obj, action=on_points) # canonical permutation
canonical_image(G, obj, action=on_points) # canonical image
canonical_form(G, obj, action=on_points) # CanonicalForm (perm+image+aut_group)
automorphism_group(D) # digraph automorphisms
canonical_digraph(D) # canonical digraph
digraph_canonical_labelling(D) # labelling permutation
isomorphism_digraphs(D1, D2) # isomorphism or nothing
is_isomorphic_digraph(D1, D2) # BoolAll constraint functions are exported directly:
stabilize(obj, action=on_points) # obj^g = obj
transport(source, target, action=on_points) # source^g = target
in_group(G) # g ∈ G
in_coset(C) # g ∈ C (right coset)
normalize(H) # g normalizes H
centralize(x) # g centralizes x
moved_points(pts) # g ∈ Sym(pts)
largest_moved_point(k) # g moves no point > k
is_even() # g is even permutation
is_odd() # g is odd permutation
none() # no solution (always fails)find_group(constraints...; points=0) # group of all solutions
find_representative(constraints...; points=0) # one solution or nothing
find_coset(constraints...; points=0) # coset of solutions
VoleFind.canonical(G, constraints...) # (group=..., canonical=...)Vole.jl is a pure Julia implementation of the backtrack search algorithms described in:
C. Jefferson, M. Pfeiffer, R. Waldecker, W. A. Wilson (2021). Permutation group algorithms based on directed graphs. Journal of Algebra.
The engine comprises:
- PartitionStack — ordered partition refinement
- Tracer — symmetry and canonical tracing
- RefinerStore — pluggable refiner system
- StabTree — stabilizer chain trees with orbital graphs
- BacktrackSearch — group and coset search with orbit pruning