cc.redberry.core.groups.permutations

Class BacktrackSearch

java.lang.Object

cc.redberry.core.groups.permutations.BacktrackSearch

All Implemented Interfaces:

OutputPort<Permutation>

public final class BacktrackSearch
extends java.lang.Object
implements OutputPort<Permutation>

An iterator (organized as output port OutputPort) over group elements, that scans group in increasing order permutations according to the ordering induced by a base (in increasing order of base images). To be precise: if base B = [b1, b2, b3,..,bn], then element g which maps all base points into themselves (g(b) ∈ B for each b ∈ B) is guaranteed to precedes (<) an element h, which base image succeeds (>) the base image of g according to ordering specified by InducedOrdering.

Pruning the tree:
The iteration is organized as a depth-first search in the search tree of specified permutation group. This search tree is organized as follows: each vertex V on a particular level l specifies some partial base image B(l), this means that all permutations produced during iteration over child nodes of vertex V have same partial base images (for all g and i ∈ 0..l, g(B(i)) is fixed). If we want to iterate over elements that satisfy some property P for which we have a test function that guarantees false answer using the knowledge of partial base image, we can rule out (prune tree) all element under the level l. The property P and the corresponding test function can be changed via setTestFunction(BacktrackSearchTestFunction) and setProperty(cc.redberry.core.utils.Indicator) during iteration. If BacktrackSearchTestFunction was specified, then it is guaranteed that all unnecessary tree branches will be ruled out.

If property or test function were specified, then the iterator will search only those elements that satisfies specified conditions.
NOTE: BacktrackSearchTestFunction should be consistent with the base of permutation group.

The main algorithm used in this implementation is an iterator-like modification of PRINTELEMENTS and GENERALSEARCH described in Sec. 4.6.1 and 4.6.2 in [Holt05].

Since:

1.1.6

See Also:

BacktrackSearchTestFunction

Nested Class Summary

Nested classes/interfaces inherited from interface cc.redberry.core.utils.OutputPort

OutputPort.PortIterable<T>, OutputPort.PortIterator<T>, OutputPort.Singleton<T>

Constructor Summary

Constructors

Constructor and Description
BacktrackSearch(java.util.List<? extends BSGSElement> bsgs) Creates an iterator over group elements.
BacktrackSearch(java.util.List<? extends BSGSElement> bsgs, BacktrackSearchTestFunction test, Indicator<Permutation> property) Creates an iterator over group elements that satisfy specified property.

Method Summary

Modifier and Type	Method and Description
IntComparator	getInducedOrdering() Returns the ordering on Ω(n) induced by a base.
Indicator<Permutation>	getProperty() Returns the property of elements that we are search in group
BacktrackSearchTestFunction	getTestFunction() Returns the test function
Permutation[]	getWordReference() Returns reference on current permutation word.
int	lastModifiedLevel() Returns level of the last changed element.
void	setProperty(Indicator<Permutation> property) Sets the property of elements that we search in group
void	setTestFunction(BacktrackSearchTestFunction test) Sets the test function used to rule out unnecessary tree branches during search.
Permutation	take() Searches and returns the next element in group.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BacktrackSearch

public BacktrackSearch(java.util.List<? extends BSGSElement> bsgs,
                       BacktrackSearchTestFunction test,
                       Indicator<Permutation> property)

Creates an iterator over group elements that satisfy specified property.

Parameters:

bsgs - base and strong generating set

test - test function that applies at each level of search tree

property - property of permutations

BacktrackSearch

public BacktrackSearch(java.util.List<? extends BSGSElement> bsgs)

Creates an iterator over group elements.

Parameters:

bsgs - base and strong generating set

Method Detail

getTestFunction

public BacktrackSearchTestFunction getTestFunction()

Returns the test function

Returns:

test function

setTestFunction

public void setTestFunction(BacktrackSearchTestFunction test)

Sets the test function used to rule out unnecessary tree branches during search. The specified test function should be consistent with the base of current permutation group.

Parameters:

test - test function

getProperty

public Indicator<Permutation> getProperty()

Returns the property of elements that we are search in group

Returns:

property of elements that we are search in group

setProperty

public void setProperty(Indicator<Permutation> property)

Sets the property of elements that we search in group

Parameters:

property - property of permutations which we search in group

getInducedOrdering

public IntComparator getInducedOrdering()

Returns the ordering on Ω(n) induced by a base.

Returns:

ordering on Ω(n) induced by a base

See Also:

InducedOrdering

lastModifiedLevel

public int lastModifiedLevel()

Returns level of the last changed element.

Returns:

level of the last changed element

getWordReference

public Permutation[] getWordReference()

Returns reference on current permutation word.

Returns:

reference on current permutation word

take

public Permutation take()

Searches and returns the next element in group.

Specified by:

take in interface OutputPort<Permutation>

Returns:

next element in group