001: //
002: // Copyright (C) 2005 United States Government as represented by the
003: // Administrator of the National Aeronautics and Space Administration
004: // (NASA). All Rights Reserved.
005: //
006: // This software is distributed under the NASA Open Source Agreement
007: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
008: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
009: // directory tree for the complete NOSA document.
010: //
011: // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
012: // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
013: // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
014: // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
015: // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
016: // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
017: // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
018: //
019: package gov.nasa.ltl.graph;
020:
021: import java.io.*;
022:
023: /**
024: * DOCUMENT ME!
025: */
026: public class SuperSetReduction {
027: public static void main(String[] args) {
028: if (args.length > 1) {
029: System.out.println("usage:");
030: System.out
031: .println("\tjava gov.nasa.ltl.graph.SuperSetReduction [<filename>]");
032:
033: return;
034: }
035:
036: Graph g = null;
037:
038: try {
039: if (args.length == 0) {
040: g = Graph.load();
041: } else {
042: g = Graph.load(args[0]);
043: }
044: } catch (IOException e) {
045: System.out.println("Can't load the graph.");
046:
047: return;
048: }
049:
050: g = reduce(g);
051:
052: g.save();
053: }
054:
055: public static Graph reduce(Graph g) {
056: final int nsets = g.getIntAttribute("nsets");
057: String type = g.getStringAttribute("type");
058: String ac = g.getStringAttribute("ac");
059:
060: if (!type.equals("gba")) {
061: throw new RuntimeException("invalid graph type: " + type);
062: }
063:
064: if (ac.equals("nodes")) {
065: final int nnodes = g.getNodeCount();
066:
067: final boolean[][] asets = new boolean[nsets][nnodes];
068:
069: g.forAllNodes(new EmptyVisitor() {
070: public void visitNode(Node n) {
071: for (int i = 0; i < nsets; i++) {
072: String acc = "acc" + i;
073:
074: if (n.getBooleanAttribute(acc)) {
075: asets[i][n.getId()] = true;
076: n.setBooleanAttribute(acc, false);
077: }
078: }
079: }
080: });
081:
082: boolean[] remove = new boolean[nsets];
083:
084: for (int i = 0; i < nsets; i++) {
085: for (int j = 0; (j < nsets) && !remove[i]; j++) {
086: if ((i != j) && !remove[j]) {
087: if (included(asets[j], asets[i])) {
088: remove[i] = true;
089: }
090: }
091: }
092: }
093:
094: int n_nsets = 0;
095:
096: for (int i = 0; i < nsets; i++) {
097: if (!remove[i]) {
098: n_nsets++;
099: }
100: }
101:
102: boolean[][] n_asets = new boolean[n_nsets][nnodes];
103:
104: n_nsets = 0;
105:
106: for (int i = 0; i < nsets; i++) {
107: if (!remove[i]) {
108: n_asets[n_nsets++] = asets[i];
109: }
110: }
111:
112: g.setIntAttribute("nsets", n_nsets);
113:
114: for (int i = 0; i < nnodes; i++) {
115: Node n = g.getNode(i);
116:
117: for (int j = 0; j < n_nsets; j++) {
118: if (n_asets[j][i]) {
119: n.setBooleanAttribute("acc" + j, true);
120: }
121: }
122: }
123:
124: return g;
125: } else if (ac.equals("edges")) {
126: final int nedges = g.getEdgeCount();
127:
128: final boolean[][] asets = new boolean[nsets][nedges];
129: final Edge[] edges = new Edge[nedges];
130:
131: g.forAllEdges(new EmptyVisitor(new Integer(0)) {
132: public void visitEdge(Edge e) {
133: int id = ((Integer) arg).intValue();
134: arg = new Integer(id + 1);
135:
136: edges[id] = e;
137:
138: for (int i = 0; i < nsets; i++) {
139: String acc = "acc" + i;
140:
141: if (e.getBooleanAttribute(acc)) {
142: asets[i][id] = true;
143: e.setBooleanAttribute(acc, false);
144: }
145: }
146: }
147: });
148:
149: boolean[] remove = new boolean[nsets];
150:
151: for (int i = 0; i < nsets; i++) {
152: for (int j = 0; (j < nsets) && !remove[i]; j++) {
153: if ((i != j) && !remove[j]) {
154: if (included(asets[j], asets[i])) {
155: remove[i] = true;
156: }
157: }
158: }
159: }
160:
161: int n_nsets = 0;
162:
163: for (int i = 0; i < nsets; i++) {
164: if (!remove[i]) {
165: n_nsets++;
166: }
167: }
168:
169: boolean[][] n_asets = new boolean[n_nsets][nedges];
170:
171: n_nsets = 0;
172:
173: for (int i = 0; i < nsets; i++) {
174: if (!remove[i]) {
175: n_asets[n_nsets++] = asets[i];
176: }
177: }
178:
179: g.setIntAttribute("nsets", n_nsets);
180:
181: for (int i = 0; i < nedges; i++) {
182: Edge e = edges[i];
183:
184: for (int j = 0; j < n_nsets; j++) {
185: if (n_asets[j][i]) {
186: e.setBooleanAttribute("acc" + j, true);
187: }
188: }
189: }
190:
191: return g;
192: } else {
193: throw new RuntimeException("invalid accepting type: " + ac);
194: }
195: }
196:
197: private static boolean included(boolean[] a, boolean[] b) {
198: final int al = a.length;
199: final int bl = b.length;
200:
201: for (int i = 0; i < al; i++) {
202: if (a[i] && !b[i]) {
203: return false;
204: }
205: }
206:
207: return true;
208: }
209: }
|