KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > annotation > arraycheck > WeightedDirectedSparseGraph


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2000 Feng Qian
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */

25
26 package soot.jimple.toolkits.annotation.arraycheck;
27
28 import java.util.*;
29
30 class WeightedDirectedSparseGraph
31 {
32     private boolean isUnknown;
33
34     /* The graph is in linked list structure. */
35     private Hashtable sources = new Hashtable();
36
37     /* vertex set, may contain superious nodes. */
38     private HashSet vertexes = new HashSet();
39
40     public WeightedDirectedSparseGraph(HashSet vertexset)
41     {
42     this(vertexset, false);
43     }
44
45     public WeightedDirectedSparseGraph(HashSet vertexset, boolean isTop)
46     {
47     this.vertexes = vertexset;
48     this.isUnknown = !isTop;
49     }
50
51     public void setTop()
52     {
53     this.isUnknown = false;
54     this.sources.clear();
55     }
56
57     public HashSet getVertexes()
58     {
59     return this.vertexes;
60     }
61
62     public void setVertexes(HashSet newset)
63     {
64     this.vertexes = newset;
65     this.sources.clear();
66     }
67     /**
68      * Add an edge with weight to the graph
69      */

70     public void addEdge(Object JavaDoc from, Object JavaDoc to, int w)
71     {
72     if (this.isUnknown)
73         throw new RuntimeException JavaDoc("Unknown graph can not have edges");
74
75     Hashtable targets = (Hashtable)sources.get(from);
76
77     if (targets == null)
78     {
79         /* a new node was added to the graph */
80         targets = new Hashtable();
81         sources.put(from, targets);
82     }
83
84         IntContainer weight = (IntContainer)targets.get(to);
85
86     if (weight == null)
87     {
88         weight = new IntContainer(w);
89         targets.put(to, weight);
90     }
91     else
92     {
93         if (weight.value > w)
94         weight.value = w;
95     }
96     }
97
98     /** addMutualEdge adds bi-direct edges between two nodes.
99      * for example,
100      * i = j + 1;
101      * generates two directed edges.
102      * one from j to i with weight 1, another from i to j with weight -1
103      */

104     public void addMutualEdges(Object JavaDoc from, Object JavaDoc to, int weight)
105     {
106     addEdge(from, to, weight);
107     addEdge(to, from, -weight);
108     }
109
110     /* removeEdge removes all edges from source to target.
111      */

112     public void removeEdge(Object JavaDoc from, Object JavaDoc to)
113     {
114     Hashtable targets = (Hashtable)sources.get(from);
115     if (targets == null)
116         return;
117
118     targets.remove(to);
119
120     if (targets.size() == 0)
121     {
122         sources.remove(from);
123     }
124     }
125     
126     public boolean hasEdge(Object JavaDoc from, Object JavaDoc to)
127     {
128     Hashtable targets = (Hashtable)sources.get(from);
129
130     if (targets == null)
131         return false;
132
133     return targets.containsKey(to);
134     }
135
136     /* return back the weight of the edge from source to target */
137     public int edgeWeight(Object JavaDoc from, Object JavaDoc to)
138     {
139     Hashtable targets = (Hashtable)sources.get(from);
140
141     if (targets == null)
142         throw new RuntimeException JavaDoc("No such edge ("+from+" ,"+to+") exists.");
143
144     IntContainer weight = (IntContainer)targets.get(to);
145     if (weight == null)
146         throw new RuntimeException JavaDoc("No such edge ("+from+", "+to+") exists.");
147
148     return weight.value;
149     }
150
151     /* If other graph is unknown, keep current one.
152     * If current graph is unknown, copy the other.
153     And if both are not unknown, union each edge.
154     */

155     public void unionSelf(WeightedDirectedSparseGraph other)
156     {
157     if (other == null)
158         return;
159     
160     WeightedDirectedSparseGraph othergraph =
161         (WeightedDirectedSparseGraph)other;
162
163     if (othergraph.isUnknown)
164         return;
165
166     if (this.isUnknown)
167         addAll(othergraph);
168     
169     List sourceList = new ArrayList(this.sources.keySet());
170
171     Iterator firstSrcIt = sourceList.iterator();
172
173     while (firstSrcIt.hasNext())
174     {
175         Object JavaDoc srcKey = firstSrcIt.next();
176         Hashtable src1 = (Hashtable)this.sources.get(srcKey);
177         Hashtable src2 = (Hashtable)othergraph.sources.get(srcKey);
178
179         /* other is unbounded */
180         if (src2 == null)
181         {
182         this.sources.remove(srcKey);
183         continue;
184         }
185
186         List targetList = new ArrayList(src1.keySet());
187
188         Iterator targetIt = targetList.iterator();
189         
190         while (targetIt.hasNext())
191         {
192         Object JavaDoc target = targetIt.next();
193         
194         IntContainer w1 = (IntContainer)src1.get(target);
195         IntContainer w2 = (IntContainer)src2.get(target);
196         /* other is unbounded */
197         if (w2 == null)
198         {
199             src1.remove(target);
200             continue;
201         }
202
203         if (w2.value > w1.value)
204             w1.value = w2.value;
205         }
206
207         if (src1.size() == 0)
208         this.sources.remove(srcKey);
209     }
210     }
211
212
213     /* it was used to compare with former graph, if the edge weight is increasing,
214        the edge is removed (unlimited distance).
215     */

216     public void widenEdges(WeightedDirectedSparseGraph othergraph)
217     {
218     WeightedDirectedSparseGraph other =
219         (WeightedDirectedSparseGraph)othergraph;
220
221     if (other.isUnknown)
222         return;
223
224     Hashtable othersources = other.sources;
225
226     List sourceList = new ArrayList(this.sources.keySet());
227
228     Iterator srcIt = sourceList.iterator();
229     while (srcIt.hasNext())
230     {
231         Object JavaDoc src = srcIt.next();
232         Hashtable thistargets = (Hashtable)this.sources.get(src);
233         Hashtable othertargets = (Hashtable)othersources.get(src);
234
235         /* the former is unbounded */
236         if (othertargets == null)
237         {
238         this.sources.remove(src);
239         continue;
240         }
241
242         List targetList = new ArrayList(thistargets.keySet());
243
244         Iterator targetIt = targetList.iterator();
245         while (targetIt.hasNext())
246         {
247         Object JavaDoc target = targetIt.next();
248         IntContainer thisweight = (IntContainer)thistargets.get(target);
249         IntContainer otherweight = (IntContainer)othertargets.get(target);
250         
251         /* the former edge is unbounded. */
252         if (otherweight == null)
253         {
254             thistargets.remove(target);
255             continue;
256         }
257         
258         if (thisweight.value > otherweight.value)
259         {
260             thistargets.remove(target);
261         }
262         }
263         
264         if (thistargets.size()==0)
265         this.sources.remove(src);
266     }
267     }
268
269     /* It is necessary to prune the graph to the shortest path. */
270
271     /* it could be replaced by a ShortestPathGraph */
272
273
274     /* kill a node. */
275
276     public void killNode(Object JavaDoc tokill)
277     {
278     if (!this.vertexes.contains(tokill))
279         return;
280
281         this.makeShortestPathGraph();
282
283     List sourceList = new ArrayList(sources.keySet());
284
285     Iterator srcIt = sourceList.iterator();
286
287     while (srcIt.hasNext())
288     {
289         Object JavaDoc src = srcIt.next();
290
291         Hashtable targets = (Hashtable)sources.get(src);
292         /* delete the in edge */
293         targets.remove(tokill);
294
295         if (targets.size() == 0)
296         sources.remove(src);
297     }
298
299     sources.remove(tokill);
300
301         this.makeShortestPathGraph();
302     }
303
304
305     /* when met i=i+c, it is necessary to update the weight of in and out edges */
306     public void updateWeight(Object JavaDoc which, int c)
307     {
308     /* for the in edge, the weight + c. for the out edge, the weight - c */
309     Iterator srcIt = sources.keySet().iterator();
310     
311     while (srcIt.hasNext())
312     {
313         Object JavaDoc from = srcIt.next();
314         
315         Hashtable targets = (Hashtable)sources.get(from);
316
317         IntContainer weight = (IntContainer)targets.get(which);
318
319         if (weight != null)
320         weight.value += c;
321     }
322
323     /* update out edges */
324     Hashtable toset = (Hashtable)sources.get(which);
325
326     if (toset == null)
327         return;
328
329     Iterator toIt = toset.keySet().iterator();
330     while (toIt.hasNext())
331     {
332         Object JavaDoc to = toIt.next();
333         
334         IntContainer weight = (IntContainer)toset.get(to);
335         
336         weight.value -= c;
337     }
338     }
339
340     public void clear()
341     {
342     sources.clear();
343     }
344
345
346     public void replaceAllEdges(WeightedDirectedSparseGraph other)
347     {
348     this.isUnknown = other.isUnknown;
349     this.vertexes = other.vertexes;
350     this.sources = other.sources;
351     }
352
353     /* add edges that belong to this vertex set */
354     public void addBoundedAll(WeightedDirectedSparseGraph another)
355     {
356     this.isUnknown = another.isUnknown;
357
358     Hashtable othersources = another.sources;
359
360     Iterator thisnodeIt = this.vertexes.iterator();
361     while (thisnodeIt.hasNext())
362     {
363         Object JavaDoc src = thisnodeIt.next();
364         Hashtable othertargets = (Hashtable)othersources.get(src);
365         if (othertargets == null)
366         continue;
367
368         Hashtable thistargets = new Hashtable();
369         Iterator othertargetIt = othertargets.keySet().iterator();
370         while (othertargetIt.hasNext())
371         {
372         Object JavaDoc key = othertargetIt.next();
373         if (this.vertexes.contains(key))
374         {
375             IntContainer weight = (IntContainer)othertargets.get(key);
376             thistargets.put(key, weight.dup());
377         }
378         }
379
380         if (thistargets.size() > 0)
381         this.sources.put(src, thistargets);
382     }
383     }
384
385     /* add another graph's edge and weight to this graph,
386        it simply replace the edge weight.
387        When used with clear, it can copy a graph to a new graph
388     */

389     public void addAll(WeightedDirectedSparseGraph othergraph)
390     {
391     WeightedDirectedSparseGraph another =
392         (WeightedDirectedSparseGraph)othergraph;
393
394     this.isUnknown = another.isUnknown;
395     this.clear();
396
397     Hashtable othersources = another.sources;
398     Iterator othersrcIt = othersources.keySet().iterator();
399
400     while (othersrcIt.hasNext())
401     {
402         Object JavaDoc src = othersrcIt.next();
403
404         Hashtable othertargets = (Hashtable)othersources.get(src);
405
406         Hashtable thistargets = new Hashtable(othersources.size());
407         this.sources.put(src, thistargets);
408
409         Iterator targetIt = othertargets.keySet().iterator();
410         while (targetIt.hasNext())
411         {
412         Object JavaDoc target = targetIt.next();
413
414         IntContainer otherweight = (IntContainer)othertargets.get(target);
415         
416         thistargets.put(target, otherweight.dup());
417         }
418     }
419     }
420
421
422     public boolean equals(Object JavaDoc other)
423     {
424     if (other == null)
425         return false;
426
427     if (!(other instanceof WeightedDirectedSparseGraph))
428         return false;
429
430     WeightedDirectedSparseGraph othergraph =
431         (WeightedDirectedSparseGraph)other;
432
433     if (this.isUnknown != othergraph.isUnknown)
434         return false;
435
436     if (this.isUnknown)
437         return true;
438
439     // compare each edges. It is not always true, only when shortest path graph can be guaranteed.
440
Hashtable othersources = othergraph.sources;
441
442     if (this.sources.size() != othersources.size())
443         return false;
444
445     Iterator sourceIt = this.sources.keySet().iterator();
446     while (sourceIt.hasNext())
447     {
448         Object JavaDoc src = sourceIt.next();
449         Hashtable thistarget = (Hashtable)sources.get(src);
450         Hashtable othertarget = (Hashtable)othersources.get(src);
451         
452         if (othertarget == null)
453         return false;
454
455         if (thistarget.size() != othertarget.size())
456         return false;
457
458         Iterator targetIt = thistarget.keySet().iterator();
459         while (targetIt.hasNext())
460         {
461         Object JavaDoc target = targetIt.next();
462         IntContainer thisweight = (IntContainer)thistarget.get(target);
463         IntContainer otherweight = (IntContainer)othertarget.get(target);
464
465         if (otherweight == null)
466             return false;
467
468         if (thisweight.value != otherweight.value)
469             return false;
470         }
471     }
472
473     return true;
474     }
475
476     public String JavaDoc toString()
477     {
478     String JavaDoc graphstring="WeightedDirectedSparseGraph:\n";
479
480     graphstring = graphstring+this.vertexes+"\n";
481
482     Iterator srcIt = sources.keySet().iterator();
483
484     while (srcIt.hasNext())
485     {
486         Object JavaDoc src = srcIt.next();
487
488         graphstring = graphstring + src +" : ";
489
490         Hashtable targets = (Hashtable)sources.get(src);
491         
492         Iterator targetIt = targets.keySet().iterator();
493         while (targetIt.hasNext())
494         {
495         Object JavaDoc target = targetIt.next();
496         IntContainer weight = (IntContainer)targets.get(target);
497         graphstring = graphstring + target +"("+weight.value+") ";
498         }
499         graphstring +="\n";
500     }
501
502     return graphstring;
503     }
504
505     public WeightedDirectedSparseGraph dup()
506     {
507     WeightedDirectedSparseGraph newone =
508         new WeightedDirectedSparseGraph(this.vertexes);
509
510     newone.addAll(this);
511     
512     return newone;
513     }
514
515     public boolean makeShortestPathGraph()
516     {
517     boolean nonegcycle = true;
518
519     List srcList = new ArrayList(sources.keySet());
520
521     Iterator srcIt = srcList.iterator();
522     
523     while (srcIt.hasNext())
524     {
525         Object JavaDoc src = srcIt.next();
526         
527         if (!SSSPFinder(src))
528         {
529         nonegcycle = false;
530         }
531     }
532     
533     return nonegcycle;
534     }
535
536     private HashSet reachableNodes = new HashSet();
537     private HashSet reachableEdges = new HashSet();
538     private Hashtable distance = new Hashtable();
539     private Hashtable pei = new Hashtable();
540     
541     private boolean SSSPFinder(Object JavaDoc src)
542     {
543     Hashtable outedges = (Hashtable)sources.get(src);
544     if (outedges == null)
545         return true;
546
547     if (outedges.size() == 0)
548         return true;
549
550     InitializeSingleSource(src);
551     getReachableNodesAndEdges(src);
552
553     // relaxation
554
int vSize = reachableNodes.size();
555
556     for (int i=0; i<vSize; i++)
557     {
558         Iterator edgeIt = reachableEdges.iterator();
559
560         while (edgeIt.hasNext())
561         {
562         WeightedDirectedEdge edge =
563             (WeightedDirectedEdge)edgeIt.next();
564
565         Relax(edge.from, edge.to, edge.weight);
566         }
567     }
568         
569     distance.remove(src);
570
571     // check negative cycle
572

573     {
574         Iterator edgeIt = reachableEdges.iterator();
575         while (edgeIt.hasNext())
576         {
577         WeightedDirectedEdge edge =
578             (WeightedDirectedEdge)edgeIt.next();
579
580         IntContainer dfrom = (IntContainer)distance.get(edge.from);
581
582         if (dfrom == null)
583             continue;
584         
585         IntContainer dto = (IntContainer)distance.get(edge.to);
586         if (dto == null)
587             continue;
588
589         if (dto.value > (dfrom.value + edge.weight))
590             return false;
591         }
592     }
593
594     // update the graph
595
outedges.clear();
596     Iterator targetIt = distance.keySet().iterator();
597     while (targetIt.hasNext())
598     {
599         Object JavaDoc to = targetIt.next();
600         IntContainer dist = (IntContainer)distance.get(to);
601
602         outedges.put(to, dist.dup());
603     }
604     
605     return true;
606
607     }
608
609     private void InitializeSingleSource(Object JavaDoc src)
610     {
611     reachableNodes.clear();
612     reachableEdges.clear();
613     pei.clear();
614     distance.clear();
615     distance.put(src, new IntContainer(0));
616     }
617
618     private void getReachableNodesAndEdges(Object JavaDoc src)
619     {
620     LinkedList worklist = new LinkedList();
621
622     reachableNodes.add(src);
623     worklist.add(src);
624
625     while (!worklist.isEmpty())
626     {
627         Object JavaDoc from = worklist.removeFirst();
628
629         Hashtable targets = (Hashtable)sources.get(from);
630         if (targets == null)
631         continue;
632
633         Iterator targetIt = targets.keySet().iterator();
634         while (targetIt.hasNext())
635         {
636         Object JavaDoc target = targetIt.next();
637
638         if (!reachableNodes.contains(target))
639         {
640             worklist.add(target);
641             reachableNodes.add(target);
642         }
643
644         IntContainer weight = (IntContainer)targets.get(target);
645
646         reachableEdges.add(new WeightedDirectedEdge(from, target, weight.value));
647         }
648     }
649     }
650
651     private void Relax(Object JavaDoc from, Object JavaDoc to, int weight)
652     {
653     IntContainer dfrom = (IntContainer)distance.get(from);
654     IntContainer dto = (IntContainer)distance.get(to);
655
656     if (dfrom != null)
657     {
658         int vfrom = dfrom.value;
659         int vnew = vfrom+weight;
660         if (dto == null)
661         {
662         distance.put(to, new IntContainer(vnew));
663         pei.put(to, from);
664         }
665         else
666         {
667         int vto = dto.value;
668         if (vto > vnew)
669         {
670             distance.put(to, new IntContainer(vnew));
671             pei.put(to, from);
672         }
673         }
674     }
675     }
676
677
678 }
679
680
681
682
683
684
685
686
687
688
689
690
691
Popular Tags