Robust/src/Analysis/SSJava/HierarchyGraph.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.util.HashMap;
   7 import java.util.HashSet;
   8 import java.util.Iterator;
   9 import java.util.Map;
  10 import java.util.Set;
  11
  12 import IR.Descriptor;
  13 import IR.FieldDescriptor;
  14 import IR.VarDescriptor;
  15
  16 public class HierarchyGraph {
  17
  18   Descriptor desc;
  19
  20   String name;
  21
  22   // graph structure
  23   Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
  24   Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
  25
  26   Map<Descriptor, HNode> mapDescToHNode;
  27   Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
  28   Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
  29   Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
  30                                                  // node
  31   Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
  32
  33   // data structures for a combination node
  34   Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
  35   Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
  36   Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
  37   Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
  38
  39   Map<HNode, Set<HNode>> mapNormalNodeToSCNodeReachToSet;
  40
  41   Set<HNode> nodeSet;
  42
  43   // for the lattice generation
  44   Map<HNode, Integer> mapHNodeToUniqueIndex;
  45   Map<HNode, Set<Integer>> mapHNodeToBasis;
  46   Set<Integer> BASISTOPELEMENT;
  47
  48   public HierarchyGraph() {
  49     mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
  50     mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
  51     mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
  52     mapDescToHNode = new HashMap<Descriptor, HNode>();
  53     mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  54     mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
  55     mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
  56     mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  57     nodeSet = new HashSet<HNode>();
  58
  59     mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
  60     mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
  61
  62     mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
  63
  64     mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
  65
  66     mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
  67
  68     mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
  69   }
  70
  71   public Descriptor getDesc() {
  72     return desc;
  73   }
  74
  75   public void setDesc(Descriptor desc) {
  76     this.desc = desc;
  77   }
  78
  79   public String getName() {
  80     return name;
  81   }
  82
  83   public void setName(String name) {
  84     this.name = name;
  85   }
  86
  87   public HierarchyGraph(Descriptor d) {
  88     this();
  89     desc = d;
  90     name = d.toString();
  91   }
  92
  93   public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
  94     return mapHNodeToDescSet;
  95   }
  96
  97   public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
  98     mapHNodeToDescSet.putAll(map);
  99   }
 100
 101   public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
 102     return mapHNodeToCurrentHNode;
 103   }
 104
 105   public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
 106     return mapHNodeNameToCurrentHNode;
 107   }
 108
 109   public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
 110     this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
 111   }
 112
 113   public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
 114     this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
 115   }
 116
 117   public Map<Descriptor, HNode> getMapDescToHNode() {
 118     return mapDescToHNode;
 119   }
 120
 121   public void setMapDescToHNode(Map<Descriptor, HNode> map) {
 122     mapDescToHNode.putAll(map);
 123   }
 124
 125   public Set<HNode> getNodeSet() {
 126     return nodeSet;
 127   }
 128
 129   public void addEdge(HNode srcHNode, HNode dstHNode) {
 130
 131     if (!nodeSet.contains(srcHNode)) {
 132       nodeSet.add(srcHNode);
 133     }
 134
 135     if (!nodeSet.contains(dstHNode)) {
 136       nodeSet.add(dstHNode);
 137     }
 138
 139     Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
 140
 141     if (possibleCycleSet.size() > 0) {
 142
 143       if (possibleCycleSet.size() == 1) {
 144         if (dstHNode.isSharedNode()) {
 145           // it has already been assigned shared node.
 146         } else {
 147           dstHNode.setSharedNode(true);
 148         }
 149         return;
 150       }
 151
 152       System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
 153       HNode newMergeNode = mergeNodes(possibleCycleSet, false);
 154       newMergeNode.setSharedNode(true);
 155
 156     } else {
 157       getIncomingNodeSet(dstHNode).add(srcHNode);
 158       getOutgoingNodeSet(srcHNode).add(dstHNode);
 159       // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
 160     }
 161
 162   }
 163
 164   public void addNode(HNode node) {
 165     nodeSet.add(node);
 166   }
 167
 168   public void addEdge(Descriptor src, Descriptor dst) {
 169
 170     if (src.equals(LocationInference.LITERALDESC)) {
 171       // in this case, we do not need to add a source hnode
 172       // just add a destination hnode
 173       getHNode(dst);
 174     } else {
 175       HNode srcHNode = getHNode(src);
 176       HNode dstHNode = getHNode(dst);
 177       addEdge(srcHNode, dstHNode);
 178     }
 179
 180   }
 181
 182   public void setParamHNode(Descriptor d) {
 183     getHNode(d).setSkeleton(true);
 184   }
 185
 186   public HNode getHNode(Descriptor d) {
 187     if (!mapDescToHNode.containsKey(d)) {
 188       HNode newNode = new HNode(d);
 189
 190       if (d instanceof FieldDescriptor) {
 191         newNode.setSkeleton(true);
 192       }
 193
 194       if (d.equals(LocationInference.TOPDESC)) {
 195         newNode.setSkeleton(true);
 196       }
 197
 198       String symbol = d.getSymbol();
 199       if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) {
 200         newNode.setSkeleton(true);
 201       }
 202
 203       mappingDescriptorToHNode(d, newNode);
 204       nodeSet.add(newNode);
 205     }
 206     return mapDescToHNode.get(d);
 207   }
 208
 209   public HNode getHNode(String name) {
 210     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 211       HNode node = (HNode) iterator.next();
 212       if (node.getName().equals(name)) {
 213         return node;
 214       }
 215     }
 216     return null;
 217   }
 218
 219   private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
 220     mapDescToHNode.put(desc, node);
 221     if (!mapHNodeToDescSet.containsKey(node)) {
 222       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 223     }
 224     mapHNodeToDescSet.get(node).add(desc);
 225   }
 226
 227   public HierarchyGraph generateSkeletonGraph() {
 228
 229     // compose a skeleton graph that only consists of fields or parameters
 230     HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
 231     skeletonGraph.setName(desc + "_SKELETON");
 232
 233     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 234       HNode src = (HNode) iterator.next();
 235       if (src.isSkeleton()) {
 236         Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
 237         if (reachSet.size() > 0) {
 238           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
 239             HNode dst = (HNode) iterator2.next();
 240             skeletonGraph.addEdge(src, dst);
 241           }
 242         } else {
 243           skeletonGraph.addNode(src);
 244         }
 245       }
 246     }
 247
 248     skeletonGraph.setMapDescToHNode(getMapDescToHNode());
 249     skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
 250     skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 251     skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 252
 253     return skeletonGraph;
 254
 255   }
 256
 257   private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
 258
 259     Set<HNode> visited = new HashSet<HNode>();
 260     Set<HNode> connected = new HashSet<HNode>();
 261     recurReachSkeletonSet(node, connected, visited);
 262
 263     return connected;
 264   }
 265
 266   public void removeRedundantEdges() {
 267
 268     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 269       HNode src = (HNode) iterator.next();
 270       Set<HNode> connectedSet = getOutgoingNodeSet(src);
 271       Set<HNode> toberemovedSet = new HashSet<HNode>();
 272       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 273         HNode dst = (HNode) iterator2.next();
 274         Set<HNode> otherNeighborSet = new HashSet<HNode>();
 275         otherNeighborSet.addAll(connectedSet);
 276         otherNeighborSet.remove(dst);
 277         for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
 278           HNode neighbor = (HNode) iterator3.next();
 279           if (reachTo(neighbor, dst, new HashSet<HNode>())) {
 280             toberemovedSet.add(dst);
 281           }
 282         }
 283       }
 284       if (toberemovedSet.size() > 0) {
 285         connectedSet.removeAll(toberemovedSet);
 286
 287         for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
 288           HNode node = (HNode) iterator2.next();
 289           getIncomingNodeSet(node).remove(src);
 290         }
 291
 292       }
 293     }
 294
 295   }
 296
 297   public void simplifyHierarchyGraph() {
 298     removeRedundantEdges();
 299     combineRedundantNodes(false);
 300   }
 301
 302   public void simplifySkeletonCombinationHierarchyGraph() {
 303     removeRedundantEdges();
 304     combineRedundantNodes(true);
 305   }
 306
 307   public void combineRedundantNodes(boolean onlyCombinationNodes) {
 308     // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
 309     boolean isUpdated = false;
 310     do {
 311       isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
 312     } while (isUpdated);
 313   }
 314
 315   public Set<HNode> getIncomingNodeSet(HNode node) {
 316     if (!mapHNodeToIncomingSet.containsKey(node)) {
 317       mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
 318     }
 319     return mapHNodeToIncomingSet.get(node);
 320   }
 321
 322   public Set<HNode> getOutgoingNodeSet(HNode node) {
 323     if (!mapHNodeToOutgoingSet.containsKey(node)) {
 324       mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
 325     }
 326     return mapHNodeToOutgoingSet.get(node);
 327   }
 328
 329   private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
 330     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 331       HNode node1 = (HNode) iterator.next();
 332
 333       if ((onlyCombinationNodes && (!node1.isCombinationNode()))
 334           || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
 335         continue;
 336       }
 337
 338       Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
 339       Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
 340
 341       for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
 342         HNode node2 = (HNode) iterator2.next();
 343
 344         if ((onlyCombinationNodes && (!node2.isCombinationNode()))
 345             || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
 346           continue;
 347         }
 348
 349         if (!isEligibleForMerging(node1, node2)) {
 350           continue;
 351         }
 352
 353         if (!node1.equals(node2)) {
 354
 355           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 356           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 357
 358           if (incomingNodeSet1.equals(incomingNodeSet2)
 359               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 360             // need to merge node1 and node2
 361
 362             Set<HNode> mergeSet = new HashSet<HNode>();
 363             mergeSet.add(node1);
 364             mergeSet.add(node2);
 365             mergeNodes(mergeSet, onlyCombinationNodes);
 366             return true;
 367           }
 368
 369         }
 370       }
 371
 372     }
 373     return false;
 374   }
 375
 376   private boolean isEligibleForMerging(HNode node1, HNode node2) {
 377
 378     if (node1.isSharedNode() || node2.isSharedNode()) {
 379
 380       // if either of nodes is a shared node,
 381       // all descriptors of node1 & node2 should have a primitive type
 382
 383       Set<Descriptor> descSet = new HashSet<Descriptor>();
 384       descSet.addAll(getDescSetOfNode(node1));
 385       descSet.addAll(getDescSetOfNode(node2));
 386
 387       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 388         Descriptor desc = (Descriptor) iterator.next();
 389         if (!LocationInference.isPrimitive(desc)) {
 390           return false;
 391         }
 392       }
 393       return true;
 394     }
 395     return false;
 396   }
 397
 398   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 399     getIncomingNodeSet(dstHNode).add(srcHNode);
 400     getOutgoingNodeSet(srcHNode).add(dstHNode);
 401     System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 402   }
 403
 404   private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
 405
 406     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 407     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 408
 409     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 410       HNode node = (HNode) iterator.next();
 411       incomingNodeSet.addAll(getIncomingNodeSet(node));
 412       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 413     }
 414
 415     String nodeName;
 416     boolean isMergeNode = false;
 417     if (onlyCombinationNodes) {
 418       nodeName = "Comb" + (LocationInference.locSeed++);
 419     } else {
 420       nodeName = "Node" + (LocationInference.locSeed++);
 421       isMergeNode = true;
 422     }
 423     HNode newMergeNode = new HNode(nodeName);
 424     newMergeNode.setMergeNode(isMergeNode);
 425
 426     nodeSet.add(newMergeNode);
 427     nodeSet.removeAll(set);
 428
 429     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 430     boolean hasSkeleton = false;
 431     boolean hasShared = false;
 432     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 433       HNode inNode = (HNode) iterator.next();
 434       if (inNode.isSkeleton()) {
 435         hasSkeleton = true;
 436       }
 437       if (inNode.isSharedNode()) {
 438         hasShared = true;
 439       }
 440     }
 441     // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
 442     // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
 443     newMergeNode.setSkeleton(hasSkeleton);
 444     newMergeNode.setSharedNode(hasShared);
 445
 446     System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
 447
 448     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 449       HNode node = (HNode) iterator.next();
 450       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 451       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 452         Descriptor desc = (Descriptor) iterator2.next();
 453         mappingDescriptorToHNode(desc, newMergeNode);
 454       }
 455     }
 456
 457     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 458       HNode inNode = (HNode) iterator.next();
 459       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 460       outSet.removeAll(set);
 461       if (!set.contains(inNode)) {
 462         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 463       }
 464     }
 465
 466     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 467       HNode outNode = (HNode) iterator.next();
 468       Set<HNode> inSet = getIncomingNodeSet(outNode);
 469       inSet.removeAll(set);
 470       if (!set.contains(outNode)) {
 471         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 472       }
 473     }
 474
 475     Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
 476     for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
 477       HNode merged = iter.next();
 478       if (merged.isSkeleton()) {
 479         mergedSkeletonNode.add(merged);
 480       }
 481     }
 482
 483     // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
 484     // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 485     mapMergeNodetoMergingSet.put(newMergeNode, set);
 486     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 487       HNode mergedNode = (HNode) iterator.next();
 488       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
 489     }
 490
 491     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 492       HNode hNode = (HNode) iterator.next();
 493       System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
 494     }
 495
 496     System.out.println();
 497
 498     return newMergeNode;
 499   }
 500
 501   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
 502     if (curNode.isMergeNode()) {
 503       Set<HNode> mergingSet = getMergingSet(curNode);
 504       mergingSet.add(curNode);
 505       System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
 506           + mergingSet + " newNode=" + newNode);
 507       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
 508         HNode mergingNode = (HNode) iterator.next();
 509         mapHNodeToCurrentHNode.put(mergingNode, newNode);
 510         mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
 511       }
 512     } else {
 513       mapHNodeToCurrentHNode.put(curNode, newNode);
 514       mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
 515     }
 516   }
 517
 518   public HNode getCurrentHNode(HNode node) {
 519     if (!mapHNodeToCurrentHNode.containsKey(node)) {
 520       mapHNodeToCurrentHNode.put(node, node);
 521     }
 522     return mapHNodeToCurrentHNode.get(node);
 523   }
 524
 525   public HNode getCurrentHNode(String nodeName) {
 526     return mapHNodeNameToCurrentHNode.get(nodeName);
 527   }
 528
 529   private Set<HNode> getMergingSet(HNode mergeNode) {
 530     Set<HNode> mergingSet = new HashSet<HNode>();
 531     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
 532     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
 533       HNode node = (HNode) iterator.next();
 534       if (node.isMergeNode()) {
 535         mergingSet.add(node);
 536         mergingSet.addAll(getMergingSet(node));
 537       } else {
 538         mergingSet.add(node);
 539       }
 540     }
 541     return mergingSet;
 542   }
 543
 544   public Set<Descriptor> getDescSetOfNode(HNode node) {
 545     if (!mapHNodeToDescSet.containsKey(node)) {
 546       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 547     }
 548     return mapHNodeToDescSet.get(node);
 549   }
 550
 551   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 552     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 553     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 554       HNode n = iterator.next();
 555       if (n.equals(dst)) {
 556         return true;
 557       }
 558       if (!visited.contains(n)) {
 559         visited.add(n);
 560         if (reachTo(n, dst, visited)) {
 561           return true;
 562         }
 563       }
 564     }
 565     return false;
 566   }
 567
 568   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 569
 570     Set<HNode> outSet = getOutgoingNodeSet(node);
 571     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 572       HNode outNode = (HNode) iterator.next();
 573
 574       if (outNode.isSkeleton()) {
 575         connected.add(outNode);
 576       } else if (!visited.contains(outNode)) {
 577         visited.add(outNode);
 578         recurReachSkeletonSet(outNode, connected, visited);
 579       }
 580     }
 581
 582   }
 583
 584   public Set<HNode> getReachableSCNodeSet(HNode startNode) {
 585     // returns the set of hnodes which is reachable from the startNode and is either SC node or a
 586     // node which is directly connected to the SC nodes
 587     Set<HNode> reachable = new HashSet<HNode>();
 588     Set<HNode> visited = new HashSet<HNode>();
 589     visited.add(startNode);
 590     recurReachableNodeSet(startNode, visited, reachable);
 591     return reachable;
 592   }
 593
 594   public Set<HNode> getSCNodeReachToSet(HNode node) {
 595     if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
 596       mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
 597     }
 598     return mapNormalNodeToSCNodeReachToSet.get(node);
 599   }
 600
 601   private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
 602
 603     Set<HNode> outSet = getOutgoingNodeSet(node);
 604     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 605       HNode out = (HNode) iterator.next();
 606
 607       if (!visited.contains(out)) {
 608         visited.add(out);
 609         Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
 610         mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
 611         if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
 612           reachable.add(out);
 613         } else {
 614           visited.add(out);
 615           recurReachableNodeSet(out, visited, reachable);
 616         }
 617
 618       }
 619
 620     }
 621
 622   }
 623
 624   private Set<HNode> reachableFromSCNode(HNode node) {
 625     Set<HNode> visited = new HashSet<HNode>();
 626     visited.add(node);
 627     Set<HNode> reachable = new HashSet<HNode>();
 628     recurReachableFromSCNode(node, reachable, visited);
 629     return reachable;
 630   }
 631
 632   private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
 633     Set<HNode> inNodeSet = getIncomingNodeSet(node);
 634     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 635       HNode inNode = (HNode) iterator.next();
 636       if (inNode.isSkeleton() || inNode.isCombinationNode()) {
 637         visited.add(inNode);
 638         reachable.add(inNode);
 639       } else if (!visited.contains(inNode)) {
 640         visited.add(inNode);
 641         recurReachableFromSCNode(inNode, reachable, visited);
 642       }
 643     }
 644   }
 645
 646   public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
 647       Set<HNode> combinationNodeSet) {
 648     Set<HNode> reachable = new HashSet<HNode>();
 649     Set<HNode> visited = new HashSet<HNode>();
 650     visited.add(node);
 651     recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
 652     return reachable;
 653   }
 654
 655   public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
 656       Set<HNode> reachable, Set<HNode> combinationNodeSet) {
 657
 658     Set<HNode> outSet = getOutgoingNodeSet(node);
 659     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 660       HNode out = (HNode) iterator.next();
 661
 662       if (!visited.contains(out)) {
 663         visited.add(out);
 664         if (out.isSkeleton()) {
 665           reachable.add(out);
 666         } else if (out.isCombinationNode()) {
 667           if (combinationNodeSet == null) {
 668             reachable.add(out);
 669           } else if (!combinationNodeSet.contains(out)) {
 670             reachable.add(out);
 671           } else {
 672             recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 673                 combinationNodeSet);
 674           }
 675         } else {
 676           recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 677               combinationNodeSet);
 678         }
 679
 680       }
 681
 682     }
 683
 684   }
 685
 686   public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
 687     Set<HNode> visited = new HashSet<HNode>();
 688     return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
 689   }
 690
 691   public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
 692
 693     Set<HNode> outSet = getOutgoingNodeSet(node);
 694     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 695       HNode out = (HNode) iterator.next();
 696       // if (!visited.contains(out)) {
 697       if (out.isCombinationNode() || out.isSkeleton()) {
 698         return out;
 699       } else {
 700         // visited.add(out);
 701         return getDirectlyReachableSkeletonCombinationNodeFrom(out);
 702       }
 703     }
 704     // }
 705
 706     return null;
 707   }
 708
 709   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 710     // if an edge from src to dst introduces a new cycle flow,
 711     // the method returns the set of elements consisting of the cycle
 712     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 713     // if the dst node reaches to the src node, the new relation
 714     // introduces a cycle to the lattice
 715     if (dst.equals(src)) {
 716       cycleNodeSet.add(dst);
 717       cycleNodeSet.add(src);
 718     } else if (reachTo(dst, src)) {
 719       cycleNodeSet.add(dst);
 720       cycleNodeSet.add(src);
 721       getInBetweenElements(dst, src, cycleNodeSet);
 722     }
 723     return cycleNodeSet;
 724   }
 725
 726   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 727     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 728     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 729       HNode cur = (HNode) iterator.next();
 730       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 731         nodeSet.add(cur);
 732         getInBetweenElements(cur, end, nodeSet);
 733       }
 734     }
 735   }
 736
 737   public boolean reachTo(HNode node1, HNode node2) {
 738     return reachTo(node1, node2, new HashSet<HNode>());
 739   }
 740
 741   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 742     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 743       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 744     }
 745     return mapCombinationNodeToCombineNodeSet.get(node);
 746   }
 747
 748   public HNode getCombinationNode(Set<HNode> combineSet) {
 749     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 750       String name = "COMB" + (LocationInference.locSeed++);
 751       HNode node = new HNode(name);
 752       node.setCombinationNode(true);
 753       nodeSet.add(node);
 754       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 755       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 756     }
 757
 758     return mapCombineNodeSetToCombinationNode.get(combineSet);
 759   }
 760
 761   public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
 762     return mapCombineNodeSetToCombinationNode;
 763   }
 764
 765   public Set<Set<HNode>> getCombineNodeSet() {
 766     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 767   }
 768
 769   public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
 770     // add a new combination node where parameter/field flows are actually combined.
 771
 772     simpleHierarchyGraph.identifyCombinationNodes();
 773
 774     Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
 775     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 776       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 777       System.out.println("--combineSet=" + combineSet);
 778       HNode combinationNode = getCombinationNode(combineSet);
 779       System.out.println("--combinationNode=" + combinationNode);
 780       // add an edge from a skeleton node to a combination node
 781       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 782         HNode inSkeletonNode = (HNode) iterator2.next();
 783         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 784         // + inSkeletonNode.getDescriptor());
 785         HNode srcNode;
 786         if (inSkeletonNode.getDescriptor() == null) {
 787           // the node is merging one...
 788           srcNode = inSkeletonNode;
 789         } else {
 790           srcNode = getHNode(inSkeletonNode.getDescriptor());
 791         }
 792         // System.out.println("--srcNode=" + srcNode);
 793         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 794       }
 795
 796       // add an edge from the combination node to outgoing nodes
 797       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 798       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 799         HNode curNode = (HNode) iterator2.next();
 800         if (curNode.isCombinationNode()) {
 801           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 802           HNode outNode = getCombinationNode(combineNode);
 803           addEdgeWithNoCycleCheck(combinationNode, outNode);
 804         } else if (curNode.isSkeleton()) {
 805           // HNode dstNode2 = getHNode(curNode.getDescriptor());
 806           HNode dstNode = getCurrentHNode(curNode);
 807           // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
 808           // + dstNode2);
 809           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 810         }
 811       }
 812
 813       System.out.println("--");
 814
 815     }
 816
 817   }
 818
 819   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 820     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 821       // need to create a new combination node
 822       String nodeName = "Comb" + (LocationInference.locSeed++);
 823       HNode newCombinationNode = new HNode(nodeName);
 824       newCombinationNode.setCombinationNode(true);
 825
 826       nodeSet.add(newCombinationNode);
 827       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 828
 829       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 830         HNode reachToNode = (HNode) iterator.next();
 831         addEdge(reachToNode, newCombinationNode);
 832       }
 833
 834     }
 835
 836     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 837     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 838       HNode reachableNode = (HNode) iterator.next();
 839       addEdge(combinationNode, reachableNode);
 840     }
 841
 842   }
 843
 844   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 845
 846     Set<HNode> reachToSet = new HashSet<HNode>();
 847     Set<HNode> visited = new HashSet<HNode>();
 848     recurSkeletonReachTo(node, reachToSet, visited);
 849
 850     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 851     // because the node is not directly connected to the combination node
 852
 853     removeRedundantReachToNodes(reachToSet);
 854
 855     return reachToSet;
 856   }
 857
 858   private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
 859
 860     Set<HNode> toberemoved = new HashSet<HNode>();
 861     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 862       HNode cur = (HNode) iterator.next();
 863
 864       for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 865         HNode dst = (HNode) iterator2.next();
 866         if (!cur.equals(dst) && reachTo(cur, dst)) {
 867           // it is redundant
 868           toberemoved.add(cur);
 869         }
 870       }
 871     }
 872     reachToSet.removeAll(toberemoved);
 873   }
 874
 875   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 876
 877     Set<HNode> inSet = getIncomingNodeSet(node);
 878     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 879       HNode inNode = (HNode) iterator.next();
 880
 881       if (inNode.isSkeleton()) {
 882         reachToSet.add(inNode);
 883       } else if (!visited.contains(inNode)) {
 884         visited.add(inNode);
 885         recurSkeletonReachTo(inNode, reachToSet, visited);
 886       }
 887     }
 888
 889   }
 890
 891   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 892     return mapHNodeToOutgoingSet;
 893   }
 894
 895   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 896     return mapHNodeToIncomingSet;
 897   }
 898
 899   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 900     mapHNodeToOutgoingSet.clear();
 901     Set<HNode> keySet = in.keySet();
 902     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 903       HNode key = (HNode) iterator.next();
 904       Set<HNode> inSet = in.get(key);
 905       Set<HNode> newSet = new HashSet<HNode>();
 906       newSet.addAll(inSet);
 907       mapHNodeToOutgoingSet.put(key, newSet);
 908     }
 909   }
 910
 911   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 912     mapHNodeToIncomingSet.clear();
 913     Set<HNode> keySet = in.keySet();
 914     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 915       HNode key = (HNode) iterator.next();
 916       Set<HNode> inSet = in.get(key);
 917       Set<HNode> newSet = new HashSet<HNode>();
 918       newSet.addAll(inSet);
 919       mapHNodeToIncomingSet.put(key, newSet);
 920     }
 921   }
 922
 923   public void setNodeSet(Set<HNode> inSet) {
 924     nodeSet.clear();
 925     nodeSet.addAll(inSet);
 926   }
 927
 928   public HierarchyGraph clone() {
 929     HierarchyGraph clone = new HierarchyGraph();
 930     clone.setDesc(getDesc());
 931     clone.setName(getName());
 932     clone.setNodeSet(getNodeSet());
 933     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 934     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 935     clone.setMapDescToHNode(getMapDescToHNode());
 936     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 937     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 938     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 939     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 940
 941     return clone;
 942   }
 943
 944   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 945     return mapMergeNodetoMergingSet;
 946   }
 947
 948   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 949     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 950   }
 951
 952   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 953
 954     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 955       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 956     }
 957     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 958   }
 959
 960   public void identifyCombinationNodes() {
 961
 962     // 1) set combination node flag if a node combines more than one skeleton node.
 963     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 964       HNode node = (HNode) iterator.next();
 965       if (!node.isSkeleton()) {
 966         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 967         if (reachToSet.size() > 1) {
 968           // if (countSkeletonNodes(reachToSet) > 1) {
 969           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
 970           System.out.println("-set combinationnode=" + node);
 971           node.setCombinationNode(true);
 972           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 973         }
 974       }
 975     }
 976
 977     // 2) compute the outgoing set that needs to be directly connected from the combination node
 978     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 979       HNode node = (HNode) iterator.next();
 980       if (node.isCombinationNode()) {
 981         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 982         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
 983         addMapCombineSetToOutgoingSet(combineSet, outSet);
 984       }
 985     }
 986
 987   }
 988
 989   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
 990     return mapCombinationNodeToCombineNodeSet;
 991   }
 992
 993   public int countSkeletonNodes(Set<HNode> set) {
 994     int count = 0;
 995
 996     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 997       HNode node = (HNode) iterator.next();
 998       Set<Descriptor> descSet = getDescSetOfNode(node);
 999       count += descSet.size();
1000     }
1001
1002     return count;
1003   }
1004
1005   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1006     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1007       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1008     }
1009     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1010   }
1011
1012   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1013     // the method returns the set of nodes that are reachable from the current node
1014     // and do not combine the same set of skeleton nodes...
1015
1016     Set<HNode> visited = new HashSet<HNode>();
1017     Set<HNode> reachableSet = new HashSet<HNode>();
1018     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1019
1020     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1021
1022     return reachableSet;
1023   }
1024
1025   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1026       Set<HNode> reachableSet, Set<HNode> visited) {
1027
1028     Set<HNode> outSet = getOutgoingNodeSet(node);
1029     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1030       HNode outNode = (HNode) iterator.next();
1031
1032       if (outNode.isCombinationNode()) {
1033         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1034         if (combineSetOfOutNode.equals(combineSet)) {
1035           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1036               visited);
1037         } else {
1038           reachableSet.add(outNode);
1039         }
1040       } else if (outNode.isSkeleton()) {
1041         reachableSet.add(outNode);
1042       }
1043
1044     }
1045
1046   }
1047
1048   private Set<HNode> getReachableNodeSetFrom(HNode node) {
1049
1050     Set<HNode> reachableSet = new HashSet<HNode>();
1051     Set<HNode> visited = new HashSet<HNode>();
1052
1053     recurReachableNodeSetFrom(node, reachableSet, visited);
1054
1055     return reachableSet;
1056   }
1057
1058   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1059
1060     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1061     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1062       HNode outNode = (HNode) iterator.next();
1063       reachableSet.add(outNode);
1064       if (!visited.contains(outNode)) {
1065         visited.add(outNode);
1066         recurReachableNodeSetFrom(outNode, reachableSet, visited);
1067       }
1068     }
1069
1070   }
1071
1072   public void assignUniqueIndexToNode() {
1073     int idx = 1;
1074     System.out.println("nodeSet=" + nodeSet);
1075     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1076       HNode node = (HNode) iterator.next();
1077       mapHNodeToUniqueIndex.put(node, idx);
1078       idx++;
1079     }
1080
1081     BASISTOPELEMENT = new HashSet<Integer>();
1082     for (int i = 1; i < idx + 1; i++) {
1083       BASISTOPELEMENT.add(i);
1084     }
1085   }
1086
1087   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1088
1089     // assign a unique index to a node
1090     assignUniqueIndexToNode();
1091
1092     // compute basis for each node
1093     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1094       HNode node = (HNode) iterator.next();
1095
1096       if (notGenerateSet.contains(node)) {
1097         System.out.println("%%%SKIP =" + node);
1098         continue;
1099       }
1100       Set<Integer> basis = new HashSet<Integer>();
1101       basis.addAll(BASISTOPELEMENT);
1102
1103       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1104       System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1105       System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1106       // if a node is reachable from the current node
1107       // need to remove the index of the reachable node from the basis
1108
1109       basis.remove(getHNodeIndex(node));
1110       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1111         HNode reachableNode = (HNode) iterator2.next();
1112         System.out.println("reachableNode=" + reachableNode);
1113         System.out.println("getHNodeIndex(reachableNode))="
1114             + mapHNodeToUniqueIndex.get(reachableNode));
1115         int idx = getHNodeIndex(reachableNode);
1116         basis.remove(idx);
1117       }
1118
1119       mapHNodeToBasis.put(node, basis);
1120     }
1121
1122     // construct the basis set
1123
1124     BasisSet basisSet = new BasisSet();
1125
1126     Set<HNode> keySet = mapHNodeToBasis.keySet();
1127     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1128       HNode node = (HNode) iterator.next();
1129       Set<Integer> basis = mapHNodeToBasis.get(node);
1130       basisSet.addElement(basis, node);
1131     }
1132
1133     return basisSet;
1134
1135   }
1136
1137   public int getHNodeIndex(HNode node) {
1138     return mapHNodeToUniqueIndex.get(node).intValue();
1139   }
1140
1141   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1142     return mapHNodeToUniqueIndex;
1143   }
1144
1145   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1146     return mapHNodeToBasis;
1147   }
1148
1149   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1150
1151     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1152     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1153     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1154       HNode key = (HNode) iterator.next();
1155
1156       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1157         combinationNodeSet.add(key);
1158       }
1159     }
1160
1161     return combinationNodeSet;
1162   }
1163
1164   public void writeGraph() {
1165
1166     String graphName = "hierarchy" + name;
1167     graphName = graphName.replaceAll("[\\W]", "");
1168
1169     try {
1170       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1171
1172       bw.write("digraph " + graphName + " {\n");
1173
1174       Iterator<HNode> iter = nodeSet.iterator();
1175
1176       Set<HNode> addedNodeSet = new HashSet<HNode>();
1177
1178       while (iter.hasNext()) {
1179         HNode u = iter.next();
1180
1181         Set<HNode> outSet = getOutgoingNodeSet(u);
1182
1183         if (outSet.size() == 0) {
1184           if (!addedNodeSet.contains(u)) {
1185             drawNode(bw, u);
1186             addedNodeSet.add(u);
1187           }
1188         } else {
1189           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1190             HNode v = (HNode) iterator.next();
1191             if (!addedNodeSet.contains(u)) {
1192               drawNode(bw, u);
1193               addedNodeSet.add(u);
1194             }
1195             if (!addedNodeSet.contains(v)) {
1196               drawNode(bw, v);
1197               addedNodeSet.add(v);
1198             }
1199             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1200           }
1201         }
1202
1203       }
1204
1205       bw.write("}\n");
1206       bw.close();
1207
1208     } catch (IOException e) {
1209       e.printStackTrace();
1210     }
1211   }
1212
1213   public boolean contains(HNode node) {
1214     return nodeSet.contains(node);
1215   }
1216
1217   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1218     return getOutgoingNodeSet(src).contains(dst);
1219   }
1220
1221   private String convertMergeSetToString(Set<HNode> mergeSet) {
1222     String str = "";
1223     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1224       HNode merged = (HNode) iterator.next();
1225       if (merged.isMergeNode()) {
1226         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1227       } else {
1228         str += " " + merged.getName();
1229       }
1230     }
1231     return str;
1232   }
1233
1234   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1235     String nodeName;
1236     if (node.isMergeNode()) {
1237       nodeName = node.getNamePropertyString();
1238       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1239       nodeName += ":" + convertMergeSetToString(mergeSet);
1240     } else {
1241       nodeName = node.getNamePropertyString();
1242     }
1243     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1244   }
1245
1246   public int countHopFromTopLocation(HNode node) {
1247
1248     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1249     int count = 0;
1250     if (inNodeSet.size() > 0) {
1251       count = recurCountHopFromTopLocation(inNodeSet, 1);
1252     }
1253
1254     return count;
1255   }
1256
1257   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1258
1259     int max = curCount;
1260     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1261       HNode node = (HNode) iterator.next();
1262       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1263       if (inNodeSet.size() > 0) {
1264         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1265         if (max < recurCount) {
1266           max = recurCount;
1267         }
1268       }
1269     }
1270     return max;
1271   }
1272
1273 }