View Javadoc
1   package org.thegalactic.lattice;
2   
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;
23  
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;
30  
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> {
84  
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;
99  
100     /*
101      * ------------- CONSTRUCTORS ------------------
102      */
103     /**
104      * Constructs this component with an empty set of nodes.
105      */
106     public Lattice() {
107         super();
108     }
109 
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     }
119 
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     }
138 
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     }
166 
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     }
255 
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     }
269 
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     }
283 
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     }
300 
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     }
314 
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);
330 
331         SortedSet<Node<N>> yMinorants = new TreeSet<Node<N>>(this.minorants(y));
332         yMinorants.add(y);
333 
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     }
342 
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);
358 
359         SortedSet<Node<N>> yMajorants = new TreeSet<Node<N>>(this.majorants(y));
360         yMajorants.add(y);
361 
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     }
370 
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     }
395 
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     }
417 
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     }
434 
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     }
450 
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     }
462 
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     }
474 
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     }
485 
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     }
523 
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     }
561 
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     }
606 
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     }
636 
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     }
666 
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     }
687 
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.
703 
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     }
737 
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     }
780 
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         }
829 
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     }
839 
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     }
941 
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     }
953 
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     }
962 
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     }
1002 
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) {
1016 
1017         //nb of observations in current context
1018         int nbObs = context.getObservations().size();
1019 
1020         //start by getting exact rules
1021         ImplicationalSystem exactRules = this.getCanonicalDirectBasis();
1022         ImplicationalSystem appRules = new ImplicationalSystem();
1023 
1024         //copy elements from exact rules to approximate rules
1025         for (Comparable e : exactRules.getSet()) {
1026             appRules.addElement(e);
1027         }
1028 
1029         for (Rule rule : exactRules.getRules()) {
1030 
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);
1035 
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;
1045 
1046                     //the rule conclusion is made of the successors minus the minimal generator
1047                     TreeSet<Comparable> conclusions = new TreeSet(succ);
1048                     conclusions.removeAll(gm);
1049 
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     }
1062 
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     }
1085 
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 }