GraphBacktracking implements the graph backtracking algorithm described in the paper Computing canonical images in permutation groups with Graph Backtracking
, by Christopher Jefferson, Rebecca Waldecker and Wilf A. Wilson (https://arxiv.org/abs/2209.02534). Graph backtracking generalises Leon's partition backtrack: instead of refining only an ordered partition of the points, the search also accumulates a stack of vertex- and edge-labelled graphs, which can capture constraints that a partition alone cannot. This makes it possible to solve problems such as normaliser computation and the canonical image of a graph under an arbitrary group.
This package builds directly on the BacktrackKit package, and reuses its framework essentially unchanged: ordered partition stacks, tracers, constraints, the refiner protocol, and the top-level search loop. Those concepts are documented in the BacktrackKit manual and are not repeated here. This manual assumes you are familiar with them, in particular with BacktrackKit: The concept of constraints and BacktrackKit: Refiners, and documents only what GraphBacktracking adds on top.
Like BacktrackKit, this package exists for learning and exploring the algorithms. Its performance is extremely poor — often orders of magnitude slower than the built-in GAP functions for the same task. For a modern, high-performance implementation of graph backtracking, use the vole package (https://github.com/peal/vole) instead.
The one substantive extension to the BacktrackKit refiner protocol is that a GraphBacktracking refiner may, in addition to splitting cells of the partition, emit graphs. A value returned by a refiner's refine functions (see BacktrackKit: The record refine) may be a record with the components:
graph — a Digraphs digraph that is added to the graph stack; and/or
vertlabels — a list giving an initial colour for each vertex.
The graph stack is then made equitable (see 4) and contributes to the branching and pruning of the search in the same way the partition does.
generated by GAPDoc2HTML