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