5 public class GraphAnalysis {
6 Termination termination;
7 static final int WORKS=0;
8 static final int ERR_NOREPAIR=1;
9 static final int ERR_CYCLE=2;
10 static final int ERR_RULE=3;
11 static final int ERR_ABSTRACT=4;
13 public GraphAnalysis(Termination t) {
17 public Set doAnalysis() {
18 HashSet nodes=new HashSet();
19 nodes.addAll(termination.conjunctions);
20 GraphNode.computeclosure(nodes,null);
21 Set cycles=GraphNode.findcycles(nodes);
22 Set couldremove=new HashSet();
23 couldremove.addAll(termination.conjunctions);
24 couldremove.addAll(termination.updatenodes);
25 couldremove.addAll(termination.consequencenodes);
26 couldremove.retainAll(cycles);
27 Vector constraints=termination.state.vConstraints;
28 for(int i=0;i<constraints.size();i++) {
29 Constraint c=(Constraint)constraints.get(i);
30 Set conjunctionset=(Set)termination.conjunctionmap.get(c);
31 if (conjunctionset.size()==1)
32 couldremove.removeAll(conjunctionset);
36 Vector couldremovevector=new Vector();
37 couldremovevector.addAll(couldremove);
38 Vector combination=new Vector();
41 if (illegal(combination,couldremovevector))
43 Set combinationset=buildset(combination,couldremovevector);
44 if (combinationset!=null) {
45 System.out.println("Checkabstract="+checkAbstract(combinationset));
46 System.out.println("Checkrepairs="+checkRepairs(combinationset));
47 System.out.println("Checkall="+checkAll(combinationset));
49 if (checkAbstract(combinationset)==0&&
50 checkRepairs(combinationset)==0&&
51 checkAll(combinationset)==0) {
52 return combinationset;
55 increment(combination,couldremovevector);
60 private static Set buildset(Vector combination, Vector couldremove) {
62 for(int i=0;i<combination.size();i++) {
63 int index=((Integer)combination.get(i)).intValue();
64 Object o=couldremove.get(index);
73 private static boolean illegal(Vector combination, Vector couldremove) {
74 if (combination.size()>couldremove.size())
78 private static void increment(Vector combination, Vector couldremove) {
79 boolean incremented=false;
80 for(int i=0;i<combination.size();i++) {
81 int newindex=((Integer)combination.get(i)).intValue()+1;
82 while(combination.contains(new Integer(newindex)))
84 if (newindex==couldremove.size()) {
86 combination.set(i,new Integer(newindex));
89 combination.set(i,new Integer(newindex));
93 if (incremented==false) /* Increase length */
94 combination.add(new Integer(0));
97 /* This function checks the graph as a whole for bad cycles */
98 public int checkAll(Collection removed) {
99 Set nodes=new HashSet();
100 nodes.addAll(termination.conjunctions);
101 nodes.removeAll(removed);
102 GraphNode.computeclosure(nodes,removed);
103 Set cycles=GraphNode.findcycles(nodes);
104 for(Iterator it=cycles.iterator();it.hasNext();) {
105 GraphNode gn=(GraphNode)it.next();
106 TermNode tn=(TermNode)gn.getOwner();
107 switch(tn.getType()) {
108 case TermNode.UPDATE:
109 case TermNode.CONJUNCTION:
111 case TermNode.ABSTRACT:
112 case TermNode.RULESCOPE:
113 case TermNode.CONSEQUENCE:
121 /* This function checks that
122 1) All abstract repairs have a corresponding data structure update
124 2) All scope nodes have either a consequence node or a compensation
125 node that isn't removed.
127 public int checkRepairs(Collection removed) {
128 Set nodes=new HashSet();
129 nodes.addAll(termination.conjunctions);
130 nodes.removeAll(removed);
131 GraphNode.computeclosure(nodes,removed);
132 Set toretain=new HashSet();
133 toretain.addAll(termination.abstractrepair);
134 toretain.addAll(termination.scopenodes);
135 nodes.retainAll(toretain);
136 /* Nodes is now the reachable set of abstractrepairs */
137 /* Check to see that each has an implementation */
138 for(Iterator it=nodes.iterator();it.hasNext();) {
139 GraphNode gn=(GraphNode)it.next();
140 TermNode tn=(TermNode)gn.getOwner();
141 if (tn.getType()==TermNode.RULESCOPE) {
142 boolean foundnode=false;
143 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
144 GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
145 GraphNode gn2=edge.getTarget();
146 if (!removed.contains(gn2)) {
147 TermNode tn2=(TermNode)gn2.getOwner();
148 if ((tn2.getType()==TermNode.CONSEQUENCE)||
149 (tn2.getType()==TermNode.UPDATE)) {
156 System.out.println(gn.getTextLabel());
159 } else if (tn.getType()==TermNode.ABSTRACT) {
160 boolean foundnode=false;
161 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
162 GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
163 GraphNode gn2=edge.getTarget();
164 if (!removed.contains(gn2)) {
165 TermNode tn2=(TermNode)gn2.getOwner();
166 if (tn2.getType()==TermNode.UPDATE) {
174 } else throw new Error("Unanticipated Node");
178 /* This method checks that all constraints have conjunction nodes
179 and that there are no bad cycles in the abstract portion of the graph.
181 public int checkAbstract(Collection removed) {
182 Vector constraints=termination.state.vConstraints;
183 for(int i=0;i<constraints.size();i++) {
184 Constraint c=(Constraint)constraints.get(i);
185 Set conjunctionset=(Set)termination.conjunctionmap.get(c);
187 boolean foundrepair=false;
188 for(Iterator it=conjunctionset.iterator();it.hasNext();) {
189 GraphNode gn=(GraphNode)it.next();
190 if (!removed.contains(gn)) {
197 Set abstractnodes=new HashSet();
198 abstractnodes.addAll(termination.conjunctions);
199 abstractnodes.removeAll(removed);
200 GraphNode.computeclosure(abstractnodes,removed);
202 Set tset=new HashSet();
203 tset.addAll(termination.conjunctions);
204 tset.addAll(termination.abstractrepair);
205 tset.addAll(termination.scopenodes);
206 tset.addAll(termination.consequencenodes);
207 abstractnodes.retainAll(tset);
208 Set cycles=GraphNode.findcycles(abstractnodes);
210 for(Iterator it=cycles.iterator();it.hasNext();) {
211 GraphNode gn=(GraphNode)it.next();
212 System.out.println("NODE: "+gn.getTextLabel());
213 TermNode tn=(TermNode)gn.getOwner();
214 switch(tn.getType()) {
215 case TermNode.CONJUNCTION:
216 case TermNode.ABSTRACT:
218 case TermNode.UPDATE:
219 throw new Error("No Update Nodes should be here");