1 package org.thegalactic.lattice;
2
3 /*
4 * Concept.java
5 *
6 *
7 * Copyright: 2010-2015 Karell Bertet, France
8 * Copyright: 2015-2016 The Galactic Organization, France
9 *
10 * License: http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html CeCILL-B license
11 *
12 * This file is part of java-lattices.
13 * You can redistribute it and/or modify it under the terms of the CeCILL-B license.
14 */
15 import java.util.ArrayList;
16 import java.util.Iterator;
17 import java.util.Set;
18 import java.util.SortedSet;
19 import java.util.TreeSet;
20
21 import org.thegalactic.context.Context;
22 import org.thegalactic.dgraph.DAGraph;
23 import org.thegalactic.dgraph.ConcreteDGraph;
24 import org.thegalactic.dgraph.Edge;
25 import org.thegalactic.dgraph.Node;
26 import org.thegalactic.util.ComparableSet;
27
28 /**
29 * This class gives a representation for a concept, i.e. a node of a concept
30 * lattice.
31 *
32 * A concept extends class {@link Node} by providing two comparable sets defined
33 * by {@link ComparableSet}, namely `setA` and `setB`, aiming at storing set of
34 * a concepts.
35 *
36 * This component can also be used to store a closed set by using only set `A`.
37 *
38 * This class implements class `Comparable` aiming at sorting concepts by
39 * providing the {@link #compareTo} method. Comparison between this component
40 * and those in parameter is realised by comparing set `A`.
41 *
42 * @todo Should not inherit from Node since content is not used. Maybe by using
43 * interface.
44 *
45 * 
46 *
47 * @uml Concept.png
48 * !include resources/org/thegalactic/dgraph/Node.iuml
49 * !include resources/org/thegalactic/lattice/Concept.iuml
50 * !include resources/org/thegalactic/util/ComparableSet.iuml
51 *
52 * hide members
53 * show Concept members
54 * class Concept #LightCyan
55 * title Concept UML graph
56 */
57 public class Concept extends Node {
58
59 /*
60 * ------------- FIELDS ------------------
61 */
62 /**
63 * This first set of comparable elements of the concept.
64 */
65 private ComparableSet setA = null;
66
67 /**
68 * This second set of comparable elements of the concept.
69 */
70 private ComparableSet setB = null;
71
72 /*
73 * ------------- CONSTRUCTORS ------------------
74 */
75 /**
76 * Constructs a new concept containing the specified comparables set as setA
77 * and setB.
78 *
79 * @param setA set of comparable used to initialise setA.
80 * @param setB set of comparable used to initialise setB.
81 */
82 public Concept(TreeSet<Comparable> setA, TreeSet<Comparable> setB) {
83 this.setA = new ComparableSet(setA);
84 this.setB = new ComparableSet(setB);
85 }
86
87 /**
88 * Constructs a new concept with an empty set of comparableset as setA and
89 * set B if the two boolean are true. False booleans allow to construct a
90 * concept with only one of the two sets.
91 *
92 * @param setA field setA is empty if true, setA is null if false.
93 * @param setB field setB is empty if true, setB is null if false.
94 */
95 public Concept(boolean setA, boolean setB) {
96 if (setA) {
97 this.setA = new ComparableSet();
98 }
99 if (setB) {
100 this.setB = new ComparableSet();
101 }
102 }
103
104 /**
105 * Constructs a new concept containing the specified comparables set as
106 * setA, and an empty set of comparableset as setB if the boolean is true. A
107 * false boolean allows to construct a concept with the only set A.
108 *
109 * @param setA set of comparable used to initialise setA.
110 * @param setB field setB is empty if true, setB is null if false.
111 */
112 public Concept(TreeSet<Comparable> setA, boolean setB) {
113 this.setA = new ComparableSet(setA);
114 if (setB) {
115 this.setB = new ComparableSet();
116 }
117 }
118
119 /**
120 * Constructs a new concept containing the specified comparables set as
121 * setB, and an empty set of comparableset as setA if the boolean is true. A
122 * false boolean allows to construct concept with the only set B.
123 *
124 * @param setA field setA is empty if true, setA is null if false.
125 * @param setB set of comparable used to initialise setB.
126 */
127 public Concept(boolean setA, TreeSet<Comparable> setB) {
128 this.setB = new ComparableSet(setB);
129 if (setA) {
130 this.setA = new ComparableSet();
131 }
132 }
133
134 /**
135 * Constructs this component as a copy of the specified ClosedSet.
136 *
137 * @param c the closed set to be copied
138 */
139 public Concept(Concept c) {
140 if (c.hasSetA()) {
141 this.setA = new ComparableSet(c.getSetA());
142 } else {
143 this.setA = null;
144 }
145 if (c.hasSetB()) {
146 this.setB = new ComparableSet(c.getSetB());
147 } else {
148 this.setB = null;
149 }
150 }
151
152 /*
153 * --------------- ACCESSOR AND OVERLAPPING METHODS ------------
154 */
155 /**
156 * Returns a clone of this component.
157 *
158 * @return a clone of this component
159 */
160 @Override
161 public Concept clone() {
162 if (this.hasSetA() && this.hasSetB()) {
163 TreeSet setA = (TreeSet) this.getSetA().clone();
164 TreeSet setB = (TreeSet) this.getSetB().clone();
165 return new Concept(setA, setB);
166 }
167 if (this.hasSetA() && !this.hasSetB()) {
168 TreeSet setA = (TreeSet) this.getSetA().clone();
169 return new Concept(setA, false);
170 } else if (this.hasSetB()) {
171 TreeSet setB = (TreeSet) this.getSetB().clone();
172 return new Concept(false, setB);
173 } else {
174 return new Concept(false, false);
175 }
176 }
177
178 /**
179 * Checks if the concept has an empty set B.
180 *
181 * @return true if and only if setB is not null
182 */
183 public boolean hasSetB() {
184 return this.setB != null;
185 }
186
187 /**
188 * Checks if the concept has an empty set A.
189 *
190 * @return true if and only if setA is not null
191 */
192 public boolean hasSetA() {
193 return this.setA != null;
194 }
195
196 /**
197 * Returns the set A of this component.
198 *
199 * @return the set A of this component
200 */
201 public TreeSet<Comparable> getSetA() {
202 return this.setA;
203 }
204
205 /**
206 * Returns the set B of comparable of this component.
207 *
208 * @return the set B of this component.
209 */
210 public TreeSet<Comparable> getSetB() {
211 return this.setB;
212 }
213
214 /**
215 * Checks if the set A contains the specified comparable.
216 *
217 * @param x comparable to find in setA.
218 *
219 * @return true if and only if setA contains x.
220 */
221 public boolean containsInA(Comparable x) {
222 if (this.hasSetA()) {
223 return this.setA.contains(x);
224 } else {
225 return false;
226 }
227 }
228
229 /**
230 * Checks if the set B contains the specified comparable.
231 *
232 * @param x comparable to find in setB.
233 *
234 * @return true if and only if setB contains x.
235 */
236 public boolean containsInB(Comparable x) {
237 if (this.hasSetB()) {
238 return this.setB.contains(x);
239 } else {
240 return false;
241 }
242 }
243
244 /**
245 * Checks if the set A contains the specified set of comparable.
246 *
247 * @param x set of comparable to find in setA.
248 *
249 * @return true if and only if setA contains all elemens of x.
250 */
251 public boolean containsAllInA(TreeSet x) {
252 if (this.hasSetA()) {
253 return this.setA.containsAll(x);
254 } else {
255 return false;
256 }
257 }
258
259 /**
260 * Checks if the set B contains the specified set of comparable.
261 *
262 * @param x set of comparable to find in setB.
263 *
264 * @return true if and only if setB contains all elemens of x.
265 */
266 public boolean containsAllInB(TreeSet x) {
267 if (this.hasSetB()) {
268 return this.setB.containsAll(x);
269 } else {
270 return false;
271 }
272 }
273
274 /**
275 * Replaces the set A of this component by the specified one.
276 *
277 * @param x set of comparable used to replace setB
278 */
279 public void putSetB(ComparableSet x) {
280 if (this.hasSetB()) {
281 this.setB = x;
282 } else {
283 this.setB = new ComparableSet(x);
284 }
285 }
286
287 /**
288 * Replaces the set A of this component by the specified one.
289 *
290 * @param x set of comparable used to replace setA
291 */
292 public void putSetA(ComparableSet x) {
293 if (this.hasSetA()) {
294 this.setA = x;
295 } else {
296 this.setA = new ComparableSet(x);
297 }
298 }
299
300 /**
301 * Adds a comparable to the set A.
302 *
303 * @param x comparable to add to setA
304 *
305 * @return true if and only if addition is successful.
306 */
307 public boolean addToA(Comparable x) {
308 if (this.hasSetA()) {
309 return this.setA.add(x);
310 } else {
311 return false;
312 }
313 }
314
315 /**
316 * Adds a comparable to the set B.
317 *
318 * @param x comparable to add to setB
319 *
320 * @return true if and only if addition is successful.
321 */
322 public boolean addToB(Comparable x) {
323 if (this.hasSetB()) {
324 return this.setB.add(x);
325 } else {
326 return false;
327 }
328 }
329
330 /**
331 * Adds the specified set of comparable to the set A.
332 *
333 * @param x set of comparable to add to setA
334 *
335 * @return true if and only if addition is successful.
336 */
337 public boolean addAllToA(TreeSet x) {
338 if (this.hasSetA()) {
339 return this.setA.addAll(x);
340 } else {
341 return false;
342 }
343 }
344
345 /**
346 * Adds the specified set of comparable to the set B.
347 *
348 * @param x set of comparable to add to setB
349 *
350 * @return true if and only if addition is successful.
351 */
352 public boolean addAllToB(TreeSet x) {
353 if (this.hasSetB()) {
354 return this.setB.addAll(x);
355 } else {
356 return false;
357 }
358 }
359
360 /**
361 * Remove a comparable from the set A.
362 *
363 * @param x comparable to remove from setA
364 *
365 * @return true if and only if removal is successful.
366 */
367 public boolean removeFromA(Comparable x) {
368 if (this.hasSetA()) {
369 return this.setA.remove(x);
370 } else {
371 return false;
372 }
373 }
374
375 /**
376 * Remove a comparable from the set B.
377 *
378 * @param x comparable to remove from setB
379 *
380 * @return true if and only if removal is successful.
381 */
382 public boolean removeFromB(Comparable x) {
383 if (this.hasSetB()) {
384 return this.setB.remove(x);
385 } else {
386 return false;
387 }
388 }
389
390 /**
391 * Remove a set of comparable from the set A.
392 *
393 * @param x set to remove from setA
394 *
395 * @return true if and only if removal is successful.
396 */
397 public boolean removeAllFromA(TreeSet x) {
398 if (this.hasSetA()) {
399 return this.setA.removeAll(x);
400 } else {
401 return false;
402 }
403 }
404
405 /**
406 * Remove a set of comparable from the set B.
407 *
408 * @param x set to remove from setB
409 *
410 * @return true if and only if removal is successful.
411 */
412 public boolean removeAllFromB(TreeSet x) {
413 if (this.hasSetB()) {
414 return this.setB.removeAll(x);
415 } else {
416 return false;
417 }
418 }
419
420 /*
421 * --------------- OVERLAPPING METHODS ------------
422 */
423 /**
424 * Returns the description of this component in a String without spaces.
425 *
426 * @return the description of this component in a String without spaces.
427 */
428 @Override
429 public String toString() {
430 StringBuilder builder = new StringBuilder();
431 if (this.hasSetA()) {
432 builder.append(this.setA);
433 }
434 if (this.hasSetA() && this.hasSetB()) {
435 builder.append('-');
436 }
437 if (this.hasSetB()) {
438 builder.append(this.setB);
439 }
440 return builder.toString();
441 }
442
443 /**
444 * Returns the hash code of this component.
445 *
446 * @return hash code of this component
447 */
448 @Override
449 public int hashCode() {
450 return super.hashCode();
451 }
452
453 /**
454 * Compares this component with the specified one.
455 *
456 * @param o object compared to this component.
457 *
458 * @return true if and only if o is equals to this component.
459 */
460 @Override
461 public boolean equals(Object o) {
462 if (!(o instanceof Concept)) {
463 return false;
464 }
465 if (!this.hasSetB()) {
466 return this.setA.equals(((Concept) o).setA);
467 }
468 if (!this.hasSetA()) {
469 return this.setB.equals(((Concept) o).setB);
470 }
471 return this.setA.equals(((Concept) o).setA) && this.setB.equals(((Concept) o).setB);
472 }
473
474 /**
475 * Compares this component with the specified one sorted by the lectic
476 * order.
477 *
478 * @return a negative integer, zero, or a positive integer as this component
479 * is less than, equal to, or greater than the specified object.
480 */
481 /*
482 * public int compareTo(Object o){
483 * if (!(o instanceof lattice.Concept)) return -1;
484 * Concept c = (Concept) o;
485 * //System.out.println("compareTo : "+this+" "+o);
486 * if (!this.hasSetB()) {
487 * return this.setA.compareTo(c.setA);
488 * }
489 * if (!this.hasSetA()) {
490 * return this.setB.compareTo(c.setB);
491 * }
492 * if (this.setA.compareTo(c.setA)!=0) {
493 * return this.setB.compareTo(c.setB);
494 * } else {
495 * return this.setA.compareTo(c.setA);
496 * }
497 * }
498 */
499 /**
500 * Computes the immediate successors of this component with the LOA
501 * algorithm.
502 *
503 * @param init context from which successor of this component are computed.
504 *
505 * @return immediate successors of this component.
506 */
507 public ArrayList<TreeSet<Comparable>> immediateSuccessorsLOA(Context init) {
508 ArrayList<TreeSet<Comparable>> succB = new ArrayList();
509 TreeSet<Comparable> attributes = (TreeSet<Comparable>) init.getSet().clone();
510 attributes.removeAll(this.getSetA());
511
512 boolean add;
513 for (Comparable x : attributes) {
514 add = true;
515 Iterator it = succB.iterator();
516 while (it.hasNext()) {
517 TreeSet tX = (TreeSet) it.next();
518 TreeSet<Comparable> bx = (TreeSet<Comparable>) this.getSetA().clone();
519 bx.add(x);
520 TreeSet<Comparable> bX = (TreeSet<Comparable>) this.getSetA().clone();
521 bX.addAll(tX);
522 TreeSet<Comparable> bXx = (TreeSet<Comparable>) bX.clone();
523 bXx.add(x);
524 int cBx = count(init, bx);
525 int cBX = count(init, bX);
526 int cBXx = count(init, bXx);
527 if (cBx == cBX) { // Try to group tests by pairs.
528 if (cBXx == cBx) {
529 it.remove(); // Update present potential successor.
530 TreeSet<Comparable> xX = new TreeSet();
531 xX.addAll(tX);
532 xX.add(x);
533 succB.add(xX);
534 add = false;
535 break;
536 }
537 }
538 if (cBx < cBX) {
539 if (cBXx == cBx) {
540 add = false;
541 break;
542 }
543 }
544 if (cBx > cBX) {
545 if (cBXx == cBX) {
546 it.remove();
547 }
548 }
549 }
550 if (add) {
551 TreeSet<Comparable> t = new TreeSet();
552 t.add(x);
553 succB.add(new TreeSet(t));
554 }
555 }
556 for (TreeSet t : succB) {
557 t.addAll(this.getSetA());
558 }
559 return succB;
560 }
561
562 /**
563 * Returns the number of observations corresponding to the set of attributes
564 * in the init context.
565 *
566 * @param init initial context from which attributes are count.
567 * @param attributes attributes from which observations are counted.
568 *
569 * @return number of observations corresponding to the set of attributes in
570 * init context.
571 */
572 private int count(Context init, TreeSet<Comparable> attributes) {
573 return init.getExtentNb(attributes);
574 }
575
576 /**
577 * Returns the list of immediate successors of a given node of the lattice.
578 *
579 * This treatment is an adaptation of Bordat's theorem stating that there is
580 * a bijection between minimal strongly connected component of the
581 * precedence subgraph issued from the specified node, and its immediate
582 * successors.
583 *
584 * This treatment is performed in O(Cl|S|^3log g) where S is the initial set
585 * of elements, Cl is the closure computation complexity and g is the number
586 * of minimal generators of the lattice.
587 *
588 * This treatment is recursively invoked by method recursiveDiagramlattice.
589 * In this case, the dependance graph is initialised by method
590 * recursiveDiagramMethod, and updated by this method, with addition some
591 * news edges and/or new valuations on existing edges. When this treatment
592 * is not invoked by method recursiveDiagramLattice, then the dependance
593 * graph is initialised, but it may be not complete. It is the case for
594 * example for on-line generation of the concept lattice.
595 *
596 * cguerin - 2013-04-12 - transfer immedateSuccessors method from
597 * ConceptLattice to Concept
598 *
599 * @param init closure system used to compute immediate successors of this
600 * component.
601 *
602 * @return the list of immediate successors of this component.
603 */
604 public ArrayList<TreeSet<Comparable>> immediateSuccessors(ClosureSystem init) {
605 // Initialisation of the dependance graph when not initialised by method recursiveDiagramLattice
606 ConcreteDGraph<Comparable, ?> dependenceGraph = new ConcreteDGraph<Comparable, Object>();
607 for (Comparable c : init.getSet()) {
608 dependenceGraph.addNode(new Node(c));
609 }
610 // computes newVal, the subset to be used to valuate every new dependance relation
611 // newVal = F\predecessors of F in the precedence graph of the closure system
612 // For a non reduced closure system, the precedence graph is not acyclic,
613 // and therefore strongly connected components have to be used.
614 ComparableSet f = new ComparableSet(this.getSetA());
615 long start = System.currentTimeMillis();
616 System.out.print("Precedence graph... ");
617 ConcreteDGraph prec = init.precedenceGraph();
618 System.out.println(System.currentTimeMillis() - start + "ms");
619 start = System.currentTimeMillis();
620 System.out.print("Srongly connected component... ");
621 DAGraph<SortedSet<Node<Comparable>>, ?> acyclPrec = prec.getStronglyConnectedComponent();
622 System.out.println(System.currentTimeMillis() - start + "ms");
623 ComparableSet newVal = new ComparableSet();
624 newVal.addAll(f);
625 for (Object x : f) {
626 // computes nx, the strongly connected component containing x
627 Node<SortedSet<Node<Comparable>>> nx = null;
628 for (Node cc : acyclPrec.getNodes()) {
629 TreeSet<Node> cC = (TreeSet<Node>) cc.getContent();
630 for (Node y : cC) {
631 if (x.equals(y.getContent())) {
632 nx = cc;
633 }
634 }
635 }
636 // computes the minorants of nx in the acyclic graph
637 SortedSet<Node<SortedSet<Node<Comparable>>>> ccMinNx = acyclPrec.minorants(nx);
638 // removes from newVal every minorants of nx
639 for (Node cc : ccMinNx) {
640 TreeSet<Node> cC = (TreeSet<Node>) cc.getContent();
641 for (Node y : cC) {
642 newVal.remove(y.getContent());
643 }
644 }
645 }
646 // computes the node belonging in S\F
647 Set<Node<Comparable>> n = new TreeSet<Node<Comparable>>();
648 for (Node in : dependenceGraph.getNodes()) {
649 if (!f.contains(in.getContent())) {
650 n.add(in);
651 }
652 }
653 System.out.print("Dependance... ");
654 start = System.currentTimeMillis();
655 // computes the dependance relation between nodes in S\F
656 // and valuated this relation by the subset of S\F
657 TreeSet<Edge> e = new TreeSet<Edge>();
658 for (Node source : n) {
659 for (Node target : n) {
660 if (!source.equals(target)) {
661 // check if source is in dependance relation with target
662 // i.e. "source" belongs to the closure of "F+target"
663 ComparableSet fPlusTo = new ComparableSet(f);
664 fPlusTo.add(target.getContent());
665 fPlusTo = new ComparableSet(init.closure(fPlusTo));
666 if (fPlusTo.contains(source.getContent())) {
667 // there is a dependance relation between source and target
668 // search for an existing edge between source and target
669 Edge ed = dependenceGraph.getEdge(source, target);
670 if (ed == null) {
671 ed = new Edge(source, target, new TreeSet<ComparableSet>());
672 dependenceGraph.addEdge(ed);
673 }
674 e.add(ed);
675 // check if F is a minimal set closed for dependance relation between source and target
676 ((TreeSet<ComparableSet>) ed.getContent()).add(newVal);
677 TreeSet<ComparableSet> valEd = new TreeSet<ComparableSet>((TreeSet<ComparableSet>) ed.getContent());
678 for (ComparableSet x1 : valEd) {
679 if (x1.containsAll(newVal) && !newVal.containsAll(x1)) {
680 ((TreeSet<ComparableSet>) ed.getContent()).remove(x1);
681 }
682 if (!x1.containsAll(newVal) && newVal.containsAll(x1)) {
683 ((TreeSet<ComparableSet>) ed.getContent()).remove(newVal);
684 }
685 }
686 }
687 }
688 }
689 }
690 System.out.println(System.currentTimeMillis() - start + "ms");
691 System.out.print("Subgraph... ");
692 start = System.currentTimeMillis();
693 // computes the dependance subgraph of the closed set F as the reduction
694 // of the dependance graph composed of nodes in S\A and edges of the dependance relation
695 ConcreteDGraph sub = dependenceGraph.getSubgraphByNodes(n);
696 ConcreteDGraph delta = sub.getSubgraphByEdges(e);
697 // computes the sources of the CFC of the dependance subgraph
698 // that corresponds to successors of the closed set F
699 DAGraph cfc = delta.getStronglyConnectedComponent();
700 SortedSet<Node> sccmin = cfc.getSinks();
701 System.out.println(System.currentTimeMillis() - start + "ms");
702 ArrayList<TreeSet<Comparable>> immSucc = new ArrayList<TreeSet<Comparable>>();
703 for (Node n1 : sccmin) {
704 TreeSet s = new TreeSet(f);
705 TreeSet<Node> toadd = (TreeSet<Node>) n1.getContent();
706 for (Node n2 : toadd) {
707 s.add(n2.getContent());
708 }
709 immSucc.add(s);
710 }
711 return immSucc;
712 }
713 }