1 package org.thegalactic.lattice;
2
3 /*
4 * LatticeFactory.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.util.BitSet;
15 import java.util.Iterator;
16
17 import org.thegalactic.dgraph.DAGraph;
18 import org.thegalactic.dgraph.DAGraphFactory;
19 import org.thegalactic.dgraph.Node;
20 import org.thegalactic.util.Couple;
21
22 /**
23 * This class provides a few methods to constructs lattice examples.
24 *
25 * 
26 *
27 * @uml LatticeFactory.png
28 * !include resources/org/thegalactic/lattice/LatticeFactory.iuml
29 *
30 * class LatticeFactory #LightCyan
31 * title LatticeFactory UML graph
32 * @author jeff
33 */
34 public class LatticeFactory {
35
36 /**
37 * Returns a randomly generated lattice with nb nodes.
38 *
39 * @param nb Number of nodes in the randomly generated lattice
40 *
41 * @return a randomly generated lattice with nb nodes
42 */
43 public static Lattice<Integer, ?> random(int nb) {
44 boolean done = false;
45 Lattice l = new Lattice();
46 while (!done) {
47 DAGraph dag = DAGraphFactory.getInstance().random(nb - 2); // what an ugly strategy :-(
48 Lattice<Integer, ?> tmp = new Lattice(dag);
49 Node<Integer> top = new Node(nb - 1);
50 tmp.addNode(top);
51 for (Node<Integer> node : tmp.max()) {
52 if (!node.equals(top)) {
53 tmp.addEdge(node, top);
54 }
55 }
56 Node<Integer> bot = new Node(nb);
57 tmp.addNode(bot);
58 for (Node<Integer> node : tmp.min()) {
59 if (!node.equals(bot)) {
60 tmp.addEdge(bot, node);
61 }
62 }
63 if (tmp.isLattice()) {
64 done = true;
65 l = tmp;
66 }
67 }
68 return l;
69 }
70
71 /**
72 * Returns the boolean algebra of cardinal 2^n.
73 *
74 * @param n cardinal of the boolean algebra return by this method is 2^n
75 *
76 * @return the boolean algebra of cardinal 2^n
77 */
78 public static Lattice booleanAlgebra(int n) {
79 Lattice<BitSet, ?> l = new Lattice();
80 BitSet b = new BitSet(n);
81 Node<BitSet> bot = new Node(b);
82 l.addNode(bot);
83 for (int i = 0; i < n; i++) {
84 BitSet bs = new BitSet(n);
85 bs.set(i, true);
86 Node<BitSet> next = new Node(bs);
87 l.addNode(next);
88 l.addEdge(bot, next);
89 recursiveBooleanAlgebra(next, l, n);
90 }
91 return l;
92 }
93
94 /**
95 * Returns the lattice of permutations of 1..n.
96 *
97 * Permutation are ordered as follows : A permutation s2 is a succesor of a
98 * permutation s1, if s2 is obtained from s1 by inverting two consecutive
99 * elements i and j such that before inversion j > i.
100 *
101 * Example : 124356 has following successors 214356, 142356, 124536 and
102 * 124365.
103 *
104 * The bottom of this lattice is identity (for exemple 123456) and the top
105 * is for instance 654321.
106 *
107 * @param n the lattice of permutations of the set 1..n
108 *
109 * @return the lattice of permutations of 1..n.
110 */
111 public static Lattice permutationLattice(int n) {
112 Lattice<Permutation, ?> l = new Lattice();
113 int[] content = new int[n];
114 for (int i = 0; i < n; i++) {
115 content[i] = i;
116 }
117 Permutation s = new Permutation(n);
118 s.setContent(content);
119 Node<Permutation> bot = new Node(s);
120 l.addNode(bot);
121 for (int i = 0; i < n - 1; i++) {
122 int[] newC = content.clone();
123 newC[i] = content[i + 1];
124 newC[i + 1] = content[i];
125 Permutation newS = new Permutation(n);
126 newS.setContent(newC);
127 Node<Permutation> succ = new Node(newS);
128 l.addNode(succ);
129 l.addEdge(bot, succ);
130 recursivePermutationLattice(succ, l, n);
131 }
132 return l;
133 }
134
135 /**
136 * Returns the lattice cartesian product of l and r.
137 *
138 * A node in the product is a cartesian product of two nodes
139 *
140 * There is an edge (n1, m1) -> (n2, m2) if and only if there are edges n1
141 * -> n2 and m1 -> m2
142 *
143 * @param l Lattice of the left hand side of the product
144 * @param r Lattice of the right hand side of the product
145 *
146 * @return the lattice cartesian product of l and r
147 */
148 public static Lattice product(Lattice l, Lattice r) {
149 Lattice prod = new Lattice();
150 // Create nodes
151 for (Object nL : l.getNodes()) {
152 for (Object nR : r.getNodes()) {
153 prod.addNode(new Node(new Couple(((Node) nL).getContent(), ((Node) nR).getContent())));
154 }
155 }
156 // Create edges
157 for (Object source : prod.getNodes()) {
158 for (Object target : prod.getNodes()) {
159 if (l.containsEdge(l.getNodeByContent(((Couple) ((Node) source).getContent()).getLeft()),
160 l.getNodeByContent(((Couple) ((Node) target).getContent()).getLeft()))
161 && r.containsEdge(r.getNodeByContent(((Couple) ((Node) source).getContent()).getRight()),
162 r.getNodeByContent(((Couple) ((Node) target).getContent()).getRight()))) {
163 prod.addEdge((Node) source, (Node) target);
164 }
165 }
166 }
167 return prod;
168 }
169
170 /**
171 * Returns lattice l in which convex c has been doubled.
172 *
173 * @param l a lattice
174 * @param c a convex subset of l, to be doubled.
175 *
176 * @return a lattice construct from l by doubling the convex subset c.
177 */
178 public static Lattice doublingConvex(Lattice l, DAGraph c) {
179 Lattice doubled = new Lattice();
180 // Copy nodes by Content
181 for (Object node : l.getNodes()) {
182 if (c.containsNode((Node) node)) {
183 // These nodes are doubled
184 Couple cpl0 = new Couple(((Node) node).getContent(), 0);
185 Node n0 = new Node(cpl0);
186 Couple cpl1 = new Couple(((Node) node).getContent(), 1);
187 Node n1 = new Node(cpl1);
188 doubled.addNode(n0);
189 doubled.addNode(n1);
190 } else {
191 // These nodes are just copied
192 doubled.addNode(new Node(((Node) node).getContent()));
193 }
194 }
195 // Construct edges of doubled
196 Couple test = new Couple(0, 0); // used to test class of contents
197 for (Object x : doubled.getNodes()) {
198 for (Object y : doubled.getNodes()) {
199 // Add an edge if x < y
200 if (((Node) x).getContent().getClass() == test.getClass()) { // x was in convex c
201 if (((Node) y).getContent().getClass() == test.getClass()) { // y was also in convex c
202 // x & y were in convex c
203 Couple cX = (Couple) ((Node) x).getContent();
204 Couple cY = (Couple) ((Node) y).getContent();
205 if ((cX.getLeft() == cY.getLeft()) && (((Integer) cX.getRight()) == 0)
206 && (((Integer) cY.getRight()) == 1)) {
207 // Same content means same node. x is of the form (cX, 0) and y is of the for (cX, 1) so x < y in doubled.
208 doubled.addEdge((Node) x, (Node) y);
209 } else if (l.majorants(l.getNodeByContent(cX.getLeft())).contains(l.getNodeByContent(cY.getLeft()))
210 && (cX.getRight() == cY.getRight())) {
211 // x < y in l and x & y have the same second component si x < y in doubled.
212 doubled.addEdge((Node) x, (Node) y);
213 }
214 } else { // y wasn't in convex c
215 // x was in c & y wasn't
216 Couple cX = (Couple) ((Node) x).getContent();
217 if (l.majorants(l.getNodeByContent(cX.getLeft())).contains(l.getNodeByContent(((Node) y).getContent()))
218 && (((Integer) cX.getRight()) == 1)) {
219 // x < y in l and second component of x is 1.
220 doubled.addEdge((Node) x, (Node) y);
221 }
222 }
223 } else // x wasn't in convex c
224 if (((Node) y).getContent().getClass() == test.getClass()) { // y was in convex c
225 // x wasn't in c but y was
226 Couple cY = (Couple) ((Node) y).getContent();
227 if (l.majorants(l.getNodeByContent(((Node) x).getContent())).contains(l.getNodeByContent(cY.getLeft()))
228 && (((Integer) cY.getRight()) == 0)) {
229 // x < y in l and x & second component of y is 0.
230 doubled.addEdge((Node) x, (Node) y);
231 }
232 } else // y wasn't in convex c
233 // x wasn't in c nor y
234 if (l.majorants(l.getNodeByContent(((Node) x).getContent())).contains(l.getNodeByContent(((Node) y).getContent()))) {
235 // x < y in l and x & second component of y is 0.
236 doubled.addEdge((Node) x, (Node) y);
237 }
238 }
239 }
240 doubled.transitiveReduction();
241 return doubled;
242 }
243
244 /**
245 * Computes successors of node n in the boolean algebra currently generated.
246 *
247 * @param node this method compute successors of this node
248 * @param l boolean algebra currently generated
249 * @param n the number of node of l will be 2^n at the end of computation
250 */
251 private static void recursiveBooleanAlgebra(Node node, Lattice l, int n) {
252 for (int i = 0; i < n; i++) {
253 BitSet b = (BitSet) node.getContent();
254 if (!b.get(i)) {
255 BitSet bs = (BitSet) b.clone();
256 bs.set(i, true);
257 if (l.getNodeByContent(bs) == null) {
258 Node next = new Node(bs);
259 l.addNode(next);
260 l.addEdge(node, next);
261 recursiveBooleanAlgebra(next, l, n);
262 } else {
263 l.addEdge(node, l.getNodeByContent(bs));
264 }
265 }
266 }
267 }
268
269 /**
270 * Computes successors of node n in the lattice l.
271 *
272 * @param node successors of this node are computed by this method
273 * @param l lattice of permutations currently generated
274 * @param n lattice of permutation of the set 1..n is currently generated
275 */
276 private static void recursivePermutationLattice(Node node, Lattice l, int n) {
277 Permutation s = (Permutation) node.getContent();
278 for (int i = 0; i < s.getLength() - 1; i++) {
279 if (s.getContent()[i] < s.getContent()[i + 1]) {
280 int[] newC = s.getContent().clone();
281 Node currentNode = new Node();
282 newC[i] = s.getContent()[i + 1];
283 newC[i + 1] = s.getContent()[i];
284 Permutation newP = new Permutation(n);
285 newP.setContent(newC);
286 boolean newNode = true;
287 Iterator<Node> it = l.getNodes().iterator();
288 while (it.hasNext() && newNode) {
289 currentNode = it.next();
290 Permutation currentContent = (Permutation) currentNode.getContent();
291 newNode = !(currentContent.equals(newP));
292 }
293 if (newNode) {
294 Permutation newS = new Permutation(n);
295 newS.setContent(newC);
296 Node next = new Node(newS);
297 l.addNode(next);
298 l.addEdge(node, next);
299 recursivePermutationLattice(next, l, n);
300 } else {
301 l.addEdge(node, currentNode);
302 }
303 }
304 }
305 }
306
307 /**
308 * Empty constructor.
309 */
310 protected LatticeFactory() {
311 super();
312 }
313
314 /**
315 * This class provides a representation of permutations.
316 *
317 * If this component transforms : 0 -> 1, 1 -> 0 & 2 -> 2. Then its length
318 * is 3 and
319 *
320 * The content contains :
321 *
322 * ~~~
323 * content[0]=1 content[1]=0 content[2]=2
324 * ~~~
325 */
326 private static class Permutation {
327
328 /**
329 * This component is a permutation of 0..length-1.
330 */
331 private int length;
332
333 /**
334 * The transformation represented by this component.
335 *
336 * If this component transforms : 0 -> 1, 1 -> 0 & 2 -> 2. The field
337 * content contains :
338 *
339 * ~~~
340 * content[0]=1 content[1]=0 content[2]=2
341 * ~~~
342 */
343 private int[] content;
344
345 /**
346 * Constructs identity of the set 0..n-1.
347 *
348 * @param n permutation of the set 0..n-1.
349 */
350 Permutation(int n) {
351 this.length = n;
352 this.content = new int[n];
353 for (int i = 0; i < n; i++) {
354 this.content[i] = i;
355 }
356 }
357
358 /**
359 * Returns the transformation coded by this component.
360 *
361 * @return the transformation coded by this component.
362 */
363 public int[] getContent() {
364 return this.content;
365 }
366
367 /**
368 * Set the transformation coded by this component.
369 *
370 * Length of this component is update by this method.
371 *
372 * @param c the transformation coded in this component.
373 *
374 * @return this for chaining
375 */
376 public Permutation setContent(int[] c) {
377 this.content = c;
378 this.length = c.length;
379 return this;
380 }
381
382 /**
383 * Return length of this component.
384 *
385 * @return length of this component.
386 */
387 public int getLength() {
388 return this.length;
389 }
390
391 /**
392 * Set length of this componenet.
393 *
394 * @param l length of this component.
395 *
396 * @return true if update is successful.
397 */
398 public boolean setLength(int l) {
399 if ((this.content.length == l) && (l <= this.getLength())) {
400 this.length = l;
401 return true;
402 } else {
403 return false;
404 }
405 }
406
407 /**
408 * Returns a string representation of this component.
409 *
410 * @return a string representation of this component.
411 */
412 @Override
413 public String toString() {
414 String str = "";
415 for (int i = 0; i < this.length; i++) {
416 str = str + this.content[i];
417 }
418 return str;
419 }
420
421 /**
422 * Returns true if this component is equal to s.
423 *
424 * @param s test if this component is equal to s
425 *
426 * @return true if this component is equal to s
427 */
428 public boolean equals(Permutation s) {
429 if (!(s.getLength() == this.length)) {
430 return false;
431 } else {
432 boolean tmp = true;
433 for (int i = 0; i < this.length; i++) {
434 tmp = tmp && (this.content[i] == s.getContent()[i]);
435 }
436 return tmp;
437 }
438 }
439
440 /**
441 * Compute the hash code.
442 *
443 * @return an integer representing the object
444 */
445 @Override
446 public int hashCode() {
447 return super.hashCode();
448 }
449 }
450 }