org.uacalc.alg.sublat
Class SubalgebraLattice

java.lang.Object
  org.uacalc.alg.sublat.SubalgebraLattice

All Implemented Interfaces:

Algebra, Lattice, Order

public class SubalgebraLattice
extends java.lang.Object
implements Lattice

A class to represent the subalgebra lattice of a basic algebra; this is, an algebra with universe the integers from 0 to n-1.

Version:

$Id: SubalgebraLattice.java,v 1.36 2009/12/05 04:00:29 ralphfreese Exp $

Author:

Ralph Freese

Field Summary

static int	MAX_DRAWABLE_SIZE
static ProgressReport	monitor

Fields inherited from interface org.uacalc.alg.Algebra

CARDINALITY_COUNTABLE, CARDINALITY_COUNTABLY_INFINITE, CARDINALITY_FINITE, CARDINALITY_INFINITE, CARDINALITY_UNKNOWN

Constructor Summary

SubalgebraLattice(SmallAlgebra alg)

Method Summary

java.util.List<BasicSet>	atoms()
int	cardinality()
java.util.List<BasicSet>	coatoms()
java.util.List	constantOperations() This gives a list of the operations of arity 0, which is a little different from the constants.
static java.util.Map<java.lang.Integer,java.lang.Integer>	extendToHomomorphism(int[] gens, int[] gensB, SmallAlgebra A, SmallAlgebra B) Try to extend the map gens[i] to gensB[i] to a homomorphism.
static java.util.Map<java.lang.Integer,java.lang.Integer>	extendToHomomorphism(java.util.Map<java.lang.Integer,java.lang.Integer> homo, SmallAlgebra A, SmallAlgebra B) Try to extend the map to a homomorphism.
java.util.Set	filter(BasicSet elt) The set of all subalgebras containing the subalgebra elt.
BasicSet	findMinimalSizedGeneratingSet()
SmallAlgebra	getAlgebra()
BasicLattice	getBasicLattice()
BasicLattice	getBasicLattice(boolean makeIfNull) Get the BasicLattice used primarily for drawing.
java.lang.String	getDescription()
org.latdraw.diagram.Diagram	getDiagram()
int	getMakeUniverseK()
ProgressReport	getMonitor()
java.lang.String	getName()
Operation	getOperation(OperationSymbol sym) Get the operation correspond to a symbol or null if the symbol is not part of the similarityType.
java.util.Map<OperationSymbol,Operation>	getOperationsMap()
int	getSizeComputed()
int	inputSize() The sum of the cardinality of the algebra raised to the arity of the operations.
boolean	isDrawable()
boolean	isIdempotent() Test if all of the operations are idempotent.
boolean	isSimilarTo(Algebra alg)
boolean	isSmallerThan(int size)
boolean	isTotal() This will fail only if there are some OperationWithDefaultValue's which are not total.
boolean	isUnary()
java.util.Iterator	iterator() returns the iterator of the universe.
java.lang.Object	join(java.util.List args)
java.lang.Object	join(java.lang.Object a, java.lang.Object b)
java.util.Set	joinClosure(java.util.Collection gens)
java.util.Set	joinClosure(java.util.Collection gens, int maxSize) This gives the set of joins of all nonempty subsets of gens, so it is necessary to add a least element if you want to include it.
boolean	joinIrreducible(BasicSet subalg)
java.util.List	joinIrreducibles() A list of the join irreducibles; constructed if necessary.
boolean	leq(java.lang.Object a, java.lang.Object b) The order relation.
static void	main(java.lang.String[] args)
void	makeJoinIrreducibles()
void	makeOperationTables() Make operation tables to speed up the evaluation of operations at the cost using more space.
BasicSet	makeSg(java.util.List<java.lang.Integer> gens) Make the subuniverse generated by gens.
BasicSet	makeSg(java.util.List<java.lang.Integer> gens, int closedMark)
BasicSet	makeSg(java.util.List<java.lang.Integer> gens, int closedMark, int maxSize) Make the subuniverse generated by gens.
void	makeUniverse() Test if one subuniverse is contained in another.
void	makeUniverse(int maxSize) Construct the universe.
java.lang.Object	meet(java.util.List args)
java.lang.Object	meet(java.lang.Object a, java.lang.Object b)
java.util.List	meetIrreducibles() An optional operation returning the list of meet irreducible elements.
boolean	monitoring()
static <T> java.util.List<T>	noDuplicates(java.util.List<T> lst) This gives a List without duplicates assuming lst is sorted.
BasicSet	one()
java.util.List<BasicSet>	oneGeneratedSubalgebras() These are really one generate subuniverses.
java.util.List	operations()
void	setDescription(java.lang.String desc)
void	setMonitor(ProgressReport m)
void	setName(java.lang.String v)
Subalgebra	Sg(BasicSet s)
BasicSet	sg(int[] gens)
Subalgebra	Sg(int[] gens)
java.util.Set	sg(java.util.Set set)
SimilarityType	similarityType()
void	stopMakeUniverse()
java.util.Set	universe() We use java.util.Set to hold the universe of the algebra.
boolean	universeFound() Has the universe been calculated.
BasicSet	zero()

Methods inherited from class java.lang.Object

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

Field Detail

monitor

public static ProgressReport monitor

MAX_DRAWABLE_SIZE

public static final int MAX_DRAWABLE_SIZE

See Also:

Constant Field Values

Constructor Detail

SubalgebraLattice

public SubalgebraLattice(SmallAlgebra alg)

Method Detail

setMonitor

public void setMonitor(ProgressReport m)

Specified by:

setMonitor in interface Algebra

getMonitor

public ProgressReport getMonitor()

Specified by:

getMonitor in interface Algebra

monitoring

public final boolean monitoring()

Specified by:

monitoring in interface Algebra

isTotal

public boolean isTotal()

Description copied from interface: Algebra

This will fail only if there are some OperationWithDefaultValue's which are not total.

Specified by:

isTotal in interface Algebra

Returns:

constantOperations

public java.util.List constantOperations()

Description copied from interface: Algebra

This gives a list of the operations of arity 0, which is a little different from the constants.

Specified by:

constantOperations in interface Algebra

getAlgebra

public SmallAlgebra getAlgebra()

isUnary

public boolean isUnary()

Specified by:

isUnary in interface Algebra

getDescription

public java.lang.String getDescription()

Specified by:

getDescription in interface Algebra

setDescription

public void setDescription(java.lang.String desc)

Specified by:

setDescription in interface Algebra

cardinality

public int cardinality()

Specified by:

cardinality in interface Algebra

Returns:

the cardinality if possible, else a negative int

inputSize

public int inputSize()

Description copied from interface: Algebra

The sum of the cardinality of the algebra raised to the arity of the operations.

Specified by:

inputSize in interface Algebra

Returns:

the inputSize or -1 if it is not an int

isSmallerThan

public boolean isSmallerThan(int size)

isDrawable

public boolean isDrawable()

getBasicLattice

public BasicLattice getBasicLattice()

getBasicLattice

public BasicLattice getBasicLattice(boolean makeIfNull)

Get the BasicLattice used primarily for drawing.

Returns:

a BasicLattice view

getDiagram

public org.latdraw.diagram.Diagram getDiagram()

universe

public java.util.Set universe()

Description copied from interface: Algebra

We use java.util.Set to hold the universe of the algebra. In order to accomodate infinite algebras and algebras with unknown cardinality, we allow the following changes:

• size can return a negative value if the cardinality is infinite or unknown or is larger that the largest int. In this case we may want to specify some information about the cardinality in another method but we have not decided on this yet.
• it is allowed that the iterator method of Set throw an UnsupportedOperationException.
• when extending AbstractSet, the contains method should be overwritten.

Specified by:

universe in interface Algebra

isSimilarTo

public boolean isSimilarTo(Algebra alg)

Specified by:

isSimilarTo in interface Algebra

similarityType

public SimilarityType similarityType()

Specified by:

similarityType in interface Algebra

iterator

public java.util.Iterator iterator()

Description copied from interface: Algebra

returns the iterator of the universe. Since we allow that to be optional, this may throw an UnsupportedOperationException.

Specified by:

iterator in interface Algebra

getName

public java.lang.String getName()

Specified by:

getName in interface Algebra

setName

public void setName(java.lang.String v)

Specified by:

setName in interface Algebra

filter

public java.util.Set filter(BasicSet elt)

The set of all subalgebras containing the subalgebra elt.

oneGeneratedSubalgebras

public java.util.List<BasicSet> oneGeneratedSubalgebras()

These are really one generate subuniverses.

Returns:

joinIrreducibles

public java.util.List joinIrreducibles()

A list of the join irreducibles; constructed if necessary.

Specified by:

joinIrreducibles in interface Lattice

joinIrreducible

public boolean joinIrreducible(BasicSet subalg)

meetIrreducibles

public java.util.List meetIrreducibles()

Description copied from interface: Lattice

An optional operation returning the list of meet irreducible elements.

Specified by:

meetIrreducibles in interface Lattice

atoms

public java.util.List<BasicSet> atoms()

Specified by:

atoms in interface Lattice

coatoms

public java.util.List<BasicSet> coatoms()

Specified by:

coatoms in interface Lattice

join

public java.lang.Object join(java.lang.Object a,
                             java.lang.Object b)

Specified by:

join in interface Lattice

join

public java.lang.Object join(java.util.List args)

Specified by:

join in interface Lattice

meet

public java.lang.Object meet(java.lang.Object a,
                             java.lang.Object b)

Specified by:

meet in interface Lattice

meet

public java.lang.Object meet(java.util.List args)

Specified by:

meet in interface Lattice

leq

public boolean leq(java.lang.Object a,
                   java.lang.Object b)

Description copied from interface: Order

The order relation.

Specified by:

leq in interface Order

operations

public java.util.List operations()

Specified by:

operations in interface Algebra

getOperation

public Operation getOperation(OperationSymbol sym)

Description copied from interface: Algebra

Get the operation correspond to a symbol or null if the symbol is not part of the similarityType.

Specified by:

getOperation in interface Algebra

getOperationsMap

public java.util.Map<OperationSymbol,Operation> getOperationsMap()

Specified by:

getOperationsMap in interface Algebra

universeFound

public boolean universeFound()

Has the universe been calculated.

stopMakeUniverse

public void stopMakeUniverse()

getMakeUniverseK

public int getMakeUniverseK()

getSizeComputed

public int getSizeComputed()

sg

public java.util.Set sg(java.util.Set set)

noDuplicates

public static <T> java.util.List<T> noDuplicates(java.util.List<T> lst)

This gives a List without duplicates assuming lst is sorted.

Parameters:

lst - a sorted list (so duplicates occur in blocks).

Sg

public Subalgebra Sg(BasicSet s)

Sg

public Subalgebra Sg(int[] gens)

sg

public BasicSet sg(int[] gens)

makeSg

public BasicSet makeSg(java.util.List<java.lang.Integer> gens)

Make the subuniverse generated by gens.

Parameters:

gens - a list of Integers without duplicates which contains all the constants of the algebra.

makeSg

public BasicSet makeSg(java.util.List<java.lang.Integer> gens,
                       int closedMark)

makeSg

public BasicSet makeSg(java.util.List<java.lang.Integer> gens,
                       int closedMark,
                       int maxSize)

Make the subuniverse generated by gens.

Parameters:

gens - a list of Integers without duplicates which contains all the constants of the algebra.

closedMark - the closure of all elements up to this are already in gens.

maxSize - return the whole algebra if we exceed this

extendToHomomorphism

public static java.util.Map<java.lang.Integer,java.lang.Integer> extendToHomomorphism(int[] gens,
                                                                                      int[] gensB,
                                                                                      SmallAlgebra A,
                                                                                      SmallAlgebra B)

Try to extend the map gens[i] to gensB[i] to a homomorphism. Both gens and gensB can have duplicates. If the induced map is inconsistent, we return null. For example gens is [1,1] and gensB is [2.3] is inconsistent.

Parameters:

gens -

gensB -

B -

Returns:

the homomorphism as a map or null if it does not exist.

extendToHomomorphism

public static java.util.Map<java.lang.Integer,java.lang.Integer> extendToHomomorphism(java.util.Map<java.lang.Integer,java.lang.Integer> homo,
                                                                                      SmallAlgebra A,
                                                                                      SmallAlgebra B)

Try to extend the map to a homomorphism.

Parameters:

homo -

B -

Returns:

makeUniverse

public void makeUniverse()

Test if one subuniverse is contained in another.

makeUniverse

public void makeUniverse(int maxSize)

Construct the universe. If this method is interupted, the whole calculation starts over. We might change that if there is enough demand. Use the usual method for computing the closure expect we keep the a HashSet jisHash. This is originally set to all one generated subalgebras but if it is discovered that one of these is not join irreducible, it is removed from the set and it is not used in computing the closure. **Clear this up.***

joinClosure

public java.util.Set joinClosure(java.util.Collection gens)

joinClosure

public java.util.Set joinClosure(java.util.Collection gens,
                                 int maxSize)

This gives the set of joins of all nonempty subsets of gens, so it is necessary to add a least element if you want to include it.

makeJoinIrreducibles

public void makeJoinIrreducibles()

findMinimalSizedGeneratingSet

public BasicSet findMinimalSizedGeneratingSet()

zero

public final BasicSet zero()

one

public final BasicSet one()

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

See Also:

Operation.makeTable

isIdempotent

public boolean isIdempotent()

Description copied from interface: Algebra

Test if all of the operations are idempotent.

Specified by:

isIdempotent in interface Algebra

main

public static void main(java.lang.String[] args)