1 package org.thegalactic.lattice;
2
3 /*
4 * ConceptLattice.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.context.Context;
15 import java.util.SortedSet;
16 import java.util.TreeMap;
17 import java.util.TreeSet;
18 import java.util.Vector;
19 import java.io.IOException;
20 import java.util.List;
21
22 import org.thegalactic.util.ComparableSet;
23 import org.thegalactic.dgraph.DAGraph;
24 import org.thegalactic.dgraph.ConcreteDGraph;
25 import org.thegalactic.dgraph.Edge;
26 import org.thegalactic.dgraph.Node;
27 import org.thegalactic.io.Filer;
28 import org.thegalactic.lattice.io.ConceptLatticeIOFactory;
29
30 /**
31 * This class extends class {@link Lattice} to provide specific methods to
32 * manipulate both a concept lattice or a closed set lattice.
33 *
34 * This class provides methods implementing classical operation on a concept
35 * lattice: join and meet reduction, concepts sets reduction, ...
36 *
37 * This class also provides two static method generating a concept lattice:
38 * methods {@link #diagramLattice} and {@link #completeLattice} both computes
39 * the closed set lattice of a given closure system. The firt one computes the
40 * hasse diagram of the closed set lattice by invoking method
41 * {@link #immediateSuccessors}. This method implements an adaptation of the
42 * well-known Bordat algorithm that also computes the dependance graph of the
43 * lattice where at once the minimal generators and the canonical direct basis
44 * of the lattice are encoded. The second static method computes the
45 * transitively closure of the lattice as the inclusion relation defined on all
46 * the closures generated by method {@link ClosureSystem#allClosures} that
47 * implements the well-known Wille algorithm.
48 *
49 * 
50 *
51 * @uml ConceptLattice.png
52 * !include resources/org/thegalactic/dgraph/DAGraph.iuml
53 * !include resources/org/thegalactic/dgraph/DGraph.iuml
54 * !include resources/org/thegalactic/dgraph/Edge.iuml
55 * !include resources/org/thegalactic/dgraph/Node.iuml
56 * !include resources/org/thegalactic/lattice/Lattice.iuml
57 * !include resources/org/thegalactic/lattice/ConceptLattice.iuml
58 * !include resources/org/thegalactic/lattice/Concept.iuml
59 *
60 * hide members
61 * show ConceptLattice members
62 * class ConceptLattice #LightCyan
63 * title ConceptLattice UML graph
64 */
65 public class ConceptLattice extends Lattice {
66
67 /**
68 * Generate the lattice composed of all the antichains of this component
69 * ordered with the inclusion relation.
70 *
71 * This treatment is performed in O(??) by implementation of Nourine
72 * algorithm that consists in a sequence of doubling intervals of nodes.
73 *
74 * @param dag a directed acyclic graph
75 *
76 * @return the concept lattice
77 */
78 public static ConceptLattice idealLattice(DAGraph dag) {
79 if (!dag.isAcyclic()) {
80 return null;
81 }
82 // initialise the poset of ideals with the emptyset
83 ConceptLattice conceptLattice = new ConceptLattice();
84 conceptLattice.addNode(new Concept(true, false));
85 // travel on graph according to a topological sort
86 DAGraph graph = new DAGraph(dag);
87 graph.transitiveClosure();
88 // treatment of nodes according to a topological sort
89 List<Node> sort = graph.topologicalSort();
90 for (Node x : sort) {
91 // computation of Jx
92 TreeSet<Node> jxmoins = new TreeSet<Node>(graph.getPredecessorNodes(x));
93 // storage of new ideals in a set
94 TreeSet<Concept> toAdd = new TreeSet<Concept>();
95 for (Object j1 : conceptLattice.getNodes()) {
96 if (((Concept) j1).containsAllInA(jxmoins)) {
97 Concept newJ = new Concept(true, false);
98 newJ.addAllToA(((TreeSet) ((Concept) j1).getSetA()));
99 newJ.addToA(x);
100 toAdd.add(newJ);
101 }
102 }
103 // addition of the new ideals in conceptLattice
104 for (Concept newJ : toAdd) {
105 conceptLattice.addNode(newJ);
106 }
107 }
108 // computation of the inclusion relaton
109 for (Object node1 : conceptLattice.getNodes()) {
110 for (Object node2 : conceptLattice.getNodes()) {
111 if (((Concept) node1).containsAllInA(((Concept) node2).getSetA())) {
112 conceptLattice.addEdge((Node) node2, (Node) node1);
113 }
114 }
115 }
116 conceptLattice.transitiveReduction();
117 return conceptLattice;
118 }
119
120 /*
121 * -------- STATIC CLOSEDSET LATTICE GENERATION FROM AN ImplicationalSystem OR A CONTEXT ------------------
122 */
123 /**
124 * Generates and returns the complete (i.e. transitively closed) closed set
125 * lattice of the specified closure system, that can be an implicational
126 * system (ImplicationalSystem) or a context.
127 *
128 * The lattice is generated using the well-known Next Closure algorithm. All
129 * closures are first generated using the method:
130 * {@link ClosureSystem#allClosures} that implements the well-known Next
131 * Closure algorithm. Then, all concepts are ordered by inclusion.
132 *
133 * @param init a closure system (an ImplicationalSystem or a Context)
134 *
135 * @return a concept lattice
136 */
137 public static ConceptLattice completeLattice(ClosureSystem init) {
138 ConceptLattice lattice = new ConceptLattice();
139 // compute all the closed set with allClosures
140 Vector<Concept> allclosure = init.allClosures();
141 for (Concept cl : allclosure) {
142 lattice.addNode(cl);
143 }
144
145 // an edge corresponds to an inclusion between two closed sets
146 for (Object source : lattice.getNodes()) {
147 for (Object target : lattice.getNodes()) {
148 if (((Concept) target).containsAllInA(((Concept) source).getSetA())) {
149 lattice.addEdge((Node) source, (Node) target);
150 }
151 }
152 }
153 // Hasse diagram is computed
154 return lattice;
155 }
156
157 /**
158 * Generates and returns the Hasse diagram of the closed set lattice of the
159 * specified closure system, that can be an implicational system
160 * (ImplicationalSystem) or a context.
161 *
162 * The Hasse diagramm of the closed set lattice is obtained by a recursively
163 * generation of immediate successors of a given closed set, starting from
164 * the botom closed set. Implemented algorithm is an adaptation of Bordat's
165 * algorithm where the dependance graph is computed while the lattice is
166 * generated. This treatment is performed in O(cCl|S|^3log g) where S is the
167 * initial set of elements, c is the number of closed sets that could be
168 * exponential in the worst case, Cl is the closure computation complexity
169 * and g is the number of minimal generators of the lattice.
170 *
171 * The dependance graph of the lattice is also computed while the lattice
172 * generation. The dependance graph of a lattice encodes at once the minimal
173 * generators and the canonical direct basis of the lattice .
174 *
175 * @param init a closure system (an ImplicationalSystem or a Context)
176 *
177 * @return a concept lattice
178 */
179 public static ConceptLattice diagramLattice(ClosureSystem init) {
180 ConceptLattice lattice = new ConceptLattice();
181 //if (Diagram) {
182 // computes the dependance graph of the closure system
183 // addition of nodes in the precedence graph
184 ConcreteDGraph graph = new ConcreteDGraph();
185 for (Comparable c : init.getSet()) {
186 graph.addNode(new Node(c));
187 }
188 lattice.setDependencyGraph(graph);
189 // intialize the close set lattice with botom element
190 Concept bot = new Concept(init.closure(new ComparableSet()), false);
191 lattice.addNode(bot);
192 // recursive genaration from the botom element with diagramLattice
193 lattice.recursiveDiagramLattice(bot, init);
194 // minimalisation of edge's content to get only inclusion-minimal valuation for each edge
195 /**
196 * for (Edge ed : lattice.dependanceGraph.getEdges()) {
197 * TreeSet<ComparableSet> valEd = new
198 * TreeSet<ComparableSet>(((TreeSet<ComparableSet>)ed.getContent()));
199 * for (ComparableSet X1 : valEd) for (ComparableSet X2 : valEd) if
200 * (X1.containsAll(X2) && !X2.containsAll(X1))
201 * ((TreeSet<ComparableSet>)ed.getContent()).remove(X1); }*
202 */
203 return lattice;
204 }
205
206 /**
207 * Generates and returns the Hasse diagram of the closed set iceberg of the
208 * specified context.
209 *
210 * The Hasse diagram of the closed set iceberg is obtained by a recursively
211 * generation of immediate successors of a given closed set, starting from
212 * the bottom closed set. Implemented algorithm is an adaptation of Bordat's
213 * algorithm where the dependence graph is computed while the lattice is
214 * generated. This treatment is performed in O(cCl|S|^3log g) where S is the
215 * initial set of elements, c is the number of closed sets that could be
216 * exponential in the worst case, Cl is the closure computation complexity
217 * and g is the number of minimal generators of the lattice. The iceberg
218 * stops when the immediate successors support is inferior to the support
219 * value.
220 *
221 * The dependence graph of the lattice is also computed while the lattice
222 * generation. The dependence graph of a lattice encodes at once the minimal
223 * generators and the canonical direct basis of the lattice .
224 *
225 * @param init a closure system (an ImplicationalSystem or a Context)
226 * @param support a support value, between 0 and 1.
227 *
228 * @return a concept iceberg
229 */
230 public static ConceptLattice diagramIceberg(Context init, double support) {
231 ConceptLattice lattice = new ConceptLattice();
232 // computes the dependance graph of the closure system
233 // addition of nodes in the precedence graph
234 ConcreteDGraph graph = new ConcreteDGraph();
235 for (Comparable c : init.getSet()) {
236 graph.addNode(new Node(c));
237 }
238 lattice.setDependencyGraph(graph);
239 // intialize the close set lattice with bottom element
240 Concept bot = new Concept(init.closure(new ComparableSet()), false);
241 lattice.addNode(bot);
242 int threshold = (int) (support * init.getExtent(bot.getSetA()).size());
243 // recursive genaration from the botom element with diagramLattice
244 lattice.recursiveDiagramIceberg(bot, init, threshold);
245 return lattice;
246 }
247
248 /*
249 * ------------- CONSTRUCTORS ------------------
250 */
251 /**
252 * Constructs this component with an empty set of nodes.
253 */
254 public ConceptLattice() {
255 super();
256 }
257
258 /**
259 * Constructs this component with the specified set of concepts, and empty
260 * treemap of successors and predecessors.
261 *
262 * @param set the set of nodes
263 */
264 public ConceptLattice(TreeSet<Concept> set) {
265 super((TreeSet) set);
266 }
267
268 /**
269 * Constructs this component as a shallow copy of the specified lattice.
270 *
271 * Concept lattice property is checked for the specified lattice. When not
272 * verified, this component is constructed with an empty set of nodes.
273 *
274 * @param lattice the lattice to be copied
275 */
276 public ConceptLattice(Lattice lattice) {
277 super(lattice);
278 if (!this.isConceptLattice()) {
279 this.setNodes(new TreeSet<Node>());
280 this.setSuccessors(new TreeMap<Node, SortedSet<Edge>>());
281 this.setPredecessors(new TreeMap<Node, SortedSet<Edge>>());
282 }
283 }
284
285 /*
286 * ------------- CONCEPT LATTICE CHEKING METHOD ------------------
287 */
288 /**
289 * Check if nodes of this component are concepts.
290 *
291 * @return a boolean
292 *
293 * @todo Comment the return
294 */
295 public boolean containsConcepts() {
296 for (Object node : this.getNodes()) {
297 if (!(node instanceof Concept)) {
298 return false;
299 }
300 }
301 return true;
302 }
303
304 /**
305 * Check if this component is a lattice whose nodes are concepts.
306 *
307 * @return a boolean
308 *
309 * @todo Comment the return
310 */
311 public boolean isConceptLattice() {
312 return this.isLattice() && this.containsConcepts();
313 }
314
315 /**
316 * Check if this component is a lattice whose nodes are concepts with non
317 * null set A.
318 *
319 * @return a boolean
320 *
321 * @todo Comment the return: conception
322 */
323 public boolean containsAllSetA() {
324 if (!this.containsConcepts()) {
325 return false;
326 }
327 for (Object node : this.getNodes()) {
328 if (!((Concept) node).hasSetA()) {
329 return false;
330 }
331 }
332 return true;
333 }
334
335 /**
336 * Check if this component is a lattice whose nodes are concepts with non
337 * null set A.
338 *
339 * @return a boolean
340 *
341 * @todo Comment the return
342 */
343 public boolean containsAllSetB() {
344 if (!this.containsConcepts()) {
345 return false;
346 }
347 for (Object node : this.getNodes()) {
348 if (!((Concept) node).hasSetB()) {
349 return false;
350 }
351 }
352 return true;
353 }
354
355 /**
356 * Returns a clone of this component composed of a clone of each concept and
357 * each edge.
358 *
359 * @return a concept lattice
360 */
361 @Override
362 public ConceptLattice clone() {
363 ConceptLattice conceptLattice = new ConceptLattice();
364 TreeMap<Concept, Concept> copy = new TreeMap<Concept, Concept>();
365 for (Object node : this.getNodes()) {
366 Concept c = (Concept) node;
367 Concept c2 = c.clone();
368 copy.put(c, c2);
369 conceptLattice.addNode(c2);
370 }
371 for (Object ed : this.getEdges()) {
372 conceptLattice.addEdge(new Edge(
373 copy.get(((Edge) ed).getSource()),
374 copy.get(((Edge) ed).getTarget()),
375 ((Edge) ed).getContent()
376 ));
377 }
378 return conceptLattice;
379 }
380
381 /*
382 * ------------- SET A AND SET B HANDLING METHOD ------------------
383 */
384 /**
385 * Returns concept defined by setA and setB; null if not found.
386 *
387 * @param setA intent of the concept to find
388 * @param setB extent of the concept to find
389 *
390 * @return concept defined by setA and setB; null if not found.
391 */
392 public Concept getConcept(ComparableSet setA, ComparableSet setB) {
393 SortedSet<Node> setNodes = this.getNodes();
394 Concept cpt = null;
395 for (Node node : setNodes) {
396 if ((setA.equals(((Concept) node).getSetA())) && (setB.equals(((Concept) node).getSetB()))) {
397 cpt = (Concept) node;
398 }
399 }
400 return cpt;
401 }
402
403 /**
404 * Replace set A in each concept of the lattice with the null value.
405 *
406 * @return a boolean
407 *
408 * @todo Comment the return
409 */
410 public boolean removeAllSetA() {
411 if (!this.containsConcepts()) {
412 return false;
413 }
414 for (Object node : this.getNodes()) {
415 Concept c = (Concept) node;
416 c.putSetA(null);
417 }
418 return true;
419 }
420
421 /**
422 * Replace set B in each concept of the lattice with the null value.
423 *
424 * @return a boolean
425 *
426 * @todo Comment the return
427 */
428 public boolean removeAllSetB() {
429 if (!this.containsConcepts()) {
430 return false;
431 }
432 for (Object node : this.getNodes()) {
433 Concept c = (Concept) node;
434 c.putSetB(null);
435 }
436 return true;
437 }
438
439 /**
440 * Replace null set A in each join irreducible concept with a set containing
441 * node ident.
442 *
443 * @return a boolean
444 *
445 * @todo Comment the return
446 */
447 public boolean initialiseSetAForJoin() {
448 if (!this.containsConcepts()) {
449 return false;
450 }
451 TreeSet<Node> joinIrr = this.joinIrreducibles();
452 for (Object node : this.getNodes()) {
453 Concept c = (Concept) node;
454 if (!c.hasSetA() && joinIrr.contains(c)) {
455 ComparableSet setX = new ComparableSet();
456 setX.add(Integer.valueOf(c.getIdentifier()));
457 c.putSetA(setX);
458 }
459 }
460 return true;
461 }
462
463 /**
464 * Replace null set B in each meet irreducible concept with a set containing
465 * node ident.
466 *
467 * @return a boolean
468 *
469 * @todo Comment the return
470 */
471 public boolean initialiseSetBForMeet() {
472 if (!this.containsConcepts()) {
473 return false;
474 }
475 TreeSet<Node> meetIrr = this.meetIrreducibles();
476 for (Object node : this.getNodes()) {
477 Concept c = (Concept) node;
478 if (!c.hasSetB() && meetIrr.contains(c)) {
479 ComparableSet setX = new ComparableSet();
480 setX.add(Integer.valueOf(c.getIdentifier()));
481 c.putSetB(setX);
482 }
483 }
484 return true;
485 }
486
487 /*
488 * --------------- INCLUSION REDUCTION METHODS ------------
489 */
490 /**
491 * Replaces, if not empty, set A of each concept with the difference between
492 * itself and set A of its predecessors; Then replaces, if not empty, set B
493 * of each concept by the difference between itself and set B of its
494 * successors.
495 *
496 * @return a boolean
497 *
498 * @todo Comment the return
499 */
500 public boolean makeInclusionReduction() {
501 if (!this.containsConcepts()) {
502 return false;
503 }
504 boolean setA = this.containsAllSetA();
505 boolean setB = this.containsAllSetB();
506 if (!setA && !setB) {
507 return false;
508 }
509 // makes setA inclusion reduction
510 if (setA) {
511 // computation of an inverse topological sort
512 this.transpose();
513 List<Node> sort = this.topologicalSort();
514 this.transpose();
515 // reduction of set A
516 for (Node to : sort) {
517 Concept cto = (Concept) to;
518 for (Object source : this.getPredecessorNodes(to)) {
519 Concept csource = (Concept) source;
520 cto.getSetA().removeAll(csource.getSetA());
521 }
522 }
523 }
524 // makes setB inclusion reduction
525 if (setB) {
526 // computation of a topological sort
527 List<Node> sort = this.topologicalSort();
528 // reduction of set B
529 for (Node to : sort) {
530 Concept cto = (Concept) to;
531 for (Object source : this.getSuccessorNodes(to)) {
532 Concept csource = (Concept) source;
533 cto.getSetB().removeAll(csource.getSetB());
534 }
535 }
536 }
537 return true;
538 }
539
540 /**
541 * Replaces set A of each join irreducible node by the difference between
542 * itself and set A of the unique predecessor.
543 *
544 * Others closed sets are replaced by an emptyset.
545 *
546 * @return a boolean
547 *
548 * @todo Comment the return
549 */
550 public boolean makeIrreduciblesReduction() {
551 // make inclusion reduction
552 if (this.makeInclusionReduction()) {
553 // check if not set A reduced concepts are join irreducibles
554 // and if not set B reduced concepts are meet irreducibles
555 TreeSet<Node> joinIrr = this.joinIrreducibles();
556 TreeSet<Node> meetIrr = this.meetIrreducibles();
557 for (Object node : this.getNodes()) {
558 Concept c = (Concept) node;
559 if (c.hasSetA() && !c.getSetA().isEmpty() && !joinIrr.contains(c)) {
560 c.putSetA(new ComparableSet());
561 }
562 if (c.hasSetB() && !c.getSetB().isEmpty() && !meetIrr.contains(c)) {
563 c.putSetB(new ComparableSet());
564 }
565 }
566 }
567 return true;
568 }
569
570 /**
571 * Returns a lattice where edges are valuated by the difference between set
572 * A of two adjacent concepts.
573 *
574 * @return a boolean
575 *
576 * @todo Change comment
577 */
578 public boolean makeEdgeValuation() {
579 if (!this.containsConcepts()) {
580 return false;
581 }
582 for (Object n1 : this.getNodes()) {
583 for (Object ed : this.getSuccessorEdges((Node) n1)) {
584 if (!((Edge) ed).hasContent()) {
585 Node n2 = ((Edge) ed).getTarget();
586 TreeSet diff = new TreeSet();
587 diff.addAll(((Concept) n2).getSetA());
588 diff.removeAll(((Concept) n1).getSetA());
589 ((Edge) ed).setContent(diff);
590 }
591 }
592 }
593 return true;
594 }
595
596 /*
597 * --------------- LATTICE GENERATION METHODS ------------
598 */
599 /**
600 * Returns a lattice where join irreducibles node's content is replaced by
601 * the first element of set A.
602 *
603 * Other nodes are replaced by a new comparable.
604 *
605 * @return a lattice
606 */
607 public Lattice getJoinReduction() {
608 if (!this.containsConcepts()) {
609 return null;
610 }
611 if (!this.containsAllSetA()) {
612 return null;
613 }
614 Lattice lattice = new Lattice();
615 //ConceptLattice csl = new ConceptLattice (this);
616 ConceptLattice csl = this.clone();
617 csl.makeIrreduciblesReduction();
618 TreeSet<Node> joinIrr = csl.joinIrreducibles();
619 // addition to lattice of a comparable issued from each reduced closed set
620 TreeMap<Node, Node> reduced = new TreeMap<Node, Node>();
621 for (Object node : csl.getNodes()) {
622 Concept c = (Concept) node;
623 Node nred;
624 if (c.hasSetA() && joinIrr.contains(node)) {
625 nred = new Node(c.getSetA().first());
626 } else {
627 nred = new Node();
628 }
629 reduced.put((Node) node, nred);
630 }
631 // addtion of nodes to lattice
632 for (Object node : csl.getNodes()) {
633 lattice.addNode(reduced.get(node));
634 }
635 // addtion of edges to lattice
636 for (Object source : csl.getNodes()) {
637 for (Object target : csl.getSuccessorNodes((Node) source)) {
638 lattice.addEdge(reduced.get(source), reduced.get(target));
639 }
640 }
641 return lattice;
642 }
643
644 /**
645 * Returns a lattice where meet irreducibles node's content is replaced by
646 * the first element of set B.
647 *
648 * Other nodes are replaced by a new comparable.
649 *
650 * @return a lattice
651 */
652 public Lattice getMeetReduction() {
653 if (!this.containsConcepts()) {
654 return null;
655 }
656 if (!this.containsAllSetB()) {
657 return null;
658 }
659 Lattice lattice = new Lattice();
660 if (!this.containsConcepts()) {
661 return lattice;
662 }
663 //ConceptLattice csl = new ConceptLattice (this);
664 ConceptLattice csl = this.clone();
665 csl.makeIrreduciblesReduction();
666 TreeSet<Node> meetIrr = csl.meetIrreducibles();
667 // addition to lattice of a comparable issued from each reduced closed set
668 TreeMap<Node, Node> reduced = new TreeMap<Node, Node>();
669 for (Object node : csl.getNodes()) {
670 Concept c = (Concept) node;
671 Node nred;
672 if (c.hasSetB() && meetIrr.contains(node)) {
673 nred = new Node(c.getSetB().first());
674 } else {
675 nred = new Node();
676 }
677 reduced.put((Node) node, nred);
678 }
679 for (Object node : csl.getNodes()) {
680 lattice.addNode(reduced.get(node));
681 }
682 // addtion of edges to lattice
683 for (Object source : csl.getNodes()) {
684 for (Object target : csl.getSuccessorNodes((Node) source)) {
685 lattice.addEdge(reduced.get(source), reduced.get(target));
686 }
687 }
688 return lattice;
689 }
690
691 /**
692 * Returns a lattice where each join irreducible concept is replaced by a
693 * node containing the first element of set A, and each meet irreducible
694 * concept is replaced by a node contining the first element of set B.
695 *
696 * A concept that is at once join and meet irreducible is replaced by a node
697 * containing the first element of set A and the first element of set B in a
698 * set. Other nodes are replaced by an empty node.
699 *
700 * @return a lattice
701 */
702 public Lattice getIrreduciblesReduction() {
703 Lattice lattice = new Lattice();
704 if (!this.containsConcepts()) {
705 return lattice;
706 }
707 //ConceptLattice csl = new ConceptLattice (this);
708 ConceptLattice csl = this.clone();
709 csl.makeIrreduciblesReduction();
710 TreeSet<Node> joinIrr = csl.joinIrreducibles();
711 TreeSet<Node> meetIrr = csl.meetIrreducibles();
712 // addition to lattice of a comparable issued from each reduced closed set
713 TreeMap<Node, Node> reduced = new TreeMap<Node, Node>();
714 for (Object node : csl.getNodes()) {
715 Concept c = (Concept) node;
716 // create a new Node with two indexed elements: the first of set A and the first of set B
717 if (c.hasSetA() && c.hasSetB() && meetIrr.contains(c) && joinIrr.contains(c)) {
718 TreeSet<Comparable> content = new TreeSet<Comparable>();
719 content.add(c.getSetA().first());
720 content.add(c.getSetB().first());
721 Node nred = new Node(content);
722 reduced.put((Node) node, nred);
723 } else if (c.hasSetA() && joinIrr.contains(node)) {
724 // create a new Node with the first element of set A
725 Node nred = new Node(((Concept) node).getSetA().first());
726 reduced.put((Node) node, nred);
727 } else if (c.hasSetB() && meetIrr.contains(node)) {
728 // create a new Node with the first element of set A
729 Node nred = new Node(((Concept) node).getSetB().first());
730 reduced.put((Node) node, nred);
731 } else {
732 reduced.put((Node) node, new Node());
733 }
734 }
735 // addtion of nodes to lattice
736 for (Object node : csl.getNodes()) {
737 lattice.addNode(reduced.get(node));
738 }
739 // addtion of edges to lattice
740 for (Object source : csl.getNodes()) {
741 for (Object target : csl.getSuccessorNodes((Node) source)) {
742 lattice.addEdge(reduced.get(source), reduced.get(target));
743 }
744 }
745 return lattice;
746 }
747
748 /**
749 * Returns iceberg lattice whose concept contains enough observations.
750 *
751 * @deprecated use getConceptIceberg method from ClosureSystem class
752 * instead. Are kept only concept whose number of observation is over
753 * threshold. A top node is added to keep the lattice structure.
754 *
755 * @param threshold used to determine nodes to be kept.
756 *
757 * @return iceberg lattice whose concept contains enough observations.
758 */
759 @Deprecated
760 public ConceptLattice iceberg(float threshold) {
761 ConceptLattice l = new ConceptLattice();
762 Concept b = (Concept) this.bottom();
763 int card = b.getSetB().size();
764 for (Object node : this.getNodes()) {
765 Concept cpt = (Concept) node;
766 if ((float) cpt.getSetB().size() / (float) card >= threshold) {
767 l.addNode((Node) node);
768 }
769 }
770 for (Object f : l.getNodes()) {
771 for (Object t : l.getNodes()) {
772 if (this.containsEdge((Node) f, (Node) t)) {
773 l.addEdge((Node) f, (Node) t);
774 }
775 }
776 }
777 Node t = this.top();
778 l.addNode(t);
779 // TODO use Node<Concept>
780 for (Object node : l.getWells()) {
781 if (!node.equals(t)) {
782 l.addEdge((Node) node, t);
783 }
784 }
785 return l;
786 }
787
788 /**
789 * Returns the Hasse diagramme of the closed set lattice of the specified
790 * closure system issued from the specified concept.
791 *
792 * Immediate successors generation is an adaptation of Bordat's theorem
793 * stating that there is a bijection between minimal strongly connected
794 * component of the precedence subgraph issued from the specified node, and
795 * its immediate successors.
796 *
797 * This treatment is performed in O(cCl|S|^3log g) where S is the initial
798 * set of elements, c is the number of closed sets that could be exponential
799 * in the worst case, Cl is the closure computation complexity and g is the
800 * number of minimal generators of the lattice.
801 *
802 * @param n a concept
803 * @param init a closure system
804 */
805 public void recursiveDiagramLattice(Concept n, ClosureSystem init) {
806 Vector<TreeSet<Comparable>> immSucc = this.immediateSuccessors(n, init);
807 for (TreeSet<Comparable> setX : immSucc) {
808 Concept c = new Concept(new TreeSet(setX), false);
809 Concept ns = (Concept) this.getNode(c);
810 if (ns != null) {
811 // when ns already exists, addition of a new edge
812 this.addEdge(n, ns);
813 } else { // when ns don't already exists, addition of a new node and recursive treatment
814 this.addNode(c);
815 this.addEdge(n, c);
816 this.recursiveDiagramLattice(c, init);
817 }
818 }
819 }
820
821 /**
822 * Returns the Hasse diagramme of the closed set iceberg of the specified
823 * closure system issued from the specified concept.
824 *
825 * Immediate successors generation is an adaptation of Bordat's theorem
826 * stating that there is a bijection between minimal strongly connected
827 * component of the precedence subgraph issued from the specified node, and
828 * its immediate successors.
829 *
830 * This treatment is performed in O(cCl|S|^3log g) where S is the initial
831 * set of elements, c is the number of closed sets that could be exponential
832 * in the worst case, Cl is the closure computation complexity and g is the
833 * number of minimal generators of the lattice.
834 *
835 * @param n a concept
836 * @param init a closure system
837 * @param threshold a support threshold, as a number of observations
838 */
839 private void recursiveDiagramIceberg(Concept n, ClosureSystem init, int threshold) {
840 Context context = (Context) init;
841 Vector<TreeSet<Comparable>> immSucc = this.immediateSuccessors(n, init);
842 for (TreeSet<Comparable> setX : immSucc) {
843 if (context.getExtentNb(setX) >= threshold) {
844 Concept c = new Concept(new TreeSet(setX), false);
845 Concept ns = (Concept) this.getNode(c);
846 if (ns != null) {
847 this.addEdge(n, ns);
848 } else {
849 this.addNode(c);
850 this.addEdge(n, c);
851 this.recursiveDiagramIceberg(c, init, threshold);
852 }
853 }
854 }
855 }
856
857 /**
858 * Returns the list of immediate successors of a given node of the lattice.
859 *
860 * This treatment is an adaptation of Bordat's theorem stating that there is
861 * a bijection between minimal strongly connected component of the
862 * precedence subgraph issued from the specified node, and its immediate
863 * successors.
864 *
865 * This treatment is performed in O(Cl|S|^3log g) where S is the initial set
866 * of elements, Cl is the closure computation complexity and g is the number
867 * of minimal generators of the lattice.
868 *
869 * This treatment is recursively invoked by method recursiveDiagramlattice.
870 * In this case, the dependance graph is initialised by method
871 * recursiveDiagramMethod, and updated by this method, with addition some
872 * news edges and/or new valuations on existing edges. When this treatment
873 * is not invoked by method recursiveDiagramLattice, then the dependance
874 * graph is initialised, but it may be not complete. It is the case for
875 * example for on-line generation of the concept lattice.
876 *
877 * @param n a node
878 * @param init a closure system
879 *
880 * @return a set of immediate successors
881 */
882 public Vector<TreeSet<Comparable>> immediateSuccessors(Node n, ClosureSystem init) {
883 // Initialisation of the dependance graph when not initialised by method recursiveDiagramLattice
884 if (!this.hasDependencyGraph()) {
885 ConcreteDGraph graph = new ConcreteDGraph();
886 for (Comparable c : init.getSet()) {
887 graph.addNode(new Node(c));
888 }
889 this.setDependencyGraph(graph);
890 }
891 // computes newVal, the subset to be used to valuate every new dependance relation
892 // newVal = F\predecessors of F in the precedence graph of the closure system
893 // For a non reduced closure system, the precedence graph is not acyclic,
894 // and therefore strongly connected components have to be used.
895 ComparableSet setF = new ComparableSet(((Concept) n).getSetA());
896 ConcreteDGraph prec = init.precedenceGraph();
897 DAGraph acyclPrec = prec.getStronglyConnectedComponent();
898 ComparableSet newVal = new ComparableSet();
899 newVal.addAll(setF);
900 for (Object x : setF) {
901 // computes nx, the strongly connected component containing x
902 Node nx = null;
903 for (Object cc : acyclPrec.getNodes()) {
904 TreeSet<Node> setCC = (TreeSet<Node>) ((Node) cc).getContent();
905 for (Node y : setCC) {
906 if (x.equals(y.getContent())) {
907 nx = (Node) cc;
908 }
909 }
910 }
911 // computes the minorants of nx in the acyclic graph
912 SortedSet<Node> ccMinNx = acyclPrec.minorants(nx);
913 // removes from newVal every minorants of nx
914 for (Node cc : ccMinNx) {
915 TreeSet<Node> setCC = (TreeSet<Node>) cc.getContent();
916 for (Node y : setCC) {
917 newVal.remove(y.getContent());
918 }
919 }
920 }
921 // computes the node belonging in S\F
922 TreeSet<Node> nodes = new TreeSet<Node>();
923 for (Object in : this.getDependencyGraph().getNodes()) {
924 if (!setF.contains(((Node) in).getContent())) {
925 nodes.add((Node) in);
926 }
927 }
928 // computes the dependance relation between nodes in S\F
929 // and valuated this relation by the subset of S\F
930 TreeSet<Edge> edges = new TreeSet<Edge>();
931 for (Node source : nodes) {
932 for (Node target : nodes) {
933 if (!source.equals(target)) {
934 // check if source is in dependance relation with target
935 // i.e. "source" belongs to the closure of "F+target"
936 ComparableSet fPlusTo = new ComparableSet(setF);
937 fPlusTo.add(target.getContent());
938 fPlusTo = new ComparableSet(init.closure(fPlusTo));
939 if (fPlusTo.contains(source.getContent())) {
940 // there is a dependance relation between source and target
941 // search for an existing edge between source and target
942 Edge ed = this.getDependencyGraph().getEdge(source, target);
943 if (ed == null) {
944 ed = new Edge(source, target, new TreeSet<ComparableSet>());
945 this.getDependencyGraph().addEdge(ed);
946 }
947 edges.add(ed);
948 // check if F is a minimal set closed for dependance relation between source and target
949 ((TreeSet<ComparableSet>) ed.getContent()).add(newVal);
950 TreeSet<ComparableSet> valEd = new TreeSet<ComparableSet>((TreeSet<ComparableSet>) ed.getContent());
951 for (ComparableSet x1 : valEd) {
952 if (x1.containsAll(newVal) && !newVal.containsAll(x1)) {
953 ((TreeSet<ComparableSet>) ed.getContent()).remove(x1);
954 }
955 if (!x1.containsAll(newVal) && newVal.containsAll(x1)) {
956 ((TreeSet<ComparableSet>) ed.getContent()).remove(newVal);
957 }
958 }
959 }
960 }
961 }
962 }
963 // computes the dependance subgraph of the closed set F as the reduction
964 // of the dependance graph composed of nodes in S\A and edges of the dependance relation
965 ConcreteDGraph sub = this.getDependencyGraph().getSubgraphByNodes(nodes);
966 ConcreteDGraph delta = sub.getSubgraphByEdges(edges);
967 // computes the sources of the CFC of the dependance subgraph
968 // that corresponds to successors of the closed set F
969 DAGraph cfc = delta.getStronglyConnectedComponent();
970 SortedSet<Node> sccMin = cfc.getSinks();
971 Vector<TreeSet<Comparable>> immSucc = new Vector<TreeSet<Comparable>>();
972 for (Node n1 : sccMin) {
973 TreeSet s = new TreeSet(setF);
974 TreeSet<Node> toadd = (TreeSet<Node>) n1.getContent();
975 for (Node n2 : toadd) {
976 s.add(n2.getContent());
977 }
978 immSucc.add(s);
979 }
980 return immSucc;
981 }
982
983 /**
984 * Save the description of this component in a file whose name is specified.
985 *
986 * @param filename the name of the file
987 *
988 * @throws IOException When an IOException occurs
989 */
990 @Override
991 public void save(final String filename) throws IOException {
992 Filer.getInstance().save(this, ConceptLatticeIOFactory.getInstance(), filename);
993 }
994 }