KickJava   Java API By Example, From Geeks To Geeks.

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


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 import java.util.List JavaDoc;
26
27
28 /**
29  * DOCUMENT ME!
30  */
31 public class SynchronousProduct {
32   public static void dfs (Graph g, Node[][] nodes, int nsets, Node n0, Node n1) {
33     Node n = get(g, nodes, n0, n1);
34
35     List JavaDoc t0 = n0.getOutgoingEdges();
36     List JavaDoc t1 = n1.getOutgoingEdges();
37
38     for (Iterator JavaDoc i0 = t0.iterator(); i0.hasNext();) {
39       Edge e0 = (Edge) i0.next();
40       Node next0 = e0.getNext();
41       Edge theEdge = null;
42
43       boolean found = false;
44
45       for (Iterator JavaDoc i1 = t1.iterator(); i1.hasNext() && !found;) {
46         Edge e1 = (Edge) i1.next();
47
48         if (e1.getBooleanAttribute("else")) {
49           if (theEdge == null) {
50             theEdge = e1;
51           }
52         } else {
53           found = true;
54
55           for (int i = 0; i < nsets; i++) {
56             boolean b0 = e0.getBooleanAttribute("acc" + i);
57             boolean b1 = e1.getBooleanAttribute("acc" + i);
58
59             if (b1 && !b0) { // corrected by Dimitra
60 found = false;
61
62               break;
63             }
64           }
65         }
66
67         if (found) {
68           theEdge = e1;
69         }
70       }
71
72       if (theEdge != null) {
73         Node next1 = theEdge.getNext();
74         boolean newNext = isNew(nodes, next0, next1);
75         Node next = get(g, nodes, next0, next1);
76         Edge e = new Edge(n, next, e0.getGuard(), theEdge.getAction(), null);
77
78         if (newNext) {
79           dfs(g, nodes, nsets, next0, next1);
80         }
81       }
82     }
83   }
84
85   public static void main (String JavaDoc[] args) {
86     Graph g0;
87     Graph g1;
88
89     try {
90       g0 = Graph.load(args[0]);
91       g1 = Graph.load(args[1]);
92     } catch (IOException JavaDoc e) {
93       System.err.println("Can't load automata");
94       System.exit(1);
95
96       return;
97     }
98
99     Graph g = product(g0, g1);
100
101     g.save();
102   }
103
104   public static Graph product (Graph g0, Graph g1) {
105     int nsets = g0.getIntAttribute("nsets");
106
107     if (nsets != g1.getIntAttribute("nsets")) {
108       System.err.println("Different number of accepting sets");
109       System.exit(1);
110     }
111
112     Node[][] nodes;
113     Graph g = new Graph();
114     g.setStringAttribute("type", "ba");
115     g.setStringAttribute("ac", "nodes");
116
117     nodes = new Node[g0.getNodeCount()][g1.getNodeCount()];
118
119     dfs(g, nodes, nsets, g0.getInit(), g1.getInit());
120
121     return g;
122   }
123
124   private static boolean isNew (Node[][] nodes, Node n0, Node n1) {
125     return nodes[n0.getId()][n1.getId()] == null;
126   }
127
128   private static Node get (Graph g, Node[][] nodes, Node n0, Node n1) {
129     if (nodes[n0.getId()][n1.getId()] == null) {
130       Node n = new Node(g);
131       String JavaDoc label0 = n0.getStringAttribute("label");
132       String JavaDoc label1 = n1.getStringAttribute("label");
133
134       if (label0 == null) {
135         label0 = Integer.toString(n0.getId());
136       }
137
138       if (label1 == null) {
139         label1 = Integer.toString(n1.getId());
140       }
141
142       n.setStringAttribute("label", label0 + "+" + label1);
143
144       if (n1.getBooleanAttribute("accepting")) {
145         n.setBooleanAttribute("accepting", true);
146       }
147
148       return nodes[n0.getId()][n1.getId()] = n;
149     }
150
151     return nodes[n0.getId()][n1.getId()];
152   }
153 }
Popular Tags