Lattice.java

  1. package org.thegalactic.lattice;

  3. /*
  4.  * Lattice.java
  5.  *
  6.  * Copyright: 2010-2015 Karell Bertet, France
  7.  * Copyright: 2015-2016 The Galactic Organization, France
  8.  *
  9.  * License: http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html CeCILL-B license
  10.  *
  11.  * This file is part of java-lattices.
  12.  * You can redistribute it and/or modify it under the terms of the CeCILL-B license.
  13.  */
  14. import org.thegalactic.rule.Rule;
  15. import org.thegalactic.rule.ImplicationalSystem;
  16. import org.thegalactic.rule.AssociationRule;
  17. import java.util.TreeMap;
  18. import java.util.TreeSet;
  19. import java.util.SortedSet;
  20. import java.util.ArrayList;
  21. import java.util.Iterator;
  22. import java.util.LinkedList;

  24. import org.thegalactic.util.ComparableSet;
  25. import org.thegalactic.context.Context;
  26. import org.thegalactic.dgraph.DAGraph;
  27. import org.thegalactic.dgraph.ConcreteDGraph;
  28. import org.thegalactic.dgraph.Edge;
  29. import org.thegalactic.dgraph.Node;

  31. /**
  32.  * This class extends class {@link org.thegalactic.dgraph.DAGraph} to provide
  33.  * specific methods to manipulate a lattice.
  34.  *
  35.  * A lattice is a directed acyclic graph
  36.  * ({@link org.thegalactic.dgraph.DAGraph}) containing particular nodes denoted
  37.  * join and meet\ (a dag is a lattice if and only if each pair of nodes admits a
  38.  * join and a meet).
  39.  *
  40.  * Since checking the lattice property is very time-expensive, this property is
  41.  * not ensured for components of this class. However, it can be explicitely
  42.  * ckecked using method {@link #isLattice}.
  43.  *
  44.  * This class provides methods implementing classical operation on a lattice
  45.  * issued from join and meet operation and irreducibles elements, and methods
  46.  * that returns a condensed representation of a lattice.
  47.  *
  48.  * A well-known condensed representation of a lattice is its table, obtained by
  49.  * method {@link #getTable}, where join-irreducibles are in column and
  50.  * meet-irreducibles are in rown.
  51.  *
  52.  * Another condensed representation is its dependency graph obtained by method
  53.  * {@link #getDependencyGraph}.
  54.  *
  55.  * The dependency graph is a directed graph where nodes are join-irreducibles,
  56.  * edges corresponds to the dependency relation between two join-irreducibles
  57.  * and are valuated by a family of subsets of irreducibles.
  58.  *
  59.  * The dependency graph encodes two other condensed representation of a lattice
  60.  * that are its minimal generators and its canonical direct basis that can be
  61.  * obtained from the dependency graph by methods {@link #getMinimalGenerators}
  62.  * and {@link #getCanonicalDirectBasis}.
  63.  *
  64.  * ![Lattice](Lattice.png)
  65.  *
  66.  * @param <N> Node content type
  67.  * @param <E> Edge content type
  68.  *
  69.  * @todo remove useless comments: Karell
  70.  *
  71.  * @uml Lattice.png
  72.  * !include resources/org/thegalactic/dgraph/DAGraph.iuml
  73.  * !include resources/org/thegalactic/dgraph/DGraph.iuml
  74.  * !include resources/org/thegalactic/dgraph/Edge.iuml
  75.  * !include resources/org/thegalactic/dgraph/Node.iuml
  76.  * !include resources/org/thegalactic/lattice/Lattice.iuml
  77.  *
  78.  * hide members
  79.  * show Lattice members
  80.  * class Lattice #LightCyan
  81.  * title Lattice UML graph
  82.  */
  83. public class Lattice<N, E> extends DAGraph<N, E> {

  85.     /*
  86.      * ------------- FIELDS ------------------
  87.      */
  88.     /**
  89.      * The dependency graph of a lattice.
  90.      *
  91.      * Nodes are join irreducibles elements, and edges correspond to the
  92.      * dependency relation of the lattice (j -> j' if and only if there exists a
  93.      * node x in the lattice such that x not greather than j and j', and x v j'
  94.      * > j), and edges are labeled with the smallest subsets X of
  95.      * join-irreducibles such that the join of elements of X corresponds to the
  96.      * node x of the lattice.
  97.      */
  98.     private ConcreteDGraph dependencyGraph = null;

  100.     /*
  101.      * ------------- CONSTRUCTORS ------------------
  102.      */
  103.     /**
  104.      * Constructs this component with an empty set of nodes.
  105.      */
  106.     public Lattice() {
  107.         super();
  108.     }

  110.     /**
  111.      * Constructs this component with the specified set of nodes, and empty
  112.      * treemap of successors and predecessors.
  113.      *
  114.      * @param set the set of nodes
  115.      */
  116.     public Lattice(SortedSet<Node<N>> set) {
  117.         super(set);
  118.     }

  120.     /**
  121.      * Constructs this component as a copy of the specified lattice.
  122.      *
  123.      * Lattice property is checked for the specified lattice.
  124.      *
  125.      * When not verified, this component is construct with an empty set of
  126.      * nodes.
  127.      *
  128.      * @param graph the Lattice to be copied
  129.      */
  130.     public Lattice(DAGraph<N, E> graph) {
  131.         super(graph);
  132.         if (!this.isAcyclic()) {
  133.             this.setNodes(new TreeSet<Node<N>>());
  134.             this.setSuccessors(new TreeMap<Node<N>, TreeSet<Edge<N, E>>>());
  135.             this.setPredecessors(new TreeMap<Node<N>, TreeSet<Edge<N, E>>>());
  136.         }
  137.     }

  139.     /*
  140.      * ------------- LATTICE CHEKING METHODS ------------------
  141.      */
  142.     /**
  143.      * Check if this component is a lattice.
  144.      *
  145.      * There exists several caracterizations of a lattice. The characterization
  146.      * implemented is the following: A lattice is a DAG if there exists a meet
  147.      * for each pair of node, and a unique maximal node.
  148.      *
  149.      * This treatment is performed in O(n^3), where n is the number of nodes.
  150.      *
  151.      * @return the truth value for this property
  152.      */
  153.     public boolean isLattice() {
  154.         if (!this.isAcyclic()) {
  155.             return false;
  156.         }
  157.         for (Node<N> x : this.getNodes()) {
  158.             for (Node<N> y : this.getNodes()) {
  159.                 if (this.meet(x, y) == null) {
  160.                     return false;
  161.                 }
  162.             }
  163.         }
  164.         return this.max().size() == 1;
  165.     }

  167.     /**
  168.      * Return true if this component is congruence normal.
  169.      *
  170.      * A lattice $L$ is in class CN (Congruence Normal) is there exists a
  171.      * sequence $L_1,\ldots,L_p$ of lattices with $L_p=L$, together with a
  172.      * sequence $C_1,\ldots,C_{p-1}$ such that $C_i$ is a convex of $L_i$ and
  173.      * $L_{i+1}$ is obtained by doubling the convex $C_i$ in $L_i$.
  174.      *
  175.      * See {@link org.thegalactic.lattice.LatticeFactory} for the doubling
  176.      * convex method which is not used here.
  177.      *
  178.      * This computation is done in O((|J|+|M|)^2|X|) from the transitive
  179.      * reduction of L.
  180.      *
  181.      * This recognition algorithm was first written in : "Doubling convex serts
  182.      * in lattices : characterizations and recognition algorithm", Bertet K.,
  183.      * Caspard N. 2002.
  184.      *
  185.      * @return true if this component is congruence normal.
  186.      */
  187.     public boolean isCN() {
  188.         TreeSet<Node<N>> joins = this.joinIrreducibles();
  189.         TreeSet<Node<N>> meets = this.meetIrreducibles();
  190.         ArrowRelation arrows = new ArrowRelation(this);
  191.         Context dbl = arrows.getDoubleArrowTable();
  192.         // steps are connected component of the double arrow table.
  193.         ArrayList<Concept> steps = new ArrayList<Concept>();
  194.         while (!joins.isEmpty()) {
  195.             TreeSet<Comparable> setA = new TreeSet<Comparable>();
  196.             TreeSet<Comparable> setB = new TreeSet<Comparable>();
  197.             int cardA = setA.size();
  198.             setA.add(joins.first());
  199.             while (cardA != setA.size()) { // something added
  200.                 cardA = setA.size(); // update card
  201.                 for (Comparable c : setA) {
  202.                     setB.addAll(dbl.getIntent(c));
  203.                 }
  204.                 for (Comparable c : setB) {
  205.                     setA.addAll(dbl.getExtent(c));
  206.                 }
  207.             }
  208.             steps.add(new Concept(setA, setB));
  209.             joins.removeAll(setA);
  210.         }
  211.         for (Concept c : steps) {
  212.             if (c.getSetB().isEmpty()) { // to be verified :-)
  213.                 return false;
  214.             }
  215.             for (Comparable j : c.getSetA()) {
  216.                 for (Comparable m : c.getSetB()) {
  217.                     if (arrows.getEdge((Node) j, (Node) m).getContent() != "UpDown"
  218.                             && arrows.getEdge((Node) j, (Node) m).getContent() != "Circ") {
  219.                         return false;
  220.                     }
  221.                 }
  222.             }
  223.         }
  224.         joins = this.joinIrreducibles();
  225.         meets = this.meetIrreducibles();
  226.         ConcreteDGraph phi = new ConcreteDGraph();
  227.         for (Node<N> j : joins) {
  228.             for (Node<N> m : meets) {
  229.                 int indJ = 0; // Search for the step containning j
  230.                 while (indJ < steps.size() && !steps.get(indJ).containsInA(j)) {
  231.                     indJ++;
  232.                 }
  233.                 if (phi.getNodeByContent(indJ) == null && indJ != steps.size()) {
  234.                     phi.addNode(new Node(indJ));
  235.                 }
  236.                 int indM = 0; // Search for the step containning m
  237.                 while (indM < steps.size() && !steps.get(indM).containsInB(m)) {
  238.                     indM++;
  239.                 }
  240.                 if (phi.getNodeByContent(indM) == null && indM != steps.size()) {
  241.                     phi.addNode(new Node(indM));
  242.                 }
  243.                 if (indM != steps.size() && indJ != steps.size()) {
  244.                     if (arrows.getEdge((Node) j, (Node) m).getContent() == "Up") {
  245.                         phi.addEdge(phi.getNodeByContent(indM), phi.getNodeByContent(indJ));
  246.                     }
  247.                     if (arrows.getEdge((Node) j, (Node) m).getContent() == "Down") {
  248.                         phi.addEdge(phi.getNodeByContent(indJ), phi.getNodeByContent(indM));
  249.                     }
  250.                 }
  251.             }
  252.         }
  253.         return (phi.isAcyclic());
  254.     }

  256.     /**
  257.      * Returns true if this component is an atomistic lattice.
  258.      *
  259.      * A lattice is atomistic if its join irreductibles are atoms (e.g.
  260.      * successors of bottom)
  261.      *
  262.      * @return true if this component is atomistic.
  263.      */
  264.     public boolean isAtomistic() {
  265.         TreeSet<Node<N>> join = this.joinIrreducibles();
  266.         TreeSet<Node> atoms = new TreeSet<Node>(this.getSuccessorNodes(this.bottom()));
  267.         return join.containsAll(atoms) && atoms.containsAll(join);
  268.     }

  270.     /**
  271.      * Returns true if this component is an coatomistic lattice.
  272.      *
  273.      * A lattice is coatomistic if its mett irreductibles are coatoms (e.g.
  274.      * predecessors of top)
  275.      *
  276.      * @return true if this component is coatomistic.
  277.      */
  278.     public boolean isCoAtomistic() {
  279.         TreeSet<Node<N>> meet = this.meetIrreducibles();
  280.         SortedSet<Node<N>> coatoms = this.getPredecessorNodes(this.top());
  281.         return meet.containsAll(coatoms) && coatoms.containsAll(meet);
  282.     }

  284.     /*
  285.      * --------------- LATTICE HANDLING METHODS ------------
  286.      */
  287.     /**
  288.      * Returns the top of the lattice.
  289.      *
  290.      * @return the node which is at the top of the lattice or null if it is not
  291.      *         unique
  292.      */
  293.     public Node<N> top() {
  294.         TreeSet<Node<N>> max = new TreeSet<Node<N>>(this.max());
  295.         if (max.size() == 1) {
  296.             return max.first();
  297.         }
  298.         return null;
  299.     }

  301.     /**
  302.      * Returns the bottom of the lattice.
  303.      *
  304.      * @return the node which is at the bottom of the lattice or null if it is
  305.      *         not unique
  306.      */
  307.     public Node<N> bottom() {
  308.         TreeSet<Node<N>> min = new TreeSet<Node<N>>(this.min());
  309.         if (min.size() == 1) {
  310.             return min.first();
  311.         }
  312.         return null;
  313.     }

  315.     /**
  316.      * Returns the meet of the two specified nodes if it exists.
  317.      *
  318.      * @param x the first node
  319.      * @param y the second node
  320.      *
  321.      * @return the node which is at the meet of the nodes or null if it does not
  322.      *         exist
  323.      *
  324.      * @todo this.minorants should return an iterator
  325.      */
  326.     public Node<N> meet(Node<N> x, Node<N> y) {
  327.         // TODO minorants should return an iterator
  328.         SortedSet<Node<N>> xMinorants = new TreeSet<Node<N>>(this.minorants(x));
  329.         xMinorants.add(x);

  331.         SortedSet<Node<N>> yMinorants = new TreeSet<Node<N>>(this.minorants(y));
  332.         yMinorants.add(y);

  334.         xMinorants.retainAll(yMinorants);
  335.         DAGraph<N, E> graph = this.getSubgraphByNodes(xMinorants);
  336.         TreeSet<Node> meet = new TreeSet<Node>(graph.max());
  337.         if (meet.size() == 1) {
  338.             return meet.first();
  339.         }
  340.         return null;
  341.     }

  343.     /**
  344.      * Returns the join of the two specified nodes if it exists.
  345.      *
  346.      * @param x the first node
  347.      * @param y the second node
  348.      *
  349.      * @return the node which is at the join of the nodes or null if it does not
  350.      *         exist
  351.      *
  352.      * @todo this.majorants should return an iterator
  353.      */
  354.     public Node<N> join(Node<N> x, Node<N> y) {
  355.         // TODO this.majorants should return an iterator
  356.         SortedSet<Node<N>> xMajorants = new TreeSet<Node<N>>(this.majorants(x));
  357.         xMajorants.add(x);

  359.         SortedSet<Node<N>> yMajorants = new TreeSet<Node<N>>(this.majorants(y));
  360.         yMajorants.add(y);

  362.         xMajorants.retainAll(yMajorants);
  363.         DAGraph<N, E> graph = this.getSubgraphByNodes(xMajorants);
  364.         TreeSet<Node> join = new TreeSet<Node>(graph.min());
  365.         if (join.size() == 1) {
  366.             return join.first();
  367.         }
  368.         return null;
  369.     }

  371.     /*
  372.      * ------------- IRREDUCIBLES RELATIVE METHODS ------------------
  373.      */
  374.     /**
  375.      * Returns the set of join irreducibles of this component.
  376.      *
  377.      * Join irreducibles are nodes with an unique immediate predecessor in the
  378.      * transitive and reflexive reduction. This component is first reduced
  379.      * reflexively and transitively.
  380.      *
  381.      * @return the set of join irreducibles of this component
  382.      */
  383.     public TreeSet<Node<N>> joinIrreducibles() {
  384.         DAGraph<N, E> graph = new DAGraph(this);
  385.         graph.reflexiveReduction();
  386.         graph.transitiveReduction();
  387.         TreeSet<Node<N>> set = new TreeSet();
  388.         for (Node<N> node : graph.getNodes()) {
  389.             if (graph.getPredecessorNodes(node).size() == 1) {
  390.                 set.add(node);
  391.             }
  392.         }
  393.         return set;
  394.     }

  396.     /**
  397.      * Returns the set of meet irreducibles of this component.
  398.      *
  399.      * Meet irreducibles are nodes with an unique immediate successor in the
  400.      * transitive and reflexiv reduction. This component is first reduced
  401.      * reflexively and transitively.
  402.      *
  403.      * @return the set of meet irreducibles of this component.
  404.      */
  405.     public TreeSet<Node<N>> meetIrreducibles() {
  406.         DAGraph<N, E> graph = new DAGraph(this);
  407.         graph.reflexiveReduction();
  408.         graph.transitiveReduction();
  409.         TreeSet<Node<N>> set = new TreeSet();
  410.         for (Node<N> node : graph.getNodes()) {
  411.             if (graph.getSuccessorNodes(node).size() == 1) {
  412.                 set.add(node);
  413.             }
  414.         }
  415.         return set;
  416.     }

  418.     /**
  419.      * Returns the set of join-irreducibles that are minorants of the specified
  420.      * node.
  421.      *
  422.      * @param node a specified node
  423.      *
  424.      * @return the set of join-irreducibles thar are minorants of the specified
  425.      *         node
  426.      */
  427.     public TreeSet<Node<N>> joinIrreducibles(Node<N> node) {
  428.         TreeSet<Node<N>> join = new TreeSet<Node<N>>(this.joinIrreducibles());
  429.         TreeSet<Node<N>> min = new TreeSet<Node<N>>(this.minorants(node));
  430.         min.add(node);
  431.         min.retainAll(join);
  432.         return min;
  433.     }

  435.     /**
  436.      * Returns the set of meet-irreducibles thar are majorants of the specified
  437.      * node.
  438.      *
  439.      * @param node a specified node
  440.      *
  441.      * @return the set of meet-irreducibles thar are majorants of the specified
  442.      *         node
  443.      */
  444.     public TreeSet<Node<N>> meetIrreducibles(Node<N> node) {
  445.         TreeSet<Node<N>> meet = new TreeSet<Node<N>>(this.meetIrreducibles());
  446.         TreeSet<Node<N>> maj = new TreeSet<Node<N>>(this.majorants(node));
  447.         maj.retainAll(meet);
  448.         return maj;
  449.     }

  451.     /**
  452.      * Returns the subgraph induced by the join irreducibles nodes of this
  453.      * component.
  454.      *
  455.      * @return the subgraph induced by the join irreducibles nodes of this
  456.      *         component
  457.      */
  458.     public DAGraph<N, E> joinIrreduciblesSubgraph() {
  459.         TreeSet<Node<N>> irr = this.joinIrreducibles();
  460.         return this.getSubgraphByNodes(irr);
  461.     }

  463.     /**
  464.      * Returns the subgraph induced by the meet irreducibles nodes of this
  465.      * component.
  466.      *
  467.      * @return the subgraph induced by the meet irreducibles nodes of this
  468.      *         component
  469.      */
  470.     public DAGraph<N, E> meetIrreduciblesSubgraph() {
  471.         TreeSet<Node<N>> irr = this.meetIrreducibles();
  472.         return this.getSubgraphByNodes(irr);
  473.     }

  475.     /**
  476.      * Returns the subgraph induced by the irreducibles nodes of this component.
  477.      *
  478.      * @return the subgraph induced by the irreducibles nodes of this component
  479.      */
  480.     public DAGraph<N, E> irreduciblesSubgraph() {
  481.         TreeSet<Node<N>> irr = this.meetIrreducibles();
  482.         irr.addAll(this.joinIrreducibles());
  483.         return this.getSubgraphByNodes(irr);
  484.     }

  486.     /**
  487.      * Generates and returns the isomorphic closed set lattice defined on the
  488.      * join irreducibles set.
  489.      *
  490.      * Each node of this component is replaced by a node containing its join
  491.      * irreducibles predecessors stored in a closed set.
  492.      *
  493.      * @return the isomorphic closed set lattice defined on the join
  494.      *         irreducibles set
  495.      */
  496.     public ConceptLattice joinClosure() {
  497.         ConceptLattice csl = new ConceptLattice();
  498.         // associates each node to a new closed set of join irreducibles
  499.         TreeSet<Node<N>> join = this.joinIrreducibles();
  500.         TreeMap<Node, Concept> closure = new TreeMap<Node, Concept>();
  501.         Lattice<N, E> lattice = new Lattice(this);
  502.         lattice.transitiveClosure();
  503.         lattice.reflexiveClosure();
  504.         for (Node<N> target : lattice.getNodes()) {
  505.             ComparableSet jx = new ComparableSet();
  506.             for (Node<N> source : lattice.getPredecessorNodes(target)) {
  507.                 if (join.contains(source)) {
  508.                     jx.add(source.getContent());
  509.                 }
  510.             }
  511.             closure.put(target, new Concept(jx, false));
  512.         }
  513.         // addition of nodes
  514.         for (Node<N> node : this.getNodes()) {
  515.             csl.addNode(closure.get(node));
  516.         }
  517.         // addition of edges
  518.         for (Edge ed : this.getEdges()) {
  519.             csl.addEdge(closure.get(ed.getSource()), closure.get(ed.getTarget()));
  520.         }
  521.         return csl;
  522.     }

  524.     /**
  525.      * Generates and returns the isomorphic closed set lattice defined on the
  526.      * meet irreducibles set.
  527.      *
  528.      * Each node of this component is replaced by a node containing its meet
  529.      * irreducibles successors stored in a closed set.
  530.      *
  531.      * @return the isomorphic closed set lattice defined on the meet
  532.      *         irreducibles set
  533.      */
  534.     public ConceptLattice meetClosure() {
  535.         ConceptLattice csl = new ConceptLattice();
  536.         // associates each node to a new closed set of join irreducibles
  537.         TreeSet<Node<N>> meet = this.meetIrreducibles();
  538.         TreeMap<Node, Concept> closure = new TreeMap<Node, Concept>();
  539.         Lattice<N, E> lattice = new Lattice(this);
  540.         lattice.transitiveClosure();
  541.         lattice.reflexiveClosure();
  542.         for (Node<N> target : lattice.getNodes()) {
  543.             ComparableSet mx = new ComparableSet();
  544.             for (Node<N> source : lattice.getSuccessorNodes(target)) {
  545.                 if (meet.contains(source)) {
  546.                     mx.add(source);
  547.                 }
  548.             }
  549.             closure.put(target, new Concept(false, mx));
  550.         }
  551.         // addition of nodes
  552.         for (Node node : this.getNodes()) {
  553.             csl.addNode(closure.get(node));
  554.         }
  555.         // addition of edges
  556.         for (Edge ed : this.getEdges()) {
  557.             csl.addEdge(closure.get(ed.getSource()), closure.get(ed.getTarget()));
  558.         }
  559.         return csl;
  560.     }

  562.     /**
  563.      * Generates and returns the isomorphic concept lattice defined on the join
  564.      * and meet irreducibles sets.
  565.      *
  566.      * Each node of this component is replaced by a node containing its meet
  567.      * irreducibles successors and its join irreducibles predecessors stored in
  568.      * a concept.
  569.      *
  570.      * @return the irreducible closure
  571.      */
  572.     public ConceptLattice irreducibleClosure() {
  573.         ConceptLattice conceptLatice = new ConceptLattice();
  574.         // associates each node to a new closed set of join irreducibles
  575.         TreeSet<Node<N>> meet = this.meetIrreducibles();
  576.         TreeSet<Node<N>> join = this.joinIrreducibles();
  577.         TreeMap<Node, Concept> closure = new TreeMap<Node, Concept>();
  578.         Lattice<N, E> lattice = new Lattice(this);
  579.         lattice.transitiveClosure();
  580.         lattice.reflexiveClosure();
  581.         for (Node<N> target : lattice.getNodes()) {
  582.             ComparableSet jx = new ComparableSet();
  583.             for (Node<N> source : lattice.getPredecessorNodes(target)) {
  584.                 if (join.contains(source)) {
  585.                     jx.add(source);
  586.                 }
  587.             }
  588.             ComparableSet mx = new ComparableSet();
  589.             for (Node source : lattice.getSuccessorNodes(target)) {
  590.                 if (meet.contains(source)) {
  591.                     mx.add(source);
  592.                 }
  593.             }
  594.             closure.put(target, new Concept(jx, mx));
  595.         }
  596.         // addition of nodes
  597.         for (Node node : this.getNodes()) {
  598.             conceptLatice.addNode(closure.get(node));
  599.         }
  600.         // addition of edges
  601.         for (Edge ed : this.getEdges()) {
  602.             conceptLatice.addEdge(closure.get(ed.getSource()), closure.get(ed.getTarget()));
  603.         }
  604.         return conceptLatice;
  605.     }

  607.     /**
  608.      * Returns the smallest set of nodes of this component containing S such
  609.      * that if a,b in JS then join(a,b) in JS.
  610.      *
  611.      * @param s set of nodes to be closed
  612.      *
  613.      * @return (JS) join-closure of s
  614.      */
  615.     public ComparableSet joinClosure(ComparableSet s) {
  616.         // Algorithm is true because join is idempotent & commutative
  617.         ComparableSet stack = new ComparableSet();
  618.         stack.addAll(s); // Nodes to be explored
  619.         ComparableSet result = new ComparableSet();
  620.         while (!stack.isEmpty()) {
  621.             Node c = (Node) stack.first();
  622.             stack.remove(c);
  623.             result.add(c);
  624.             Iterator<Node> it = stack.iterator();
  625.             ComparableSet newNodes = new ComparableSet(); // Node to be added. Must be done AFTER while
  626.             while (it.hasNext()) {
  627.                 Node node = this.join(it.next(), c);
  628.                 if (!result.contains(node) && !stack.contains(node)) {
  629.                     newNodes.add(node);
  630.                 }
  631.             }
  632.             stack.addAll(newNodes);
  633.         }
  634.         return result;
  635.     }

  637.     /**
  638.      * Returns the smallest set of nodes of this component containing S such
  639.      * that if a,b in MS then meet(a,b) in MS.
  640.      *
  641.      * @param s set of nodes to be closed
  642.      *
  643.      * @return (MS) meet-closure of s
  644.      */
  645.     public ComparableSet meetClosure(ComparableSet s) {
  646.         // Algorithm is true because meet is idempotent & commutative
  647.         ComparableSet stack = new ComparableSet();
  648.         stack.addAll(s); // Nodes to be explored
  649.         ComparableSet result = new ComparableSet();
  650.         while (!stack.isEmpty()) {
  651.             Node c = (Node) stack.first();
  652.             stack.remove(c);
  653.             result.add(c);
  654.             Iterator<Node> it = stack.iterator();
  655.             ComparableSet newNodes = new ComparableSet(); // Node to be added. Must be done AFTER while
  656.             while (it.hasNext()) {
  657.                 Node node = this.meet(it.next(), c);
  658.                 if (!result.contains(node) && !stack.contains(node)) {
  659.                     newNodes.add(node);
  660.                 }
  661.             }
  662.             stack.addAll(newNodes);
  663.         }
  664.         return result;
  665.     }

  667.     /**
  668.      * Returns the smallest sublattice of this component containing s.
  669.      *
  670.      * @param s set of nodes to be closed.
  671.      *
  672.      * @return the smallest sublattice of this component containing s.
  673.      */
  674.     public ComparableSet fullClosure(ComparableSet s) {
  675.         ComparableSet result = new ComparableSet();
  676.         result.addAll(s);
  677.         int present = result.size();
  678.         int previous = 0;
  679.         while (previous != present) {
  680.             previous = present;
  681.             result = this.joinClosure(result);
  682.             result = this.meetClosure(result);
  683.             present = result.size();
  684.         }
  685.         return result;
  686.     }

  688.     /**
  689.      * Returns the list of all sets of nodes that generates all nodes. Both join
  690.      * and meet operations are allowed and the sets are minimal for inclusion.
  691.      *
  692.      * @return : List of all hybridGenerators families.
  693.      */
  694.     public TreeSet<ComparableSet> hybridGenerators() {
  695.         TreeSet<Node<N>> joinIrr = this.joinIrreducibles();
  696.         TreeSet<Node<N>> meetIrr = this.meetIrreducibles();
  697.         ComparableSet bothIrr = new ComparableSet();
  698.         for (Node<N> node : joinIrr) {
  699.             if (meetIrr.contains(node)) {
  700.                 bothIrr.add(node);
  701.             }
  702.         } // bothIrr contains nodes that are join and meet irreductibles.

  704.         TreeSet<ComparableSet> generators = new TreeSet<ComparableSet>();
  705.         // First point is that all minimal families have the same number of nodes.
  706.         LinkedList<ComparableSet> list = new LinkedList<ComparableSet>(); // Family of sets to be examined
  707.         list.add(bothIrr);
  708.         while (!list.isEmpty()) {
  709.             int test;
  710.             if (generators.isEmpty()) {
  711.                 test = this.sizeNodes();
  712.             } else {
  713.                 test = generators.first().size();
  714.             }
  715.             if (test < list.peek().size()) {
  716.                 // Elements are sorted by size, thus if the first is to large, all are.
  717.                 list.clear();
  718.             } else {
  719.                 ComparableSet family = list.poll(); // Retrieve and remove head.
  720.                 if (this.fullClosure(family).size() == this.sizeNodes()) {
  721.                     // This family generates l
  722.                     generators.add(family);
  723.                 } else {
  724.                     for (Node node : this.getNodes()) {
  725.                         ComparableSet newFamily = new ComparableSet();
  726.                         newFamily.addAll(family);
  727.                         newFamily.add(node);
  728.                         if (!list.contains(newFamily)) {
  729.                             list.add(newFamily); // add at the end, bigger families
  730.                         }
  731.                     }
  732.                 }
  733.             }
  734.         }
  735.         return generators;
  736.     }

  738.     /**
  739.      * Returns the table of the lattice, composed of the join and meet
  740.      * irreducibles nodes.
  741.      *
  742.      * Each attribute of the table is a copy of a join irreducibles node. Each
  743.      * observation of the table is a copy of a meet irreducibles node. An
  744.      * attribute is extent of an observation when its join irreducible node is
  745.      * greater than the meet irreducible node in the lattice.
  746.      *
  747.      * @return the table of the lattice
  748.      */
  749.     public Context getTable() {
  750.         // generation of attributes
  751.         TreeSet<Node<N>> join = this.joinIrreducibles();
  752.         //TreeMap<Node,Node> JoinContent = new TreeMap();
  753.         Context context = new Context();
  754.         for (Node<N> j : join) {
  755.             //  Node<N> nj = new Node(j);
  756.             //JoinContent.put(j,nj);
  757.             context.addToAttributes(j);
  758.         }
  759.         // generation of observations
  760.         TreeSet<Node<N>> meet = this.meetIrreducibles();
  761.         //TreeMap<Node,Node> MeetContent = new TreeMap();
  762.         for (Node<N> m : meet) {
  763.             //    Node nm = new Node(m);
  764.             context.addToObservations(m);
  765.             //    MeetContent.put(m,nm);
  766.         }
  767.         // generation of extent-intent
  768.         Lattice tmp = new Lattice(this);
  769.         tmp.transitiveClosure();
  770.         for (Node j : join) {
  771.             for (Node m : meet) {
  772.                 if (j.equals(m) || tmp.getSuccessorNodes(j).contains(m)) {
  773.                     context.addExtentIntent(m, j);
  774.                     //T.addExtentIntent(MeetContent.get(m),JoinContent.get(j));
  775.                 }
  776.             }
  777.         }
  778.         return context;
  779.     }

  781.     /**
  782.      * Returns an ImplicationalSystem of the lattice defined on the join
  783.      * irreducibles nodes.
  784.      *
  785.      * Each element of the ImplicationalSystem is a copy of a join irreducible
  786.      * node.
  787.      *
  788.      * @return an implicational system
  789.      */
  790.     public ImplicationalSystem getImplicationalSystem() {
  791.         // initialisation of ImplicationalSystem
  792.         TreeSet<Node<N>> join = this.joinIrreducibles();
  793.         ImplicationalSystem sigma = new ImplicationalSystem();
  794.         for (Node<N> j : join) {
  795.             sigma.addElement((Comparable) j.getContent());
  796.         }
  797.         // generation of the family of closures
  798.         TreeSet<ComparableSet> family = new TreeSet<ComparableSet>();
  799.         Lattice lattice = new Lattice(this);
  800.         ConceptLattice conceptLattice = lattice.joinClosure();
  801.         for (Object node : conceptLattice.getNodes()) {
  802.             Concept concept = (Concept) node;
  803.             ComparableSet setA = new ComparableSet(concept.getSetA());
  804.             family.add(setA);
  805.         }
  806.         // rules generation
  807.         for (ComparableSet jx : family) {
  808.             for (Node j : join) {
  809.                 ComparableSet p = new ComparableSet();
  810.                 p.add(j.getContent());
  811.                 p.addAll(jx);
  812.                 if (!family.contains(p)) {
  813.                     ComparableSet min = new ComparableSet();
  814.                     min.addAll(family.last());
  815.                     for (ComparableSet c : family) {
  816.                         //System.out.println("min: "+min.getClass()+" -C:"+C.getClass());
  817.                         if (c.containsAll(p) && !p.containsAll(c) && min.containsAll(c)) {
  818.                             min = c.clone();
  819.                         }
  820.                     }
  821.                     Rule r = new Rule();
  822.                     r.addAllToPremise(p);
  823.                     min.removeAll(p);
  824.                     r.addAllToConclusion(min);
  825.                     sigma.addRule(r);
  826.                 }
  827.             }
  828.         }

  830.         /**
  831.          * for (Node j : join) for (Node m : meet) if (j.equals(m) ||
  832.          * tmp.getSuccessorNodes(j).contains(m)) T.addExtentIntent (m,j);
  833.          * //T.addExtentIntent (MeetContent.get(m),JoinContent.get(j)); return
  834.          * T;*
  835.          */
  836.         sigma.makeRightMaximal();
  837.         return sigma;
  838.     }

  840.     /*
  841.      * ------------- dependency GRAPH RELATIVE METHODS ------------------
  842.      */
  843.     /**
  844.      * Returns the dependency graph of this component.
  845.      *
  846.      * The dependency graph is a condensed representation of a lattice that
  847.      * encodes its minimal generators, and its canonical direct basis.
  848.      *
  849.      * In the dependency graph, nodes are join irreducibles, egdes correspond to
  850.      * the dependency relation between join-irreducibles (j -> j' if and only if
  851.      * there exists a node x in the lattice such that x not greather than j and
  852.      * j', and x v j' > j), and edges are labeled with the smallest subsets X of
  853.      * join-irreducibles such that the join of elements of X corresponds to the
  854.      * node x of the lattice.
  855.      *
  856.      * The dependency graph could has been already computed in the case where
  857.      * this component has been instancied as the diagramm of the closed set
  858.      * lattice of a closure system using the static method
  859.      * {@link ConceptLattice#diagramLattice} This method implements an
  860.      * adaptation adaptation of Bordat's where the dependency graph is computed
  861.      * while the lattice is generated.
  862.      *
  863.      * However, it is generated in O(nj^3) where n is the number of nodes of the
  864.      * lattice, and j is the number of join-irreducibles of the lattice.
  865.      *
  866.      * @return the dependency graph
  867.      */
  868.     public ConcreteDGraph getDependencyGraph() {
  869.         if (!(this.dependencyGraph == null)) {
  870.             return this.dependencyGraph;
  871.         }
  872.         this.dependencyGraph = new ConcreteDGraph();
  873.         // nodes of the dependency graph are join-irreducibles
  874.         TreeSet<Node<N>> joins = this.joinIrreducibles();
  875.         for (Node<N> j : joins) {
  876.             this.dependencyGraph.addNode(j);
  877.         }
  878.         // computes the transitive closure of the join-irreducibles subgraph of this compnent
  879.         DAGraph joinG = this.irreduciblesSubgraph();
  880.         joinG.transitiveClosure();
  881.         // edges of the dependency graph are dependency relation between join-irreducibles
  882.         // they are first valuated by nodes of the lattice
  883.         for (Node<N> j1 : joins) {
  884.             SortedSet<Node<N>> majj1 = this.majorants(j1);
  885.             for (Node<N> j2 : joins) {
  886.                 if (!j1.equals(j2)) {
  887.                     // computes the set S of nodes not greather than j1 and j2
  888.                     TreeSet<Node<N>> set = new TreeSet<Node<N>>(this.getNodes());
  889.                     set.removeAll(majj1);
  890.                     set.removeAll(this.majorants(j2));
  891.                     set.remove(j1);
  892.                     set.remove(j2);
  893.                     for (Node<N> x : set) {
  894.                         // when j2 V x greather than j1 then add a new edge from j1 to J2
  895.                         // or only a new valuation when the edge already exists
  896.                         if (majj1.contains(this.join(j2, x))) {
  897.                             Edge ed = this.dependencyGraph.getEdge(j1, j2);
  898.                             if (ed == null) {
  899.                                 ed = new Edge(j1, j2, new TreeSet<ComparableSet>());
  900.                                 this.dependencyGraph.addEdge(ed);
  901.                             }
  902.                             // add {Jx minus predecessors in joinG of j in Jx} as valuation of edge
  903.                             // from j1 to j2
  904.                             TreeSet<ComparableSet> valEd = (TreeSet<ComparableSet>) ed.getContent();
  905.                             ComparableSet newValByNode = new ComparableSet(this.joinIrreducibles(x));
  906.                             for (Node<N> j : this.joinIrreducibles(x)) {
  907.                                 newValByNode.removeAll(joinG.getPredecessorNodes(j));
  908.                             }
  909.                             ComparableSet newVal = new ComparableSet();
  910.                             for (Object j : newValByNode) {
  911.                                 Node node = (Node) j;
  912.                                 newVal.add(node.getContent());
  913.                             }
  914.                             ((TreeSet<ComparableSet>) ed.getContent()).add(newVal);
  915.                             // Minimalisation by inclusion of valuations on edge j1->j2
  916.                             valEd = new TreeSet<ComparableSet>((TreeSet<ComparableSet>) ed.getContent());
  917.                             for (ComparableSet x1 : valEd) {
  918.                                 if (x1.containsAll(newVal) && !newVal.containsAll(x1)) {
  919.                                     ((TreeSet<ComparableSet>) ed.getContent()).remove(x1);
  920.                                 }
  921.                                 if (!x1.containsAll(newVal) && newVal.containsAll(x1)) {
  922.                                     ((TreeSet<ComparableSet>) ed.getContent()).remove(newVal);
  923.                                 }
  924.                             }
  925.                         }
  926.                     }
  927.                 }
  928.             }
  929.         }
  930.         // minimalisation of edge's content to get only inclusion-minimal valuation for each edge
  931.         /**
  932.          * for (Edge ed : this.dependencyGraph.getEdges()) {
  933.          * TreeSet<ComparableSet> valEd = new
  934.          * TreeSet<ComparableSet>(((TreeSet<ComparableSet>)ed.getContent()));
  935.          * for (ComparableSet X1 : valEd) for (ComparableSet X2 : valEd) if
  936.          * (X1.containsAll(X2) && !X2.containsAll(X1))
  937.          * ((TreeSet<ComparableSet>)ed.getContent()).remove(X1); }*
  938.          */
  939.         return this.dependencyGraph;
  940.     }

  942.     /**
  943.      * Set the dependency graph.
  944.      *
  945.      * @param graph the dependency graph
  946.      *
  947.      * @return this for chaining
  948.      */
  949.     protected Lattice setDependencyGraph(ConcreteDGraph graph) {
  950.         this.dependencyGraph = graph;
  951.         return this;
  952.     }

  954.     /**
  955.      * Test if this component has a dependency graph.
  956.      *
  957.      * @return the truth value for this property
  958.      */
  959.     protected boolean hasDependencyGraph() {
  960.         return this.dependencyGraph != null;
  961.     }

  963.     /**
  964.      * Returns the canonical direct basis of the lattice.
  965.      *
  966.      * The canonical direct basis is a condensed representation of a lattice
  967.      * encoding by the dependency graph.
  968.      *
  969.      * This canonical direct basis is deduced from the dependency graph of the
  970.      * lattice: for each edge b -> a valuated by a subset X, the rule a+X->b is
  971.      * a rule of the canonical direct basis.
  972.      *
  973.      * If not yet exists, the dependency graph of this component has to be
  974.      * generated by method {@link #getDependencyGraph}.
  975.      *
  976.      * @return the canonical direct basis of the lattice
  977.      */
  978.     public ImplicationalSystem getCanonicalDirectBasis() {
  979.         ConcreteDGraph odGraph = this.getDependencyGraph();
  980.         // initialise elements of the ImplicationalSystem with nodes of the ODGraph
  981.         ImplicationalSystem bcd = new ImplicationalSystem();
  982.         for (Object node : odGraph.getNodes()) {
  983.             bcd.addElement((Comparable) ((Node) node).getContent());
  984.         }
  985.         // computes rules of the BCD from edges of the ODGraph
  986.         for (Object ed : odGraph.getEdges()) {
  987.             Node source = ((Edge) ed).getSource();
  988.             Node target = ((Edge) ed).getTarget();
  989.             TreeSet<ComparableSet> l = (TreeSet<ComparableSet>) ((Edge) ed).getContent();
  990.             for (ComparableSet set : l) {
  991.                 ComparableSet premise = new ComparableSet(set);
  992.                 premise.add((Comparable) target.getContent());
  993.                 ComparableSet conclusion = new ComparableSet();
  994.                 conclusion.add((Comparable) source.getContent());
  995.                 bcd.addRule(new Rule(premise, conclusion));
  996.             }
  997.         }
  998.         //bcd.makeLeftMinimal();
  999.         bcd.makeCompact();
  1000.         return bcd;
  1001.     }

  1003.     /**
  1004.      * Returns a set of association rules based on a confidence threshold.
  1005.      *
  1006.      * The canonical direct basis is computed. For each generated rule, a set of
  1007.      * approximative rules (above the confidence threshold) is generated.
  1008.      *
  1009.      * @param context    a context
  1010.      * @param support    a support threshold, between 0 and 1
  1011.      * @param confidence a confidence threshold, between 0 and 1
  1012.      *
  1013.      * @return a set of approximative rules
  1014.      */
  1015.     public ImplicationalSystem getAssociationBasis(Context context, double support, double confidence) {

  1017.         //nb of observations in current context
  1018.         int nbObs = context.getObservations().size();

  1020.         //start by getting exact rules
  1021.         ImplicationalSystem exactRules = this.getCanonicalDirectBasis();
  1022.         ImplicationalSystem appRules = new ImplicationalSystem();

  1024.         //copy elements from exact rules to approximate rules
  1025.         for (Comparable e : exactRules.getSet()) {
  1026.             appRules.addElement(e);
  1027.         }

  1029.         for (Rule rule : exactRules.getRules()) {

  1031.             //we get the premisse of the rule, aka the closed set minimal generator
  1032.             TreeSet<Comparable> gm = rule.getPremise();
  1033.             //then we retrieve the closed set from the minimal generator
  1034.             TreeSet<Comparable> closedSet = context.closure(gm);

  1036.             //we get the cardinality of its extent to compute confidence later
  1037.             double supportClosedSet = context.getExtentNb(closedSet);
  1038.             if (supportClosedSet / nbObs > support) {
  1039.                 //we get the immediate successors of the concept made of the set
  1040.                 ArrayList<TreeSet<Comparable>> succs = new Concept(closedSet, new TreeSet()).immediateSuccessorsLOA(context);
  1041.                 for (TreeSet<Comparable> succ : succs) {
  1042.                     //we compute the support of the rule as the ratio between closed set and successor extent
  1043.                     double ex = context.getExtentNb(succ);
  1044.                     double supportSucc = ex / supportClosedSet;

  1046.                     //the rule conclusion is made of the successors minus the minimal generator
  1047.                     TreeSet<Comparable> conclusions = new TreeSet(succ);
  1048.                     conclusions.removeAll(gm);

  1050.                     //if the ratio support exceed the confidence threshold, the rule is created
  1051.                     if (supportSucc > confidence) {
  1052.                         appRules.addRule(new AssociationRule(gm, conclusions, ex / nbObs, supportSucc));
  1053.                     }
  1054.                 }
  1055.                 //the exact rule is copied in the output rule set
  1056.                 appRules.addRule(new AssociationRule(rule.getPremise(), rule.getConclusion(), supportClosedSet / nbObs, 1));
  1057.             }
  1058.         }
  1059.         appRules.makeCompactAssociation();
  1060.         return appRules;
  1061.     }

  1063.     /**
  1064.      * Returns the minimal generators of the lattice.
  1065.      *
  1066.      * Minimal generators a condensed representation of a lattice encoding by
  1067.      * the dependency graph.
  1068.      *
  1069.      * Minimal generators are premises of the canonical direct basis. that is
  1070.      * deduced from the dependency graph of the lattice.
  1071.      *
  1072.      * If not yet exists, the dependency graph of this component has to be
  1073.      * generated by method {@link #getDependencyGraph}.
  1074.      *
  1075.      * @return a TreeSet of the minimal generators
  1076.      */
  1077.     public TreeSet getMinimalGenerators() {
  1078.         ImplicationalSystem bcd = this.getCanonicalDirectBasis();
  1079.         TreeSet genMin = new TreeSet();
  1080.         for (Rule r : bcd.getRules()) {
  1081.             genMin.add(r.getPremise());
  1082.         }
  1083.         return genMin;
  1084.     }

  1086.     /**
  1087.      * The arrowRelation method encodes arrow relations between meet &
  1088.      * join-irreductibles of this component.
  1089.      *
  1090.      * Let m and j be respectively meet and join irreductibles of a lattice.
  1091.      * Recall that m has a unique successor say m+ and j has a unique
  1092.      * predecessor say j-, then :
  1093.      *
  1094.      * - j "Up Arrow" m (stored has "Up") iff j is not less or equal than m and j is less than m+
  1095.      * - j "Down Arrow" m (stored has "Down") iff j is not less or equal than m and j- is less than m
  1096.      * - j "Up Down Arrow" m (stored has "UpDown") iff j "Up" m and j "Down" m
  1097.      * - j "Cross" m (stored has "Cross") iff j is less or equal than m
  1098.      * - j "Circ" m (stored has "Circ") iff neither j "Up" m nor j "Down" m nor j "Cross" m
  1099.      *
  1100.      * @return ConcreteDGraph whose :
  1101.          - Nodes are join or meet irreductibles of the lattice.
  1102.          - Edges content encodes arrows as String "Up", "Down", "UpDown", "Cross", "Circ".
  1103.      *
  1104.      */
  1105.     public ArrowRelation getArrowRelation() {
  1106.         return new ArrowRelation(this);
  1107.     }
  1108. }
Created with JaCoCo 0.7.7.201606060606