KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gov > nasa > ltl > graph > Simplify


1
2 //
3 // Copyright (C) 2005 United States Government as represented by the
4 // Administrator of the National Aeronautics and Space Administration
5 // (NASA). All Rights Reserved.
6 //
7 // This software is distributed under the NASA Open Source Agreement
8 // (NOSA), version 1.3. The NOSA has been approved by the Open Source
9 // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
10 // directory tree for the complete NOSA document.
11 //
12 // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
13 // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
14 // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
15 // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
16 // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
17 // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
18 // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
19 //
20 package gov.nasa.ltl.graph;
21
22 import java.io.IOException JavaDoc;
23
24 import java.util.Iterator JavaDoc;
25
26
27 /**
28  * DOCUMENT ME!
29  */
30 public class Simplify {
31   public static void main (String JavaDoc[] args) {
32     if (args.length > 1) {
33       System.out.println("usage:");
34       System.out.println("\tjava gov.nasa.ltl.graph.Simplify [<filename>]");
35
36       return;
37     }
38
39     Graph g = null;
40
41     try {
42       if (args.length == 0) {
43         g = Graph.load();
44       } else {
45         g = Graph.load(args[0]);
46       }
47     } catch (IOException JavaDoc e) {
48       System.out.println("Can't load the graph.");
49
50       return;
51     }
52
53     g = simplify(g);
54
55     g.save();
56   }
57
58   public static Graph simplify (Graph g) {
59     boolean simplified;
60
61     do {
62       simplified = false;
63
64       for (Iterator JavaDoc i = g.getNodes().iterator(); i.hasNext();) {
65         Node n0 = (Node) i.next();
66
67         for (Iterator JavaDoc j = g.getNodes().iterator(); j.hasNext();) {
68           Node n1 = (Node) j.next();
69
70           if (n1.getId() <= n0.getId()) {
71             continue;
72           }
73
74           if (n1.getBooleanAttribute("accepting") != n0.getBooleanAttribute(
75                                                            "accepting")) {
76             continue;
77           }
78
79           boolean equivalent = true;
80
81           for (Iterator JavaDoc k = n0.getOutgoingEdges().iterator();
82                equivalent && k.hasNext();) {
83             Edge e0 = (Edge) k.next();
84
85             equivalent = false;
86
87             for (Iterator JavaDoc l = n1.getOutgoingEdges().iterator();
88                  !equivalent && l.hasNext();) {
89               Edge e1 = (Edge) l.next();
90
91               if ((e0.getNext() == e1.getNext()) ||
92                       ((e0.getNext() == n0 || e0.getNext() == n1) &&
93                         (e1.getNext() == n0 || e1.getNext() == n1))) {
94                 if (e0.getGuard().equals(e1.getGuard())) {
95                   if (e0.getAction().equals(e1.getAction())) {
96                     equivalent = true;
97                   }
98                 }
99               }
100             }
101           }
102
103           for (Iterator JavaDoc k = n1.getOutgoingEdges().iterator();
104                equivalent && k.hasNext();) {
105             Edge e1 = (Edge) k.next();
106
107             equivalent = false;
108
109             for (Iterator JavaDoc l = n0.getOutgoingEdges().iterator();
110                  !equivalent && l.hasNext();) {
111               Edge e0 = (Edge) l.next();
112
113               if ((e0.getNext() == e1.getNext()) ||
114                       ((e0.getNext() == n0 || e0.getNext() == n1) &&
115                         (e1.getNext() == n0 || e1.getNext() == n1))) {
116                 if (e0.getGuard().equals(e1.getGuard())) {
117                   if (e0.getAction().equals(e1.getAction())) {
118                     equivalent = true;
119                   }
120                 }
121               }
122             }
123           }
124
125           if (equivalent) {
126             for (Iterator JavaDoc k = n1.getIncomingEdges().iterator();
127                  equivalent && k.hasNext();) {
128               Edge e = (Edge) k.next();
129
130               new Edge(e.getSource(), n0, e.getGuard(), e.getAction(),
131                        e.getAttributes());
132             }
133
134             n1.remove();
135
136             simplified = true;
137           }
138         }
139       }
140     } while (simplified);
141
142     return g;
143   }
144 }
Popular Tags