1 package org.thegalactic.lattice;
2
3 /*
4 * ClosureSystem.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.SortedSet;
16 import java.util.TreeMap;
17 import java.util.TreeSet;
18 import java.util.Vector;
19
20 import org.thegalactic.dgraph.DAGraph;
21 import org.thegalactic.dgraph.ConcreteDGraph;
22 import org.thegalactic.dgraph.Node;
23 import org.thegalactic.util.ComparableSet;
24
25 /**
26 * This class is an abstract class defining the common behavior of closure
27 * systems, and specialy its closed set lattice generation.
28 *
29 * Both a context and an implicational system have properties of a closure
30 * system, and therefore extend this class.
31 *
32 * A closure system is formaly defined by a set of indexed elements and a
33 * closure operator (abstract methods {@link #getSet} and {@link #closure}).
34 *
35 * Abstract method {@link #save} also describe the common behavior of a closure
36 * system.
37 *
38 * However, this abstract class provides both abstract and non abstract methods.
39 *
40 * Although abstract methods depends on data, and so have to be implemented by
41 * each extended class, non abstract methods only used property of a closure
42 * system. It is the case for methods {@link #nextClosure} (that computes the
43 * next closure of the specified one according to the lectic order implemented
44 * the well-known Wille algorithm) invoked by method {@link #allClosures} and
45 * the main method {@link #closedSetLattice} (where lattice can be transitively
46 * closed or reduced).
47 *
48 *
49 * 
50 *
51 * @uml ClosureSystem.png
52 * !include resources/org/thegalactic/lattice/ClosureSystem.iuml
53 *
54 * hide members
55 * show ClosureSystem members
56 * class ClosureSystem #LightCyan
57 * title ClosureSystem UML graph
58 */
59 public abstract class ClosureSystem {
60
61 /*
62 * ------------- ABSTRACT METHODS ------------------
63 */
64 /**
65 * Returns the set of elements of the closure system.
66 *
67 * @return the set of elements of the closure system
68 */
69 public abstract SortedSet<Comparable> getSet();
70
71 /**
72 * Returns the closure of the specified set.
73 *
74 * @param set The specified set
75 *
76 * @return The closure
77 */
78 public abstract TreeSet<Comparable> closure(TreeSet<Comparable> set);
79
80 /**
81 * Saves this component in a file which name is specified.
82 *
83 * @param file name of file
84 *
85 * @throws IOException When an IOException occurs
86 */
87 public abstract void save(String file) throws IOException;
88
89 /*
90 * ------------- IMPLEMENTED METHODS ------------------
91 */
92 /**
93 * Returns the closed set lattice of this component.
94 *
95 * A true value of the boolean `diagram` indicates that the Hasse diagramm
96 * of the lattice is computed (i.e. it is transitively reduced), whereas a
97 * false value indicates that the lattice is transitively closed
98 *
99 * A transitively reduced lattice is generated by the static method
100 * `ConceptLattice diagramLattice (ClosureSystem init)` that implements an
101 * adaptation of Bordat's algorithm. This adaptation computes the dependance
102 * graph while the lattice is generated, with the same complexity.
103 *
104 * A transitively closed lattice is generated bye well-known Next Closure
105 * algorithm. In this case, the dependance graph of the lattice isn't
106 * computed.
107 *
108 * @param diagram a boolean indicating if the Hasse diagramm of the lattice
109 * is computed or not.
110 *
111 * @return The concept lattice
112 */
113 public ConceptLattice closedSetLattice(boolean diagram) {
114 if (diagram) {
115 return ConceptLattice.diagramLattice(this);
116 } else {
117 return ConceptLattice.completeLattice(this);
118 }
119 }
120
121 /**
122 * Returns the lattice of this component.
123 *
124 * @return The concept lattice
125 */
126 public ConceptLattice lattice() {
127 return this.closedSetLattice(true);
128 }
129
130 /**
131 * Returns all the closed sets of the specified closure system (that can be
132 * an IS or a context).
133 *
134 * Closed sets are generated in lecticaly order, with the emptyset's closure
135 * as first closed set, using the Ganter's Next Closure algorithm.
136 *
137 * Therefore, closed sets have to be comparable using `ComparableSet` class.
138 * This treatment is performed in O(cCl|S|^3) where S is the initial set of
139 * elements, c is the number of closed sets that could be exponential in the
140 * worst case, and Cl is the closure computation complexity.
141 *
142 * @return all the closeds set in the lectically order.
143 */
144 public Vector<Concept> allClosures() {
145 Vector<Concept> allclosure = new Vector<Concept>();
146 // first closure: closure of the empty set
147 allclosure.add(new Concept(this.closure(new ComparableSet()), false));
148 Concept cl = allclosure.firstElement();
149 // next closures in lectically order
150 boolean continu = true;
151 do {
152 cl = this.nextClosure(cl);
153 if (allclosure.contains(cl)) {
154 continu = false;
155 } else {
156 allclosure.add(cl);
157 }
158 } while (continu);
159
160 return allclosure;
161 }
162
163 /**
164 * Returns the lecticaly next closed set of the specified one.
165 *
166 * This treatment is an implementation of the best knowm algorithm of Wille
167 * whose complexity is in O(Cl|S|^2), where S is the initial set of
168 * elements, and Cl is the closure computation complexity.
169 *
170 * @param cl a concept
171 *
172 * @return the lecticaly next closed set
173 */
174 public Concept nextClosure(Concept cl) {
175 TreeSet<Comparable> set = new TreeSet(this.getSet());
176 boolean success = false;
177 TreeSet setA = new TreeSet(cl.getSetA());
178 Comparable ni = set.last();
179 do {
180 ni = (Comparable) set.last();
181 set.remove(ni);
182 if (!setA.contains(ni)) {
183 setA.add(ni);
184 TreeSet setB = this.closure(setA);
185 setB.removeAll(setA);
186 if (setB.isEmpty() || ((Comparable) setB.first()).compareTo(ni) >= 1) {
187 setA = this.closure(setA);
188 success = true;
189 } else {
190 setA.remove(ni);
191 }
192 } else {
193 setA.remove(ni);
194 }
195 } while (!success && ni.compareTo(this.getSet().first()) >= 1);
196 return new Concept(setA, false);
197 }
198
199 /**
200 * Returns the precedence graph of this component.
201 *
202 * Nodes of the graph are elements of this component. There is an edge from
203 * element a to element b when a belongs to the closure of b.
204 *
205 * The rule a -> a isn't added to the precedence graph
206 *
207 * When precedence graph is acyclic, then this component is a reduced one.
208 *
209 * @return the precedence graph
210 */
211 public ConcreteDGraph<Comparable, ?> precedenceGraph() {
212 // compute a TreeMap of closures for each element of the component
213 TreeMap<Comparable, TreeSet<Comparable>> closures = new TreeMap<Comparable, TreeSet<Comparable>>();
214 for (Comparable x : this.getSet()) {
215 ComparableSet setX = new ComparableSet();
216 setX.add(x);
217 closures.put(x, this.closure(setX));
218 }
219 // nodes of the graph are elements
220 ConcreteDGraph<Comparable, ?> prec = new ConcreteDGraph<Comparable, Object>();
221 TreeMap<Comparable, Node> nodeCreated = new TreeMap<Comparable, Node>();
222 for (Comparable x : this.getSet()) {
223 Node node = new Node(x);
224 prec.addNode(node);
225 nodeCreated.put(x, node);
226 }
227 // edges of the graph are closures containments
228 for (Comparable source : this.getSet()) {
229 for (Comparable target : this.getSet()) {
230 if (!source.equals(target)) {
231 // check if source belongs to the closure of target
232 if (closures.get(target).contains(source)) {
233 prec.addEdge(nodeCreated.get(source), nodeCreated.get(target));
234 }
235 }
236 }
237 }
238 return prec;
239 }
240
241 /**
242 * This function returns all reducible elements.
243 *
244 * A reducible elements is equivalent by closure to one or more other
245 * attributes. Reducible elements are computed using the precedence graph of
246 * the closure system. Complexity is in O()
247 *
248 * @return The map of reductible attributes with their equivalent attributes
249 */
250 public TreeMap<Object, TreeSet> getReducibleElements() {
251 // If you can't remove nodes, put them in the rubbish bin ...
252 TreeSet<Node> rubbishBin = new TreeSet<Node>();
253 // Initialise a map Red of reducible attributes
254 TreeMap<Object, TreeSet> red = new TreeMap();
255 // Initialise the precedence graph G of the closure system
256 ConcreteDGraph<Comparable, ?> graph = this.precedenceGraph();
257 // First, compute each group of equivalent attributes
258 // This group will be a strongly connected component on the graph.
259 // Then, only one element of each group is skipped, others will be deleted.
260 DAGraph<SortedSet<Node<Comparable>>, ?> cfc = graph.getStronglyConnectedComponent();
261 for (Node<SortedSet<Node<Comparable>>> node : cfc.getNodes()) {
262 // Get list of node of this component
263 SortedSet<Node<Comparable>> sCC = node.getContent();
264 if (sCC.size() > 1) {
265 Node<?> y = sCC.first();
266 TreeSet yClass = new TreeSet();
267 yClass.add(y.getContent());
268 for (Node x : sCC) {
269 if (!x.getContent().equals(y.getContent())) {
270 rubbishBin.add(x); // instead of : graph.removeNode(x);
271 red.put(x.getContent(), yClass);
272 }
273 }
274 }
275 }
276 // Next, check if an attribute is equivalent to emptyset
277 // i.e. its closure is equal to emptyset closure
278 TreeSet<Node> sinks = new TreeSet<Node>(graph.getSinks());
279 sinks.removeAll(rubbishBin);
280 if (sinks.size() == 1) {
281 Node s = sinks.first();
282 red.put(s.getContent(), new TreeSet());
283 rubbishBin.add(s); // instead of : graph.removeNode(s);
284 }
285 // Finaly, checking a remaining attribute equivalent to its predecessors or not may reduce more attributes.
286 // Check all remaining nodes of graph G
287 TreeSet<Node> remainingNodes = new TreeSet<Node>();
288 for (Node node : graph.getNodes()) {
289 remainingNodes.add(node);
290 }
291 remainingNodes.removeAll(rubbishBin);
292 for (Node x : remainingNodes) {
293 // TODO getPredecessorNodes must return an iterator
294 SortedSet<Node> predecessors = new TreeSet<Node>(graph.getPredecessorNodes(x));
295 predecessors.removeAll(rubbishBin);
296 if (predecessors.size() > 1) {
297 // Create the closure of x
298 TreeSet set = new TreeSet();
299 set.add(x.getContent());
300 TreeSet closureSet = this.closure(set);
301 // Create the closure of predecessors
302 TreeSet<Comparable> pred = new TreeSet<Comparable>();
303 for (Node node : predecessors) {
304 pred.add((Comparable) node.getContent());
305 }
306 TreeSet<Comparable> closureP = this.closure(pred);
307 // Check the equality of two closures
308 if (closureSet.containsAll(closureP) && closureP.containsAll(closureSet)) {
309 red.put(x.getContent(), pred);
310 }
311 }
312 }
313 // Finally, return the list of reducible elements with their equivalent attributes.
314 return red;
315 }
316 }