ImplicationalSystem.java
package org.thegalactic.rule;
/*
* ImplicationalSystem.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.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import org.thegalactic.dgraph.ConcreteDGraph;
import org.thegalactic.dgraph.Edge;
import org.thegalactic.dgraph.Node;
import org.thegalactic.io.Filer;
import org.thegalactic.lattice.ClosureSystem;
import org.thegalactic.lattice.io.ImplicationalSystemIOFactory;
import org.thegalactic.util.ComparableSet;
/**
* This class gives a representation for an implicational system
* (ImplicationalSystem), a set of rules.
*
* An ImplicationalSystem is composed of a TreeSet of comparable elements, and a
* TreeSet of rules defined by class {@link Rule}.
*
* This class provides methods implementing classical transformation of an
* implicational system : make proper, make minimum, make right maximal, make
* left minimal, make unary, make canonical basis, make canonical direct basis
* and reduction.
*
* An implicational system 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 an ImplicationalSystem can be generated
* by invoking method {@link #closedSetLattice} of a closure system.
*
* An implicational system can be instancied from and save to a text file in the
* following format: - a list of elements separated by a space in the first line
* ; - then, each rule on a line, written like [premise] -> [conclusion] where
* elements are separated by a space.
*
* ~~~
* a b c d e
* a b -> c d
* c d -> e
* ~~~
*
* 
*
* @uml ImplicationalSystem.png
* !include resources/org/thegalactic/lattice/ImplicationalSystem.iuml
* !include resources/org/thegalactic/lattice/ClosureSystem.iuml
*
* hide members
* show ImplicationalSystem members
* class ImplicationalSystem #LightCyan
* title ImplicationalSystem UML graph
*/
public class ImplicationalSystem extends ClosureSystem {
/*
* --------------- FIELDS -----------------
*/
/**
* Generates a random ImplicationalSystem with a specified number of nodes
* and rules.
*
* @param nbS the number of nodes of the generated ImplicationalSystem
* @param nbR the number of rules of the generated ImplicationalSystem
*
* @return a random implicational system with a specified number of nodes
* and rules.
*/
public static ImplicationalSystem random(int nbS, int nbR) {
ImplicationalSystem sigma = new ImplicationalSystem();
// addition of elements
for (int i = 0; i < nbS; i++) {
sigma.addElement(Integer.valueOf(i));
}
// addition of rules
//for (int i = 0; i < nbR; i++) { One could get twice the same rule ...
while (sigma.getRules().size() < nbR) {
ComparableSet conclusion = new ComparableSet();
int choice = (int) Math.rint(nbS * Math.random());
int j = 1;
for (Comparable c : sigma.getSet()) {
if (j == choice) {
conclusion.add(c);
}
j++;
}
ComparableSet premisse = new ComparableSet();
for (Comparable c : sigma.getSet()) {
choice = (int) Math.rint(nbS * Math.random());
if (choice < nbS / 5) {
premisse.add(c);
}
}
//if (!premisse.isEmpty()) {
sigma.addRule(new Rule(premisse, conclusion));
//}
}
return sigma;
}
/**
* For the implicational rules of this component.
*/
private TreeSet<Rule> sigma;
/**
* For the elements space of this component.
*/
private TreeSet<Comparable> set;
/*
* --------------- CONSTRUCTORS -----------
*/
/**
* Constructs a new empty component.
*/
public ImplicationalSystem() {
this.init();
}
/**
* Constructs this component from the specified set of rules `sigma`.
*
* @param sigma the set of rules.
*/
public ImplicationalSystem(Collection<Rule> sigma) {
this.sigma = new TreeSet<Rule>(sigma);
this.set = new TreeSet<Comparable>();
for (Rule rule : this.sigma) {
set.addAll(rule.getPremise());
set.addAll(rule.getConclusion());
}
}
/**
* Constructs this component as a copy of the specified ImplicationalSystem
* `is`.
*
* Only structures (conataining reference of indexed elements) are copied.
*
* @param is the implicational system to be copied
*/
public ImplicationalSystem(ImplicationalSystem is) {
this.sigma = new TreeSet<Rule>(is.getRules());
this.set = new TreeSet<Comparable>(is.getSet());
}
/**
* Constructs this component from the specified file.
*
* The file have to respect a certain format:
*
* An implicational system can be instancied from and save to a text file in
* the following format: - A list of elements separated by a space in the
* first line ; - then, each rule on a line, written like [premise] ->
* [conclusion] where elements are separated by a space.
*
* ~~~
* a b c d e a b -> c d c d -> e
* ~~~
*
* Each element must be declared on the first line, otherwise, it is not
* added in the rule Each rule must have a non empty concusion, otherwise,
* it is not added in the component
*
* @param filename the name of the file
*
* @throws IOException When an IOException occurs
*/
public ImplicationalSystem(String filename) throws IOException {
this.parse(filename);
}
/**
* Initialise the implicational system.
*
* @return this for chaining
*/
public ImplicationalSystem init() {
this.sigma = new TreeSet<Rule>();
this.set = new TreeSet<Comparable>();
return this;
}
/*
* ------------- ACCESSORS METHODS ------------------
*/
/**
* Returns the set of rules.
*
* @return the set of rules of this component.
*/
public SortedSet<Rule> getRules() {
return Collections.unmodifiableSortedSet((SortedSet<Rule>) this.sigma);
}
/**
* Returns the set of indexed elements.
*
* @return the elements space of this component.
*/
public SortedSet<Comparable> getSet() {
return Collections.unmodifiableSortedSet((SortedSet<Comparable>) this.set);
}
/**
* Returns the number of elements in the set S of this component.
*
* @return the number of elements in the elements space of this component.
*/
public int sizeElements() {
return this.set.size();
}
/**
* Returns the number of rules of this component.
*
* @return the number of rules of this component.
*/
public int sizeRules() {
return this.sigma.size();
}
/*
* ------------- MODIFICATION METHODS ------------------
*/
/**
* Adds the specified element to the set `S` of this component.
*
* @param e the comparable to be added
*
* @return true if the element has been added to `S`
*/
public boolean addElement(Comparable e) {
return set.add(e);
}
/**
* Adds the specified element to the set `S` of this component.
*
* @param x the treeset of comparable to be added
*
* @return true if the element has been added to `S`
*/
public boolean addAllElements(TreeSet<Comparable> x) {
boolean all = true;
for (Comparable e : x) {
if (!set.add(e)) {
all = false;
}
}
return all;
}
/**
* Delete the specified element from the set `S` of this component and from
* all the rule containing it.
*
* @param e the comparable to be added
*
* @return true if the element has been added to `S`
*/
public boolean deleteElement(Comparable e) {
if (set.contains(e)) {
set.remove(e);
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule : save.sigma) {
Rule newR = new Rule(rule.getPremise(), rule.getConclusion());
newR.removeFromPremise(e);
newR.removeFromConclusion(e);
if (!rule.equals(newR)) {
if (newR.getConclusion().size() != 0) {
this.replaceRule(rule, newR);
} else {
this.removeRule(rule);
}
}
}
return true;
}
return false;
}
/**
* Checks if the set S of this component contains the elements of the
* specified rule.
*
* @param rule the rule to be checked
*
* @return true if `S` contains all the elements of the rule
*/
public boolean checkRuleElements(Rule rule) {
for (Object e : rule.getPremise()) {
if (!set.contains(e)) {
return false;
}
}
for (Object e : rule.getConclusion()) {
if (!set.contains(e)) {
return false;
}
}
return true;
}
/**
* Checks if this component already contains the specified rule.
*
* Rules are compared according to their premise and conclusion
*
* @param rule the rule to be tested
*
* @return true if `sigma` contains the rule
*/
public boolean containsRule(Rule rule) {
return this.sigma.contains(rule);
}
/**
* Adds the specified rule to this component.
*
* @param rule the rule to be added
*
* @return true the rule has been added to if `sigma`
*/
public boolean addRule(Rule rule) {
if (!this.containsRule(rule) && this.checkRuleElements(rule)) {
return this.sigma.add(rule);
}
return false;
}
/**
* Removes the specified rule from the set of rules of this component.
*
* @param rule the rule to be removed
*
* @return true if the rule has been removed
*/
public boolean removeRule(Rule rule) {
return this.sigma.remove(rule);
}
/**
* Replaces the first specified rule by the second one.
*
* @param rule1 the rule to be replaced by `rule2`
* @param rule2 the replacing rule
*
* @return true the rule has been replaced
*/
public boolean replaceRule(Rule rule1, Rule rule2) {
return this.removeRule(rule1) && this.addRule(rule2);
}
/*
* ----------- SAVING METHODS --------------------
*/
/**
* Returns a string representation of this component.
*
* The following format is used:
*
* An implicational system can be instancied from and save to a text file in
* the following format:
* - A list of elements separated by a space in the first line ;
* - then, each rule on a line, written like [premise] -> [conclusion] where
* elements are separated by a space.
*
* ~~~
* a b c d e
* a b -> c
* d c d -> e
* ~~~
*
* @return a string representation of this component.
*/
@Override
public String toString() {
StringBuilder s = new StringBuilder();
// first line : All elements of S separated by a space
// a StringTokenizer is used to delete spaces in the
// string description of each element of S
for (Comparable e : this.set) {
StringTokenizer st = new StringTokenizer(e.toString());
while (st.hasMoreTokens()) {
s.append(st.nextToken());
}
s.append(" ");
}
String newLine = System.getProperty("line.separator");
s.append(newLine);
// next lines : a rule on each line, described by:
// [elements of the premise separated by a space] -> [elements of the conclusion separated by a space]
for (Rule rule : this.sigma) {
s.append(rule.toString()).append(newLine);
}
return s.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, ImplicationalSystemIOFactory.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 ImplicationalSystem parse(final String filename) throws IOException {
this.init();
Filer.getInstance().parse(this, ImplicationalSystemIOFactory.getInstance(), filename);
return this;
}
/*
* ----------- PROPERTIES TEST METHODS --------------------
*/
/**
* Returns true if this component is a proper ImplicationalSystem.
*
* This test is perfomed in O(|Sigma||S|) by testing conclusion of each rule
*
* @return true if and only if this component is a proper implicational
* system.
*/
public boolean isProper() {
for (Rule rule : this.sigma) {
for (Object c : rule.getConclusion()) {
if (rule.getPremise().contains(c)) {
return false;
}
}
}
return true;
}
/**
* Returns true if this component is an unary ImplicationalSystem.
*
* This test is perfomed in O(|Sigma||S|) by testing conclusion of each rule
*
* @return true if this component is an unary ImplicationalSystem.
*/
public boolean isUnary() {
for (Rule rule : this.sigma) {
if (rule.getConclusion().size() > 1) {
return false;
}
}
return true;
}
/**
* Returns true if this component is a compact ImplicationalSystem.
*
* This test is perfomed in O(|Sigma|^2|S|) by testing premises of each pair
* of rules
*
* @return true if this component is a compact ImplicationalSystem.
*/
public boolean isCompact() {
for (Rule rule1 : this.sigma) {
for (Rule rule2 : this.sigma) {
if (!rule1.equals(rule2) && rule1.getPremise().equals(rule2.getPremise())) {
return false;
}
}
}
return true;
}
/**
* Returns true if conclusion of rules of this component are closed.
*
* This test is perfomed in O(|Sigma||S|) by testing conclusion of each rule
*
* @return true if conclusion of rules of this component are closed.
*/
public boolean isRightMaximal() {
for (Rule rule : this.sigma) {
if (!rule.getConclusion().containsAll(this.closure(rule.getConclusion()))) {
return false;
}
}
return true;
}
/**
* Returns true if this component is left minimal.
*
* This test is perfomed in O(|Sigma|^2|S|) by testing conclusions of each
* pair of rules
*
* @return true if this component is left minimal.
*/
public boolean isLeftMinimal() {
for (Rule rule1 : this.sigma) {
for (Rule rule2 : this.sigma) {
if (!rule1.equals(rule2)
&& rule1.getPremise().containsAll(rule2.getPremise())
&& rule1.getConclusion().equals(rule2.getConclusion())) {
return false;
}
}
}
return true;
}
/**
* Returns true if this component is direct.
*
* This test is perfomed in O(|Sigma|^2|S|) by testing if closure of the
* premisse of each conclusion can be obtained by only one iteration on the
* set of rules.
*
* @return true if this component is direct.
*/
public boolean isDirect() {
for (Rule rule1 : this.sigma) {
TreeSet<Comparable> onePass = new TreeSet(rule1.getPremise());
for (Rule rule2 : this.sigma) {
if (rule1.getPremise().containsAll(rule2.getPremise())) {
onePass.addAll(rule2.getConclusion());
}
}
if (!onePass.equals(this.closure(rule1.getPremise()))) {
return false;
}
}
return true;
}
/**
* Returns true if this component is minimum.
*
* This test is perfomed in O(|Sigma|^2|S|) by testing if closure of the
* premisse of each conclusion can be obtained by only one iteration on the
* set of rules.
*
* @return true if this component is minimum.
*/
public boolean isMinimum() {
ImplicationalSystem tmp = new ImplicationalSystem(this);
tmp.makeRightMaximal();
for (Rule rule : sigma) {
ImplicationalSystem epsilon = new ImplicationalSystem(tmp);
epsilon.removeRule(rule);
TreeSet<Comparable> clThis = this.closure(rule.getPremise());
TreeSet<Comparable> clEpsilon = epsilon.closure(rule.getPremise());
if (clThis.equals(clEpsilon)) {
return false;
}
}
return true;
}
/**
* Returns true if this component is equal to its canonical direct basis.
*
* The canonical direct basis is computed before to be compare with this
* component.
*
* This test is performed in O(d|S|), where d corresponds to the number of
* rules that have to be added by the direct treatment. This number is
* exponential in the worst case.
*
* @return true if this component is equal to its canonical direct basis.
*/
public boolean isCanonicalDirectBasis() {
ImplicationalSystem cdb = new ImplicationalSystem(this);
cdb.makeCanonicalDirectBasis();
return this.isIncludedIn(cdb) && cdb.isIncludedIn(this);
}
/**
* Returns true if this component is equal to its canonical basis.
*
* The canonical basis is computed before to be compare with this component.
*
* This treatment is performed in (|Sigma||S|cl) where O(cl) is the
* computation of a closure.
*
* @return true if this component is equal to its canonical basis.
*/
public boolean isCanonicalBasis() {
ImplicationalSystem cb = new ImplicationalSystem(this);
cb.makeCanonicalBasis();
return this.isIncludedIn(cb) && cb.isIncludedIn(this);
}
/**
* Compares by inclusion of the proper and unary form of this component with
* the specified one.
*
* @param is another ImplicationalSystem
*
* @return true if really include in this componenet.
*/
public boolean isIncludedIn(ImplicationalSystem is) {
ImplicationalSystem tmp = new ImplicationalSystem(this);
tmp.makeProper();
tmp.makeUnary();
is.makeProper();
is.makeUnary();
for (Rule rule : tmp.sigma) {
if (!is.containsRule(rule)) {
return false;
}
}
return true;
}
/*
* ----------- PROPERTIES MODIFICATION METHODS --------------------
*/
/**
* Makes this component a proper ImplicationalSystem.
*
* Elements that are at once in the conclusion and in the premise are
* deleted from the conclusion. When the obtained conclusion is an empty
* set, the rule is deleted from this component
*
* This treatment is performed in O(|Sigma||S|).
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeProper() {
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule : save.sigma) {
// deletes elements of conclusion which are in the premise
Rule newR = new Rule(rule.getPremise(), rule.getConclusion());
for (Object e : rule.getConclusion()) {
if (newR.getPremise().contains(e)) {
newR.removeFromConclusion(e);
}
}
// replace the rule by the new rule is it has been modified
if (!rule.equals(newR)) {
this.replaceRule(rule, newR);
}
// delete rule with an empty conclusion
if (newR.getConclusion().isEmpty()) {
this.removeRule(newR);
}
}
return save.sizeRules() - this.sizeRules();
}
/**
* Makes this component an unary ImplicationalSystem.
*
* This treatment is performed in O(|Sigma||S|)
*
* A rule with a non singleton as conclusion is replaced with a sets of
* rule, one rule for each element of the conclusion.
*
* This treatment is performed in O(|Sigma||S|).
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeUnary() {
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule : save.sigma) {
if (rule.getConclusion().size() > 1) {
this.removeRule(rule);
TreeSet<Comparable> conclusion = rule.getConclusion();
TreeSet<Comparable> premise = rule.getPremise();
for (Comparable e : conclusion) {
TreeSet<Comparable> newC = new TreeSet();
newC.add(e);
Rule newRule = new Rule(premise, newC);
this.addRule(newRule);
}
}
}
return save.sizeRules() - this.sizeRules();
}
/**
* Replaces rules of same premise by only one rule.
*
* This treatment is performed in O(|sigma|^2|S|)
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeCompact() {
ImplicationalSystem save = new ImplicationalSystem(this);
int before = this.sigma.size();
this.sigma = new TreeSet();
while (save.sigma.size() > 0) {
Rule rule1 = save.sigma.first();
ComparableSet newConc = new ComparableSet();
Iterator<Rule> it2 = save.sigma.iterator();
while (it2.hasNext()) {
Rule rule2 = it2.next();
if (!rule1.equals(rule2) && rule1.getPremise().equals(rule2.getPremise())) {
newConc.addAll(rule2.getConclusion());
it2.remove();
}
}
if (newConc.size() > 0) {
newConc.addAll(rule1.getConclusion());
Rule newR = new Rule(rule1.getPremise(), newConc);
this.addRule(newR);
} else {
this.addRule(rule1);
}
save.removeRule(rule1);
}
return before - this.sigma.size();
}
/**
* Replaces association rules of same premise, same support and same
* confidence by only one rule.
*
* This treatment is performed in O(|sigma|^2|S|)
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeCompactAssociation() {
ImplicationalSystem save = new ImplicationalSystem(this);
int before = this.sigma.size();
this.sigma = new TreeSet();
while (save.sigma.size() > 0) {
AssociationRule rule1 = (AssociationRule) save.sigma.first();
ComparableSet newConc = new ComparableSet();
Iterator<Rule> it2 = save.sigma.iterator();
while (it2.hasNext()) {
AssociationRule rule2 = (AssociationRule) it2.next();
if (!rule1.equals(rule2) && rule1.getPremise().equals(rule2.getPremise())
&& rule1.getConfidence() == rule2.getConfidence() && rule1.getSupport() == rule2.getSupport()) {
newConc.addAll(rule2.getConclusion());
it2.remove();
}
}
if (newConc.size() > 0) {
newConc.addAll(rule1.getConclusion());
AssociationRule newR = new AssociationRule(rule1.getPremise(), newConc, rule1.getSupport(), rule1.getConfidence());
this.addRule(newR);
} else {
this.addRule(rule1);
}
save.removeRule(rule1);
}
return before - this.sigma.size();
}
/**
* Replaces conclusion of each rule with their closure without the premise.
*
* This treatment is performed in O(|sigma||S|cl), where O(cl) is the
* computation of a closure.
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeRightMaximal() {
int s = this.sizeRules();
this.makeCompact();
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule : save.sigma) {
Rule newR = new Rule(rule.getPremise(), this.closure(rule.getPremise()));
if (!rule.equals(newR)) {
this.replaceRule(rule, newR);
}
}
return s - this.sizeRules();
}
/**
* Makes this component a left minimal and compact ImplicationalSystem.
*
* The unary form of this componant is first computed: if two rules have the
* same unary conclusion, the rule with the inclusion-maximal premise is
* deleted.
*
* Then, the left-minimal treatment is performed in O(|sigma|^2|S|))
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeLeftMinimal() {
this.makeUnary();
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule1 : save.sigma) {
for (Rule rule2 : save.sigma) {
if (!rule1.equals(rule2)
&& rule2.getPremise().containsAll(rule1.getPremise())
&& rule1.getConclusion().equals(rule2.getConclusion())) {
this.sigma.remove(rule2);
}
}
}
this.makeCompact();
return save.sizeRules() - this.sizeRules();
}
/**
* Makes this component a compact and direct ImplicationalSystem.
*
* The unary and proper form of this componant is first computed. For two
* given rules rule1 and rule2, if the conclusion of rule1 contains the
* premise of rule1, then a new rule is addes, with rule1.premisse +
* rule2.premisse - rule1.conclusion as premise, and rule2.conclusion as
* conlusion. This treatment is performed in a recursive way until no new
* rule is added.
*
* This treatment is performed in O(d|S|), where d corresponds to the number
* of rules that have to be added by the direct treatment, that can be
* exponential in the worst case.
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeDirect() {
this.makeUnary();
this.makeProper();
int s = this.sizeRules();
boolean ok = true;
while (ok) {
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule1 : save.sigma) {
for (Rule rule2 : save.sigma) {
if (!rule1.equals(rule2) && !rule1.getPremise().containsAll(rule2.getConclusion())) {
ComparableSet c = new ComparableSet(rule2.getPremise());
c.removeAll(rule1.getConclusion());
c.addAll(rule1.getPremise());
if (!c.containsAll(rule2.getPremise())) {
Rule newR = new Rule(c, rule2.getConclusion());
// new_rule.addAllToPremise (rule1.getPremise());
// new_rule.addAllToPremise (rule2.getPremise());
// new_rule.removeAllFromPremise(rule1.getConclusion());
// new_rule.addAllToConclusion(rule2.getConclusion() );
this.addRule(newR);
}
}
}
}
if (this.sizeRules() == save.sizeRules()) {
ok = false;
}
}
this.makeCompact();
return s - this.sizeRules();
}
/**
* Makes this component a minimum and proper ImplicationalSystem.
*
* A rule is deleted when the closure of its premisse remains the same even
* if this rule is suppressed.
*
* This treatment is performed in O(|sigma||S|cl) where O(cl) is the
* computation of a closure.
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeMinimum() {
this.makeRightMaximal();
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule : save.sigma) {
ImplicationalSystem epsilon = new ImplicationalSystem(this);
epsilon.removeRule(rule);
if (epsilon.closure(rule.getPremise()).equals(this.closure(rule.getPremise()))) {
this.removeRule(rule);
}
}
return save.sizeRules() - this.sizeRules();
}
/**
* Replace this component by its canonical direct basis.
*
* The proper, unary and left minimal form of this component is first
* computed, before to apply the recursive directe treatment, then the left
* minimal treatment.
*
* This treatment is performed in O(d), where d corresponds to the number of
* rules that have to be added by the direct treatment. This number is
* exponential in the worst case.
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeCanonicalDirectBasis() {
int s = this.sizeRules();
this.makeProper();
this.makeLeftMinimal();
this.makeDirect();
this.makeLeftMinimal();
this.makeCompact();
return s - this.sizeRules();
}
/**
* Replace this component by the canonical basis.
*
* Conclusion of each rule is first replaced by its closure. Then, premise
* of each rule r is replaced by its closure in ImplicationalSystem \ rule.
* This treatment is performed in (|Sigma||S|cl) where O(cl) is the
* computation of a closure.
*
* @return the difference between the number of rules of this component
* before and after this treatment
*/
public int makeCanonicalBasis() {
this.makeMinimum();
ImplicationalSystem save = new ImplicationalSystem(this);
for (Rule rule : save.sigma) {
ImplicationalSystem epsilon = new ImplicationalSystem(this);
epsilon.removeRule(rule);
Rule tmp = new Rule(epsilon.closure(rule.getPremise()), rule.getConclusion());
if (!rule.equals(tmp)) {
this.replaceRule(rule, tmp);
}
}
this.makeProper();
return save.sizeRules() - this.sizeRules();
}
/*
* --------------- METHODS BASED ON GRAPH ------------
*/
/**
* Returns the representative graph of this component.
*
* Nodes of the graph are attributes of this components. For each proper
* rule X+b->a, there is an {X}-valuated edge from a to b. Notice that, for
* a rule b->a, the edge from a to b is valuated by emptyset. and for the
* two rules X+b->a and Y+b->a, the edge from a to b is valuated by {X,Y}.
*
* @return the representative graph of this component.
*/
public ConcreteDGraph representativeGraph() {
ImplicationalSystem tmp = new ImplicationalSystem(this);
tmp.makeUnary();
// nodes of the graph are elements not belonging to X
ConcreteDGraph pred = new ConcreteDGraph();
TreeMap<Comparable, Node> nodeCreated = new TreeMap<Comparable, Node>();
for (Comparable x : tmp.getSet()) {
Node node = new Node(x);
pred.addNode(node);
nodeCreated.put(x, node);
}
// an edge is added from b to a when there exists a rule X+a -> b or a -> b
for (Rule rule : tmp.getRules()) {
for (Object a : rule.getPremise()) {
ComparableSet diff = new ComparableSet(rule.getPremise());
diff.remove(a);
Node source = nodeCreated.get(rule.getConclusion().first());
Node target = nodeCreated.get(a);
Edge ed;
if (pred.containsEdge(source, target)) {
ed = pred.getEdge(source, target);
} else {
ed = new Edge(source, target, new TreeSet<ComparableSet>());
pred.addEdge(ed);
}
((TreeSet<ComparableSet>) ed.getContent()).add(diff);
}
}
return pred;
}
/**
* Returns the dependency graph of this component.
*
* Dependency graph of this component is the representative graph of the
* canonical direct basis. Therefore, the canonical direct basis has to be
* generated before to compute its representativ graph, and this treatment
* is performed in O(d), as for the canonical direct basis generation, where
* d corresponds to the number of rules that have to be added by the direct
* treatment. This number is exponential in the worst case.
*
* @return the dependency graph of this component.
*/
public ConcreteDGraph dependencyGraph() {
ImplicationalSystem bcd = new ImplicationalSystem(this);
bcd.makeCanonicalDirectBasis();
bcd.makeUnary();
return bcd.representativeGraph();
}
/**
* Removes from this component reducible elements.
*
* Reducible elements are elements equivalent by closure to others elements.
* They are computed by `getReducibleElements` of `ClosureSystem` in
* O(O(|Sigma||S|^2)
*
* @return the set of reducibles removed elements, with their equivalent
* elements
*/
public TreeMap<Comparable, TreeSet<Comparable>> reduction() {
// compute the reducible elements
TreeMap red = this.getReducibleElements();
// collect elements implied by nothing
TreeSet<Comparable> truth = this.closure(new TreeSet<Comparable>());
// modify each rule
for (Object x : red.keySet()) {
TreeSet<Rule> rules = this.sigma;
rules = (TreeSet<Rule>) rules.clone();
for (Rule rule : rules) {
Rule rule2 = new Rule();
boolean modif = false;
// replace the reducible element by its equivalent in the premise
TreeSet premise = rule.getPremise();
premise = (TreeSet) premise.clone();
if (premise.contains(x)) {
premise.remove(x);
premise.addAll((TreeSet) red.get(x));
rule2.addAllToPremise(premise);
modif = true;
} else {
rule2.addAllToPremise(premise);
}
// replace the reducible element by its equivalent in the conclusion
TreeSet conclusion = rule.getConclusion();
conclusion = (TreeSet) conclusion.clone();
if (conclusion.contains(x)) {
conclusion.remove(x);
conclusion.addAll((TreeSet) red.get(x));
rule2.addAllToConclusion(conclusion);
modif = true;
} else {
rule2.addAllToConclusion(conclusion);
}
// replace the rule if modified
if (modif) {
if (truth.containsAll(rule2.getConclusion())) {
this.removeRule(rule); // Conclusions of this rule are always true, thus the rule is useless
} else {
this.replaceRule(rule, rule2);
}
} else if (truth.containsAll(rule.getConclusion())) {
this.removeRule(rule); // Conclusions of this rule are always true, thus the rule is useless
}
}
// remove the reducible elements from the elements set
this.deleteElement((Comparable) x);
}
return red;
}
/**
* Return true if this component is reduced.
*
* @return true if this component is reduced.
*/
public boolean isReduced() {
// Copy this component not to modify it
ImplicationalSystem tmp = new ImplicationalSystem(this);
return tmp.reduction().isEmpty();
}
/*
* --------------- IMPLEMENTATION OF CLOSURESYSTEM ABSTRACT METHODS ------------
*/
/**
* Builds the closure of a set X of indexed elements.
*
* The closure is initialised with X. The closure is incremented with the
* conclusion of each rule whose premise is included in it. Iterations over
* the rules are performed until no new element has to be added in the
* closure.
*
* For direct ImplicationalSystem, only one iteration is needed, and the
* treatment is performed in O(|Sigma||S|).
*
* For non direct ImplicationalSystem, at most |S| iterations are needed,
* and this tratment is performed in O(|Sigma||S|^2).
*
* @param x a TreeSet of indexed elements
*
* @return the closure of X for this component
*/
public TreeSet<Comparable> closure(TreeSet<Comparable> x) {
TreeSet<Comparable> oldES = new TreeSet<Comparable>();
// all the attributes are in their own closure
TreeSet<Comparable> newES = new TreeSet<Comparable>(x);
do {
oldES.addAll(newES);
for (Rule rule : this.sigma) {
if (newES.containsAll(rule.getPremise()) || rule.getPremise().isEmpty()) {
newES.addAll(rule.getConclusion());
}
}
} while (!oldES.equals(newES));
return newES;
}
}