org.uacalc.alg
Class SubProductAlgebra

java.lang.Object
  org.uacalc.alg.GeneralAlgebra
      org.uacalc.alg.SubProductAlgebra

All Implemented Interfaces:

Algebra, SmallAlgebra

Direct Known Subclasses:

FreeAlgebra

public class SubProductAlgebra
extends GeneralAlgebra
implements SmallAlgebra

This class represents a subalgebra of a direct product of SmallAlgebras. It allows one to construct such an algebra even though the direct product may be too big to be a SmallAlgebra.

Version:

$Id: SubProductAlgebra.java,v 1.31 2011/04/02 19:42:37 ralphfreese Exp $

Author:

Ralph Freese

Nested Class Summary

Nested classes/interfaces inherited from interface org.uacalc.alg.SmallAlgebra

SmallAlgebra.AlgebraType

Field Summary

protected boolean	decompose
protected java.util.List<IntArray>	gens
protected BigProductAlgebra	productAlgebra
protected java.util.Map<IntArray,Term>	termMap
protected Term[]	terms
protected boolean	thinGenerators
protected java.util.List<IntArray>	univ
protected java.util.Map<IntArray,java.lang.Integer>	univHashMap
protected java.util.List<Variable>	variables
protected java.util.Map<Variable,IntArray>	varsMap

Fields inherited from class org.uacalc.alg.GeneralAlgebra

con, description, monitor, name, operations, operationsMap, similarityType, size, sub, universe

Fields inherited from interface org.uacalc.alg.Algebra

CARDINALITY_COUNTABLE, CARDINALITY_COUNTABLY_INFINITE, CARDINALITY_FINITE, CARDINALITY_INFINITE, CARDINALITY_UNKNOWN

Constructor Summary

protected	SubProductAlgebra()
	SubProductAlgebra(SmallAlgebra alg, int pow, java.util.Map<IntArray,Partition> rels)
protected	SubProductAlgebra(java.lang.String name)
	SubProductAlgebra(java.lang.String name, BigProductAlgebra prod, java.util.List<IntArray> gens) Construct the direct product of a List of SmallAlgebra's.
	SubProductAlgebra(java.lang.String name, BigProductAlgebra prod, java.util.List<IntArray> gens, boolean findTerms)
	SubProductAlgebra(java.lang.String name, BigProductAlgebra prod, java.util.List<IntArray> gens, boolean findTerms, boolean includeConstants, ProgressReport report) Construct the direct product of a List of SmallAlgebra's.
	SubProductAlgebra(java.lang.String name, BigProductAlgebra prod, java.util.List<IntArray> gens, boolean findTerms, ProgressReport report) Construct the direct product of a List of SmallAlgebra's.
	SubProductAlgebra(java.lang.String name, BigProductAlgebra prod, java.util.List<IntArray> gens, java.util.List<IntArray> univList) Construct a SubProductAlgebra when the gens and univ are already given.
	SubProductAlgebra(java.lang.String name, SmallAlgebra alg, int pow, java.util.Map<IntArray,Partition> rels)

Method Summary

SmallAlgebra.AlgebraType	algebraType() The type of algebra this is, like a quotient algebra.
CongruenceLattice	con() The congurence lattice.
void	convertToDefaultValueOps() This is used in the UI.
int	elementIndex(java.lang.Object obj) This method will return k if elem is the kth element; otherwise -1.
java.util.List<IntArray>	generators()
boolean	getDecompose(boolean v)
java.lang.Object	getElement(int index) returns the kth element.
IntArray	getElementFromTerm(Term t) Get the element associate with a term.
BigProductAlgebra	getProductAlgebra()
Term	getTerm(IntArray elt) Get the term associated with an element.
java.util.Map<IntArray,Term>	getTermMap()
Term[]	getTerms()
boolean	getThinGenerators(boolean v)
java.util.List<IntArray>	getUniverseList() The universe as a List such getElement(k) will equal the kth element of the List.
java.util.Map<IntArray,java.lang.Integer>	getUniverseOrder() A map that can be used for elementIndex(a).
java.util.List<Variable>	getVariables() The variables corresponding to the generator in the list of terms.
java.util.Map<Variable,IntArray>	getVariableToGeneratorMap()
static void	main(java.lang.String[] args)
protected void	makeOperations()
void	makeOperationTables() Make operation tables to speed up the evaluation of operations at the cost using more space.
BasicPartition	projectionKernel(int k)
void	setDecompose(boolean v)
void	setThinGenerators(boolean v)
protected java.util.Map<IntArray,Term>	setupGensToVarsMap(java.util.List<IntArray> gens)
SubalgebraLattice	sub() The subalgebra lattice.
BigProductAlgebra	superAlgebra()
java.util.List<IntArray>	thinGenerators()
static java.util.List<IntArray>	transpose(java.util.List<IntArray> lst)
static java.util.List<IntArray>	universeFromRelations(int n, int pow, java.util.Map<IntArray,Partition> rels) This gives all pow tuples with entries 0 to n-1 such that if (i,j) maps to theta, then the ith element is theta related to the jth element.

Methods inherited from class org.uacalc.alg.GeneralAlgebra

cardinality, constantOperations, getDescription, getMonitor, getName, getOperation, getOperationsMap, inputSize, isIdempotent, isSimilarTo, isTotal, isUnary, iterator, monitoring, operations, parent, parents, resetConAndSub, setDescription, setMonitor, setName, setOperations, setUniverse, similarityType, universe

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.uacalc.alg.SmallAlgebra

parent, parents, resetConAndSub

Methods inherited from interface org.uacalc.alg.Algebra

cardinality, constantOperations, getDescription, getMonitor, getName, getOperation, getOperationsMap, inputSize, isIdempotent, isSimilarTo, isTotal, isUnary, iterator, monitoring, operations, setDescription, setMonitor, setName, similarityType, universe

Field Detail

productAlgebra

protected BigProductAlgebra productAlgebra

gens

protected java.util.List<IntArray> gens

univ

protected java.util.List<IntArray> univ

thinGenerators

protected boolean thinGenerators

decompose

protected boolean decompose

univHashMap

protected java.util.Map<IntArray,java.lang.Integer> univHashMap

terms

protected Term[] terms

termMap

protected java.util.Map<IntArray,Term> termMap

variables

protected java.util.List<Variable> variables

varsMap

protected java.util.Map<Variable,IntArray> varsMap

Constructor Detail

SubProductAlgebra

protected SubProductAlgebra()

SubProductAlgebra

protected SubProductAlgebra(java.lang.String name)

SubProductAlgebra

public SubProductAlgebra(java.lang.String name,
                         BigProductAlgebra prod,
                         java.util.List<IntArray> gens)

Construct the direct product of a List of SmallAlgebra's. gens is a list of IntArray's.

SubProductAlgebra

public SubProductAlgebra(java.lang.String name,
                         BigProductAlgebra prod,
                         java.util.List<IntArray> gens,
                         boolean findTerms)

SubProductAlgebra

public SubProductAlgebra(java.lang.String name,
                         BigProductAlgebra prod,
                         java.util.List<IntArray> gens,
                         boolean findTerms,
                         ProgressReport report)

Construct the direct product of a List of SmallAlgebra's. gens is a list of IntArray's.

SubProductAlgebra

public SubProductAlgebra(java.lang.String name,
                         BigProductAlgebra prod,
                         java.util.List<IntArray> gens,
                         boolean findTerms,
                         boolean includeConstants,
                         ProgressReport report)

Construct the direct product of a List of SmallAlgebra's. gens is a list of IntArray's.

SubProductAlgebra

public SubProductAlgebra(java.lang.String name,
                         BigProductAlgebra prod,
                         java.util.List<IntArray> gens,
                         java.util.List<IntArray> univList)

Construct a SubProductAlgebra when the gens and univ are already given. Useful for reading back from a file without calculating the universe again.

SubProductAlgebra

public SubProductAlgebra(SmallAlgebra alg,
                         int pow,
                         java.util.Map<IntArray,Partition> rels)

SubProductAlgebra

public SubProductAlgebra(java.lang.String name,
                         SmallAlgebra alg,
                         int pow,
                         java.util.Map<IntArray,Partition> rels)

Method Detail

transpose

public static java.util.List<IntArray> transpose(java.util.List<IntArray> lst)

setThinGenerators

public void setThinGenerators(boolean v)

getThinGenerators

public boolean getThinGenerators(boolean v)

Parameters:

v -

Returns:

true if the generators have been thinned

setDecompose

public void setDecompose(boolean v)

getDecompose

public boolean getDecompose(boolean v)

Parameters:

v -

Returns:

true if the generators have been decomposed and thinned

thinGenerators

public java.util.List<IntArray> thinGenerators()

makeOperations

protected void makeOperations()

makeOperationTables

public void makeOperationTables()

Description copied from interface: Algebra

Make operation tables to speed up the evaluation of operations at the cost using more space.

Specified by:

makeOperationTables in interface Algebra

Overrides:

makeOperationTables in class GeneralAlgebra

See Also:

Operation.makeTable

setupGensToVarsMap

protected java.util.Map<IntArray,Term> setupGensToVarsMap(java.util.List<IntArray> gens)

getVariableToGeneratorMap

public java.util.Map<Variable,IntArray> getVariableToGeneratorMap()

getTerms

public Term[] getTerms()

getVariables

public java.util.List<Variable> getVariables()

The variables corresponding to the generator in the list of terms.

Returns:

getTerm

public Term getTerm(IntArray elt)

Get the term associated with an element.

getTermMap

public java.util.Map<IntArray,Term> getTermMap()

getProductAlgebra

public BigProductAlgebra getProductAlgebra()

superAlgebra

public BigProductAlgebra superAlgebra()

generators

public java.util.List<IntArray> generators()

getUniverseList

public java.util.List<IntArray> getUniverseList()

Description copied from interface: SmallAlgebra

The universe as a List such getElement(k) will equal the kth element of the List. It is allowed to be null.

Specified by:

getUniverseList in interface SmallAlgebra

getUniverseOrder

public java.util.Map<IntArray,java.lang.Integer> getUniverseOrder()

Description copied from interface: SmallAlgebra

A map that can be used for elementIndex(a). It is allowed to be null.

Specified by:

getUniverseOrder in interface SmallAlgebra

con

public CongruenceLattice con()

Description copied from interface: SmallAlgebra

The congurence lattice.

Specified by:

con in interface SmallAlgebra

Overrides:

con in class GeneralAlgebra

sub

public SubalgebraLattice sub()

Description copied from interface: SmallAlgebra

The subalgebra lattice.

Specified by:

sub in interface SmallAlgebra

Overrides:

sub in class GeneralAlgebra

getElementFromTerm

public IntArray getElementFromTerm(Term t)

Get the element associate with a term. This is linear in the size of the subalgebra.

Parameters:

t - the term

Returns:

the element as an IntArray

elementIndex

public int elementIndex(java.lang.Object obj)

Description copied from interface: SmallAlgebra

This method will return k if elem is the kth element; otherwise -1. (Should we have it throw an error instead?)

Specified by:

elementIndex in interface SmallAlgebra

getElement

public java.lang.Object getElement(int index)

Description copied from interface: SmallAlgebra

returns the kth element.

Specified by:

getElement in interface SmallAlgebra

projectionKernel

public BasicPartition projectionKernel(int k)

universeFromRelations

public static java.util.List<IntArray> universeFromRelations(int n,
                                                             int pow,
                                                             java.util.Map<IntArray,Partition> rels)

This gives all pow tuples with entries 0 to n-1 such that if (i,j) maps to theta, then the ith element is theta related to the jth element. So is A is an algebra of size n, this gives the subuniverse where the coordinates are related by the partitions (or congruences) of rels.

Parameters:

n - the size of the projections

pow - the power

rels - a map from pairs of coords to partition on n

Returns:

convertToDefaultValueOps

public void convertToDefaultValueOps()

Description copied from interface: SmallAlgebra

This is used in the UI. Only valid for BASIC algebras.

Specified by:

convertToDefaultValueOps in interface SmallAlgebra

algebraType

public SmallAlgebra.AlgebraType algebraType()

Description copied from interface: SmallAlgebra

The type of algebra this is, like a quotient algebra.

Specified by:

algebraType in interface SmallAlgebra

Returns:

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException,
                        BadAlgebraFileException

Throws:

java.io.IOException

BadAlgebraFileException