org.uacalc.alg.conlat
Class CongruenceLattice

java.lang.Object
  org.uacalc.alg.conlat.CongruenceLattice

All Implemented Interfaces:

Algebra, Lattice, Order

public class CongruenceLattice
extends java.lang.Object
implements Lattice

A class to represent the congruence lattice of a SmallAlgebra; this is, an algebra with universe the integers from 0 to n-1. This uses the very fast algorithms from my unpublished paper Computing Congruences Efficiently which is available at http://www.math.hawaii.edu/~ralph/papers.html.

Version:

$Id: CongruenceLattice.java,v 1.38 2008/09/13 02:44:44 ralphfreese Exp $

Author:

Ralph Freese

Field Summary

static int	MAX_DRAWABLE_INPUT_SIZE
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

CongruenceLattice(SmallAlgebra alg)

Method Summary

java.util.List<Partition>	atoms()
int	cardinality()
Partition	Cg(int a, int b)
Partition	Cg(java.lang.Object a, java.lang.Object b)
java.util.List<Partition>	coatoms()
java.util.List	constantOperations() This gives a list of the operations of arity 0, which is a little different from the constants.
Partition	findJoinIrred(Partition a, Partition b) This finds a join irreducible congruence which is minimal with respect to being below b and not below a.
Partition	findMeetIrred(Partition a, Partition b) This finds a meet irreducible congruence which is maximal with respect to being above a and not above b.
IntArray	generatingPair(Partition part) Find a pair [a, b] (as an IntArray) which generates part.
SmallAlgebra	getAlgebra()
BasicLattice	getBasicLattice()
BasicLattice	getBasicLattice(boolean makeIfNull) Get the BasicLattice used primarily for drawing.
java.lang.String	getDescription()
org.latdraw.diagram.Diagram	getDiagram()
java.util.Map<Partition,Subtrace>	getJoinIrredToSubtraceMap()
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()
TypeFinder	getTypeFinder()
int	inputSize() The sum of the cardinality of the algebra raised to the arity of the operations.
java.util.List<Partition>	irredundantMeetDecomposition() Find a set of meet irreducible irredundantly meeting to zero.
java.util.List<Partition>	irredundantMeetDecompositionOld()
boolean	isDistributive()
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)
boolean	joinIrreducible(Partition part)
java.util.List<Partition>	joinIrreducibles() An optional operation returning the list of join irreducible elements.
java.util.List<Partition>	joinIrreducibles(ProgressReport report) A list of the join irreducibles; constructed if necessary.
boolean	joinIrreduciblesFound()
boolean	joinPrime(Partition beta) Test if beta is join prime.
boolean	leq(java.lang.Object a, java.lang.Object b) The order relation.
Partition	lowerStar(Partition beta) If beta is join irreducible, this gives its lower cover; otherwise null.
void	makeAtoms()
java.util.List<Partition>	makeIrredundantMeet(java.util.List<Partition> list)
void	makeJoinIrreducibles(ProgressReport report)
void	makeOperationTables() Make operation tables to speed up the evaluation of operations at the cost using more space.
void	makePrincipals(ProgressReport report)
void	makeUniverse()
void	makeUniverse(int size)
void	makeUniverse(int maxSize, ProgressReport report) Construct the universe.
void	makeUniverse(ProgressReport report)
java.lang.Object	meet(java.util.List args)
java.lang.Object	meet(java.lang.Object a, java.lang.Object b)
java.util.List<Partition>	meetIrreducibles() An optional operation returning the list of meet irreducible elements.
boolean	monitoring()
Partition	one()
java.util.List	operations()
java.util.List<Partition>	principals()
java.util.List<Partition>	principals(ProgressReport report)
void	setDescription(java.lang.String desc)
void	setMonitor(ProgressReport m)
void	setName(java.lang.String v)
SimilarityType	similarityType()
void	sortByRank(java.util.List<Partition> lst) Sort by rank.
void	stopMakeUniverse()
Subtrace	subtrace(Partition beta) Find a subtrace for beta over its lower cover.
Subtrace	subtrace(Partition beta, Partition alpha) Find a subtrace for beta over alpha.
int	type(Partition beta)
int	type(Partition beta, Partition alpha)
int	type(Partition beta, Partition alpha, ProgressReport report) Find the type for beta over alpha.
int	typeJI(Partition beta, ProgressReport report) Find the type of beta over its lower cover.
java.util.Set	typeSet()
java.util.Set	typeSet(ProgressReport report)
java.util.Set<Partition>	universe() We use java.util.Set to hold the universe of the algebra.
java.util.Set<Partition>	universe(ProgressReport report)
boolean	universeFound()
java.util.Map<Partition,java.util.List<Partition>>	upperCoversMap()
Partition	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

MAX_DRAWABLE_INPUT_SIZE

public static final int MAX_DRAWABLE_INPUT_SIZE

See Also:

Constant Field Values

Constructor Detail

CongruenceLattice

public CongruenceLattice(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:

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

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()

principals

public java.util.List<Partition> principals()

principals

public java.util.List<Partition> principals(ProgressReport report)

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

universe

public java.util.Set<Partition> 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

universe

public java.util.Set<Partition> universe(ProgressReport report)

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

joinIrreduciblesFound

public boolean joinIrreduciblesFound()

joinIrreducibles

public java.util.List<Partition> joinIrreducibles()

Description copied from interface: Lattice

An optional operation returning the list of join irreducible elements.

Specified by:

joinIrreducibles in interface Lattice

joinIrreducibles

public java.util.List<Partition> joinIrreducibles(ProgressReport report)

A list of the join irreducibles; constructed if necessary.

joinIrreducible

public boolean joinIrreducible(Partition part)

meetIrreducibles

public java.util.List<Partition> 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<Partition> atoms()

Specified by:

atoms in interface Lattice

makeAtoms

public void makeAtoms()

coatoms

public java.util.List<Partition> 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

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

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

makePrincipals

public void makePrincipals(ProgressReport report)

universeFound

public boolean universeFound()

stopMakeUniverse

public void stopMakeUniverse()

getMakeUniverseK

public int getMakeUniverseK()

getSizeComputed

public int getSizeComputed()

makeUniverse

public void makeUniverse(ProgressReport report)

makeUniverse

public void makeUniverse(int size)

makeUniverse

public void makeUniverse()

makeUniverse

public void makeUniverse(int maxSize,
                         ProgressReport report)

Construct the universe. If this method is interupted, the whole calculation starts over. We might change that if there is enough demand.

joinPrime

public boolean joinPrime(Partition beta)

Test if beta is join prime.

isDistributive

public boolean isDistributive()

makeJoinIrreducibles

public void makeJoinIrreducibles(ProgressReport report)

sortByRank

public void sortByRank(java.util.List<Partition> lst)

Sort by rank. The rank in size() - numberOfBlocks().

Parameters:

lst -

lowerStar

public Partition lowerStar(Partition beta)

If beta is join irreducible, this gives its lower cover; otherwise null.

upperCoversMap

public java.util.Map<Partition,java.util.List<Partition>> upperCoversMap()

Cg

public Partition Cg(java.lang.Object a,
                    java.lang.Object b)

Cg

public Partition Cg(int a,
                    int b)

typeSet

public java.util.Set typeSet()

typeSet

public java.util.Set typeSet(ProgressReport report)

type

public int type(Partition beta)

typeJI

public int typeJI(Partition beta,
                  ProgressReport report)

Find the type of beta over its lower cover. Beta is assumed to be join irreducible.

type

public int type(Partition beta,
                Partition alpha)

type

public int type(Partition beta,
                Partition alpha,
                ProgressReport report)

Find the type for beta over alpha. Beta is assumed to cover alpha.

subtrace

public Subtrace subtrace(Partition beta)

Find a subtrace for beta over its lower cover. Beta is assumed to be join irreducible.

subtrace

public Subtrace subtrace(Partition beta,
                         Partition alpha)

Find a subtrace for beta over alpha. Beta is assumed to cover alpha.

getJoinIrredToSubtraceMap

public java.util.Map<Partition,Subtrace> getJoinIrredToSubtraceMap()

getTypeFinder

public TypeFinder getTypeFinder()

generatingPair

public IntArray generatingPair(Partition part)

Find a pair [a, b] (as an IntArray) which generates part. Gives null if part is not principal.

findMeetIrred

public Partition findMeetIrred(Partition a,
                               Partition b)

This finds a meet irreducible congruence which is maximal with respect to being above a and not above b. Note if a is covered by b then [a,b] transposes up to [m,m*].

findJoinIrred

public Partition findJoinIrred(Partition a,
                               Partition b)

This finds a join irreducible congruence which is minimal with respect to being below b and not below a. Note if a is covered by b then [a,b] transposes down to [j,j_*].

zero

public final Partition zero()

one

public final Partition one()

irredundantMeetDecomposition

public java.util.List<Partition> irredundantMeetDecomposition()

Find a set of meet irreducible irredundantly meeting to zero.

Returns:

irredundantMeetDecompositionOld

public java.util.List<Partition> irredundantMeetDecompositionOld()

makeIrredundantMeet

public java.util.List<Partition> makeIrredundantMeet(java.util.List<Partition> list)

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