Simplify.java Source File

00001 package gov.nasa.arc.ase.util.graph;
00002 
00003 import java.io.IOException;
00004 //#ifdef JDK11
00005 
00006 //#else JDK11
00007 import java.util.Iterator;
00008 //#endif JDK11
00009 
00010 public class Simplify {
00011   public static void main(String[] args) {
00012     if(args.length > 1) {
00013       System.out.println("usage:");
00014       System.out.println("\tjava gov.nasa.arc.ase.util.graph.Simplify [<filename>]");
00015       return;
00016     }
00017 
00018     Graph g = null;
00019 
00020     try {
00021       if(args.length == 0)
00022     g = Graph.load();
00023       else
00024     g = Graph.load(args[0]);
00025     } catch(IOException e) {
00026       System.out.println("Can't load the graph.");
00027       return;
00028     }
00029 
00030     g = simplify(g);
00031 
00032     g.save();
00033   }  
00034   public static Graph simplify(Graph g) {
00035     boolean simplified;
00036 
00037     do {
00038       simplified = false;
00039 
00040       for(Iterator i = g.getNodes().iterator(); i.hasNext(); ) {
00041     Node n0 = (Node)i.next();
00042 
00043     for(Iterator j = g.getNodes().iterator(); j.hasNext(); ) {
00044       Node n1 = (Node)j.next();
00045 
00046       if(n1.getId() <= n0.getId()) continue;
00047 
00048       if(n1.getBooleanAttribute("accepting") != 
00049           n0.getBooleanAttribute("accepting"))
00050         continue;
00051 
00052 //#ifdef DEBUG
00053 
00054 
00055 //#endif DEBUG
00056 
00057       boolean equivalent = true;
00058 
00059       for(Iterator k = n0.getOutgoingEdges().iterator(); equivalent && k.hasNext(); ) {
00060         Edge e0 = (Edge)k.next();
00061 
00062         equivalent = false;
00063 
00064 //#ifdef DEBUG
00065 
00066 
00067 
00068 
00069 
00070 
00071 
00072 
00073 
00074 
00075 //#endif DEBUG
00076 
00077         for(Iterator l = n1.getOutgoingEdges().iterator(); !equivalent && l.hasNext(); ) {
00078           Edge e1 = (Edge)l.next();
00079 
00080 //#ifdef DEBUG
00081 
00082 
00083 
00084 
00085 
00086 
00087 
00088 
00089 //#endif DEBUG
00090 
00091           if(e0.getNext() == e1.getNext() ||
00092           (
00093            (e0.getNext() == n0 || e0.getNext() == n1) &&
00094            (e1.getNext() == n0 || e1.getNext() == n1)))
00095         if(e0.getGuard().equals(e1.getGuard()))
00096           if(e0.getAction().equals(e1.getAction()))
00097 //#ifdef DEBUG
00098 
00099 
00100 //#endif DEBUG
00101             equivalent = true;
00102 //#ifdef DEBUG
00103 
00104 
00105 
00106 
00107 
00108 
00109 
00110 //#endif DEBUG
00111         }
00112 
00113 //#ifdef DEBUG
00114 
00115 
00116 
00117 
00118 
00119 
00120 
00121 
00122 
00123 
00124 
00125 
00126 //#endif DEBUG
00127       }
00128 
00129       for(Iterator k = n1.getOutgoingEdges().iterator(); equivalent && k.hasNext(); ) {
00130         Edge e1 = (Edge)k.next();
00131 
00132         equivalent = false;
00133 
00134 //#ifdef DEBUG
00135 
00136 
00137 
00138 
00139 
00140 
00141 
00142 
00143 
00144 
00145 //#endif DEBUG
00146 
00147         for(Iterator l = n0.getOutgoingEdges().iterator(); !equivalent && l.hasNext(); ) {
00148           Edge e0 = (Edge)l.next();
00149 
00150 //#ifdef DEBUG
00151 
00152 
00153 
00154 
00155 
00156 
00157 
00158 
00159 //#endif DEBUG
00160 
00161           if(e0.getNext() == e1.getNext() ||
00162           (
00163            (e0.getNext() == n0 || e0.getNext() == n1) &&
00164            (e1.getNext() == n0 || e1.getNext() == n1)))
00165         if(e0.getGuard().equals(e1.getGuard()))
00166           if(e0.getAction().equals(e1.getAction()))
00167 //#ifdef DEBUG
00168 
00169 //#endif DEBUG
00170             equivalent = true;
00171 //#ifdef DEBUG
00172 
00173 
00174 
00175 
00176 
00177 
00178 
00179 
00180 //#endif DEBUG
00181         }
00182 
00183 //#ifdef DEBUG
00184 
00185 
00186 
00187 
00188 
00189 
00190 
00191 
00192 
00193 
00194 
00195 //#endif DEBUG
00196       }
00197 
00198       if(equivalent) {
00199 //#ifdef DEBUG
00200 
00201 //#endif DEBUG
00202         for(Iterator k = n1.getIncomingEdges().iterator(); equivalent && k.hasNext(); ) {
00203           Edge e = (Edge)k.next();
00204 
00205           new Edge(e.getSource(), n0, e.getGuard(), e.getAction(), e.getAttributes());
00206         }
00207 
00208         n1.remove();
00209 
00210         simplified = true;
00211       }
00212     }
00213       }
00214     } while(simplified);
00215 
00216     return g;
00217   }  
00218 }