During search, the partition must be refined with respect to the current graph stack until it is equitable: informally, until no cell can be split by looking at how its points connect to the cells of the partition. GraphBacktracking offers several methods of differing strength and cost. A stronger method splits the partition at least as much as a weaker one, prunes the search tree more, but costs more per node. Which one is used is controlled by the consolidator field of the configuration record passed to the search functions (see 2); the default is GB_MakeEquitableStrong (4.1-3).
Each method takes a partition stack ps, a tracer tracer (see BacktrackKit: Ordered tracers), and a list graphs of digraphs. It refines ps in place, recording the splits in tracer, and returns true on success or false if a split contradicted the tracer (a dead branch).
‣ GB_MakeEquitableNone( ps, tracer, graphs ) | ( operation ) |
Does nothing and returns true: the partition is left unchanged. Provided as a baseline (it makes graph backtracking behave like ordinary backtracking with respect to the graphs).
‣ GB_MakeEquitableWeak( ps, tracer, graphs ) | ( operation ) |
Refines ps by repeatedly splitting each cell according to the multiset of cells reached along out- and in-edges of each graph, iterating to a fixed point. This is the classical equitable-partition refinement applied to each graph in turn.
‣ GB_MakeEquitableStrong( ps, tracer, graphs ) | ( operation ) |
A stronger refinement than GB_MakeEquitableWeak (4.1-2): it distinguishes points using the combined edge information across all graphs simultaneously, rather than one graph at a time. This is the default consolidator.
‣ GB_MakeEquitableFull( ps, tracer, graphs ) | ( operation ) |
The strongest (and most expensive) refinement: it builds a single digraph encoding the whole graph stack, computes its automorphism group and orbits, and splits the partition by those orbits. This can prune branches the cheaper methods miss, at a substantial cost per node.
generated by GAPDoc2HTML