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