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