Context.java
package org.thegalactic.context;
/*
* Context.java
*
* Copyright: 2010-2015 Karell Bertet, France
* Copyright: 2015-2016 The Galactic Organization, France
*
* License: http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html CeCILL-B license
*
* This file is part of java-lattices.
* You can redistribute it and/or modify it under the terms of the CeCILL-B license.
*/
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;
import org.thegalactic.context.io.ContextIOFactory;
import org.thegalactic.dgraph.Node;
import org.thegalactic.io.Filer;
import org.thegalactic.lattice.ArrowRelation;
import org.thegalactic.lattice.ClosureSystem;
import org.thegalactic.lattice.Concept;
import org.thegalactic.lattice.ConceptLattice;
import org.thegalactic.lattice.Lattice;
import org.thegalactic.util.ComparableSet;
import org.thegalactic.util.Couple;
/**
* This class gives a standard representation for a context.
* A context is a binary table, with attributes in column, and observations
* in row.
*
* A context is composed of
*
* - attributes, a treeset of comparable objects;
* - observations, a treeset of comparable objects;
* - a Galois connexion (extent,intent) between objects and attributes where
* `extent` is a TreeMap that associates to each attribute a TreeSet of
* observations and
* `intent` is a TreeMap that associates to each observation a TreeSet of
* attributes.
*
* This class provides methods implementing classical operation on a context:
* closure, reduction, reverse, ...
*
* A context owns properties of a closure system, and thus extends the abstract
* class
* {@link ClosureSystem} and implements methods {@link #getSet} and
* {@link #closure}.
* Therefore, the closed set lattice of a context can be generated by invoking
* method
* {@link ClosureSystem#closedSetLattice} of a closure system.
* However, this class also provides a method generating the concept lattice of
* this component
* by completing each closed set of the closed set lattice.
*
* A context can be instancied from and save to a text file in the following
* format:
*
* - the list of observations separated by a space on the first line;
* - the list of attrbutes separated by a space on the second line;
* - then, for each observations o, the list of its intent on a line, written
* like o a1 a2 ...
*
* ~~~
* Observations: 1 2 3
* Attributes: a b c d e
* 1: a c
* 2: a b
* 3: b d e
* 4: c e
* ~~~
*
* 
*
* @uml Context.png
* !include resources/org/thegalactic/context/Context.iuml
* !include resources/org/thegalactic/lattice/ClosureSystem.iuml
*
* hide members
* show Context members
* class Context #LightCyan
* title Context UML graph
*/
public class Context extends ClosureSystem {
/**
* Generates a partially random context.
*
* @param nbObs number of observations
* @param nbGrp number of groups of attributes . Attributes are
* grouped such that each observation has one
* attribute per group.
* @param nbAttrPerGrp number of attributes per group.
*
* @return randomly generated context
*/
public static Context random(int nbObs, int nbGrp, int nbAttrPerGrp) {
Context ctx = new Context();
StringBuilder name = new StringBuilder();
// Generates Observations.
for (int i = 1; i <= nbObs; i++) {
ctx.addToObservations(Integer.toString(i));
}
// Generates Attributes.
for (int i = 1; i <= nbGrp; i++) {
for (int j = 1; j <= nbAttrPerGrp; j++) {
int q = i;
name.setLength(0);
do {
int rem = q % 26;
q = q / 26;
name.append((char) (rem + 65));
} while (q != 0);
name.append(j);
ctx.addToAttributes(name.toString());
}
}
// Generates all requested observations.
Random r = new Random();
int attr = r.nextInt(nbAttrPerGrp) + 1;
for (int i = 1; i <= nbObs; i++) {
// i : Observation
for (int j = 1; j <= nbGrp; j++) {
// j : Familly
int q = j;
// Clear the StringBuilder
name.setLength(0);
do {
int rem = q % 26;
q = q / 26;
name.append((char) (rem + 65));
} while (q != 0);
name.append(attr);
ctx.addExtentIntent(Integer.toString(i), name.toString());
attr = r.nextInt(nbAttrPerGrp) + 1;
}
}
ctx.setBitSets();
return ctx;
}
/*
* ------------- FIELD ------------------
*/
/**
* A set of observations.
*/
private TreeSet<Comparable> observations;
/**
* A set of attributes.
*/
private TreeSet<Comparable> attributes;
/**
* A map to associate a set of attributes to each observation.
*/
private TreeMap<Comparable, TreeSet<Comparable>> intent;
/**
* A map to associate a set of observations to each attribute.
*/
private TreeMap<Comparable, TreeSet<Comparable>> extent;
/*
* ------------- BITSET ADDON ------------------
*/
/**
* A bit set for intent.
*/
private TreeMap<Comparable, BitSet> bitsetIntent;
/**
* A bit set for extent.
*/
private TreeMap<Comparable, BitSet> bitsetExtent;
/**
* An array for observations.
*/
private ArrayList<Comparable> arrayObservations;
/**
* An array for attributes.
*/
private ArrayList<Comparable> arrayAttributes;
/*
* ------------- CONSTRUCTORS ------------------
*/
/**
* Constructs a new empty context.
*/
public Context() {
this.init();
}
/**
* Constructs a new context as a copy of the specified context.
*
* @param context context to be copied
*/
public Context(Context context) {
this();
this.attributes.addAll(context.getAttributes());
this.observations.addAll(context.getObservations());
for (Comparable o : context.getObservations()) {
this.intent.put(o, new TreeSet(context.getIntent(o)));
}
for (Comparable a : context.getAttributes()) {
this.extent.put(a, new TreeSet(context.getExtent(a)));
}
this.setBitSets();
}
/**
* Constructs this component from the specified file.
*
* The file have to respect a certain format:
*
* The list of observations separated by a space on the first line ;
* the list of attrbutes separated by a space on the second line ;
* then, for each observations o, the list of its intent on a line, written
* like o a1 a2 ...
*
* ~~~
* Observations: 1 2 3
* Attributes: a b c d e
* 1: a c
* 2: a b
* 3: b d e
* 4: c e
* ~~~
*
* Each observation must be declared on the first line, otherwise, it is not
* added.
* Each attribute must be declared on the second line, otherwise, it is not
* added.
*
* @param filename the name of the file
*
* @throws IOException When an IOException occurs
*/
public Context(String filename) throws IOException {
this.parse(filename);
}
/**
* Initialise the context.
*
* @return this for chaining
*/
public Context init() {
this.observations = new TreeSet();
this.attributes = new TreeSet();
this.intent = new TreeMap();
this.extent = new TreeMap();
this.bitsetIntent = new TreeMap();
this.bitsetExtent = new TreeMap();
this.arrayObservations = new ArrayList();
this.arrayAttributes = new ArrayList();
return this;
}
/**
* Returns subcontext with selected obs and attr.
*
* @param obs : observations to be keeped
* @param attr : attributes to be keeped
*
* @return subcontext with selected obs and attr.
*/
public Context getSubContext(TreeSet<Comparable> obs, TreeSet<Comparable> attr) {
Context ctx = new Context();
ctx.addAllToAttributes(attr);
ctx.addAllToObservations(obs);
for (Comparable o : obs) {
for (Comparable a : attr) {
if (this.getIntent(o).contains(a)) {
ctx.addExtentIntent(o, a);
}
}
}
ctx.setBitSets();
return ctx;
}
/**
* Returns the context defining the concept lattice of arrow-closed
* subcontexts of this component.
*
* Each observation of the returned context is a $1$-generated arrow-closed
* subcontext.
* The observation used to generate the context is used as a name for the
* subcontext.
* Attributes are the same of this component, and are used to defined the
* subcontext.
*
* @return the context defining the concept lattice of arrow-closed
* subcontexts of this component.
*/
public Context getArrowClosedSubContext() {
Context result = new Context();
result.addAllToAttributes(this.getAttributes());
for (Comparable o : this.getObservations()) {
result.addToObservations(o);
TreeSet<Comparable> setO = new TreeSet<Comparable>();
setO.add(o);
Context c = this.arrowClosureObject(setO);
for (Comparable a : c.getAttributes()) {
result.addExtentIntent(o, a);
}
}
return result;
}
/**
* Returns a list of subcontexts such that the concept lattice of this
* component is obtained from a subcontext by doubling a convex.
*
* Each subcontext defines a concept lattice L. With the getDivisionConvex
* method, a convex C of this concept lattice is obtained.
* By doubling the convex set C of L, we get L[C], the concept lattice of
* this component.
*
* @return a list of subcontexts such that the concept lattice of this
* component is obtained from a subcontext by doubling a convex.
*/
public ArrayList<Context> getDivisionContext() {
Context arrowCtx = this.getArrowClosedSubContext();
arrowCtx.reverse(); // We need co-atoms which are atoms of the reverse context.
ConceptLattice clArrowClosed = arrowCtx.conceptLattice(true); // This lattice is fun :-)
Vector<TreeSet<Comparable>> coAtoms = clArrowClosed.immediateSuccessors(clArrowClosed.bottom(), arrowCtx);
// Check if the complement of coAtoms is "empty".
// Only these coAtoms are kept
ArrayList<Context> goodCoAtoms = new ArrayList<Context>();
// Be careful that the concept has been reversed
for (int i = 0; i < coAtoms.size(); i++) {
TreeSet<Comparable> attrComp = (TreeSet<Comparable>) this.getAttributes().clone(); // Initial context
TreeSet<Comparable> attr = arrowCtx.getExtent(coAtoms.get(i));
attrComp.removeAll(attr); // As arrowCtx is reversed, Extent means Intent.
TreeSet<Comparable> obsComp = (TreeSet<Comparable>) this.getObservations().clone(); // Initial context
TreeSet<Comparable> obs = this.arrowClosureObject(coAtoms.get(i)).getObservations();
obsComp.removeAll(obs);
boolean cross = false; // If there is a cross, it is not empty.
for (Comparable o : obsComp) {
for (Comparable a : attrComp) {
cross = cross || this.getIntent(o).contains(a);
}
}
if (!cross) {
Context subContext = this.getSubContext(obs, attr);
goodCoAtoms.add(subContext);
}
}
return goodCoAtoms;
}
/**
* Returns a convex set of the concept lattice of c which can be doubled to
* recover the concept lattice of this component.
*
* This method must be used with contexts returned by the
* getDivisionContext. In other cases, it is meaningless.
*
* @param ctx context from which the convex set is computed.
*
* @return a convex set of the concept lattice of c which can be doubled to
* recover the concept lattice of this component.
*/
public TreeSet<Node> getDivisionConvex(Context ctx) {
ConceptLattice factor = ctx.conceptLattice(true);
TreeSet<Node> convex = new TreeSet<Node>();
// TODO Use parameterized Node
for (Node node : (SortedSet<Node>) factor.getNodes()) {
Concept c = (Concept) node;
if (!c.getSetB().containsAll(this.getExtent(c.getSetA()))
&& !c.getSetA().containsAll(this.getIntent(c.getSetB()))) {
convex.add(node);
}
}
return convex;
}
/*
* --------------- HANDLING METHODS FOR ATTRIBUTES AND OBSERVATIONS ------------
*/
/**
* Returns the set of attributes of this component.
*
* @return the set of attributes of this component
*/
public TreeSet<Comparable> getAttributes() {
return this.attributes;
}
/**
* Checks if the specified attribute belong to this component.
*
* @param att an attribute
*
* @return true if the attribute belongs to this component
*/
public boolean containsAttribute(Comparable att) {
return this.attributes.contains(att);
}
/**
* Checks if the specified set of attributes belongs to this component.
*
* @param set set of attributes
*
* @return true if all attributes belong to this component
*/
public boolean containsAllAttributes(TreeSet<Comparable> set) {
return this.attributes.containsAll(set);
}
/**
* Adds the specified element to the set of attributes of this component.
*
* @param att an attribute
*
* @return true if the attribute was successfully added
*/
public boolean addToAttributes(Comparable att) {
if (!this.containsAttribute(att)) {
this.extent.put(att, new TreeSet<Comparable>());
}
boolean ok = this.attributes.add(att);
this.setBitSets();
return ok;
}
/**
* Adds the set of specified element to the set of attributes of this
* component.
*
* @param set set of attributes
*
* @return true if all attributes were successfully added
*/
public boolean addAllToAttributes(TreeSet<Comparable> set) {
boolean all = true;
for (Comparable att : set) {
if (!this.addToAttributes(att)) {
all = false;
}
}
this.setBitSets();
return all;
}
/**
* Removes the specified element from the set of attributes of this
* component
* and from all the intents it belongs to.
*
* @param att an attribute
*
* @return true if the attribute was successfully removed
*/
public boolean removeFromAttributes(Comparable att) {
this.extent.remove(att);
for (Comparable o : this.getObservations()) {
this.intent.get(o).remove(att);
}
boolean ok = this.attributes.remove(att);
this.setBitSets();
return ok;
}
/**
* Returns the set of observations of this component.
*
* @return the set of observations
*/
public TreeSet<Comparable> getObservations() {
return this.observations;
}
/**
* Checks if the specified observation belongs to this component.
*
* @param obs an observation
*
* @return true if the observation belongs to this component
*/
public boolean containsObservation(Comparable obs) {
return this.observations.contains(obs);
}
/**
* Checks if the specified set of observations belong to this component.
*
* @param set set of observations
*
* @return true if all the observations are in this component
*/
public boolean containsAllObservations(TreeSet<Comparable> set) {
return this.observations.containsAll(set);
}
/**
* Adds the specified element to the set of observations of this component.
*
* @param obs an observation
*
* @return true if the observation was successfully added
*/
public boolean addToObservations(Comparable obs) {
if (!this.containsObservation(obs)) {
this.intent.put(obs, new TreeSet<Comparable>());
}
boolean ok = this.observations.add(obs);
this.setBitSets();
return ok;
}
/**
* Adds the set of specified element to the set of observations of this
* component.
*
* @param set set of observations
*
* @return true if all observations were successfully added
*/
public boolean addAllToObservations(TreeSet<Comparable> set) {
boolean all = true;
for (Comparable obs : set) {
if (!this.addToObservations(obs)) {
all = false;
}
}
this.setBitSets();
return all;
}
/**
* Removes the specified element from the set of observations of this
* component.
* and from all the extents it belongs to
*
* @param obs an observation
*
* @return true if the observation was removed
*/
public boolean removeFromObservations(Comparable obs) {
this.intent.remove(obs);
for (Comparable att : this.getAttributes()) {
this.extent.get(att).remove(obs);
}
boolean ok = this.observations.remove(obs);
this.setBitSets();
return ok;
}
/**
* Set the needed structures for the bitset optimization.
* WARNING: this must be called each time your dataset change
*/
public void setBitSets() {
this.setMaps();
this.setBitSetsIntentExtent();
}
/**
* Set the mapping structure for the bitset optimization.
*/
private void setMaps() {
this.arrayAttributes = new ArrayList();
this.arrayObservations = new ArrayList();
Iterator<Comparable> i = this.attributes.iterator();
while (i.hasNext()) {
this.arrayAttributes.add(i.next());
}
i = this.observations.iterator();
while (i.hasNext()) {
this.arrayObservations.add(i.next());
}
}
/**
* Set the extent and intent structures for the bitset optimization.
*/
private void setBitSetsIntentExtent() {
this.bitsetIntent = new TreeMap();
this.bitsetExtent = new TreeMap();
Iterator<Comparable> i = this.attributes.iterator();
BitSet b = new BitSet(this.observations.size());
while (i.hasNext()) {
Comparable att = i.next();
for (Comparable c : this.extent.get(att)) {
b.set(this.arrayObservations.indexOf(c));
}
this.bitsetExtent.put(att, (BitSet) b.clone());
b.clear();
}
i = this.observations.iterator();
b = new BitSet(this.attributes.size());
while (i.hasNext()) {
Comparable obs = i.next();
for (Comparable c : this.intent.get(obs)) {
b.set(this.arrayAttributes.indexOf(c));
}
this.bitsetIntent.put(obs, (BitSet) b.clone());
b.clear();
}
}
/*
* --------------- HANDLING METHODS FOR INTENT AND EXTENT ------------
*/
/**
* Returns the set of attributes that are intent of the specified
* observation.
*
* @param obs an observation
*
* @return the set of attributes
*/
public TreeSet<Comparable> getIntent(Comparable obs) {
if (this.containsObservation(obs)) {
return this.intent.get(obs);
} else {
return new TreeSet();
}
}
/**
* Returns the set of attributes that are all intent of observations of the
* specified set.
*
* @param set set of observations
*
* @return the set of observations
*/
public TreeSet<Comparable> getIntent(TreeSet<Comparable> set) {
TreeSet<Comparable> resIntent = new TreeSet(this.getAttributes());
for (Comparable obs : set) {
resIntent.retainAll(this.getIntent(obs));
}
return resIntent;
}
/**
* Return the number of attributes that are all intent of observations of
* the specified set.
*
* @param set set of observations
*
* @return the number of attributes
*/
public int getIntentNb(TreeSet<Comparable> set) {
int size = this.getAttributes().size();
BitSet obsIntent = new BitSet(size);
obsIntent.set(0, size);
for (Comparable obs : set) {
try {
obsIntent.and(this.bitsetIntent.get(obs));
} catch (NullPointerException e) {
return 0;
}
}
return obsIntent.cardinality();
}
/**
* Checks if the second specified element is an intent of the first
* specified element.
*
* @param obs an observation
* @param att an attribute
*
* @return true if the attribute is an intent of the observation
*/
public boolean containAsIntent(Comparable obs, Comparable att) {
if (this.containsObservation(obs) && this.containsAttribute(att)) {
return this.intent.get(obs).contains(att);
} else {
return false;
}
}
/**
* Returns the set of observations that are intent of the specified
* attribute.
*
* @param att an attribute
*
* @return the set of observations
*/
public TreeSet<Comparable> getExtent(Comparable att) {
if (this.containsAttribute(att)) {
return this.extent.get(att);
} else {
return new TreeSet();
}
}
/**
* Returns the set of observations that are all intent of attributes of the
* specified set.
*
* @param set set of attributes
*
* @return the set of observations
*/
public TreeSet<Comparable> getExtent(TreeSet<Comparable> set) {
TreeSet<Comparable> attExtent = new TreeSet(this.getObservations());
for (Comparable att : set) {
attExtent.retainAll(this.getExtent(att));
}
return attExtent;
}
/**
* Return the number of observations that are all intent of attributes of
* the specified set.
*
* @param set set of attributes
*
* @return the number of observations
*/
public int getExtentNb(TreeSet<Comparable> set) {
int size = this.getObservations().size();
BitSet attExtent = new BitSet(size);
attExtent.set(0, size);
for (Comparable att : set) {
try {
attExtent.and(this.bitsetExtent.get(att));
} catch (NullPointerException e) {
return 0;
}
}
return attExtent.cardinality();
}
/**
* Checks if the second specified element is an extent of the first
* specified element.
*
* @param att an attribute
* @param obs an observation
*
* @return true if the proposition is true
*/
public boolean containAsExtent(Comparable att, Comparable obs) {
if (this.containsObservation(obs) && this.containsAttribute(att)) {
return this.extent.get(att).contains(obs);
} else {
return false;
}
}
/**
* Adds the second specified element as intent of the first one,
* and the first one as extent of the second one.
* The first one has to belong to the observations set
* and the second one to the attribute set.
*
* @param obs an observation
* @param att an attribute
*
* @return true if both were added
*/
public boolean addExtentIntent(Comparable obs, Comparable att) {
if (this.containsObservation(obs) && this.containsAttribute(att)) {
boolean ok = this.intent.get(obs).add(att) && this.extent.get(att).add(obs);
this.setBitSets();
return ok;
} else {
return false;
}
}
/**
* Removes the second specified element from the intent of the first one,
* and the first one from the extent of the second one.
* The first one has to belong to the observations set
* and the second one to the attribute set.
*
* @param obs an observation
* @param att an attribute
*
* @return true if both were removed
*/
public boolean removeExtentIntent(Comparable obs, Comparable att) {
if (this.containsObservation(obs) && this.containsAttribute(att)) {
boolean ok = this.intent.get(obs).remove(att) && this.extent.get(att).remove(obs);
this.setBitSets();
return ok;
} else {
return false;
}
}
/*
* --------------- CONTEXT HANDLING METHODS ------------
*/
/**
* Returns a String representation of this component.
* The following format is respected:
*
* The list of observations separated by a space on the first line ;
* the list of attrbutes separated by a space on the second line ;
* then, for each observations o, the list of its intent on a line, written
* like o a1 a2 ...
*
* ~~~
* Observations: 1 2 3
* Attributes: a b c d e
* 1: a c
* 2: a b
* 3: b d e
* 4: c e
* ~~~
*
* @return the string representation of this component
*
* @todo Enforce test
*/
@Override
public String toString() {
String string;
StringBuilder builder = new StringBuilder();
builder.append("Observations: ");
for (Comparable o : this.observations) {
// first line : All observations separated by a space
// a StringTokenizer is used to delete spaces in the
// string description of each observation
string = o.toString();
if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
}
builder.append(string).append(" ");
}
String newLine = System.getProperty("line.separator");
builder.append(newLine).append("Attributes: ");
for (Comparable a : this.attributes) {
// second line : All attributes separated by a space
// a StringTokenizer is used to delete spaces in the
// string description of each observation
string = a.toString();
if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
}
builder.append(string).append(" ");
}
// next lines : All intents of observations, one on each line:
// observation : list of attributes
// a StringTokenizer is used to delete spaces in the
// string description of each observation and attributes
builder.append(newLine);
for (Comparable o : this.observations) {
string = o.toString();
if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
}
builder.append(string).append(": ");
for (Comparable a : this.getIntent(o)) {
string = a.toString();
if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
}
builder.append(string).append(" ");
}
builder.append(newLine);
}
return builder.toString();
}
/**
* Save the description of this component in a file whose name is specified.
*
* @param filename the name of the file
*
* @throws IOException When an IOException occurs
*/
public void save(final String filename) throws IOException {
Filer.getInstance().save(this, ContextIOFactory.getInstance(), filename);
}
/**
* Parse the description of this component from a file whose name is
* specified.
*
* @param filename the name of the file
*
* @return this for chaining
*
* @throws IOException When an IOException occurs
*/
public Context parse(final String filename) throws IOException {
this.init();
Filer.getInstance().parse(this, ContextIOFactory.getInstance(), filename);
return this;
}
/**
* Removes from this component reducible attributes.
*
* Reducible attributes are attributes equivalent by closure to others
* attributes.
* They are computed by `getReducibleElements` od `ClosureSystem` in
* O(|A|^3|O|)
*
* @return the set of reducibles removed attributes, with their equivalent
* attributes
*/
public TreeMap<Comparable, TreeSet<Comparable>> attributesReduction() {
// compute the reducible elements
TreeMap red = this.getReducibleElements();
// remove the reducible elements from the attributes set
for (Object att : red.keySet()) {
this.removeFromAttributes((Comparable) att);
}
return red;
}
/**
* Removes from this component reducible observations.
*
* Reducible observations are attributes equivalent by closure to others
* observations.
* They are computed by `getReducibleElements` od `ClosureSystem`
* applied on the reverse context in O(|O|^3|A|)
*
* @return the set of reducibles removed attributes, with their equivalent
* attributes
*/
public TreeMap<Comparable, TreeSet<Comparable>> observationsReduction() {
// compute the reducible elements of the reverse context
this.reverse();
TreeMap red = this.getReducibleElements();
this.reverse();
// remove the reducible elements from the observations set
for (Object att : red.keySet()) {
this.removeFromObservations((Comparable) att);
}
return red;
}
/**
* Removes from this component reducible attributes and observations.
*
* They are computed by `attributesReduction` then
* `observationsReduction` in O(|A|^3|O|+|O|^3|A|)
*
* @return the set of reducibles removed attributes and observations with
* their equivalent elements
*/
public TreeMap<Comparable, TreeSet<Comparable>> reduction() {
TreeMap<Comparable, TreeSet<Comparable>> red = this.attributesReduction();
red.putAll(this.observationsReduction());
return red;
}
/**
* Reverses this component by replacing attributes by observations and
* observations by
* attributes. Intent and extent are exchanged in the same way.
*/
public void reverse() {
TreeSet<Comparable> tmp = this.attributes;
this.attributes = this.observations;
this.observations = tmp;
TreeMap<Comparable, TreeSet<Comparable>> sauv = this.intent;
this.intent = this.extent;
this.extent = sauv;
}
/**
* Return a new reversed Context.
*
* @return a new reversed Context
*/
public Context getReverseContext() {
Context context = new Context(this);
context.reverse();
context.setBitSets();
return context;
}
/**
* Returns the arrow-closed subcontext of this component containing obs.
*
* A sub-context (H,N) of (G,M) is arrow-closed if :
* 1. For all h in H, h uparrow m implies m in N and
* 2. For all n in N, g downarrow n implies g in H
*
* @param obs set of observations to keep
*
* @return the arrow-closed subcontext of this component containing obs.
*/
public Context arrowClosureObject(TreeSet<Comparable> obs) {
ConceptLattice cl = this.getReverseContext().conceptLattice(true); // Where is bug with it ^^
ArrowRelation ar = cl.getArrowRelation();
/*
WARNING : this component contains "observations" and "attributes"
whereas following contexts, down and up, are made of concept.
*/
Context down = ar.getDoubleDownArrowTable();
Context up = ar.getDoubleUpArrowTable();
Context ctx = new Context();
ctx.addAllToObservations(obs);
int sizeObs = ctx.getObservations().size();
int sizeAttr = ctx.getAttributes().size();
int prevObs = 0;
int prevAttr = 0;
while ((prevObs < sizeObs) || (prevAttr < sizeAttr)) {
for (Comparable o : ctx.getObservations()) {
// Concept corresponding to observation o
TreeSet<Comparable> setBo = this.getIntent(o);
TreeSet<Comparable> setAo = this.getExtent(setBo);
Concept cptO = new Concept(setAo, setBo);
TreeSet<Comparable> attrUp = up.getIntent(cl.getNode(cptO)); // Doesn't work with up.getIntent(cptO) ...
for (Comparable a : this.getAttributes()) { // NOT GOOD for complexity :-(
// Try to find attributes in up-arrow relation
TreeSet<Comparable> setAa = this.getExtent(a);
TreeSet<Comparable> setBa = this.getIntent(setAa);
Concept cptA = new Concept(setAa, setBa); // Concept corresponding to attribute a
if (attrUp.contains(cl.getNode(cptA))) {
ctx.addToAttributes(a);
}
}
}
for (Comparable a : ctx.getAttributes()) {
// Concept corresponding to observation a
TreeSet<Comparable> setAa = this.getExtent(a);
TreeSet<Comparable> setBa = this.getIntent(setAa);
Concept cptA = new Concept(setAa, setBa);
TreeSet<Comparable> obsDown = down.getExtent(cl.getNode(cptA));
for (Comparable o : this.getObservations()) {
// Try to find attributes in down-arrow relation
TreeSet<Comparable> setBo = this.getIntent(o);
TreeSet<Comparable> setAo = this.getExtent(setBo);
Concept cptO = new Concept(setAo, setBo); // Concept corresponding to attribute o
if (obsDown.contains(cl.getNode(cptO))) {
ctx.addToObservations(o);
}
}
}
prevObs = sizeObs;
prevAttr = sizeAttr;
sizeObs = ctx.getObservations().size();
sizeAttr = ctx.getAttributes().size();
}
return this.getSubContext(ctx.getObservations(), ctx.getAttributes());
}
/**
* Returns the arrow-closed subcontext of this component containing attr.
*
* A sub-context (H,N) of (G,M) is arrow-closed if :
* 1. For all h in H, h uparrow m implies m in N and
* 2. For all n in N, g downarrow n implies g in H
*
* @param attr set of attributes to keep
*
* @return the arrow-closed subcontext of this component containing attr.
*/
public Context arrowClosureAttribute(TreeSet<Comparable> attr) {
ConceptLattice cl = this.getReverseContext().conceptLattice(true); // Where is bug with it ^^
ArrowRelation ar = cl.getArrowRelation();
Context down = ar.getDoubleDownArrowTable();
Context up = ar.getDoubleUpArrowTable();
Context ctx = new Context();
ctx.addAllToAttributes(attr);
int sizeObs = ctx.getObservations().size();
int sizeAttr = ctx.getAttributes().size();
int prevObs = 0;
int prevAttr = 0;
while ((prevObs < sizeObs) || (prevAttr < sizeAttr)) {
for (Comparable a : ctx.getAttributes()) {
// Concept corresponding to observation a
TreeSet<Comparable> setAa = this.getExtent(a);
TreeSet<Comparable> setBa = this.getIntent(setAa);
Concept cptA = new Concept(setAa, setBa);
TreeSet<Comparable> obsDown = down.getExtent(cl.getNode(cptA));
for (Comparable o : this.getObservations()) {
// Try to find attributes in down-arrow relation
TreeSet<Comparable> setBo = this.getIntent(o);
TreeSet<Comparable> setAo = this.getExtent(setBo);
Concept cptO = new Concept(setAo, setBo); // Concept corresponding to attribute o
if (obsDown.contains(cl.getNode(cptO))) {
ctx.addToObservations(o);
}
}
}
for (Comparable o : ctx.getObservations()) {
// Concept corresponding to observation o
TreeSet<Comparable> setBo = this.getIntent(o);
TreeSet<Comparable> setAo = this.getExtent(setBo);
Concept cptO = new Concept(setAo, setBo);
TreeSet<Comparable> attrUp = up.getIntent(cl.getNode(cptO)); // Doesn't work with up.getIntent(cptO) ...
for (Comparable a : this.getAttributes()) { // NOT GOOD for complexity :-(
// Try to find attributes in up-arrow relation
TreeSet<Comparable> setAa = this.getExtent(a);
TreeSet<Comparable> setBa = this.getIntent(setAa);
Concept cptA = new Concept(setAa, setBa); // Concept corresponding to attribute a
if (attrUp.contains(cl.getNode(cptA))) {
ctx.addToAttributes(a);
}
}
}
prevObs = sizeObs;
prevAttr = sizeAttr;
sizeObs = ctx.getObservations().size();
sizeAttr = ctx.getAttributes().size();
}
return this.getSubContext(ctx.getObservations(), ctx.getAttributes());
}
/*
* --------------- IMPLEMENTATION OF CLOSURE SYSTEM ABSTRACT METHODS ------------
*/
/*
* --------------- AND CONCEPT LATTICE GENERATION------------
*/
/**
* Returns the set of attributes as elements set used by the lattice
* generator abstract class
* to generate closed set lattice on attributes. The closed set lattice on
* abservations can
* be otained using the reverse method of this class.
*
* @return the set of attributes
*/
@Override
public TreeSet<Comparable> getSet() {
return this.attributes;
}
/**
* Builds the closure of a set X of attributes.
*
* The closure corresponds to the maximal set of attributes having the
* same intent as the specified one.
*
* This treatment is performed in O(|A||O|)
*
* @param set a TreeSet of indexed elements
*
* @return the closure of the set for this component
*/
@Override
public TreeSet<Comparable> closure(TreeSet<Comparable> set) {
return this.getIntent(this.getExtent(set));
}
/**
* Returns the set of union of observations that are intent with one of
* attributes of the specified set.
*
* @param set a specified set
*
* @return the set of union of observations
*/
public TreeSet<Comparable> getExtentUnion(TreeSet<Comparable> set) {
TreeSet<Comparable> ext = new TreeSet();
for (Comparable att : set) {
for (Comparable obs : this.getExtent(att)) {
if (this.containAsExtent(att, obs) && !ext.contains(obs)) {
ext.add(obs);
}
}
}
return ext;
}
/**
* Builds the inverse of the closure operator of a set of observations.
*
* The inverse closure corresponds to the maximal set of observations having
* the
* same intent as the specified one.
* This treatment is performed in O(|A||O|)
*
* @param set a TreeSet of indexed elements
*
* @return the closure of the set for this component
*/
public ComparableSet inverseClosure(ComparableSet set) {
return new ComparableSet(this.getExtent(this.getIntent((TreeSet) set)));
}
/**
* Returns the concept 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
*
* The closed set lattice is first generated using
* `ConceptLattice closedSetLattice (boolean diagram)`
* Then, nodes of the lattice are completed as concepts.
*
* @param diagram a boolean indicating if the Hasse diagramm of the lattice
* is computed or not.
*
* @return The concept lattice induced by this component
*/
public ConceptLattice conceptLattice(boolean diagram) {
ConceptLattice csl = this.closedSetLattice(diagram);
// TreeMap<Concept, Concept> nodes = new TreeMap<Concept, Concept>();
for (Object node : csl.getNodes()) {
Concept cl = (Concept) node;
cl.putSetB(new ComparableSet(this.getExtent(cl.getSetA())));
}
return csl;
}
/**
* Reccursively generates nodes of the product lattice.
*
* @param c couple to be completed
* @param clParts list of last context to deal with
*
* @return a list of nodes to add to the product.
*/
private ArrayList<Couple> recursiveGenProd(Couple c, LinkedList<ConceptLattice> clParts) {
LinkedList<ConceptLattice> copy = (LinkedList<ConceptLattice>) clParts.clone();
if (copy.isEmpty()) {
ArrayList<Couple> result = new ArrayList<Couple>();
result.add(c);
return result;
} else {
ConceptLattice cl = (ConceptLattice) copy.poll();
ArrayList<Couple> nodes = new ArrayList<Couple>();
for (Object node : cl.getNodes()) {
ArrayList<Concept> listCopy = new ArrayList<Concept>();
for (Concept cpt : (ArrayList<Concept>) c.getLeft()) {
listCopy.add(cpt);
}
Couple coupleCopy = new Couple(listCopy, c.getRight());
((ArrayList<Concept>) coupleCopy.getLeft()).add((Concept) node);
nodes.addAll(recursiveGenProd(coupleCopy, copy));
}
return nodes;
}
}
/**
* Returns the concept lattice of this component represented as a subdirect
* product of its irreductibles components.
*
* WARNING : Context MUST BE REDUCED !
*
* @return concept Lattice of this component represented as a subdirect
* product of its irreductibles components.
*/
public Lattice subDirectDecomposition() {
// First, compute 1-generated arrow-closed subcontextes
ArrayList<Context> parts = new ArrayList<Context>();
for (Comparable o : this.getObservations()) {
TreeSet<Comparable> setO = new TreeSet<Comparable>();
setO.add(o);
parts.add(this.arrowClosureObject(setO));
}
// Second, remove contexts contained in other. They are dispendable.
// Remove first all contexts that appeared at least twice.
ArrayList<Context> single = new ArrayList<Context>();
for (int i = 0; i < parts.size(); i++) {
boolean containedNext = false;
for (int j = i + 1; j < parts.size(); j++) {
containedNext = containedNext || (parts.get(i).containsAllObservations(parts.get(j).getObservations())
&& parts.get(j).containsAllObservations(parts.get(i).getObservations())
&& parts.get(i).containsAllAttributes(parts.get(j).getAttributes())
&& parts.get(j).containsAllAttributes(parts.get(i).getAttributes()));
}
if (!containedNext) {
single.add(parts.get(i));
}
}
parts = single;
ArrayList<Context> toBeRemoved = new ArrayList<Context>();
for (Context remove : parts) {
for (Context test : parts) {
if ((parts.indexOf(test) != parts.indexOf(remove))
&& (test.containsAllObservations(remove.getObservations()))
&& (test.containsAllAttributes(remove.getAttributes()))) {
toBeRemoved.add(remove);
}
}
}
parts.removeAll(toBeRemoved);
// Third, compute the product but can't use LatticeFactory.product :-(
/*
* Content of each node is of the following form :
* 1. They are Couple
* 2. Left part is an ArrayList corresponding to the terms of the product
* 3. Right part is a boolean, true if the node is inside the sub-product.
* Thus we have : the full product, and nodes of the subproduct marked
*/
// First compute all nodes of the product
LinkedList<ConceptLattice> clParts = new LinkedList<ConceptLattice>();
for (Context ctx : parts) {
clParts.add(ctx.conceptLattice(true));
}
Lattice prod = new Lattice();
// Computes nodes
ArrayList<Couple> nodes = new ArrayList<Couple>();
LinkedList<ConceptLattice> copy = (LinkedList<ConceptLattice>) clParts.clone();
ConceptLattice firstCL = (ConceptLattice) copy.poll();
for (Object node : firstCL.getNodes()) {
Couple couple = new Couple(new ArrayList<Concept>(), false);
ArrayList<Concept> prodCPT = new ArrayList<Concept>();
prodCPT.add((Concept) node);
couple.setLeft(prodCPT);
nodes.addAll(recursiveGenProd(couple, copy));
}
for (Couple c : nodes) {
prod.addNode(new Node(c));
}
// Add edges
for (Object source : prod.getNodes()) {
for (Object target : prod.getNodes()) {
Couple contentSource = (Couple) ((Node) source).getContent();
Couple contentTarget = (Couple) ((Node) target).getContent();
boolean haveEdge = true;
boolean equals = true;
for (int i = 0; i < clParts.size(); i++) { // clParts.size() is the number of factor
Concept cptSource = ((ArrayList<Concept>) contentSource.getLeft()).get(i);
Concept cptTarget = ((ArrayList<Concept>) contentTarget.getLeft()).get(i);
equals = equals && cptSource.equals(cptTarget);
haveEdge = haveEdge && (clParts.get(i).containsEdge(cptSource, cptTarget) || cptSource.equals(cptTarget));
}
if (haveEdge && !equals) {
prod.addEdge(((Node) source), ((Node) target));
}
}
}
prod.transitiveReduction();
// Last, identify the sub-product, e.g. nodes of this component in the product.
// In the subdirect decomposition, if (A,B) is a concept then (A \cap H,B \cap N) also.
// Transform nodes of the original lattice into nodes of the subproduct lattice and mark them
ConceptLattice cl = this.conceptLattice(true);
for (Object cpt : cl.getNodes()) {
// Compute cpt representation in prod
ArrayList<Concept> subCpt = new ArrayList<Concept>();
for (int i = 0; i < parts.size(); i++) {
Context ctx = parts.get(i);
ConceptLattice term = clParts.get(i);
ComparableSet setA = new ComparableSet();
setA.addAll(((Concept) cpt).getSetA());
ComparableSet setB = new ComparableSet();
setB.addAll(((Concept) cpt).getSetB());
setA.retainAll(ctx.getAttributes());
setB.retainAll(ctx.getObservations());
subCpt.add(term.getConcept((ComparableSet) setA, (ComparableSet) setB));
}
// Check if cpt is in prod
for (Object nodeProd : prod.getNodes()) {
if (((Couple) ((Node) nodeProd).getContent()).getLeft().equals(subCpt)) {
((Couple) ((Node) nodeProd).getContent()).setRight(true);
}
}
}
return prod;
}
/**
* Returns the closed set iceberg of this component.
*
* The Hasse diagramm of the iceberg is computed (i.e. it is transitively
* reduced)
* until the support of the closed set is less than the support value.
*
* @param support a threshold, between 0 and 1, for a closed set to be part
* of the iceberg.
*
* @return The concept iceberg
*/
public ConceptLattice closedSetIceberg(double support) {
return ConceptLattice.diagramIceberg(this, support);
}
/**
* Returns the lattice of this component.
*
* @return The lattice induced by this component
*/
@Override
public ConceptLattice lattice() {
return this.conceptLattice(true);
}
}