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