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 * 
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 }