View Javadoc
1   package org.thegalactic.context;
2   
3   /*
4    * Context.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 java.io.IOException;
15  import java.util.ArrayList;
16  import java.util.BitSet;
17  import java.util.Iterator;
18  import java.util.LinkedList;
19  import java.util.Random;
20  import java.util.SortedSet;
21  import java.util.TreeMap;
22  import java.util.TreeSet;
23  import java.util.Vector;
24  
25  import org.thegalactic.context.io.ContextIOFactory;
26  import org.thegalactic.dgraph.Node;
27  import org.thegalactic.io.Filer;
28  import org.thegalactic.lattice.ArrowRelation;
29  import org.thegalactic.lattice.ClosureSystem;
30  import org.thegalactic.lattice.Concept;
31  import org.thegalactic.lattice.ConceptLattice;
32  import org.thegalactic.lattice.Lattice;
33  import org.thegalactic.util.ComparableSet;
34  import org.thegalactic.util.Couple;
35  
36  /**
37   * This class gives a standard representation for a context.
38   * A context is a binary table, with attributes in column, and observations
39   * in row.
40   *
41   * A context is composed of
42   *
43   * - attributes, a treeset of comparable objects;
44   * - observations, a treeset of comparable objects;
45   * - a Galois connexion (extent,intent) between objects and attributes where
46   * `extent` is a TreeMap that associates to each attribute a TreeSet of
47   * observations and
48   * `intent` is a TreeMap that associates to each observation a TreeSet of
49   * attributes.
50   *
51   * This class provides methods implementing classical operation on a context:
52   * closure, reduction, reverse, ...
53   *
54   * A context owns properties of a closure system, and thus extends the abstract
55   * class
56   * {@link ClosureSystem} and implements methods {@link #getSet} and
57   * {@link #closure}.
58   * Therefore, the closed set lattice of a context can be generated by invoking
59   * method
60   * {@link ClosureSystem#closedSetLattice} of a closure system.
61   * However, this class also provides a method generating the concept lattice of
62   * this component
63   * by completing each closed set of the closed set lattice.
64   *
65   * A context can be instancied from and save to a text file in the following
66   * format:
67   *
68   * - the list of observations separated by a space on the first line;
69   * - the list of attrbutes separated by a space on the second line;
70   * - then, for each observations o, the list of its intent on a line, written
71   * like o a1 a2 ...
72   *
73   * ~~~
74   * Observations: 1 2 3
75   * Attributes: a b c d e
76   * 1: a c
77   * 2: a b
78   * 3: b d e
79   * 4: c e
80   * ~~~
81   *
82   * ![Context](Context.png)
83   *
84   * @uml Context.png
85   * !include resources/org/thegalactic/context/Context.iuml
86   * !include resources/org/thegalactic/lattice/ClosureSystem.iuml
87   *
88   * hide members
89   * show Context members
90   * class Context #LightCyan
91   * title Context UML graph
92   */
93  public class Context extends ClosureSystem {
94  
95      /**
96       * Generates a partially random context.
97       *
98       * @param nbObs        number of observations
99       * @param nbGrp        number of groups of attributes . Attributes are
100      *                     grouped such that each observation has one
101      *                     attribute per group.
102      * @param nbAttrPerGrp number of attributes per group.
103      *
104      * @return randomly generated context
105      */
106     public static Context random(int nbObs, int nbGrp, int nbAttrPerGrp) {
107         Context ctx = new Context();
108         StringBuilder name = new StringBuilder();
109         // Generates Observations.
110         for (int i = 1; i <= nbObs; i++) {
111             ctx.addToObservations(Integer.toString(i));
112         }
113         // Generates Attributes.
114         for (int i = 1; i <= nbGrp; i++) {
115             for (int j = 1; j <= nbAttrPerGrp; j++) {
116                 int q = i;
117                 name.setLength(0);
118                 do {
119                     int rem = q % 26;
120                     q = q / 26;
121                     name.append((char) (rem + 65));
122                 } while (q != 0);
123                 name.append(j);
124                 ctx.addToAttributes(name.toString());
125             }
126         }
127         // Generates all requested observations.
128         Random r = new Random();
129         int attr = r.nextInt(nbAttrPerGrp) + 1;
130         for (int i = 1; i <= nbObs; i++) {
131             // i : Observation
132             for (int j = 1; j <= nbGrp; j++) {
133                 // j : Familly
134                 int q = j;
135                 // Clear the StringBuilder
136                 name.setLength(0);
137                 do {
138                     int rem = q % 26;
139                     q = q / 26;
140                     name.append((char) (rem + 65));
141                 } while (q != 0);
142                 name.append(attr);
143                 ctx.addExtentIntent(Integer.toString(i), name.toString());
144                 attr = r.nextInt(nbAttrPerGrp) + 1;
145             }
146         }
147         ctx.setBitSets();
148         return ctx;
149     }
150 
151     /*
152      * ------------- FIELD ------------------
153      */
154     /**
155      * A set of observations.
156      */
157     private TreeSet<Comparable> observations;
158 
159     /**
160      * A set of attributes.
161      */
162     private TreeSet<Comparable> attributes;
163 
164     /**
165      * A map to associate a set of attributes to each observation.
166      */
167     private TreeMap<Comparable, TreeSet<Comparable>> intent;
168 
169     /**
170      * A map to associate a set of observations to each attribute.
171      */
172     private TreeMap<Comparable, TreeSet<Comparable>> extent;
173 
174     /*
175      * ------------- BITSET ADDON ------------------
176      */
177     /**
178      * A bit set for intent.
179      */
180     private TreeMap<Comparable, BitSet> bitsetIntent;
181 
182     /**
183      * A bit set for extent.
184      */
185     private TreeMap<Comparable, BitSet> bitsetExtent;
186 
187     /**
188      * An array for observations.
189      */
190     private ArrayList<Comparable> arrayObservations;
191 
192     /**
193      * An array for attributes.
194      */
195     private ArrayList<Comparable> arrayAttributes;
196 
197     /*
198      * ------------- CONSTRUCTORS ------------------
199      */
200     /**
201      * Constructs a new empty context.
202      */
203     public Context() {
204         this.init();
205     }
206 
207     /**
208      * Constructs a new context as a copy of the specified context.
209      *
210      * @param context context to be copied
211      */
212     public Context(Context context) {
213         this();
214         this.attributes.addAll(context.getAttributes());
215         this.observations.addAll(context.getObservations());
216         for (Comparable o : context.getObservations()) {
217             this.intent.put(o, new TreeSet(context.getIntent(o)));
218         }
219         for (Comparable a : context.getAttributes()) {
220             this.extent.put(a, new TreeSet(context.getExtent(a)));
221         }
222         this.setBitSets();
223     }
224 
225     /**
226      * Constructs this component from the specified file.
227      *
228      * The file have to respect a certain format:
229      *
230      * The list of observations separated by a space on the first line ;
231      * the list of attrbutes separated by a space on the second line ;
232      * then, for each observations o, the list of its intent on a line, written
233      * like o a1 a2 ...
234      *
235      * ~~~
236      * Observations: 1 2 3
237      * Attributes: a b c d e
238      * 1: a c
239      * 2: a b
240      * 3: b d e
241      * 4: c e
242      * ~~~
243      *
244      * Each observation must be declared on the first line, otherwise, it is not
245      * added.
246      * Each attribute must be declared on the second line, otherwise, it is not
247      * added.
248      *
249      * @param filename the name of the file
250      *
251      * @throws IOException When an IOException occurs
252      */
253     public Context(String filename) throws IOException {
254         this.parse(filename);
255     }
256 
257     /**
258      * Initialise the context.
259      *
260      * @return this for chaining
261      */
262     public Context init() {
263         this.observations = new TreeSet();
264         this.attributes = new TreeSet();
265         this.intent = new TreeMap();
266         this.extent = new TreeMap();
267         this.bitsetIntent = new TreeMap();
268         this.bitsetExtent = new TreeMap();
269         this.arrayObservations = new ArrayList();
270         this.arrayAttributes = new ArrayList();
271         return this;
272     }
273 
274     /**
275      * Returns subcontext with selected obs and attr.
276      *
277      * @param obs  : observations to be keeped
278      * @param attr : attributes to be keeped
279      *
280      * @return subcontext with selected obs and attr.
281      */
282     public Context getSubContext(TreeSet<Comparable> obs, TreeSet<Comparable> attr) {
283         Context ctx = new Context();
284         ctx.addAllToAttributes(attr);
285         ctx.addAllToObservations(obs);
286         for (Comparable o : obs) {
287             for (Comparable a : attr) {
288                 if (this.getIntent(o).contains(a)) {
289                     ctx.addExtentIntent(o, a);
290                 }
291             }
292         }
293         ctx.setBitSets();
294         return ctx;
295     }
296 
297     /**
298      * Returns the context defining the concept lattice of arrow-closed
299      * subcontexts of this component.
300      *
301      * Each observation of the returned context is a $1$-generated arrow-closed
302      * subcontext.
303      * The observation used to generate the context is used as a name for the
304      * subcontext.
305      * Attributes are the same of this component, and are used to defined the
306      * subcontext.
307      *
308      * @return the context defining the concept lattice of arrow-closed
309      *         subcontexts of this component.
310      */
311     public Context getArrowClosedSubContext() {
312         Context result = new Context();
313         result.addAllToAttributes(this.getAttributes());
314         for (Comparable o : this.getObservations()) {
315             result.addToObservations(o);
316             TreeSet<Comparable> setO = new TreeSet<Comparable>();
317             setO.add(o);
318             Context c = this.arrowClosureObject(setO);
319             for (Comparable a : c.getAttributes()) {
320                 result.addExtentIntent(o, a);
321             }
322         }
323         return result;
324     }
325 
326     /**
327      * Returns a list of subcontexts such that the concept lattice of this
328      * component is obtained from a subcontext by doubling a convex.
329      *
330      * Each subcontext defines a concept lattice L. With the getDivisionConvex
331      * method, a convex C of this conceptĀ lattice is obtained.
332      * By doubling the convex set C of L, we get L[C], the concept lattice of
333      * this component.
334      *
335      * @return a list of subcontexts such that the concept lattice of this
336      *         component is obtained from a subcontext by doubling a convex.
337      */
338     public ArrayList<Context> getDivisionContext() {
339         Context arrowCtx = this.getArrowClosedSubContext();
340         arrowCtx.reverse(); // We need co-atoms which are atoms of the reverse context.
341         ConceptLattice clArrowClosed = arrowCtx.conceptLattice(true); // This lattice is fun :-)
342         Vector<TreeSet<Comparable>> coAtoms = clArrowClosed.immediateSuccessors(clArrowClosed.bottom(), arrowCtx);
343         // Check if the complement of coAtoms is "empty".
344         // Only these coAtoms are kept
345         ArrayList<Context> goodCoAtoms = new ArrayList<Context>();
346         // Be careful that the concept has been reversed
347         for (int i = 0; i < coAtoms.size(); i++) {
348             TreeSet<Comparable> attrComp = (TreeSet<Comparable>) this.getAttributes().clone(); // Initial context
349             TreeSet<Comparable> attr = arrowCtx.getExtent(coAtoms.get(i));
350             attrComp.removeAll(attr); // As arrowCtx is reversed, Extent means Intent.
351             TreeSet<Comparable> obsComp = (TreeSet<Comparable>) this.getObservations().clone(); // Initial context
352             TreeSet<Comparable> obs = this.arrowClosureObject(coAtoms.get(i)).getObservations();
353             obsComp.removeAll(obs);
354             boolean cross = false; // If there is a cross, it is not empty.
355             for (Comparable o : obsComp) {
356                 for (Comparable a : attrComp) {
357                     cross = cross || this.getIntent(o).contains(a);
358                 }
359             }
360             if (!cross) {
361                 Context subContext = this.getSubContext(obs, attr);
362                 goodCoAtoms.add(subContext);
363             }
364         }
365         return goodCoAtoms;
366     }
367 
368     /**
369      * Returns a convex set of the concept lattice of c which can be doubled to
370      * recover the concept lattice of this component.
371      *
372      * This method must be used with contexts returned by the
373      * getDivisionContext. In other cases, it is meaningless.
374      *
375      * @param ctx context from which the convex set is computed.
376      *
377      * @return a convex set of the concept lattice of c which can be doubled to
378      *         recover the concept lattice of this component.
379      */
380     public TreeSet<Node> getDivisionConvex(Context ctx) {
381         ConceptLattice factor = ctx.conceptLattice(true);
382         TreeSet<Node> convex = new TreeSet<Node>();
383         // TODO Use parameterized Node
384         for (Node node : (SortedSet<Node>) factor.getNodes()) {
385             Concept c = (Concept) node;
386             if (!c.getSetB().containsAll(this.getExtent(c.getSetA()))
387                     && !c.getSetA().containsAll(this.getIntent(c.getSetB()))) {
388                 convex.add(node);
389             }
390         }
391         return convex;
392     }
393 
394     /*
395      * --------------- HANDLING METHODS FOR ATTRIBUTES AND OBSERVATIONS ------------
396      */
397 
398     /**
399      * Returns the set of attributes of this component.
400      *
401      * @return the set of attributes of this component
402      */
403     public TreeSet<Comparable> getAttributes() {
404         return this.attributes;
405     }
406 
407     /**
408      * Checks if the specified attribute belong to this component.
409      *
410      * @param att an attribute
411      *
412      * @return true if the attribute belongs to this component
413      */
414     public boolean containsAttribute(Comparable att) {
415         return this.attributes.contains(att);
416     }
417 
418     /**
419      * Checks if the specified set of attributes belongs to this component.
420      *
421      * @param set set of attributes
422      *
423      * @return true if all attributes belong to this component
424      */
425     public boolean containsAllAttributes(TreeSet<Comparable> set) {
426         return this.attributes.containsAll(set);
427     }
428 
429     /**
430      * Adds the specified element to the set of attributes of this component.
431      *
432      * @param att an attribute
433      *
434      * @return true if the attribute was successfully added
435      */
436     public boolean addToAttributes(Comparable att) {
437         if (!this.containsAttribute(att)) {
438             this.extent.put(att, new TreeSet<Comparable>());
439         }
440         boolean ok = this.attributes.add(att);
441         this.setBitSets();
442         return ok;
443     }
444 
445     /**
446      * Adds the set of specified element to the set of attributes of this
447      * component.
448      *
449      * @param set set of attributes
450      *
451      * @return true if all attributes were successfully added
452      */
453     public boolean addAllToAttributes(TreeSet<Comparable> set) {
454         boolean all = true;
455         for (Comparable att : set) {
456             if (!this.addToAttributes(att)) {
457                 all = false;
458             }
459         }
460         this.setBitSets();
461         return all;
462     }
463 
464     /**
465      * Removes the specified element from the set of attributes of this
466      * component
467      * and from all the intents it belongs to.
468      *
469      * @param att an attribute
470      *
471      * @return true if the attribute was successfully removed
472      */
473     public boolean removeFromAttributes(Comparable att) {
474         this.extent.remove(att);
475         for (Comparable o : this.getObservations()) {
476             this.intent.get(o).remove(att);
477         }
478         boolean ok = this.attributes.remove(att);
479         this.setBitSets();
480         return ok;
481     }
482 
483     /**
484      * Returns the set of observations of this component.
485      *
486      * @return the set of observations
487      */
488     public TreeSet<Comparable> getObservations() {
489         return this.observations;
490     }
491 
492     /**
493      * Checks if the specified observation belongs to this component.
494      *
495      * @param obs an observation
496      *
497      * @return true if the observation belongs to this component
498      */
499     public boolean containsObservation(Comparable obs) {
500         return this.observations.contains(obs);
501     }
502 
503     /**
504      * Checks if the specified set of observations belong to this component.
505      *
506      * @param set set of observations
507      *
508      * @return true if all the observations are in this component
509      */
510     public boolean containsAllObservations(TreeSet<Comparable> set) {
511         return this.observations.containsAll(set);
512     }
513 
514     /**
515      * Adds the specified element to the set of observations of this component.
516      *
517      * @param obs an observation
518      *
519      * @return true if the observation was successfully added
520      */
521     public boolean addToObservations(Comparable obs) {
522         if (!this.containsObservation(obs)) {
523             this.intent.put(obs, new TreeSet<Comparable>());
524         }
525         boolean ok = this.observations.add(obs);
526         this.setBitSets();
527         return ok;
528     }
529 
530     /**
531      * Adds the set of specified element to the set of observations of this
532      * component.
533      *
534      * @param set set of observations
535      *
536      * @return true if all observations were successfully added
537      */
538     public boolean addAllToObservations(TreeSet<Comparable> set) {
539         boolean all = true;
540         for (Comparable obs : set) {
541             if (!this.addToObservations(obs)) {
542                 all = false;
543             }
544         }
545         this.setBitSets();
546         return all;
547     }
548 
549     /**
550      * Removes the specified element from the set of observations of this
551      * component.
552      * and from all the extents it belongs to
553      *
554      * @param obs an observation
555      *
556      * @return true if the observation was removed
557      */
558     public boolean removeFromObservations(Comparable obs) {
559         this.intent.remove(obs);
560         for (Comparable att : this.getAttributes()) {
561             this.extent.get(att).remove(obs);
562         }
563         boolean ok = this.observations.remove(obs);
564         this.setBitSets();
565         return ok;
566     }
567 
568     /**
569      * Set the needed structures for the bitset optimization.
570      * WARNING: this must be called each time your dataset change
571      */
572     public void setBitSets() {
573         this.setMaps();
574         this.setBitSetsIntentExtent();
575     }
576 
577     /**
578      * Set the mapping structure for the bitset optimization.
579      */
580     private void setMaps() {
581         this.arrayAttributes = new ArrayList();
582         this.arrayObservations = new ArrayList();
583         Iterator<Comparable> i = this.attributes.iterator();
584         while (i.hasNext()) {
585             this.arrayAttributes.add(i.next());
586         }
587         i = this.observations.iterator();
588         while (i.hasNext()) {
589             this.arrayObservations.add(i.next());
590         }
591     }
592 
593     /**
594      * Set the extent and intent structures for the bitset optimization.
595      */
596     private void setBitSetsIntentExtent() {
597         this.bitsetIntent = new TreeMap();
598         this.bitsetExtent = new TreeMap();
599         Iterator<Comparable> i = this.attributes.iterator();
600         BitSet b = new BitSet(this.observations.size());
601         while (i.hasNext()) {
602             Comparable att = i.next();
603             for (Comparable c : this.extent.get(att)) {
604                 b.set(this.arrayObservations.indexOf(c));
605             }
606             this.bitsetExtent.put(att, (BitSet) b.clone());
607             b.clear();
608         }
609         i = this.observations.iterator();
610         b = new BitSet(this.attributes.size());
611         while (i.hasNext()) {
612             Comparable obs = i.next();
613             for (Comparable c : this.intent.get(obs)) {
614                 b.set(this.arrayAttributes.indexOf(c));
615             }
616             this.bitsetIntent.put(obs, (BitSet) b.clone());
617             b.clear();
618         }
619     }
620 
621     /*
622      * --------------- HANDLING METHODS FOR INTENT AND EXTENT ------------
623      */
624     /**
625      * Returns the set of attributes that are intent of the specified
626      * observation.
627      *
628      * @param obs an observation
629      *
630      * @return the set of attributes
631      */
632     public TreeSet<Comparable> getIntent(Comparable obs) {
633         if (this.containsObservation(obs)) {
634             return this.intent.get(obs);
635         } else {
636             return new TreeSet();
637         }
638     }
639 
640     /**
641      * Returns the set of attributes that are all intent of observations of the
642      * specified set.
643      *
644      * @param set set of observations
645      *
646      * @return the set of observations
647      */
648     public TreeSet<Comparable> getIntent(TreeSet<Comparable> set) {
649         TreeSet<Comparable> resIntent = new TreeSet(this.getAttributes());
650         for (Comparable obs : set) {
651             resIntent.retainAll(this.getIntent(obs));
652         }
653         return resIntent;
654     }
655 
656     /**
657      * Return the number of attributes that are all intent of observations of
658      * the specified set.
659      *
660      * @param set set of observations
661      *
662      * @return the number of attributes
663      */
664     public int getIntentNb(TreeSet<Comparable> set) {
665         int size = this.getAttributes().size();
666         BitSet obsIntent = new BitSet(size);
667         obsIntent.set(0, size);
668         for (Comparable obs : set) {
669             try {
670                 obsIntent.and(this.bitsetIntent.get(obs));
671             } catch (NullPointerException e) {
672                 return 0;
673             }
674         }
675         return obsIntent.cardinality();
676     }
677 
678     /**
679      * Checks if the second specified element is an intent of the first
680      * specified element.
681      *
682      * @param obs an observation
683      * @param att an attribute
684      *
685      * @return true if the attribute is an intent of the observation
686      */
687     public boolean containAsIntent(Comparable obs, Comparable att) {
688         if (this.containsObservation(obs) && this.containsAttribute(att)) {
689             return this.intent.get(obs).contains(att);
690         } else {
691             return false;
692         }
693     }
694 
695     /**
696      * Returns the set of observations that are intent of the specified
697      * attribute.
698      *
699      * @param att an attribute
700      *
701      * @return the set of observations
702      */
703     public TreeSet<Comparable> getExtent(Comparable att) {
704         if (this.containsAttribute(att)) {
705             return this.extent.get(att);
706         } else {
707             return new TreeSet();
708         }
709     }
710 
711     /**
712      * Returns the set of observations that are all intent of attributes of the
713      * specified set.
714      *
715      * @param set set of attributes
716      *
717      * @return the set of observations
718      */
719     public TreeSet<Comparable> getExtent(TreeSet<Comparable> set) {
720         TreeSet<Comparable> attExtent = new TreeSet(this.getObservations());
721         for (Comparable att : set) {
722             attExtent.retainAll(this.getExtent(att));
723         }
724         return attExtent;
725     }
726 
727     /**
728      * Return the number of observations that are all intent of attributes of
729      * the specified set.
730      *
731      * @param set set of attributes
732      *
733      * @return the number of observations
734      */
735     public int getExtentNb(TreeSet<Comparable> set) {
736         int size = this.getObservations().size();
737         BitSet attExtent = new BitSet(size);
738         attExtent.set(0, size);
739         for (Comparable att : set) {
740             try {
741                 attExtent.and(this.bitsetExtent.get(att));
742             } catch (NullPointerException e) {
743                 return 0;
744             }
745         }
746         return attExtent.cardinality();
747     }
748 
749     /**
750      * Checks if the second specified element is an extent of the first
751      * specified element.
752      *
753      * @param att an attribute
754      * @param obs an observation
755      *
756      * @return true if the proposition is true
757      */
758     public boolean containAsExtent(Comparable att, Comparable obs) {
759         if (this.containsObservation(obs) && this.containsAttribute(att)) {
760             return this.extent.get(att).contains(obs);
761         } else {
762             return false;
763         }
764     }
765 
766     /**
767      * Adds the second specified element as intent of the first one,
768      * and the first one as extent of the second one.
769      * The first one has to belong to the observations set
770      * and the second one to the attribute set.
771      *
772      * @param obs an observation
773      * @param att an attribute
774      *
775      * @return true if both were added
776      */
777     public boolean addExtentIntent(Comparable obs, Comparable att) {
778         if (this.containsObservation(obs) && this.containsAttribute(att)) {
779             boolean ok = this.intent.get(obs).add(att) && this.extent.get(att).add(obs);
780             this.setBitSets();
781             return ok;
782         } else {
783             return false;
784         }
785     }
786 
787     /**
788      * Removes the second specified element from the intent of the first one,
789      * and the first one from the extent of the second one.
790      * The first one has to belong to the observations set
791      * and the second one to the attribute set.
792      *
793      * @param obs an observation
794      * @param att an attribute
795      *
796      * @return true if both were removed
797      */
798     public boolean removeExtentIntent(Comparable obs, Comparable att) {
799         if (this.containsObservation(obs) && this.containsAttribute(att)) {
800             boolean ok = this.intent.get(obs).remove(att) && this.extent.get(att).remove(obs);
801             this.setBitSets();
802             return ok;
803         } else {
804             return false;
805         }
806     }
807 
808     /*
809      * --------------- CONTEXT HANDLING METHODS ------------
810      */
811     /**
812      * Returns a String representation of this component.
813      * The following format is respected:
814      *
815      * The list of observations separated by a space on the first line ;
816      * the list of attrbutes separated by a space on the second line ;
817      * then, for each observations o, the list of its intent on a line, written
818      * like o a1 a2 ...
819      *
820      * ~~~
821      * Observations: 1 2 3
822      * Attributes: a b c d e
823      * 1: a c
824      * 2: a b
825      * 3: b d e
826      * 4: c e
827      * ~~~
828      *
829      * @return the string representation of this component
830      *
831      * @todo Enforce test
832      */
833     @Override
834     public String toString() {
835         String string;
836         StringBuilder builder = new StringBuilder();
837         builder.append("Observations: ");
838         for (Comparable o : this.observations) {
839             // first line : All observations separated by a space
840             // a StringTokenizer is used to delete spaces in the
841             // string description of each observation
842             string = o.toString();
843             if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
844                 string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
845             }
846             builder.append(string).append(" ");
847         }
848 
849         String newLine = System.getProperty("line.separator");
850         builder.append(newLine).append("Attributes: ");
851         for (Comparable a : this.attributes) {
852             // second line : All attributes separated by a space
853             // a StringTokenizer is used to delete spaces in the
854             // string description of each observation
855             string = a.toString();
856             if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
857                 string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
858             }
859             builder.append(string).append(" ");
860         }
861 
862         // next lines : All intents of observations, one on each line:
863         // observation : list of attributes
864         // a StringTokenizer is used to delete spaces in the
865         // string description of each observation and attributes
866         builder.append(newLine);
867         for (Comparable o : this.observations) {
868             string = o.toString();
869             if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
870                 string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
871             }
872             builder.append(string).append(": ");
873             for (Comparable a : this.getIntent(o)) {
874                 string = a.toString();
875                 if (string.contains(" ") || string.contains("\"") || string.contains("\n") || string.contains("\t")) {
876                     string = "\"" + string.replace("\"", "\\\"").replace("\n", "\\n").replace("\t", "\\t") + "\"";
877                 }
878                 builder.append(string).append(" ");
879             }
880             builder.append(newLine);
881         }
882         return builder.toString();
883     }
884 
885     /**
886      * Save the description of this component in a file whose name is specified.
887      *
888      * @param filename the name of the file
889      *
890      * @throws IOException When an IOException occurs
891      */
892     public void save(final String filename) throws IOException {
893         Filer.getInstance().save(this, ContextIOFactory.getInstance(), filename);
894     }
895 
896     /**
897      * Parse the description of this component from a file whose name is
898      * specified.
899      *
900      * @param filename the name of the file
901      *
902      * @return this for chaining
903      *
904      * @throws IOException When an IOException occurs
905      */
906     public Context parse(final String filename) throws IOException {
907         this.init();
908         Filer.getInstance().parse(this, ContextIOFactory.getInstance(), filename);
909         return this;
910     }
911 
912     /**
913      * Removes from this component reducible attributes.
914      *
915      * Reducible attributes are attributes equivalent by closure to others
916      * attributes.
917      * They are computed by `getReducibleElements` od `ClosureSystem` in
918      * O(|A|^3|O|)
919      *
920      * @return the set of reducibles removed attributes, with their equivalent
921      *         attributes
922      */
923     public TreeMap<Comparable, TreeSet<Comparable>> attributesReduction() {
924         // compute the reducible elements
925         TreeMap red = this.getReducibleElements();
926         // remove the reducible elements from the attributes set
927         for (Object att : red.keySet()) {
928             this.removeFromAttributes((Comparable) att);
929         }
930         return red;
931     }
932 
933     /**
934      * Removes from this component reducible observations.
935      *
936      * Reducible observations are attributes equivalent by closure to others
937      * observations.
938      * They are computed by `getReducibleElements` od `ClosureSystem`
939      * applied on the reverse context in O(|O|^3|A|)
940      *
941      * @return the set of reducibles removed attributes, with their equivalent
942      *         attributes
943      */
944     public TreeMap<Comparable, TreeSet<Comparable>> observationsReduction() {
945         // compute the reducible elements of the reverse context
946         this.reverse();
947         TreeMap red = this.getReducibleElements();
948         this.reverse();
949         // remove the reducible elements from the observations set
950         for (Object att : red.keySet()) {
951             this.removeFromObservations((Comparable) att);
952         }
953         return red;
954     }
955 
956     /**
957      * Removes from this component reducible attributes and observations.
958      *
959      * They are computed by `attributesReduction` then
960      * `observationsReduction` in O(|A|^3|O|+|O|^3|A|)
961      *
962      * @return the set of reducibles removed attributes and observations with
963      *         their equivalent elements
964      */
965     public TreeMap<Comparable, TreeSet<Comparable>> reduction() {
966         TreeMap<Comparable, TreeSet<Comparable>> red = this.attributesReduction();
967         red.putAll(this.observationsReduction());
968         return red;
969     }
970 
971     /**
972      * Reverses this component by replacing attributes by observations and
973      * observations by
974      * attributes. Intent and extent are exchanged in the same way.
975      */
976     public void reverse() {
977         TreeSet<Comparable> tmp = this.attributes;
978         this.attributes = this.observations;
979         this.observations = tmp;
980         TreeMap<Comparable, TreeSet<Comparable>> sauv = this.intent;
981         this.intent = this.extent;
982         this.extent = sauv;
983     }
984 
985     /**
986      * Return a new reversed Context.
987      *
988      * @return a new reversed Context
989      */
990     public Context getReverseContext() {
991         Context context = new Context(this);
992         context.reverse();
993         context.setBitSets();
994         return context;
995     }
996 
997     /**
998      * Returns the arrow-closed subcontext of this component containing obs.
999      *
1000      * A sub-context (H,N) of (G,M) is arrow-closed if :
1001      * 1. For all h in H, h uparrow m implies m in N and
1002      * 2. For all n in N, g downarrow n implies g in H
1003      *
1004      * @param obs set of observations to keep
1005      *
1006      * @return the arrow-closed subcontext of this component containing obs.
1007      */
1008     public Context arrowClosureObject(TreeSet<Comparable> obs) {
1009         ConceptLattice cl = this.getReverseContext().conceptLattice(true); // Where is bug with it ^^
1010         ArrowRelation ar = cl.getArrowRelation();
1011         /*
1012         WARNING : this component contains "observations" and "attributes"
1013         whereas following contexts, down and up, are made of concept.
1014          */
1015         Context down = ar.getDoubleDownArrowTable();
1016         Context up = ar.getDoubleUpArrowTable();
1017         Context ctx = new Context();
1018         ctx.addAllToObservations(obs);
1019         int sizeObs = ctx.getObservations().size();
1020         int sizeAttr = ctx.getAttributes().size();
1021         int prevObs = 0;
1022         int prevAttr = 0;
1023         while ((prevObs < sizeObs) || (prevAttr < sizeAttr)) {
1024             for (Comparable o : ctx.getObservations()) {
1025                 // Concept corresponding to observation o
1026                 TreeSet<Comparable> setBo = this.getIntent(o);
1027                 TreeSet<Comparable> setAo = this.getExtent(setBo);
1028                 Concept cptO = new Concept(setAo, setBo);
1029                 TreeSet<Comparable> attrUp = up.getIntent(cl.getNode(cptO)); // Doesn't work with up.getIntent(cptO) ...
1030                 for (Comparable a : this.getAttributes()) { // NOT GOOD for complexity :-(
1031                     // Try to find attributes in up-arrow relation
1032                     TreeSet<Comparable> setAa = this.getExtent(a);
1033                     TreeSet<Comparable> setBa = this.getIntent(setAa);
1034                     Concept cptA = new Concept(setAa, setBa); // Concept corresponding to attribute a
1035                     if (attrUp.contains(cl.getNode(cptA))) {
1036                         ctx.addToAttributes(a);
1037                     }
1038                 }
1039             }
1040             for (Comparable a : ctx.getAttributes()) {
1041                 // Concept corresponding to observation a
1042                 TreeSet<Comparable> setAa = this.getExtent(a);
1043                 TreeSet<Comparable> setBa = this.getIntent(setAa);
1044                 Concept cptA = new Concept(setAa, setBa);
1045                 TreeSet<Comparable> obsDown = down.getExtent(cl.getNode(cptA));
1046                 for (Comparable o : this.getObservations()) {
1047                     // Try to find attributes in down-arrow relation
1048                     TreeSet<Comparable> setBo = this.getIntent(o);
1049                     TreeSet<Comparable> setAo = this.getExtent(setBo);
1050                     Concept cptO = new Concept(setAo, setBo); // Concept corresponding to attribute o
1051                     if (obsDown.contains(cl.getNode(cptO))) {
1052                         ctx.addToObservations(o);
1053                     }
1054                 }
1055             }
1056             prevObs = sizeObs;
1057             prevAttr = sizeAttr;
1058             sizeObs = ctx.getObservations().size();
1059             sizeAttr = ctx.getAttributes().size();
1060         }
1061         return this.getSubContext(ctx.getObservations(), ctx.getAttributes());
1062     }
1063 
1064     /**
1065      * Returns the arrow-closed subcontext of this component containing attr.
1066      *
1067      * A sub-context (H,N) of (G,M) is arrow-closed if :
1068      * 1. For all h in H, h uparrow m implies m in N and
1069      * 2. For all n in N, g downarrow n implies g in H
1070      *
1071      * @param attr set of attributes to keep
1072      *
1073      * @return the arrow-closed subcontext of this component containing attr.
1074      */
1075     public Context arrowClosureAttribute(TreeSet<Comparable> attr) {
1076         ConceptLattice cl = this.getReverseContext().conceptLattice(true); // Where is bug with it ^^
1077         ArrowRelation ar = cl.getArrowRelation();
1078         Context down = ar.getDoubleDownArrowTable();
1079         Context up = ar.getDoubleUpArrowTable();
1080         Context ctx = new Context();
1081         ctx.addAllToAttributes(attr);
1082         int sizeObs = ctx.getObservations().size();
1083         int sizeAttr = ctx.getAttributes().size();
1084         int prevObs = 0;
1085         int prevAttr = 0;
1086         while ((prevObs < sizeObs) || (prevAttr < sizeAttr)) {
1087             for (Comparable a : ctx.getAttributes()) {
1088                 // Concept corresponding to observation a
1089                 TreeSet<Comparable> setAa = this.getExtent(a);
1090                 TreeSet<Comparable> setBa = this.getIntent(setAa);
1091                 Concept cptA = new Concept(setAa, setBa);
1092                 TreeSet<Comparable> obsDown = down.getExtent(cl.getNode(cptA));
1093                 for (Comparable o : this.getObservations()) {
1094                     // Try to find attributes in down-arrow relation
1095                     TreeSet<Comparable> setBo = this.getIntent(o);
1096                     TreeSet<Comparable> setAo = this.getExtent(setBo);
1097                     Concept cptO = new Concept(setAo, setBo); // Concept corresponding to attribute o
1098                     if (obsDown.contains(cl.getNode(cptO))) {
1099                         ctx.addToObservations(o);
1100                     }
1101                 }
1102             }
1103             for (Comparable o : ctx.getObservations()) {
1104                 // Concept corresponding to observation o
1105                 TreeSet<Comparable> setBo = this.getIntent(o);
1106                 TreeSet<Comparable> setAo = this.getExtent(setBo);
1107                 Concept cptO = new Concept(setAo, setBo);
1108                 TreeSet<Comparable> attrUp = up.getIntent(cl.getNode(cptO)); // Doesn't work with up.getIntent(cptO) ...
1109                 for (Comparable a : this.getAttributes()) { // NOT GOOD for complexity :-(
1110                     // Try to find attributes in up-arrow relation
1111                     TreeSet<Comparable> setAa = this.getExtent(a);
1112                     TreeSet<Comparable> setBa = this.getIntent(setAa);
1113                     Concept cptA = new Concept(setAa, setBa); // Concept corresponding to attribute a
1114                     if (attrUp.contains(cl.getNode(cptA))) {
1115                         ctx.addToAttributes(a);
1116                     }
1117                 }
1118             }
1119             prevObs = sizeObs;
1120             prevAttr = sizeAttr;
1121             sizeObs = ctx.getObservations().size();
1122             sizeAttr = ctx.getAttributes().size();
1123         }
1124         return this.getSubContext(ctx.getObservations(), ctx.getAttributes());
1125     }
1126 
1127     /*
1128      * --------------- IMPLEMENTATION OF CLOSURE SYSTEM ABSTRACT METHODS ------------
1129      */
1130  /*
1131      * --------------- AND CONCEPT LATTICE GENERATION------------
1132      */
1133 
1134     /**
1135      * Returns the set of attributes as elements set used by the lattice
1136      * generator abstract class
1137      * to generate closed set lattice on attributes. The closed set lattice on
1138      * abservations can
1139      * be otained using the reverse method of this class.
1140      *
1141      * @return the set of attributes
1142      */
1143     @Override
1144     public TreeSet<Comparable> getSet() {
1145         return this.attributes;
1146     }
1147 
1148     /**
1149      * Builds the closure of a set X of attributes.
1150      *
1151      * The closure corresponds to the maximal set of attributes having the
1152      * same intent as the specified one.
1153      *
1154      * This treatment is performed in O(|A||O|)
1155      *
1156      * @param set a TreeSet of indexed elements
1157      *
1158      * @return the closure of the set for this component
1159      */
1160     @Override
1161     public TreeSet<Comparable> closure(TreeSet<Comparable> set) {
1162         return this.getIntent(this.getExtent(set));
1163     }
1164 
1165     /**
1166      * Returns the set of union of observations that are intent with one of
1167      * attributes of the specified set.
1168      *
1169      * @param set a specified set
1170      *
1171      * @return the set of union of observations
1172      */
1173     public TreeSet<Comparable> getExtentUnion(TreeSet<Comparable> set) {
1174         TreeSet<Comparable> ext = new TreeSet();
1175         for (Comparable att : set) {
1176             for (Comparable obs : this.getExtent(att)) {
1177                 if (this.containAsExtent(att, obs) && !ext.contains(obs)) {
1178                     ext.add(obs);
1179                 }
1180             }
1181         }
1182         return ext;
1183     }
1184 
1185     /**
1186      * Builds the inverse of the closure operator of a set of observations.
1187      *
1188      * The inverse closure corresponds to the maximal set of observations having
1189      * the
1190      * same intent as the specified one.
1191      * This treatment is performed in O(|A||O|)
1192      *
1193      * @param set a TreeSet of indexed elements
1194      *
1195      * @return the closure of the set for this component
1196      */
1197     public ComparableSet inverseClosure(ComparableSet set) {
1198         return new ComparableSet(this.getExtent(this.getIntent((TreeSet) set)));
1199     }
1200 
1201     /**
1202      * Returns the concept lattice of this component.
1203      *
1204      * A true value of the boolean `diagram` indicates that the
1205      * Hasse diagramm of the lattice is computed (i.e. it is transitively
1206      * reduced),
1207      * whereas a false value indicates that the lattice is transitively closed
1208      *
1209      * The closed set lattice is first generated using
1210      * `ConceptLattice closedSetLattice (boolean diagram)`
1211      * Then, nodes of the lattice are completed as concepts.
1212      *
1213      * @param diagram a boolean indicating if the Hasse diagramm of the lattice
1214      *                is computed or not.
1215      *
1216      * @return The concept lattice induced by this component
1217      */
1218     public ConceptLattice conceptLattice(boolean diagram) {
1219         ConceptLattice csl = this.closedSetLattice(diagram);
1220         // TreeMap<Concept, Concept> nodes = new TreeMap<Concept, Concept>();
1221         for (Object node : csl.getNodes()) {
1222             Concept cl = (Concept) node;
1223             cl.putSetB(new ComparableSet(this.getExtent(cl.getSetA())));
1224         }
1225         return csl;
1226     }
1227 
1228     /**
1229      * Reccursively generates nodes of the product lattice.
1230      *
1231      * @param c       couple to be completed
1232      * @param clParts list of last context to deal with
1233      *
1234      * @return a list of nodes to add to the product.
1235      */
1236     private ArrayList<Couple> recursiveGenProd(Couple c, LinkedList<ConceptLattice> clParts) {
1237         LinkedList<ConceptLattice> copy = (LinkedList<ConceptLattice>) clParts.clone();
1238         if (copy.isEmpty()) {
1239             ArrayList<Couple> result = new ArrayList<Couple>();
1240             result.add(c);
1241             return result;
1242         } else {
1243             ConceptLattice cl = (ConceptLattice) copy.poll();
1244             ArrayList<Couple> nodes = new ArrayList<Couple>();
1245             for (Object node : cl.getNodes()) {
1246                 ArrayList<Concept> listCopy = new ArrayList<Concept>();
1247                 for (Concept cpt : (ArrayList<Concept>) c.getLeft()) {
1248                     listCopy.add(cpt);
1249                 }
1250                 Couple coupleCopy = new Couple(listCopy, c.getRight());
1251                 ((ArrayList<Concept>) coupleCopy.getLeft()).add((Concept) node);
1252                 nodes.addAll(recursiveGenProd(coupleCopy, copy));
1253             }
1254             return nodes;
1255         }
1256     }
1257 
1258     /**
1259      * Returns the concept lattice of this component represented as a subdirect
1260      * product of its irreductibles components.
1261      *
1262      * WARNING : Context MUST BE REDUCED !
1263      *
1264      * @return concept Lattice of this component represented as a subdirect
1265      *         product of its irreductibles components.
1266      */
1267     public Lattice subDirectDecomposition() {
1268         // First, compute 1-generated arrow-closed subcontextes
1269         ArrayList<Context> parts = new ArrayList<Context>();
1270         for (Comparable o : this.getObservations()) {
1271             TreeSet<Comparable> setO = new TreeSet<Comparable>();
1272             setO.add(o);
1273             parts.add(this.arrowClosureObject(setO));
1274         }
1275         // Second, remove contexts contained in other. They are dispendable.
1276         // Remove first all contexts that appeared at least twice.
1277         ArrayList<Context> single = new ArrayList<Context>();
1278         for (int i = 0; i < parts.size(); i++) {
1279             boolean containedNext = false;
1280             for (int j = i + 1; j < parts.size(); j++) {
1281                 containedNext = containedNext || (parts.get(i).containsAllObservations(parts.get(j).getObservations())
1282                         && parts.get(j).containsAllObservations(parts.get(i).getObservations())
1283                         && parts.get(i).containsAllAttributes(parts.get(j).getAttributes())
1284                         && parts.get(j).containsAllAttributes(parts.get(i).getAttributes()));
1285             }
1286             if (!containedNext) {
1287                 single.add(parts.get(i));
1288             }
1289         }
1290         parts = single;
1291         ArrayList<Context> toBeRemoved = new ArrayList<Context>();
1292         for (Context remove : parts) {
1293             for (Context test : parts) {
1294                 if ((parts.indexOf(test) != parts.indexOf(remove))
1295                         && (test.containsAllObservations(remove.getObservations()))
1296                         && (test.containsAllAttributes(remove.getAttributes()))) {
1297                     toBeRemoved.add(remove);
1298                 }
1299             }
1300         }
1301         parts.removeAll(toBeRemoved);
1302         // Third, compute the product but can't use LatticeFactory.product :-(
1303         /*
1304          * Content of each node is of the following form :
1305          * 1. They are Couple
1306          * 2. Left part is an ArrayList corresponding to the terms of the product
1307          * 3. Right part is a boolean, true if the node is inside the sub-product.
1308          * Thus we have : the full product, and nodes of the subproduct marked
1309          */
1310         // First compute all nodes of the product
1311         LinkedList<ConceptLattice> clParts = new LinkedList<ConceptLattice>();
1312         for (Context ctx : parts) {
1313             clParts.add(ctx.conceptLattice(true));
1314         }
1315         Lattice prod = new Lattice();
1316         // Computes nodes
1317         ArrayList<Couple> nodes = new ArrayList<Couple>();
1318         LinkedList<ConceptLattice> copy = (LinkedList<ConceptLattice>) clParts.clone();
1319         ConceptLattice firstCL = (ConceptLattice) copy.poll();
1320         for (Object node : firstCL.getNodes()) {
1321             Couple couple = new Couple(new ArrayList<Concept>(), false);
1322             ArrayList<Concept> prodCPT = new ArrayList<Concept>();
1323             prodCPT.add((Concept) node);
1324             couple.setLeft(prodCPT);
1325             nodes.addAll(recursiveGenProd(couple, copy));
1326         }
1327         for (Couple c : nodes) {
1328             prod.addNode(new Node(c));
1329         }
1330         // Add edges
1331         for (Object source : prod.getNodes()) {
1332             for (Object target : prod.getNodes()) {
1333                 Couple contentSource = (Couple) ((Node) source).getContent();
1334                 Couple contentTarget = (Couple) ((Node) target).getContent();
1335                 boolean haveEdge = true;
1336                 boolean equals = true;
1337                 for (int i = 0; i < clParts.size(); i++) { // clParts.size() is the number of factor
1338                     Concept cptSource = ((ArrayList<Concept>) contentSource.getLeft()).get(i);
1339                     Concept cptTarget = ((ArrayList<Concept>) contentTarget.getLeft()).get(i);
1340                     equals = equals && cptSource.equals(cptTarget);
1341                     haveEdge = haveEdge && (clParts.get(i).containsEdge(cptSource, cptTarget) || cptSource.equals(cptTarget));
1342                 }
1343                 if (haveEdge && !equals) {
1344                     prod.addEdge(((Node) source), ((Node) target));
1345                 }
1346             }
1347         }
1348         prod.transitiveReduction();
1349         // Last, identify the sub-product, e.g. nodes of this component in the product.
1350         // In the subdirect decomposition, if (A,B) is a concept then (A \cap H,B \cap N) also.
1351         // Transform nodes of the original lattice into nodes of the subproduct lattice and mark them
1352         ConceptLattice cl = this.conceptLattice(true);
1353         for (Object cpt : cl.getNodes()) {
1354             // Compute cpt representation in prod
1355             ArrayList<Concept> subCpt = new ArrayList<Concept>();
1356             for (int i = 0; i < parts.size(); i++) {
1357                 Context ctx = parts.get(i);
1358                 ConceptLattice term = clParts.get(i);
1359                 ComparableSet setA = new ComparableSet();
1360                 setA.addAll(((Concept) cpt).getSetA());
1361                 ComparableSet setB = new ComparableSet();
1362                 setB.addAll(((Concept) cpt).getSetB());
1363                 setA.retainAll(ctx.getAttributes());
1364                 setB.retainAll(ctx.getObservations());
1365                 subCpt.add(term.getConcept((ComparableSet) setA, (ComparableSet) setB));
1366             }
1367             // Check if cpt is in prod
1368             for (Object nodeProd : prod.getNodes()) {
1369                 if (((Couple) ((Node) nodeProd).getContent()).getLeft().equals(subCpt)) {
1370                     ((Couple) ((Node) nodeProd).getContent()).setRight(true);
1371                 }
1372             }
1373         }
1374         return prod;
1375     }
1376 
1377     /**
1378      * Returns the closed set iceberg of this component.
1379      *
1380      * The Hasse diagramm of the iceberg is computed (i.e. it is transitively
1381      * reduced)
1382      * until the support of the closed set is less than the support value.
1383      *
1384      * @param support a threshold, between 0 and 1, for a closed set to be part
1385      *                of the iceberg.
1386      *
1387      * @return The concept iceberg
1388      */
1389     public ConceptLattice closedSetIceberg(double support) {
1390         return ConceptLattice.diagramIceberg(this, support);
1391     }
1392 
1393     /**
1394      * Returns the lattice of this component.
1395      *
1396      * @return The lattice induced by this component
1397      */
1398     @Override
1399     public ConceptLattice lattice() {
1400         return this.conceptLattice(true);
1401     }
1402 }