001: package ro.infoiasi.donald.compiler.simple;
002:
003: import java.util.*;
004:
005: class RelationNotInternal extends RuntimeException {
006: }
007:
008: class IncompatibleRelations extends RuntimeException {
009: };
010:
011: public class Relation {
012: public class IntPair implements Comparable {
013: private int first;
014: private int second;
015:
016: public IntPair(int i, int j) {
017: first = i;
018: second = j;
019: }
020:
021: public int getFirst() {
022: return first;
023: }
024:
025: public int getSecond() {
026: return second;
027: }
028:
029: public void setFirst(int i) {
030: first = i;
031: }
032:
033: public void setSecond(int j) {
034: second = j;
035: }
036:
037: public boolean equals(Object o) {
038: return (o instanceof IntPair)
039: && first == ((IntPair) o).first
040: && second == ((IntPair) o).second;
041: }
042:
043: public int hashCode() {
044: int result = 17;
045: result = 37 * result + first;
046: result = 37 * result + second;
047: return result;
048: }
049:
050: public int compareTo(Object o) {
051: IntPair ip = (IntPair) o;
052: if (first < ip.first) {
053: return -1;
054: } else if (first > ip.first) {
055: return +1;
056: } else if (second < ip.second) {
057: return -1;
058: } else if (second > ip.second) {
059: return +1;
060: } else {
061: return 0;
062: }
063: }
064:
065: public String toString() {
066: return "(" + first + "," + second + ")";
067: }
068: }
069:
070: // a subset of {1,...,n}x{1,...,m}
071: private Set s = newSet();
072: private int n = 0;
073: private int m = 0;
074:
075: private static Set newSet() {
076: return new LinkedHashSet();
077: }
078:
079: public Relation(int n) {
080: this (n, n);
081: }
082:
083: public Relation(int n, int m) {
084: this .n = n;
085: this .m = m;
086: }
087:
088: public Relation(int n, boolean[][] a) {
089: this (n, n, a);
090: }
091:
092: public Relation(int n, int m, boolean[][] a) {
093: this (n, m);
094: for (int i = 0; i < n; i++) {
095: for (int j = 0; j < m; j++) {
096: if (a[i][j]) {
097: add(i, j);
098: }
099: }
100: }
101: }
102:
103: public Relation(Relation r) {
104: this (r.m, r.m);
105: s = newSet();
106: s.addAll(r.s);
107: }
108:
109: private void checkPair(int i, int j)
110: throws IndexOutOfBoundsException {
111: if (i < 0 || i >= n || j < 0 || j >= m) {
112: throw new IndexOutOfBoundsException();
113: }
114: }
115:
116: private void checkInternal() throws RelationNotInternal {
117: if (n != m) {
118: throw new RelationNotInternal();
119: }
120: }
121:
122: public boolean contains(int i, int j) {
123: checkPair(i, j);
124: return s.contains(new IntPair(i, j));
125: }
126:
127: public boolean add(int i, int j) {
128: checkPair(i, j);
129: return s.add(new IntPair(i, j));
130: }
131:
132: public boolean remove(int i, int j) {
133: checkPair(i, j);
134: return s.remove(new IntPair(i, j));
135: }
136:
137: public Iterator iterator() {
138: return s.iterator();
139: }
140:
141: public boolean isReflexive() {
142: checkInternal();
143: for (int i = 0; i < n; i++) {
144: if (!contains(i, i)) {
145: return false;
146: }
147: }
148: return true;
149: }
150:
151: public boolean isIreflexive() {
152: checkInternal();
153: for (int i = 0; i < n; i++) {
154: if (contains(i, i)) {
155: return false;
156: }
157: }
158: return true;
159: }
160:
161: public Relation reflexiveClosure() {
162: checkInternal();
163: Relation r = new Relation(this );
164: for (int i = 0; i < n; i++) {
165: r.add(i, i);
166: }
167: return r;
168: }
169:
170: public boolean isTransitive() {
171: checkInternal();
172: for (int k = 0; k < n; k++) {
173: for (int i = 0; i < n; i++) {
174: if (contains(i, k)) {
175: for (int j = 0; j < n; j++) {
176: if (contains(k, j) && !contains(i, j)) {
177: return false;
178: }
179: }
180: }
181: }
182: }
183: return true;
184: }
185:
186: public Relation transitiveClosure() {
187: checkInternal();
188: Relation r = new Relation(this );
189: // Floyd - Warshal algorithm
190: for (int k = 0; k < n; k++) {
191: for (int i = 0; i < n; i++) {
192: if (r.contains(i, k)) {
193: for (int j = 0; j < n; j++) {
194: if (r.contains(k, j)) {
195: r.add(i, j);
196: }
197: }
198: }
199: }
200: }
201: return r;
202: }
203:
204: public boolean isSymmetrical() {
205: checkInternal();
206: Iterator it = s.iterator();
207: while (it.hasNext()) {
208: IntPair ip = (IntPair) it.next();
209: if (!contains(ip.getSecond(), ip.getFirst())) {
210: return false;
211: }
212: }
213: return true;
214: }
215:
216: public boolean isAsymmetrical() {
217: checkInternal();
218: Iterator it = s.iterator();
219: while (it.hasNext()) {
220: IntPair ip = (IntPair) it.next();
221: if (contains(ip.getSecond(), ip.getFirst())) {
222: return false;
223: }
224: }
225: return true;
226: }
227:
228: public boolean isAntisymmetrical() {
229: checkInternal();
230: Iterator it = s.iterator();
231: while (it.hasNext()) {
232: IntPair ip = (IntPair) it.next();
233: if (contains(ip.getSecond(), ip.getFirst())
234: && ip.getFirst() != ip.getSecond()) {
235: return false;
236: }
237: }
238: return true;
239: }
240:
241: public Relation symmetricalClosure() {
242: checkInternal();
243: Relation r = new Relation(this );
244: Iterator it = s.iterator();
245: while (it.hasNext()) {
246: IntPair ip = (IntPair) it.next();
247: r.add(ip.getSecond(), ip.getFirst());
248: }
249: return r;
250: }
251:
252: public Relation reflexiveTransitiveClosure() {
253: return reflexiveClosure().transitiveClosure();
254: }
255:
256: public boolean isEquivalence() {
257: return (isReflexive() && isSymmetrical() && isTransitive());
258: }
259:
260: public Relation equivalenceClosure() {
261: return reflexiveClosure().transitiveClosure()
262: .symmetricalClosure();
263: }
264:
265: public boolean isPartialOrdering() {
266: return (isReflexive() && isAntisymmetrical() && isTransitive());
267: }
268:
269: public boolean isTotalOrdering() {
270: return (isPartialOrdering() && isConex());
271: }
272:
273: public boolean isConex() {
274: checkInternal();
275: for (int i = 0; i < n; i++) {
276: for (int j = i + 1; j < n; j++) {
277: if (!contains(i, j) && !contains(j, i)) {
278: return false;
279: }
280: }
281: }
282: return true;
283: }
284:
285: public Relation inverse() {
286: Relation r = new Relation(m, n);
287: Iterator it = s.iterator();
288: while (it.hasNext()) {
289: IntPair ip = (IntPair) it.next();
290: r.add(ip.getSecond(), ip.getFirst());
291: }
292: return r;
293: }
294:
295: public static Relation product(Relation r1, Relation r2) {
296: if (r1.m != r2.n) {
297: throw new IncompatibleRelations();
298: }
299: Relation r = new Relation(r1.n, r2.m);
300: Iterator it = r1.s.iterator();
301: while (it.hasNext()) {
302: IntPair ip1 = (IntPair) it.next();
303: for (int i = 0; i < r2.m; i++) {
304: if (r2.contains(ip1.getSecond(), i)) {
305: r.add(ip1.getFirst(), i);
306: }
307: }
308: }
309: return r;
310: }
311:
312: public boolean[][] toArray() {
313: boolean[][] a = new boolean[n][];
314: for (int i = 0; i < n; i++) {
315: a[i] = new boolean[m];
316: for (int j = 0; j < m; j++) {
317: if (s.contains(new IntPair(i, j))) {
318: a[i][j] = true;
319: } else {
320: a[i][j] = false;
321: }
322: }
323: }
324: return a;
325: }
326:
327: public String toString() {
328: StringBuffer sb = new StringBuffer();
329: sb.append("{");
330: Iterator it = s.iterator();
331: while (it.hasNext()) {
332: IntPair ip = (IntPair) it.next();
333: sb.append(ip.toString());
334: }
335: sb.append("}");
336: return sb.toString();
337: }
338:
339: private static void printBoolMatrix(boolean[][] a) {
340: for (int i = 0; i < a.length; i++) {
341: for (int j = 0; j < a[i].length; j++) {
342: if (a[i][j]) {
343: System.out.print("1");
344: } else {
345: System.out.print("0");
346: }
347: }
348: System.out.println();
349: }
350: //System.out.println();
351: }
352:
353: public static void main(String[] args) throws RelationNotInternal {
354: boolean[][] a = { { false, true, false, false },
355: { false, false, true, false },
356: { false, false, false, true },
357: { false, true, false, true } };
358:
359: boolean[][] c = { { true, false, false, false, false },
360: { false, true, false, false, false },
361: { false, true, false, false, false },
362: { false, true, false, false, true } };
363:
364: Relation rho = new Relation(4, a);
365: Relation sigma = new Relation(4, 5, c);
366: printBoolMatrix(rho.toArray());
367: printBoolMatrix(sigma.toArray());
368: printBoolMatrix(product(rho, sigma).toArray());
369:
370: System.out.println(rho);
371: System.out.println(rho.reflexiveClosure() + " "
372: + rho.isReflexive() + " "
373: + rho.reflexiveClosure().isReflexive());
374: System.out.println(rho.transitiveClosure() + " "
375: + rho.isTransitive() + " "
376: + rho.transitiveClosure().isTransitive());
377: System.out.println(rho.symmetricalClosure() + " "
378: + rho.isSymmetrical() + " "
379: + rho.symmetricalClosure().isSymmetrical());
380: }
381: }
|