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.IOException;
022:
023: import java.util.Iterator;
024:
025: /**
026: * DOCUMENT ME!
027: */
028: public class Simplify {
029: public static void main(String[] args) {
030: if (args.length > 1) {
031: System.out.println("usage:");
032: System.out
033: .println("\tjava gov.nasa.ltl.graph.Simplify [<filename>]");
034:
035: return;
036: }
037:
038: Graph g = null;
039:
040: try {
041: if (args.length == 0) {
042: g = Graph.load();
043: } else {
044: g = Graph.load(args[0]);
045: }
046: } catch (IOException e) {
047: System.out.println("Can't load the graph.");
048:
049: return;
050: }
051:
052: g = simplify(g);
053:
054: g.save();
055: }
056:
057: public static Graph simplify(Graph g) {
058: boolean simplified;
059:
060: do {
061: simplified = false;
062:
063: for (Iterator i = g.getNodes().iterator(); i.hasNext();) {
064: Node n0 = (Node) i.next();
065:
066: for (Iterator j = g.getNodes().iterator(); j.hasNext();) {
067: Node n1 = (Node) j.next();
068:
069: if (n1.getId() <= n0.getId()) {
070: continue;
071: }
072:
073: if (n1.getBooleanAttribute("accepting") != n0
074: .getBooleanAttribute("accepting")) {
075: continue;
076: }
077:
078: boolean equivalent = true;
079:
080: for (Iterator k = n0.getOutgoingEdges().iterator(); equivalent
081: && k.hasNext();) {
082: Edge e0 = (Edge) k.next();
083:
084: equivalent = false;
085:
086: for (Iterator l = n1.getOutgoingEdges()
087: .iterator(); !equivalent && l.hasNext();) {
088: Edge e1 = (Edge) l.next();
089:
090: if ((e0.getNext() == e1.getNext())
091: || ((e0.getNext() == n0 || e0
092: .getNext() == n1) && (e1
093: .getNext() == n0 || e1
094: .getNext() == n1))) {
095: if (e0.getGuard().equals(e1.getGuard())) {
096: if (e0.getAction().equals(
097: e1.getAction())) {
098: equivalent = true;
099: }
100: }
101: }
102: }
103: }
104:
105: for (Iterator k = n1.getOutgoingEdges().iterator(); equivalent
106: && k.hasNext();) {
107: Edge e1 = (Edge) k.next();
108:
109: equivalent = false;
110:
111: for (Iterator l = n0.getOutgoingEdges()
112: .iterator(); !equivalent && l.hasNext();) {
113: Edge e0 = (Edge) l.next();
114:
115: if ((e0.getNext() == e1.getNext())
116: || ((e0.getNext() == n0 || e0
117: .getNext() == n1) && (e1
118: .getNext() == n0 || e1
119: .getNext() == n1))) {
120: if (e0.getGuard().equals(e1.getGuard())) {
121: if (e0.getAction().equals(
122: e1.getAction())) {
123: equivalent = true;
124: }
125: }
126: }
127: }
128: }
129:
130: if (equivalent) {
131: for (Iterator k = n1.getIncomingEdges()
132: .iterator(); equivalent && k.hasNext();) {
133: Edge e = (Edge) k.next();
134:
135: new Edge(e.getSource(), n0, e.getGuard(), e
136: .getAction(), e.getAttributes());
137: }
138:
139: n1.remove();
140:
141: simplified = true;
142: }
143: }
144: }
145: } while (simplified);
146:
147: return g;
148: }
149: }
|