|
1
19
20
25
26 package soot.jimple.toolkits.annotation.arraycheck;
27
28 import java.util.*;
29
30 class WeightedDirectedSparseGraph
31 {
32 private boolean isUnknown;
33
34
35 private Hashtable sources = new Hashtable();
36
37
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
70 public void addEdge(Object  from, Object to, int w)
71 {
72 if (this.isUnknown)
73 throw new RuntimeException ("Unknown graph can not have edges");
74
75 Hashtable targets = (Hashtable)sources.get(from);
76
77 if (targets == null)
78 {
79
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
104 public void addMutualEdges(Object from, Object to, int weight)
105 {
106 addEdge(from, to, weight);
107 addEdge(to, from, -weight);
108 }
109
110
112 public void removeEdge(Object from, Object 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 from, Object 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
137 public int edgeWeight(Object from, Object to)
138 {
139 Hashtable targets = (Hashtable)sources.get(from);
140
141 if (targets == null)
142 throw new RuntimeException ("No such edge ("+from+" ,"+to+") exists.");
143
144 IntContainer weight = (IntContainer)targets.get(to);
145 if (weight == null)
146 throw new RuntimeException ("No such edge ("+from+", "+to+") exists.");
147
148 return weight.value;
149 }
150
151
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 srcKey = firstSrcIt.next();
176 Hashtable src1 = (Hashtable)this.sources.get(srcKey);
177 Hashtable src2 = (Hashtable)othergraph.sources.get(srcKey);
178
179
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 target = targetIt.next();
193
194 IntContainer w1 = (IntContainer)src1.get(target);
195 IntContainer w2 = (IntContainer)src2.get(target);
196
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
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 src = srcIt.next();
232 Hashtable thistargets = (Hashtable)this.sources.get(src);
233 Hashtable othertargets = (Hashtable)othersources.get(src);
234
235
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 target = targetIt.next();
248 IntContainer thisweight = (IntContainer)thistargets.get(target);
249 IntContainer otherweight = (IntContainer)othertargets.get(target);
250
251
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
270
271
272
273
274
275
276 public void killNode(Object 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 src = srcIt.next();
290
291 Hashtable targets = (Hashtable)sources.get(src);
292
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
306 public void updateWeight(Object which, int c)
307 {
308
309 Iterator srcIt = sources.keySet().iterator();
310
311 while (srcIt.hasNext())
312 {
313 Object 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
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 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
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 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 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
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 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 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 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 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 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 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 toString()
477 {
478 String 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 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 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 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 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 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
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 outedges.clear();
596 Iterator targetIt = distance.keySet().iterator();
597 while (targetIt.hasNext())
598 {
599 Object 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 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 src)
619 {
620 LinkedList worklist = new LinkedList();
621
622 reachableNodes.add(src);
623 worklist.add(src);
624
625 while (!worklist.isEmpty())
626 {
627 Object 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 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 from, Object 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 |
Java API By Example, From Geeks To Geeks.