org.thegalactic.lattice

Class ClosureSystem

java.lang.Object

org.thegalactic.lattice.ClosureSystem

Direct Known Subclasses:

Context, ImplicationalSystem

public abstract class ClosureSystem
extends Object

This class is an abstract class defining the common behavior of closure systems, and specialy its closed set lattice generation.

Both a context and an implicational system have properties of a closure system, and therefore extend this class.

A closure system is formaly defined by a set of indexed elements and a closure operator (abstract methods getSet() and closure(java.util.TreeSet<java.lang.Comparable>)).

Abstract method save(java.lang.String) also describe the common behavior of a closure system.

However, this abstract class provides both abstract and non abstract methods.

Although abstract methods depends on data, and so have to be implemented by each extended class, non abstract methods only used property of a closure system. It is the case for methods nextClosure(org.thegalactic.lattice.Concept) (that computes the next closure of the specified one according to the lectic order implemented the well-known Wille algorithm) invoked by method allClosures() and the main method closedSetLattice(boolean) (where lattice can be transitively closed or reduced).

Constructor Summary

Constructors

Constructor and Description
ClosureSystem()

Method Summary

Modifier and Type	Method and Description
Vector<Concept>	allClosures() Returns all the closed sets of the specified closure system (that can be an IS or a context).
ConceptLattice	closedSetLattice(boolean diagram) Returns the closed set lattice of this component.
abstract TreeSet<Comparable>	closure(TreeSet<Comparable> set) Returns the closure of the specified set.
TreeMap<Object,TreeSet>	getReducibleElements() This function returns all reducible elements.
abstract SortedSet<Comparable>	getSet() Returns the set of elements of the closure system.
ConceptLattice	lattice() Returns the lattice of this component.
Concept	nextClosure(Concept cl) Returns the lecticaly next closed set of the specified one.
ConcreteDGraph<Comparable,?>	precedenceGraph() Returns the precedence graph of this component.
abstract void	save(String file) Saves this component in a file which name is specified.

Methods inherited from class java.lang.Object

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

Constructor Detail

ClosureSystem

public ClosureSystem()

Method Detail

getSet

public abstract SortedSet<Comparable> getSet()

Returns the set of elements of the closure system.

Returns:

the set of elements of the closure system

closure

public abstract TreeSet<Comparable> closure(TreeSet<Comparable> set)

Returns the closure of the specified set.

Parameters:

set - The specified set

Returns:

The closure

save

public abstract void save(String file)
                   throws IOException

Saves this component in a file which name is specified.

Parameters:

file - name of file

Throws:

IOException - When an IOException occurs

closedSetLattice

public ConceptLattice closedSetLattice(boolean diagram)

Returns the closed set lattice of this component.

A true value of the boolean diagram indicates that the Hasse diagramm of the lattice is computed (i.e. it is transitively reduced), whereas a false value indicates that the lattice is transitively closed

A transitively reduced lattice is generated by the static method ConceptLattice diagramLattice (ClosureSystem init) that implements an adaptation of Bordat’s algorithm. This adaptation computes the dependance graph while the lattice is generated, with the same complexity.

A transitively closed lattice is generated bye well-known Next Closure algorithm. In this case, the dependance graph of the lattice isn’t computed.

Parameters:

diagram - a boolean indicating if the Hasse diagramm of the lattice is computed or not.

Returns:

The concept lattice

lattice

public ConceptLattice lattice()

Returns the lattice of this component.

Returns:

The concept lattice

allClosures

public Vector<Concept> allClosures()

Returns all the closed sets of the specified closure system (that can be an IS or a context).

Closed sets are generated in lecticaly order, with the emptyset’s closure as first closed set, using the Ganter’s Next Closure algorithm.

Therefore, closed sets have to be comparable using ComparableSet class. This treatment is performed in O(cCl|S|^3) where S is the initial set of elements, c is the number of closed sets that could be exponential in the worst case, and Cl is the closure computation complexity.

Returns:

all the closeds set in the lectically order.

nextClosure

public Concept nextClosure(Concept cl)

Returns the lecticaly next closed set of the specified one.

This treatment is an implementation of the best knowm algorithm of Wille whose complexity is in O(Cl|S|^2), where S is the initial set of elements, and Cl is the closure computation complexity.

Parameters:

cl - a concept

Returns:

the lecticaly next closed set

precedenceGraph

public ConcreteDGraph<Comparable,?> precedenceGraph()

Returns the precedence graph of this component.

Nodes of the graph are elements of this component. There is an edge from element a to element b when a belongs to the closure of b.

The rule a -> a isn’t added to the precedence graph

When precedence graph is acyclic, then this component is a reduced one.

Returns:

the precedence graph

getReducibleElements

public TreeMap<Object,TreeSet> getReducibleElements()

This function returns all reducible elements.

A reducible elements is equivalent by closure to one or more other attributes. Reducible elements are computed using the precedence graph of the closure system. Complexity is in O()

Returns:

The map of reductible attributes with their equivalent attributes