|
1
2 package gov.nasa.ltl.graph;
21
22 import java.io.*;
23
24
27 public class SuperSetReduction {
28 public static void main (String  [] args) {
29 if (args.length > 1) {
30 System.out.println("usage:");
31 System.out.println(
32 "\tjava gov.nasa.ltl.graph.SuperSetReduction [<filename>]");
33
34 return;
35 }
36
37 Graph g = null;
38
39 try {
40 if (args.length == 0) {
41 g = Graph.load();
42 } else {
43 g = Graph.load(args[0]);
44 }
45 } catch (IOException e) {
46 System.out.println("Can't load the graph.");
47
48 return;
49 }
50
51 g = reduce(g);
52
53 g.save();
54 }
55
56 public static Graph reduce (Graph g) {
57 final int nsets = g.getIntAttribute("nsets");
58 String type = g.getStringAttribute("type");
59 String ac = g.getStringAttribute("ac");
60
61 if (!type.equals("gba")) {
62 throw new RuntimeException ("invalid graph type: " + type);
63 }
64
65 if (ac.equals("nodes")) {
66 final int nnodes = g.getNodeCount();
67
68 final boolean[][] asets = new boolean[nsets][nnodes];
69
70 g.forAllNodes(new EmptyVisitor() {
71 public void visitNode (Node n) {
72 for (int i = 0; i < nsets; i++) {
73 String acc = "acc" + i;
74
75 if (n.getBooleanAttribute(acc)) {
76 asets[i][n.getId()] = true;
77 n.setBooleanAttribute(acc, false);
78 }
79 }
80 }
81 });
82
83 boolean[] remove = new boolean[nsets];
84
85 for (int i = 0; i < nsets; i++) {
86 for (int j = 0; (j < nsets) && !remove[i]; j++) {
87 if ((i != j) && !remove[j]) {
88 if (included(asets[j], asets[i])) {
89 remove[i] = true;
90 }
91 }
92 }
93 }
94
95 int n_nsets = 0;
96
97 for (int i = 0; i < nsets; i++) {
98 if (!remove[i]) {
99 n_nsets++;
100 }
101 }
102
103 boolean[][] n_asets = new boolean[n_nsets][nnodes];
104
105 n_nsets = 0;
106
107 for (int i = 0; i < nsets; i++) {
108 if (!remove[i]) {
109 n_asets[n_nsets++] = asets[i];
110 }
111 }
112
113 g.setIntAttribute("nsets", n_nsets);
114
115 for (int i = 0; i < nnodes; i++) {
116 Node n = g.getNode(i);
117
118 for (int j = 0; j < n_nsets; j++) {
119 if (n_asets[j][i]) {
120 n.setBooleanAttribute("acc" + j, true);
121 }
122 }
123 }
124
125 return g;
126 } else if (ac.equals("edges")) {
127 final int nedges = g.getEdgeCount();
128
129 final boolean[][] asets = new boolean[nsets][nedges];
130 final Edge[] edges = new Edge[nedges];
131
132 g.forAllEdges(new EmptyVisitor(new Integer (0)) {
133 public void visitEdge (Edge e) {
134 int id = ((Integer ) arg).intValue();
135 arg = new Integer (id + 1);
136
137 edges[id] = e;
138
139 for (int i = 0; i < nsets; i++) {
140 String acc = "acc" + i;
141
142 if (e.getBooleanAttribute(acc)) {
143 asets[i][id] = true;
144 e.setBooleanAttribute(acc, false);
145 }
146 }
147 }
148 });
149
150 boolean[] remove = new boolean[nsets];
151
152 for (int i = 0; i < nsets; i++) {
153 for (int j = 0; (j < nsets) && !remove[i]; j++) {
154 if ((i != j) && !remove[j]) {
155 if (included(asets[j], asets[i])) {
156 remove[i] = true;
157 }
158 }
159 }
160 }
161
162 int n_nsets = 0;
163
164 for (int i = 0; i < nsets; i++) {
165 if (!remove[i]) {
166 n_nsets++;
167 }
168 }
169
170 boolean[][] n_asets = new boolean[n_nsets][nedges];
171
172 n_nsets = 0;
173
174 for (int i = 0; i < nsets; i++) {
175 if (!remove[i]) {
176 n_asets[n_nsets++] = asets[i];
177 }
178 }
179
180 g.setIntAttribute("nsets", n_nsets);
181
182 for (int i = 0; i < nedges; i++) {
183 Edge e = edges[i];
184
185 for (int j = 0; j < n_nsets; j++) {
186 if (n_asets[j][i]) {
187 e.setBooleanAttribute("acc" + j, true);
188 }
189 }
190 }
191
192 return g;
193 } else {
194 throw new RuntimeException ("invalid accepting type: " + ac);
195 }
196 }
197
198 private static boolean included (boolean[] a, boolean[] b) {
199 final int al = a.length;
200 final int bl = b.length;
201
202 for (int i = 0; i < al; i++) {
203 if (a[i] && !b[i]) {
204 return false;
205 }
206 }
207
208 return true;
209 }
210 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.